Construindo uma busca por filtros: atualizar sem interromper

Até aqui, tratamos o índice como uma fotografia. Catálogos reais não ficam parados: itens são publicados, vendidos, pausados, removidos e corrigidos; preço, localização e disponibilidade mudam.

Alterar um bit parece barato. O problema é alterar todos os bits relacionados ao item sem deixar uma query observar metade do estado antigo e metade do novo.

Leitores permanecem numa geração enquanto escritores constroem a seguinte.

Eu modelaria cada réplica de shard como uma máquina de estados reconstruível, combinando o regime de componentes e merges do LSM-tree com um protocolo de commit log e recuperação mais próximo do descrito pelo Bigtable:[1][4]

State(S) = Base(B) ⊕ WAL(B+1 ... S)

A base imutável é otimizada para leitura. O delta contém o estado recente usado pelas consultas. O log é a fonte durável que permite reconstruir esse delta. Isso também separa quatro tipos de estado:

• índice persistente: segmentos, dicionários, postings e índice direto;
• recuperação persistente: log, checkpoints e manifests;
• estado operacional: epoch, papel da réplica, watermarks e migrações;
• estado temporário: caches, heaps e consultas em andamento.

O último pode desaparecer num crash. Os três primeiros precisam permitir reconstrução e diagnóstico.

Update exige conhecer o antes

Se um item muda de cor=azul para cor=verde, não basta ligar o bit verde. Precisamos desligar o azul.

Isso exige uma representação reversa:

internal_id → atributos indexados atuais

O caminho de escrita pode então calcular um diff:

antes: categoria=celular, cor=azul,  preço_bucket=10
agora: categoria=celular, cor=verde, preço_bucket=12

remove: cor=azul,  preço_bucket=10
adiciona: cor=verde, preço_bucket=12

Para delete, podemos desligar o item do conjunto live imediatamente e registrar um tombstone. Limpar todos os demais conjuntos pode acontecer depois, porque toda query termina com AND live. O tombstone transforma remoção física em uma etapa de manutenção, sem permitir que o item continue aparecendo.

Esse atalho tem custo: bits mortos ocupam espaço e aumentam trabalho até a compactação. O conjunto live vira parte crítica da correção.

Uma camada de sobreposição evita editar postings antigos. Para cada campo, o delta registra quais documentos mudaram e os novos valores:

effective(field=value)
  = (base(field=value) − changed[field])
    ∪ delta(field=value)

effective = effective ∩ live_documents

O conjunto atual é calculado; ele não exige reescrever o bitmap antigo no disco.

Se o preço do documento 42 mudou de 2.000 para 2.500, changed[price] remove 42 de qualquer resultado numérico da base. O delta fornece o preço atual. Se um campo virou nulo, o documento aparece em changed[field], mas não entra em posting novo algum. O mesmo mecanismo cobre remoção de atributo sem ressuscitar o valor anterior.

Não editar o snapshot dos leitores

Uma solução simples é separar o estado em duas famílias:

• segmentos imutáveis, publicados e seguros para leitura concorrente;
• delta mutável, pequeno, que recebe mudanças recentes.

Uma query escolhe uma geração e combina os segmentos pertencentes a ela. Escritores continuam acumulando mudanças fora do snapshot. Eu usaria um escritor lógico por shard, processando mutações em lote e publicando raízes imutáveis para múltiplos leitores — uma escolha próxima ao modelo single-writer/multiple-reader descrito pelo Earlybird.[3] Periodicamente, o sistema congela o delta, constrói novos segmentos e publica um novo mapa por troca atômica.

geração 41 = [S0, S1, delta_7, tombstones_7]

geração 42 = [S2_compactado, delta_8, tombstones_8]

O leitor que começou na geração 41 termina nela. Novas queries recebem a 42. Os arquivos ou páginas da 41 só podem ser reclamados quando não houver leitor que ainda os referencie.

O mecanismo pode ser implementado com contadores de referência, épocas ou outro esquema de reclamation. O nome importa menos que o invariante: publicar primeiro, remover depois de provar que nenhum leitor depende da versão antiga.

Enquanto base e delta coexistem, a leitura resolve cada item pela versão aceita mais nova. Um tombstone mais novo vence qualquer versão antiga; caso contrário, uma compactação ou réplica atrasada poderia ressuscitar um item removido. O tombstone só pode ser descartado depois que nenhum snapshot, réplica ou processo de recuperação ainda puder observar a versão anterior.

O protocolo de escrita

Um evento de atualização precisa carregar identidade e ordem suficientes para ser reaplicado:

item_id
sequence_number
operação
atributos indexados

Um caminho possível:

1. validar a sequência do item
2. registrar a intenção num log durável
3. consultar o estado anterior
4. aplicar diff ao delta e ao reverse map
5. avançar o watermark aplicado
6. confirmar a atualização para o produtor

O sequence_number torna retries idempotentes: receber novamente a versão 18 depois de já aplicar a 18 não repete efeitos. Receber a 17 depois da 18 deve ser ignorado ou enviado para reconciliação, nunca aplicado como se fosse novo.

Durabilidade e visibilidade são momentos diferentes. O evento pode estar salvo e ainda não aparecer nas consultas. Eu manteria marcadores separados:

received_sequence
 durable_sequence
committed_sequence
  applied_sequence
published_sequence

Durable significa gravado localmente. Committed, aceito pelo grupo de réplicas. Applied, incorporado ao delta. Published, visível numa geração de leitura. Uma confirmação ao produtor precisa dizer qual dessas garantias oferece.

