Storage Engines: LSM-Tree, Compaction, Write Amplification und die Wahl der Engine

Track Konzepte · Datenbank-Interna · ca. 50 Min.

Was du aus Teil a brauchst

Ein B-Baum ändert Seiten an ihrem Platz, schreibt dafür ganze Seiten und macht Änderungen mit einem Write-Ahead Log absturzsicher: erst ins Log, dann in die Seiten. Gezählt werden Seitenzugriffe, nicht Vergleiche. Falls das neu ist: Teil 1.

Worum es geht

Der LSM-Tree (log-structured merge tree) dreht den Spieß um: Er ändert nie eine Seite an ihrem Platz, sondern hängt nur an und räumt später auf. Das macht Schreiben billig und Lesen und Aufräumen teuer, und genau diesen Handel musst du beurteilen können, wenn du eine Datenbank für eine Last wählst.

Am Ende dieses Teils kannst du:

  • den Lesepfad eines LSM-Trees mit Memtable, Runs und Tombstones bauen, auch für Bereichsabfragen (Übung 1),
  • Write Amplification (Schreibverstärkung) rechnen und Tiered gegen Leveled Compaction vergleichen (Übung 2),
  • zu Randbedingungen (schreiblastig, lesbar, Bereichsabfragen) die passende Engine wählen (Übung 3).

Bloom Filter kommen hier als Hilfsmittel vor und stehen in Lektion 20 Teil 2.

Plane ehrlich 50 Minuten ein: etwa 20 Minuten Lesen, 30 Minuten Übungen (drei Stück). Eine gute Pause ist nach Übung 1.

Von JS/TS her gedacht

Du kennst In der Storage Engine
Array.push und später aufräumen LSM-Tree: anhängen, später Compaction
Eine Kopie mit {...alt, ...neu} zusammenführen Compaction: Runs zusammenführen, neuere Einträge überschreiben ältere
delete als “ist gelöscht”-Markierung (Soft Delete) Tombstone: Marker statt echtes Löschen

Eine Beobachtung nebenbei: Wenn du in Node je level (LevelDB) verwendet hast, hast du einen LSM-Tree benutzt (allgemeines Fachwissen, bitte prüfen, bevor du es weitergibst).

Konzept

Schritt 1: LSM-Tree, nur anhängen und später aufräumen

Der LSM-Tree dreht den Spieß um. Er ändert nie eine Seite an ihrem Platz:

  1. Ein Schreibzugriff geht (nach dem WAL) in die Memtable: eine sortierte Struktur im RAM, hier ein dict.
  2. Ist die Memtable voll, wird sie als Run auf die Platte geschrieben (Flush): eine sortierte, unveränderliche Liste (bei echten Systemen SSTable genannt). Ein Run wird nie wieder geändert, nur am Stück geschrieben (sequenziell, schnell).
  3. Lesen sucht erst in der Memtable, dann in den Runs von neu nach alt. Der erste Treffer gewinnt, weil er der neueste Stand ist.
  4. Löschen schreibt einen Tombstone (tombstone, Grabstein): einen Marker “gelöscht”. Der Marker liegt im neuesten Run und verdeckt ältere Werte. Wichtig: Trifft das Lesen einen Tombstone, heißt das “nicht vorhanden”, und die Suche in älteren Runs hört auf.
  5. Mit der Zeit gibt es viele Runs, und das Lesen muss alle prüfen. Die Compaction führt Runs zusammen: Pro Schlüssel bleibt nur der neueste Eintrag, und Tombstones fallen weg, wenn alle älteren Runs im Merge enthalten sind (sonst würden verdeckte alte Werte wieder auftauchen).

Wir bauen das nach und zählen: lesezugriffe ist die Zahl der geprüften Runs, geschrieben die Zahl der Einträge, die in Runs geschrieben wurden.

Ausgabe:

[[('a', 2), ('c', 3), ('d', 1)]] {}
[[('a', 20), ('c', 'X'), ('e', 5)], [('a', 2), ('c', 3), ('d', 1)]] {}
[[('a', 20), ('c', 'X'), ('e', 5)], [('a', 2), ('c', 3), ('d', 1)]] {'f': 6}
get f -> 6 | geprüfte Runs: 0
get a -> 20 | geprüfte Runs: 1
get c -> None | geprüfte Runs: 1
get z -> None | geprüfte Runs: 2
[[('a', 20), ('d', 1), ('e', 5)]] geschrieben: 9
get f -> 6 | geprüfte Runs: 0
get a -> 20 | geprüfte Runs: 1
get c -> None | geprüfte Runs: 1
get z -> None | geprüfte Runs: 1

