Search System — inverted index, sharding, ranking e latência sub-100ms

Em 1999, Doug Cutting trabalhava como engenheiro freelancer e começou a escrever, num cubículo emprestado, uma biblioteca de busca em Java porque acreditava que o mundo precisava de uma implementação open-source madura de inverted index — todas as alternativas da época eram fechadas ou acadêmicas demais. Ele chamou de Lucene, juntando o sobrenome da esposa com o "Lu" do meio do nome dela. Cinco anos depois, doou o código para a Apache Foundation. Em 2010, Shay Banon, um engenheiro israelense que estava desempregado tentando construir um app de receitas para sua esposa, percebeu que Lucene resolvia indexação mas não distribuição — então embrulhou Lucene numa camada de rede e cluster management, e batizou de Elasticsearch. Hoje, praticamente toda função de busca em produto SaaS no mundo é Lucene rodando em algum lugar — Elasticsearch, OpenSearch, Solr, ou diretamente. Entender search systems é, em grande parte, entender por que essas decisões de design de 1999 ainda dominam.

O que torna um sistema de busca diferente de uma consulta SQL com LIKE '%foo%' é a estrutura de dados. Um LIKE num banco relacional faz full scan de cada linha; para 1 bilhão de documentos, isso é proibitivo independentemente do hardware. A solução fundamental — descoberta nas décadas de 1960-70 em sistemas de bibliotecas e refinada por motores como AltaVista nos anos 90 — é o inverted index: em vez de mapear documento → palavras, mapear palavra → documentos. Essa inversão transforma uma operação O(N×M) num lookup O(1) na palavra seguido de uma intersecção O(K) entre listas de IDs. O resto do sistema de busca — distribuição, ranking, atualização em tempo real, snippets — são todos otimizações e extensões em torno dessa ideia central.

Requisitos e estimation

Requisitos funcionais:

• Busca textual em 1B de documentos (ex: produtos, artigos, posts)
• Multi-termo com operadores implícitos (AND por default) e filtros (categoria, preço, data)
• Ranking por relevância — não cronológico, não alfabético
• Autocomplete enquanto o usuário digita
• Correção ortográfica ("dyd you mean...")
• Snippets com highlight dos termos da query
• Indexação de novos documentos em até 1s (near real-time)

Requisitos não-funcionais:

• Latência P99 <100ms (P50 <30ms)
• Throughput: 10.000 queries/s no pico (1000 QPS sustentado)
• Disponibilidade 99.95% (a busca quebrada degrada todo o produto)
• Resultados consistentes para a mesma query no mesmo segundo

# Estimation — catálogo de 1B documentos

# Tamanho de um documento médio: 2KB de texto + 1KB de metadados = 3KB
# Storage bruto dos documentos: 1B × 3KB = 3TB
# Inverted index é tipicamente 30-50% do tamanho dos documentos (depende de compressão)
# Index size: ~1TB

# Vocabulário (termos únicos): ~10M termos em corpus diverso
# Postings list média por termo: 1B docs × probabilidade média de ocorrência
# Termos raros: dezenas de postings; termos comuns ("o", "de"): bilhões
# Distribuição segue Zipf — 100 termos mais comuns representam ~50% das ocorrências

# Capacity por shard:
# Um shard Lucene/Elasticsearch saudável: 10-50GB de índice
# 1TB de índice / 30GB por shard = ~35 shards
# Com replicação (RF=3 para alta disponibilidade): 105 shards físicos
# Hardware: 105 shards × 32GB RAM cada = ~30 servidores de 128GB

# Latência target (P99 <100ms) com scatter-gather:
# 35 shards consultados em paralelo, latência limitada pelo shard mais lento
# Cada shard: lookup no inverted index (~5ms) + ranking dos top-K (~10ms) = 15ms
# Coordenador: agregação + re-ranking final (~5ms) + serialização (~5ms) = 10ms
# Total: 15ms (shard) + 10ms (coord) + rede (10ms) = 35ms P50; P99 ~80ms

# Throughput:
# 10k QPS / 35 shards = ~285 QPS por shard
# Lucene single-shard suporta 1000+ QPS em hardware moderno → folga de 3.5x

