Schreiben statt Suchen – Log-Structured Merge-Trees und die Umkehrung der Datenbank

Der Aufhänger

Stellen Sie sich einen Bibliothekar vor, dem jede Sekunde ein neues Buch in die Hand gedrückt wird. Er soll jedes davon sofort an seinen alphabetisch korrekten Platz stellen. Beim ersten Buch läuft er ins Regal, schiebt Nachbarn beiseite, macht Platz, stellt es hinein. Beim zweiten dasselbe, nur in einem anderen Gang. Beim dritten wieder woanders. Nach zehn Minuten ist der Bibliothekar außer Atem und der Bücherstapel auf seinem Tresen höher als zuvor. Er verbringt fast seine ganze Zeit mit Laufen, nicht mit Einsortieren.

Nun ein zweiter Bibliothekar mit derselben Flut. Er stellt kein einziges Buch sofort ins Regal. Er legt jedes ankommende Buch einfach oben auf einen Stapel auf seinem Tresen – Ankunftsreihenfolge, kein Sortieren, keine Wege. Wenn der Stapel eine bestimmte Höhe erreicht, sortiert er ihn einmal in Ruhe und schiebt ihn als geschlossenen, bereits sortierten Block ins Regal. Ab und zu nimmt er mehrere solcher Blöcke und verschmilzt sie zu einem größeren, weiterhin sortierten Block. Dieser zweite Bibliothekar nimmt in derselben Zeit ein Vielfaches an Büchern entgegen. Der Preis: Wer ein bestimmtes Buch sucht, muss unter Umständen in mehreren sortierten Blöcken nachsehen, nicht nur an einer Stelle.

Dieser Unterschied ist keine Anekdote, sondern der Kern einer der folgenreichsten Entwurfsentscheidungen im Bau von Datenbanken. Der erste Bibliothekar ist der klassische B-Baum, das seit den 1970er-Jahren dominierende Indexverfahren, das jede Änderung sofort an ihren endgültigen Platz schreibt. Der zweite ist der Log-Structured Merge-Tree, kurz LSM-Tree – die Speicherarchitektur, die heute unter Cassandra, RocksDB, LevelDB, HBase, ScyllaDB und über Umwege unter einem Großteil der modernen Cloud-Datenbanken steckt.

Dieser Artikel erklärt, warum sequentielles Schreiben so viel billiger ist als wahlfreies, welche Idee der LSM-Tree daraus macht, wie seine Bauteile – Memtable, SSTable, Write-Ahead-Log, Bloom-Filter und Compaction – zusammenspielen, welche drei Kosten man dabei gegeneinander abwägt und warum es kein universell bestes Speicherverfahren geben kann. Am Ende sollten Sie eine Datenbank nicht mehr nur an ihrer Abfragesprache messen, sondern an der Frage, wie sie schreibt.

Das Kernproblem: warum wahlfreies Schreiben weh tut

Um zu verstehen, warum der LSM-Tree existiert, muss man kurz auf die Physik der Speichermedien schauen. Datenbanken leben nicht im luftleeren Raum; ihre Entwürfe sind Antworten auf die Eigenheiten der Hardware, auf der sie laufen.

Auf einer klassischen Magnetfestplatte (HDD) besteht ein Zugriff aus zwei Teilen: dem Suchen (die Schreib-/Leseköpfe zur richtigen Spur bewegen, dazu warten, bis der richtige Sektor unter dem Kopf rotiert) und dem eigentlichen Übertragen der Daten. Das Suchen ist mechanisch und dauert Millisekunden; das Übertragen ist schnell. Der entscheidende Punkt: Sequentielles Schreiben – also ein großer, zusammenhängender Block – kostet einmal Suchen und dann nur noch Übertragen. Wahlfreies Schreiben (random write) – viele kleine Änderungen an verstreuten Stellen – kostet für jede Änderung erneut das teure Suchen. Der Unterschied liegt bei rotierenden Platten schnell bei zwei bis drei Größenordnungen.

