Was ist ein LSM-Baum? Der Log-Structured Merge Tree erklärt

Was ist ein LSM-Baum?

Ein Log-Structured Merge Tree (LSM) ist eine Datenstruktur, die eingehende Schreibvorgänge im Arbeitsspeicher puffert und sie in sortierten, unveränderlichen Batches auf dem Datenträger zusammenführt. Sie verändert Daten niemals direkt an ihrem Speicherort. Stattdessen sammelt sie Änderungen und verschiebt die Organisation auf später. So tauscht sie einfache Lesevorgänge gegen höheren Schreibdurchsatz.

Der LSM-Baum wurde 1996 in einem Paper von Patrick O’Neil, Edward Cheng, Dieter Gawlick und Elizabeth O’Neil mit dem Titel The log-structured merge-tree (LSM-tree) formalisiert. Etwa ein Jahrzehnt lang blieb er eine relativ unbekannte akademische Struktur, bevor Google die Speicherschicht von Bigtable auf diesem Konzept aufbaute. Aus dem Design von Bigtable entstand LevelDB, aus LevelDB entstand RocksDB, und unter den meisten Systemen für hohe Ingest-Raten arbeitet heute eine Variante des LSM-Baums.  

Der Name suggeriert einen einzelnen Baum, was stark irreführend ist. 

Ein LSM-Baum lässt sich besser als Zusammenspiel von drei Komponenten verstehen:

• Eine Memtable: ein Puffer im Arbeitsspeicher für die neuesten Schreibvorgänge
• Ein Write-Ahead Log (WAL): eine ausschließlich erweiterte Datei auf dem Datenträger, die diese Schreibvorgänge dauerhaft speichert
• Eine wachsende Sammlung von Sorted-String-Table-Dateien (SSTs): unveränderliche, sortierte Dateien, die alle älteren Daten enthalten

Fast alle interessanten Eigenschaften eines LSM-Baums ergeben sich daraus, wie Daten zwischen diesen drei Komponenten verschoben werden. Jede dieser Bewegungen beginnt mit einem einzelnen, täuschend einfachen Funktionsaufruf, der üblicherweise als Put bezeichnet wird.

Was ist ein Put? 

Put ist ein praktischer Wrapper, der intern einen WriteBatch mit genau einem Datensatz erstellt und ihn an Write() übergibt, das die Änderungen verarbeitet. 

Der naheliegende Ausgangspunkt ist Put(key, value). Streng genommen kennt RocksDB eine solche Operation jedoch nicht. Jeder Schreibvorgang ist ein Batch, und ein einzelner Put ist lediglich ein Batch mit einem Element. Atomare Schreibvorgänge über mehrere Schlüssel gibt es in RocksDB ohne Zusatzaufwand, weil sie eine native Operation sind.

Ein WriteBatch ist eine kompakte Bytefolge mit einem festen Aufbau: ein 12 Byte großer Header mit einer 8 Byte großen Sequenznummer und einer 4 Byte großen Datensatzanzahl, gefolgt von den Datensätzen selbst. Jeder Datensatz besteht aus einem ein Byte großen Typ-Tag, einem Schlüssel mit vorangestellter Länge und bei Schreibvorgängen einem Wert mit vorangestellter Länge.

Die Aussage aus dem ersten Artikel dieser Reihe – Schlüssel und Werte sind beliebige Byte-Arrays – wird hier wörtlich wahr. Die Batch-Codierung weiß weder, was die Bytes bedeuten, noch interessiert sie sich dafür. Die einzige vorgegebene Struktur sind die vorangestellten Längen. 

Jeder Batch erhält einen monoton steigenden Zähler, die sogenannte Sequenznummer. Sie legt eine vollständige Reihenfolge für alle Schreibvorgänge fest, die die Datenbank jemals angenommen hat. Sequenznummern ermöglichen Snapshots, konsistente Lesevorgänge und die Wiederherstellung nach einem Absturz. Das WAL lässt sich wiedergeben, weil jeder darin enthaltene Datensatz seine Position in der Reihenfolge kennt.

