A escolha entre LSM-Trees e B-Trees define a física de I/O e a durabilidade do hardware. Ela determina o comportamento da latência de cauda (tail latency) e a taxa de amplificação de escrita em SSDs NVMe modernos.
O que é o Trilema RUM e como ele governa os motores de armazenamento?
O Trilema RUM estabelece que nenhum motor de armazenamento consegue otimizar simultaneamente amplificação de leitura, escrita e espaço. Formalizado pelo Harvard DASlab (Athanassoulis et al., 2016), ele comprova que ganhos em uma dimensão exigem concessões imediatas em outra.
Os três vértices do trilema representam compromissos físicos fundamentais:
- Read Amplification (R): Razão entre os bytes lidos da mídia física e os bytes úteis retornados à aplicação.
- Write/Update Amplification (U/W): Razão entre o volume total gravado no armazenamento persistente e os dados requisitados pela mutação.
- Memory/Space Amplification (M/S): Proporção de espaço adicional em disco ou RAM ocupado por dados obsoletos, índices e fragmentação.
A tabela abaixo sintetiza como as duas principais famílias de storage engines se posicionam frente ao compromisso RUM:
| Dimensão RUM | B-Trees (SQLite, PostgreSQL, InnoDB) | LSM-Trees (RocksDB, Pebble, ScyllaDB) |
|---|---|---|
| Ponto Forte | Baixa amplificação de leitura pontual (R ≈ 1) | Baixíssima amplificação de escrita inicial (W ≈ 1 na RAM) |
| Gargalo Principal | Severa amplificação de escrita (W = 10× a 100×+) | Maior amplificação de leitura em buscas pontuais |
| Paradigma de I/O | Atualização no local (in-place updates) | Anexação sequencial imutável (append-only) |
| Ocupação de Espaço | Baixa amplificação de espaço contínuo | Espaço temporário extra durante compactações |
Como funcionam as B-Trees e por que mutações in-place degradam SSDs?
B-Trees organizam registros em páginas de tamanho fixo atualizadas diretamente no local do arquivo. Essa abordagem garante buscas pontuais previsíveis em O(log N), mas impõe reescritas completas de blocos inteiros para alterar pequenos registros.
Originalmente documentadas para mídias magnéticas, variantes como B+Trees são a base de motores como SQLite B-Tree Module e MySQL InnoDB. Quando uma aplicação altera um campo de 32 bytes em uma página de 4 KB (4096 bytes), o motor precisa descarregar os 4096 bytes inteiros para a mídia de armazenamento.
A amplificação de escrita direta na camada de software é calculada por:
WA_btree = S_pagina ÷ S_registro
Para uma página de 4 KB modificando um contador de 32 bytes:
WA_btree = 4096 ÷ 32 = 128×
Em unidades de estado sólido Flash NAND, essa mutação colide com a arquitetura dos blocos de apagamento (erase blocks de 2 MB a 8 MB). O controlador do SSD (Flash Translation Layer - FTL) precisa executar ciclos constantes de Read-Modify-Write. Esse ciclo causa desgaste prematuro por ciclos P/E (Program/Erase) e gera picos de latência P99.
Como a arquitetura LSM-Tree elimina gravações aleatórias?
LSM-Trees transformam todas as mutações aleatórias em gravações sequenciais estritas em memória e em disco. Descrita originalmente no artigo canônico de Patrick O'Neil, Edward O'Neil e Gerhard Weikum (1996), essa estrutura separa a ingestão em dois estágios complementares.
Ao receber uma operação de escrita (Put ou Delete), o motor executa duas etapas simultâneas:
- Write-Ahead Log (WAL): Grava a operação sequencialmente em disco para assegurar durabilidade contra falhas do processo.
- Memtable em RAM: Insere a chave em uma estrutura ordenada na memória principal, tipicamente uma SkipList concorrente.
Como a escrita no WAL é estritamente sequencial, o motor evita buscas de cabeçote ou fragmentação de blocos NAND. O retorno da chamada ocorre em microssegundos, desacoplando a taxa de ingestão da latência de escrita em disco.
Pipeline de Ingestão e Flush de uma LSM-Tree:
[Aplicação: Put(k, v)]
|
+---> [WAL (Disco: Append-Only Sequencial)]
|
+---> [Memtable Ativa (RAM: Concurrent SkipList)]
| (Ao atingir write_buffer_size, ex: 64MB)
v
[Memtable Imutável (RAM)]
| (Flush assíncrono em segundo plano)
v
[L0 SSTables (Disco: Blocos Ordenados Imutáveis)]
O que são SSTables e como funcionam as Memtables Lockless?
SSTables são arquivos de disco imutáveis contendo pares chave-valor rigorosamente ordenados por chave. Elas são particionadas em blocos de dados comprimidos, acompanhados por índices de blocos e filtros probabilísticos.
Na memória, a Memtable ativa precisa suportar leituras e gravações concorrentes sem bloqueios globais. Motores de alto desempenho como o Meta RocksDB e o Cockroach Labs Pebble implementam SkipLists concorrentes lockless.
As principais propriedades da SkipList concorrente incluem:
- Operações Atômicas: Inserções utilizam instruções atômicas
Compare-And-Swap(CAS) em ponteiros de nós em múltiplos níveis probabilísticos. - Leituras Não-Bloqueantes: Leituras percorrem os ponteiros da SkipList sem adquirir mutexes, eliminando contenção entre threads de consulta e de escrita.
- Flush Imutável: Quando a Memtable atinge o limite configurado (
write_buffer_size, tipicamente 64 MB), ela é marcada como imutável e uma nova Memtable ativa é instanciada. Uma thread de flush grava a tabela em disco como uma SSTable no Nível 0 (L0).
Cada SSTable gravada possui uma seção de metadados contendo filtros de busca e um rodapé (Footer) com referências aos índices de bloco.
Qual a diferença entre Leveled Compaction e Size-Tiered Compaction?
A compactação é o processo em segundo plano que mescla SSTables para purgar registros obsoletos e restaurar a performance de leitura. Existem duas estratégias dominantes: Size-Tiered Compaction Strategy (STCS) e Leveled Compaction Strategy (LCS).
A estratégia Size-Tiered agrupa SSTables de tamanhos similares em conjuntos independentes. Quando um conjunto atinge um limiar de arquivos, eles são mesclados em uma nova SSTable maior.
A estratégia Leveled organiza o armazenamento em níveis hierárquicos numerados (L0, L1, L2 até LN), onde cada nível possui um limite fixo de capacidade multiplicativo (geralmente T = 10× o nível anterior).
A tabela abaixo compara as propriedades operacionais das duas estratégias:
| Métrica / Propriedade | Size-Tiered Compaction (STCS) | Leveled Compaction (LCS) |
|---|---|---|
| Write Amplification (WA) | Menor (WA ≈ 4× a 8×) | Maior (WA ≈ 10× a 30×) |
| Space Amplification (SA) | Alta (exige até 50% de espaço livre) | Baixa e estável (SA ≈ 1.1× a 1.2×) |
| Read Amplification (RA) | Alta (múltiplas SSTables por partição) | Mínima (máximo 1 SSTable por chave de L1 em diante) |
| Caso de Uso Ideal | Cargas massivas de escrita de séries temporais | Bancos relacionais e buscas pontuais frequentes |
No Leveled Compaction, os arquivos nos níveis L1 em diante possuem intervalos de chaves estritamente disjuntos. Uma busca por chave toca no máximo um arquivo por nível a partir de L1.
A amplificação de escrita no pior caso para Leveled Compaction é modelada por:
WA_leveled ≈ 1 + L × T
Onde L representa o número de níveis ocupados e T é o fator de escala entre níveis. Com T = 10 e 4 níveis ativos, o fator teórico alcança 41×, enquanto na prática estabiliza entre 12× e 25×.
Como Bloom Filters e Ribbon Filters aceleram leituras em disco?
Filtros de Bloom evitam acessos desnecessários a SSTables em disco calculando se uma chave definitivamente não existe no arquivo. Eles operam inteiramente em RAM antes de emitir chamadas de leitura física ao sistema operacional.
O filtro de Bloom clássico utiliza um vetor de m bits e k funções de hash independentes. A taxa de falso positivo (FPR) é modelada por:
FPR_bloom = (1 - e^(-k ÷ b))^k
Onde b = m ÷ n representa os bits alocados por chave. O número ótimo de funções de hash é dado por:
k_otimo = ln(2) × b ≈ 0.693 × b
Para uma alocação padrão de b = 10 bits/chave com k = 7, a taxa de falso positivo resultante é de aproximadamente 0.82%.
Para reduzir o consumo de memória em conjuntos massivos de dados, o RocksDB introduziu os Ribbon Filters. Baseados em sistemas de equações lineares esparsas, os Ribbon Filters alcançam a mesma taxa de falsos positivos com economia expressiva de RAM:
Economia_RAM = (b_bloom - b_ribbon) ÷ b_bloom ≈ (10 - 7) ÷ 10 = 30%
Essa redução de 30% na pegada de memória permite manter filtros de bilhões de chaves residentes em memória cache L3 ou RAM rápida.
O que é separação Key-Value e como o WiscKey e BlobDB reduzem o WAF?
A separação Key-Value desacopla chaves pequenas de valores volumosos para eliminar a reescrita desnecessária de dados durante compactações. Proposta pela Universidade de Wisconsin no paper WiscKey (Lu et al., FAST 2016), essa técnica inspirou a arquitetura do RocksDB BlobDB.
Em LSM-Trees tradicionais, quando uma SSTable é recompactada de L1 para L2, tanto as chaves quanto os valores são lidos e regravados. Se os valores possuem centenas de kilobytes, a compactação consome largura de banda excessiva de I/O.
No modelo BlobDB/WiscKey, o sistema adota dois fluxos distintos:
- Value Log (vLog / Blob Files): Os valores brutos são anexados diretamente a um arquivo de log sequencial imutável em disco.
- LSM-Tree Index: Apenas a chave e o ponteiro de endereço do Blob (
<blob_file_id, offset, size>) são inseridos na LSM-Tree.
Como a LSM-Tree processa apenas referências compactas de 24 a 32 bytes, as compactações operam com volume mínimo de dados. Isso reduz a amplificação de escrita de valores grandes para níveis próximos de 1.5× a 2.5×.
Como o MaxVision Code e motores de IA utilizam LSM-Trees para indexação?
Motores de indexação de código e agentes de IA locais utilizam LSM-Trees embarcadas para gerenciar grafos de símbolos e índices lexicais sem saturar a CPU ou o disco. Nessas aplicações, a taxa de mutação contínua de código e embeddings exige alta vazão de ingestão.
Na plataforma MaxVision Code, a infraestrutura local organiza os índices de desenvolvimento em três camadas otimizadas:
- Tabelas de Símbolos AST e Trigramas: Armazenadas em instâncias de LSM-Trees (via RocksDB ou Pebble) com blocos compactados em ZSTD e Two-Level Indexing.
- Cache de Embeddings Vetoriais: Valores densos de vetores utilizam separação de Blobs, mantendo as chaves de busca rápidas na Memtable.
- Filtragem de Prefixos: Utiliza Prefix Bloom Filters para resolver autocompletes e navegação de símbolos de código com latência sub-milissegundo.
A combinação de gravações sequenciais em RAM com compactação escalonada garante que a análise contínua de repositórios não degrade a vida útil dos SSDs dos desenvolvedores.
Resumo comparativo: Quando escolher LSM-Tree ou B-Tree?
A decisão arquitetural entre B-Trees e LSM-Trees depende da proporção entre leituras e gravações e da sensibilidade a amplificação de espaço e escrita.
O checklist prático abaixo orienta a seleção para sistemas modernos:
- Escolha B-Trees (SQLite, PostgreSQL, InnoDB): Quando a carga de trabalho for predominantemente de leitura pontual (
> 80% leituras), o conjunto de dados couber confortavelmente no buffer pool de memória e atualizações forem esparsas. - Escolha LSM-Trees (RocksDB, Pebble, ScyllaDB): Quando houver ingestão contínua em alta taxa, gravações intensivas, necessidade de compressão densa de disco e tolerância a processamento em background.
- Adote Separação Key-Value (BlobDB): Quando os registros possuírem valores individuais médios superiores a 1 KB a 4 KB, reduzindo a amplificação de escrita durante ciclos de compactação.
A física do hardware e o Trilema RUM continuam ditando os limites fundamentais de engenharia de dados. Entender essas fronteiras permite desenhar sistemas resilientes, rápidos e econômicos.
