O que é uma árvore LSM? Entenda a árvore de mesclagem estruturada em log

O que é uma árvore LSM?

Uma árvore de mesclagem estruturada em log (LSM) é uma estrutura de dados que armazena temporariamente na memória as escritas recebidas e as mescla no disco em lotes ordenados e imutáveis. Ela nunca modifica dados no local. Em vez disso, acumula alterações e adia o trabalho de organização, trocando a simplicidade das leituras por maior taxa de transferência de escrita.

A árvore LSM foi formalizada em um artigo de 1996 de Patrick O’Neil, Edward Cheng, Dieter Gawlick e Elizabeth O’Neil, intitulado A árvore de mesclagem estruturada em log (árvore LSM). Ela passou cerca de uma década como uma estrutura acadêmica relativamente desconhecida até que o Bigtable do Google baseou sua camada de armazenamento nesse conceito. O design do Bigtable deu origem ao LevelDB, o LevelDB deu origem ao RocksDB, e alguma variação da árvore LSM sustenta a maioria dos sistemas criados para ingestão intensiva.  

O nome sugere uma única árvore, o que é bastante enganoso. 

É melhor entender uma árvore LSM como uma coreografia de três componentes:

• Uma memtable: um buffer na memória que mantém as escritas mais recentes
• Um log de gravação antecipada (WAL): um arquivo somente de acréscimo no disco que torna essas escritas duráveis
• Uma coleção crescente de arquivos de tabelas de strings ordenadas (SSTs): arquivos imutáveis e ordenados que armazenam tudo o que é mais antigo

Quase tudo que é interessante no comportamento de uma LSM decorre de como os dados se movem entre esses três componentes. Todo esse movimento começa com uma única chamada de função aparentemente simples, normalmente chamada de put.

O que é um put? 

Put é um wrapper de conveniência que, internamente, cria um WriteBatch contendo exatamente um registro e o entrega a Write(), que processa as mutações. 

O ponto de partida natural é Put(key, value), mas, rigorosamente falando, o RocksDB não tem essa operação. Toda escrita é um lote, e um put isolado é simplesmente um lote de um único item. Escritas atômicas em várias chaves são obtidas sem custo adicional no RocksDB porque essa é uma operação nativa.

Um WriteBatch é uma string compacta de bytes com formato fixo. Ou seja, um cabeçalho de 12 bytes contendo um número de sequência de 8 bytes e uma contagem de registros de 4 bytes, seguido pelos próprios registros. Cada registro contém uma tag de tipo de um byte, uma chave prefixada pelo comprimento e, para escritas, um valor prefixado pelo comprimento.

A afirmação do primeiro artigo desta série — chaves e valores são arrays arbitrários de bytes — torna-se literal. A codificação do lote não sabe nem se importa com o significado dos bytes. A única estrutura imposta são os prefixos de comprimento. 

Cada lote recebe um contador monotonicamente crescente conhecido como número de sequência. Ele estabelece uma ordem total para todas as escritas já aceitas pelo banco de dados. Os números de sequência viabilizam snapshots, leituras consistentes e recuperação após falhas. O WAL pode ser reproduzido porque cada registro nele conhece sua posição na fila.

Put, Delete, Merge

É importante observar que um Put é kTypeValue e um Delete é kTypeDeletion, o que significa que uma exclusão não é uma remoção. Em vez disso, é uma escrita — um tombstone — que registra a exclusão, enquanto a recuperação efetiva do espaço é adiada para a compactação.

Put e Delete compartilham o formato WriteBatch com kTypeMerge, gravado pela operação Merge. Merge existe porque o padrão ler-modificar-gravar é nocivo para um armazenamento otimizado para escrita. Incrementar um contador com Put exige ler o valor atual, somar um e gravar o resultado de volta. Isso representa duas travessias do banco de dados para alterar um único número, e a leitura paga o custo total do caminho de leitura. 

Merge elimina completamente a leitura. 

Em vez disso, ele acrescenta um operando (ou seja, uma descrição da alteração, como “somar um”) e retorna. Nada é calculado no momento da escrita. O banco de dados combina os operandos em um valor final posteriormente, usando um operador de mesclagem fornecido pela aplicação, seja na próxima leitura da chave ou quando a compactação encontrar a cadeia.

