Construindo uma busca por filtros: o mapa da arquitetura

Depois de sete partes, a arquitetura da busca ficou espalhada por mecanismos locais e protocolos distribuídos. Sabemos como representar um filtro, publicar uma geração e mover um shard. Ainda falta enxergar onde cada decisão mora e quais contratos atravessam as fronteiras entre componentes.

Este texto consolida a versão atual do projeto. Ele não acrescenta uma tecnologia ao desenho. Organiza os building blocks já derivados em três planos:

• o data plane serve consultas sobre snapshots publicados;
• o storage/write plane transforma mutações em novas gerações consultáveis;
• o control plane decide quem pode servir, escrever e mover cada shard.

A separação é de responsabilidade, não necessariamente de processo. Um servidor de índice pode executar partes do data plane e do write plane no mesmo binário. O importante é não permitir que uma decisão local de disco se transforme em autoridade de cluster, nem colocar consenso no caminho de cada operação lógica sobre bitmaps.

O control plane publica autoridade; o write plane publica gerações; o data plane serve snapshots.

Quatro tokens evitam quatro ambiguidades

A arquitetura usa números parecidos para responder perguntas diferentes:

Uma query pode usar a routing_epoch=85, ler a generation=43 de um shard, a generation=17 de outro e exigir published_sequence >= 9182044 num escopo definido. Seu snapshot_token reúne essa visão para o cursor. Colocar tudo num único “version” esconderia estados incompatíveis: o owner pode estar correto com um índice atrasado; o índice pode estar atualizado num servidor que já perdeu a autoridade; dois segmentos podem ter o mesmo watermark e dicionários diferentes.

Generation é local à partição neste desenho. Um snapshot distribuído pode usar um vetor de gerações ou uma geração global coordenada; essa escolha permanece explícita no token, em vez de ser presumida.

As interfaces entre os planos carregam esses identificadores explicitamente:

control → data/write
    shard map, routing epoch, papéis, fencing token

write → data
    manifest, generation, published sequence, schema, semântica, checksums

data → cliente
    snapshot token, completude, exatidão, cursor, lag e shards ausentes

Identidade lógica não é posição física

O projeto também precisa distinguir quatro formas de identidade:

O SearchDocumentID = (micro_partition_id, local_slot) usado durante um split é uma identidade lógica de movimento. Ele pode preservar postings enquanto a micro-partição troca de owner, sem prometer que toda posição física sobreviverá a qualquer compactação. Cursores usam public_id ou outra identidade lógica estável, nunca uma posição interna isolada.

Data plane: responder sem decidir ownership

O data plane é o caminho síncrono da busca. Ele precisa ser rápido, limitado por deadline e capaz de declarar quando a resposta não está completa.

API e coordenador de query

O coordenador recebe filtros, facetas, ordenação, k, cursor e requisitos de freshness. Ele:

1. valida limites e normaliza a expressão;
2. fixa uma deadline fim a fim;
3. resolve o conjunto de shards na routing_epoch conhecida;
4. agrupa subconsultas por máquina;
5. combina contagens e sequências ordenadas;
6. devolve geração, completude e próximo cursor.

Ele é stateless entre requests, exceto por caches descartáveis. Cursor e request carregam o estado necessário para reproduzir a leitura; a memória de um coordenador específico não pode ser pré-requisito da página seguinte.

Uma shard-query carrega, além da expressão normalizada, a versão da semântica das facetas, ordem e desempate, snapshot_token, minimum_visible_sequence com seu escopo, epoch, deadline e budgets. A resposta devolve watermarks, geração servida, freshness, custo e dois estados diferentes: complete | partial | unavailable e exact | approximate. Assim, “adicionar esta opção” não é confundido com “substituir a seleção atual”, e uma aproximação não se disfarça de contagem exata.

Routing cache

O roteador mantém uma cópia observada do shard map. A leitura local evita consultar o quorum de metadata a cada query. Cada request ainda carrega a epoch usada: um servidor que já perdeu o shard responde STALE_EPOCH em vez de servir silenciosamente como autoridade.

A distinção entre roteamento rápido e decisões de placement fora do caminho crítico é o ponto central do Slicer. O desenho transfere essa separação para o serviço de busca sem assumir que o algoritmo de placement do paper seja o único possível.

Réplica de índice

Cada réplica serve uma ou mais micro-partições. Internamente, ela reúne componentes menores:

O planner usa estimativas para escolher o plano, mas os operadores mantêm a mesma álgebra observável. Uma troca de lista ordenada por bitmap não pode mudar os IDs retornados.

Merge e hidratação