Put, Delete, Merge

Wichtig ist: Ein Put ist kTypeValue, und ein Delete ist kTypeDeletion. Ein Delete entfernt also nichts. Stattdessen ist es ein Schreibvorgang – ein Tombstone –, der die Löschung vermerkt. Die tatsächliche Freigabe des Speicherplatzes erfolgt erst bei der Komprimierung.

Put und Delete verwenden dasselbe WriteBatch-Format wie kTypeMerge, das von der Operation Merge geschrieben wird. Merge existiert, weil Read-Modify-Write für einen schreiboptimierten Speicher Gift ist. Um einen Zähler mit Put zu erhöhen, muss der aktuelle Wert gelesen, um eins erhöht und das Ergebnis zurückgeschrieben werden. Eine einzige Zahl zu ändern erfordert somit zwei Durchläufe durch die Datenbank, wobei der Lesevorgang die vollständigen Kosten des Lesepfads verursacht. 

Merge überspringt den Lesevorgang vollständig. 

Stattdessen hängt es einen Operanden an – also eine Beschreibung der Änderung wie „eins addieren“ – und kehrt zurück. Beim Schreiben wird nichts berechnet. Die Datenbank fasst die Operanden später mithilfe eines von der Anwendung bereitgestellten Merge-Operators zu einem endgültigen Wert zusammen: entweder beim nächsten Lesen des Schlüssels oder wenn die Komprimierung auf die Kette trifft.

Deletes verschieben die Speicherfreigabe, während Merges die Berechnung verschieben. 

Der gesamte Charakter des LSM-Baums zeigt sich in diesen drei Typ-Tags: Jede Änderung, auch wenn sie logisch vom bestehenden Zustand abhängt, wird zu einem blinden Anhängen. In einem LSM-Baum wird alles angehängt. 

Der Schreibpfad eines LSM-Baums erklärt

LSM-Bäume lassen sich am besten verstehen, indem man einen einzelnen Put(key, value) vom Funktionsaufruf bis auf den Datenträger verfolgt.

Schritt eins: Das Write-Ahead Log

Der Schreibvorgang wird zuerst an das WAL angehängt. Dies geschieht, bevor die Memtable verändert wird. Diese Reihenfolge bildet die Dauerhaftigkeitsgarantie. Sobald das Anhängen an das WAL abgeschlossen ist, liegt der Schreibvorgang in einer Form auf dem Datenträger vor, die einen Absturz übersteht – auch wenn er noch nicht für das Lesen organisiert wurde.

Das Anhängen an ein Log ist die günstigste mögliche Datenträgeroperation. Genau darum geht es. Dauerhaftigkeit gibt es zum Preis sequenzieller Schreibvorgänge.

RocksDB fasst gleichzeitige Schreibvorgänge in Group Commits zusammen, um die Kosten weiter zu verteilen. Die Option sync steuert, ob der Anhang über den Page Cache des Betriebssystems in den dauerhaften Speicher geschrieben wird, bevor der Aufruf zurückkehrt.

Schritt zwei: Die Memtable

Nachdem die Dauerhaftigkeit sichergestellt ist, wird der Schreibvorgang in die Memtable eingefügt. Standardmäßig ist die Memtable von RocksDB eine Skiplist. RocksDB verwendet eine Skiplist, weil die Memtable gleichzeitige Schreibvorgänge aufnehmen und ihre Inhalte in sortierter Schlüsselreihenfolge zurückgeben muss – sowohl für Lesevorgänge als auch für den späteren Flush.

Eine Skiplist unterstützt lock-freie, gleichzeitige Einfügungen und hält dabei jederzeit alles sortiert. Als Datenstruktur entspricht sie dem sofortigen Ablegen eingehender Dokumente, statt sie auf einem Stapel zu sammeln.