As exclusões adiam a recuperação de espaço, enquanto as mesclagens adiam o cálculo. 

Toda a personalidade da árvore LSM está visível nessas três tags de tipo: toda mutação, inclusive as que dependem logicamente do estado existente, torna-se um acréscimo cego. Em uma árvore LSM, tudo é um acréscimo. 

Entenda o caminho de escrita da árvore LSM

A maneira mais clara de entender árvores LSM é acompanhar um único Put(key, value) desde a chamada de função até o disco.

Etapa um: o log de gravação antecipada

Primeiro, a escrita é acrescentada ao WAL. Esse acréscimo ocorre antes de qualquer alteração na memtable, e essa ordem forma o contrato de durabilidade. Ou seja, assim que o acréscimo ao WAL é concluído, a escrita existe no disco em um formato que sobrevive a uma falha, mesmo que ainda não tenha sido organizada para leitura.

Acrescentar dados a um log é a operação de disco mais barata possível — e esse é justamente o objetivo. A durabilidade é obtida pelo custo de escritas sequenciais.

O RocksDB agrupa escritas simultâneas em commits em grupo para amortizar ainda mais o custo, e a opção sync controla se ele envia o acréscimo do cache de páginas do sistema operacional para o armazenamento persistente antes de a chamada retornar.

Etapa dois: a memtable

Com a durabilidade garantida, a escrita é inserida na memtable. Por padrão, a memtable do RocksDB é uma skiplist. Ela usa uma skiplist porque precisa absorver escritas simultâneas e disponibilizar seu conteúdo em ordem de chave, tanto para leituras quanto para o flush posterior.

Uma skiplist permite inserções simultâneas sem bloqueio e mantém tudo ordenado o tempo todo. É o equivalente, em estruturas de dados, a arquivar documentos conforme eles chegam, em vez de deixá-los se acumular.

Etapa três: a memtable fica cheia

A memtable cresce até atingir um limite configurado (ou seja, write_buffer_size), cujo padrão é 64 MB. Nesse momento, ela é marcada como imutável, uma nova memtable vazia assume seu lugar e as escritas recebidas continuam sem interrupção. A memtable cheia e congelada aguarda sua vez de passar por flush em segundo plano. 

As escritas nunca são bloqueadas pelo flush em si.

Etapa quatro: o flush

Uma thread em segundo plano grava a memtable imutável no disco como um arquivo SST no nível 0 (L0) da árvore. Como a skiplist já está ordenada, o flush é uma única passagem sequencial que percorre as entradas em ordem e as grava.

O trabalho da memtable está concluído, e as entradas correspondentes do WAL podem ser descartadas posteriormente. Agora, os dados persistem no disco em seu formato permanente e legível.

O que há dentro de um arquivo SST?

É no arquivo SST que os dados passam o restante de sua vida. Ele é organizado em três blocos e um rodapé:

• Blocos de dados: as próprias entradas ordenadas, com alguns kilobytes cada e compactadas individualmente
• Blocos de índice: mapeiam intervalos de chaves para offsets de blocos, permitindo que uma consulta vá diretamente ao bloco correto
• Um bloco opcional de bloom filter: um resumo probabilístico compacto capaz de responder “esta chave definitivamente não está neste arquivo” sem ler mais nada
• Um rodapé: localiza todos os itens acima

Cada elemento desse layout existe para permitir que futuras leituras acessem o mínimo possível de bytes, especialmente o índice e o bloom filter.

Um passo a passo do caminho de escrita

Tudo que foi explicado acima pode ser observado diretamente. Esta seção apresenta um rastreamento rápido de um Put pelo banco de dados usando ldb e sst_dump, as ferramentas de inspeção incluídas no RocksDB. O exemplo usa Rust e o crate rocksdb, embora qualquer binding sirva.

Pré-requisitos

Para acompanhar, instale as ferramentas de linha de comando do RocksDB e um conjunto de ferramentas Rust. 

No macOS, brew install rocksdb fornece tanto ldb quanto sst_dump. No Debian/Ubuntu, o pacote é rocksdb-tools.

Com tudo instalado, crie um novo projeto:

$ cargo new lsm-trace
$ cd lsm-trace
$ cargo add rocksdb