Como os shards são disjuntos, o coordenador soma contagens somente quando todas as respostas pertencem ao contrato aceito. Para uma mesma ordem total e documentos independentes, ele combina os top k locais com um heap. Se a resposta agrupa variações por anúncio, vendedor ou outra entidade, cada shard precisa agrupar localmente ou devolver candidatos adicionais; k resultados brutos por shard deixam de ser suficientes por definição.

Os IDs vencedores podem então ser hidratados. Preço, estoque e elegibilidade continuam sob autoridade do sistema transacional; a busca descobre candidatos, mas não autoriza uma compra com base num snapshot derivado.

Sequência de uma consulta distribuída

O merge só começa depois que o coordenador conhece a epoch, as gerações lidas e o estado de cada shard.

O fluxo principal tem quatro fronteiras de falha:

1. antes do scatter: query inválida, overload ou mapa indisponível falham sem consumir CPU dos shards;
2. durante a execução local: cada réplica respeita a mesma deadline e devolve seu status;
3. no gather: o coordenador não apresenta uma soma parcial como total exato;
4. na hidratação: itens removidos ou alterados podem ser descartados após revalidação.

Se um shard responder STALE_EPOCH, a unidade segura de retry é a query distribuída inteira. Misturar respostas obtidas antes e depois de um split pode duplicar documentos e contagens. O cursor, por isso, carrega snapshot_token, semântica, ordenação, chave de desempate, último public_id e expiração — não apenas o último preço observado.

Storage/write plane: transformar eventos em snapshots

O write plane mantém o índice enquanto o catálogo muda. Seu trabalho não termina quando um evento entra no WAL; termina quando uma garantia explícita foi alcançada.

Produtor e write router

O estado autoritativo emite uma mutação com item_id, sequence_number, operação e atributos indexados. O write router consulta o mapa e encaminha o evento ao owner vigente. A epoch viaja com a escrita para que um owner antigo não aceite uma mutação depois do cutover.

Escritor lógico, WAL e replicação

Cada shard possui um escritor lógico que ordena as mutações aceitas. Antes de alterar o delta, ele registra a entrada no WAL e a replica conforme a política do grupo.

O protocolo distingue:

received  → aceito pelo processo
 durable  → persistido localmente
committed → aceito pelo grupo de réplicas
  applied → incorporado ao estado de escrita
published → visível para novas queries

Um ACK precisa nomear um desses marcos. “Salvo” não é um contrato suficiente.

Os marcadores têm escopo por partição e réplica. Se somente entradas commitadas forem aplicadas, a relação monotônica esperada é published ≤ applied ≤ committed ≤ durable ≤ received; occurred_at mede idade do evento, mas não substitui a ordem dada pelo sequence_number.

Delta, reverse map e tombstones

O delta mantém os valores novos; changed[field] mascara os valores antigos da base; o reverse map permite calcular o diff; tombstones e live_documents impedem ressurreição de itens removidos.

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

O delta é mutável apenas para o escritor. Leitores nunca percorrem essa estrutura enquanto ela muda: o write plane publica raízes imutáveis e versionadas do delta, e cada query fixa uma dessas raízes junto do manifest. Assim, “delta ativo” e “parte de uma geração” deixam de ser estados concorrentes da mesma memória.

Segment builder e compactor

Quando um delta é congelado, o builder produz arquivos imutáveis com postings, colunas diretas, índices numéricos, ordenações e checksums. A compactação incorpora deltas e tombstones a uma base nova, mas só é correta se preservar toda resposta observável.

Essa família de log, memória, arquivos imutáveis, compactação, partições lógicas e recuperação aparece integrada no Bigtable. A transferência para busca está na organização do estado, não na equivalência entre as APIs dos sistemas.

Manifest publisher e recuperação

Arquivos persistidos ainda não são visíveis. O manifest referencia o conjunto exato de artefatos, dicionários, schema, versão da semântica das facetas, checksums e watermarks de uma geração. Publicar o manifest localmente é a pequena transação de metadata que torna uma grande quantidade de I/O observável naquela réplica.

Essa publicação local não transfere ownership. A réplica já precisa estar autorizada pela routing_epoch e por seu papel no replica set; a geração é elegível quando o manifest local é válido e satisfaz os requisitos da query. O servidor reporta geração, checksums, watermarks, readiness e lag. O control plane usa esses sinais para placement e para retirar uma réplica não saudável do routing, sem colocar consenso no caminho de cada compactação.

Depois de um crash, a réplica:

1. encontra o último manifest válido;
2. verifica os segmentos;
3. carrega o checkpoint;
4. reproduz o WAL posterior;
5. valida invariantes;
6. anuncia readiness com geração e lag.

Sequência de update e publicação

Publicar a raiz do delta pode tornar uma mutação visível antes da compactação; publicar um novo manifest instala uma geração persistente.

