Construindo uma busca por filtros: fechar o contrato online

Chegamos a uma arquitetura com bitmaps, deltas, segmentos, cursores, shards e réplicas. Ainda não temos um serviço confiável.

Um serviço precisa dizer o que acontece entre a mudança de um item e sua aparição na busca, durante a perda de uma máquina, quando uma réplica atrasa e quando a carga ultrapassa a capacidade. Sem esses contratos, o diagrama descreve componentes, não comportamento.

Freshness, completude e geração fazem parte da resposta, mesmo quando não aparecem na interface.

O fluxo de indexação

O estado autoritativo do item produz mudanças ordenáveis por item ou partição:

item_id
sequence_number
operação
atributos indexados
occurred_at

Um indexador:

1. recebe e valida o evento;
2. persiste a intenção antes de confirmar;
3. ignora duplicatas já aplicadas;
4. rejeita ou reconcilia versões antigas;
5. atualiza delta, reverse map e tombstones;
6. avança seu watermark;
7. replica o estado necessário;
8. publica uma geração consultável.

O log permite reconstruir deltas depois de crash. Snapshots limitam quanto histórico precisa ser reaplicado. O manifesto vincula segmentos, checksums, watermarks e formato a uma geração.

manifest generation=43
  shard=7
  applied_through=9182044
  segments=[a3, b9, d1]
  tombstones=t8
  schema=5
  checksum=...

Uma query pode registrar esse identificador para auditoria e reprodução.

Freshness é uma função, não um adjetivo

“Quase em tempo real” não define um contrato. Podemos medir:

indexing_lag = published_at - occurred_at

Mas um único percentil também esconde casos importantes. O painel precisa separar:

• inserts;
• mudança de preço;
• indisponibilidade e delete;
• reindexação completa;
• shards e tenants;
• eventos fora de ordem;
• idade máxima, não apenas média.

A política pode priorizar remoções no delta e agrupar mudanças menos críticas. Isso reduz risco sem exigir que toda mutação siga o caminho mais caro.

Uma confirmação de escrita também precisa de significado: recebida em memória, persistida localmente, replicada, aplicada ao índice ou publicada para leitura. Usar a palavra “salvo” para todos esses estados apenas transfere ambiguidade ao cliente.

O índice de busca também não deve ser a autoridade final para estoque, preço ou possibilidade de compra. Ele encontra candidatos com uma freshness conhecida. Ao abrir ou comprar o item, o sistema transacional revalida existência, versão, estoque, preço e elegibilidade da oferta. Eventual consistency na busca não pode virar venda baseada em estado obsoleto.

Recuperação de uma réplica

Quando uma réplica reinicia:

1. lê o último manifesto válido
2. verifica segmentos e checksums
3. carrega o snapshot
4. descobre o watermark aplicado
5. reproduz o log posterior
6. valida cardinalidades e invariantes
7. anuncia readiness com geração e lag

Readiness não é “o processo está aceitando conexões”. É capacidade de responder uma classe de query dentro do contrato de freshness e completude.

Se o log necessário já expirou, a réplica precisa de novo snapshot. Essa transição é normal e deve ser testada; não pode depender de cópia manual durante um incidente.

O que precisa de consenso

Nem todo bitmap precisa passar por consenso a cada leitura. Segmentos imutáveis podem ser copiados, verificados por checksum e reconstruídos. O plano de controle, porém, precisa de uma única decisão vigente para:

• quem possui cada intervalo na routing_epoch atual;
• qual manifesto foi publicado para uma geração;
• até qual posição do log uma atualização está commitada;
• quem pode promover uma nova configuração;
• como impedir que um líder antigo continue publicando depois de substituído.

Um log replicado com maioria e fencing é um building block possível para essas transições.[1] A mudança de membros também precisa preservar sobreposição suficiente entre a configuração antiga e a nova. Sem isso, uma partição de rede pode produzir dois mapas ou manifests considerados autoritativos.

Isso não obriga a leitura de cada conjunto a consultar um quorum. Obriga a leitura a provar que sua geração deriva de um estado de controle commitado e que a réplica atende ao modo solicitado: líder, commitado, snapshot específico ou atraso limitado.