Schritt drei: Die Memtable füllt sich

Die Memtable wächst, bis sie einen konfigurierten Schwellenwert erreicht, also write_buffer_size, der standardmäßig bei 64 MB liegt. Dann wird sie als unveränderlich markiert, durch eine neue leere Memtable ersetzt und eingehende Schreibvorgänge werden ohne Unterbrechung fortgesetzt. Die volle, eingefrorene Memtable wartet darauf, im Hintergrund geschrieben zu werden. 

Schreibvorgänge blockieren niemals wegen des Flushs selbst.

Schritt vier: Der Flush

Ein Hintergrund-Thread schreibt die unveränderliche Memtable als SST-Datei in Level 0 (L0) des Baums auf den Datenträger. Da die Skiplist bereits sortiert ist, besteht der Flush aus einem einzigen sequenziellen Durchlauf, der die Einträge der Reihe nach durchläuft und schreibt.

Die Aufgabe der Memtable ist erledigt, und die entsprechenden WAL-Einträge können schließlich verworfen werden. Die Daten liegen jetzt dauerhaft und lesbar auf dem Datenträger vor.

Was enthält eine SST-Datei?

In der SST-Datei verbringen die Daten den Rest ihres Lebens. Sie ist in drei Blöcke und einen Footer gegliedert:

• Datenblöcke: die sortierten Einträge selbst, jeweils einige Kilobyte groß und einzeln komprimiert
• Indexblöcke: Sie ordnen Schlüsselbereiche Block-Offsets zu, damit eine Suche direkt zum richtigen Block springen kann
• Ein optionaler Bloomfilter-Block: eine kompakte probabilistische Zusammenfassung, die ohne weitere Lesevorgänge sagen kann: „Dieser Schlüssel befindet sich definitiv nicht in dieser Datei“
• Ein Footer: Er gibt die Position aller oben genannten Elemente an

Jedes Element dieses Layouts soll dafür sorgen, dass spätere Lesevorgänge möglichst wenige Bytes berühren. Das gilt besonders für den Index und den Bloomfilter.

Schritt für Schritt durch den Schreibpfad

Alles oben Erklärte lässt sich direkt beobachten. Dieser Abschnitt verfolgt mit ldb und sst_dump, den mit RocksDB ausgelieferten Inspektionswerkzeugen, einen einzelnen Put durch eine Datenbank. Das Beispiel verwendet Rust und das rocksdb-Crate, aber jedes Binding funktioniert.

Voraussetzungen

Installiere die RocksDB-Kommandozeilenwerkzeuge und eine Rust-Toolchain, um die Schritte nachzuvollziehen. 

Unter macOS stellt brew install rocksdb sowohl ldb als auch sst_dump bereit. Unter Debian/Ubuntu heißt das Paket rocksdb-tools.

Erstelle anschließend ein neues Projekt:

$ cargo new lsm-trace
$ cd lsm-trace
$ cargo add rocksdb

Das rocksdb-Crate kompiliert die C++-Bibliothek von RocksDB beim ersten Build aus dem Quellcode. Rechne daher damit, dass der erste Aufruf von cargo run mehrere Minuten dauert.

Schritt eins: Schreiben und anhalten

Ersetze den Inhalt von src/main.rs durch den folgenden Code:

use rocksdb::{Options, DB};

fn main() {
    let mut opts = Options::default();
    opts.create_if_missing(true);
    let db = DB::open(&opts, "/tmp/lsm-trace").unwrap();

    db.put(b"slot:0001", b"hello").unwrap();
// Deliberately no flush. Let the process exit.
}

Führe ihn einmal mit cargo run aus und liste anschließend das erstellte Datenbankverzeichnis auf:

$ ls /tmp/lsm-trace
000004.log CURRENT IDENTITY LOCK LOG MANIFEST-000005 OPTIONS-000007

