Un Log-Structured Merge-tree (LSM-tree) es una estructura de datos persistente diseñada para manejar eficientemente grandes volúmenes de escrituras y actualizaciones. Opera manteniendo los datos en múltiples componentes ordenados: un componente en memoria (memtable) y uno o más componentes en disco (SSTables o Run Files). Las escrituras se aplican primero al memtable y a un write-ahead log (WAL) para durabilidad. Cuando el memtable alcanza un cierto tamaño, se vacía a un nuevo SSTable inmutable en disco. Periódicamente, los SSTables en disco se fusionan (compactan) en segundo plano para eliminar duplicados, liberar espacio y mantener un número manejable de archivos, optimizando así las lecturas. Este diseño prioriza las escrituras secuenciales, que son más rápidas que las escrituras aleatorias, y difiere el costo de organización de datos a las operaciones de compactación en segundo plano.
La implementación de LSM-trees es fundamental en muchos sistemas de almacenamiento NoSQL y bases de datos modernas. Ejemplos prominentes incluyen Apache Cassandra, que utiliza LSM-trees para su almacenamiento de datos distribuidos y tolerante a fallos, y Apache HBase, que los emplea como su motor de almacenamiento subyacente. RocksDB, una biblioteca de almacenamiento incrustable de alto rendimiento, es otra implementación popular de LSM-tree, utilizada en sistemas como CockroachDB y Apache Flink. Google Bigtable, uno de los pioneros en bases de datos NoSQL, también se basa en principios similares a los LSM-trees. Estos sistemas aprovechan la eficiencia de escritura de los LSM-trees para escalar horizontalmente y manejar grandes volúmenes de datos con alta disponibilidad.
Para un arquitecto, el LSM-tree es una elección estratégica para sistemas con cargas de trabajo intensivas en escritura, como bases de datos de series temporales, logs de eventos o sistemas de mensajería. Su principal ventaja es la alta tasa de escritura y la durabilidad, ya que las escrituras son principalmente secuenciales. Sin embargo, introduce trade-offs importantes: las lecturas pueden ser más lentas debido a la necesidad de consultar múltiples componentes (memtable y SSTables) y fusionar los resultados. La compactación en segundo plano consume recursos de CPU e I/O, lo que puede generar picos de latencia o afectar el rendimiento de las operaciones en primer plano si no se gestiona adecuadamente. La elección de un LSM-tree implica aceptar una mayor complejidad operativa y de ajuste para optimizar la compactación, el tamaño de los SSTables y la estrategia de lectura, buscando un equilibrio entre rendimiento de escritura, latencia de lectura y uso de recursos.