Storage Engines: B-Baum, Buffer Pool und Write-Ahead Log

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

Worum es geht

Du schreibst eine Zeile in die Datenbank, der Strom fällt aus, der Server startet neu. Die Zeile ist da, wenn dein COMMIT durchging, und sie ist nicht halb da. Das leistet die Storage Engine (storage engine): der Teil der Datenbank, der Daten auf Platte ablegt, wiederfindet und gegen Abstürze schützt. Zwei Bauarten teilen sich den Markt: der B-Baum (B-tree), der Daten an ihrem Platz ändert, und der LSM-Tree (log-structured merge tree), der nur hinten anhängt und später aufräumt. In diesem Teil geht es um den B-Baum und um das, was beide Bauarten absturzsicher macht: das Write-Ahead Log.

Am Ende dieses Teils kannst du:

  • mit Zahlen erklären, warum Datenbanken B-Bäume statt Binärbäume nutzen (Übung 1),
  • vorhersagen, wie ein Buffer Pool mit LRU-Verdrängung Seiten behält und verdrängt (Übung 2),
  • ein Write-Ahead Log (WAL) lesen und eine Crash-Recovery schreiben, die nur committete Transaktionen anwendet und idempotent ist (Übung 3).

Der LSM-Tree, Write Amplification und die Wahl der Engine folgen in Teil 2. Nicht Thema: Index-Strukturen aus Sicht der SQL-Abfrage und die B-Baum-Analogie (Lektion 2), Isolation und MVCC (Lektion 3), Hashmap (Lektion 20 Teil 1). Wir bauen darauf auf.

Plane ehrlich 45 Minuten ein: etwa 17 Minuten Lesen, 28 Minuten Übungen (drei Stück). Eine gute Pause ist nach Übung 2.

Von JS/TS her gedacht

Das Prinzip “erst ins Log, dann in den Zustand” kennst du aus Redux und aus Event Sourcing (Lektion 5): Der Zustand ist abgeleitet, das Log ist die Wahrheit. Wer das Log von vorn abspielt, bekommt den Zustand zurück, und wer es an einer beliebigen Stelle abschneidet (Absturz), bekommt den Zustand zu diesem Zeitpunkt. In TypeScript (mit Node ausgeführt):

const log = [
  { type: "add", id: 1 }, { type: "add", id: 2 },
  { type: "remove", id: 1 }, { type: "add", id: 3 },
];
const replay = (entries) => entries.reduce(
  (s, e) => e.type === "add" ? new Set(s).add(e.id) : new Set([...s].filter(x => x !== e.id)),
  new Set());
console.log([...replay(log)], [...replay(log.slice(0, 3))]);

Ausgabe:

[ 2, 3 ] [ 2 ]

Der ganze Log ergibt {2, 3}, das nach drei Einträgen abgeschnittene Log {2}. Die Datenbank macht dasselbe, nur mit einer Regel obendrauf: Was nicht committet ist, wird beim Abspielen übersprungen.

Du kennst In der Storage Engine
Redux-Action-Log, Event Store Write-Ahead Log (WAL)
Objekt im Speicher ändern Seite im B-Baum an ihrem Platz ändern (in-place update)
LRU-Cache im Frontend Buffer Pool (Seiten-Cache im RAM)

Konzept

Schritt 1: Warum B-Baum statt Binärbaum

Eine Platte (und auch eine SSD) liest nicht ein Byte, sondern eine Seite (page, block), typisch einige KB. Ob du 8 Byte oder die ganze Seite brauchst, kostet dasselbe. Darum zählt man in einer Storage Engine nicht Vergleiche, sondern Seitenzugriffe, und die will man minimieren.

Ein Binärbaum (binary tree) hat pro Knoten einen Schlüssel und zwei Kinder. Liegt jeder Knoten auf einer eigenen Seite, kostet jede Ebene einen Seitenzugriff, und bei einer Million Einträge sind es rund 20 Ebenen. Ein B-Baum packt in eine Seite viele Schlüssel und Zeiger: den Fanout (fanout, Verzweigungsgrad), also die Zahl der Kinder pro Knoten. Je größer der Fanout, desto flacher der Baum. Wir rechnen mit einem vereinfachten Modell: Jede Seite ist voll, und h Ebenen fassen f hoch h Einträge.

Ausgabe:

Fanout: 341
1000 Einträge: Binärbaum 10 Ebenen, B-Baum 2 Ebenen
1000000 Einträge: Binärbaum 20 Ebenen, B-Baum 3 Ebenen
1000000000 Einträge: Binärbaum 30 Ebenen, B-Baum 4 Ebenen