CURRENT und die Datei MANIFEST verwalten das Dateiinventar der Datenbank, während OPTIONS die Konfiguration speichert, mit der sie geöffnet wurde. LOG ohne Nummer ist ein menschenlesbares Textprotokoll für das Debugging. Verwechsle es nicht mit 000004.log, dem eigentlichen Write-Ahead Log.

Die genauen Dateinummern unterscheiden sich bei jedem Durchlauf, die Struktur bleibt jedoch gleich.

Beachte, dass sich keine einzige .sst-Datei im Verzeichnis befindet. Der Schreibvorgang ist dauerhaft gespeichert, da er das Beenden des Prozesses überstanden hat. Er existiert jedoch nur als WAL-Datensatz. Hier zeigt sich die Trennung zwischen Dauerhaftigkeit und Organisation.

Schritt zwei: Das WAL ausgeben

Richte ldb auf die .log-Datei im Verzeichnis:

$ ldb dump_wal --walfile=/tmp/lsm-trace/000004.log --header
Sequence,Count,ByteSize,Physical Offset,Key(s) 1,1,29,0,PUT(0) : 0x736C6F743A30303031

Wir haben einen Batch: Sequenznummer 1 mit einem Datensatz (29 Byte). Es handelt sich um einen PUT, dessen Schlüssel die Hexadezimalcodierung von slot:0001 ist. 

Die Größe entspricht der zuvor beschriebenen Codierung: ein 12 Byte großer Header plus ein 17 Byte großer Datensatz mit einem Typ-Tag, zwei vorangestellten Längen, einem 9 Byte großen Schlüssel und einem 5 Byte großen Wert.

Schritt drei: Flush ausführen und SST ausgeben

Lösche zuerst das Datenbankverzeichnis, also rm -rf /tmp/lsm-trace, damit dieser Durchlauf mit einem sauberen Zustand beginnt.

Füge nach dem Put eine Zeile zu main.rs hinzu:

db.put(b"slot:0001", b"hello").unwrap();
db.flush().unwrap();

Der Aufruf db.flush().unwrap(); erzwingt, dass die Memtable als SST-Datei geschrieben wird, statt darauf zu warten, dass sie sich füllt.

Führe die Datei erneut aus und liste anschließend das Verzeichnis auf. 

In der Ausgabe sehen wir jetzt eine neue .sst-Datei. Wir können sie mit beiden nützlichen Modi von sst_dump untersuchen. Ersetze dabei den Dateinamen durch den tatsächlichen Namen:

$ sst_dump --file=/tmp/lsm-trace/000010.sst --command=scan
'slot:0001' seq:1, type:1 => hello

Beachte, dass sst_dump vor der Scan-Ausgabe einige einleitende Zeilen zum Dateiformat ausgibt. Sie wurden hier und in den folgenden Ausgaben entfernt.

Das ist das Schlüssel-Wert-Paar an seinem neuen dauerhaften Speicherort. Seine Sequenznummer ist weiterhin enthalten. 

Mit dem folgenden Befehl können wir uns seine Eigenschaften ansehen:

$ sst_dump --file=/tmp/lsm-trace/000010.sst --show_properties

Die Eigenschaftenausgabe listet die zuvor im Artikel beschriebene Anatomie der SST auf: Anzahl und Größe der Datenblöcke, Größe des Indexblocks, Vorhandensein eines Filters, Kompressionsalgorithmus und Anzahl der Einträge. 

Obwohl wir nur einen einzigen Schlüssel haben, werden alle Strukturelemente aufgeführt – mit einer aufschlussreichen Ausnahme. Die Größe des Filterblocks beträgt null und die Filterrichtlinie ist N/A, weil Bloomfilter in RocksDB explizit aktiviert werden müssen. Sie werden über filter_policy konfiguriert und sind in den Standardoptionen nicht gesetzt. 

Der nächste Artikel dieser Reihe erklärt, warum sie in Produktionsumgebungen fast immer aktiviert werden. 

