Log-Structured Merge (LSM)-Trees sind eine innovative Art der Datenorganisation und -speicherung, die besonders für schreib-intensive Szenarien geeignet ist , und in einer ganzen Reihe verteilter Datenbanken zum Zug kommt. In diesem Blog-Post untersuchen die grundsätzliche Architektur und Funktionsweise moderner LSM-Trees.
LSM-Trees wurden 1996 von O’Neil et al im Paper “The log-structured merge-tree (LSM-tree)” vorgeschlagen. Seither wurde die Idee weiterentwickelt und fand Eingang in einer Reihe moderner, verteilter Datenbanksysteme.
Mit Bigtable dem Paper “Bigtable: A Distributed Storage System for Structured Data” veröffentlichten in 2006 Google-Mitarbeiter ihr Konzept, wie sie über dem Google Filesystem, eine sehr schnelle NoSQL-Datenbank realisieren konnten.
Die Konzepte des Papers wurden als erste von der HBase-Community in einem Open-Source-Projekt nachgebaut und hat seither in verschiedenen anderen OLTP-Systemen Eingang gefunden, die in sehr schnell massive Datenmengen verarbeiten können. Prominente Beispiele sind Apache Cassandra, InfluxDB und RocksDB.
Wir untersuchen in diesem Artikel diese moderne Form der LSM-Trees.
Grundstruktur eines modernen LSM-Baums
Die Hauptidee hinter LSM-Bäumen besteht in der Beobachtung, dass in sehr großen Datenbeständen die jüngsten Daten – oft als hot data bezeichnet – am häufigsten gelesen werden.
Ein LSM-Baum besteht aus mehreren Ebenen:
- Write Ahead Log oder Commit Log (WAL)
- MemTable: die jüngsten Daten befinden sich im Memory.
- SSTables (Sorted String Tables): ist die MemTable voll, dann werden die Daten in eine SSTable auf die Festplatte geflushed.
Die Grafik verdeutlicht die Struktur. Sowohl die MemTable als auch die SSTables sind mit einem Suchbaum versehen, beispielsweise mit einem B-Baum (engl. B-Tree).
Sowohl MemTable als auch SSTables enthalten Logeinträge der Datenmanipulationen, sortiert nach Timestamp des Ereignisses. Aus diesen Eigenschaften leitet sich die Bezeichnung ‘Log-Structured Merge-Trees’.
Insert und delete in einem LSM-Tree
In einem LSM-Baum unterscheiden wir zwei Schreibbefehle: insert und delete. Update ist immer delete mit anschließendem insert.
Beim Schreiben wird der Befehl zuerst in ein sogenanntes Write Ahead Log (WAL) auf die Festplatte geschrieben, so dass sie im Fall eines Systemfehlers nicht verloren sind und fürs Recovery genutzt werden können. Manchmal ist statt von einem WAL die Rede von einem Commit Log.
Sind die Daten dort sicher angekommen, dann werden sie in die MemTable geschrieben – eine In-Memory-Tabelle im Arbeitsspeicher. Die Daten liegen dort in der Reihenfolge vor, wie sie eingetroffen sind.
Wenn die MemTable eine bestimmte Maximalgröße erreicht hat, wird nach Schlüssel sortiert. Von jedem Schlüssel, wird das jüngste Element berücksichtigt. Gelöschte Elemente sind mit einem Tombstone – also einem Delete-Flag – versehen.
MemTables können beachtlich groß werden. Und so lohnt es sich, sie mit einer Suchstruktur zu versehen. Rot-Schwarz-Bäume sind dazu besonders gut geeignet, weil sie das Einfügen neuer Knoten und das anschließende Balancieren des Baumes im Mittel mit konstantem Aufwand und nur im Worst-Case mit O(log(n)) erfolgt.
Das Ergebnis wird auf die Festplatte geschrieben – diese Struktur wird SST, oder SSTable, also Sorted String Table genannt.
In der Grafik sehen wir das WAL – der älteste Eintrag steht zuunterst, der jüngste zuoberst.
Die MemTable und die SSTables sind auf der Grafik sehr klein, können sie doch nur zwei Elemente fassen. In produktiven Systemen sind sie größer, jedoch immer noch relativ klein, gemessen an den immensen Datenmengen, die mit dieser Architektur verarbeitet werden.
Wir sehen in der Grafik die verschiedenen SSTables, die sich bereits angesammelt haben. Die Älteste steht ganz rechts.
Lesen in einem LSM-Tree
Soll im Beispiel in der Grafik oben der Wert für 18 gelesen werden, dann wird zuerst in der MemTable gesucht, wobei nur das jüngste Element berücksichtigt wird. Der Wert Eva wird gefunden und zurückgegeben.
Wird der Vorname für Key 22 gesucht, dann wird zuerst die Memtable konsultiert. 22 ist dort nicht vorhanden. Dann werden die SSTables durchsucht und zwar die jüngste zuerst – in unserer Grafik von links nach rechts. In der zweiten SSTable finden wir den aktuellen Wert für 22 und zwar Ana, wiederum wird das jüngste Element berücksichtigt.
Dass der Key 22 in der vierten SSTable mit einem anderen Wert auch schon vorhanden war, ist irrelevant.
Analoges passiert, wenn wir nach einem gelöschten Schlüssel suchen, beispielsweise nach 17. Diesen Key finden wir in der ältesten SSTable und er ist als gelöscht markiert.
Compaction
Das WAL und die Zahl der SSTables nehmen ständig zu. Das System würde damit ziemlich langsam werden, gerade wenn in älteren SSTables gesucht werden muss.
Die Compaction wirkt dem entgegen. Sie wird periodisch – alle paar Minuten – vom System durchgeführt.
Bei einer Minor-Compaction werden die jüngsten SSTable zu einer einzigen SSTable zusammengefasst. Diese wird größer werden, als die bisherigen SSTables. Dabei werden jeweils die jüngsten Einträge berücksichtigt. Deletes werden gelöscht und die Elemente werden nach Key Sortiert. Ob jetzt noch eine Suchstruktur wie ein Binärbaum organisiert wird, hängt vom Systemdesign ab. Sicher hat auch die Größe dieser lompaktierten SSTables einen Einfluss darauf.
Nach der Compaction werden die kleinen SSTables gelöscht. Die kompaktierte SSTable wird beim Suchen jeweils mitberücksichtigt.
Wird diese Compaction zum Beispiel jede Minute einmal ausgeführt, dann ergeben sich bald viele kompaktierte SSTables.
Hier kommt die Major Compaction zum Zuge. Sie wird weniger oft ausgeführt und führt die kompaktierten Tabellen zusammen zu einer großen SSTable. Die Major Compaction ist auf der grafischen Darstellung nicht berücksichtigt.
Das WAL darf auch nicht zu viel Platz einnehmen. Es wird dann überflüssig, wenn wir sicher sein können, dass die Daten nicht verloren gehen können. Wen also Beispielsweise die Festplatte auf der sich die SSTables befinden crasht, dann dürfen die Daten nicht verloren gehen.
Wann wir uns dessen sicher sein können, hängt auch wieder vom Design des Systems ab. LSM-Trees kommen in verteilten Systemen zum Einsatz. Dort werden die Daten zur Sicherheit repliziert. Können wir also sicher sein, dass alle Daten repliziert sind, an kann das WAL ebenfalls gekürzt werden – um diejenigen Daten, die sicher repliziert wurden.
Vorteile von LSM-Bäumen
LSM-Trees sind sehr effizient beim Schreiben und können für sehr große Tabellen mit vielen Zeilen und Spalten eingesetzt werden.
LSM-Bäume werden gerne dort eingesetzt, wo ehesten die gerade geschriebenen Daten – gelesen werden. Diese befinden sich noch in der Memtable oder in den jüngeren SSTables.
LSM-Bäume in modernen Datensystemen
- Apache Cassandra ist ein weit verbreitetes Open-Source-Datenbanksystem, das für seine hohe Skalierbarkeit und Ausfallsicherheit bekannt ist. Cassandra verwendet LSM-Bäume, um Daten effizient zu speichern und schnelle Schreibvorgänge zu ermöglichen. Dies macht es ideal für Anwendungen mit hohem Schreibvolumen und verteilten Daten.
- ScyllaDB wurde nach den gleichen Prinzipien gebaut wie Apache Cassandra und soll mit Cassandra kompatibel sein. Die hohe Performanz erreicht ScyllaDB auch dank LSM-Bäumen.
- InfluxDB, die beliebte Zeitreihendatenbank verwendet mit TSM (Time-Structured Merge Tree) eine Variante von LSM-Bäumen.
- Apache AsterixDB ist ein hochskalierbares und sehr flexibles Big Data Management System, dessen Storage Library unter anderem auf LSM-Bäumen basiert.
- RocksDB ist eine eingebettete Datenbank-Engine, die von Facebook entwickelt wurde und häufig als Grundlage für andere Anwendungen und Systeme dient. Sie basiert auf LSM-Bäumen und bietet eine hohe Leistung und Skalierbarkeit, was sie für viele Anwendungsfälle in der Softwareentwicklung attraktiv
Fazit
Zusammenfassend haben wir gesehen, wie moderne LSM-Trees die Balance zwischen Schreibeffizienz und Leseleistung schaffen. Die jüngsten Daten werden im Memory-Cache gehalten und ältere Daten werden auf der Festplatte von Hintergrundprozessen kompaktiert.
Besonders bemerkenswert ist die Anpassungsfähigkeit von LSM-Trees auf verschiedene Datenbank-Typen, die Spannweite reicht vom Wide-Column Store, über Zeitreihendatenbanken bis hin zum verteilten Cache.