Lies es so: Eine Million Einträge brauchen im Binärbaum 20 Seitenzugriffe, im B-Baum mit Fanout 341 nur 3. Selbst eine Milliarde Einträge kosten nur 4. Das ist die Antwort auf die erste Hälfte des Prüfsteins: Wenige, breite Knoten passen zur Seitengröße der Platte, und der Baum bleibt flach. Die Zahlen 8 KB, 16 und 8 Byte sind Beispielwerte (bitte prüfen, die Werte hängen vom System ab). Echte Seiten sind nie ganz voll, die echte Höhe ist also etwas größer.

Noch zwei Eigenschaften, ohne Code:

  • Seite voll heißt teilen. Passt ein neuer Schlüssel nicht mehr in eine Seite, wird sie in zwei Seiten geteilt (split), der mittlere Schlüssel wandert in die Elternseite. Wächst die Wurzel über, entsteht eine neue Wurzel. So bleibt der Baum immer balanciert (alle Blätter gleich tief), und der Baum wächst nur an der Wurzel.
  • B+-Baum (B+ tree): Die Nutzdaten stehen nur in den Blättern, und die Blätter sind miteinander verkettet. Eine Bereichsabfrage (range query) findet den Anfang in 3 Seitenzugriffen und liest dann die Blätter der Reihe nach. Die meisten relationalen Datenbanken nutzen diese Form für ihre Indizes (allgemeines Fachwissen).

Der Preis des B-Baums: Eine Änderung ersetzt eine Seite an ihrem Platz. Das sind zufällige Schreibzugriffe (random writes), und für eine Änderung von 100 Byte wird die ganze Seite geschrieben (Teil 2, Schritt 2 rechnet das aus).

Schritt 2: Buffer Pool, der Seiten-Cache

Die Platte ist langsam, der Hauptspeicher schnell. Der Buffer Pool (buffer pool, buffer cache) hält die zuletzt benutzten Seiten im RAM. Ist eine Seite im Pool (Treffer, hit), kostet sie keinen Plattenzugriff. Ist der Pool voll, fliegt die Seite raus, die am längsten nicht benutzt wurde: LRU (least recently used). Das ist derselbe Gedanke wie ein LRU-Cache im Frontend. Mit OrderedDict in wenigen Zeilen, bei einem Pool für 3 Seiten:

Ausgabe: 5 5 ['a', 'x', 'wurzel']. Von zehn Zugriffen gingen fünf direkt aus dem RAM. wurzel und a werden ständig gebraucht und bleiben drin, x und y verdrängen sich gegenseitig. Genau so verhält sich ein B-Baum: Die Wurzel und die oberen Ebenen werden bei jedem Lookup gebraucht und liegen praktisch immer im Pool. Bei Fanout 100 und drei Ebenen sind das 1 + 100 = 101 Seiten (Rechnung: 1 + f). Der Lookup kostet dann real oft einen Plattenzugriff statt drei.

Schritt 3: Write-Ahead Log (WAL)

Eine Überweisung ändert zwei Seiten: Konto A minus 30, Konto B plus 30. Stürzt der Server zwischen den beiden Schreibzugriffen ab, sind 30 Euro verschwunden. Seiten kann man nicht atomar zusammen schreiben. Das Mittel ist das Write-Ahead Log (write-ahead log, WAL), auf Deutsch “Vorab-Protokoll”:

  1. Jede Änderung wird zuerst ins Log geschrieben. Das Log wird nur hinten angehängt (append-only, sequenziell, schnell) und auf die Platte erzwungen (fsync).
  2. Erst danach ändert die Engine die Seiten, und das darf auch später passieren.
  3. Der Commit ist ein Eintrag commit im Log. Erst wenn der auf der Platte steht, antwortet die Datenbank “fertig”.

Das Log enthält pro Transaktion begin, mehrere write mit neuem Wert und am Ende commit. Hier ein Log mit drei Transaktionen (Kontostände in Euro). Eine Hilfsfunktion findet die committeten Transaktionen. Dann simulieren wir den Absturz, indem wir das Log abschneiden:

Ausgabe: {1, 2} {1} {1}. Der volle Log hat zwei Commits (Transaktionen 1 und 2). Transaktion 3 hat Änderungen, aber kein commit: Sie war beim Absturz unterwegs. Schneidest du nach Eintrag 7 ab (mitten in Transaktion 2), bleibt nur Transaktion 1 committet. Beim Neustart gilt deshalb:

  • Committet (Eintrag commit ist im Log): Die Änderungen müssen da sein. Die Recovery wiederholt sie (redo), falls die Seiten sie noch nicht haben.
  • Nicht committet: Die Änderungen dürfen nicht sichtbar werden. Die Recovery ignoriert sie. Damit gilt Atomicity (alles oder nichts) und Durability (committet heißt dauerhaft) aus Lektion 1.