O crate rocksdb compila a biblioteca C++ do RocksDB a partir do código-fonte na primeira build, então a execução inicial de cargo run pode levar vários minutos.

Etapa um: grave e pare

Substitua o conteúdo de src/main.rs pelo código a seguir:

use rocksdb::{Options, DB};

fn main() {
    let mut opts = Options::default();
    opts.create_if_missing(true);
    let db = DB::open(&opts, "/tmp/lsm-trace").unwrap();

    db.put(b"slot:0001", b"hello").unwrap();
// Deliberately no flush. Let the process exit.
}

Execute-o uma vez com cargo run e, em seguida, liste o diretório do banco de dados criado:

$ ls /tmp/lsm-trace
000004.log CURRENT IDENTITY LOCK LOG MANIFEST-000005 OPTIONS-000007

CURRENT e o arquivo MANIFEST controlam o inventário de arquivos do banco de dados, enquanto OPTIONS registra a configuração usada para abri-lo. LOG, sem nenhum número, é um log de texto legível por humanos para depuração e não deve ser confundido com 000004.log, que é o próprio log de gravação antecipada.

Os números exatos dos arquivos variam entre execuções, mas a estrutura permanece igual.

Observe que não temos um único arquivo .sst no diretório. A escrita é durável, pois sobreviveu ao encerramento do processo, mas existe apenas como um registro no WAL. Essa é a separação entre durabilidade e organização em ação.

Etapa dois: inspecione o WAL

Aponte ldb para qualquer arquivo .log contido no diretório:

$ ldb dump_wal --walfile=/tmp/lsm-trace/000004.log --header
Sequence,Count,ByteSize,Physical Offset,Key(s) 1,1,29,0,PUT(0) : 0x736C6F743A30303031

Temos um lote: número de sequência 1, contendo 1 registro (29 bytes), que é um PUT cuja chave é a codificação hexadecimal de slot:0001. 

O tamanho corresponde à codificação anterior: um cabeçalho de 12 bytes mais um registro de 17 bytes, que inclui uma tag de tipo, dois prefixos de comprimento, uma chave de 9 bytes e um valor de 5 bytes.

Etapa três: faça o flush e inspecione o SST

Primeiro, exclua o diretório do banco de dados (ou seja, rm -rf /tmp/lsm-trace) para que esta execução comece do zero.

Adicione uma linha ao main.rs depois do put:

db.put(b"slot:0001", b"hello").unwrap();
db.flush().unwrap();

Chamar db.flush().unwrap(); força a gravação da memtable como um arquivo SST, em vez de esperar até que ela fique cheia.

Execute o arquivo novamente e liste o diretório. 

Agora podemos ver um novo arquivo .sst na saída. Podemos inspecioná-lo com os dois modos úteis do sst_dump, substituindo pelo nome real do arquivo:

$ sst_dump --file=/tmp/lsm-trace/000010.sst --command=scan
'slot:0001' seq:1, type:1 => hello

Observe que sst_dump exibe algumas linhas introdutórias sobre o formato do arquivo antes da saída da varredura; elas foram removidas aqui e nas saídas abaixo.

Este é o par chave-valor em seu novo local permanente, ainda acompanhado de seu número de sequência. 

Em seguida, podemos ver suas propriedades usando o comando abaixo:

$ sst_dump --file=/tmp/lsm-trace/000010.sst --show_properties

A saída de propriedades enumera a anatomia do SST apresentada anteriormente no artigo: quantidade e tamanho dos blocos de dados, tamanho do bloco de índice, presença de filtro, algoritmo de compactação e contagem de entradas. 

Embora tenhamos apenas uma chave, todos os elementos estruturais são enumerados, com uma exceção instrutiva. O tamanho do bloco de filtro é zero, e a política de filtro é N/A porque bloom filters são opcionais no RocksDB, configurados por meio de filter_policy, e as opções padrão não definem nenhum. 

O próximo artigo desta série explicará por que implantações em produção quase sempre os ativam. 

Etapa quatro: reabra e verifique o log

