Log-Structured Merge Tree
Un arbre LSM ajoute les écritures à une table en mémoire, la vidant vers des SSTables immuables une fois pleine, avec une compression multi-niveaux équilibrant le débit d'écriture contre l'amplification de lecture.
Objectif
Comprendre la structure de données centrale des moteurs de stockage à écriture intensive, utilisée dans LevelDB/RocksDB/Cassandra.
Mécanisme
Les écritures vont dans une MemTable (skip list en mémoire) ; une fois pleine, elle est vidée vers une SSTable L0. Les lectures fusionnent toutes les SSTables et la MemTable. La compaction fusionne les niveaux adjacents pour réduire l'amplification de lecture. Les écritures séquentielles du LSM optimisent le débit au prix de l'amplification de lecture et d'espace.
Cas d’usage
- Conception de stockage à écriture intensive
- Optimisation des SSTables
- Compaction LSM