LSM Trees : la révolution log-structured
Les moteurs de stockage modernes doivent concilier durabilité, performance d’écriture, efficacité de lecture et comportement prévisible. Les architectures B-Tree traditionnelles excellent pour les recherches ponctuelles, mais elles s’essoufflent lorsqu’il faut absorber un volume massif d’écritures ou fonctionner sur du matériel à bande passante limitée. Les Log-Structured Merge Trees (LSM Trees) proposent une alternative radicale, centrée sur une idée simple : ne jamais modifier les données en place.
Cette approche append-only, déjà au cœur de Bigtable, LevelDB et RocksDB, permet d’atteindre des débits d’ingestion très élevés tout en restant adaptée à des environnements variés. Y compris ceux où le CPU est la ressource la plus stable.
Le principe log-structured
Le LSM repose sur une intuition élégante : remplacer les écritures aléatoires par des ajouts séquentiels.
À la place de modifier directement des pages sur disque, le moteur stocke les écritures dans une memtable, puis les transforme en fichiers immuables — les SSTables.
Écriture → Memtable
│
└─ flush → SSTable immuable
Cette stratégie améliore les performances, simplifie la récupération après crash et permet d’optimiser l’utilisation du disque.
De la memtable aux SSTables : une hiérarchie de stockage
Un moteur LSM organise ses données en plusieurs niveaux :
+----------------------+
| Memtable |
+----------------------+
│ flush
▼
+----------------------+
| SSTable Niveau 0 |
+----------------------+
│ compaction
▼
+----------------------+
| SSTable Niveau 1 |
+----------------------+
Memtable
Structure en mémoire, triée, utilisée pour absorber les écritures.
SSTables
Fichiers triés, immuables, contenant blocs, index et bloom filters.
L’immuabilité simplifie fortement la concurrence et garantit un état cohérent même après crash.
La compaction : le moteur invisible
Sans compaction, les SSTables s’accumuleraient, dégradant les lectures. La compaction fusionne les fichiers, élimine les clés obsolètes et maintient une hiérarchie bien structurée.
Niveau 0
│
├─→ Compaction → Niveau 1 fusionné
└─→ Suppression des fichiers obsolètes
Elle assure performance et cohérence, mais représente aussi le principal coût des moteurs LSM.
LSM vs B-Tree : deux philosophies
| Aspect | B-Tree | LSM Tree |
|---|---|---|
| Écriture | Aléatoire, mise à jour en place | Append-only, séquentielle |
| Lecture | Excellente pour lookup direct | Nécessite plusieurs niveaux |
| Gestion d’espace | Split/merge | Compaction |
| Durabilité | WAL + pages | WAL + fichiers immuables |
| Force | Lectures optimisées | Débits d’écriture très élevés |
| Faiblesse | Sensible aux workloads écriture | Coût de compaction |
Les LSM ne remplacent pas les B-Trees : ils répondent à d’autres contraintes. Leur popularité découle d’un monde où les systèmes doivent absorber des flux continus, fonctionner en cloud ou sur matériel limité.
Conclusion
Les LSM Trees incarnent une évolution majeure des moteurs de stockage. Leur approche log-structured, centrée sur l’immuabilité et les écritures séquentielles, offre une robustesse et une scalabilité très difficiles à atteindre avec des architectures traditionnelles. De Bigtable à RocksDB, ils sont devenus le socle de nombreux systèmes modernes.
Comprendre les LSM est essentiel pour analyser le comportement des moteurs, anticiper leurs performances et concevoir des architectures adaptées.
Références recommandées
- Google — Bigtable: A Distributed Storage System for Structured Data
- O’Neil et al. — “The Log-Structured Merge-Tree (LSM-Tree)”
- Documentation LevelDB — Design
- RocksDB Engineering Notes
- Sears & Ramakrishnan — “bLSM: A General Purpose Log Structured Merge Tree”