Consenso também não escolhe sozinho o contrato de disponibilidade. Dynamo mostra uma arquitetura que privilegia disponibilidade, versionamento e resolução de conflitos; chain replication explora outro ponto, buscando throughput e disponibilidade com garantias fortes para objetos.[4][5] Em presença de partição, o serviço ainda precisa declarar quando bloqueia, quando serve estado stale e quando aceita conflito.[6]

Deploy e reparticionamento são protocolos diferentes

Deploy troca o binário que executa a consulta. Reparticionamento troca a autoridade sobre uma faixa de documentos. Misturar os dois torna rollback e diagnóstico muito mais difíceis. Shard Manager destaca justamente que eventos planejados, como upgrades, são parte central do lifecycle de aplicações shardadas, e não uma exceção operacional.[3]

Os dois protocolos usam checkpoints e rollback, mas preservam invariantes diferentes.

Coordenadores stateless podem receber uma pequena parcela do tráfego e ser substituídos. Servidores de índice precisam respeitar as réplicas de cada shard:

ACTIVE → DRAINING → UPGRADING → CATCHING_UP → WARMING → READY

Antes de parar uma réplica, o controlador transfere a liderança, interrompe novas queries, espera as atuais, troca o processo, reproduz o log, aquece estruturas e reintroduz tráfego gradualmente. O lote é escolhido por shard e domínio de falha, não apenas por uma porcentagem de servidores.

Mudança de formato exige compatibilidade em etapas:

1. versão nova lê F1 e F2, mas continua escrevendo F1;
2. depois que todos leem F2, novos segmentos passam a escrevê-lo;
3. somente quando nenhum segmento F1 permanece ativo, o leitor antigo pode ser removido.

Assim, rollback não depende de reescrever o índice no meio do deploy.

O reparticionamento, por sua vez, é uma máquina de estados persistente. Slicer e Shard Manager oferecem dois antecedentes úteis: o primeiro separa roteamento rápido de decisão de placement fora do caminho crítico; o segundo trata placement, replicação e movimentação como lifecycle reutilizável.[2][3]

PLANNED → COPYING → CATCHING_UP → READY_TO_CUTOVER
        → CUTOVER_COMMITTED → RETIRING_OLD → COMPLETED

Um split constrói os filhos a partir de um snapshot do pai, reproduz o log posterior e define uma sequência de corte. O mapa troca atomicamente uma faixa pelo conjunto de filhos e incrementa a epoch. Um coordenador com mapa antigo recebe STALE_EPOCH e repete a query inteira; combinar resposta do pai com um filho poderia duplicar documentos e contagens.

Se um item muda justamente o campo usado no roteamento, eu usaria add-before-delete: indexar a versão nova no destino, confirmá-la e só então criar tombstone na origem. Durante a pequena sobreposição, o coordenador deduplica por item_id e mantém a maior versão.

Cópia de índice, compactação e deploy competem por CPU, disco, cache e rede. Um orçamento global limita bytes de transferência, réplicas em bootstrap e compactações pesadas. Um shard não deve ser simultaneamente dividido, migrado e convertido de formato.

Sobrecarregar a busca reduz trabalho útil

Cada consulta pode combinar dezenas de conjuntos, calcular centenas de counts e atingir dezenas de shards. Sem limites, uma pequena quantidade de queries amplas pode consumir toda a capacidade.

O serviço precisa de admissão:

• limite de filtros e valores por faceta;
• limite de counts solicitados;
• tamanho máximo de página;
• budget de CPU, bytes e fan-out;
• deadline propagada;
• filas limitadas por classe;
• cancelamento de trabalho expirado;
• retry budget centralizado.

Quando a capacidade acaba, aceitar tudo aumenta fila, faz respostas perderem deadline e dispara retries. Rejeitar cedo parte do trabalho pode preservar o goodput: respostas úteis concluídas a tempo.

Podemos também definir degradações explícitas, caso o produto as aceite:

• omitir counts não essenciais e sinalizar isso;
• limitar facetas de alta cardinalidade;
• servir snapshot um pouco mais antigo dentro de um bound;
• recusar paginação profunda;
• retornar erro de overload não-retriável por uma janela.

