O^3-LSM: Maximizing Disaggregated LSM Write Performance via Three-Layer Offloading

Die Arbeit stellt O³-LSM vor, eine neue Architektur für LSM-basierte Key-Value-Stores in entkoppelten Speichersystemen, die durch dreistufiges Offloading (Memtable, Flush und Compaction) sowie optimierte Lese-Delegierung die Schreibleistung und Abfragegeschwindigkeit im Vergleich zu bestehenden Lösungen signifikant steigert.

Das Wesentliche

Stell dir vor, du betreibst eine riesige, ultra-schnelle Bibliothek in einem modernen Rechenzentrum. Diese Bibliothek ist ein LSM-KVS (ein spezieller Datenspeicher), der darauf ausgelegt ist, Millionen von Büchern (Daten) pro Sekunde zu registrieren und wiederzufinden.

In der herkömmlichen Welt (monolithisch) sitzen die Bibliothekare (Rechner) direkt neben den Regalen (Festplatten). Aber in der modernen Cloud-Welt haben wir uns die Dinge entkoppelt: Die Bibliothekare sitzen in einem Raum, die Regale in einem anderen, und dazwischen gibt es einen riesigen, schnellen Flur (das Netzwerk).

Das Problem: Die Bibliothekare haben nur einen kleinen Schreibtisch (Arbeitsspeicher). Wenn sie zu viele neue Bücher auf einmal bekommen, wird ihr Schreibtisch voll. Sie müssen dann warten, bis sie die Bücher in die Regale (Festplatten) räumen können. Dieser Räumvorgang ist langsam und blockiert alles.

O3-LSM ist eine neue, revolutionäre Idee, um dieses Problem zu lösen. Die Autoren nennen es "Drei-Schichten-Entlastung". Hier ist die Erklärung mit einfachen Analogien:

Das Grundproblem: Der überfüllte Schreibtisch

Stell dir vor, ein Bibliothekar muss neue Bücher sofort notieren. Sein Schreibtisch ist klein. Wenn er voll ist, muss er warten, bis er die Notizen in ein großes Archiv (die Festplatte) schreibt. Das Archiv ist weit weg. Das Warten kostet Zeit, und die Bibliothek wird langsam.

Bisherige Lösungen haben versucht, das Sortieren der alten Bücher in den Regalen (eine Aufgabe namens "Compaction") an einen anderen Raum auszulagern. Aber das löste nicht das Problem des vollen Schreibtisches.

Die Lösung: O3-LSM (Die Drei-Schichten-Strategie)

O3-LSM nutzt einen riesigen, gemeinsamen Zwischenboden (Disaggregated Memory), der sich zwischen dem Schreibtisch und dem Archiv befindet. Dieser Zwischenboden ist riesig, schnell, aber nicht dauerhaft (wie ein Whiteboard).

Hier sind die drei genialen Tricks:

1. Der "Smart-Notizblock" (DM-Optimized Memtable)

Das Problem: Wenn man einen normalen Notizblock vom Schreibtisch auf den Zwischenboden bringt, muss man oft alles neu schreiben, weil die Adressen der Bücher auf dem Zwischenboden anders sind. Das dauert ewig.
Die Lösung: O3-LSM baut den Notizblock so um, dass er "transportfreundlich" ist. Statt komplexer Verweise (wie "Buch liegt links neben dem Fenster") nutzt er einfache Abstände ("Buch liegt 5 Meter nach rechts vom Start").

• Analogie: Statt einen komplizierten Stadtplan mit Straßennamen zu kopieren, schreibt man einfach: "Geh 10 Schritte geradeaus, dann 5 Schritte rechts." Das kann man sofort auf den Zwischenboden übertragen, ohne ihn neu zu zeichnen. Das macht das Verschieben der Daten extrem schnell.

2. Der "Team-Räumungsdienst" (Collaborative Flush Offloading)

Das Problem: Normalerweise muss der Bibliothekar, der die Notizen geschrieben hat, selbst zum Zwischenboden laufen, sie holen und ins Archiv bringen. Das ist ineffizient, wenn er gerade beschäftigt ist.
Die Lösung: O3-LSM hat einen Räumungs-Koordinator. Wenn ein Notizblock voll ist, ruft der Bibliothekar den Koordinator. Der Koordinator schaut sich um: "Wer hat gerade Zeit und Kraft?" Er schickt dann einen anderen Bibliothekar oder sogar einen Roboter auf dem Zwischenboden, der die Notizen direkt vom Zwischenboden ins Archiv bringt.