Nun der B-Baum. Ein B-Baum hält seine Schlüssel sortiert in Knoten, die über die Platte verteilt liegen. Fügt man einen neuen Datensatz ein, muss er an genau die Stelle geschrieben werden, wo er hingehört – irgendwo mitten im Baum. Bei hoher Einfügerate bedeutet das genau die verstreuten, wahlfreien Schreibvorgänge, die die Platte hasst. Schlimmer noch: Damit eine einzige geänderte Zeile persistiert wird, muss oft eine ganze Seite (typisch 4 bis 16 KB) neu geschrieben werden, auch wenn die Änderung nur wenige Bytes betraf. Man nennt dieses Missverhältnis zwischen logischer Änderung und physisch geschriebenen Bytes Schreibverstärkung (write amplification) – ein Begriff, der uns noch mehrfach begegnen wird.

Man könnte meinen, SSDs lösen das Problem, weil sie keine beweglichen Teile haben. Sie mildern es, heben es aber nicht auf. Flash-Speicher kann nicht einfach überschrieben werden; er muss in großen Blöcken gelöscht werden, bevor er neu beschrieben wird. Viele kleine, verstreute Schreibvorgänge führen deshalb zu internem Umkopieren (der Flash Translation Layer schiebt gültige Daten um, um Blöcke freizuräumen) – wieder Schreibverstärkung, diesmal versteckt in der Firmware, und obendrein Abnutzung, denn Flash-Zellen halten nur eine begrenzte Zahl von Löschzyklen aus. Auch auf moderner Hardware gilt also: große, sequentielle Schreibvorgänge sind der Freund, viele kleine, wahlfreie der Feind.

Die Frage, die sich daraus ergibt, ist einfach zu stellen und schwer zu beantworten: Kann man eine Datenbank so bauen, dass sie fast nur sequentiell schreibt – und trotzdem effizient nach einzelnen Schlüsseln suchen kann?

Die Idee: erst schreiben, später sortieren

Die konzeptionelle Wurzel liegt in einer Arbeit, die zunächst gar nichts mit Datenbanken zu tun hatte. 1991 beschrieben Mendel Rosenblum und John Ousterhout in The Design and Implementation of a Log-Structured File System (SOSP 1991) ein Dateisystem, das jede Änderung nicht an ihren angestammten Platz schreibt, sondern sie im Speicher puffert und dann alle gepufferten Änderungen zusammen als einen einzigen, langen sequentiellen Schreibvorgang – ein „Log" – auf die Platte streamt. Die Idee: Das Medium wird als endlos fortlaufendes Journal behandelt; man hängt immer nur hinten an.

Fünf Jahre später übertrugen Patrick O'Neil, Edward Cheng, Dieter Gawlick und Elizabeth O'Neil dieses Prinzip auf das Problem des Indexierens. Ihre Arbeit The Log-Structured Merge-Tree (LSM-Tree) erschien 1996 in Acta Informatica (Band 33, Heft 4, S. 351–385). Ihr Ausgangsszenario war sehr konkret: Dateien mit einer sehr hohen Rate an Einfügungen über lange Zeit – etwa Verlaufstabellen oder Transaktionsprotokolle –, bei denen ein herkömmlicher B-Baum-Index an den wahlfreien Schreibvorgängen erstickt. Ihre Lösung war ein mehrstufiges Gebilde: eine kleine, sortierte Komponente im Arbeitsspeicher (in der Originalarbeit C0 genannt) und eine oder mehrere größere, sortierte Komponenten auf der Platte (C1, C2, …). Neue Einträge landen zuerst in C0; läuft diese voll, wird ihr Inhalt in einem sequentiellen Durchlauf mit C1 verschmolzen – ein Prozess, den die Autoren rolling merge nannten.

Der Kerngedanke, der aus alldem hervorgeht, lässt sich in einem Satz fassen: Ersetze viele teure, wahlfreie Schreibvorgänge durch wenige billige, sequentielle – indem du Änderungen im Speicher sammelst, sortiert auf die Platte streamst und die Sortierung des Gesamtbestands später in geordneten Verschmelzungen nachholst. Die Datenbank wird gewissermaßen von innen nach außen gekehrt: Statt beim Schreiben zu sortieren und beim Lesen zu profitieren, schreibt sie roh und arbeitet die Ordnung im Hintergrund nach.

Der Bauplan eines modernen LSM-Trees

Die heute in RocksDB, LevelDB oder Cassandra verbaute Form weicht im Detail von der Originalarbeit ab, folgt aber demselben Geist. Fünf Bauteile bilden das Gerüst.

