CS Fundamentals Trainer · Guias
Motores de armazenamento: B-trees e LSM trees
Como as B-trees atualizam páginas no lugar e as LSM trees acrescentam, descarregam e compactam, com amplificação de escrita, de leitura e de espaço medidas, Bloom filters, estratégias de compactação e quando escolher cada uma.
35 min de leitura
Todo banco de dados precisa responder a duas perguntas: como encontro uma linha rapidamente? e como altero os dados em disco sem perdê-los? As duas respostas clássicas são a B-tree, que mantém os dados ordenados em páginas de tamanho fixo que ela atualiza no lugar, e a log-structured merge tree (LSM tree), que nunca atualiza no lugar: ela acrescenta a um log e ordena e mescla em segundo plano. O Postgres, o InnoDB do MySQL, o SQLite e a maioria dos bancos relacionais usam B-trees; o RocksDB, o LevelDB, o Cassandra, o HBase e o ScyllaDB usam LSM trees. Nenhuma é melhor. Elas trocam amplificação de escrita, amplificação de leitura e amplificação de espaço entre si, e entender essa troca é como se escolhe entre elas e se ajusta qualquer uma.
Este guia constrói as duas do zero. Medi o SQLite (uma B-tree de verdade) e escrevi pequenas simulações de uma B+tree e de uma LSM tree, de modo que todo número abaixo pode ser reproduzido a partir do apêndice. Ele se apoia em índices de banco de dados, na hierarquia de memória e nas ideias de página e cache de sistemas operacionais.
Três tipos de evidência, mantidos separados. Os números deste guia vêm de três fontes diferentes, que não devem ser confundidas: | Rótulo | O que é | Quanto confiar | |---|---|---| | SQLite real | medido no SQLite, um motor B-tree de produção, nesta máquina virtual | comportamento real, mas um só motor, uma só máquina e um conjunto de dados pequeno | | B+tree de brinquedo / LSM de brinquedo | meus modelos em Python que contam páginas e entradas; eles não guardam dados e não têm disco, travas nem custo de CPU | a direção e a ordem de grandeza de um efeito (por exemplo, "a compactação em camadas escreve menos"); nunca a velocidade de um banco de dados real | | Documentação | o que dizem os manuais e os artigos dos motores; não foi executado aqui | tão boa quanto a fonte | O título de cada experimento abaixo diz qual dos três ele é. O brinquedo não tem um motor LSM real para comparar, porque o RocksDB e bibliotecas semelhantes não puderam ser instalados no sandbox; portanto, nenhuma medição aqui compara uma B-tree real com uma LSM tree real. A seção 4.1 mostra o quanto a resposta muda com as configurações e a carga de trabalho.
1. A restrição: discos gostam de I/O grande e sequencial
O armazenamento é lido e escrito em blocos (4 KB ou mais), e um bloco custa o mesmo quer você queira 1 byte ou todos os 4.096. Flash e discos também preferem o acesso sequencial ao acesso aleatório. Nesta máquina virtual (uma medição real, não um modelo), escrever blocos de 4 KB um após o outro, com um flush a cada 64 escritas, rodou a cerca de 207 MB/s, e as mesmas escritas em lugares aleatórios de um arquivo de 1 GB, a cerca de 92 MB/s, pouco mais de duas vezes mais lento. Em um disco giratório a diferença é de duas ordens de grandeza, e em SSDs as escritas aleatórias também desgastam o dispositivo mais depressa, porque a flash precisa apagar um bloco grande para reescrever uma página. Um motor de armazenamento é, em boa parte, uma estratégia para transformar as escritas pequenas e aleatórias da aplicação em algo de que o dispositivo gosta.
Três números descrevem qualquer motor:
- Amplificação de escrita: bytes fisicamente gravados por byte que a aplicação gravou.
- Amplificação de leitura: quantas leituras de disco (ou páginas, ou tabelas) uma busca exige.
- Amplificação de espaço: bytes em disco por byte de dados vivos.
Não dá para minimizar os três ao mesmo tempo (a "conjectura RUM": leituras, atualizações, memória). Cada design escolhe um canto.
2. A B-tree
Uma B-tree (em bancos de dados, quase sempre uma B+tree) guarda chaves ordenadas em páginas. As páginas internas guardam chaves e ponteiros para páginas filhas; as páginas folha guardam os registros (ou ponteiros para eles) e são ligadas às vizinhas para que varreduras por intervalo possam percorrer as folhas.
Diagram: A B+tree: few levels, wide pages
Como uma página guarda centenas de chaves, a árvore é muito rasa. Com uma página de 4 KB e 16 bytes por entrada de chave e ponteiro, uma página interna tem um fan-out de cerca de 250; três níveis de páginas internas indexam cerca de 250 × 250 × 250 ≈ 15 milhões de páginas folha, e quatro níveis alcançam bilhões de linhas. Uma busca em uma tabela de um bilhão de linhas lê cerca de quatro páginas, e os níveis do topo ficam no buffer pool, então na prática é uma leitura de disco. Essa é a grande força da B-tree: baixa amplificação de leitura, previsível.
As atualizações acontecem no lugar
Para inserir, ache a folha e adicione o registro. Se a folha está cheia, ela é dividida em duas páginas meio vazias e o pai ganha uma nova chave (que pode se dividir por sua vez, até a raiz). Para tornar isso seguro contra quedas, o motor primeiro acrescenta a mudança a um write-ahead log (WAL) e grava as páginas modificadas depois; após uma queda, ele reproduz o log. Então toda mudança é gravada duas vezes: uma no log, outra na página.
Experimento 1 (B+tree de brinquedo): fator de preenchimento e ordem das chaves
Construí uma B+tree com 40 registros por folha e inseri 100 000 chaves, uma vez em ordem crescente e outra em ordem aleatória:
| Ordem de inserção | Páginas folha | Preenchimento médio | Divisões |
|---|---|---|---|
| chaves sequenciais | 2 500 | 100% | 2 499 |
| chaves aleatórias | 3 574 | 70% | 3 573 |
Acrescentar na borda direita mantém todas as páginas cheias (a divisão deixa a página antiga cheia e começa uma nova). Inserções aleatórias dividem páginas ao meio repetidamente e se estabilizam em cerca de 70% de preenchimento (a média teórica é ln 2 ≈ 69%). Chaves aleatórias usam, portanto, cerca de 43% mais páginas para os mesmos dados, o que é mais espaço em disco e menos dados por linha de cache do buffer pool. Esta é a razão prática para ter cuidado com identificadores aleatórios como chaves primárias clusterizadas: um UUID aleatório insere em todo lugar, enquanto um id ordenado por tempo insere no fim. (O SQLite é mais esperto que o meu brinquedo no caso sequencial; em um teste com 300 000 linhas, o arquivo dele teve aproximadamente o mesmo tamanho nas duas ordens, mas inseriu as chaves sequenciais a 659 000 linhas por segundo contra 183 000 das aleatórias, 3,6 vezes mais rápido, porque inserções aleatórias tocam uma página diferente a cada vez e o cache de páginas de 2 MB que lhe dei não conseguia guardá-las.)
Experimento 2 (B+tree de brinquedo): amplificação de escrita das atualizações no lugar
Uma mudança em um registro de 100 bytes precisa reescrever a página inteira de 4 KB. Peguei uma árvore de 100 000 registros e inseri mais 20 000 aleatórios, gravando de volta cada página modificada depois de cada n inserções:
| Gravação de volta a cada | Escritas de página por registro | Bytes gravados por byte de dados |
|---|---|---|
| 1 inserção | 1,00 | 41,0 |
| 10 inserções | 1,00 | 40,9 |
| 100 inserções | 0,99 | 40,6 |
| 1 000 inserções | 0,93 | 38,0 |
| 10 000 inserções | 0,56 | 22,8 |
Para escritas pequenas e aleatórias, uma B-tree grava cerca de 40 vezes mais bytes do que a aplicação pediu (e o WAL acrescenta mais). Só quando milhares de inserções compartilham uma página entre as gravações de volta (lotes grandes, ou um buffer pool que absorve muitas mudanças antes de um checkpoint) o custo cai. Motores reais o reduzem com buffer pools grandes e group commit, mas o fato fundamental permanece: uma atualização no lugar custa uma página.
Outros custos da B-tree
- Fragmentação: deletes e divisões deixam páginas parcialmente vazias. Os motores as recuperam com vacuuming,
OPTIMIZEou reindexação. - Concorrência: as páginas são compartilhadas entre leitores e escritores, então os motores usam latches e controle de concorrência multiversão (o guia de níveis de isolamento explica como o Postgres mantém versões antigas das linhas).
- Páginas rasgadas (torn pages): uma queda no meio da gravação de uma página pode deixar metade da página. O Postgres grava páginas inteiras no seu WAL na primeira vez que uma página muda depois de um checkpoint ("full-page writes") para poder repará-la, o que é outra fonte de amplificação de escrita.
3. A LSM tree
Uma LSM tree vira o problema do avesso: nunca modifique nada em disco. As escritas são baratas porque vão só para a memória (e um log sequencial); a ordenação, a deduplicação e a limpeza são pagas depois, em lotes.
Diagram: The write path and read path of an LSM tree
- Uma escrita é acrescentada a um log (para durabilidade) e inserida em uma estrutura ordenada em memória, a memtable.
- Quando a memtable está cheia, ela é gravada em disco em uma passada sequencial como uma tabela ordenada imutável, uma SSTable (sorted string table), e começa uma nova memtable.
- As tabelas se acumulam. Uma leitura precisa verificar a memtable e depois as tabelas, das mais novas para as mais antigas, porque uma versão mais nova de uma chave esconde as mais antigas.
- Em segundo plano, a compactação mescla tabelas: combina várias tabelas ordenadas em uma, mantém apenas a versão mais nova de cada chave e descarta as chaves apagadas. Um delete é registrado como uma tombstone, um marcador que esconde valores mais antigos até a compactação remover os dois.
Percorra um pequeno exemplo. Ele tem uma memtable de quatro entradas, mescla o nível 0 no nível 1 quando existem duas tabelas e termina com a busca de uma chave que nunca foi gravada. Ligue a opção do Bloom filter para comparar o custo de leitura:
Interactive animation: lsm tree
Nesta execução, 12 escritas custam 19 entradas gravadas em disco: 12 em tabelas descarregadas mais 7 reescritas pela compactação (amplificação de escrita de 1,6 até agora; ela cresce à medida que os dados passam por mais níveis). E a busca da chave ausente precisou de 2 leituras de tabela sem filtros e nenhuma com eles.
Amplificação de leitura e Bloom filters
Uma busca pode ter de olhar em todas as tabelas, o que é a fraqueza da LSM tree. Duas ferramentas resolvem a maior parte:
- Um Bloom filter por tabela: um array compacto de bits que responde "definitivamente não está nesta tabela" ou "talvez". Um filtro com 10 bits por chave tem cerca de 1% de falsos positivos, então uma busca por uma chave pula quase todas as tabelas que não a contêm.
- Tabelas ordenadas e sem sobreposição por nível, de modo que, dentro de um nível, só uma tabela pode conter a chave (é isso que a compactação em níveis garante).
Experimento 3 (LSM tree de brinquedo): o compromisso da compactação
Escrevi uma pequena LSM tree com uma memtable de 200 entradas e enviei a ela 300 000 escritas aleatórias para 100 000 chaves distintas, de modo que cada chave foi sobrescrita cerca de três vezes. Comparei a compactação em níveis (leveled; cada nível é uma sequência ordenada, um fator T maior que a de cima; os dados são reescritos a cada vez que descem) com a compactação por camadas de tamanho (size-tiered; quando existem T tabelas de tamanho parecido, mescle-as em uma tabela maior), com e sem Bloom filters (10 bits por chave):
| Estratégia | Tabelas | Amplificação de escrita | Espaço | Leituras de tabela por busca, chave presente (sem filtro / com filtro) | Leituras de tabela, chave ausente (sem filtro / com filtro) |
|---|---|---|---|---|---|
| leveled, T = 10 | 4 | 12,8 | 1,63x | 3,1 / 1,0 | 4,00 / 0,03 |
| leveled, T = 4 | 6 | 9,1 | 1,48x | 5,2 / 1,0 | 6,00 / 0,05 |
| size-tiered, T = 4 | 10 | 4,9 | 1,77x | 8,1 / 1,1 | 10,00 / 0,08 |
| size-tiered, T = 10 | 22 | 3,1 | 1,88x | 18,3 / 1,1 | 22,00 / 0,19 |
Leia da esquerda para a direita:
- A compactação por camadas escreve menos (3,1 a 4,9 vezes contra 9 a 13), porque cada entrada é reescrita uma vez por camada e não repetidamente para o nível seguinte, mas deixa mais tabelas para pesquisar e mais versões obsoletas em disco (espaço de 1,77 a 1,88 vez os dados vivos).
- A compactação em níveis lê menos e desperdiça menos espaço, e custa mais escrita, porque mesclar um nível no seguinte reescreve os dados que já estavam lá. Uma razão de tamanho T maior significa menos níveis, mas mais reescrita por nível.
- Os Bloom filters mudam completamente o lado da leitura: o número de leituras de tabela para uma chave ausente caiu de 4 a 22 para 0,03 a 0,19, e uma chave presente precisou de cerca de uma leitura. Com filtros, as tabelas extras da estratégia por camadas custam memória (os filtros) e não leituras de disco.
(Os números de espaço são um instantâneo ao fim da execução e dependem de quando ocorreu a última compactação; o que importa é o formato. Motores reais, como o RocksDB, compactam arquivos individuais em segundo plano, em vez de níveis inteiros, então seus números são mais suaves.) Compare os 3 a 13 bytes escritos por byte na LSM tree de brinquedo com os 40 da B-tree de brinquedo: uma LSM tree transforma muitas escritas pequenas e aleatórias em poucas escritas grandes e sequenciais, e é por isso que ela serve para cargas de trabalho com muita escrita, como logs, séries temporais, mensageria e pipelines de ingestão.
Os custos de uma LSM tree
- A compactação é uma carga oculta. Ela usa largura de banda de disco e CPU em segundo plano e, quando as escritas chegam mais rápido do que a compactação consegue mesclar, as tabelas se acumulam e o motor precisa limitar ou travar as escritas ("write stalls" são um incidente clássico do RocksDB e do Cassandra). Monitore o número de tabelas por nível e os bytes de compactação pendentes.
- O espaço pode disparar durante uma compactação (tabelas antigas e novas coexistem); você precisa de disco livre bem além do tamanho dos dados vivos, muitas vezes 50% ou mais nas estratégias por camadas.
- As leituras custam mais e variam mais: varreduras por intervalo precisam mesclar várias fontes ordenadas, e uma falha pode tocar várias tabelas (os filtros ajudam só em buscas pontuais, não em intervalos).
- Os deletes não são imediatos. Uma tombstone precisa descer até o último nível antes de o espaço voltar, e muitas tombstones em um intervalo deixam as varreduras lentas (um problema conhecido no Cassandra).
- A amplificação de escrita ainda existe, e em SSDs ela custa vida útil; ela só é menor do que na B-tree ingênua, não zero.
4. Escolhendo entre elas
| B-tree | LSM tree | |
|---|---|---|
| Caminho de escrita | atualizações de página no lugar, mais um WAL | sequencial: log, memtable, flush, compactação |
| Amplificação de escrita | alta para escritas pequenas e aleatórias (cerca de 40 no brinquedo), menor com lotes | menor, ajustável pela estratégia de compactação (3 a 13 no brinquedo) |
| Leituras pontuais | previsíveis: cerca de 3 a 4 páginas, em geral uma leitura de disco | várias tabelas, salvas pelos Bloom filters |
| Varreduras por intervalo | excelentes: siga os links das folhas | mesclam várias fontes ordenadas, ainda sequenciais |
| Espaço | fragmentação, páginas 70% cheias | versões obsoletas até a compactação, espaço temporário durante ela |
| Latência | estável | boa em média, com latência de cauda por stalls e compactações |
| Transações e locks | maduros; uma linha mora em um só lugar, então travá-la é simples | possíveis (RocksDB, CockroachDB, TiDB), mas as versões de uma chave moram em muitas tabelas |
| Usuários típicos | Postgres, MySQL InnoDB, SQLite, SQL Server, LMDB, a maioria dos sistemas de arquivos | RocksDB, LevelDB, Cassandra, HBase, ScyllaDB, a família MergeTree do ClickHouse (ideia parecida) e a camada de armazenamento de muitos bancos SQL mais novos |
Regras práticas:
- Muita leitura, OLTP misto, muitos índices secundários, consultas por intervalo, comportamento transacional forte: um motor de B-tree.
- Taxas de escrita muito altas, ingestão de eventos ou métricas, dados muito maiores que a memória, tolerância a trabalho em segundo plano: um motor LSM.
- Muitos sistemas ficam no meio: o WiredTiger (MongoDB) oferece os dois, e motores como o Postgres podem ficar mais amigáveis a cargas de muita escrita com lotes, atualizações
HOTe particionamento (veja replicação, particionamento e sharding). - Meça com a sua própria carga; a amplificação teórica é facilmente dominada pelo tamanho do buffer pool, pelas configurações de compactação e pelo hardware.
4.1 Quando o vencedor aparente se inverte
"LSM trees escrevem mais rápido, B-trees leem mais rápido" é uma boa primeira aproximação e uma má conclusão. Quatro coisas costumam virar o resultado de cabeça para baixo. Os dois primeiros conjuntos de números vêm dos modelos de brinquedo, as linhas do SQLite são do SQLite real, e o resto é documentação.
1. Estratégia e configuração de compactação (brinquedo). Escrevi 60.000 registros novos de 100 bytes em um armazenamento que já tinha 100.000 registros e contei os bytes escritos no armazenamento por byte de dados do usuário:
| Motor e configuração | Amplificação de escrita (brinquedo) |
|---|---|
| B-tree, páginas modificadas gravadas de volta a cada inserção | 41,0 |
| B-tree, gravadas de volta a cada 100 inserções | 40,5 |
| B-tree, gravadas de volta a cada 10.000 inserções (um buffer pool muito grande) | 16,7 |
| LSM, em níveis (leveled), T = 10 | 12,2 |
| LSM, em níveis (leveled), T = 4 | 11,4 |
| LSM, por tamanho (size-tiered), T = 4 | 5,8 |
| LSM, por tamanho (size-tiered), T = 10 | 3,0 |
A diferença entre "a B-tree" e "a LSM tree" vai de cerca de 14 vezes (41,0 contra 3,0) a cerca de 1,4 vez (16,7 contra 12,2), dependendo apenas de duas configurações. A compactação em camadas (tiered) escreve menos, mas deixa mais tabelas para pesquisar (veja abaixo); a em níveis escreve mais e lê menos. Não existe um único "custo de escrita da LSM". Observe também que, no brinquedo, a LSM nunca escreveu mais que a B-tree. Motores reais acrescentam custos que o brinquedo deixa de fora (a compactação disputando CPU e disco com o trabalho em primeiro plano, paradas de escrita quando a compactação fica para trás, o write-ahead log dos dois motores), e é aí que os benchmarks reais encontram casos que favorecem a B-tree.
2. Tamanho do cache e memória (SQLite real). Inseri 300.000 linhas com valores de 92 bytes no SQLite, com o journal e o fsync desligados para isolar a própria árvore:
| Chaves | Cache de páginas de 0,5 MB | Cache de páginas de 64 MB |
|---|---|---|
| sequenciais | cerca de 902.000 inserções/s | cerca de 908.000 inserções/s |
| aleatórias | cerca de 265.000 inserções/s | cerca de 507.000 inserções/s |
Um cache maior deixou as inserções aleatórias cerca de 1,9 vez mais rápidas e não fez nada pelas sequenciais, porque os appends só tocam a borda direita da árvore. Um benchmark de B-tree com um conjunto de dados que cabe na memória diz, portanto, pouco sobre a mesma árvore quando os dados são dez vezes maiores que a memória. Os motores LSM têm seus próprios botões de memória (o tamanho do memtable, o cache de blocos, a memória gasta com filtros de Bloom), e um benchmark que cabe na memória esconde também o custo de compactação deles. Teste sempre com dados maiores que a RAM.
3. Distribuição de chaves e valores.
- Ordem das chaves (SQLite real). Com o cache pequeno, chaves sequenciais foram cerca de 3,4 vezes mais rápidas que chaves aleatórias (902.000 contra 265.000 inserções/s), e as chaves aleatórias precisaram de 8.649 páginas para as mesmas linhas, contra 7.521 das sequenciais (15% mais espaço). Uma LSM tree não tem essa penalidade, porque ordena na memória antes de escrever. É por isso que um UUID aleatório como chave clusterizada prejudica um motor B-tree e quase não muda um motor LSM.
- Sobrescritas (brinquedo). Quando 200 chaves quentes foram sobrescritas repetidamente, a LSM tree escreveu apenas 0,2 a 1,2 bytes por byte (o memtable e as compactações descartam as versões antigas), contra 41,0 da B-tree gravada de volta a cada inserção e 2,8 mesmo com o intervalo de gravação muito grande. Quando toda escrita era uma chave nova, a LSM tree precisava reescrever tudo à medida que os dados desciam pelos níveis (3,0 a 12,2). O mesmo motor parece excelente ou apenas bom, dependendo de quanto dos dados é sobrescrito.
- Valores grandes (documentação). A compactação reescreve os valores junto com as chaves, então uma LSM tree com valores grandes paga por eles em todos os níveis. Motores como os projetos no estilo WiscKey e o BlobDB do RocksDB guardam valores grandes separadamente e compactam só as chaves, o que pode inverter o resultado.
4. Formato da carga de trabalho.
- Chaves ausentes e varreduras de intervalo (brinquedo). Com 10 bits por chave, os filtros de Bloom reduziram as leituras de tabelas para uma chave que não existe de 3,9 (leveled T = 10), 6,8 (tiered T = 4) e 10,7 (tiered T = 10) para 0,03 a 0,07. Mas uma varredura de intervalo não pode usar um filtro de Bloom: ela precisou ler todas as tabelas cujo intervalo de chaves se sobrepunha, 3,9, 6,8 e 10,7 tabelas nas mesmas três configurações, enquanto uma B-tree lê as páginas folha que o intervalo cobre (cerca de 6 para os aproximadamente 160 registros desses intervalos). Uma carga com muitas varreduras pode inverter o vencedor, e a configuração em camadas que menos escreveu é a que mais lê.
- Ler-modificar-escrever. A "escrita cega" barata de uma LSM tree desaparece se toda atualização começar lendo o valor antigo, e então a amplificação de leitura vista acima é paga a cada escrita.
- Exclusões (documentação). Uma exclusão em uma LSM tree é uma lápide (tombstone) que precisa ser lida até que a compactação a elimine; cargas que excluem muitas linhas (filas, dados com validade) podem deixar as leituras mais lentas até a compactação alcançar.
- Índices secundários. Cada índice é mais uma árvore a atualizar, nas duas famílias, então a amplificação se multiplica pelo número de índices (veja índices de banco de dados).
Como decidir. O único procedimento confiável é rodar o motor candidato sobre uma cópia da sua própria carga de trabalho, com dados maiores que a memória, por tempo suficiente para chegar ao estado estável em que a compactação (ou o checkpointing) está rodando o tempo todo, e comparar a latência de cauda (p99), as amplificações de escrita, leitura e espaço, e o desgaste do disco, não apenas a vazão. Trate qualquer afirmação isolada de que "a B-tree é mais rápida" ou "a LSM é mais rápida", inclusive os números de brinquedo deste guia, como resposta para uma carga de trabalho e um conjunto de configurações.
Onde as ideias aparecem em outros lugares
- Um índice de busca é a ideia da LSM aplicada a documentos: segmentos imutáveis com mesclagens em segundo plano (busca e indexação de texto completo).
- O write-ahead log também é o núcleo da replicação e do consenso: um log replicado é um WAL sobre o qual muitos nós concordam (consenso e Raft).
- O cache e o cache de páginas decidem quantas dessas leituras de página chegam ao disco (estratégias de cache).
- Os armazenamentos analíticos colunares combinam um caminho de escrita estruturado em log com arquivos de colunas ordenados e comprimidos.
5. Erros comuns
- Usar um UUID aleatório como chave primária clusterizada de uma tabela grande em um motor de B-tree e se perguntar por que as inserções e as taxas de acerto do cache pioram.
- Acreditar que "a LSM é sempre mais rápida para escrever": com poucos dados em memória, ou com uma compactação que não acompanha, uma B-tree pode ganhar.
- Dimensionar os discos só para o tamanho dos dados vivos e ficar sem espaço durante a compactação.
- Ignorar as métricas de compactação até as escritas travarem.
- Usar um motor LSM para cargas de ler-modificar-escrever ou de muitos intervalos sem checar a amplificação de leitura.
- Apagar muitos dados em um armazenamento LSM e esperar que o disco encolha de uma vez.
- Esquecer que cada índice extra é outra árvore para atualizar: a amplificação de escrita se multiplica com o número de índices.
6. Coisas a mencionar em uma entrevista
- Páginas e fan-out: por que uma B+tree tem só três ou quatro níveis e uma busca é cerca de uma leitura de disco.
- Atualizações no lugar, divisões de página, o WAL e por que uma escrita pequena custa uma página.
- O caminho de escrita da LSM (WAL, memtable, flush de SSTable) e a compactação com tombstones.
- Amplificação de escrita, de leitura e de espaço, e como a compactação em níveis e por camadas trocam entre elas.
- Bloom filters e por que importam nas leituras pontuais.
- Que sistemas reais usam o quê, e como escolher pensando em uma carga de trabalho.
- Que a ordem sequencial das chaves ajuda as B-trees (páginas cheias) e que chaves aleatórias custam espaço e cache.
Resumo rápido
- Uma B-tree mantém dados ordenados em páginas atualizadas no lugar: rasa (cerca de uma leitura de disco por busca), mas uma pequena escrita aleatória custa uma página inteira (cerca de 40 vezes os dados gravados no brinquedo) e chaves aleatórias deixam as páginas com cerca de 70% de preenchimento.
- Uma LSM tree acrescenta a um log e a uma memtable, descarrega tabelas imutáveis ordenadas e as mescla em segundo plano: as escritas são sequenciais (3 a 13 vezes os dados gravados no brinquedo), ao custo do trabalho de compactação, de espaço extra e de mais lugares onde ler.
- Os Bloom filters reduzem as leituras de uma chave ausente de 4 a 22 tabelas para quase zero.
- A compactação em níveis lê menos e usa menos espaço; a por camadas escreve menos.
- Escolha pela carga de trabalho: B-tree para trabalho de muita leitura e transacional, LSM para ingestão de muita escrita, e meça compactação e stalls se escolher a segunda.
Apêndice: o código dos experimentos
Os dois scripts são Python 3 só com a biblioteca padrão. O primeiro mede o SQLite (uma B-tree) e escritas brutas em disco em uma pequena máquina virtual, então seus números absolutos dependem da máquina e variam entre execuções. O segundo é um modelo, não um banco de dados: conta entradas e páginas em vez de guardar bytes, usa uma semente aleatória fixa e imprime exatamente as tabelas acima. Sua LSM tree mescla níveis inteiros (motores reais compactam arquivos individuais), conta cada entrada como um registro de 100 bytes e usa como Bloom filter um array de bits de verdade com 10 bits por chave. Trate suas cifras de amplificação como ilustrações dos trade-offs e não como previsões para o RocksDB ou o Cassandra.
O SQLite como uma B-tree de verdade, e escritas em disco sequenciais contra aleatórias
import sqlite3, os, random, time, hashlib
def run(kind, n=300_000):
path = f"/var/tmp/lsm/{kind}.db"
for ext in ("", "-wal", "-journal"):
if os.path.exists(path + ext): os.remove(path + ext)
db = sqlite3.connect(path); db.execute("pragma journal_mode=off"); db.execute("pragma synchronous=off"); db.execute("pragma cache_size=-2048") # a 2 MB page cache
db.execute("create table t(k text primary key, v text) without rowid")
keys = [f"{i:012d}" for i in range(n)] if kind == "sequential" else [hashlib.md5(str(i).encode()).hexdigest()[:12] for i in range(n)]
payload = "x" * 80
t0 = time.perf_counter()
for i in range(0, n, 10000):
db.executemany("insert into t values (?,?)", [(k, payload) for k in keys[i:i+10000]]); db.commit()
dt = time.perf_counter() - t0
pages = db.execute("pragma page_count").fetchone()[0]; ps = db.execute("pragma page_size").fetchone()[0]
raw = n * (12 + 80)
rnd = random.Random(1); probe = [rnd.choice(keys) for _ in range(20000)]
t1 = time.perf_counter()
for k in probe: db.execute("select v from t where k=?", (k,)).fetchone()
lt = time.perf_counter() - t1
return f"{kind:>10}: {n/dt:>9,.0f} inserts/s, file {pages*ps/1e6:5.1f} MB for {raw/1e6:4.1f} MB of data (x{pages*ps/raw:.2f}), {20000/lt:>8,.0f} lookups/s"
print("SQLite (a B-tree), page size 4096, 2 MB cache, 300,000 rows of 92 bytes:")
for kind in ("sequential", "random"): print(" ", run(kind))
# raw disk: appending 4 KB blocks against rewriting random blocks of a 1 GB file, flushing every 64 writes
def disk(kind, n=20000, size=1 << 30):
path = "/var/tmp/lsm/blob";
fd = os.open(path, os.O_RDWR | os.O_CREAT); os.ftruncate(fd, size); buf = os.urandom(4096); rnd = random.Random(2)
t = time.perf_counter()
for i in range(n):
off = i * 4096 if kind == "append" else rnd.randrange(size // 4096) * 4096
os.pwrite(fd, buf, off)
if i % 64 == 63: os.fdatasync(fd)
dt = time.perf_counter() - t; os.close(fd); os.remove(path); return n * 4096 / dt / 1e6
print(f"4 KB writes with an fdatasync every 64 writes: append {disk('append'):.0f} MB/s, random in place {disk('random'):.0f} MB/s")
Uma B+tree de brinquedo e uma LSM tree de brinquedo com Bloom filters
import bisect, random, math, hashlib
# ===================== a toy B+tree: leaves hold up to LEAF records (a 4 KB page of ~100-byte records) =====================
LEAF = 40
class BPlusLeafs:
"""Only the leaf level matters for the questions below, so the interior is a sorted list of leaf minimums."""
def __init__(self): self.leaves = [[]]; self.mins = [None]; self.splits = 0
def find(self, k): return max(0, bisect.bisect_right(self.mins[1:], k)) if len(self.leaves) > 1 else 0
def insert(self, k):
i = self.find(k); leaf = self.leaves[i]; bisect.insort(leaf, k); touched = {i}
if len(leaf) > LEAF:
if i == len(self.leaves) - 1 and k == leaf[-1]: # appending at the right edge: split off just the new record
new = [leaf.pop()]
else: # otherwise split in half
half = len(leaf) // 2; new = leaf[half:]; del leaf[half:]
self.leaves.insert(i + 1, new); self.mins.insert(i + 1, new[0]); self.splits += 1; touched.add(i + 1)
return touched
def fill(self): return sum(map(len, self.leaves)) / (len(self.leaves) * LEAF)
def btree_experiment(n=100_000):
print("B+tree leaf pages, 100,000 inserts, 40 records per page:")
for kind in ("sequential", "random"):
t = BPlusLeafs(); keys = list(range(n)) if kind == "sequential" else random.Random(5).sample(range(10**9), n)
for k in keys: t.insert(k)
print(f" {kind:>10} keys: {len(t.leaves):>5} leaf pages, average fill {t.fill()*100:.0f}%, {t.splits} page splits")
# write amplification: after every `batch` inserts all modified pages are written back in full (4096 bytes)
print("page writes per record, when modified pages are written back after every `batch` inserts (record = 100 bytes, page = 4096 bytes):")
keys = random.Random(7).sample(range(10**9), 200_000)
t = BPlusLeafs()
for k in keys[:100_000]: t.insert(k) # a tree that already holds 100,000 records
for batch in (1, 10, 100, 1000, 10000):
dirty = set(); writes = 0; n_ins = 0
for k in keys[100_000:100_000 + 20_000]:
# a split moves page numbers, so count by id of the page object
i = t.find(k); leaf = t.leaves[i]; before = id(leaf)
t.insert(k); dirty.add(before); n_ins += 1
if n_ins % batch == 0: writes += len(dirty); dirty = set()
writes += len(dirty)
print(f" batch {batch:>5}: {writes/n_ins:5.2f} page writes per inserted record = {writes*4096/(n_ins*100):6.1f} bytes written per byte of data")
# ===================== a toy LSM tree =====================
class Bloom:
def __init__(self, n, bits_per_key=10):
self.m = max(8, n * bits_per_key); self.k = max(1, round(bits_per_key * math.log(2))); self.bits = bytearray(self.m // 8 + 1)
def _h(self, x):
d = hashlib.blake2b(str(x).encode(), digest_size=16).digest(); a = int.from_bytes(d[:8], "big"); b = int.from_bytes(d[8:], "big") | 1
return ((a + i * b) % self.m for i in range(self.k))
def add(self, x):
for h in self._h(x): self.bits[h >> 3] |= 1 << (h & 7)
def __contains__(self, x): return all(self.bits[h >> 3] & (1 << (h & 7)) for h in self._h(x))
class Table:
def __init__(self, keys, bloom_bits):
self.keys = sorted(set(keys)); self.bloom = Bloom(len(self.keys), bloom_bits) if bloom_bits else None
for k in self.keys: self.bloom and self.bloom.add(k)
class LSM:
"""Entries are keys only (every key is a 100-byte record). `written` counts every entry written to 'disk' by flushes and compactions."""
def __init__(self, strategy, T=10, mem=200, bloom_bits=10):
self.strategy, self.T, self.mem, self.bits = strategy, T, mem, bloom_bits
self.memtable = set(); self.levels = [[]]; self.written = 0; self.user = 0
def put(self, k):
self.memtable.add(k); self.user += 1
if len(self.memtable) >= self.mem: self.flush()
def flush(self):
t = Table(self.memtable, self.bits); self.memtable = set(); self.written += len(t.keys)
self.levels[0].append(t); self.compact()
def merge(self, tables):
keys = set(); [keys.update(t.keys) for t in tables]
out = Table(keys, self.bits); self.written += len(out.keys); return out
def compact(self):
if self.strategy == "tiered":
lvl = 0
while lvl < len(self.levels) and len(self.levels[lvl]) >= self.T:
merged = self.merge(self.levels[lvl]); self.levels[lvl] = []
if lvl + 1 == len(self.levels): self.levels.append([])
self.levels[lvl + 1].append(merged); lvl += 1
else: # leveled: level 0 collects up to 4 tables; level i >= 1 is one sorted run holding at most mem * 4 * T**i entries
if len(self.levels[0]) >= 4:
self.push(0)
lvl = 1
while lvl < len(self.levels) and self.levels[lvl] and len(self.levels[lvl][0].keys) > self.mem * 4 * self.T ** lvl:
self.push(lvl); lvl += 1
def push(self, lvl):
if lvl + 1 == len(self.levels): self.levels.append([])
merged = self.merge(self.levels[lvl] + self.levels[lvl + 1]); self.levels[lvl] = []; self.levels[lvl + 1] = [merged]
def get(self, k):
"""Returns (found, tables whose data had to be read)."""
if k in self.memtable: return True, 0
reads = 0
for lvl in self.levels:
for t in reversed(lvl):
if t.bloom is not None and k not in t.bloom: continue
reads += 1 # read the table (a disk read)
if bisect.bisect_left(t.keys, k) < len(t.keys) and t.keys[bisect.bisect_left(t.keys, k)] == k: return True, reads
return False, reads
def tables(self): return sum(len(l) for l in self.levels)
def stored(self): return sum(len(t.keys) for l in self.levels for t in l)
def lsm_experiment(n=300_000):
print(f"LSM tree, {n:,} random writes to 100,000 distinct keys (so keys are overwritten about 3 times), memtable of 200 entries:")
rnd = random.Random(9); space_keys = [rnd.randrange(10**12) for _ in range(100_000)]; keys = [rnd.choice(space_keys) for _ in range(n)]
absent = [rnd.randrange(10**12) for _ in range(2000)]
for strategy, T in (("leveled", 10), ("leveled", 4), ("tiered", 4), ("tiered", 10)):
for bits in (0, 10):
db = LSM(strategy, T, bloom_bits=bits)
for k in keys: db.put(k)
present = [rnd.choice(keys) for _ in range(2000)]
rp = sum(db.get(k)[1] for k in present) / 2000; ra = sum(db.get(k)[1] for k in absent) / 2000
if bits == 0 or True:
print(f" {strategy:>7} T={T:>2} bloom={'on ' if bits else 'off'}: {db.tables():>2} tables, write amplification {db.written/db.user:5.1f}, space {db.stored()/len(set(keys)):.2f}x, table reads per lookup: present {rp:4.1f}, absent {ra:4.2f}")
def lsm_vs_btree_bytes():
print("bytes written to storage per byte of user data (random inserts, 100-byte records, 4 KB pages):")
print(" B-tree, write-back after every insert: 4096/100 = 41 bytes (plus the write-ahead log)")
print(" B-tree, one write-back per 1,000 inserts into 100,000 leaf pages: see the table above")
if __name__ == "__main__":
btree_experiment(); lsm_experiment()
Quando o vencedor se inverte: SQLite com caches e ordens de chave diferentes, e os modelos de brinquedo com configurações diferentes
Salve o script de brinquedo da seção anterior do apêndice como toy.py (ele só define classes quando importado) e este como reversal.py na mesma pasta. A parte 1 precisa apenas do sqlite3 da biblioteca padrão; seus tempos variam conforme a máquina. A parte 2 usa os modelos de brinquedo, portanto conta entradas e páginas e não guarda dados.
"""When does the apparent winner between a B-tree and an LSM tree flip?
Part 1 uses SQLite, a real B-tree. Part 2 uses the toy models from the other script (toy.py): they count entries and pages,
they are not databases, so their numbers show the direction of an effect and not the speed of any real engine."""
import os, random, sqlite3, time, bisect
import toy
# ---------------------------------------------------------------- part 1: real SQLite
def sqlite_insert(keys, cache_kb, path="/tmp/rev.db"):
for ext in ("", "-journal", "-wal"):
try: os.remove(path + ext)
except FileNotFoundError: pass
db = sqlite3.connect(path)
db.execute("pragma journal_mode=off"); db.execute("pragma synchronous=off"); db.execute(f"pragma cache_size=-{cache_kb}")
db.execute("create table t(k integer primary key, v blob)")
v = b"x" * 92
t = time.perf_counter()
db.executemany("insert into t values (?, ?)", ((k, v) for k in keys))
db.commit(); dt = time.perf_counter() - t
pages = db.execute("pragma page_count").fetchone()[0]; db.close(); os.remove(path)
return dt, pages
def part1(n=300_000):
rnd = random.Random(1)
seq = list(range(n)); rand = rnd.sample(range(10**9), n)
print(f"SQLite (a real B-tree), {n:,} inserts of 92-byte values, journal and fsync off to isolate the tree itself:")
for label, keys in (("sequential keys", seq), ("random keys", rand)):
for kb in (512, 65_536):
dt, pages = sqlite_insert(keys, kb)
print(f" {label:>15}, page cache {kb//1024 if kb >= 1024 else 0.5:>4} MB: {n/dt:>9,.0f} inserts/s, {pages:,} pages in the file")
# ---------------------------------------------------------------- part 2: toy models
def btree_write_amp(keys, preload, batch):
"""Page writes (4096 bytes) per 100-byte record when dirty pages are written back every `batch` inserts."""
t = toy.BPlusLeafs()
for k in preload: t.insert(k)
dirty, writes, n = set(), 0, 0
for k in keys:
before = id(t.leaves[t.find(k)]); t.insert(k); dirty.add(before); n += 1
if n % batch == 0: writes += len(dirty); dirty = set()
writes += len(dirty)
return writes * 4096 / (n * 100)
def lsm_run(keys, strategy, T, bits=10, preload=(), checkpoints=None, probe=None):
"""Loads `preload` first (a store that already holds data), then counts only the writes made for `keys`."""
db = toy.LSM(strategy, T, bloom_bits=bits)
for k in preload: db.put(k)
db.written, db.user = 0, 0
samples = []
for n, k in enumerate(keys, 1):
db.put(k)
if checkpoints and n in checkpoints: samples.append(probe(db))
return db, samples
def scan_tables(db, lo, hi):
"""Tables whose key range overlaps [lo, hi]: every one of them has to be read for a range scan (a Bloom filter cannot help)."""
c = 0
for lvl in db.levels:
for t in lvl:
if t.keys and t.keys[0] <= hi and t.keys[-1] >= lo: c += 1
return c
def part2():
rnd = random.Random(3)
W = 60_000 # writes measured, on top of a store that already holds 100,000 records
pre = rnd.sample(range(10**12), 100_000)
hot_space = rnd.sample(pre, 200) # 200 keys that already exist
workloads = {
"every write is a new key": [rnd.randrange(10**12) for _ in range(W)],
"200 hot keys overwritten again and again": [rnd.choice(hot_space) for _ in range(W)],
}
print(f"\nToy models: {W:,} writes of 100-byte records into a store that already holds {len(pre):,} records")
print(" (a) write amplification = bytes written to storage per byte the application wrote (the B-tree figure excludes its write-ahead log)")
for name, keys in workloads.items():
row = [f"B-tree write-back every {b:>6}: {btree_write_amp(keys, pre, b):5.1f}" for b in (1, 100, 10_000)]
row += [f"LSM {s} T={T}: {lsm_run(keys, s, T, preload=pre)[0].written / len(keys):4.1f}" for s, T in (("leveled", 10), ("leveled", 4), ("tiered", 4), ("tiered", 10))]
print(f" {name}\n " + "\n ".join(row))
print(" (b) read side after loading new keys; averaged over 10 checkpoints, because the number of tables rises and falls as compactions run")
keys = workloads["every write is a new key"]
absent = [rnd.randrange(10**12) for _ in range(500)]
cps = set(range(W // 10, W + 1, W // 10))
def probe(db):
ra = sum(db.get(k)[1] for k in absent) / len(absent)
starts = [rnd.randrange(10**12) for _ in range(100)]
return db.tables(), ra, sum(scan_tables(db, a, a + 10**9) for a in starts) / 100
for s, T in (("leveled", 10), ("tiered", 4), ("tiered", 10)):
for bits in (0, 10):
_, smp = lsm_run(keys, s, T, bits, preload=pre, checkpoints=cps, probe=probe)
m = lambda i: sum(x[i] for x in smp) / len(smp)
print(f" LSM {s:>7} T={T:>2} bloom={'on ' if bits else 'off'}: {m(0):4.1f} tables on average (max {max(x[0] for x in smp)}), reads for an absent key {m(1):5.2f}, tables to read for a short range {m(2):4.1f}")
print(" B-tree: a lookup reads 3 to 4 pages (the upper levels are cached); a range scan reads the leaf pages it covers")
if __name__ == "__main__":
part1(); part2()
Fontes
- Patrick O'Neil, Edward Cheng, Dieter Gawlick e Elizabeth O'Neil, The Log-Structured Merge-Tree (LSM-Tree) (Acta Informatica, 1996).
- Fay Chang et al., Bigtable: A Distributed Storage System for Structured Data (OSDI 2006), que popularizou memtables e SSTables.
- Martin Kleppmann, Designing Data-Intensive Applications (O'Reilly), capítulo 3, "Storage and Retrieval".
- Manos Athanassoulis et al., Designing Access Methods: The RUM Conjecture (EDBT 2016).
- A wiki do RocksDB: compactação em níveis e universal, amplificação de escrita, filtros de Bloom e paradas de escrita.
- Alex Petrov, Database Internals (O'Reilly), partes sobre variantes de B-tree e armazenamento LSM.
- A documentação do formato de arquivo do SQLite e o capítulo da documentação do PostgreSQL sobre write-ahead logging.
- Manos Athanassoulis et al., Designing Access Methods: The RUM Conjecture (EDBT 2016); Niv Dayan e Stratos Idreos, Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores (SIGMOD 2018), sobre como a política de compactação move o compromisso.
- Lanyue Lu et al., WiscKey: Separating Keys from Values in SSD-conscious Storage (FAST 2016), e as páginas da wiki do RocksDB sobre compactação e BlobDB.
Pratique este tema: Databases