Construindo uma busca por filtros: guia de leitura

Uma bibliografia genérica de sistemas distribuídos não ajuda muito a construir uma busca facetada. A arquitetura da série possui três problemas diferentes:

data plane
    filtros, interseções, facetas, top k

storage/write plane
    WAL, delta, segmentos, snapshots, compactação

control plane
    ownership, réplicas, deploy, movimentação, split e merge

Separar os planos deixa claro quais decisões estão no caminho da query e quais pertencem à operação do sistema.

A ordem de leitura abaixo acompanha essa decomposição. Primeiro entendemos o índice e a consulta. Depois aprendemos a manter esse índice enquanto os itens mudam. Só então distribuímos ownership e controlamos o ciclo de vida dos shards.

Primeira rodada: os papers essenciais

Data plane

1. Inverted Files for Text Search Engines

Justin Zobel e Alistair Moffat apresentam uma visão ampla de índices invertidos, armazenamento, construção, compressão e execução de queries.

Embora o domínio principal seja texto, a tradução para filtros é direta:

termo             → atributo=valor
posting list      → documentos que satisfazem o filtro
consulta booleana → combinação dos filtros

É a melhor primeira leitura porque explica a estrutura que existe antes de bitmaps, shards ou consenso.

2. Bitmap Index Design and Evaluation

Chee-Yong Chan e Yannis Ioannidis tratam bitmap como um espaço de design físico, não como uma opção booleana.

O paper ajuda a responder:

• um bitmap por valor fecha o orçamento?
• igualdade, range encoding ou bit slicing favorecem o workload?
• como cardinalidade e codificação mudam espaço e tempo?
• qual ponto da fronteira espaço–tempo é operacionalmente aceitável?

Os números pertencem ao ambiente de 1998; o framework continua útil, mas qualquer configuração precisa de benchmark atual.

3. Better Bitmap Performance with Roaring Bitmaps

Samy Chambi, Daniel Lemire, Owen Kaser e Robert Godin descrevem uma representação adaptativa para IDs de 32 bits. Os 16 bits superiores selecionam um container; dentro dele, valores raros podem usar arrays compactos e valores densos, bitmaps.

Essa é a fundamentação mais próxima do container adaptativo usado na Parte 2:

raro  → array ordenado
comum → bitmap

O paper compara esse formato com alternativas comprimidas específicas. Ele demonstra um ponto do espaço de design, não que um formato vença todo workload.

4. Adaptive Set Intersections, Unions, and Differences

Erik Demaine, Alejandro López-Ortiz e J. Ian Munro estudam interseção, união e diferença de conjuntos ordenados com custo adaptado à dificuldade da instância.

A leitura muda o foco de O(|A| + |B|) para a distribuição concreta dos elementos. Ela fundamenta a escolha entre:

• dois ponteiros;
• busca binária;
• galloping search;
• lista contra bitmap;
• operadores adaptativos.

É teórico, mas fornece vocabulário para o executor local.

5. Access Path Selection in a Relational Database Management System

O paper clássico de Patricia Selinger e coautores descreve como o System R escolhe access paths e ordem de joins a partir de estimativas.

Para nossa busca, a transferência é:

estimar cardinalidade e seletividade
→ escolher o primeiro conjunto
→ ordenar interseções
→ decidir entre posting, índice numérico ou forward index
→ mudar o plano quando restam poucos candidatos

É aqui que as estruturas deixam de formar apenas uma biblioteca de operadores e passam a formar um query planner.

6. WAND e Block-Max WAND

Efficient Query Evaluation Using a Two-Level Retrieval Process, de Andrei Broder e coautores, usa limites superiores para evitar avaliações completas de candidatos que provavelmente não entrarão no top k.

Faster Top-k Document Retrieval Using Block-Max Indexes, de Shuai Ding e Torsten Suel, adiciona máximos por bloco e permite pular blocos inteiros com terminação segura.

Esses papers não são prioridade para filtros booleanos com ordenação estática por preço ou data. Eles se tornam fundamentais quando o score depende da query, de relevância, personalização ou múltiplos sinais.

Storage/write plane

7. The Log-Structured Merge-Tree

Patrick O’Neil e coautores apresentam o LSM-tree: mudanças entram num componente recente e são incorporadas a componentes persistentes por merges amortizados.

Para nosso índice, a tradução combina duas ideias distintas:

LSM-tree  → componente recente + componentes persistentes + merge
protocolo do sistema → WAL + confirmação + recuperação

O paper do LSM-tree fundamenta a primeira linha; ele não especifica sozinho WAL, snapshots ou recuperação distribuída. Leia observando write amplification, custo de merge e penalidade de consultar múltiplos componentes.

8. Earlybird: Real-Time Search at Twitter