• Analogie: Stell dir vor, du hast einen vollen Müllsack. Statt ihn selbst zum Müllwagen zu schleppen, rufst du einen Dienst an. Der Dienst schaut, welcher Müllmann gerade nicht beschäftigt ist, holt den Sack von deinem Balkon und bringt ihn weg. Du musst nicht warten.

3. Die "Zerteilte Räumung" (Shard-Level Optimization)

Das Problem: Wenn man einen riesigen Notizblock (64 MB) auf einmal zum Archiv bringt, staut sich der Verkehr im Flur. Zudem müssen die Bücher im Archiv oft neu sortiert werden, was langsam ist.
Die Lösung: O3-LSM zerschneidet den Notizblock in viele kleine Streifen (Shards), basierend auf den Anfangsbuchstaben der Titel (z.B. alle Bücher mit "A" in einem Streifen, "B" in einem anderen).

• Analogie: Statt einen riesigen Lastwagen mit 1000 Paketen zu schicken, der den Verkehr blockiert, schickt man 100 kleine Lieferboten gleichzeitig los. Jeder bringt nur Pakete für einen bestimmten Stadtteil. Im Archiv werden diese Pakete dann direkt in die richtigen Regale gelegt, ohne dass man alles neu sortieren muss. Das verhindert Staus und macht den Räumungsvorgang parallel und schnell.

Das Leseproblem: Der "Schnelle Blick" (Cache-Enhanced Read Delegation)

Wenn jemand ein Buch sucht, muss man oft durch viele Notizblöcke auf dem Zwischenboden schauen. Das ist langsam, weil man jedes Mal zum Zwischenboden rennen muss.

• Die Lösung: O3-LSM hat einen kleinen Spickzettel am Schreibtisch des Bibliothekars. Darauf steht: "Buch X liegt genau an Position Y auf dem Zwischenboden."
  • Wenn der Bibliothekar das Buch sucht, schaut er erst auf den Spickzettel.
  • Treffer (Hit): Er rennt direkt zur genauen Stelle auf dem Zwischenboden und holt das Buch (sehr schnell).
  • Fehlschlag (Miss): Wenn das Buch nicht im Spickzettel steht, schickt er einen Bot zum Zwischenboden, der dort selbst sucht und das Ergebnis zurückbringt.
• Der Clou: Für die häufigsten Bücher (die "Hot Spots") ist der Weg extrem kurz. Für die seltenen Bücher wird die Suche ausgelagert, damit der Bibliothekar nicht selbst den ganzen Zwischenboden durchsuchen muss.

Das Ergebnis

Durch diese drei Tricks (Smart-Notizblock, Team-Räumung, Zerteilte Räumung + Spickzettel) erreicht O3-LSM:

• 4,5-mal schnelleres Schreiben: Die Bibliothekare können viel mehr Bücher pro Sekunde registrieren, ohne zu warten.
• Bis zu 76% weniger Wartezeit: Die schlimmsten Verzögerungen (P99 Latenz) sind fast verschwunden.
• Stabilität: Selbst wenn plötzlich 1000 Leute gleichzeitig Bücher anfordern, staut sich nichts mehr.

Zusammenfassend: O3-LSM verwandelt einen chaotischen, überfüllten Schreibtisch in ein hochorganisiertes, verteiltes System, bei dem Aufgaben intelligent aufgeteilt, Daten in transportfreundliche Pakete verpackt und Suchwege durch kleine Spickzettel optimiert werden. Es ist wie der Unterschied zwischen einem einzelnen, überlasteten Kurier und einem effizienten Logistiknetzwerk.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „O3-LSM: Maximizing Disaggregated LSM Write Performance via Three-Layer Offloading" auf Deutsch:

1. Problemstellung

Log-Structured Merge-Tree-basierte Key-Value-Stores (LSM-KVS) wie RocksDB werden zunehmend in entkoppelten Rechenzentren (Disaggregated Data Centers, DDCs) eingesetzt, um Speicher- und Rechenressourcen unabhängig skalieren zu können. In herkömmlichen, entkoppelten LSM-KVS-Architekturen werden die persistenten Daten (SST-Dateien) auf einem getrennten Speicherpool (Disaggregated Storage, DS) gehalten, während die Schreibpuffer (Memtables) auf den Rechenknoten (Compute Nodes, CNs) verbleiben.