Schritt vier: Erneut öffnen und das Log prüfen

Kommentiere die Zeilen für Put und Flush aus, sodass nur die Zeile DB::open übrig bleibt, und führe das Programm erneut aus. Wenn du das Verzeichnis jetzt auflistest, ist die alte Datei 000004.log verschwunden. An ihre Stelle ist ein neues, fast leeres Log mit einer höheren Nummer getreten. Der Inhalt wurde in Schritt drei in die SST geschrieben. Damit waren die Datensätze veraltet, und RocksDB hat die Datei beim erneuten Öffnen verworfen.

Das ist die vollständige Kopplung der Lebenszyklen von WAL und Memtable. 

Um eine Ebene tiefer zu gehen, können wir das Binary aus Schritt eins unter Linux mit strace -e trace=write,fdatasync ausführen. So wird die Dauerhaftigkeitsgarantie an der Syscall-Grenze sichtbar. Die sequenziellen write-Aufrufe hängen Daten an die .log-Datei an. fdatasync erscheint nur, wenn WriteOptions.sync gesetzt ist.

Schritt fünf: Den Schlüssel löschen und die verbleibenden Daten betrachten

Die frühere Aussage, dass ein Delete ein Schreibvorgang ist, lässt sich direkt beobachten. 

Ändere main.rs, um den Schlüssel zu löschen und einen weiteren Flush zu erzwingen:

db.delete(b"slot:0001").unwrap();
db.flush().unwrap();

Führe das Programm aus und liste anschließend das Verzeichnis auf. 

Jetzt gibt es zwei .sst-Dateien. Die ältere Datei bleibt unverändert, weil sie unveränderlich ist. Sie enthält also weiterhin den Schlüssel und seinen Wert. Mit einem Scan können wir das überprüfen:

$ sst_dump --file=/tmp/lsm-trace/000010.sst --command=scan
'slot:0001' seq:1, type:1 => hello

Scanne jetzt die neuere Datei:

$ sst_dump --file=/tmp/lsm-trace/000014.sst --command=scan
'slot:0001' seq:2, type:0 =>

Es ist derselbe Schlüssel, aber mit einer höheren Sequenznummer. Er hat type:0 statt type:1 und enthält keinen Wert. Das ist ein Tombstone: Der Datensatz kTypeDeletion aus dem Abschnitt über WriteBatch wurde in eine eigene SST geschrieben. Die Datenbank enthält jetzt sowohl den Wert als auch den Datensatz seiner Löschung – nebeneinander in getrennten Dateien.

Beim Lesen des Schlüssels wird dieser Widerspruch zugunsten des Tombstones aufgelöst. 

Wir können das überprüfen, indem wir dem Programm eine Suche hinzufügen:

match db.get(b"slot:0001").unwrap() {
    Some(v) => println!("found: {:?}", v),
    None => println!("not found"),
}

Das Programm gibt not found aus, weil der Lesepfad neuere Daten zuerst prüft und Sequenznummer 2 Vorrang vor Sequenznummer 1 hat. Aus Sicht der Datenbank ist der Wert verschwunden, obwohl er sich weiterhin in der älteren SST-Datei auf dem Datenträger befindet. 

Es wurde kein Speicher freigegeben. Die Löschung wurde lediglich vermerkt und überschattet den Wert, bis die Komprimierung die beiden Dateien schließlich zusammenführt und sowohl den Tombstone als auch den überschatteten Wert entfernt.

Schritt sechs: Den Schlüssel löschen und die verbleibenden Daten betrachten

Auch der Datensatztyp Merge lässt sich beobachten. Dafür muss ein Merge-Operator konfiguriert werden, da RocksDB ohne ihn nicht weiß, was ein Operand bedeutet.

Lösche das Datenbankverzeichnis erneut und ersetze main.rs durch den folgenden Code:

use rocksdb::{Options, DB, MergeOperands};