Das Write-Ahead-Log (WAL). Bevor irgendetwas anderes passiert, wird jede Schreiboperation ans Ende einer Log-Datei auf der Platte angehängt – rein sequentiell, also billig. Dieses Journal dient allein der Dauerhaftigkeit: Stürzt der Prozess ab, bevor die Daten anderswohin gelangt sind, kann der Zustand aus dem WAL rekonstruiert werden. Es ist dasselbe Prinzip des unveränderlichen Ereignisprotokolls, das auch Event Sourcing zugrunde liegt.

Die Memtable. Zugleich wird der Eintrag in eine sortierte Datenstruktur im Arbeitsspeicher geschrieben – die Memtable, meist eine Skip-Liste oder ein balancierter Baum. Weil sie im RAM liegt, sind Einfügungen und Sortierung hier billig. Alle jüngsten Schreibvorgänge leben zunächst nur hier (und, zur Sicherheit, im WAL).

Die SSTable. Erreicht die Memtable eine Schwellengröße, wird sie „eingefroren" und ihr sortierter Inhalt in einem einzigen sequentiellen Schwung auf die Platte geschrieben – als Sorted String Table (SSTable): eine unveränderliche Datei, die Schlüssel-Wert-Paare in Schlüsselreihenfolge enthält, meist begleitet von einem kleinen Index über die enthaltenen Schlüsselbereiche. „Unveränderlich" ist das entscheidende Wort: Eine einmal geschriebene SSTable wird nie mehr an Ort und Stelle geändert. Danach wird eine frische, leere Memtable eröffnet und der zugehörige WAL-Abschnitt darf verworfen werden.

Die Ebenen und die Compaction. Über die Zeit entstehen so immer mehr SSTables. Blieben sie einfach liegen, müsste jede Suche immer mehr Dateien durchkämmen. Deshalb läuft im Hintergrund die Compaction: Ein Prozess nimmt mehrere SSTables, verschmilzt ihre sortierten Inhalte zu einer neuen, größeren, weiterhin sortierten SSTable und wirft die Ausgangsdateien weg. Weil alle Eingaben sortiert sind, ist dies ein klassischer Merge wie beim Mergesort – sequentielles Lesen, sequentielles Schreiben. Meist sind die SSTables in Ebenen (levels) organisiert, wobei jede tiefere Ebene um einen festen Faktor größer ist als die darüberliegende.

Der Bloom-Filter. Um zu vermeiden, dass eine Suche jede SSTable anfassen muss, hängt an jeder SSTable ein Bloom-Filter – eine kleine, probabilistische Datenstruktur, die die Frage „ist Schlüssel k möglicherweise in dieser Datei?" sehr schnell und speicherarm beantwortet. Ein Bloom-Filter kann sich irren, aber nur in eine Richtung: Er meldet nie fälschlich „nicht enthalten" (keine false negatives), wohl aber gelegentlich fälschlich „vielleicht enthalten" (ein false positive). Für den LSM-Tree ist genau diese Asymmetrie Gold wert: Sagt der Filter „nein", kann die ganze Datei ohne Plattenzugriff übersprungen werden.

Lesen, Löschen, Ändern: die Rückseite der Medaille

So elegant der Schreibpfad ist – die Kosten wandern auf den Lesepfad. Eine Punktsuche nach einem Schlüssel läuft so ab: Zuerst schaut die Datenbank in der Memtable. Wird sie dort nicht fündig, geht sie die SSTables von der jüngsten zur ältesten durch – denn ein Schlüssel kann in mehreren SSTables mit unterschiedlichen Versionen liegen, und die jüngste gewinnt. Für jede infrage kommende SSTable befragt sie zuerst den Bloom-Filter; nur wenn dieser „vielleicht" sagt, wird tatsächlich in die Datei gelesen. Der erste Treffer (von neu nach alt) ist die gültige Antwort.

Hier zeigt sich der Preis des Verfahrens: Während der B-Baum eine Punktsuche in einer festen, geringen Zahl von Zugriffen erledigt (die Baumhöhe), muss der LSM-Tree im ungünstigen Fall mehrere Ebenen konsultieren. Man nennt das Leseverstärkung (read amplification) – ein logischer Lesevorgang löst mehrere physische aus. Die Bloom-Filter drücken diese Kosten dramatisch, heben sie aber nicht vollständig auf.

