Conceitos
LSM-tree versus B-tree (log-structured storage)
Intuição
Imagine um caderno de anotações onde, em vez de procurar a página certa no índice toda vez que chega uma informação nova, você a escreve rapidamente numa folha de rascunho sobre a mesa. Quando o rascunho enche, você passa tudo a limpo de uma só vez, em ordem, no caderno principal. Escrever fica muito mais barato, porque você não corre até uma página diferente a cada anotação. O preço é que, para achar algo, às vezes você precisa olhar no rascunho e também em mais de um lugar do caderno.
Como funciona
Uma B-tree em disco mantém o índice sempre atualizado no lugar: cada inserção pode cair numa página diferente, o que exige várias interações com o disco e muito movimento do braço do disco. O paper da LSM-tree (1996) afirma que, numa tabela de histórico com inserções constantes, manter um índice B-tree em tempo real pode dobrar aproximadamente o custo de I/O de cada transação. A LSM-tree divide o índice em componentes: C0, pequeno e inteiramente em memória, e C1 em disco, com forma de B-tree otimizada para acesso sequencial (nós totalmente preenchidos, vizinhos em blocos contíguos). Novas entradas vão sempre para C0; quando ele se aproxima do limite de tamanho, uma rolling merge em segundo plano retira um intervalo contíguo de C0 e o funde em C1, bloco a bloco, gravando os nós resultantes em novos locais. Isso troca muitas escritas pequenas e aleatórias por poucas escritas grandes e sequenciais, no espírito de um merge sort. O desenho generaliza para uma série C0...CK de tamanhos crescentes, e o paper 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. O custo aparece na leitura: a busca consulta C0 e depois os componentes em disco, e deleções são registradas como entradas que filtram resultados, então o desempenho de busca fica parecido com o de uma B-tree, porém com algum overhead. Mais componentes reduzem o custo de escrita, mas aumentam CPU de fusão, memória de buffers e o número de lugares a consultar.
Na prática
O Bigtable adota esse padrão: toda escrita vai primeiro para um log de commit e para a memtable (buffer ordenado em memória); ao encher, a memtable é gravada como SSTable imutável (compactação menor), as compactações de mesclagem rodam em segundo plano e a maior reescreve tudo em uma única SSTable. As leituras operam sobre a visão mesclada de memtable e SSTables, com filtros de Bloom opcionais para evitar acessos a disco inúteis. Fontes técnicas secundárias apontam que LevelDB, RocksDB, Cassandra e HBase seguem a mesma linha. Escolha armazenamento log-estruturado quando a carga tem muita escrita e pouca leitura posterior (logs, históricos, séries temporais); prefira uma B-tree quando as leituras são muito frequentes, pois a LSM-tree não traz vantagem nesse cenário.
Use em um desenho
Pratique na escola de System Design os casos que dependem deste conceito.