o problema
Em 2008 a Facebook lançou o Inbox Search: buscar dentro das próprias mensagens. A conta que isso gera não é de leitura, é de escrita. Cada mensagem trocada precisa virar índice invertido por usuário, e o paper fala em bilhões de escritas por dia, começando com cerca de 100 milhões de usuários e chegando a mais de 250 milhões. O dado precisa estar replicado entre data centers na costa leste e na oeste, porque a latência de busca depende de servir do centro mais perto. E o resultado precisa sair ordenado por tempo, que é como o usuário lê a caixa de entrada.
Nenhum dos dois sistemas de referência da época resolvia isso inteiro. O Bigtable dava a estrutura — column families, ordenação, dado esparso — mas apoiava a durabilidade num sistema de arquivos distribuído com master, e o master vira uma peça que você precisa consertar com Chubby. O Dynamo dava o oposto: nada de master, disponibilidade durante partição, roteamento em no máximo um salto. Só que o Dynamo detecta conflito com vector clock, e manter o vector clock obriga a fazer uma leitura antes de cada escrita. Num sistema em que a escrita é a carga dominante, essa leitura é justamente o que você não pode pagar.
a ideia
Cassandra costura os dois lados e corta a leitura. A topologia é a do Dynamo: anel de consistent hashing, todo nó sabe de todo nó por gossip, qualquer nó atende qualquer requisição e roteia para as réplicas. O modelo de dados é o do Bigtable: um mapa multidimensional indexado por chave, colunas agrupadas em column families, mais um nível a mais — a super column family, uma column family dentro de outra — e a aplicação escolhe se as colunas são ordenadas por nome ou por tempo. O Inbox Search vive dessa ordenação por tempo.
O conflito deixa de ser resolvido por causalidade e passa a ser resolvido por relógio: a resposta mais recente por timestamp vence, e se alguma réplica está desatualizada o coordenador agenda o reparo. É uma garantia mais fraca, deliberadamente, em troca de uma escrita que não precisa consultar ninguém antes de acontecer.
como funciona
A escrita entra num commit log — em disco dedicado, porque assim todo acesso é sequencial e o disco entrega throughput máximo — e só depois atualiza uma estrutura em memória. Quando essa estrutura passa de um limite de tamanho, ela é despejada para disco em um arquivo por column family, junto com um índice por chave. Arquivos acumulam e um processo de compaction em segundo plano funde arquivos de tamanho parecido; um arquivo de 100 GB nunca é fundido com um de menos de 50 GB. Periodicamente roda uma compaction maior, que junta tudo num arquivo só.
A leitura consulta a memória primeiro e, se não achar, vai aos arquivos do mais novo para o mais velho. Para não abrir arquivo à toa, cada arquivo carrega um bloom filter das suas chaves, mantido também em memória. Dentro do arquivo, os dados vêm em blocos de no máximo 128 chaves com índice de bloco, e as colunas ganham índice a cada fronteira de 256 KB, para não varrer coluna por coluna.
O commit log é rolado a cada 128 MB. Cada log tem um cabeçalho com um bit vector: quando a estrutura em memória de uma column family é persistida, o bit correspondente é marcado, e um log cujos bits estão todos marcados pode ser apagado.
A associação de faixas do anel a nós passa por um líder eleito via Zookeeper, que tenta manter a invariante de nenhum nó responsável por mais de N-1 faixas. A detecção de falha usa uma variante do Φ accrual failure detector, com distribuição exponencial em vez de gaussiana, porque foi o que descreveu melhor o intervalo entre mensagens de gossip. Entrada e saída de nó são explícitas, disparadas por um operador — queda de máquina em produção costuma ser transitória e não deve provocar rebalanceamento.
o que isso custou
O paper é honesto sobre a lista. Não há transação: a atomicidade é por chave e por réplica, e quem vinha de RDBMS pediu operações atômicas justamente para manter índice secundário à mão. Índice secundário e compressão aparecem como trabalho futuro. O modo fast sync no commit log bufferiza a escrita e admite perda de dados se a máquina cair. A compaction é intensiva em I/O, e os autores dizem que muitas otimizações “podem ser colocadas” para não afetar leitura — ou seja, não estavam lá.
A escolha do hash que preserva ordem traz o custo clássico: distribuição desigual e insensibilidade à heterogeneidade das máquinas. Em vez de virtual nodes como o Dynamo, Cassandra move nós no anel para aliviar quem está sobrecarregado, escolha justificada por tornar o design tratável — e que empurra o balanceamento para o operador. O bootstrap transfere dados a 40 MB/s de um único nó; paralelizar entre réplicas, no estilo BitTorrent, ainda era plano. E o sistema suporta múltiplas tabelas, mas todo deployment usava só uma.
Vale notar o que os números medem: as latências publicadas — mediana de 15,69 ms para interações e 18,27 ms para busca por termo, num cluster de 150 nós com mais de 50 TB — são de leitura. A tese do paper é throughput de escrita, e escrita não tem tabela.
onde isso aparece hoje
Cassandra foi aberto pela Facebook e virou projeto Apache, e a combinação que ele propõe — anel sem master, replicação configurável por data center, resolução por timestamp com read repair — passou a ser o vocabulário padrão de quem discute banco distribuído disponível sob partição. As duas metades da herança estão explícitas no próprio texto: o anel e o gossip vêm do Dynamo, as column families e a compaction vêm do Bigtable, e o particionamento é o consistent hashing de 1997 aplicado direto.
O caminho de escrita descrito aqui — commit log, memória, arquivo imutável, compaction por tamanho, bloom filter por arquivo — é o desenho da LSM-tree em produção, o mesmo que engines posteriores como o RocksDB documentariam com muito mais detalhe operacional. O uso de bloom filters para evitar I/O inútil em arquivo que não contém a chave continua sendo o truque mais barato desse tipo de engine.