Besonders lehrreich ist der Umgang mit dem Löschen. Weil SSTables unveränderlich sind, kann man einen Datensatz nicht einfach herausstreichen – die Datei, in der er steht, darf ja nicht angefasst werden. Stattdessen schreibt der LSM-Tree einen speziellen Markierungseintrag, einen Grabstein (tombstone): „Schlüssel k ist ab jetzt gelöscht." Bei der Suche gilt der jüngste Eintrag; trifft man zuerst auf den Grabstein, lautet die Antwort „nicht vorhanden", selbst wenn tiefere Ebenen noch den alten Wert enthalten. Erst bei einer späteren Compaction, die sowohl den Grabstein als auch den alten Wert einsammelt, wird der Platz tatsächlich freigegeben. Genau dieselbe Logik gilt fürs Ändern: Ein Update ist nichts anderes als das Schreiben einer neuen Version desselben Schlüssels; die alte lebt weiter, bis die Compaction sie überschreibt. Der LSM-Tree kennt im Grunde nur eine Operation – das Anhängen –, und Löschen wie Ändern sind Spezialfälle davon. Wer den Vault-Artikel über Event Sourcing gelesen hat, erkennt hier dieselbe Philosophie: Der Zustand ist das Ergebnis einer Folge unveränderlicher Ereignisse, nicht ein Wert, den man überschreibt.

Diese Grabsteine haben eine unangenehme Nebenwirkung, die in der Praxis regelmäßig zu Überraschungen führt: Löscht man sehr viele Datensätze, füllt sich die Datenbank zunächst mit Grabsteinen und wird dabei größer, nicht kleiner, und Bereichsabfragen über gelöschte Bereiche können langsamer werden, weil sie sich durch Massen von Grabsteinen arbeiten müssen. Ich bin der Meinung, dass dieses kontraintuitive Verhalten – Löschen kostet erst einmal Platz und Leseleistung – einer der häufigsten Stolpersteine beim produktiven Betrieb von Cassandra und ähnlichen Systemen ist.

Die drei Kosten: Schreiben, Lesen, Platz

An dieser Stelle lohnt es sich, die Abwägung sauber zu benennen. Jede Speicher-Engine jongliert mit drei Arten von Verstärkung:

• Schreibverstärkung (write amplification): Wie viele Bytes werden physisch geschrieben pro Byte logischer Nutzdaten? Jede Compaction schreibt Daten erneut; ein Datensatz, der durch mehrere Ebenen wandert, wird mehrfach kopiert.
• Leseverstärkung (read amplification): Wie viele physische Zugriffe kostet eine logische Suche? Je mehr SSTables und Ebenen, desto teurer im ungünstigen Fall.
• Platzverstärkung (space amplification): Wie viel mehr Platz belegt die Datenbank, als die reinen Nutzdaten bräuchten? Alte Versionen und Grabsteine, die noch nicht wegkompaktiert wurden, kosten Speicher.

Der Clou ist, dass man diese drei nicht gleichzeitig minimieren kann. Genau das hält die Wahl der Compaction-Strategie in der Hand, und hier trennen sich zwei Schulen.

Size-Tiered Compaction (STCS) wartet, bis mehrere SSTables ähnlicher Größe auf einer Ebene angesammelt sind, und verschmilzt sie dann in einem Rutsch zu einer größeren. Das hält die Schreibverstärkung niedrig – jeder Datensatz wird pro Ebene nur etwa einmal umkopiert –, erkauft das aber mit hoher Lese- und Platzverstärkung: Ein Schlüssel kann in vielen gleich großen SSTables liegen, und während einer Verschmelzung existieren Eingabe- und Ausgabedateien kurzzeitig gleichzeitig, was den Platzbedarf vorübergehend nahezu verdoppeln kann. Diese Strategie ist der Freund schreiblastiger, platztoleranter Arbeitslasten – der Standard etwa in Cassandras klassischem Betrieb.