Comente as linhas de put e flush, deixando apenas a linha DB::open, e execute mais uma vez. Ao listar o diretório, você verá que o antigo 000004.log desapareceu e foi substituído por um log novo, quase vazio e com um número maior. Seu conteúdo foi enviado ao SST na etapa três, então os registros ficaram obsoletos e o RocksDB descartou o arquivo ao reabrir.

Esse é todo o acoplamento do ciclo de vida entre WAL e memtable. 

Para descer mais uma camada, podemos executar o binário da etapa um com strace -e trace=write,fdatasync no Linux e visualizar o contrato de durabilidade no limite das syscalls. Ou seja, as chamadas sequenciais de write acrescentam dados ao arquivo .log, e fdatasync aparece somente quando WriteOptions.sync está definido.

Etapa cinco: exclua a chave e veja o que resta

A afirmação anterior de que uma exclusão é uma escrita pode ser observada diretamente. 

Modifique main.rs para excluir a chave e forçar outro flush:

db.delete(b"slot:0001").unwrap();
db.flush().unwrap();

Execute-o e liste o diretório. 

Agora haverá dois arquivos .sst. O mais antigo permanece inalterado porque é imutável, o que significa que ainda contém a chave e seu valor. Podemos confirmar isso com uma varredura:

$ sst_dump --file=/tmp/lsm-trace/000010.sst --command=scan
'slot:0001' seq:1, type:1 => hello

Agora, examine o arquivo mais recente:

$ sst_dump --file=/tmp/lsm-trace/000014.sst --command=scan
'slot:0001' seq:2, type:0 =>

É a mesma chave, mas com um número de sequência maior, é type:0 em vez de type:1 e não contém valor. Isso é um tombstone: o registro kTypeDeletion da seção WriteBatch, gravado por flush em seu próprio SST. Agora, o banco de dados contém tanto o valor quanto o registro de sua exclusão, lado a lado em arquivos separados.

A leitura da chave resolverá a contradição a favor do tombstone. 

Podemos confirmar isso adicionando uma consulta ao programa:

match db.get(b"slot:0001").unwrap() {
    Some(v) => println!("found: {:?}", v),
    None => println!("not found"),
}

Ele exibirá not found porque o caminho de leitura verifica primeiro os dados mais recentes, e um número de sequência 2 tem prioridade sobre um número de sequência 1. Do ponto de vista do banco de dados, o valor desapareceu, embora ainda esteja armazenado no disco no arquivo SST mais antigo. 

Nenhum espaço foi recuperado, o que significa que a exclusão apenas foi registrada. Ela continuará ocultando o valor até que a compactação finalmente mescle os dois arquivos e descarte tanto o tombstone quanto o valor ocultado.

Etapa seis: exclua a chave e veja o que resta

O tipo de registro Merge também pode ser observado. Ele exige a configuração de um operador de mesclagem, pois o RocksDB não sabe o que um operando significa sem um.

Exclua novamente o diretório do banco de dados e substitua main.rs pelo código a seguir:

use rocksdb::{Options, DB, MergeOperands};

fn add(_key: &[u8], existing: Option<&[u8]>, operands: &MergeOperands) -> Option<Vec<u8>> {
    let mut total: i64 = existing
        .and_then(|v| std::str::from_utf8(v).ok())
        .and_then(|s| s.parse().ok())
        .unwrap_or(0);
    for op in operands {
        total += std::str::from_utf8(op).ok().and_then(|s| s.parse().ok()).unwrap_or(0);
    }
    Some(total.to_string().into_bytes())
}

fn main() {
    let mut opts = Options::default();
    opts.create_if_missing(true);
    opts.set_merge_operator_associative("add", add);
    let db = DB::open(&opts, "/tmp/lsm-merge").unwrap();

    db.merge(b"counter", b"1").unwrap();
    db.merge(b"counter", b"1").unwrap();
    db.merge(b"counter", b"1").unwrap();
    println!("{:?}", db.get(b"counter").unwrap());
}

A inspeção do WAL mostra três registros MERGE separados. Ou seja, três acréscimos em vez de uma única leitura:

$ ldb dump_wal --walfile=/tmp/lsm-trace/000004.log --header
Sequence,Count,ByteSize,Physical Offset,Key(s)
1,1,23,0,MERGE(0) : 0x636F756E746572
2,1,23,30,MERGE(0) : 0x636F756E746572
3,1,23,60,MERGE(0) : 0x636F756E746572

