LSM-Tree (Log-Structured Merge-Tree)

In Cassandra, HBase, RocksDB (und damit CockroachDB, TiDB). Wenn du eine DB für "Write-Heavy" Workloads (z. B. Sensor-Daten, Event-Logs) brauchst, wähle eine LSM-basierte DB. Wenn du viele Updates/Deletes auf denselben Rows hast, ist LSM manchmal langsamer als B-Tree (wegen Compaction Overhead).

1. Compaction Strategies

• Size-Tiered: (Cassandra Standard). Viele kleine Files werden zu einem großen gemergt. Schnell beim Schreiben (wenig Write Amplification), langsam beim Lesen.
• Leveled: (LevelDB/RocksDB). Jedes Level ist 10x größer als das vorige. Garantiert bessere Lese-Performance (weniger Files zu prüfen), aber höhere Write-Kosten (mehr Merges).

2. Bloom Filters

LSM-Trees wären beim Lesen katastrophal langsam ($O(N)$ Files checken), wenn es keine Bloom Filter gäbe. Jede SSTable hat einen Bloom Filter. Bevor die DB liest, fragt sie den Filter: "Ist Key X überhaupt hier drin?" Filter sagt "Nein" -> Datei wird übersprungen. Das macht Reads fast so schnell wie bei B-Trees ($O(1)$ Disk Seek).

1. Write Amplification Penalty (WAP) in RocksDB

Das ewige Trilemma der NoSQL-Datensysteme (Rum-Conjecture) zwingt Architekten zu Kompromissen zwischen Read (R), Update (U) und Memory (M). LSM-Trees leiden radikal unter exponentieller Write Amplification. In der "Leveled Compaction" (Standard bei AWS DynamoDB Storage) verschwinden SSTables nicht spurlos. Wenn Level 1 eine 10MB Table in Level 2 (100MB fassend) heruntermerged, muss RocksDB oft die komplette Region in Level 2 dekomprimieren, in RAM holen, mit den 10MB sortieren, und als brandneue SSTable Blöcke runterschreiben. Das resultiert in einer Amplification von $F \cdot L$ (Fanout x Lagen). Effektiv führt ein winziges 1 Byte UPDATE age=30 im RAM zu bis zu 30–50 Bytes SSD Flash-Burn, was die Lebensdauer (TBW - Terabytes Written) von Enterprise-NVMe Festplatten im Dauerfeuer der Sensor-Daten regelrecht pulverisiert. O-Key-Update-Systeme benötigen SSDs mit gewaltigem Hardware-Overprovisioning.

2. Fused Compaction via Block-basierenden Bloom Filters

Klassische Read-Routen bei Lese-Misses ("Key=XYZ" prüfen und es ist nirgendwo) sind der Feind der Latenz, daher integriert man Bloom Filters. Die tieferen Optimierungstricks liegen in der granular-feinen Matrix der Bits. Statt eines gigantischen Filter Arrays pro "SSTable" speichern hochperformante LSMs Block-Based Bloom Filters. Die 128 MB .sst Datei wird in hunderten 4KB "Data Blocks" gesnapped. Der SST-Header beinhaltet ein Micro-Register an hunderten Mini-Bloom-filtern, die genau das Vorhandensein eines Keys in einem mikroskopischen 4 KB Disk-Fenster verneinen. Somit kann die Storage Engine mit minimalstem Heap-Space-Memory die $O(1)$-Disksuche auf ein einzelnes Sektor-Read begrenzen, wo ein normaler globaler Bloom Filter noch 5 nutzlose Sektorpagings provoziert hätte.

3. Read Amplification vs Tiered Merge-Heuristik

In Szenarien wo man Write-Rate priorisiert (Apache Cassandra in Heavy-Ingest), baut man auf Size-Tiered Compaction Strategy (STCS). Hier werden L0 Tables einfach so lange aufgereiht, bis z.B. 4 Tables identischer Größe nebeneinander existieren. Diese werden dann massig zu einer L1-Table (4x so fett) gestampft. Vorteil: Extrem tiefe Write-Ersparnis. Massives Produktionsproblem (Read Amplification): Ein Lesevorgang muss per Iterator die Top-N Keys durch alle SSTable Ebenen matchen. Bei Size-Tiered häufen sich "Duplicate Mutations" desselben Datensatzes völlig verstreut in overlapping Key-Ranges der SSTables. Die CPU verbrennt Latenzzeit via Merging-Iteratoren und Priority-Queues (MinHeap Array), um den neuesten Versions-Key aus dem Disk-Wirrwarr parallel-on-the-fly zusammenzupuzzlen. Wer Read-Latenz (wie im Webbrowser IndexedDB) liebt, meidet Size-Tiered radikal!