# Indexação:
# 100M novos docs/dia = ~1200 docs/s sustentado, pico 5000 docs/s
# Lucene single-shard: ~10k docs/s sustentado → folga confortável
# Refresh interval de 1s = compromisso entre near-real-time e overhead de I/O

Inverted index — a estrutura fundamental

O inverted index mapeia termo → lista de documentos que contêm o termo. A lista, chamada de postings list, geralmente armazena também a posição do termo no documento (para queries de frase) e a frequência (para ranking). É a inversão dessa estrutura — em vez do natural "para cada documento, quais palavras" — que torna a busca tratável em escala.

# Construção conceitual do inverted index:

# Documentos:
# doc_1: "the quick brown fox"
# doc_2: "the lazy brown dog"
# doc_3: "quick fox jumps over lazy dog"

# Pipeline de tokenização:
# 1. Lowercase: "the quick brown fox"
# 2. Tokenize (split por whitespace + pontuação): [the, quick, brown, fox]
# 3. Stop words (remover "the", "a", "of"...): [quick, brown, fox]
# 4. Stemming (Porter, Snowball): [quick, brown, fox] (sem mudança aqui)
#    "jumps" → "jump"; "running" → "run"; "cats" → "cat"

# Inverted index resultante:
# {
#   "quick":  [(doc_1, freq=1, pos=[1]), (doc_3, freq=1, pos=[0])],
#   "brown":  [(doc_1, freq=1, pos=[2]), (doc_2, freq=1, pos=[2])],
#   "fox":    [(doc_1, freq=1, pos=[3]), (doc_3, freq=1, pos=[1])],
#   "lazy":   [(doc_2, freq=1, pos=[1]), (doc_3, freq=1, pos=[4])],
#   "dog":    [(doc_2, freq=1, pos=[3]), (doc_3, freq=1, pos=[5])],
#   "jump":   [(doc_3, freq=1, pos=[2])],
#   "over":   [(doc_3, freq=1, pos=[3])]
# }

# Query "quick fox" (AND implícito):
# 1. Lookup postings("quick") → [doc_1, doc_3]
# 2. Lookup postings("fox")   → [doc_1, doc_3]
# 3. Intersecção (merge sorted) → [doc_1, doc_3]
# 4. Ranking dos candidatos (TF-IDF/BM25) → ordenar por score
# 5. Retornar top-K

# Por que postings são sempre sorted por doc_id:
# - Intersecção de N listas sorted é O(M*N) com merge linear
# - Permite skip lists para pular grandes ranges quando uma lista é muito menor
# - Compressão delta-encoding: armazenar diferenças entre IDs (1, 5, 12 → 1, 4, 7)
#   reduz storage em ~70% para postings densas

A maior parte da inteligência de um engine de busca está em como esse índice é armazenado, comprimido e atualizado. Lucene usa uma estrutura chamada FST (Finite State Transducer) para o term dictionary — permite lookup O(1) mesmo com 100M termos únicos sem carregar tudo em memória. Os postings ficam em arquivos separados, lidos por mmap.

# Lucene storage layout (simplificado):

# Term dictionary (em RAM, via mmap do .tim/.tip):
# - FST mapeia "brown" → offset 0x4A2C no arquivo de postings
# - FST é compacto: 50M termos cabem em ~500MB RAM

# Postings file (.doc, .pos, .pay):
# - Para cada termo: lista comprimida de (doc_id, freq, positions)
# - Delta encoding + varint para doc_ids
# - Frame-of-reference (FOR) + PFOR-Delta para compressão eficiente
# - Block-encoded: blocos de 128 docs comprimidos juntos → cache-friendly

# Stored fields (.fdt):
# - O texto original ou metadata do documento (para snippets/retrieval)
# - Comprimido com LZ4 ou Deflate
# - Stored != indexed: pode-se indexar sem armazenar e vice-versa

# DocValues (.dvd):
# - Column-store por campo, otimizado para sorting/aggregations
# - Ex: sort by price, aggregate by category
# - Disjunto do inverted index — diferente estrutura para diferente query pattern