Para read-after-write, o produtor pode receber a sequência confirmada e enviar minimum_visible_sequence numa busca posterior. O coordenador escolhe uma réplica cujo published_sequence já alcançou esse valor ou falha explicitamente dentro da deadline.

O delta continua reconstruível pelo log, mas reproduzir horas de mutações após cada reinício é caro. Checkpoints imutáveis serializam changed sets, postings recentes, overrides, versões e dicionários do delta. Depois do snapshot e do checkpoint, a réplica reproduz apenas o trecho posterior do WAL.

Inserts e o espaço de IDs

Um insert recebe um ID interno no delta ativo. Como segmentos usam espaços locais densos, o mesmo número pode existir em segmentos diferentes desde que a identidade completa inclua o segmento:

(segment_id, local_doc_id)

Isso reduz o tamanho de cada bitmap e facilita particionamento. Na compactação, itens vivos podem receber novas posições locais, pois todos os bitmaps, a coluna de ordenação e o mapa reverso do novo segmento são reconstruídos juntos.

O ID público permanece estável. O mapa de localização muda somente quando a nova geração é publicada. Uma query nunca mistura o mapa novo com bitmaps antigos.

O manifest é o commit do índice

Eu não criaria um arquivo por (campo, valor). Milhões de postings virariam milhões de arquivos pequenos, desperdiçando metadados e I/O aleatório. Um segmento agrupa estruturas em poucos arquivos grandes:

segment.meta
dictionaries
postings.index + postings.data
forward.index  + forward.data
numeric.index  + numeric.data
sort.index     + sort.data
live-documents
checksums

postings.index localiza o payload por (field_id, value_id) e registra offset, comprimento, cardinalidade e representação. O manifest não contém os dados; ele referencia exatamente os segmentos, checkpoint, sequência e schema que formam uma geração consistente.

A regra é simples: um arquivo só faz parte do índice depois de aparecer num manifest publicado. Arquivos novos são escritos em área temporária, persistidos, verificados e só então referenciados. Um crash anterior à troca deixa lixo órfão, não uma geração parcialmente visível.

Compactação é uma transação de metadados

Compactar não significa apenas juntar arquivos. A operação precisa:

1. escolher segmentos e um watermark de entrada;
2. copiar somente itens vivos;
3. reconstruir bitmaps, ordenações e reverse maps;
4. incorporar tombstones cobertos;
5. validar cardinalidades e checksums;
6. produzir um novo manifesto imutável;
7. publicar o manifesto como nova geração;
8. reter a geração anterior até seus leitores terminarem;
9. remover arquivos antigos de forma recuperável.

Se a máquina falhar antes da publicação, o novo segmento é lixo órfão e a geração anterior continua válida. Se falhar depois da publicação, o manifesto precisa permitir descobrir quais arquivos pertencem à geração nova. Essa fronteira transforma uma sequência longa de I/O numa mudança atômica pequena: trocar o ponteiro do manifesto autoritativo.

A ideia se relaciona à família de estruturas log-structured: absorver escrita em componentes recentes e transformar o layout por merges posteriores.[1] Não precisamos adotar uma implementação específica para usar o princípio. Estratégias híbridas para índices invertidos mostram ainda outro ponto do espaço: manter postings longos separados e atualizá-los no lugar, enquanto listas curtas entram por merge.[2] Nossa escolha por base imutável e delta favorece snapshots e rollback, mas precisa ser comparada contra write amplification e custo extra de leitura.

Quanto tempo uma mudança pode esperar?

Há escolhas legítimas:

• aplicar disponibilidade no delta em milissegundos;
• publicar atributos menos críticos em pequenos lotes;
• compactar apenas quando tombstones ou segmentos excederem um limite;
• bloquear uma confirmação até que determinada geração esteja replicada.

Essas políticas dependem do risco. Um item vendido que continua aparecendo produz uma experiência diferente de uma correção de descrição que demora alguns segundos. Um único SLA de indexação pode esconder prioridades distintas.

Também existe uma tensão entre freshness e eficiência. Deltas minúsculos atualizados a cada evento aumentam o número de componentes consultados. Lotes maiores melhoram amortização, mas atrasam visibilidade. A solução precisa medir ambos.

Verificação

O caminho mutável precisa de um oracle simples. Para um catálogo pequeno, mantemos uma implementação de referência que varre linhas e comparamos seu resultado com o índice após sequências aleatórias de:

• insert;
• update de uma ou várias facetas;
• delete;
• retry duplicado;
• evento fora de ordem;
• compactação;
• crash antes e depois da publicação.

Propriedades úteis:

popcount(live) = quantidade de itens visíveis
resultado_indexado(query, geração)
  = resultado_scan(query, snapshot_da_mesma_geração)
compactar não altera o resultado observável
reaplicar um evento não altera o estado

Agora o sistema encontra e conta sobre um catálogo em movimento. Mas os conjuntos não têm ordem. Para mostrar vinte resultados, ordenar por preço e buscar a página seguinte, precisamos combinar membership com uma ordem total e decidir o que um cursor significa quando o catálogo muda.

Referências

1. Patrick O’Neil, Edward Cheng, Dieter Gawlick e Elizabeth O’Neil. The Log-Structured Merge-Tree (LSM-Tree), 1996.
2. Stefan Büttcher, Charles L. A. Clarke e Brad Lushman. Hybrid Index Maintenance for Growing Text Collections, SIGIR 2006.
3. Michael Busch et al. Earlybird: Real-Time Search at Twitter, ICDE 2012.
4. Fay Chang et al. Bigtable: A Distributed Storage System for Structured Data, OSDI 2006.

Parte anterior: Contar facetas

Próxima parte: Ordenar e paginar sobre um catálogo em movimento