Michael Busch e coautores descrevem um índice invertido de busca em tempo real, com ingestão rápida, visibilidade imediata e concorrência single-writer/multiple-reader.

É o caso mais próximo da nossa combinação:

base orientada a leitura
+ estrutura ativa amigável à escrita
+ escritor lógico único
+ múltiplos leitores
+ publicação de uma visão

O desenho é condicionado pelo workload do Twitter; o valor está no mecanismo e nas forças que o produziram.

9. Bigtable

Bigtable: A Distributed Storage System for Structured Data, de Fay Chang e coautores, conecta log, memória, arquivos imutáveis, compactação, partições lógicas, assignment e recuperação.

Não é um paper de busca. Ele mostra como o storage local de cada partição e o gerenciamento distribuído se encontram, preservando a unidade lógica independentemente do servidor físico.

Control plane

10. In Search of an Understandable Consensus Algorithm

Diego Ongaro e John Ousterhout apresentam o Raft: eleição de líder, log replicado, safety e mudança de membership por maiorias sobrepostas.

O consenso não precisa entrar no caminho de cada leitura. Ele serve ao estado pequeno e autoritativo:

• mapa e epoch dos shards;
• configuração das réplicas;
• liderança de escrita;
• sequência commitada;
• cutover de split e merge.

O disco local do nó não pode decidir sozinho “sou líder” ou “sou dono deste intervalo”. Raft protege o log e a configuração do grupo de consenso; ele não define placement, cópia de estado ou split de ranges. Esses mecanismos pertencem aos próximos papers.

11. Slicer

Atul Adya e coautores descrevem o Slicer, separando:

data plane    → encaminha requisições rapidamente
control plane → observa carga e decide placement fora do caminho crítico

O sistema monitora hotspots e saúde, tenta reduzir desbalanceamento e minimiza churn. É a leitura certa para discutir quando mover trabalho, como evitar oscilação e como manter a decisão lenta fora do roteamento rápido.

12. Shard Manager

Shard Manager: A Generic Shard Management Framework for Geo-distributed Applications, de Chunqiang Tang e coautores, trata shard, placement, replicação, movimentação e eventos planejados como abstrações reutilizáveis.

Depois dessa leitura, reparticionamento deixa de ser “copiar arquivos” e vira uma máquina de estados:

PLANNED → COPYING → CATCHING_UP → READY
        → CUTOVER → RETIRING → COMPLETED

O paper também chama atenção para upgrades planejados: um framework de sharding precisa operar durante manutenção, não apenas sobreviver a falhas inesperadas.

Segunda rodada: aprofundar conforme o gargalo

Compressão e CPU

• Techniques for Inverted Index Compression, de Giulio Ermanno Pibiri e Rossano Venturini — revisão das famílias de codificação e de seus custos na hierarquia de memória.
• Decoding Billions of Integers per Second Through Vectorization, de Daniel Lemire e Leonid Boytsov — decodificação vetorizada de arrays de inteiros.
• SIMD Compression and the Intersection of Sorted Integers, de Lemire, Boytsov e Nathan Kurz — combina compressão, interseção vetorizada e SIMD galloping.

Essas leituras importam quando o sistema está limitado por bandwidth de memória, cache misses ou decodificação — não pela complexidade abstrata do AND.

Filtros numéricos

Bit-Sliced Index Arithmetic, de Denis Rinfret, Patrick O’Neil e Elizabeth O’Neil, representa valores numéricos por slices de bits e executa comparações e operações por álgebra bitmap.

É outro ponto do espaço de design. Não precisa ser a primeira implementação; precisa estar entre as alternativas qualificadas para ranges, agregações e top k numérico.

Atualização do índice

Hybrid Index Maintenance for Growing Text Collections, de Stefan Büttcher, Charles Clarke e Brad Lushman, combina estratégias: postings curtos entram por merge, enquanto postings longos são mantidos separados e atualizados no lugar.

A leitura impede tratar segmento imutável + delta como única solução possível. Ela explicita o compromisso entre relocação, write amplification e custo de consulta.

Forward index colunar

C-Store: A Column-Oriented DBMS, de Michael Stonebraker e coautores, ajuda a pensar em colunas compactas como:

price[doc_id]
brand[doc_id]
availability[doc_id]

Quando restam poucos candidatos, queremos ler somente os campos necessários, com boa localidade e sem materializar o documento completo.

Top-k distribuído

Optimal Aggregation Algorithms for Middleware, de Ronald Fagin, Amnon Lotem e Moni Naor, apresenta FA, TA e NRA para combinar listas ordenadas sob funções de agregação monotônicas, usando acessos sequenciais e aleatórios e condições de parada demonstráveis.