Eine Eigenschaft ist entscheidend: Idempotenz (idempotence, mehrfaches Anwenden wirkt wie einmaliges). Die Recovery kann selbst abstürzen und läuft dann nochmal über dasselbe Log. Darum enthält ein write den neuen Wert (anna = 40), nicht die Änderung (“minus 30”). Ein “minus 30” ein zweites Mal angewendet wäre falsch, ein “setze auf 40” nicht.

Zwei Ergänzungen, über die Quelle hinaus (allgemeines Fachwissen): Ein Checkpoint vermerkt, dass alle Änderungen bis zu einer Stelle schon in den Seiten stehen. Das Log davor wird nicht mehr gebraucht, und die Recovery beginnt am Checkpoint. Echte Engines (Stichwort ARIES) machen zusätzlich ein Undo für Änderungen unfertiger Transaktionen, die schon in den Seiten stehen. Unsere Übung vereinfacht das: Sie baut den Zustand aus dem Checkpoint-Stand (Snapshot) und dem Log neu auf.

Falle

  1. Mit float rechnen. Die Baumhöhe als ceil(math.log(n, f)) sieht richtig aus und liefert bei exakten Potenzen falsche Werte, weil math.log(125, 5) den Wert 3.0000000000000004 ergibt. Mit ganzen Zahlen schleifen (Übung 1).
  2. Seitenzugriffe zählen, als gäbe es keinen Buffer Pool. Die oberen Ebenen des Baums liegen praktisch immer im RAM. Ein Lookup kostet real oft einen Plattenzugriff statt drei (Übung 2).
  3. Recovery wendet alles aus dem Log an. Ein write im Log heißt nicht, dass die Transaktion committet ist (Übung 3).
  4. Inkrement statt Neuwert im Log. “Plus 30” ist beim zweiten Abspielen falsch, “setze auf 40” nicht.

Übungen

Übung 1: B-Baum-Höhe aus dem Fanout (ca. 8 Min.)

Ein Index liegt auf Seiten von seitengroesse Byte, jeder Eintrag (Schlüssel plus Zeiger) braucht eintragsgroesse Byte. Schreibe lesezugriffe(n, seitengroesse, eintragsgroesse): die Zahl der Seitenzugriffe für einen Lookup in einem vollen Baum mit n Schlüsseln, wie im Modell aus Schritt 1 (Fanout = ganzzahlige Division, mindestens eine Seite, ohne Buffer Pool). Das Ergebnis ist eine ganze Zahl (int). Der Check prüft auch exakte Potenzen und den Fall “eine Potenz plus 1”.

Die letzte Zeile gibt die Funktion zurück.

Wie viele Einträge fassen h Ebenen bei Fanout f? Zähle Ebenen hoch, bis die Kapazität reicht. Und bei Potenzen wie 125 = 5 hoch 3: Verlässt du dich auf math.log, passiert bei Gleitkommazahlen etwas Überraschendes.

def lesezugriffe(n, seitengroesse, eintragsgroesse):
    fanout = seitengroesse // eintragsgroesse
    ebenen, kapazitaet = 1, fanout
    while kapazitaet < n:
        kapazitaet *= fanout
        ebenen += 1
    return ebenen

print(lesezugriffe(1_000_000, 4096, 16), lesezugriffe(2**20, 16, 8))
lesezugriffe

Die Schleife zählt Ebenen, bis fanout ** ebenen mindestens n Einträge fasst, nur mit ganzen Zahlen. Bei n = 125 und Fanout 5 sind es genau 3 Ebenen, math.log würde wegen 3.0000000000000004 auf 4 aufrunden.

Übung 2: Buffer Pool vorhersagen (ca. 7 Min.)

Ein Buffer Pool für 3 Seiten mit LRU-Verdrängung arbeitet wie der Pool aus Schritt 2: Eine benutzte Seite rückt ans neue Ende, ist der Pool voll, fliegt die am längsten unbenutzte Seite raus. Er ist am Anfang leer, und es werden diese Seiten gelesen:

p1, p2, p1, p3, p4, p1, p2, p3, p1

Trage ein Tupel (treffer, platte, inhalt) ein: wie viele Lesezugriffe aus dem RAM kamen (treffer), wie viele zur Platte gingen (platte), und welche Seiten am Ende im Pool liegen, von der am längsten unbenutzten bis zur zuletzt benutzten, als Tupel von Namen. Die Klasse Pool aus dem Text gibt es hier nicht, rechne von Hand oder baue sie dir selbst in die Zelle.

Führe den Pool Zugriff für Zugriff nach und notiere die Reihenfolge nach jedem Schritt. Was passiert bei einem Treffer mit der Reihenfolge, und wer fliegt raus, wenn eine vierte Seite kommt?

