Facebook, Netflix y LinkedIn corren sus bases de datos de mayor volumen de escritura sobre la misma idea: nunca modificar un archivo que ya quedó escrito en disco. Esa regla, aparentemente simple, es el corazón de los árboles LSM (Log-Structured Merge-Tree), la estructura de datos que sostiene a RocksDB, Cassandra, LevelDB y decenas de sistemas que necesitan aceptar un volumen alto de escrituras concurrentes sin bloquear al que llega detrás.
La memtable en RAM, el write-ahead log, los SSTables inmutables en disco y el proceso de compactación (compaction) definen si esa promesa de velocidad se mantiene con el tiempo o se degrada.
TL;DR
- Vas a entender por qué un árbol LSM escribe más rápido que un B-tree tradicional.- Vas a poder distinguir memtable, write-ahead log (WAL) y SSTable en cualquier base de datos basada en LSM.- Vas a saber qué es la compactación (compaction) y por qué determina el rendimiento a largo plazo.- Vas a poder instalar y probar RocksDB en Python con un ejemplo funcional.- Vas a identificar cuándo NO conviene usar una base de datos basada en LSM.- Vas a conocer los comandos exactos para verificar el estado de la compactación en RocksDB y Cassandra.- Vas a comparar árboles LSM contra B-trees con una tabla de decisión práctica.
Qué es un árbol LSM y por qué importa
Un árbol LSM (Log-Structured Merge-Tree) es una estructura de datos pensada para bases de datos que necesitan absorber muchas escrituras sin pagar el costo de reescribir un archivo entero cada vez. La idea nace de un paper de 1996 firmado por Patrick O'Neil, Edward Cheng, Dieter Gawlick y Elizabeth O'Neil, que proponía separar la escritura (rápida, secuencial, en memoria) de la organización final de los datos, que ocurre después, en segundo plano.
Un B-tree, la estructura que usan Postgres o MySQL/InnoDB por defecto, actualiza el dato en su lugar: busca la página exacta donde vive la clave y la reescribe. Esa operación es barata para leer, pero cara para escribir cuando hay mucha concurrencia, porque cada escritura implica localizar una página en disco y modificarla. Un árbol LSM invierte la lógica: nunca busca ni modifica una página existente. Todo lo nuevo se agrega al final, ordenado, en archivos que después se fusionan. Escribir en RocksDB o Cassandra es, en esencia, un append: no hay búsqueda previa, no hay bloqueo de una página compartida.
Esta arquitectura importa porque decide qué motor conviene en cada escenario: sensores IoT, logs de eventos, series temporales y feeds de actividad, es decir, todo lo que escribe mucho más de lo que borra.
Cómo funciona un árbol LSM por dentro
Cuando una aplicación escribe una clave en una base de datos basada en árboles LSM, pasan dos cosas casi simultáneas. Primero, el motor anota la operación en el write-ahead log (WAL), un archivo de solo apéndice en disco que garantiza que la escritura sobrevive a un corte de energía. Segundo, la misma clave se inserta en la memtable, una estructura ordenada en memoria RAM (normalmente un skip list o un árbol rojo-negro) que mantiene las claves recientes disponibles para lectura inmediata.
La memtable tiene un tamaño límite. Cuando se llena, el motor la vuelca a disco como un SSTable (Sorted String Table): un archivo inmutable, ordenado por clave, que nunca vuelve a modificarse. Ese nunca modificarse es la clave de todo el diseño: una vez escrito, un SSTable solo se lee o se borra, jamás se edita en el lugar.
flowchart LR
A["Escritura (SET key)"] --> B["WAL (write-ahead log)"]
A --> C["Memtable (arbol en memoria)"]
C -->|"memtable llena"| D["Flush a SSTable"]
D --> E[("Disco: SSTables inmutables")]
Con el tiempo se acumulan decenas de SSTables en el nivel más superficial (L0). Leer una clave implicaría entonces revisar la memtable y, en el peor caso, todos los SSTables de L0 uno por uno. Para evitar esa degradación, un proceso en segundo plano llamado compactación fusiona varios SSTables en uno nuevo, más grande, descartando las versiones viejas de cada clave y los tombstones (marcadores de borrado) que ya cumplieron su propósito. El resultado de una compactación se promueve a un nivel más profundo: L1, L2 y así sucesivamente, cada uno más grande y más frío que el anterior.
sequenceDiagram
participant M as Memtable
participant L0 as SSTable L0
participant L1 as SSTable L1
M->>L0: flush cuando la memtable se llena
L0->>L1: compaction fusiona y ordena
Note over L0,L1: se descartan claves duplicadas y tombstones
Cada SSTable además guarda un filtro de bloom por clave, una estructura probabilística que permite responder rápido si una clave definitivamente no está en ese archivo, sin necesidad de abrirlo. Esa combinación de SSTables ordenados, niveles y filtros de bloom es lo que permite que una lectura no tenga que revisar todos los archivos en disco.
Cada escritura se agrega al final: nunca se reescribe una página existente.
Ejemplos prácticos
El comportamiento de un árbol LSM se entiende mejor viéndolo en código. El primer ejemplo simula, en pocas líneas, lo mínimo que hace cualquier motor basado en LSM: acumular escrituras en memoria y volcarlas ordenadas a un archivo.
class MemTable:
def __init__(self):
self.data = {}
def put(self, key, value):
self.data[key] = value
def flush_to_sstable(self, path):
with open(path, 'w') as f:
for key in sorted(self.data):
f.write(key)
f.write('=')
f.write(self.data[key])
f.write(chr(10))
self.data = {}
memtable = MemTable()
memtable.put('usuario:42', 'ana')
memtable.put('usuario:7', 'beto')
memtable.flush_to_sstable('sstable_0001.txt')
Al correr este script, memtable.data queda vacío después de flush_to_sstable, y el archivo sstable_0001.txt contiene las dos claves ordenadas alfabéticamente (usuario:42 antes que usuario:7, porque la comparación es de texto, no numérica). Ese detalle (el orden es lexicográfico, salvo que la aplicación lo controle) es una fuente común de sorpresas al diseñar claves para producción.
El segundo ejemplo usa RocksDB de verdad, a través del binding oficial de Python, para mostrar cómo se ve la misma idea en un motor de producción.
import rocksdb
opts = rocksdb.Options()
opts.create_if_missing = True
db = rocksdb.DB('tienda.db', opts)
db.put(b'producto:1001', b'teclado mecanico')
db.put(b'producto:1002', b'mouse inalambrico')
valor = db.get(b'producto:1001')
print(valor)
stats = db.get_property(b'rocksdb.num-files-at-level0')
print(stats)
Este código crea o abre una base en el directorio tienda.db, escribe dos claves y las lee de vuelta. La llamada a get_property con la propiedad rocksdb.num-files-at-level0 devuelve cuántos SSTables hay actualmente en el nivel L0; es la forma más directa de confirmar, desde código, que el motor está generando archivos y no solo acumulando todo en la memtable.
Cómo empezar
Para probar un árbol LSM sin escribir un motor propio alcanza con instalar RocksDB o levantar un nodo de Cassandra. Ambos exponen, con distintos comandos, exactamente los mismos conceptos: memtable, SSTable y compactación.
En Linux, instalar el binding de Python de RocksDB requiere primero la librería nativa:
sudo apt-get install librocksdb-dev
pip install python-rocksdb
Con eso instalado, el segundo bloque de código de la sección anterior ya corre tal cual. Para forzar una compactación manual y ver el efecto en los niveles, se puede llamar directamente al método de compactación del binding:
db.compact_range()
💡 Tip: forzar una compactación completa con compact_range() está pensado para pruebas o mantenimiento puntual. Llamarlo en cada escritura en producción anula la ventaja de las escrituras en segundo plano.
Esa llamada fusiona los SSTables pendientes y actualiza los contadores por nivel. Volver a leer rocksdb.num-files-at-level0 después de compact_range() debería devolver un número menor, o cero, al que había antes.
Si el interés es Cassandra en vez de RocksDB, el comando equivalente para inspeccionar el estado de la compactación es:
nodetool compactionstats
Ese comando, ejecutado en cualquier nodo Cassandra, muestra las compactaciones en curso, cuántos bytes lleva procesados cada una y cuántas están pendientes en la cola. Es el primer lugar donde mirar cuando la latencia de escritura empieza a subir sin motivo aparente.
Casos de uso reales
RocksDB, desarrollado por Facebook a partir de LevelDB, es hoy el motor de almacenamiento embebido detrás de MyRocks (el motor alternativo a InnoDB para MySQL), de CockroachDB y de Kafka Streams para el estado local de las tareas.
Apache Cassandra usa árboles LSM desde su diseño original, inspirado en el paper de Google sobre Bigtable y en el paper de Amazon sobre Dynamo. Cada nodo Cassandra mantiene su propia memtable, su propio commit log (el equivalente al WAL) y sus propios SSTables en disco, lo que le permite escalar horizontalmente sin coordinar cada escritura entre nodos.
LevelDB, la base sobre la que Google construyó RocksDB, corre embebido dentro de Chrome para IndexedDB y dentro de Bitcoin Core para el índice de bloques. En ambos casos el patrón de acceso es el mismo que motivó el diseño original: muchas escrituras secuenciales, lecturas por clave y tolerancia a que una lectura ocasional sea un poco más lenta a cambio de escrituras consistentemente rápidas.
MyRocks reemplaza a InnoDB dentro de MySQL con este mismo diseño.
Errores comunes y buenas prácticas
El error más frecuente al operar una base LSM es no vigilar la amplificación de escritura (write amplification): cada compactación reescribe datos que ya estaban en disco, así que una clave puede terminar escribiéndose físicamente varias veces antes de llegar a su nivel final. Ignorar esta métrica lleva a un sistema que consume mucho más ancho de banda de disco del que sus escrituras lógicas deberían justificar.
⚠️ Ojo: si el ritmo de escritura supera la velocidad de compactación, los SSTables de L0 se acumulan sin control. Esto se conoce como compaction storm y termina bloqueando las escrituras nuevas hasta que la compactación se pone al día.
Otro error común es diseñar claves que crecen siempre al final del rango, como timestamps ascendentes o IDs autoincrementales. Eso concentra toda la escritura en un mismo rango de SSTables y reduce el paralelismo que la compactación podría aprovechar. La práctica recomendada es distribuir el prefijo de la clave, por ejemplo con un hash corto, cuando el volumen de escritura es alto.
Los tombstones en Cassandra son otra fuente típica de problemas: si una aplicación borra y reescribe la misma clave con frecuencia, los tombstones se acumulan entre compactaciones y una lectura puede terminar descartando cientos de versiones muertas antes de encontrar el valor vigente. Cassandra expone el umbral de tombstones por lectura en sus logs de advertencia, y subirlo sin entender la causa solo pospone el problema.
Comparativa con alternativas
La pregunta de si conviene un árbol LSM o un B-tree no tiene una respuesta única: depende del patrón de acceso.
EstructuraMejor paraVentaja principalLimitaciónB-tree (Postgres, InnoDB)Cargas con muchas lecturas y actualizaciones puntualesLectura de un solo registro muy predecibleEscritura cara: cada update reescribe una página en su lugarLSM-tree (RocksDB, Cassandra, LevelDB)Cargas con escritura intensiva: logs, series temporales, eventosEscritura secuencial, casi siempre un appendAmplificación de escritura por compactación y lecturas más costosas sin bloom filtersHash index (Redis, memcached)Acceso por clave exacta, sin rangos ni ordenLectura y escritura en tiempo constanteNo soporta consultas por rango ni orden de claves
Profundizando
La decisión de diseño más importante dentro de un motor LSM es la estrategia de compactación: leveled compaction contra size-tiered compaction, también llamada tiered.
En leveled compaction, cada nivel tiene un tamaño máximo fijo y las claves de un nivel no se solapan entre SSTables del mismo nivel. Cuando un nivel supera su límite, un SSTable se fusiona con los SSTables del nivel siguiente que cubren el mismo rango de claves. RocksDB usa leveled compaction por defecto porque minimiza el espacio en disco y acota la amplificación de lectura, a costa de más trabajo de compactación en segundo plano.
En size-tiered compaction, el motor agrupa SSTables de tamaño similar y los fusiona cuando se acumulan suficientes del mismo tamaño, sin garantizar que las claves de un nivel no se solapen. Cassandra ofrece ambas estrategias configurables por tabla: SizeTieredCompactionStrategy, la histórica, y LeveledCompactionStrategy, pensada para tablas con más lecturas que escrituras.
flowchart TD
A["Memtable (RAM)"] --> B["Nivel L0 (SSTables recientes)"]
B --> C["Nivel L1"]
C --> D["Nivel L2"]
D --> E["Nivel LN (mas frio, mas grande)"]
subgraph Compaction
B
C
D
end
La tabla también revela otra tensión de diseño: los filtros de bloom. Cada SSTable guarda uno para poder responder que una clave no está ahí sin abrir el archivo. Cuantos más niveles tenga que revisar una lectura, más filtros se consultan antes de tocar disco; ajustar la tasa de falsos positivos de esos filtros, a costa de más memoria RAM, es la palanca más directa para bajar la latencia de lectura en un motor LSM maduro.
📖 Resumen en Telegram: Ver resumen
Tu próximo paso: instalá python-rocksdb, corré el segundo ejemplo de código de este artículo y compará el valor de rocksdb.num-files-at-level0 antes y después de llamar a compact_range().
Preguntas frecuentes
¿Qué significa LSM en árbol LSM?
LSM son las siglas de Log-Structured Merge-Tree: una estructura organizada como un registro de solo apéndice que se fusiona en segundo plano para mantenerse ordenada.
¿Por qué los árboles LSM escriben más rápido que un B-tree?
Porque cada escritura es un append en memoria y en el write-ahead log, sin necesidad de localizar ni modificar una página existente en disco, como sí ocurre en un B-tree.
¿Qué bases de datos usan árboles LSM?
RocksDB, Cassandra, LevelDB, ScyllaDB, HBase y MyRocks, el motor de almacenamiento alternativo para MySQL, están construidos sobre árboles LSM.
¿Qué es la amplificación de escritura?
Es la relación entre los bytes que la aplicación pidió escribir y los bytes que el motor termina escribiendo físicamente en disco debido a las compactaciones sucesivas.
¿Cuándo no conviene una base de datos basada en árboles LSM?
Cuando la carga es mayormente de lecturas puntuales sobre datos que casi no cambian: ahí un B-tree ofrece latencia de lectura más predecible sin pagar el costo de la compactación en segundo plano.
¿Qué relación tienen los SSTables con los árboles LSM?
Un SSTable es la unidad de almacenamiento inmutable en disco que resulta de volcar una memtable llena; la sucesión de niveles de SSTables, fusionados por compactación, es lo que constituye el árbol LSM.
Referencias
- Repositorio oficial de RocksDB: código fuente, documentación de diseño y el binding de Python usado en los ejemplos.- Repositorio oficial de LevelDB: la implementación original de Google en la que se basó RocksDB.- Documentación de Apache Cassandra: referencia de nodetool, estrategias de compactación y arquitectura interna.- Log-structured merge-tree, Wikipedia: historia del paper original de 1996 y variantes del diseño.
📱 ¿Te gusta este contenido? Únete a nuestro canal de Telegram @programacion donde publicamos a diario lo más relevante de tecnología, IA y desarrollo. Resúmenes rápidos, contenido fresco todos los días.
Top comments (0)