Gehe es durch. Die ersten drei Schreibzugriffe füllen die Memtable, der dritte löst den Flush aus: ein Run mit a, c, d (sortiert). Dann kommen a = 20, ein Tombstone für c (X) und e = 5: Der zweite Flush legt einen neueren Run davor. Beachte: Der alte Run wurde nicht angefasst, a = 2 steht dort noch, wird aber vom neuen a = 20 verdeckt. f = 6 liegt noch in der Memtable.

Lesezugriffe: f kostet 0 Runs (Memtable). a findet sich im neuesten Run (1). c trifft im neuesten Run den Tombstone und hört auf: None, ohne den alten Wert 3 zu sehen. z gibt es nirgends, also werden alle 2 Runs geprüft: Ein Schlüssel, der nicht existiert, ist der teuerste Lesezugriff. Hier hilft ein Bloom Filter pro Run (Lektion 20 Teil 2): Er sagt “sicher nicht in diesem Run” und spart den Zugriff.

Die Compaction führt beide Runs zu einem zusammen, a = 20 überschreibt a = 2, der Tombstone und der alte Wert von c verschwinden. Das Ergebnis hat 3 Einträge (geschrieben steigt von 6 auf 9), und z kostet nur noch 1 Run. Compaction schreibt Daten neu, nur um später schneller zu lesen. Genau dort entsteht die Write Amplification.

Bereichsabfragen gehen auch: Die Runs sind sortiert, aber die Treffer liegen in jedem Run verstreut. Eine Bereichsabfrage muss darum alle Runs lesen und das Ergebnis zusammenführen (Übung 1).

Schritt 2: Write Amplification, Read Amplification und die Compaction-Strategien

Write Amplification (WA, Schreibverstärkung) ist das Verhältnis von tatsächlich auf die Platte geschriebenen Daten zu den Daten, die die Anwendung geschrieben hat. WA 10 heißt: Für jedes Byte, das du speicherst, schreibt die Platte 10 Byte. Das kostet Durchsatz und bei SSDs Lebensdauer. Read Amplification ist die Zahl der Stellen, die ein Lesezugriff prüfen muss. Beide gibt es im B-Baum und im LSM-Tree, aber an anderen Stellen:

  • B-Baum: Ändert eine Zeile 100 Byte, schreibt die Engine die ganze Seite (hier 8192 Byte), dazu den WAL-Eintrag. Das ist grob ein Faktor von 8192 / 100, in Python 81.92. Lesen ist billig (wenige Ebenen, Teil 1, Schritt 1).
  • LSM-Tree: Schreiben ist billig (RAM, dann ein sequenzieller Flush). Dafür schreibt die Compaction jeden Eintrag mehrfach neu. Lesen ist teurer (mehrere Runs, Schritt 1).

Wie oft ein Eintrag umgeschrieben wird, hängt von der Compaction-Strategie ab. Zwei Grundformen, hier in einem einfachen Modell (Einheit: ein Flush schreibt 1 Einheit, T ist das Größenverhältnis der Level):

  • Tiered (size-tiered): Sammelt T gleich große Runs auf einem Level und führt sie zu einem Run des nächsten Levels zusammen. Jeder Eintrag wird auf jedem Level einmal neu geschrieben. Wenig Schreibarbeit, aber auf jedem Level liegen bis zu T - 1 Runs, das Lesen prüft mehr.
  • Leveled: Hält pro Level einen Run. Jeder neue Run wird in den Run von Level 1 gemischt, und läuft Level i über (mehr als T hoch i Einheiten), geht er in Level i + 1 über. Das Lesen prüft höchstens einen Run pro Level, aber Einträge werden pro Level mehrfach umgeschrieben.

Tiered per Hand für 64 Flushes bei T = 4: Die Einträge durchlaufen vier Schritte (Flush, Level 0 nach 1, 1 nach 2, 2 nach 3), und jeder Schritt schreibt insgesamt alle 64 Einheiten: 64 + 64 + 64 + 64 = 256, also WA 4. Leveled als Code (Tiered schreibst du in Übung 2):

Ausgabe:

16 Flushes: geschrieben 77 | WA 4.81
64 Flushes: geschrieben 404 | WA 6.31
256 Flushes: geschrieben 1997 | WA 7.8