O operador de mesclagem combinou a cadeia no momento da leitura, com os resultados em bytes brutos. O programa exibe Some([51]) porque 51 é o código ASCII do caractere 3. Novamente, isso ocorre porque chaves e valores são arrays arbitrários de bytes.

Também podemos adicionar db.flush().unwrap(); antes da consulta, excluir o diretório e executar o programa novamente. Uma varredura do SST mostra um único registro:

'counter' seq:3, type:2 => 3

O flush aplicou o operador e condensou os registros em um único operando.

Por que o nível 0 é especial?

Novos arquivos SST chegam ao nível 0. Eles são snapshots diretos de memtables, cada um cobrindo o intervalo de chaves que aquela memtable absorveu. Por isso, os arquivos L0 podem se sobrepor — e isso acontece com frequência. Esse comportamento difere de todos os níveis mais profundos, nos quais os arquivos não se sobrepõem; cada arquivo possui um intervalo distinto de chaves, portanto no máximo um arquivo por nível pode conter determinada chave.

A consequência é que cada arquivo L0 representa outro lugar em que uma chave pode estar escondida, o que torna a quantidade de arquivos L0 um custo direto para o desempenho de leitura. Por isso, o RocksDB monitora atentamente a quantidade de arquivos L0 e começa a limitar, ou até interromper, as escritas quando esse número fica alto demais.

Manter o L0 pequeno é uma das principais funções da compactação.

Por que árvores LSM superam árvores B nas escritas?

Árvores B pagam o custo da organização no momento da escrita para que as leituras encontrem tudo exatamente onde deve estar. Já as árvores LSM adiam a organização para a compactação em segundo plano, cujo custo é pago posteriormente em lotes.

A árvore B é a estrutura que sustenta a maioria dos bancos de dados tradicionais. Ela atualiza os dados no local, o que significa que cada escrita encontra a página responsável pela chave, lê essa página, modifica-a e a grava de volta. As páginas envolvidas estão espalhadas pelo disco, então um fluxo de escritas logicamente aleatórias torna-se um fluxo de E/S fisicamente aleatória.

A árvore LSM se recusa a pagar no momento da escrita. Ela acrescenta (ao WAL), armazena em buffer (na memtable) e agrupa em lotes (nos flushes). Toda escrita em disco é sequencial, e a dívida organizacional é adiada para a compactação. O trabalho não desaparece. Em vez disso, é pago posteriormente em lotes, consolidado em um formato que os discos processam muito bem.

Isso faz muita diferença em SSDs, pois eles não conseguem sobrescrever dados no local. 

O armazenamento flash é apagado em blocos grandes, que variam de centenas de kilobytes a megabytes, e gravado em páginas menores. Isso significa que cada pequena sobrescrita aleatória força a camada de tradução flash (FTL) da unidade a realocar dados ativos e apagar blocos nos bastidores. 

As escritas aleatórias de páginas de uma árvore B fazem a FTL executar esse trabalho constantemente. A amplificação de escrita é imposta pelo dispositivo, somada ao custo gerado pela própria estrutura de dados, e é paga tanto na taxa de transferência quanto na vida útil da unidade. As grandes escritas sequenciais de uma árvore LSM estão próximas do melhor cenário possível para o hardware flash.

A melhor forma de pensar nisso é como um empréstimo. A organização adiada vence na forma de E/S de compactação, e as leituras precisam verificar mais lugares do que em uma árvore B. Assim, a árvore LSM compra taxa de transferência de escrita agora e paga depois na forma de amplificação de leitura e de espaço. 

Para uma análise mais aprofundada de como a árvore LSM se compara à árvore B em termos de amplificação de leitura, escrita e espaço, consulte Árvore B vs. árvore LSM. 

O que acontece após uma falha do RocksDB?

A memtable fica em memória volátil, o que significa que uma falha a apaga. É exatamente por isso que o WAL existe.

Ao reiniciar, o RocksDB reproduz todas as escritas confirmadas que ainda não haviam sido enviadas para um SST. Ele as insere em uma nova memtable para reconstruir o estado anterior à falha. O custo de recuperação é proporcional aos dados que ainda não passaram por flush, razão pela qual os ciclos de vida do WAL e da memtable estão vinculados. Quando o conteúdo de uma memtable é gravado com segurança em um SST, as entradas de log correspondentes ficam obsoletas e o WAL pode ser truncado.