fn add(_key: &[u8], existing: Option<&[u8]>, operands: &MergeOperands) -> Option<Vec<u8>> {
    let mut total: i64 = existing
        .and_then(|v| std::str::from_utf8(v).ok())
        .and_then(|s| s.parse().ok())
        .unwrap_or(0);
    for op in operands {
        total += std::str::from_utf8(op).ok().and_then(|s| s.parse().ok()).unwrap_or(0);
    }
    Some(total.to_string().into_bytes())
}

fn main() {
    let mut opts = Options::default();
    opts.create_if_missing(true);
    opts.set_merge_operator_associative("add", add);
    let db = DB::open(&opts, "/tmp/lsm-merge").unwrap();

    db.merge(b"counter", b"1").unwrap();
    db.merge(b"counter", b"1").unwrap();
    db.merge(b"counter", b"1").unwrap();
    println!("{:?}", db.get(b"counter").unwrap());
}

Die Ausgabe des WAL zeigt drei separate MERGE-Datensätze. Das sind drei Anhänge statt eines einzelnen Lesevorgangs:

$ ldb dump_wal --walfile=/tmp/lsm-trace/000004.log --header
Sequence,Count,ByteSize,Physical Offset,Key(s)
1,1,23,0,MERGE(0) : 0x636F756E746572
2,1,23,30,MERGE(0) : 0x636F756E746572
3,1,23,60,MERGE(0) : 0x636F756E746572

Der Merge-Operator hat die Kette beim Lesen zusammengeführt und das Ergebnis als Rohbytes ausgegeben. Das Programm gibt Some([51]) aus, weil 51 der ASCII-Code für das Zeichen 3 ist. Auch das liegt daran, dass Schlüssel und Werte beliebige Byte-Arrays sind.

Wir können außerdem vor der Suche db.flush().unwrap(); hinzufügen, das Verzeichnis löschen und das Programm erneut ausführen. Ein Scan der SST zeigt einen einzigen Datensatz:

'counter' seq:3, type:2 => 3

Der Flush hat den Operator angewendet und die Datensätze zu einem einzelnen Operanden zusammengeführt.

Warum ist Level 0 besonders?

Neue SST-Dateien landen in Level 0. Sie sind direkte Snapshots von Memtables. Jede deckt den Schlüsselbereich ab, den die jeweilige Memtable aufgenommen hat. Deshalb können sich L0-Dateien überschneiden, was häufig geschieht. Das unterscheidet L0 von allen tieferen Leveln. Dort überschneiden sich die Dateien nicht: Jede Datei besitzt einen eigenen Schlüsselbereich, sodass ein bestimmter Schlüssel pro Level in höchstens einer Datei enthalten sein kann.

Daraus folgt, dass jede L0-Datei ein weiterer möglicher Speicherort für einen Schlüssel ist. Die Anzahl der L0-Dateien wirkt sich daher direkt negativ auf die Leseleistung aus. Deshalb überwacht RocksDB diese Anzahl genau und drosselt Schreibvorgänge oder hält sie sogar an, wenn sie zu stark steigt.

L0 klein zu halten ist eine der Hauptaufgaben der Komprimierung.

Warum übertreffen LSM-Bäume B-Bäume beim Schreiben?

B-Bäume bezahlen die Kosten der Organisation beim Schreiben, damit Lesevorgänge alles genau dort finden, wo es hingehört. LSM-Bäume verschieben die Organisation dagegen in die Hintergrundkomprimierung, die später gesammelt ausgeführt wird.

Der B-Baum ist die Grundlage der meisten traditionellen Datenbanken. Er aktualisiert Daten direkt an ihrem Speicherort. Jeder Schreibvorgang sucht daher die Seite, zu der der Schlüssel gehört, liest sie, verändert sie und schreibt sie zurück. Die beteiligten Seiten sind über den Datenträger verteilt. Ein Strom logisch zufälliger Schreibvorgänge wird damit zu einem Strom physisch zufälliger I/O-Operationen.