# Segments:
# - Um índice é composto de N segments (cada um é um mini-índice imutável)
# - Novos docs vão para um novo segment (in-memory, "buffer")
# - Periodicamente flush para disco (commit)
# - Em background, merge de segments pequenos em maiores (merge policy)
# - Delete: marcador no .liv file ("liveDocs"); doc físico só some no próximo merge

Tokenização e analisadores

Tokenização é o passo que determina o que pode ser buscado. Decisões aparentemente simples — case sensitivity, stemming, sinônimos — têm impacto direto na relevância e no recall. O erro mais comum: usar o analisador default para todos os campos.

# Analyzer = CharFilter → Tokenizer → TokenFilter chain

# Exemplo: analisador para busca em produtos (português)

# 1. CharFilters:
#    - HTML strip (remover tags se o conteúdo vem de HTML)
#    - Mapeamento de caracteres: ç→c, ã→a, ó→o (NFD normalization)

# 2. Tokenizer:
#    - StandardTokenizer (split por whitespace + pontuação, respeita Unicode)
#    - Alternativas: WhitespaceTokenizer, NGramTokenizer, KeywordTokenizer

# 3. TokenFilters (aplicados em sequência):
#    - Lowercase
#    - StopFilter: remover "o", "a", "de", "para"... (lista pt-BR)
#    - SynonymFilter: "celular" ↔ "smartphone" ↔ "telefone"
#    - StemmerFilter: "rodando" → "rod"; "casas" → "cas" (Snowball pt-BR)
#    - ASCIIFoldingFilter: garantir que "ação" e "acao" matchem

# CRÍTICO: o mesmo analyzer DEVE ser aplicado na indexação E na query
# Se indexar com stemming mas buscar sem, "rodando" no doc não casa com "rodando" na query
# (o índice tem "rod", a query busca "rodando")

# Analyzers diferentes para campos diferentes:
# - title: standard + stemming agressivo (boost de recall)
# - description: standard + stemming leve
# - sku: keyword (sem tokenização — match exato)
# - tags: lowercase only (sem stemming — termos curados)

# Multi-field indexing (mesmo conteúdo, analyzers diferentes):
# field "title" indexado três vezes:
#   - title (com stemming → recall)
#   - title.exact (sem stemming → precisão para frases exatas)
#   - title.autocomplete (edge n-grams → busca como você digita)
# Query usa o sub-field apropriado conforme o caso

# Custos de stemming agressivo:
# "computação" → "comput"
# "computador" → "comput"
# Ambos casam, mas perde-se a distinção semântica
# Tradeoff: recall (achar mais) vs precision (achar o certo)

Sharding: documento vs termo

Um índice de 1TB não cabe num único servidor — precisa ser distribuído. Existem duas estratégias fundamentais, com propriedades opostas.

# Estratégia 1: SHARDING POR DOCUMENTO (document-partitioned)
# Cada shard tem um subconjunto dos documentos, com índice completo localmente
# Particionamento: hash(doc_id) % N_shards

# Shard 0: docs cujo hash % 35 == 0 (cerca de 28M docs)
#   Inverted index local: todos os termos dos 28M docs deste shard
# Shard 1: docs cujo hash % 35 == 1
#   Inverted index local: todos os termos dos 28M docs deste shard
# ...

# Query "quick fox":
# 1. Coordinator dispara a query para TODOS os 35 shards (scatter)
# 2. Cada shard executa a query local: lookup + intersect + rank top-K (geralmente K=20)
# 3. Coordinator coleta resultados (gather)
# 4. Re-ranking global: ordena os 35 × 20 = 700 candidatos
# 5. Retorna top-10 ao cliente

# Vantagens:
# - Indexação trivialmente paralela: cada doc vai para um shard, não há coordenação
# - Adicionar/remover docs é local (sem reorganização global)
# - Falha de um shard degrada parcialmente, não totalmente

# Desvantagens:
# - Toda query toca TODOS os shards (overhead de coordenação)
# - Term frequency (df) é local — IDF aproximado, não exato
#   Fix: distributed frequency calculation (DFS_QUERY_THEN_FETCH no Elasticsearch)
# - Top-K em cada shard pode perder docs relevantes:
#   se o top-1 global está no shard X mas não no top-K do shard X, é descartado
#   Mitigação: K > 10 (geralmente K = max(num_results × 2, 20))