Uma escrita torna-se durável assim que o acréscimo ao log chega ao disco. Depois, ela se torna barata de ler quando o flush a organiza. Árvores B combinam essas duas etapas, enquanto árvores LSM as separam, e grande parte das características dessa estrutura decorre dessa separação. 

Como a Solana leva o caminho de escrita ao limite?

O primeiro artigo desta série descreveu como o Agave armazena o ledger da Solana no RocksDB. Pela perspectiva do caminho de escrita, essa carga de trabalho parece um teste de estresse criado especificamente para esse fim. Ou seja, shreds — as unidades brutas de dados do ledger — chegam continuamente pela rede na velocidade máxima, e todos precisam passar pelo caminho de acréscimo ao WAL e inserção na memtable antes que a camada de armazenamento do validator conclua seu trabalho.

O mecanismo envolvido é exatamente o mesmo rastreado neste artigo, mas em escala de produção. Quando os shreds chegam, o caminho de inserção do Blockstore no Agave valida um lote inteiro de shreds recebidos, tenta a recuperação Reed-Solomon dos que estiverem ausentes e prepara tudo — payloads de shreds, metadados de slots, metadados de apagamento e atualizações de índices — em um único WriteBatch do RocksDB antes de fazer commit em uma única escrita atômica.

Simplificado a partir de insert_data_shred:

// We don't want only a subset of these changes going through.
write_batch.put_bytes::<cf::ShredData>((slot, index), &shred.payload)?;
update_slot_meta(/* ...metadata updates */);
data_index.set_present(index, true);

Esse comentário resume o argumento deste artigo em nove palavras escritas pelos engenheiros do Agave: o lote é a unidade de atomicidade, e uma falha do validator no meio da inserção nunca pode deixar o ledger parcialmente atualizado. 

O lote de um único item rastreado no passo a passo torna-se, dentro de um validator, um lote de milhares — shreds e seus metadados em várias famílias de colunas, um intervalo de números de sequência, um acréscimo ao WAL e um commit em grupo.

A vantagem, porém, é que os shreds começam com o número do slot — ou seja, a tupla (slot, index) do trecho de código simplificado é a chave ShredData — e os slots aumentam de forma quase monotônica. Portanto, cada memtable absorve uma faixa estreita e principalmente consecutiva do espaço de chaves, e os flushes produzem arquivos L0 que quase não se sobrepõem.

Sentimos esse caminho de escrita diretamente. 

Os sistemas de arquivamento que operamos na Helius ingerem todo o histórico de transações da Solana no RocksDB — centenas de terabytes em uma carga com muitos acréscimos e crescimento permanente — e a migração que produziu essa arquitetura está documentada em nosso artigo sobre a migração do ClickHouse para o RocksDB.

Conclusão

Uma árvore LSM é um acordo firmado com o hardware. Todas as escritas tornam-se sequenciais em troca do adiamento do trabalho de manter os dados organizados. Isso significa, por exemplo, que o caminho de leitura precisa procurar os dados em mais lugares do que em uma árvore B. A memtable absorve, o WAL garante e os SSTs se acumulam. Em armazenamento flash, onde sobrescritas aleatórias são penalizadas duas vezes, esse é um excelente acordo.

No entanto, as escritas são a parte fácil. O preço desse design é pago nas leituras, pois o valor atual de uma chave pode estar na memtable, em um arquivo L0 ou em qualquer nível inferior. É no mecanismo que mantém esse custo sob controle que a engenharia de LSM fica realmente interessante. 

O próximo artigo da série percorrerá o caminho de leitura, abordando memtables, bloom filters, o cache de blocos e o triângulo de amplificação em ação.

Se acompanhar um único par chave-valor por quatro estruturas de dados distintas parece uma boa forma de passar a tarde, venha construir conosco. Os sistemas descritos nesta série são os que implantamos, operamos e ajustamos na escala dos mercados de capitais da Internet. Temos vagas abertas em toda a nossa equipe de engenharia. Veja todas as oportunidades em helius.dev/careers.