antwort = (3, 6, ("p2", "p3", "p1"))
antwort

Die Reihenfolge nach jedem Zugriff (alt nach neu): p1 (Platte), p1 p2 (Platte), p2 p1 (Treffer), p2 p1 p3 (Platte), p1 p3 p4 (Platte, p2 fliegt raus), p3 p4 p1 (Treffer), p4 p1 p2 (Platte, p3 fliegt raus), p1 p2 p3 (Platte, p4 fliegt raus), p2 p3 p1 (Treffer). Das sind 3 Treffer und 6 Plattenzugriffe. Entscheidend ist, dass ein Treffer die Seite ans neue Ende schiebt: So überlebt p1, die am häufigsten benutzte Seite.

Übung 3: Crash-Recovery aus dem WAL (ca. 12 Min.)

Ein Lager speichert Bestände ({"schrauben": 100, ...}). Beim letzten Checkpoint war der Stand snapshot. Danach schrieb die Engine ein WAL, dann stürzte der Server ab. Schreibe recover(snapshot, log): Sie liefert den Zustand, den die Datenbank nach dem Neustart haben muss. Das Log besteht aus Tupeln:

  • ("begin", tx), ("write", tx, key, wert) (setzt key auf den neuen Wert), ("delete", tx, key), ("commit", tx), ("abort", tx).

Regeln:

  • Angewendet werden nur Änderungen von Transaktionen, die ein commit im Log haben. Transaktionen mit abort oder ohne Ende (Absturz) bleiben ohne Wirkung.
  • Die Änderungen werden in Log-Reihenfolge angewendet (spätere Einträge überschreiben frühere). Transaktionen dürfen im Log verschränkt sein.
  • snapshot wird nicht verändert, die Funktion gibt ein neues dict zurück.
  • Die Recovery ist idempotent: recover(recover(snapshot, log), log) ist dasselbe wie recover(snapshot, log). (Das erfüllt sich von selbst, wenn du nur Neuwerte setzt und löschst.)

Die letzte Zeile gibt die Funktion zurück.

Zwei Durchläufe über das Log: Im ersten sammelst du, welche Transaktionen ein commit haben. Im zweiten wendest du nur deren Einträge auf eine Kopie des Snapshots an. Was passiert mit einem delete?

snapshot = {"schrauben": 100, "muttern": 50}
log = [
    ("begin", 1), ("write", 1, "schrauben", 80), ("write", 1, "muttern", 70), ("commit", 1),
    ("begin", 2), ("write", 2, "schrauben", 10), ("delete", 2, "muttern"),
    ("begin", 3), ("write", 3, "winkel", 5), ("commit", 3),
]

def recover(snapshot, log):
    gesichert = {eintrag[1] for eintrag in log if eintrag[0] == "commit"}
    zustand = dict(snapshot)
    for eintrag in log:
        if eintrag[1] not in gesichert:
            continue
        if eintrag[0] == "write":
            zustand[eintrag[2]] = eintrag[3]
        elif eintrag[0] == "delete":
            zustand.pop(eintrag[2], None)
    return zustand

print(recover(snapshot, log))
recover

Erst werden die committeten Transaktionen gesammelt, dann ihre Einträge in Log-Reihenfolge auf eine Kopie des Snapshots angewendet. Unfertige und abgebrochene Transaktionen fallen heraus. Weil nur Neuwerte gesetzt und Schlüssel gelöscht werden, ändert ein zweiter Durchlauf nichts mehr (Idempotenz).

Merksatz und Prüfstein

Merksatz: Ein B-Baum hält die Zahl der Seitenzugriffe klein, weil breite Knoten den Baum flach machen, ein Buffer Pool hält die oft gebrauchten oberen Ebenen im RAM, und das Write-Ahead Log macht Änderungen absturzsicher, weil nach einem Absturz nur committete Einträge zählen.

Prüfstein:

  1. Warum nutzen Datenbanken B-Bäume statt Binärbäume? Nenne die Rechnung mit Fanout und Seitenzugriffen.
  2. Was macht eine Recovery mit einem Write-Ahead Log, und warum muss sie idempotent sein?

Weiter mit Teil 2: LSM-Tree, Compaction und die Wahl der Engine.

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 Erklärung von Seiten, Fanout, Split und B+-Baum, der Buffer Pool als LRU-Cache, der Ablauf von WAL, Commit, Redo, Checkpoint und ARIES, die Nutzungsaussage zu SQLite und PostgreSQL (bitte prüfen). Seitengröße 8 KB und Eintragsgrößen sind Beispielwerte (bitte prüfen). Alle Zahlen und Ausgaben in dieser Lektion stammen aus ausgeführtem Code.