RESYSTANCE: Unleashing Hidden Performance of Compaction in LSM-trees via eBPF

Die Arbeit stellt RESYSTANCE vor, ein System, das mithilfe von eBPF und io_uring den Software-Overhead bei der Compaktion in LSM-Bäumen reduziert, indem es I/O-Operationen direkt im Kernel ausführt, was zu einer drastischen Verringerung der Systemaufrufe und einer signifikanten Steigerung des Durchsatzes sowie einer Senkung der Latenz führt.

Das Wesentliche

Stell dir vor, dein Computer ist wie eine riesige, hochmoderne Bibliothek. In dieser Bibliothek gibt es einen besonders schnellen, aber etwas chaotischen Helfer: den LSM-Baum.

Das Problem: Der überarbeitete Bibliothekar

Normalerweise funktioniert es so: Wenn du ein neues Buch (Daten) ablegst, wirft der Helfer es erst in einen Korb auf dem Schreibtisch (Arbeitsspeicher). Wenn der Korb voll ist, trägt er die Bücher in Reihen auf den Regalen (Festplatte) ab. Das geht schnell, weil er viele Bücher auf einmal trägt.

Aber hier kommt das Problem: Irgendwann sind die Regale so voll, dass der Helfer anfangen muss, alte Bücher aus den unteren Reihen zu holen, sie mit neuen zu mischen, neu zu sortieren und wieder zurückzustellen. Dieser Prozess heißt Komprimierung (Compaction).

In der alten Welt (die normale Datenbank) muss dieser Helfer für jedes einzelne Buch, das er vom Regal holt, erst zur Tür laufen, den Pförtner (den Betriebssystem-Kernel) fragen: "Darf ich das Buch holen?", warten, das Buch nehmen, zur Tür zurücklaufen, und dann wieder zum Regal.

Da moderne Festplatten (NVMe SSDs) so unglaublich schnell sind (wie ein Hochgeschwindigkeitszug), verbringt der Helfer fast seine gesamte Zeit nicht mit dem Sortieren der Bücher, sondern mit dem Laufen zur Tür und Warten auf den Pförtner. Das ist wie ein Rennfahrer, der 90% der Zeit im Stau steht, weil er an jeder Ampel den Führerschein vorzeigen muss.

Die Lösung: RESYSTANCE – Der geheime Tunnel

Die Forscher von der Sogang-Universität haben eine Lösung namens RESYSTANCE entwickelt. Stell dir vor, sie bauen einen geheimen Tunnel direkt vom Schreibtisch des Helfers ins Regal, der den Pförtner umgeht.

Hier ist, wie sie das gemacht haben, mit ein paar einfachen Vergleichen:

1. eBPF (Der magische Roboter):
   Normalerweise muss der Helfer (die Datenbank) immer mit dem Betriebssystem reden. RESYSTANCE nutzt eine Technologie namens eBPF. Stell dir eBPF wie einen kleinen, super-sicheren Roboter vor, den du direkt in die Bibliothek (den Kernel) stellst. Dieser Roboter darf bestimmte Aufgaben übernehmen, ohne dass der Chef (der Kernel) Angst haben muss, dass er die Bibliothek in die Luft sprengt. Er ist sicher, weil er von einem strengen Prüfer (dem Verifier) kontrolliert wird.

2. io_uring (Der Express-Lieferdienst):
   Statt dass der Helfer jedes Buch einzeln holt, nutzt RESYSTANCE io_uring. Stell dir das wie einen Lieferdienst vor, bei dem du einen ganzen Stapel von "Hole-Bücher"-Aufträgen auf einen Zettel schreibst und dem Roboter gibst. Der Roboter holt dann alle Bücher auf einmal und bringt sie zurück, bevor du überhaupt merkst, dass er los war. Das spart enorm viel Zeit.

3. Der große Trick:
   RESYSTANCE nimmt die mühsame Aufgabe des "Bücher-Holens und Sortierens" und gibt sie dem Roboter (eBPF) im Inneren der Bibliothek. Der Roboter holt die Bücher, sortiert sie und legt sie bereit. Der ursprüngliche Helfer muss nur noch die fertigen Stapel abholen.

   • Ergebnis: Der Helfer muss nicht mehr zur Tür laufen. Die "Tür-Transaktionen" (Systemaufrufe) werden um 99% reduziert.

Was bringt das?