Leveled Compaction (LCS) hält stattdessen jede Ebene als eine Menge nicht-überlappender SSTables, sodass ein Schlüssel auf einer Ebene in höchstens einer Datei liegt. Das drückt Lese- und Platzverstärkung stark: Eine Punktsuche muss pro Ebene nur eine Datei prüfen, und es gibt kaum überflüssige Kopien. Der Preis ist eine deutlich höhere Schreibverstärkung, weil das Einordnen neuer Daten in eine Ebene das Neuschreiben überlappender Dateien der nächsten Ebene erzwingt. Als Faustzahl gilt hier ein Faktor von rund 10 pro Ebene; über einen mehrstufigen Baum summiert sich die Schreibverstärkung leicht auf das Zehn- bis Dreißigfache. LCS ist der Freund leselastiger, platzsensibler Arbeitslasten – der Standard etwa in RocksDB.

Man sieht: Es gibt kein „besser", nur ein „anders". Wer Lese- und Platzkosten senkt, zahlt beim Schreiben; wer beim Schreiben spart, zahlt beim Lesen und beim Platz. Diese Symmetrie ist kein Zufall der Implementierung, sondern hat einen tieferen, fast gesetzesartigen Grund.

Die RUM-Vermutung: warum es kein bestes Verfahren gibt

2016 gaben Manos Athanassoulis, Stratos Idreos und Kollegen dieser Beobachtung einen Namen und eine Form. In Designing Access Methods: The RUM Conjecture (EDBT 2016) formulierten sie: Jedes Zugriffsverfahren muss drei Größen gegeneinander abwägen – die Kosten des Lesens (Read), die Kosten des Aktualisierens (Update) und den Speicher-Overhead (Memory). Die Vermutung lautet, dass man nicht in allen dreien zugleich optimal sein kann: Optimiert man zwei dieser Größen scharf, verschlechtert sich zwangsläufig die dritte. Man kann sich den Entwurfsraum als Dreieck denken, in dem jedes reale Verfahren einen Punkt einnimmt – und die drei Ecken sind unerreichbare Ideale.

Diese Linse ordnet die ganze Landschaft. Der B-Baum sitzt in der Nähe der Lese-Ecke: Er ist auf schnelle Punkt- und Bereichssuchen optimiert und zahlt dafür beim Aktualisieren (wahlfreie Schreibvorgänge, Seiten-Neuschreiben). Der LSM-Tree sitzt in der Nähe der Update-Ecke: Er ist auf billiges, sequentielles Schreiben optimiert und zahlt dafür beim Lesen (mehrere Ebenen) und, je nach Compaction, beim Platz. Bloom-Filter wiederum sind ein bewusster Tausch: Sie geben ein wenig Speicher her (M), um Lesekosten (R) zu senken – ein Zug in Richtung einer Ecke, bezahlt mit der anderen.

Die RUM-Vermutung ist bewusst eine Vermutung, kein bewiesenes Theorem; sie ist ein Denkrahmen, kein formaler Unmöglichkeitsbeweis wie etwa das FLP-Resultat für verteilten Konsens. Aber als Kompass ist sie außerordentlich nützlich. Sie erklärt, warum die Datenbankwelt nicht auf eine Sieger-Architektur zusteuert, sondern in ein Spektrum spezialisierter Engines auseinanderläuft. Und sie liefert die richtige Frage, die man an jede neue Speicher-Engine stellen sollte: In welche Ecke des Dreiecks hat dieses Design sich bewegt, und was hat es dafür in der gegenüberliegenden Ecke aufgegeben?

Wo die Forschung weiterschraubt

Der LSM-Tree ist kein abgeschlossenes Kapitel, sondern ein aktives Forschungsfeld – und interessanterweise geht es dabei fast immer darum, den RUM-Kompromiss geschickter zu legen, statt ihn aufzuheben.

Ein erster Ansatz optimiert die Bloom-Filter. In der naiven Implementierung bekommt jede SSTable gleich viele Filter-Bits pro Element. Niv Dayan, Manos Athanassoulis und Stratos Idreos zeigten mit Monkey (SIGMOD 2017), dass das verschwenderisch ist: Weil die Gesamt-Lesekosten proportional zur Summe der Falsch-Positiv-Raten über alle Ebenen sind, lohnt es sich, den knappen Speicher ungleich zu verteilen – kleinere, dichtere Filter für die tieferen, größeren Ebenen. Bei gleichem Speicherbudget sinken so die Lesekosten spürbar, allein durch klügere Aufteilung derselben Bits.

