Papers
The Log-Structured Merge-Tree (LSM-Tree)
Patrick O'Neil, Edward Cheng, Dieter Gawlick, Elizabeth O'Neil · Acta Informatica 33(4), 1996, 1996
O problema: indexar uma tabela com inserções constantes custa caro em I/O de disco
O ponto de partida do paper são sistemas transacionais de alto desempenho que inserem registros o tempo todo em arquivos que crescem por longos períodos. O exemplo usado pelos autores é uma tabela de histórico, que registra a atividade de contas e é indexada por conta. Estruturas de índice tradicionais em disco, como a B-tree, exigem várias interações com o disco para cada inserção, porque cada novo registro pode cair em uma página diferente do índice, e isso gera muito movimento do braço do disco. O abstract afirma que, nesse cenário, manter um índice B-tree em tempo real pode dobrar aproximadamente o custo de I/O de cada transação, o que elevaria o custo total do sistema em até cinquenta por cento. A pergunta que motiva o trabalho é, portanto, como oferecer um índice de baixo custo para arquivos com taxa muito alta de inserções e remoções, sem pagar um acesso aleatório ao disco por operação. O paper também deixa claro o escopo: a estrutura faz sentido quando a taxa de escrita é alta em relação à de leitura, mas as consultas ainda são frequentes o bastante para que varrer a tabela inteira seja inviável e um índice seja necessário.
A ideia central: componentes C0 e C1 e a rolling merge
A LSM-tree divide o índice em dois ou mais componentes, sendo dois o caso básico. O componente C0 é pequeno, fica inteiramente em memória e pode ter qualquer estrutura de árvore, pois inserir nele não gera I/O de disco. O componente C1 fica em disco e tem forma parecida com uma B-tree, mas otimizada para acesso sequencial: os nós são totalmente preenchidos e nós vizinhos ficam armazenados em blocos contíguos de várias páginas. Novas entradas vão sempre para C0 primeiro. Quando C0 se aproxima de um limite de tamanho, um processo em segundo plano, a rolling merge, retira um intervalo contíguo de entradas de C0 e o funde em C1, trabalhando um bloco de cada vez: lê um bloco de várias páginas, mescla as entradas nas folhas e grava os nós resultantes em novos locais do disco. O efeito é trocar muitas escritas pequenas e aleatórias por poucas escritas grandes e sequenciais, no espírito de um merge sort. Enquanto isso, os valores do índice continuam consultáveis, pois cada entrada está em C0 ou em C1, exceto por períodos muito curtos de travamento. Uma busca olha primeiro em C0 e depois em C1.
Mais componentes, deleções e recuperação
O paper generaliza o desenho de dois componentes para uma série C0, C1, ..., CK, com tamanhos crescentes: C0 em memória e os demais em disco. Entre cada par adjacente existe uma rolling merge assíncrona, disparada quando o componente menor passa do seu limite. A análise de custo, que usa a Regra dos Cinco Minutos para identificar em que pontos muda o fator de custo dominante, conclui que a taxa total de I/O das fusões é mínima (para um C0 fixo) quando os tamanhos formam uma progressão geométrica, com razão fixa r entre componentes vizinhos. O custo total depende de r, do tamanho de C0 e do número de componentes. Mais componentes reduzem o custo de escrita, mas aumentam o custo de CPU das fusões, a memória para buffers de fusão e o número de lugares onde uma busca precisa olhar. Uma deleção de entrada que já está em disco é registrada como uma entrada de deleção em C0, que remove a entrada correspondente de C1 durante uma fusão; o custo é um filtro extra nas buscas. Para recuperação de falhas, o que estava apenas em C0 precisa ser reconstruído, e como os blocos fundidos são gravados em novos locais, os blocos antigos continuam disponíveis para a recuperação. Os detalhes completos de concorrência e recuperação do paper não foram verificados nesta autoria.
O trade-off: escrita barata, leitura mais custosa
A garantia central da LSM-tree é uma redução grande no movimento do braço do disco em comparação com B-trees, o que importa quando esse movimento domina o custo de armazenamento. O preço aparece na leitura. Uma busca precisa consultar mais de um componente e filtrar os resultados, por exemplo descartando entradas que uma entrada de deleção invalida. Por isso, o desempenho de busca fica parecido com o de uma B-tree, mas com algum overhead, e a LSM-tree não traz vantagem quando as buscas são muito frequentes. O melhor caso de uso são cargas com muita inserção e pouca leitura posterior, como registros de log ou históricos de atividade, em que os dados costumam ser séries temporais, embora isso não seja requisito. A decisão de projeto também é econômica: a memória é cara por unidade, o que limita o tamanho de C0, e o paper dimensiona o sistema comparando o custo do armazenamento com o custo da capacidade de I/O. Em resumo, a LSM-tree desloca trabalho do caminho de escrita para as fusões em segundo plano e para o caminho de leitura.
Legado: a base dos armazenamentos modernos de escrita intensiva
A ideia de absorver escritas em memória e fundi-las em lote em estruturas ordenadas no disco tornou-se a base de muitos motores de armazenamento atuais. Fontes técnicas secundárias consultadas afirmam que Bigtable, LevelDB, RocksDB, Cassandra e HBase usam LSM-trees, geralmente com a mesma forma de caminho de escrita: a escrita é registrada primeiro em um log de escrita antecipada (write-ahead log) para durabilidade, entra em um buffer ordenado em memória (memtable), e quando este enche é gravada em disco como um arquivo ordenado imutável (SSTable). Em segundo plano, a compactação (compaction) funde esses arquivos e descarta chaves sobrescritas ou removidas. As leituras consultam a memtable e depois os arquivos, do mais novo para o mais antigo, e filtros de Bloom ajudam a pular arquivos que não podem conter a chave. Esses termos e otimizações vêm de sistemas posteriores, não do paper de 1996, que fala de C0, C1 e rolling merge. As variantes divergem sobretudo na estratégia de compactação: LevelDB e RocksDB usam compactação por níveis, e HBase usa a estratégia de agrupar arquivos por tamanho. O trade-off geral se mantém: alta vazão de escrita em troca de leituras que podem tocar vários arquivos e de I/O extra de compactação.
Veja as ideias em ação
Pratique na escola de System Design os desenhos que usam este paper.