A leitura é útil para ranking com múltiplos sinais e para pensar sobre quanto cada shard precisa revelar antes de o coordenador poder parar. Ela não é automaticamente equivalente ao merge de top k de shards disjuntos; as hipóteses sobre listas, acesso e função de agregação precisam coincidir.

Particionamento e replicação

• Consistent Hashing and Random Trees — formulação clássica para limitar movimento, útil como referência e não como resposta automática.
• Dynamo: Amazon’s Highly Available Key-value Store — virtual nodes, versionamento, quóruns e conflitos em um desenho orientado à disponibilidade.
• Chain Replication for Supporting High Throughput and Availability — outro ponto do espaço, com coordenação de réplicas e garantias fortes para objetos.

Consistent hashing distribui chaves, mas não resolve poda semântica, hot shards, agrupamento de variações, fan-out ou split controlado.

Semântica de facetas

Beyond Basic Faceted Search, de Ori Ben-Yitzhak e coautores, amplia facetas para agregações e dimensões correlacionadas. É menos importante para o storage engine, mas ajuda a impedir que a interface seja reduzida a um conjunto de contadores independentes.

Livros

Information Retrieval: Implementing and Evaluating Search Engines

O livro de Stefan Büttcher, Charles Clarke e Gordon Cormack, publicado pela MIT Press, é minha escolha principal para implementação. Ele trata algoritmos, estruturas, indexação, retrieval, avaliação e experimentação.

Introduction to Information Retrieval

O livro de Christopher Manning, Prabhakar Raghavan e Hinrich Schütze possui HTML e PDFs oficiais gratuitos. Para este projeto, a sequência útil é:

1  Boolean retrieval
2  Vocabulary and postings lists
4  Index construction
5  Index compression
7  Computing scores
20 Web crawling and indexes

Search Engines: Information Retrieval in Practice

Bruce Croft, Donald Metzler e Trevor Strohman disponibilizam uma versão oficial gratuita. É uma boa visão arquitetural antes de WAND e Block-Max WAND.

Database Internals

Alex Petrov organiza storage engines e mecanismos distribuídos em torno de arquivos, B-trees, estruturas log-structured, WAL, page cache, partição, replicação e consenso. É o livro mais próximo das perguntas sobre o estado interno dos nós.

Designing Data-Intensive Applications, segunda edição

Martin Kleppmann e Chris Riccomini cobrem trade-offs de sistemas de dados e fundamentos distribuídos. O livro não ensina o índice invertido; ensina a raciocinar sobre o sistema que o cerca.

Principles of Distributed Database Systems, quarta edição

M. Tamer Özsu e Patrick Valduriez oferecem o tratamento mais acadêmico de fragmentação, query processing distribuído, transações, replicação e bancos paralelos.

Managing Gigabytes

Ian Witten, Alistair Moffat e Timothy Bell tratam compressão e indexação como partes do mesmo problema. A página oficial da segunda edição também preserva sumário, errata e software histórico.

A ordem que eu seguiria

Eu não começaria por consenso ou consistent hashing. Eles explicam a infraestrutura ao redor do índice, não o índice.

1. capítulos 1, 2, 4 e 5 de Introduction to Information Retrieval;
2. Inverted Files for Text Search Engines;
3. Bitmap Index Design and Evaluation;
4. Better Bitmap Performance with Roaring Bitmaps;
5. Adaptive Set Intersections, Unions, and Differences;
6. Selinger e o query planner;
7. WAND e Block-Max WAND, somente quando o ranking entrar;
8. LSM-tree, manutenção híbrida e Earlybird;
9. Bigtable;
10. Raft;
11. Slicer e Shard Manager.

Transformar leitura em entendimento

Cada bloco deveria terminar numa implementação pequena.

Depois dos papers de índice

document ID local
dicionário de campo e valor
postings como arrays ordenados
postings como bitmaps
container adaptativo
AND, OR e AND NOT

Depois de Selinger

cardinalidade por posting
estimativa de custo
ordem dos filtros
troca para forward-index scan
explain plan da query

Depois de WAND

heap top k
score upper bound
máximo por bloco
early termination

Depois de LSM e Earlybird

WAL
delta em memória
segmento imutável
manifest e checkpoint
tombstone
compactação
publicação atômica de geração

Depois de Slicer e Shard Manager

shard map versionado
placement de réplicas
bootstrap por snapshot
replay do log
split e merge
cutover por epoch
retirement do shard antigo

Para um primeiro ciclo, eu priorizaria três livros: Information Retrieval: Implementing and Evaluating Search Engines, Database Internals e Designing Data-Intensive Applications. O primeiro explica o motor de consulta; o segundo, como persistir e reconstruir o estado; o terceiro, como operar esses componentes como sistema distribuído.

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