Ein zweiter Ansatz feilt an der Compaction-Logik selbst. Mit Dostoevsky (SIGMOD 2018) identifizierten dieselben Autoren überflüssige Verschmelzungsarbeit und schlugen ein „lazy leveling" vor, das für die größte Ebene ein leveltypisches Verhalten beibehält, für die kleineren aber ein tiered-artiges – ein Mischverfahren, das gezielt bessere Punkte im Entwurfsraum trifft, als reines Tiering oder reines Leveling erreichen.

Ein dritter, sehr wirkungsvoller Ansatz greift die Schreibverstärkung an der Wurzel an. WiscKey (FAST 2016) beruht auf der Beobachtung, dass für die Sortierung nur die Schlüssel gebraucht werden, nicht die oft viel größeren Werte. Also trennt WiscKey beide: Schlüssel bleiben im LSM-Baum, die Werte wandern in ein separates, sequentielles Value-Log. Weil die Compaction nun nur noch Schlüssel und Metadaten umkopiert und nicht mehr die großen Werte, sinkt die Schreibverstärkung bei großen Werten drastisch – in der Arbeit um bis zu zwei Größenordnungen. Der Preis ist zusätzliche Komplexität bei der Speicherbereinigung des Value-Logs; auch hier gilt die RUM-Logik.

Diese Linie – Monkey, Dostoevsky und Verwandte aus Idreos' Harvard-Gruppe – verfolgt ein größeres Ziel: den LSM-Entwurfsraum navigierbar zu machen, also aus einer festen Architektur eine kontinuierliche Fläche von Konfigurationen zu machen, aus der man für eine gegebene Arbeitslast automatisch den optimalen Punkt wählen kann. Ich bin der Meinung, dass genau darin die eigentliche Zukunft liegt: nicht in einer weiteren „besten" Engine, sondern in Systemen, die ihre Position im RUM-Dreieck selbst an die beobachtete Last anpassen.

Wer den LSM-Tree benutzt – und warum

Die Reichweite dieses Verfahrens ist leicht zu unterschätzen, weil es meist unsichtbar in der untersten Schicht steckt. Googles BigTable (2006) machte den Ansatz für verteilte Systeme populär. Aus derselben Denkschule stammt LevelDB von Sanjay Ghemawat und Jeff Dean, eine kompakte eingebettete Bibliothek, die zur Blaupause für vieles Folgende wurde. Facebook (Meta) forkte LevelDB zu RocksDB, das heute als Speicher-Engine in einer erstaunlichen Bandbreite von Systemen dient. Apache Cassandra und HBase, die großen spaltenorientierten Speicher, ruhen ebenso auf dem LSM-Prinzip wie das auf Cassandra-Kompatibilität getrimmte ScyllaDB. Zeitreihendatenbanken wie InfluxDB und verteilte SQL-Systeme wie CockroachDB oder TiKV setzen auf LSM-basierte Engines (RocksDB beziehungsweise dessen Nachfolger), weil ihre Arbeitslast – hohe, kontinuierliche Schreibraten – exakt die Stärke des Verfahrens trifft.

Das Muster ist überall dasselbe: Sobald eine Anwendung mehr schreibt als sie punktuell liest, sobald Daten strömen statt vereinzelt abgefragt zu werden – Sensormessungen, Logs, Metriken, Chat-Nachrichten, Event-Streams –, ist der LSM-Tree die natürliche Wahl. Umgekehrt bleibt der B-Baum überlegen, wo Lesevorgänge dominieren, wo einzelne Zeilen häufig an Ort und Stelle aktualisiert werden und wo geringe, vorhersagbare Lese-Latenz wichtiger ist als maximaler Schreibdurchsatz – weshalb klassische relationale Systeme wie PostgreSQL, MySQL/InnoDB oder Oracle weiterhin auf B-Bäumen bauen. Beide leben nebeneinander, nicht weil die eine Welt rückständig wäre, sondern weil sie in unterschiedlichen Ecken des RUM-Dreiecks zu Hause sind.

Erkenntnis zum Mitnehmen

Die eigentliche Lehre des LSM-Trees reicht über Datenbanken hinaus. Sie lautet: Man kann eine teure, sofort fällige Arbeit in eine billige, aufgeschobene verwandeln – wenn man bereit ist, die aufgeschobene Arbeit später gebündelt und in einer für das Medium günstigen Form nachzuholen. Der LSM-Tree sortiert nicht beim Schreiben, sondern beim Verschmelzen; er löscht nicht sofort, sondern markiert; er räumt nicht ständig auf, sondern in großen, seltenen Durchläufen. Jedes Mal wird eine sofortige, feinkörnige, teure Operation durch eine spätere, grobkörnige, billige ersetzt.

