Der LSM-Tree (Log-Structured Merge Tree) ist eine 1996 von Patrick O'Neil und Kollegen vorgestellte Datenstruktur, die randomisierte Schreibzugriffe in sequenzielle umwandelt. Er ist das Speicherfundament vieler NoSQL- und eingebetteter Datenbanken wie LevelDB, RocksDB, Apache Cassandra, ScyllaDB und HBase.
Das Grundprinzip: Schreiben im Speicher, Mergen auf der Platte
Ein LSM-Tree besteht aus mehreren Ebenen:
- MemTable: Neue Schreibvorgänge landen zunächst in einer sortierten In-Memory-Struktur, häufig einer Skip-Liste. So entstehen keine teuren Random Writes auf der Festplatte.
- WAL (Write-Ahead-Log): Parallel wird jeder Schreibvorgang append-only ins Log geschrieben, damit nach einem Absturz nichts verloren geht.
- SSTables: Ist die MemTable voll, wird sie als sortierte, unveränderliche Datei (Sorted String Table) auf die Platte geschrieben. Im Hintergrund führt Compaction die sortierten Dateien zusammen, entfernt veraltete Versionen und hält die Ebenen klein.
Weil nur sequenziell geschrieben und im Hintergrund gemerged wird, erreichen LSM-Trees bei schreiblastigen Workloads deutlich höhere Durchsätze als klassische B-Bäume, die bei jedem Update an Ort und Stelle schreiben müssen.
Lesen: Der Preis der Schreiboptimierung
Ein Schlüssel kann in mehreren SSTables liegen — der Preis der Schreiboptimierung ist eine aufwändigere Suche: Die Ebenen werden von der jüngsten zur ältesten durchsucht. Drei Techniken halten Lesevorgänge schnell:
- Bloom-Filter: Vor jeder SSTable-Suche prüft ein Bloom-Filter, ob der Schlüssel überhaupt enthalten sein kann — nicht betroffene Dateien werden übersprungen.
- Block-Caches: Häufig gelesene Blöcke bleiben im RAM.
- Compaction: Regelmäßiges Mergen reduziert die Zahl der zu durchsuchenden Dateien.
Compaction-Strategien
- Size-Tiered Compaction: Mehrere ähnlich große SSTables werden zu einer größeren zusammengeführt (Cassandra-Standard).
- Leveled Compaction: Die Daten werden in strikt getrennte Level aufgeteilt, jedes Level ist sortiert (LevelDB/RocksDB) — bessere Leselatenzen, aber mehr Schreibverstärkung.
Verwandte Grundlagen: Bloom-Filter, Skip-Liste, NoSQL-Datenbank, Key-Value-Store, Sharding.