¿Qué es un árbol LSM? Explicación del árbol de fusión con estructura de log

¿Qué es un árbol LSM?

Un árbol de fusión con estructura de log (LSM) es una estructura de datos que almacena temporalmente las escrituras entrantes en memoria y las fusiona en el disco en lotes ordenados e inmutables. Nunca modifica los datos en el mismo lugar. En cambio, acumula los cambios y aplaza la tarea de organizarlos, sacrificando simplicidad de lectura a cambio de rendimiento de escritura.

El árbol LSM se formalizó en un artículo de 1996 de Patrick O’Neil, Edward Cheng, Dieter Gawlick y Elizabeth O’Neil titulado El árbol de fusión con estructura de log (árbol LSM). Pasó cerca de una década como una estructura académica relativamente desconocida antes de que Bigtable de Google basara su capa de almacenamiento en este concepto. El diseño de Bigtable dio origen a LevelDB, LevelDB dio origen a RocksDB, y alguna variante del árbol LSM sustenta la mayoría de los sistemas creados para una ingesta intensiva.  

El nombre sugiere que se trata de un único árbol, lo cual es muy engañoso. 

Es mejor entender un árbol LSM como la coordinación de tres componentes:

• Una memtable: un búfer en memoria que contiene las escrituras más recientes
• Un log de escritura anticipada (WAL): un archivo de solo anexado en disco que hace persistentes esas escrituras
• Una colección creciente de archivos de tablas de cadenas ordenadas (SST): archivos inmutables y ordenados que contienen todos los datos anteriores

Casi todo lo interesante del comportamiento de un LSM surge de cómo se mueven los datos entre estos tres componentes. Todo ese movimiento comienza con una única llamada a una función engañosamente sencilla, que suele denominarse put.

¿Qué es un put? 

Put es un contenedor práctico que crea internamente un WriteBatch con exactamente un registro y se lo entrega a Write(), que gestiona las mutaciones. 

El punto de partida natural es Put(key, value), pero, en sentido estricto, RocksDB no tiene esa operación. Cada escritura es un lote, y un put individual es simplemente un lote de un elemento. Las escrituras atómicas de varias claves vienen incluidas en RocksDB porque se trata de una operación nativa.

Un WriteBatch es una cadena compacta de bytes con una estructura fija. Es decir, un encabezado de 12 bytes que contiene un número de secuencia de 8 bytes y un conteo de registros de 4 bytes, seguido de los propios registros. Cada registro consta de una etiqueta de tipo de un byte, una clave con prefijo de longitud y, para las escrituras, un valor con prefijo de longitud.

La afirmación del primer artículo de esta serie —las claves y los valores son arreglos de bytes arbitrarios— se vuelve literal. La codificación del lote no sabe ni le importa qué significan los bytes. La única estructura impuesta son los prefijos de longitud. 

Cada lote recibe un contador que aumenta de forma monótona, conocido como número de secuencia. Este establece un orden total para cada escritura que la base de datos haya aceptado. Los números de secuencia permiten las instantáneas, las lecturas coherentes y la recuperación ante fallos. El WAL se puede reproducir porque cada registro conoce su posición en la secuencia.

Put, Delete y Merge

Es importante señalar que un Put es kTypeValue y un Delete es kTypeDeletion, lo que significa que una eliminación no quita nada. En cambio, es una escritura —una marca de eliminación— que registra la eliminación y aplaza la recuperación real del espacio hasta la compactación.

Put y Delete comparten el formato WriteBatch con kTypeMerge, que escribe la operación Merge. Merge existe porque leer, modificar y escribir es perjudicial para un almacén optimizado para escrituras. Incrementar un contador con Put requiere leer el valor actual, sumarle uno y volver a escribir el resultado. Esto implica dos recorridos por la base de datos para cambiar un solo número, y la lectura asume el costo total de la ruta de lectura. 

Merge omite la lectura por completo. 

En su lugar, anexa un operando (es decir, una descripción del cambio, como “sumar uno”) y finaliza. No se calcula nada durante la escritura. La base de datos combina después los operandos en un valor final mediante un operador de fusión proporcionado por la aplicación, ya sea cuando se vuelve a leer la clave o cuando la compactación encuentra la cadena.

Las eliminaciones aplazan la recuperación del espacio, mientras que las fusiones aplazan el cálculo. 

Toda la personalidad del árbol LSM queda reflejada en estas tres etiquetas de tipo: cada mutación, incluso las que dependen lógicamente del estado existente, se convierte en un anexado a ciegas. En un árbol LSM, todo es un anexado. 