Bei 64 Flushes schreibt Leveled 404 Einheiten (WA 6.31), Tiered 256 (WA 4.0). Der Abstand wächst mit den Daten: Bei 256 Flushes sind es 7.8 gegen 5.0 (bei Tiered ist die Write Amplification etwa 1 plus die Zahl der Level, die Zahlen rechnest du in Übung 2 selbst nach). Dafür liegen bei Tiered kurz vor einem Merge bis zu T - 1 = 3 Runs pro Level herum (bei 63 Flushes sind es 3 + 3 + 3 = 9 Runs), bei Leveled höchstens ein Run pro Level. Das ist der Trade-off: Tiered schreibt weniger und liest mehr, Leveled schreibt mehr und liest weniger. Dazu kommt die Space Amplification (Platzverstärkung): Solange Runs nicht zusammengeführt sind, liegen alte Versionen und Tombstones noch auf der Platte. Echte Leveled-Systeme sind feiner als dieses Modell (sie mischen pro Compaction nur einen Teil eines Levels, die Faustregel “etwa T Umschreibungen pro Level” gilt es zu prüfen, bitte prüfen), die Richtung stimmt aber.

Schritt 3: Wann welche Engine

Randbedingung B-Baum (B+-Baum) LSM-Tree
Schreiblast sehr hoch, sequenziell anhängen zufällige Seitenschreibzugriffe, ganze Seite pro Änderung stark: RAM plus sequenzieller Flush
Punktabfragen mit festem Latenzziel stark: wenige Seitenzugriffe, kein Hintergrund-Umschreiben mehrere Runs, Compaction erzeugt Lastspitzen (Bloom Filter helfen)
Bereichsabfragen stark: Blätter verkettet und sortiert Treffer in jedem Run, Zusammenführen nötig
Schreibvolumen auf SSD klein halten hohe WA durch ganze Seiten Tiered: niedrige WA, Leveled: mittlere
Änderungen am Ort, Updates natürlich (in place) neue Version anhängen, alte bleibt bis zur Compaction

Das ist die zweite Hälfte des Prüfsteins: Ein LSM-Tree ist die bessere Wahl bei schreiblastigen Workloads, bei denen Lesen seltener oder tolerant ist. Für lesedominierte Last mit Bereichsabfragen und gleichmäßiger Latenz ist der B-Baum die bessere Wahl (allgemeines Fachwissen, Verallgemeinerung).

Falle

  1. Tombstone überspringen. Wer beim Lesen einen Tombstone ignoriert und weitersucht, holt den gelöschten Wert aus einem älteren Run zurück (Übung 1).
  2. Compaction als kostenlos betrachten. Sie schreibt Daten neu und ist der Grund für die Write Amplification des LSM-Trees (Übung 2).
  3. “LSM ist schneller” ohne Randbedingung. Schneller beim Schreiben, nicht automatisch beim Lesen oder bei Bereichsabfragen (Übung 3).
  4. Space Amplification vergessen. Solange Runs nicht zusammengeführt sind, liegen alte Versionen und Tombstones auf der Platte. Plane Platz für die Compaction ein.

Übungen

Übung 1: Bereichsabfrage im LSM-Tree (ca. 10 Min.)

Ein Sensor-Speicher ist eine MiniLSM aus Schritt 1 (Klasse MiniLSM und TOMBSTONE stehen bereit, Schlüssel sind Messzeiten als Text). Schreibe bereich(lsm, von, bis): Sie liefert alle lebenden Einträge mit von <= key < bis als nach Schlüssel sortierte Liste von Tupeln (key, wert).

  • Der neueste Stand jedes Schlüssels gilt (Memtable vor allen Runs, neuere Runs vor älteren). Ein Tombstone als neuester Stand heißt: Der Schlüssel zählt nicht.
  • Jeder Run muss durchsucht werden (die Treffer liegen verstreut). Erhöhe lsm.lesezugriffe um 1 pro Run, den du durchsuchst. Die Memtable kostet nichts.
  • Die Funktion verändert lsm nicht, außer dem Zähler.

Die letzte Zeile gibt die Funktion zurück.

Wie baust du pro Schlüssel den neuesten Stand auf, wenn du die Runs der Reihe nach durchgehst (in welcher Richtung, und wer darf wen überschreiben)? Wann darfst du Tombstones aussortieren: schon beim Einsammeln oder erst am Ende? Was steckt außer den Runs noch im Speicher?

