LSM-Tree und Sorted String Tables

Kurz: Ein LSM-Tree sammelt Schreibvorgänge zuerst im Speicher und schreibt sie gebündelt und sortiert auf die Platte. Das macht Schreiben sehr schnell, Lesen braucht dafür mehr Arbeit.

Genauer: Neue Daten landen in einer Memtable (sortiert im RAM) und im Write-Ahead-Log. Ist die Memtable voll, wird sie als unveränderliche, sortierte Datei (SSTable) gespeichert. Im Hintergrund fasst die Compaction viele kleine Dateien zu größeren zusammen und entfernt veraltete Werte.

Im Detail

• Lesen: Erst Memtable, dann SSTables von neu nach alt. Bloom-Filter sparen unnötige Plattenzugriffe.
• Löschen: Wird als Markierung (Tombstone) geschrieben und bei der Compaction entfernt.
• Compaction: Kompromiss aus Schreib-, Lese- und Platzverstärkung.
• Strategien: Size-tiered (günstig schreiben) und leveled (günstig lesen).
• Einsatz: RocksDB, LevelDB, Cassandra, HBase.
• Gegenstück: B-Baum, besser für Lesen und Bereichsabfragen mit weniger Schreibverstärkung bei kleinen Updates.

Siehe auch: B-Baum und B+-Baum, Write-Ahead-Log und Wiederherstellung