Die bestehenden Optimierungen konzentrieren sich hauptsächlich auf das Offloading von Compaction-Prozessen (das Zusammenführen von SST-Dateien) auf den DS oder andere Knoten, um Netzwerk-I/O zu reduzieren. Dies löst jedoch nicht die fundamentalen Engpässe beim Schreiben:

• Begrenzter Arbeitsspeicher: Rechenknoten haben oft nur wenig RAM, da sie viele Instanzen hosten müssen. Wenn der lokale Schreibpuffer (Memtable) voll ist, müssen neue Schreibvorgänge blockiert werden (Write Stalls), bis Daten in den DS geleert (Flush) werden.
• Langsame Flush-Operationen: Das Übertragen von Memtables über das Netzwerk zum DS ist langsam und verursacht hohe Latenz. Zudem führt das Füllen der Ebene 0 (L0) im LSM-Baum zu sequentiellen Compaction-Prozessen, die weitere Schreibverzögerungen verursachen.
• Ineffiziente Nutzung von Disaggregated Memory (DM): Eine naive Lösung wäre, Memtables in den getrennten Speicher (DM) auszulagern. Dies scheitert jedoch an drei Problemen:
  1. Teure Übertragung: Das Verschieben pointer-basierter Strukturen (wie Skip-Lists) erfordert eine teure Rekonstruktion der Zeiger im DM.
  2. Ineffizientes Flushen: Da DM keine Persistenzlogik hat, müssten Memtables für den Flush zurück zum CN gelesen werden, was zusätzliche Netzwerk-Hops und Overhead verursacht.
  3. Langsame Lesezugriffe: Das Durchsuchen von Memtables im DM über RDMA führt zu hohen Latenzen aufgrund mehrerer Round-Trips.

2. Methodik und Architektur (O3-LSM)

O3-LSM ist eine neue Architektur, die Disaggregated Memory (DM) als dritte Schicht in das LSM-Design integriert. Sie führt ein Drei-Schichten-Offloading ein: Memtable-Offloading, Flush-Offloading und das bestehende Compaction-Offloading.

Die vier Kerninnovationen sind:

A. DM-Optimierte Memtable (DM-Optimized Memtable)

Um die teure Rekonstruktion von Zeigern zu vermeiden, wird die Memtable-Struktur neu gestaltet:

• Trennung von Index und Daten: Die Memtable wird in einen Index-Block (enthält die Skip-List-Struktur mit Zeigern) und einen KV-Block (enthält die Key-Value-Paare sequentiell und zusammenhängend) aufgeteilt.
• Offset-basierte Adressierung: Der KV-Block wird als zusammenhängender Speicherblock übertragen. Die Zeiger im Index-Block zeigen nicht auf absolute Adressen, sondern auf Offsets innerhalb des KV-Blocks.
• Vorteil: Der KV-Block kann direkt per RDMA übertragen werden, ohne Rekonstruktion. Nur der Index-Block muss im DM angepasst werden (Reparatur der Basisadresse), was sehr schnell ist.

B. Kollaboratives Flush-Offloading (Collaborative Flush Offloading)

Dieser Ansatz entkoppelt die Flush-Steuerung von der LSM-Instanz, die die Memtable erstellt hat.

• Protokoll: Ein zentraler Flush-Scheduler weist Flush-Jobs dynamisch jedem Knoten im Cluster zu (lokaler CN, DM-Knoten oder ein anderer CN), der freie Ressourcen hat.
• Ausführungsmodi: Der Flush kann lokal, direkt im DM (In-DM) oder auf einem entfernten CN ausgeführt werden.
• Vorteil: Dies vermeidet, dass der ursprüngliche CN blockiert wird, und nutzt die gesamte Rechenleistung des Clusters für das Erstellen von SST-Dateien, was den Flaschenhals beim Flush beseitigt.

C. Asynchrones Sharding (Asynchronous Sharding)

Um die Parallelität zu maximieren und das Problem der L0-Compaction zu lösen:

• Sharding: Jede Memtable wird in mehrere nicht-überlappende Schlüsselbereiche (Shards) unterteilt.
• Paralleles Übertragen: Diese Shards können asynchron und parallel an den DM übertragen werden, ohne auf das Schließen der gesamten Memtable warten zu müssen.
• Shard-Level Flush: Beim Flush werden Shards mit demselben Schlüsselbereich aus verschiedenen Memtables zusammengeführt. Dies kombiniert den Flush mit der L0-Compaction, reduziert die Anzahl der überlappenden L0-Dateien und ermöglicht paralleles Schreiben.