Há dois ritmos no mesmo fluxo. O primeiro leva uma mutação do WAL ao delta publicado e controla freshness. O segundo transforma lotes em segmentos compactos e controla eficiência de leitura e recuperação. Obrigar cada evento a esperar uma compactação reduziria freshness; criar uma geração persistente para cada evento destruiria amortização.

Depois de persistir e validar um manifest, o write plane publica a geração localmente e reporta readiness, watermarks e lag. O control plane usa esses sinais para routing e placement; não comita cada generation no log de consenso.

Sequência de compactação e publicação

Compactar reescreve o layout; publicar o manifest altera o snapshot.

A sequência separa manutenção física de visibilidade lógica:

1. thresholds de memória, tombstones, quantidade de segmentos ou custo de leitura disparam a operação;
2. o escritor congela D11 e abre D12, portanto novas mutações continuam;
3. o builder combina a base B10 com o delta congelado até uma sequência de corte;
4. postings, forward index, sort, live documents e checksums são reconstruídos;
5. arquivos temporários são persistidos e verificados;
6. o manifest B11 + D12 é commitado e instalado por troca atômica;
7. B10 e D11 só são coletados depois de leitores, réplicas e rollback.

Se o processo falha antes do manifest, os arquivos novos são órfãos. Se falha depois, o manifest identifica a geração recuperável. Compactação precisa preservar resultados, counts, ordem e semântica; reduzir bytes não autoriza mudar a resposta.

Control plane: decidir autoridade e lifecycle

O control plane mantém estado pequeno, versionado e autoritativo. Ele não executa interseções nem armazena todos os bitmaps no log de consenso.

Metadata state machine

Uma máquina de estados replicada mantém:

• shard map e routing_epoch;
• owners, líderes e réplicas;
• versões de configuração;
• operações de lifecycle em andamento;
• cutovers commitados;
• políticas de placement, schema e formato;
• fencing tokens.

Um log replicado como o descrito no paper do Raft é um building block possível para ordenar essas decisões. Raft protege log, liderança e mudança de membership; não escolhe sozinho como medir hotspots, posicionar uma réplica ou dividir os dados.

Placement controller

O placement controller combina configuração desejada com sinais observados:

• capacidade e failure domain dos servidores;
• CPU, memória, disco e rede;
• tamanho e taxa de crescimento dos shards;
• QPS, fan-out e cauda;
• lag e saúde das réplicas;
• orçamento de movimento.

Mover, replicar e dividir corrigem sintomas diferentes. A decisão precisa de hysteresis e orçamento para não transformar uma oscilação de carga numa sequência infinita de cópias.

Lifecycle orchestrator

O orquestrador persiste máquinas de estado para bootstrap, movimento, split, merge e deploy. O Shard Manager é uma referência importante porque trata placement, replicação, movimentação e eventos planejados como problemas do lifecycle de aplicações shardadas.

Deploy e reparticionamento permanecem protocolos distintos:

deploy
ACTIVE → DRAINING → UPGRADING → CATCHING_UP → WARMING → READY

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

Um troca o executor; o outro troca a autoridade pelos dados.

Watchers e agentes locais

Routers e servidores observam a configuração versionada. Um agente local aplica tarefas idempotentes — baixar snapshot, iniciar bootstrap, drenar réplica, trocar formato — e reporta progresso. O controlador decide; o agente executa; o metadata log registra a transição autoritativa.

Sequência de um split

Os filhos podem estar fisicamente prontos antes de possuir a faixa. A autoridade muda somente no commit da epoch nova.

O split preserva cinco invariantes:

1. pai e filhos concordam sobre o snapshot e a sequência de corte;
2. os filhos alcançam o watermark exigido antes do cutover;
3. uma única entrada de metadata substitui o pai pelos filhos;
4. requests antigos recebem STALE_EPOCH e não criam dupla autoridade;
5. o pai permanece recuperável até o fim da janela de rollback e dos leitores antigos.

Micro-partições reduzem o custo desse protocolo. O split pode transferir ownership de unidades cujos IDs e postings já são estáveis, em vez de renumerar e reconstruir o shard inteiro.

Durante a cópia, sobreposição física é esperada; sobreposição de autoridade lógica não é. Counts globais incluem somente o owner da epoch vigente. Para um item que muda a própria chave de roteamento, add-before-delete também exige uma regra de ownership e contagem: deduplicar apenas o top k final não corrige facet counts somados duas vezes.

Sequência de deploy de uma réplica

O lote é seguro por shard e zona; a versão nova prova compatibilidade antes de servir.

Deploy troca o executor, não a autoridade sobre os dados:

1. o controlador reserva budget e escolhe um lote que preserve réplicas e failure domains;
2. a réplica antiga deixa de receber queries e transfere liderança;
3. depois de inflight=0, a versão nova inicia sobre o mesmo manifest;
4. ela precisa ler o formato atual e o anterior, carregar segmentos e reproduzir WAL;
5. shadow queries comparam IDs, ordem, counts, p99, CPU, memória e checksums;
6. somente depois de readiness o diretório habilita routing gradualmente.

Mudança de formato ocorre em fases: primeiro todos leem F1/F2; depois passam a escrever F2; por fim o leitor F1 é removido quando nenhum segmento antigo permanece. Assim, rollback não exige reverter o formato no mesmo instante.

Deploy, compactação e reparticionamento competem por CPU, disco, cache e rede. O control plane mantém budget global e um lock lógico por shard para impedir operações estruturais incompatíveis simultâneas.

Uma topologia possível de processos

Os planos não exigem um microserviço por caixa do diagrama. Uma implantação inicial pode agrupá-los assim:

Separar processos cedo demais adicionaria RPCs e modos de falha sem esclarecer responsabilidades. Misturar autoridades, por outro lado, permitiria que um componente local tomasse decisões globais sem fencing.

Invariantes que atravessam a arquitetura

O desenho inteiro depende de um conjunto pequeno de propriedades:

• snapshot: uma query não mistura dicionários, bitmaps, ordenações ou tombstones de gerações incompatíveis;
• identidade: todos os conjuntos de uma visão usam o mesmo namespace, enquanto posições físicas permanecem fora do contrato externo;
• ownership: para uma epoch, existe uma decisão autoritativa sobre quem pode aceitar escrita e servir cada shard;
• idempotência: reaplicar a mesma sequência não altera o estado;
• remoção: um tombstone mais novo vence qualquer base antiga;
• compactação: mudar o layout não muda o resultado observável;
• distribuição: contagens só são somadas entre shards disjuntos e respostas compatíveis;
• ordenação: o top k global usa a mesma chave total em todos os shards;
• semântica: versão de schema, álgebra das facetas e estado exact | approximate acompanham a visão de leitura;
• completude: timeout ou shard ausente aparece na resposta ou faz a query falhar;
• fencing: um owner antigo não publica metadata nem aceita escrita após perder a autoridade;
• revalidação: descoberta na busca não substitui a decisão transacional final.

Esses invariantes também definem a estratégia de testes. O scan simples continua como oracle; compactação, retry, crash, split e troca de réplica entram como transformações que não deveriam alterar a resposta permitida pelo contrato.

O que o diagrama ainda não decide

Esta arquitetura é uma referência, não uma configuração universal. Ela ainda deixa escolhas que dependem do produto e do workload:

• resposta parcial é aceitável ou toda query precisa ser completa?
• freshness é global, por tipo de mutação ou por cliente?
• o cursor fixa uma geração global ou um vetor por shard?
• quais mudanças exigem quorum antes do ACK?
• facet counts podem ser aproximados? Com qual erro declarado?
• ranking depende apenas de uma coluna ou exige WAND e limites por bloco?
• segmentos vivem em disco local, storage remoto ou ambos?
• quando mover, replicar ou dividir um shard?

O valor da separação em planos é tornar essas decisões localizáveis. Uma mudança no algoritmo de interseção pertence ao data plane. Uma mudança na granularidade de compactação pertence ao write plane. Uma política nova de placement pertence ao control plane. Quando uma decisão atravessa os três, os identificadores e invariantes mostram exatamente quais contratos precisam evoluir juntos.

Referências

1. Justin Zobel e Alistair Moffat. Inverted Files for Text Search Engines, 2006.
2. David DeWitt et al. The Gamma Database Machine Project, 1990.
3. Patricia G. Selinger et al. Access Path Selection in a Relational Database Management System, 1979.
4. Erik D. Demaine, Alejandro López-Ortiz e J. Ian Munro. Adaptive Set Intersections, Unions, and Differences, 2000.
5. Andrei Z. Broder et al. Efficient Query Evaluation Using a Two-Level Retrieval Process, 2003.
6. Patrick O’Neil et al. The Log-Structured Merge-Tree, 1996.
7. Fay Chang et al. Bigtable, 2006.
8. Michael Busch et al. Earlybird: Real-Time Search at Twitter, 2012.
9. Diego Ongaro e John Ousterhout. In Search of an Understandable Consensus Algorithm, 2014.
10. Jeffrey Dean e Luiz André Barroso. The Tail at Scale, 2013.
11. Atul Adya et al. Slicer: Auto-Sharding for Datacenter Applications, 2016.
12. Chunqiang Tang et al. Shard Manager, 2021.

Voltar para a série: Construindo uma busca por filtros

Leituras que fundamentam os três planos: Guia de leitura e implementação