Praktisch heißt das: Wenn Sie das nächste Mal vor einer Systemkomponente stehen, die unter einer Flut kleiner, teurer Änderungen leidet – eine Suchindexierung, ein Cache, eine Audit-Spur, eine Analytics-Pipeline –, fragen Sie sich, ob Sie dem LSM-Muster folgen können: Änderungen zunächst nur anhängen, in einem billigen Puffer sammeln und die teure Ordnungsarbeit gebündelt in den Hintergrund verschieben. Und wenn Sie eine Datenbank auswählen, hören Sie auf, nur auf die Abfragesprache und die Feature-Liste zu schauen. Fragen Sie stattdessen: Wie schreibt dieses System, wie liest es, wie viel Platz verschwendet es dabei – und in welche Ecke des RUM-Dreiecks passt das zu meiner Arbeitslast? Diese eine Frage sagt oft mehr über die Eignung eines Systems aus als jedes Datenblatt.

Reflexionsfrage

An welcher Stelle in Ihren eigenen Systemen bezahlen Sie heute den Preis des ersten Bibliothekars – viele kleine, teure „Sofort-an-den-richtigen-Platz"-Operationen –, obwohl die Arbeitslast in Wahrheit ein „erst anhängen, später bündeln" verträgt; und wo wäre umgekehrt der aufgeschobene Aufräumaufwand eines LSM-artigen Ansatzes gefährlicher als das Problem, das er löst?

Querverweise im Vault

• Das Logbuch der Wahrheit: Event Sourcing und CQRS verstehen – dieselbe Philosophie des unveränderlichen Anhängens: Zustand als Ergebnis einer Ereignisfolge.
• Zusammenwachsen ohne Absprache – CRDTs und die Mathematik der konfliktfreien Replikation – die konfliktfreie Verschmelzung von Daten, verwandt mit dem Merge der Compaction.
• Der Ring, der die Last verteilt: Consistent Hashing und die Kunst des sanften Umzugs – wie die LSM-Daten von Cassandra & Co. überhaupt auf viele Knoten verteilt werden.
• Wie Maschinen sich einig werden: Verteilter Konsens von FLP über Paxos zu Raft – die andere Sorte Unmöglichkeitsgrenze: FLP als bewiesenes Gegenstück zur RUM-Vermutung.
• Uhren, die ihre eigene Unsicherheit kennen: Google Spanner, TrueTime und die Beherrschung der Zeit in der Cloud – ein verteiltes Datenbanksystem, das viele dieser Bausteine zusammenführt.

Quellen

• O'Neil, Cheng, Gawlick, O'Neil (1996): The Log-Structured Merge-Tree (LSM-Tree), Acta Informatica 33(4):351–385 – die Originalarbeit. https://dl.acm.org/doi/10.1007/s002360050048
• Rosenblum, Ousterhout (1991): The Design and Implementation of a Log-Structured File System, SOSP 1991 – die konzeptionelle Wurzel. https://web.stanford.edu/~ouster/cgi-bin/papers/lfs.pdf
• Athanassoulis, Kester, Maas, Stoica, Idreos, Ailamaki, Callaghan (2016): Designing Access Methods: The RUM Conjecture, EDBT 2016, S. 461–466. https://openproceedings.org/2016/conf/edbt/paper-12.pdf
• Dayan, Athanassoulis, Idreos (2017): Monkey: Optimal Navigable Key-Value Store, SIGMOD 2017 – optimale Bloom-Filter-Zuteilung. https://stratos.seas.harvard.edu/publications/monkey-optimal-navigable-key-value-store
• Dayan, Idreos (2018): Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores, SIGMOD 2018 – lazy leveling. https://nivdayan.github.io/dostoevsky.pdf
• Lu, Sears, Arpaci-Dusseau et al. (2016): WiscKey: Separating Keys from Values in SSD-Conscious Storage, FAST 2016 – Schlüssel-Wert-Trennung. https://pages.cs.wisc.edu/~ll/papers/wisckey_tos.pdf

← All articles