lsm = MiniLSM(memtable_max=3)
for zeit, wert in [("08:00", 11), ("08:05", 12), ("08:10", 13), ("08:05", 14), ("08:15", 15), ("08:20", 16)]:
    lsm.put(zeit, wert)
lsm.delete("08:10")
lsm.put("08:25", 17)

def bereich(lsm, von, bis):
    stand = {}
    for run in reversed(lsm.runs):          # alt zuerst, neuere überschreiben
        lsm.lesezugriffe += 1
        for k, w in run:
            if von <= k < bis:
                stand[k] = w
    for k, w in lsm.memtable.items():       # die Memtable ist am neuesten
        if von <= k < bis:
            stand[k] = w
    return sorted((k, w) for k, w in stand.items() if w is not TOMBSTONE)

print(bereich(lsm, "08:05", "08:20"), lsm.lesezugriffe)
bereich

Von alt nach neu einsammeln, damit neuere Stände überschreiben, danach die Memtable. Tombstones werden erst am Ende entfernt, sonst würde ein gelöschter Wert aus einem älteren Run wieder auftauchen. Die obere Grenze bis ist ausgeschlossen. Der Zähler steigt um die Zahl der Runs.

Übung 2: Write Amplification von Tiered Compaction (ca. 10 Min.)

Setze das Tiered-Modell aus Schritt 2 um. Schreibe tiered(n_flushes, T): Sie simuliert n_flushes Flushes zu je 1 Einheit und liefert die Gesamtzahl der geschriebenen Einheiten als int (Flushes plus Compactions).

  • Jeder Flush schreibt 1 Einheit und legt einen neuen Run der Größe 1 auf Level 0.
  • Sobald ein Level T Runs hat, werden diese T Runs zu einem Run auf dem nächsten Level zusammengeführt. Der neue Run hat T mal die Größe der alten Runs und kostet entsprechend viele geschriebene Einheiten. Danach ist das Level leer. Der neue Run kann das nächste Level füllen und eine weitere Zusammenführung auslösen (Kaskade).

Handrechnung: Bei T = 4 und 16 Flushes sind das 16 Einheiten Flush, dazu 4 Merges zu je 4 Einheiten und 1 Merge zu 16 Einheiten, zusammen 48. Der Check testet andere Werte, auch solche, bei denen am Ende noch Runs unvollständig auf Levels liegen.

Die letzte Zeile gibt die Funktion zurück.

Es reicht, pro Level die Anzahl der Runs zu kennen, denn auf Level i hat jeder Run dieselbe Größe. Wann prüfst du auf “Level voll”, und was passiert mit dem Zähler des nächsten Levels, wenn du dort einen Run ablegst? Das kann sich mehrfach hintereinander wiederholen.

def tiered(n_flushes, T):
    anzahl = [0]                    # anzahl[i] = Zahl der Runs auf Level i, jeder Run hat Größe T**i
    geschrieben = 0
    for _ in range(n_flushes):
        geschrieben += 1            # der Flush schreibt 1 Einheit
        anzahl[0] += 1
        i = 0
        while anzahl[i] == T:       # Level voll: zusammenführen, eventuell mehrfach nacheinander
            anzahl[i] = 0
            geschrieben += T * T ** i
            if i + 1 == len(anzahl):
                anzahl.append(0)
            anzahl[i + 1] += 1
            i += 1
    return geschrieben

print(tiered(16, 4), tiered(9, 3))
tiered

Die Schleife while anzahl[i] == T setzt die Kaskade um: Ein Merge füllt eventuell das nächste Level. Jeder Merge schreibt T mal die Größe der alten Runs. Für 64 Flushes bei T = 4 ergibt das 256, also WA 4.

Übung 3: B-Baum oder LSM-Tree, drei Fälle (ca. 8 Min.)

Wähle in jedem Fall die Lösung, die zu allen genannten Randbedingungen passt. Gib ein Tupel mit drei Buchstaben zurück, z. B. ("A", "B", "C").