• Geschwindigkeit: Da der Helfer nicht mehr auf den Pförtner warten muss, kann er seine eigentliche Arbeit (das Sortieren) viel schneller erledigen. In Tests war die Datenbank bis zu 75% schneller beim Schreiben von Daten.
• Weniger Wartezeit: Wenn du eine Datenbank benutzt, die viele Schreibvorgänge hat (wie eine Bank oder ein Online-Shop), warten die Kunden nicht mehr so lange. Die Antwortzeiten werden um bis zu 40% kürzer.
• Kein Umbau nötig: Das Schönste ist: Man muss die Bibliothek nicht komplett neu bauen. Man braucht keine neuen teuren Maschinen. Man stellt einfach den Roboter (eBPF) und den Express-Lieferdienst (io_uring) auf und fertig.

Zusammenfassung

Stell dir vor, du hast einen extrem schnellen Sportwagen (die neue Festplatte), aber du fährst in einem Dorf, in dem du an jeder Kreuzung anhalten und einen Stempel holen musst (das Betriebssystem).

RESYSTANCE ist wie eine neue Straße, die alle Kreuzungen umgeht. Der Sportwagen kann jetzt seine volle Geschwindigkeit entfalten, ohne vom Stempelholen aufgehalten zu werden. Die Datenbank wird dadurch nicht nur schneller, sondern auch effizienter, weil sie weniger Energie für das "Laufen zur Tür" verschwendet.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „RESYSTANCE: Unleashing Hidden Performance of Compaction in LSM-trees via eBPF" auf Deutsch:

1. Problemstellung

Mit dem Aufkommen ultraschneller Speichergeräte wie NVMe-SSDs hat sich der primäre Engpass bei I/O-Operationen von der Hardware auf die Software verschoben. Moderne Datenbanksysteme, insbesondere NoSQL-Datenbanken, die auf Log-Structured Merge-Trees (LSM-Trees) basieren (z. B. RocksDB, LevelDB), leiden unter erheblichen Software-Overheads.

• Der Flaschenhals: Der Hintergrundprozess der Compaction (das Zusammenführen und Sortieren von Datenblöcken auf der Festplatte) ist der Hauptverursacher für Systemaufrufe (System Calls).
• Die Ursache: Bei der Compaction werden Tausende von SSTable-Blöcken sequenziell gelesen und geschrieben. Jeder Lesevorgang eines Datenblocks erfordert einen pread()-Systemaufruf.
• Die Konsequenz: Diese häufigen Übergänge zwischen Benutzer- und Kernelraum (User-Kernel Transitions) sowie die damit verbundenen Kontextwechsel und Datenkopien verbrauchen wertvolle CPU-Zyklen. Auf modernen NVMe-Laufwerken übersteigt die Latenz des Software-Stacks (Kernel, Treiber, Dateisystem) oft die reine Hardware-Latenz.
• Grenzen bestehender Lösungen: Ansätze wie Kernel-Bypass (z. B. SPDK) umgehen zwar den Kernel, erfordern jedoch eine komplette Neugestaltung des I/O-Subsystems und sind für etablierte Datenbanksysteme oft zu invasiv und wartungsintensiv.

2. Methodik: RESYSTANCE

Die Autoren schlagen RESYSTANCE vor, ein Framework, das die Compaction-Logik von Systemaufrufen befreit, indem es eBPF (extended Berkeley Packet Filter) und io_uring nutzt, ohne die LSM-Tree-Struktur oder den Compaction-Algorithmus zu ändern.

• Kernidee: Die I/O-Routinen der Compaction werden in den Kernel ausgelagert. Anstatt dass der User-Space für jeden Datenblock einen Systemaufruf tätigt, werden die Operationen im Kernel ausgeführt.
• Architektur-Komponenten:
  1. Controller: Ein Benutzermodul, das Metadaten über die zu kompaktierenden SSTables in eine gemeinsame Speicherstruktur (SST-Map) lädt.
  2. io_uring: Wird genutzt, um asynchrone Leseanforderungen für mehrere Datenblöcke parallel und in einem Batch zu stellen. Dies eliminiert die Notwendigkeit, für jeden Block einen separaten Systemaufruf zu tätigen.
  3. eBPF-Programm: Ein im Kernel verifiziertes Programm, das an einem Hook-Punkt (innerhalb des I/O-Pfads) angehängt wird. Es führt das eigentliche Merge-Sort der gelesenen Datenblöcke direkt im Kernel durch.