Explicación de la ruta de escritura del árbol LSM

La forma más clara de entender los árboles LSM es seguir un único Put(key, value) desde la llamada a una función hasta el disco.

Paso uno: el log de escritura anticipada

Primero, la escritura se anexa al WAL. Este anexado ocurre antes de modificar la memtable, y este orden establece el contrato de persistencia. Es decir, una vez que se completa el anexado al WAL, la escritura existe en el disco de una forma que sobrevive a un fallo, aunque todavía no se haya organizado para su lectura.

Anexar datos a un log es la operación de disco más económica posible, y ese es el objetivo. La persistencia se obtiene al costo de las escrituras secuenciales.

RocksDB agrupa las escrituras simultáneas en confirmaciones grupales para amortizar aún más el costo, y la opción sync controla si transfiere el anexado desde la caché de páginas del sistema operativo al almacenamiento estable antes de que finalice la llamada.

Paso dos: la memtable

Una vez garantizada la persistencia, la escritura se inserta en la memtable. De forma predeterminada, la memtable de RocksDB es una skiplist. Utiliza una skiplist porque la memtable debe absorber escrituras simultáneas y devolver su contenido ordenado por clave, tanto para las lecturas como para el vaciado posterior.

Una skiplist admite inserciones simultáneas sin bloqueos y mantiene todo ordenado en todo momento. Es el equivalente, en estructuras de datos, a archivar los documentos conforme llegan en lugar de dejar que se acumulen.

Paso tres: la memtable se llena

La memtable crece hasta alcanzar un umbral configurado (es decir, write_buffer_size), cuyo valor predeterminado es 64 MB. En ese momento se marca como inmutable, se sustituye por una memtable nueva y vacía, y las escrituras entrantes continúan sin interrupciones. La memtable llena y congelada espera su turno para vaciarse en segundo plano. 

Las escrituras nunca se bloquean debido al vaciado.

Paso cuatro: el vaciado

Un hilo en segundo plano escribe la memtable inmutable en el disco como un archivo SST en el nivel 0 (L0) del árbol. Como la skiplist ya está ordenada, el vaciado consiste en una única pasada secuencial que recorre las entradas en orden y las escribe.

El trabajo de la memtable ha terminado, y las entradas correspondientes del WAL podrán descartarse más adelante. Ahora los datos persisten en el disco en su formato permanente y legible.

¿Qué contiene un archivo SST?

El archivo SST es donde los datos pasan el resto de su vida. Está organizado en tres bloques y un pie:

• Bloques de datos: las propias entradas ordenadas, de unos pocos kilobytes cada una y comprimidas individualmente
• Bloques de índice: asignan rangos de claves a desplazamientos de bloques para que una búsqueda pueda saltar directamente al bloque correcto
• Un bloque opcional de filtro de Bloom: un resumen probabilístico compacto que puede responder “esta clave definitivamente no está en este archivo” sin leer nada más
• Un pie: ubica todo lo anterior

Cada elemento de este diseño existe para que las lecturas futuras procesen la menor cantidad posible de bytes, en especial el índice y el filtro de Bloom.

Recorrido por la ruta de escritura

Todo lo explicado anteriormente se puede observar de forma directa. Esta sección presenta un rastreo rápido de un Put en una base de datos mediante ldb y sst_dump, las herramientas de inspección incluidas con RocksDB. El ejemplo utiliza Rust y el crate rocksdb, aunque cualquier binding sirve.

Requisitos previos

Para seguir los pasos, instala las herramientas de línea de comandos de RocksDB y una cadena de herramientas de Rust. 

En macOS, brew install rocksdb proporciona tanto ldb como sst_dump. En Debian/Ubuntu, el paquete es rocksdb-tools.

Una vez instalados, crea un proyecto nuevo:

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

El crate rocksdb compila la biblioteca de C++ de RocksDB desde el código fuente durante la primera compilación, así que el primer cargo run tardará varios minutos.

Paso uno: escribir y detener

Reemplaza el contenido de src/main.rs con el siguiente código:

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.
}

Ejecútalo una vez con cargo run y luego enumera el contenido del directorio de la base de datos que creó:

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

CURRENT y el archivo MANIFEST registran el inventario de archivos de la base de datos, mientras que OPTIONS registra la configuración con la que se abrió. LOG, sin ningún número, es un log de texto legible para depuración y no debe confundirse con 000004.log, que es el propio log de escritura anticipada.

