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.
Eine moderne LSM-Tree-Speicherengine besitzt üblicherweise folgende Bestandteile:
Das ursprüngliche Modell von 1996 beschrieb eine kleine speicherresidente Komponente und eine größere plattenbasierte Komponente . Heutige Systeme verwenden meist mehrere aufeinanderfolgende Ebenen mit wachsender Kapazität.
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.
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.
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.