# Estratégia 2: SHARDING POR TERMO (term-partitioned)
# Cada shard tem TODOS os documentos, mas apenas um subconjunto de termos
# Particionamento: hash(termo) % N_shards

# Shard 0: postings de termos que hash % 35 == 0 (talvez "quick", "brown", ...)
# Shard 1: postings de termos que hash % 35 == 1 (talvez "fox", "lazy", ...)
# ...

# Query "quick fox":
# 1. Coordinator roteia "quick" para shard_A, "fox" para shard_B
# 2. shard_A retorna postings de "quick"; shard_B retorna postings de "fox"
# 3. Coordinator faz a intersecção
# 4. Ranking final

# Vantagens:
# - Apenas N shards consultados, onde N = número de termos da query (geralmente 2-4)
# - Term frequency é exata (toda a lista está num shard)
# - Eficiente para queries muito específicas

# Desvantagens:
# - Indexação é difícil: um doc com 100 palavras precisa atualizar 100 shards distintos
# - Transferência de postings entre shards no merge (overhead de rede)
# - Termos hot (palavras comuns) criam hotspots impossíveis de balancear
# - Mais complexo operacionalmente — quase ninguém usa

# Quem usa cada um:
# - Document-partitioned: Lucene/Elasticsearch/Solr, Google interno (versão simplificada)
# - Term-partitioned: pesquisa acadêmica, casos especializados
# - HÍBRIDO (Google real): document-partitioned dentro de DC, term-partitioned entre DCs
#   ou usado em sub-índices especializados

Query execution: scatter-gather

# Fluxo de uma query distribuída (document-partitioned):

# 1. Cliente → Query Coordinator (HTTP/gRPC)
#    GET /search?q=quick+fox&from=0&size=10

# 2. Query Coordinator:
async def execute_search(query: str, from_: int, size: int):
    # Parse + análise da query (mesma análise da indexação)
    parsed = query_parser.parse(query)
    analyzed = analyzer.analyze(parsed)  # ["quick", "fox"]

    # Phase 1: QUERY (scatter)
    # Cada shard retorna apenas (doc_id, score) — não os documentos completos
    shard_results = await asyncio.gather(*[
        shard.search(analyzed, size=from_ + size)
        for shard in active_shards
    ])
    # Timeout por shard (ex: 200ms) — se um shard não responder, ignorar e seguir
    # Resultado: list[list[(doc_id, score)]]

    # Phase 2: REDUCE (merge)
    # Heap dos top (from_ + size) globais
    global_top = heapq.nlargest(
        from_ + size,
        chain.from_iterable(shard_results),
        key=lambda x: x.score
    )
    # Aplicar paginação: top_global[from_ : from_ + size]
    page = global_top[from_:from_ + size]

    # Phase 3: FETCH (gather)
    # Buscar os documentos completos dos shards corretos
    docs_by_shard = defaultdict(list)
    for hit in page:
        shard_id = hit.doc_id % N_SHARDS
        docs_by_shard[shard_id].append(hit.doc_id)

    fetched = await asyncio.gather(*[
        shards[shard_id].fetch(doc_ids)
        for shard_id, doc_ids in docs_by_shard.items()
    ])

    # Phase 4: ASSEMBLE
    return assemble_response(page, fetched)

# Por que duas phases (query + fetch)?
# - Transferir apenas (doc_id, score) na phase 1 é barato
# - Documentos completos podem ser 10KB+; transferir só os 10 que vão ao usuário
# - Se transferíssemos tudo: 35 shards × 20 docs × 10KB = 7MB por query (proibitivo)

# Variantes:
# - QUERY_THEN_FETCH (default): a descrita acima
# - DFS_QUERY_THEN_FETCH: phase 0 extra para calcular IDF global → ranking mais preciso
#   custo: roundtrip adicional, +20-50ms latência
# - QUERY_AND_FETCH: combina em uma fase, mais rápido mas só correto se size > total docs