Los números exactos de los archivos cambiarán entre ejecuciones, pero la estructura será la misma.

Observa que no tenemos ni un solo archivo .sst en el directorio. La escritura es persistente, ya que sobrevivió al cierre del proceso, pero solo existe como registro del WAL. Esta es la separación entre persistencia y organización en acción.

Paso dos: volcar el WAL

Apunta ldb a cualquier archivo .log que contenga el directorio:

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

Tenemos un lote: el número de secuencia 1, que contiene 1 registro (29 bytes), un PUT cuya clave es la codificación hexadecimal de slot:0001. 

El tamaño coincide con la codificación anterior: un encabezado de 12 bytes más un registro de 17 bytes, que incluye una etiqueta de tipo, dos prefijos de longitud, una clave de 9 bytes y un valor de 5 bytes.

Paso tres: vaciar y volcar el SST

Primero, elimina el directorio de la base de datos (es decir, rm -rf /tmp/lsm-trace) para que esta ejecución comience desde cero.

Agrega una línea a main.rs después del put:

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

Llamar a db.flush().unwrap(); fuerza la escritura de la memtable como archivo SST en lugar de esperar a que se llene.

Vuelve a ejecutar el archivo y luego enumera el contenido del directorio. 

Ahora podemos ver un nuevo archivo .sst en la salida. Podemos inspeccionarlo con los dos modos útiles de sst_dump, sustituyendo el nombre real del archivo:

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

Ten en cuenta que sst_dump imprime algunas líneas preliminares sobre el formato del archivo antes de mostrar el resultado del análisis. Se omiten aquí y en los resultados posteriores.

Este es el par clave-valor en su nuevo hogar permanente, y todavía conserva su número de secuencia. 

Luego podemos ver sus propiedades con el siguiente comando:

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

El resultado de las propiedades enumera la anatomía del SST descrita anteriormente en el artículo: conteo y tamaño de los bloques de datos, tamaño del bloque de índice, presencia del filtro, algoritmo de compresión y conteo de entradas. 

Aunque solo tenemos una clave, se enumeran todos los elementos estructurales, con una excepción reveladora. El tamaño del bloque de filtro es cero y la política de filtro es N/A porque los filtros de Bloom son opcionales en RocksDB, se configuran mediante filter_policy y las opciones predeterminadas no establecen ninguno. 

El próximo artículo de esta serie explicará por qué casi siempre se activan en las implementaciones de producción. 

Paso cuatro: volver a abrir y revisar el log

Comenta las líneas del put y el vaciado, deja solo la línea DB::open y ejecuta el programa una vez más. Al enumerar el directorio, verás que el antiguo 000004.log desapareció y fue reemplazado por un log nuevo, casi vacío y con un número mayor. Su contenido se vació en el SST durante el paso tres, por lo que los registros quedaron obsoletos y RocksDB descartó el archivo al volver a abrir la base de datos.

Este es el acoplamiento completo entre los ciclos de vida del WAL y la memtable. 

Para profundizar un nivel más, podemos ejecutar el binario del paso uno con strace -e trace=write,fdatasync en Linux y mostrar el contrato de persistencia en el límite de las llamadas al sistema. Es decir, las llamadas secuenciales a write anexan datos al archivo .log, mientras que fdatasync solo aparece cuando se establece WriteOptions.sync.

Paso cinco: eliminar la clave y observar lo que queda

La afirmación anterior de que una eliminación es una escritura se puede observar directamente. 

Modifica main.rs para eliminar la clave y forzar otro vaciado:

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

Ejecútalo y luego enumera el directorio. 

Ahora habrá dos archivos .sst. El más antiguo permanece intacto porque es inmutable, lo que significa que todavía contiene la clave y su valor. Podemos verificarlo con un análisis:

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

Ahora analiza el archivo más reciente:

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

Es la misma clave, pero con un número de secuencia mayor, tiene type:0 en lugar de type:1 y no contiene ningún valor. Esta es una marca de eliminación: el registro kTypeDeletion de la sección WriteBatch, vaciado en su propio SST. Ahora la base de datos contiene tanto el valor como el registro de su eliminación, uno al lado del otro en archivos separados.

Al leer la clave, la contradicción se resolverá a favor de la marca de eliminación. 

Podemos comprobarlo agregando una búsqueda al programa:

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

Imprimirá not found porque la ruta de lectura revisa primero los datos más recientes, y un número de secuencia de 2 tiene prioridad sobre uno de 1. Desde el punto de vista de la base de datos, el valor desapareció, aunque todavía se encuentra en el disco dentro del archivo SST más antiguo. 