Fall 1: Ein Telemetrie-Dienst nimmt dauerhaft 150000 Messwerte pro Sekunde auf, Schlüssel ist (Gerät, Zeit). Gelesen wird nur selten (ein Dashboard pro Minute), ein Lesezugriff darf mehrere Runs prüfen. Die Daten liegen auf SSDs mit begrenzter Schreiblebensdauer, darum soll das geschriebene Datenvolumen möglichst klein sein. Nach einem Absturz dürfen bestätigte Messwerte nicht fehlen.

  • A: B-Baum, jeder Messwert ändert eine Seite an ihrem Platz, dazu ein WAL
  • B: LSM-Tree mit Tiered Compaction, dazu ein WAL für die Memtable
  • C: LSM-Tree mit Leveled Compaction, dazu ein WAL für die Memtable
  • D: Hashmap im RAM, die regelmäßig als Ganzes in eine Datei kopiert wird

Fall 2: Eine Bestellverwaltung hält 200 GB. 90 Prozent der Zugriffe sind Punktabfragen nach der Bestellnummer, 10 Prozent ändern eine bestehende Bestellung. Das Latenzziel (p99) soll gleichmäßig eingehalten werden: Es darf kein Hintergrundprozess laufen, der Einträge umschreibt, und jeder Lookup soll mit einer kleinen, festen Zahl von Seitenzugriffen auskommen.

  • A: B+-Baum, Lookup über wenige Ebenen, Änderungen am Ort
  • B: LSM-Tree mit Tiered Compaction, mehrere Runs pro Level
  • C: LSM-Tree mit Leveled Compaction, laufend zusammengeführt
  • D: Nur anhängen ohne Index, beim Lesen rückwärts vom Ende suchen

Fall 3: Ein Preisverzeichnis hat 50 Millionen Einträge, sortiert nach Artikelnummer. Die Hauptabfrage lautet “alle Artikel von Nummer 400000 bis 410000” (Bereichsabfrage). Preise ändern sich selten (wenige hundert pro Stunde), schnelles Lesen ist wichtiger als Schreibdurchsatz.

  • A: Hash-Index auf der Artikelnummer, Lookup in einem Schritt
  • B: LSM-Tree mit Tiered Compaction, viele Runs pro Level
  • C: Ungeordnete Datei mit einem Bloom Filter pro Seite
  • D: B+-Baum, Blätter verkettet, Anfang suchen und weiterlesen

Wo entsteht jeweils die Arbeit: beim Schreiben (ganze Seite oder Compaction), beim Lesen (Zahl der Runs) oder im Hintergrund? Streiche zuerst alles, was eine genannte Randbedingung verletzt, auch Optionen, die nur wie ein Index aussehen.

antwort = ("B", "A", "D")
antwort

Fall 1: schreibintensiv, wenig Lesen, kleines Schreibvolumen: LSM mit Tiered Compaction (niedrigere Write Amplification als Leveled, die Read Amplification ist hier erlaubt). Fall 2: feste Seitenzugriffe und kein Hintergrund-Umschreiben: B+-Baum. Fall 3: Bereichsabfrage auf sortierten Daten mit wenigen Änderungen: B+-Baum mit verketteten Blättern.

Merksatz und Prüfstein

Merksatz: Ein LSM-Tree schreibt nur anhängend und räumt per Compaction später auf: gut für Schreiblast, bezahlt mit Write und Read Amplification, und für lesedominierte Last mit Bereichsabfragen und gleichmäßiger Latenz ist der B-Baum die bessere Wahl.

Prüfstein: Wann ist ein LSM-Tree die bessere Wahl, und was bezahlst du dafür (Write und Read Amplification, Compaction)?

Quelle: quellen/konzeptuebersicht-software-fortgeschritten.docx, Schicht 5 (Stichpunkt “Storage Engines: Write-Ahead Log, Buffer Pool, B-Tree vs. LSM, Compaction, Write Amplification”) und Schicht 2 (Stichpunkt “Indexstrukturen: B-/B+-Bäume, LSM-Trees, Skip Lists, Tries, invertierter Index”, Prüfstein “Warum nutzen Datenbanken B-Bäume statt Binärbäume, und wann ist ein LSM-Tree die bessere Wahl?”). Skip Lists, Tries und der invertierte Index sind hier nicht behandelt.

Über die Quelle hinaus (allgemeines Fachwissen): die Beschreibung von Memtable, Runs, Tombstones und Compaction, die Definition von Write, Read und Space Amplification, die beiden Compaction-Strategien in ihrem vereinfachten Modell (echte Systeme arbeiten feiner), die Nutzungsaussage zu LevelDB (bitte prüfen), die Tabelle zur Engine-Wahl als Verallgemeinerung. Alle Zahlen und Ausgaben in dieser Lektion stammen aus ausgeführtem Code.