Como funciona a btree apenas de append (2010)
Desenhos de B-tree apenas de append e copy-on-write prometem recuperação de falhas simples, snapshots baratos e forte concorrência de leitura ao tratar a própria base de dados como um log e nunca modificar páginas in-place. Os comentadores comparam estes benefícios com a forte amplificação de escrita, a acumulação de páginas de lixo e a necessidade de compactação complexa ou gestão de páginas livres, contrastando abordagens como o write-ahead logging tradicional, a implementação CoW do LMDB, o intent log do ZFS e variantes de árvores log-structured ou buffered. A discussão destaca como as características do hardware de armazenamento (SSDs, flash bruto, dispositivos zoned) e os padrões de carga (mais leitura ou mais escrita, acesso multithread) influenciam fortemente se estruturas de árvore imutáveis são práticas em sistemas reais.
Desempenho de append-only vs mutable/WAL
- Vários comentadores argumentam que B-trees apenas de append são demasiado ineficientes para uso geral devido à forte amplificação de escrita e a snapshots por operação.
- Outros contrapõem que, em suportes onde escritas sequenciais são mais baratas do que escritas aleatórias, layouts log-structured ou apenas de append podem ser mais rápidos, e que a “escrita in-place” em SSDs é em grande parte ilusória.
- Bases de dados tradicionais usam muitas vezes write-ahead logs (WAL) ou undo logs, escrevendo os dados duas vezes, mas podem atenuar isso com hardware separado para log e dados.
- Benchmarks do LMDB são citados como prova de que B-trees copy-on-write (CoW) cuidadosamente desenhadas podem igualar ou superar sistemas baseados em WAL, com um ponto de equilíbrio dependente do tamanho.
Imutabilidade, concorrência e snapshots
- Árvores imutáveis/CoW suportam naturalmente múltiplos leitores concorrentes sem locks e oferecem snapshots e clones baratos.
- Simplificam o raciocínio sobre correção e concorrência, mas tornam os caminhos de escrita mais complexos e dispendiosos.
- Desenhos com um único escritor são comuns; a contenção na meta-page é um gargalo para escritores concorrentes.
Lixo, compactação e gestão de espaço livre
- B+trees apenas de append e imutáveis criam muitas páginas obsoletas. Técnicas discutidas:
- Rastrear páginas em uso por transação e recuperá-las quando nenhuma transação as referenciar.
- Manter uma lista de páginas livres através de páginas “free list” acrescentadas e atualizar uma meta page.
- Usar duas meta pages em local fixo que alternam papéis para evitar varrer desde o fim do ficheiro.
- Designs puramente append-only podem acabar com ~99% de páginas obsoletas na prática; o LMDB mudou para CoW com reutilização de páginas em vez de append-only puro.
- Alguns veem o lixo extra como algo alinhado com o wear-leveling da flash; outros sublinham a necessidade de minimizar a produção de lixo apesar do comportamento append-only.
Contexto de hardware e filesystem
- Flash bruto, zoned NVMe e discos SMR são destacados como ambientes que efetivamente impõem padrões de escrita append-only ou zoned.
- Cenários embebidos/flash bruto diferem de SSDs empresariais com FTLs opacas, onde ajustes ao nível do utilizador podem ter efeito limitado.
Desenhos alternativos de árvores e otimizações
- As ideias discutidas incluem delta records em vez de cópias completas de nós (rejeitadas por trocarem espaço por leituras/cálculo extra), árvores duplas hot/cold (semelhantes a WAL+btree), e uso de write buffers em nós internos (buffer trees, Bε-trees, Fractal trees, Hitchhiker tree, Bw-tree) para amortizar os custos de escrita do CoW à custa de lookups ligeiramente mais lentos.
- O intent log do ZFS e árvores CoW, a B+tree apenas de append do CouchDB com compactação em background, e árvores segmentadas ao estilo Datomic são citadas como arquiteturas relacionadas.
Terminologia e paralelos ao nível da linguagem
- “Persistent” é usado para estruturas de dados imutáveis e versionadas; surge alguma confusão com “persistent” no sentido de “em disco”.
- Experiências com bibliotecas de Scala, Clojure e JS (por exemplo, transients/Immer) mostram que os idioms e a batching têm um impacto enorme no desempenho para lá da escolha básica entre imutável e mutável.