# Tail latency: o problema dos shards lentos
# P99 do sistema = P99 do shard mais lento (não a média)
# Mitigações:
# - Hedged requests: enviar para 2 shards (primary + replica), usar quem responder primeiro
# - Partial results: timeout por shard, marcar resultado como "incompleto"
# - Adaptive timeout: baseado em latência histórica do shard

Ranking: TF-IDF, BM25 e além

Ranking é o que diferencia busca de filtragem. A intersecção de postings dá os documentos que contêm os termos; o ranking ordena por relevância. As fórmulas clássicas, descobertas nos anos 70-90, ainda são o baseline de qualquer sistema moderno — mesmo quando o ranking final é feito por ML.

# TF-IDF: a intuição fundamental

# TF (Term Frequency): quantas vezes o termo aparece no documento
# Mais ocorrências → mais relevante (assumindo que o termo é informativo)
tf(termo, doc) = count(termo, doc)

# IDF (Inverse Document Frequency): quão raro é o termo no corpus inteiro
# Termos raros (ocorrem em poucos docs) carregam mais informação
# log para suavizar: a diferença entre "1 doc" e "10 docs" importa mais que entre "1M" e "10M"
idf(termo) = log(N / df(termo))
# N = total de docs; df = doc frequency (em quantos docs o termo aparece)

# Score TF-IDF de um doc para uma query (soma sobre os termos):
score(doc, query) = sum(tf(t, doc) * idf(t) for t in query.terms)

# Problemas do TF-IDF puro:
# 1. Documentos longos têm TF maior naturalmente — fica enviesado para docs grandes
# 2. TF cresce linearmente — 100 ocorrências do termo é 100x melhor que 1? Não é
# 3. Sem normalização por tamanho do documento

# BM25 (Best Matching 25 — Robertson et al., 1994):
# Refinamento do TF-IDF que corrige os problemas acima
# É o ranking default do Elasticsearch desde a v5

import math

def bm25(tf, df, doc_len, avg_doc_len, N, k1=1.2, b=0.75):
    """
    tf: term frequency no doc
    df: document frequency do termo no corpus
    doc_len: tamanho do doc em tokens
    avg_doc_len: tamanho médio dos docs no corpus
    N: número total de docs
    k1: saturação de TF (1.2-2.0)
    b: normalização por tamanho (0 = sem; 1 = completa)
    """
    idf = math.log(1 + (N - df + 0.5) / (df + 0.5))
    norm = tf * (k1 + 1) / (tf + k1 * (1 - b + b * doc_len / avg_doc_len))
    return idf * norm

# Por que k1 cria saturação:
# Com k1=1.2, o ganho de TF se aproxima de um teto:
#   TF=1  → norm ≈ 1.0
#   TF=2  → norm ≈ 1.5
#   TF=10 → norm ≈ 2.0
#   TF=100 → norm ≈ 2.1  (quase nada de ganho a partir daqui)
# Modela a intuição: 100 ocorrências NÃO é 100x melhor que 1

# Por que b normaliza por tamanho:
# Doc de 100 palavras com 5 menções de "fox" é mais relevante que
# doc de 10000 palavras com as mesmas 5 menções
# b=0.75 ajusta o score em proporção ao doc_len / avg_doc_len

# Boosting por campo (queries multi-campo):
# Mesmo termo na URL/título importa mais que no body
final_score = (
    3.0 * bm25(...) [no campo title] +
    1.5 * bm25(...) [no campo headers] +
    1.0 * bm25(...) [no campo body]
)

# Re-ranking com ML (Learning to Rank):
# - BM25 dá os top-200 (fast, full corpus)
# - Modelo ML (LambdaMART, neural ranker) re-ranqueia os top-200 → top-10
# - Features: BM25 score, click-through rate histórico, freshness, autor, popularidade
# - Treinamento: judgements humanos OU clickstream (clicks como proxy de relevância)
# - Trade-off: latência (+20-50ms) vs qualidade (quase sempre vale a pena para search comercial)

Near-real-time indexing: o segredo dos segments

Como atualizar um índice gigante em tempo quase real sem parar o serviço? A resposta de Lucene: nunca modificar o índice no lugar. Todo índice é uma coleção de segments imutáveis; novos documentos vão para um novo segment; segments velhos são compactados em background.

# Lifecycle de um documento no Lucene/Elasticsearch:

# 1. Indexação:
#    - Doc chega → adicionado ao in-memory buffer (no segment ainda)
#    - Buffer cresce até atingir o threshold (16MB default) OU refresh_interval (1s default)

# 2. Refresh:
#    - In-memory buffer vira um in-memory segment SEARCHABLE
#    - Aqui a busca já encontra o doc — "near-real-time"
#    - Mas ainda NÃO está no disco — risco de perda em crash

# 3. Translog (write-ahead log):
#    - Em paralelo, o doc também foi escrito num translog persistente
#    - Translog garante durabilidade mesmo antes do flush para disco
#    - Default: translog é fsync'd a cada request OU a cada 5s

# 4. Flush:
#    - In-memory segment é escrito para disco como um novo segment file
#    - Translog antigo é descartado
#    - Default: a cada 30 minutos OU translog atinge 512MB

# 5. Merge:
#    - Background: pequenos segments são merged em maiores
#    - Tiered Merge Policy: agrupa segments de tamanhos similares
#    - Durante o merge, os segments antigos continuam servindo queries
#    - Quando o novo segment está pronto, atomicamente substitui os antigos
#    - Segments antigos são deletados

# Por que segments imutáveis?
# - Sem locking: leitura nunca bloqueia escrita
# - Filesystem caching é eficiente: arquivos não mudam → cache válido por mais tempo
# - Incremental backup: copiar segments novos é suficiente (os antigos não mudaram)
# - Snapshot consistency: lista de segments num momento = snapshot atômico

# Update e Delete são "soft":
# - Delete: marca doc_id no .liv file ("liveDocs") — bitset de docs ativos
#   Doc físico permanece no segment; queries filtram pelo liveDocs
# - Update: equivale a delete + insert → marca antigo, insere novo no buffer
# - O espaço só é recuperado no próximo merge que processa o segment

# Custo do refresh frequente:
# - Cada refresh cria um novo segment file
# - Muitos segments pequenos = muitos arquivos = muitos file handles + I/O
# - Index time vs Search time tradeoff:
#   refresh_interval=1s  → indexação rápida, mais merges, query overhead
#   refresh_interval=30s → indexação batched, menos overhead, mas resultados "atrasados"
# - Bulk loading: setar refresh_interval=-1 (desativado) durante load inicial, depois reabilitar

# Translog vs commit:
# - Commit (flush) é caro: fsync de todos os segments, ~segundos
# - Translog é fsync'd a cada operação → muito mais frequente, muito mais barato
# - Em caso de crash: ao iniciar, Elasticsearch replay translog desde o último commit
# - Tradeoff: durabilidade total vs throughput (translog assíncrono é 3-5x mais rápido)

Autocomplete, snippets e correção

# Autocomplete: dois approaches comuns

# Approach 1: Edge N-grams (indexação especial)
# Para o termo "search", indexa: ["s", "se", "sea", "sear", "searc", "search"]
# Query "sea" → match em qualquer doc com termo começando com "sea"
# Vantagem: prefix queries são naturalmente rápidas (lookup direto no index)
# Desvantagem: índice cresce ~10x por campo de autocomplete

# Approach 2: Completion Suggester (estrutura dedicada)
# Lucene/Elasticsearch tem uma estrutura chamada FST especializada para autocomplete
# Cada termo é indexado como sequência → FST permite percorrer todos os prefixos em O(L)
# Suporta pesos por sugestão (popularidade) e fuzziness (typos)
# Sub-milissegundo independente do tamanho do corpus

# Highlight / Snippets:
# - Para cada hit, extrair fragmentos do doc original onde os termos aparecem
# - Marcar os termos com ... para renderização
# - Strategy 1: re-scan do stored field (mais simples, mais lento)
# - Strategy 2: term_vectors armazenados na indexação (mais rápido, mais storage)
#   Term vectors = (termo, posição, offset) por documento, permite extrair contexto sem re-scan

# Exemplo de resultado com snippet:
# {
#   "doc_id": 12345,
#   "title": "How to design search systems at scale",
#   "snippet": "...this article explains how to build a robust search
#              system for catalogs of billions of documents...",
#   "score": 8.42
# }