Der LSM-Baum weigert sich, diese Kosten beim Schreiben zu bezahlen. Er hängt an das WAL an, puffert in der Memtable und fasst Daten bei Flushes zusammen. Jeder Schreibvorgang auf den Datenträger erfolgt sequenziell. Die organisatorischen Schulden werden auf die Komprimierung verschoben. Die Arbeit verschwindet nicht. Sie wird später gesammelt bezahlt und in eine Form gebracht, mit der Datenträger besonders gut umgehen können.

Bei SSDs ist das besonders wichtig, weil sie Daten überhaupt nicht direkt an ihrem Speicherort überschreiben können. 

Flash-Speicher wird in großen Blöcken gelöscht, die von Hunderten Kilobyte bis zu mehreren Megabyte reichen, und in kleineren Seiten beschrieben. Daher zwingt jedes kleine, zufällige Überschreiben den Flash Translation Layer (FTL) des Laufwerks dazu, aktive Daten zu verschieben und im Hintergrund Blöcke zu löschen. 

Die zufälligen Seitenschreibvorgänge eines B-Baums zwingen den FTL ständig dazu. Das Gerät verursacht zusätzliche Schreibverstärkung, die zu der Schreibverstärkung der Datenstruktur selbst hinzukommt. Bezahlt wird dafür sowohl beim Durchsatz als auch bei der Lebensdauer des Laufwerks. Die großen sequenziellen Schreibvorgänge eines LSM-Baums kommen dem Optimalfall für Flash-Hardware sehr nahe.

Am besten lässt sich das als Kredit verstehen. Die aufgeschobene Organisation wird später als I/O für die Komprimierung fällig, und Lesevorgänge müssen mehr Orte prüfen als bei einem B-Baum. Der LSM-Baum kauft also heute Schreibdurchsatz und zahlt später mit Lese- und Speicherplatzverstärkung zurück. 

Einen ausführlicheren Vergleich von LSM-Baum und B-Baum hinsichtlich Lese-, Schreib- und Speicherplatzverstärkung bietet B-Baum vs. LSM-Baum. 

Was geschieht nach einem Absturz von RocksDB?

Die Memtable liegt im flüchtigen Arbeitsspeicher. Ein Absturz löscht sie also. Genau deshalb gibt es das WAL.

Beim Neustart gibt RocksDB jeden bestätigten Schreibvorgang wieder, der noch nicht in eine SST geschrieben wurde. Diese Schreibvorgänge werden in eine neue Memtable eingefügt, um den Zustand vor dem Absturz wiederherzustellen. Die Wiederherstellungskosten sind proportional zur noch nicht geschriebenen Datenmenge. Deshalb sind die Lebenszyklen von WAL und Memtable miteinander verknüpft. Sobald der Inhalt einer Memtable sicher in eine SST geschrieben wurde, sind die entsprechenden Log-Einträge veraltet und das WAL kann gekürzt werden.

Ein Schreibvorgang ist dauerhaft, sobald der Log-Anhang gespeichert wurde. Später wird er durch die Organisation beim Flush effizient lesbar. B-Bäume koppeln diese Vorgänge, LSM-Bäume trennen sie. Die meisten Eigenschaften der Struktur ergeben sich aus dieser Trennung. 

Wie belastet Solana den Schreibpfad?

Der erste Artikel dieser Reihe beschreibt, wie Agave das Ledger von Solana in RocksDB speichert. Aus Sicht des Schreibpfads kommt diese Arbeitslast einem eigens entwickelten Stresstest nahe. Shreds – die Roheinheiten der Ledger-Daten – treffen kontinuierlich mit voller Leitungsgeschwindigkeit über das Netzwerk ein. Jeder einzelne muss den Pfad aus WAL-Anhang und Einfügen in die Memtable durchlaufen, bevor die Speicherschicht des Validators ihre Arbeit erledigt hat.

