Log-Structured Merge-Tree

Ein Log-Structured Merge-Tree, kurz LSM-Tree, ist eine für schreibintensive Datenbestände optimierte Datenstruktur zur persistenten Speicherung sortierter Schlüssel-Wert-Paare. Änderungen werden zunächst im Arbeitsspeicher gesammelt und später in zusammenhängenden, sortierten Dateien auf einen Massenspeicher geschrieben. Hintergrundprozesse führen diese Dateien schrittweise zusammen. Dadurch werden viele kleine zufällige Schreibzugriffe durch größere sequenzielle Schreibvorgänge ersetzt.

Aufbau

Eine moderne LSM-Tree-Speicherengine besitzt üblicherweise folgende Bestandteile:

1. Ein Write-Ahead Log hält Änderungen für die Wiederherstellung nach einem Absturz fest.
2. Eine sortierte Datenstruktur im Arbeitsspeicher, häufig Memtable genannt, nimmt neue und geänderte Schlüssel auf.
3. Sobald die Memtable eine Größenbegrenzung erreicht, wird sie eingefroren und als unveränderliche sortierte Datei auf den Massenspeicher geschrieben. Solche Dateien werden häufig Sorted String Tables, kurz SSTables, genannt.
4. Eine Hintergrundverdichtung, die Compaction, führt mehrere SSTables zusammen, entfernt überschriebene Werte und verarbeitet Löschmarkierungen.

Das ursprüngliche Modell von 1996 beschrieb eine kleine speicherresidente Komponente $C_{0}$ und eine größere plattenbasierte Komponente $C_{1}$. Heutige Systeme verwenden meist mehrere aufeinanderfolgende Ebenen mit wachsender Kapazität.

Schreib- und Lesevorgänge

Ein Schreibvorgang wird zunächst sequenziell im Write-Ahead Log protokolliert und anschließend in die Memtable übernommen. Das Schreiben der sortierten Dateien erfolgt gebündelt. Dieses Verfahren ermöglicht einen hohen Schreibdurchsatz, da die Speicherengine nicht bei jeder Änderung eine bestehende Datei an einer zufälligen Position umorganisieren muss.

Bei einer Leseanfrage werden zunächst die Memtable und danach die relevanten SSTables durchsucht. Da ein Schlüssel in mehreren Dateien vorkommen kann, muss das System die neueste Version bestimmen. Bloomfilter und zusätzliche Indizes helfen dabei, Dateien auszuschließen, die den gesuchten Schlüssel sicher nicht enthalten.

Compaction

Bei der Leveled Compaction enthält eine Ebene normalerweise nur nicht überlappende Schlüsselbereiche. Dateien werden regelmäßig mit überlappenden Dateien der nächsten Ebene zusammengeführt. Dies begrenzt die Zahl der Dateien, die eine Leseanfrage prüfen muss, kann Daten während ihrer Lebensdauer jedoch mehrfach neu schreiben.

Bei der Tiered Compaction dürfen mehrere sortierte Läufe ähnlicher Größe nebeneinander bestehen. Sie werden seltener zusammengeführt. Das reduziert die Schreibverstärkung, erhöht aber typischerweise den Aufwand für Lesevorgänge und den vorübergehend benötigten Speicherplatz. Die Wahl der Strategie ist daher ein Kompromiss zwischen Schreibverstärkung, Leseverstärkung und Platzverstärkung.

Einsatz und Eigenschaften

LSM-Trees sind besonders für Arbeitslasten mit vielen Einfügungen und Aktualisierungen geeignet. Der hohe Schreibdurchsatz wird mit zusätzlicher Hintergrundarbeit erkauft. Compaction benötigt Ein- und Ausgabe-Bandbreite, kann dieselben Daten mehrfach schreiben und kann bei unzureichender Kapazität Schreibvorgänge verzögern.

Die Schlüssel-Wert-Datenbank RocksDB und das verteilte Datenbankmanagementsystem Apache Cassandra verwenden LSM-basierte Speicherarchitekturen.