No se ha recuperado ningún espacio, lo que significa que la eliminación solo se registró y seguirá ocultando el valor hasta que la compactación fusione los dos archivos y descarte tanto la marca de eliminación como el valor oculto.

Paso seis: eliminar la clave y observar lo que queda

También se puede observar el tipo de registro Merge. Requiere configurar un operador de fusión, ya que RocksDB no sabe qué significa un operando sin uno.

Elimina de nuevo el directorio de la base de datos y reemplaza main.rs con el siguiente código:

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());
}

El volcado del WAL muestra tres registros MERGE independientes. Es decir, tres anexados en lugar de una sola lectura:

$ 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

El operador de fusión combinó la cadena durante la lectura y produjo el resultado como bytes sin procesar. El programa imprime Some([51]) porque 51 es el código ASCII del carácter 3. Una vez más, esto ocurre porque las claves y los valores son arreglos de bytes arbitrarios.

También podemos agregar db.flush().unwrap(); antes de la búsqueda, eliminar el directorio y volver a ejecutar el programa. Un análisis del SST muestra un único registro:

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

El vaciado aplicó el operador y los redujo a un único operando.

¿Por qué el nivel 0 es especial?

Los archivos SST nuevos llegan al nivel 0. Son instantáneas directas de las memtables, y cada uno abarca el rango de claves que haya absorbido esa memtable. Por eso, los archivos L0 pueden superponerse, y a menudo lo hacen. Esto difiere de todos los niveles inferiores, donde los archivos no se superponen. Cada archivo posee un rango de claves distinto, por lo que como máximo un archivo por nivel puede contener una clave determinada.

En consecuencia, cada archivo L0 es un lugar diferente donde podría ocultarse una clave, por lo que la cantidad de archivos L0 supone un costo directo para el rendimiento de lectura. Por eso RocksDB vigila de cerca la cantidad de archivos L0 y comienza a limitar, o incluso detener, las escrituras cuando aumenta demasiado.

Mantener L0 pequeño es una de las principales tareas de la compactación.

¿Por qué los árboles LSM superan a los árboles B en las escrituras?

Los árboles B pagan el costo de la organización durante la escritura para que las lecturas encuentren todo exactamente donde corresponde. Los árboles LSM aplazan la organización hasta la compactación en segundo plano, cuyo costo se paga después y por lotes.

El árbol B es la estructura que sustenta la mayoría de las bases de datos tradicionales. Actualiza los datos en el mismo lugar, lo que significa que cada escritura encuentra la página que contiene la clave, la lee, la modifica y vuelve a escribirla. Las páginas involucradas están dispersas por el disco, por lo que una secuencia de escrituras lógicamente aleatorias se convierte en una secuencia de E/S físicamente aleatoria.

El árbol LSM se niega a pagar durante la escritura. Anexa (al WAL), almacena temporalmente (en la memtable) y agrupa (en los vaciados). Cada escritura en disco es secuencial, y la deuda de organización se aplaza hasta la compactación. El trabajo no desaparece. Se paga después y por lotes, consolidado en un formato que los discos manejan muy bien.

Esto es muy importante en las unidades SSD porque no pueden sobrescribir datos en el mismo lugar. 

El almacenamiento flash se borra en bloques grandes, que abarcan desde cientos de kilobytes hasta megabytes, y se escribe en páginas más pequeñas. Esto significa que cada pequeña sobrescritura aleatoria obliga a la capa de traducción flash (FTL) de la unidad a reubicar los datos activos y borrar bloques en segundo plano. 

Las escrituras aleatorias de páginas de un árbol B obligan a la FTL a hacerlo constantemente. El dispositivo impone una amplificación de escritura que se suma a la que genera la propia estructura de datos, y su costo se paga tanto en rendimiento como en vida útil de la unidad. Las escrituras secuenciales grandes de un árbol LSM se acercan al mejor escenario posible para el hardware flash.

La mejor forma de entenderlo es como un préstamo. La organización aplazada se cobra como E/S de compactación, y las lecturas deben revisar más lugares de los que requeriría un árbol B. Por lo tanto, el árbol LSM obtiene rendimiento de escritura ahora y lo paga después mediante la amplificación de lectura y espacio. 

Para ver con más detalle cómo se compara el árbol LSM con el árbol B en cuanto a la amplificación de lectura, escritura y espacio, consulta Árbol B frente a árbol LSM. 

¿Qué ocurre después de que RocksDB falla?

