Cómo funciona el btree solo de anexado (2010)
Los diseños de B-tree de solo anexado y copy-on-write prometen una recuperación tras fallos simple, snapshots baratos y una fuerte concurrencia de lectura al tratar la base de datos como un log y nunca modificar páginas en el lugar. Los comentaristas sopesan estas ventajas frente a una fuerte amplificación de escritura, la acumulación de páginas basura y la necesidad de compactación compleja o gestión de páginas libres, comparando enfoques como el write-ahead logging tradicional, la implementación CoW de LMDB, el intent log de ZFS y variantes de árboles estructurados como logs o con buffers. El intercambio destaca cómo las características del hardware de almacenamiento (SSDs, flash sin procesar, dispositivos zonificados) y los patrones de carga (más lectura o más escritura, acceso multihilo) influyen mucho en si las estructuras de árbol inmutables son prácticas en sistemas reales.
Rendimiento de solo anexado frente a mutable/WAL
- Varios comentaristas sostienen que los B-trees de solo anexado son demasiado ineficientes para uso general debido a la alta amplificación de escritura y a los snapshots por operación.
- Otros responden que en medios donde las escrituras secuenciales son más baratas que las aleatorias, los diseños estructurados como log o de solo anexado pueden ser más rápidos, y que la “escritura en el lugar” en SSDs es en gran medida ilusoria.
- Las bases de datos tradicionales suelen usar write-ahead logs (WAL) o undo logs, escribiendo los datos dos veces, pero pueden mitigar esto con hardware separado para el log y los datos.
- Se citan benchmarks de LMDB como evidencia de que los B-trees copy-on-write (CoW) bien diseñados pueden igualar o superar a los sistemas basados en WAL, con un punto de equilibrio que depende del tamaño.
Inmutabilidad, concurrencia y snapshots
- Los árboles inmutables/CoW soportan de forma natural múltiples lectores concurrentes sin bloqueos y ofrecen snapshots y clones baratos.
- Simplifican el razonamiento sobre corrección y concurrencia, pero hacen que las rutas de escritura sean más complejas y costosas.
- Los diseños de un solo escritor son comunes; la contención en la meta-página es un cuello de botella para escritores concurrentes.
Basura, compactación y gestión del espacio libre
- Los B+trees de solo anexado e inmutables crean muchas páginas obsoletas. Técnicas discutidas:
- Rastrear las páginas en uso por transacción y reclamarlas cuando ninguna transacción las referencia.
- Mantener una lista de páginas libres mediante páginas de “free list” anexadas y actualizar una meta página.
- Usar dos meta páginas en ubicaciones fijas que alternan roles para evitar escanear desde el final del archivo.
- Los diseños puramente de solo anexado pueden acabar con ~99% de páginas obsoletas en la práctica; LMDB pasó a CoW con reutilización de páginas en lugar de solo anexado puro.
- Algunos ven la “basura” extra como algo alineado con el wear leveling de flash; otros subrayan minimizar la generación de basura pese al comportamiento de solo anexado.
Contexto de hardware y sistema de archivos
- Flash sin procesar, NVMe zoned y HDDs SMR se destacan como entornos que imponen de hecho patrones de escritura de solo anexado o zonificados.
- Los escenarios de flash embebido/sin procesar difieren de los SSD empresariales con FTLs opacos, donde los ajustes a nivel de usuario pueden tener un efecto limitado.
Diseños alternativos de árboles y optimizaciones
- Entre las ideas discutidas están los delta records en lugar de copiar nodos completos (rechazados por intercambiar espacio por lecturas/cómputo extra), árboles duales hot/cold (parecidos a WAL+btree), y el uso de buffers de escritura en nodos internos (buffer trees, Bε-trees, Fractal trees, Hitchhiker tree, Bw-tree) para amortizar los costes de escritura CoW a cambio de búsquedas algo más lentas.
- Se citan como arquitecturas relacionadas el intent log y los árboles CoW de ZFS, el B+tree de solo anexado de CouchDB con compactación en segundo plano, y los árboles segmentados al estilo Datomic.
Terminología y paralelismos a nivel de lenguaje
- “Persistent” se usa para estructuras de datos inmutables y versionadas; surge cierta confusión con “persistent” queriendo decir “en disco”.
- Experiencias con bibliotecas de Scala, Clojure y JS (por ejemplo, transients/Immer) muestran que los idioms y el batching tienen un gran impacto en el rendimiento más allá de la simple elección entre inmutable y mutable.