D. Cache-Erhöhte Lese-Delegation (Cache-Enhanced Read Delegation)

Um die hohe Latenz beim Suchen im DM zu minimieren:

• Lokaler Key-Offset-Cache: Auf dem CN wird ein kleiner Cache für „heiße" Schlüssel gehalten, der die DM-Adresse speichert.
• Adaptive Strategie:
  • Bei einem Cache-Hit wird direkt per einseitigem RDMA_READ (One-sided) auf die Daten im DM zugegriffen (sehr schnell).
  • Bei einem Cache-Miss wird die Suchaufgabe per zweiseitigem RDMA_SEND (Two-sided) an einen Worker im DM delegiert, der die Suche lokal durchführt und das Ergebnis zurücksendet. Dies reduziert die Anzahl der Round-Trips im Vergleich zum manuellen Durchlaufen der Skip-List über das Netzwerk.

3. Wichtige Beiträge

1. Neue Architektur: O3-LSM ist der erste LSM-KVS, der DM als Schreibpuffer-Erweiterung nutzt und dabei die spezifischen Herausforderungen von Pointer-Rekonstruktion und Flush-Logik löst.
2. Datenlayout: Die Einführung des DM-freundlichen Layouts (Index/Data Separation) ermöglicht das direkte Übertragen von Memtables ohne teure Rekonstruktion.
3. Kollaborative Orchestrierung: Das Flush-Offloading-Protokoll mit einem Scheduler, der Ressourcen im gesamten Cluster nutzt, beseitigt Engpässe beim Schreiben.
4. Shard-Level-Optimierung: Die Aufteilung in Shards ermöglicht parallele Transfers und kombiniert Flush mit L0-Compaction, was Write-Stalls drastisch reduziert.
5. Read-Delegation: Eine hybride Lese-Strategie, die lokale Caches und Remote-Suche kombiniert, um Lese-Latenzen im DM zu minimieren.

4. Ergebnisse

Die Evaluation wurde auf CloudLab mit RocksDB v8.2.0 durchgeführt und verglich O3-LSM mit State-of-the-Art-Lösungen wie Disaggregated-RocksDB, CaaS-LSM und Nova-LSM.

• Schreibdurchsatz: O3-LSM erreicht bis zu 4,5-fach höheren Schreibdurchsatz im Vergleich zu den Baselines.
• Leseleistung: Bei Punkt-Abfragen (Point Lookups) wurde eine 1,8-fache Steigerung des Durchsatzes erreicht.
• Bereichsabfragen (Range Queries): Bis zu 5,2-fache Verbesserung des Durchsatzes.
• Latenz: Die P99-Latenz wurde um bis zu 76% reduziert.
• Write Stalls: Die Anzahl der Schreibblockaden (Write Stalls) wurde um bis zu 95% reduziert.
• Real-World-Test: In einem Test mit Kvrocks (Redis-kompatibel) zeigte O3-LSM bis zu 3,4-fach höheren Durchsatz und eine 54% geringere P99-Latenz.
• Skalierbarkeit: O3-LSM skaliert linear mit der Anzahl der Rechenknoten und DM-Knoten und nutzt den geteilten Speicherpool effizient, um Lastspitzen abzufedern.

5. Bedeutung

O3-LSM adressiert eine kritische Lücke in der Architektur entkoppelter Datenbanken. Während frühere Arbeiten sich auf das Offloading von Compaction konzentrierten, zeigt O3-LSM, dass die Nutzung von Disaggregated Memory als Schreibpuffer-Erweiterung möglich ist, wenn die Datenstrukturen und die Orchestrierung (Flush/Scheduling) entsprechend angepasst werden.

Die Arbeit beweist, dass durch die Kombination von spezialisierten Datenlayouts (DM-Optimized Memtable), intelligenter Ressourcenverteilung (Collaborative Flush) und feingranularer Parallelisierung (Sharding) die Leistungsgrenzen von entkoppelten Speichersystemen überwunden werden können. Dies ermöglicht hochperformante, skalierbare Key-Value-Stores in modernen Cloud-Umgebungen, die sowohl hohe Schreiblasten als auch niedrige Latenzen bewältigen können, ohne die Persistenzgarantien zu opfern.