# Spell correction ("Did you mean?"):
# Quando a query não retorna resultados (ou retorna poucos), sugerir alternativas

# Approach 1: Edit distance (Levenshtein)
# Para cada termo da query sem matches, buscar termos do índice com edit_distance ≤ 2
# Usar BK-tree ou Levenshtein automaton para tornar a busca tratável
# "serch" → ["search" (1), "serch" → "porch" (2), "perch" (2)]

# Approach 2: Trigrams / n-grams
# Indexar trigrams: "search" → ["sea", "ear", "arc", "rch"]
# Query "serch" → trigrams ["ser", "erc", "rch"]
# Termos compartilhando muitos trigrams são candidatos → ordenar por overlap

# Approach 3: Frequency-based (estatística do corpus)
# Sugestões devem ser termos comuns no índice (não pode sugerir typo por typo)
# Combinar: edit_distance ≤ 2 AND doc_frequency > threshold
# Para multi-termo: usar log-likelihood de cada candidato e o contexto

# Approach 4 (state-of-the-art): query log mining
# Coletar pares (query_with_typo, query_correta) do clickstream histórico
# Treinar modelo seq2seq ou embedding-based → sugestões aprendidas
# Google usa basicamente isso desde meados dos anos 2000

Arquitetura completa

                                Cliente
                                   │
                                   ▼
                       ┌─────────────────────┐
                       │  Search API Gateway │ (rate limit, auth, A/B)
                       └──────────┬──────────┘
                                  │
                  ┌───────────────┴───────────────┐
                  ▼                               ▼
        ┌───────────────────┐         ┌──────────────────────┐
        │ Query Coordinator │         │ Autocomplete Service │
        └─────────┬─────────┘         │  (FST in-memory)     │
                  │                   └──────────────────────┘
        scatter-gather paralelo
                  │
   ┌──────┬──────┼──────┬──────┐
   ▼      ▼      ▼      ▼      ▼
 Shard1 Shard2 Shard3 ... Shard35     (Lucene indices, RF=3)
   │      │      │      │      │
   └──────┴──┬───┴──────┴──────┘
             │ scores
             ▼
        ┌────────────────┐
        │ Reduce + Top-K │
        └────┬───────────┘
             │ top doc_ids
             ▼
        ┌────────────────┐
        │  Fetch docs    │ (de volta aos shards corretos)
        └────┬───────────┘
             │
             ▼
        ┌────────────────┐
        │ ML Re-ranker   │ (LambdaMART / neural — opcional)
        └────┬───────────┘
             │
             ▼
        ┌────────────────┐
        │ Snippet / hl   │
        └────┬───────────┘
             │ resposta
             ▼
          Cliente

Pipeline de indexação (separado da query path):

  Source (DB, Kafka topic, crawler)
     │ events: doc_created, doc_updated, doc_deleted
     ▼
  ┌────────────────────┐
  │ Ingestion Service  │ (Kafka consumer)
  └──────────┬─────────┘
             │ batch (1000 docs / 5s)
             ▼
  ┌────────────────────┐
  │  Index Builder     │ (analyzer, validação, enrichment)
  └──────────┬─────────┘
             │ routing por hash(doc_id)
             ▼
  ┌──────────┴──────────┐
  ▼                     ▼
Shard primary    Shard replica (RF=3)
  │                     │
  └──────── ack ────────┘
             │
             ▼
  Cliente notificado (commit_id)

Caches:
  - Edge cache (CDN): queries muito populares com TTL curto (10-60s)
  - Query result cache (Redis): top-N por query normalizada, TTL 5min
  - Field data cache (Lucene): valores de sort/aggregation em memória
  - OS page cache: o "cache" mais importante — segments mmap'd, hot data fica em RAM

Observabilidade essencial:
  - Latência por phase: parse / shard query / reduce / fetch / rerank
  - Tail latency por shard (P99 individual)
  - Cache hit ratio
  - Indexação lag (event_timestamp - searchable_at)
  - Top-N queries (para identificar candidatos a cache especial)
  - Queries sem resultados (sinal de gap de cobertura ou typos não corrigidos)

Decisões de engenharia

Perguntas de entrevista

Exercícios práticos