• Workflow:
  1. Der Compaction-Iterator ruft ReadNextKV auf.
  2. Der Controller nutzt io_uring, um asynchron die benötigten Datenblöcke aus den SSTables in den Kernel-Speicher zu laden.
  3. Das eBPF-Programm sortiert die Schlüssel-Wert-Paare der geladenen Blöcke (Merge-Sort) und schreibt das Ergebnis in einen Kernel-Puffer.
  4. Der gefüllte Puffer wird über Shared Memory zurück an den User-Space gegeben.
  5. Der User-Space führt den Schreibvorgang (WriteKV) über den konventionellen Pfad aus (da Schreibvorgänge seltener und granularer sind, ist der Gewinn hier geringer).
• Design-Entscheidungen:
  • Nur der Merge-Schritt wird in eBPF ausgelagert, um die Komplexität und das Risiko von Verifizierungsfehlern zu minimieren.
  • Die eBPF-Verifizierungsregeln wurden angepasst (z. B. Erhöhung der Instruktionsobergrenze), um komplexe Merge-Logik zuzulassen, ohne die Systemsicherheit zu gefährden.
  • Es werden zwei Algorithmen für die Schlüsselsuche unterstützt: Lineare Suche (für wenige Dateien) und Min-Heap (für viele Dateien), je nach Anzahl der Eingabedateien.

3. Schlüsselbeiträge

• Identifikation des Problems: Nachweis, dass die Compaction in LSM-Trees die dominierende Quelle für Systemaufruf-Overhead ist (insbesondere pread()).
• Innovatives Framework: Entwicklung von RESYSTANCE, das eBPF und io_uring kombiniert, um den I/O-Pfad der Compaction in den Kernel zu verlagern.
• Nicht-invasiv: Die Lösung erfordert keine Änderungen am LSM-Tree-Algorithmus, keine Hardware-Modifikationen und keine tiefgreifenden Kernel-Änderungen (außer minimalen Anpassungen für eBPF-Hooks).
• Dynamische Anpassbarkeit: Da die Logik in eBPF injiziert wird, können Merge-Strategien zur Laufzeit geändert werden, ohne den Datenbank-Server neu zu starten.

4. Ergebnisse

Die Evaluation erfolgte mit RocksDB v10.1.3 unter Verwendung von db_bench, YCSB und OLTP-Workloads (Sysbench).

• Reduktion von Systemaufrufen: Die durchschnittliche Anzahl der Systemaufrufe während der Compaction wurde um 99 % reduziert.
• Compaction-Latenz: Die Compaction-Zeit verkürzte sich um 50 %.
• Durchsatz (Throughput):
  • Bei write-lastigen Workloads (z. B. FillRandom) stieg der Durchsatz um bis zu 75 %.
  • Bei gemischten OLTP-Workloads (Read-Write) wurde eine Steigerung von 22 % erreicht.
• Latenz (Latency): Die p99-Latenz (99. Perzentil) wurde um 40 % reduziert, was insbesondere bei Schreib-Stalls (Write Stalls) kritisch ist.
• Vergleich mit Kernel-Bypass: Im Gegensatz zu SPDK (Kernel-Bypass) bietet RESYSTANCE eine höhere Praktikabilität, da es das bestehende Dateisystem und den Kernel-Stack nutzt, ohne die Kompatibilität zu verlieren.

5. Bedeutung und Fazit

RESYSTANCE demonstriert, dass die Performance-Grenzen moderner Speichersysteme nicht mehr durch die Hardware, sondern durch den Software-Stack definiert werden. Durch die intelligente Nutzung von eBPF und io_uring gelingt es, den Overhead der Systemaufrufe bei der Compaction drastisch zu senken, ohne die Architektur bestehender Datenbanksysteme zu zerstören.

Dieser Ansatz bietet einen nicht-invasiven Weg, um die volle Leistungsfähigkeit von NVMe-SSDs auch für komplexe Datenbank-Operationen nutzbar zu machen. Er stellt einen wichtigen Schritt dar, um die Lücke zwischen extrem schneller Hardware und ineffizienten Software-Interfaces zu schließen, und zeigt das Potenzial von eBPF als Werkzeug zur Optimierung von I/O-intensiven Kernel-Aufgaben.