Dabei kommt exakt dieselbe Technik zum Einsatz, die dieser Artikel nachverfolgt hat – nur im Produktionsmaßstab. Wenn Shreds eintreffen, validiert der Einfügepfad des Blockstore in Agave einen vollständigen Batch eingehender Shreds, versucht für fehlende Shreds eine Reed-Solomon-Wiederherstellung und stellt alles – Shred-Payloads, Slot-Metadaten, Erasure-Metadaten und Indexaktualisierungen – in einem einzigen RocksDB-WriteBatch bereit, bevor es mit einem atomaren Schreibvorgang gespeichert wird.

Vereinfacht aus insert_data_shred:

// We don't want only a subset of these changes going through.
write_batch.put_bytes::<cf::ShredData>((slot, index), &shred.payload)?;
update_slot_meta(/* ...metadata updates */);
data_index.set_present(index, true);

Dieser Kommentar bringt die Aussage dieses Artikels durch die Agave-Entwickler in neun Wörtern auf den Punkt: Der Batch ist die Einheit der Atomarität. Ein Absturz des Validators während des Einfügens darf das Ledger niemals in einem teilweise aktualisierten Zustand hinterlassen. 

Der im Beispiel verfolgte Batch mit einem Element wird in einem Validator zu einem Batch mit Tausenden Elementen: Shreds und ihre Metadaten über mehrere Column Families hinweg, ein Sequenznummernbereich, ein WAL-Anhang und ein Group Commit.

Das Praktische daran: Shreds beginnen mit der Slot-Nummer – das Tupel (slot, index) aus dem vereinfachten Codebeispiel ist der Schlüssel ShredData – und Slots steigen nahezu monoton. Jede Memtable nimmt daher ein schmales, weitgehend zusammenhängendes Band des Schlüsselraums auf. Die Flushes erzeugen L0-Dateien, die sich kaum überschneiden.

Wir erleben diesen Schreibpfad unmittelbar. 

Die Archivsysteme, die wir bei Helius betreiben, nehmen den vollständigen Transaktionsverlauf von Solana in RocksDB auf – Hunderte Terabyte in einer dauerhaft wachsenden, von Anhängen geprägten Arbeitslast. Die Migration, aus der diese Architektur hervorging, dokumentieren wir in unserem Artikel Von ClickHouse zu RocksDB migrieren.

Fazit

Ein LSM-Baum ist ein Handel mit der Hardware. Alle Schreibvorgänge werden sequenziell, dafür wird die Organisation der Daten auf später verschoben. Der Lesepfad muss deshalb beispielsweise an mehr Stellen nach Daten suchen als bei einem B-Baum. Die Memtable nimmt Daten auf, das WAL garantiert ihre Dauerhaftigkeit und die SSTs sammeln sich an. Auf Flash-Speichern, die zufälliges Überschreiben doppelt bestrafen, ist das ein hervorragender Handel.

Schreibvorgänge sind jedoch die einfache Hälfte. Der Preis dieses Designs wird beim Lesen bezahlt, weil der aktuelle Wert eines Schlüssels in der Memtable, einer L0-Datei oder einem beliebigen tieferen Level liegen kann. Die Mechanismen, die diesen Preis begrenzen, machen die Entwicklung von LSM-Systemen besonders interessant. 

Der nächste Artikel dieser Reihe führt durch den Lesepfad und behandelt Memtables, Bloomfilter, den Block-Cache und das Verstärkungsdreieck in der Praxis.

Wenn es für dich nach einem gelungenen Nachmittag klingt, ein einzelnes Schlüssel-Wert-Paar durch vier verschiedene Datenstrukturen zu verfolgen, dann entwickle mit uns. Die in dieser Reihe beschriebenen Systeme stellen wir bereit, betreiben und optimieren sie für die Größenordnung globaler Kapitalmärkte. Wir suchen Verstärkung für unser gesamtes Engineering-Team. Alle offenen Stellen findest du unter helius.dev/careers.