Resultado parcial apresentado como completo não é degradação; é corrupção do contrato.

Cache e invalidação

Há três níveis distintos:

1. cache de bitmaps ou blocos quentes;
2. cache de bases intermediárias de uma query;
3. cache da resposta final.

Todos precisam de geração. Um bitmap da geração 42 não pode ser combinado com tombstones da 43 sem uma regra formal. Uma resposta final pode ter TTL curto, mas TTL não prova que item removido deixou de aparecer a tempo.

Para invalidação urgente, o caminho de leitura pode sempre intersectar um pequeno conjunto atual de itens indisponíveis. Isso troca uma operação extra por remoção rápida enquanto caches maiores expiram ou mudam de geração.

Como provar correção

A arquitetura nasceu de um modelo simples; ele deve continuar como oracle.

Teste diferencial

Geramos um catálogo pequeno, uma sequência de updates e queries aleatórias. Comparamos:

scan de linhas no snapshot
versus
resultado do índice na mesma geração

Comparamos IDs, total, facet counts, ordem e cursores.

Testes de propriedade

• A AND B = B AND A;
• A AND live nunca contém item morto;
• compactação preserva toda resposta observável;
• aplicar o mesmo evento duas vezes não altera o estado;
• a soma das contagens de shards disjuntos equivale à contagem global;
• merge dos top k locais equivale ao top k do conjunto unido;
• percorrer páginas de snapshot não duplica nem omite IDs.

Injeção de falhas

• crash antes e depois da troca de manifesto;
• perda de resposta depois de aplicar um update;
• réplica atrasada;
• evento duplicado ou fora de ordem;
• shard ausente durante query;
• rebalanceamento concorrente com escrita;
• compaction sem espaço temporário;
• retry storm depois de timeout.

Benchmark do contrato

Não basta medir queries por segundo. Precisamos estratificar por:

• quantidade de filtros ativos;
• densidade e cardinalidade;
• número de counts;
• seletividade;
• cold e warm cache;
• taxa de update/delete;
• compaction concorrente;
• quantidade de shards;
• p50, p95, p99 e máximo;
• CPU, memória, bandwidth e bytes de rede;
• resultados completos dentro da deadline.

O que construímos

Começamos com uma consulta SQL correta. Quando as restrições cresceram, não a substituímos por um nome. Extraímos os mecanismos escondidos em qualquer solução desse tipo:

identidade interna densa
+ conjuntos por predicado
+ álgebra de interseção e união
+ contagens laterais
+ representação orientada por densidade
+ deltas, tombstones e segmentos imutáveis
+ publicação por geração
+ ordem total e cursor
+ particionamento e scatter-gather
+ replicação, watermarks e recuperação
+ admissão, backpressure e verificação

Implementações reais agrupam esses mecanismos de maneiras diferentes. Conhecer os building blocks não elimina tecnologias existentes; muda a forma de avaliá-las. Em vez de perguntar se uma ferramenta “faz busca facetada”, podemos perguntar:

• qual representação usa para conjuntos densos e esparsos?
• como calcula counts e múltipla escolha?
• qual é o custo de update, delete e compaction?
• o que um cursor fixa?
• como soma resultados incompletos?
• qual geração uma réplica pode servir?
• que propriedade continua válida durante rebalanceamento?

Mesmo incompleta, uma resposta pode ser examinada pelo percurso: começar pequeno, reconhecer o limite da abstração atual e construir o próximo mecanismo sem esconder os custos que ele introduz.

Referências

1. Diego Ongaro e John Ousterhout. In Search of an Understandable Consensus Algorithm, USENIX ATC 2014.
2. Atul Adya et al. Slicer: Auto-Sharding for Datacenter Applications, OSDI 2016.
3. Chunqiang Tang et al. Shard Manager: A Generic Shard Management Framework for Geo-distributed Applications, SOSP 2021.
4. Giuseppe DeCandia et al. Dynamo: Amazon’s Highly Available Key-value Store, SOSP 2007.
5. Robbert van Renesse e Fred B. Schneider. Chain Replication for Supporting High Throughput and Availability, OSDI 2004.
6. Seth Gilbert e Nancy Lynch. Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services, 2002.

Parte anterior: Quando uma máquina não basta