La memtable reside en memoria volátil, lo que significa que un fallo la borra. Esta es precisamente la razón por la que existe el WAL.

Al reiniciarse, RocksDB reproduce cada escritura que se había confirmado pero que aún no se había vaciado en un SST. Las inserta en una memtable nueva para reconstruir el estado anterior al fallo. El costo de recuperación es proporcional a los datos no vaciados, por eso están vinculados los ciclos de vida del WAL y la memtable. Una vez que el contenido de una memtable se vacía de forma segura en un SST, las entradas correspondientes del log quedan obsoletas y el WAL puede truncarse.

Una escritura se vuelve persistente en cuanto se guarda el anexado al log. Después se vuelve fácil de leer cuando el vaciado la organiza. Los árboles B acoplan ambos procesos, mientras que los árboles LSM los separan, y gran parte del carácter de esta estructura surge de esa separación. 

¿Cómo somete Solana la ruta de escritura a presión?

El primer artículo de esta serie describió cómo Agave almacena el ledger de Solana en RocksDB. Desde la perspectiva de la ruta de escritura, esa carga de trabajo se asemeja a una prueba de estrés diseñada específicamente para este fin. Es decir, los shreds (las unidades sin procesar de datos del ledger) llegan continuamente por la red a la velocidad de la línea, y cada uno debe completar la ruta de anexado al WAL e inserción en la memtable antes de que la capa de almacenamiento del validador termine su trabajo.

El mecanismo involucrado es exactamente el mismo que se rastreó en este artículo, pero a escala de producción. Cuando llegan los shreds, la ruta de inserción de Blockstore en Agave valida un lote completo de shreds entrantes, intenta la recuperación Reed-Solomon de los que falten y prepara todo (cargas útiles de shreds, metadatos de slots, metadatos de borrado y actualizaciones de índices) en un único WriteBatch de RocksDB antes de confirmarlo mediante una sola escritura atómica.

Versión simplificada 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);

Ese comentario resume en nueve palabras la idea central de este artículo según los ingenieros de Agave: el lote es la unidad de atomicidad, y un fallo del validador durante la inserción nunca debe dejar el ledger actualizado a medias. 

El lote de un elemento rastreado en el recorrido se convierte, dentro de un validador, en un lote de miles: shreds y sus metadatos repartidos entre varias familias de columnas, un rango de números de secuencia, un anexado al WAL y una confirmación grupal.

Lo bueno es que los shreds comienzan con el número de slot (es decir, la tupla (slot, index) del fragmento de código simplificado es la clave ShredData), y los slots aumentan de manera casi monótona. Por lo tanto, cada memtable absorbe una franja estrecha y prácticamente consecutiva del espacio de claves, y los vaciados producen archivos L0 que apenas se superponen.

Experimentamos directamente esta ruta de escritura. 

Los sistemas de archivo que operamos en Helius ingieren el historial completo de transacciones de Solana en RocksDB —cientos de terabytes en una carga de trabajo con anexado intensivo y crecimiento permanente—, y la migración que produjo esa arquitectura está documentada en nuestro artículo sobre la migración de ClickHouse a RocksDB.

Conclusión

Un árbol LSM es un acuerdo con el hardware. Todas las escrituras se vuelven secuenciales a cambio de aplazar el trabajo de mantener los datos organizados. Esto significa que la ruta de lectura debe buscar los datos en más lugares que, por ejemplo, un árbol B. La memtable absorbe, el WAL garantiza y los SST se acumulan. En el almacenamiento flash, donde las sobrescrituras aleatorias reciben una doble penalización, este es un acuerdo excelente.

Sin embargo, las escrituras son la mitad sencilla. El precio de este diseño se paga en las lecturas, ya que el valor actual de una clave podría existir en la memtable, en un archivo L0 o en cualquier nivel inferior. El mecanismo que mantiene ese costo bajo control es donde la ingeniería de LSM se vuelve realmente interesante. 

El próximo artículo de la serie recorrerá la ruta de lectura y explicará las memtables, los filtros de Bloom, la caché de bloques y el triángulo de amplificación en acción.

Si seguir un único par clave-valor a través de cuatro estructuras de datos diferentes te parece una buena forma de pasar la tarde, ven a desarrollar con nosotros. Los sistemas descritos en esta serie son los que implementamos, operamos y optimizamos a la escala de los mercados de capitales de Internet. Estamos contratando para todo nuestro equipo de ingeniería. Consulta todos nuestros puestos disponibles en helius.dev/careers.