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

Dit artikel introduceert RESYSTANCE, een systeem dat eBPF en io_uring gebruikt om de compaction-proces in LSM-trees direct in de kernel uit te voeren, waardoor het aantal systeemoproepen met 99% wordt verminderd en de doorvoersnelheid in schrijfgewogen workloads tot 75% stijgt.

De kern

🚀 De Probleemstelling: De Snelste Auto met een Trage Chauffeur

Stel je voor dat je een supersnelle raceauto hebt (een moderne NVMe SSD-schijf). Deze auto kan razendsnel rijden, veel sneller dan de wegen vroeger waren. Maar er is een groot probleem: de chauffeur (de software van je computer) is traag en onhandig.

Elke keer als de chauffeur een opdracht moet uitvoeren (bijvoorbeeld: "Haal die data op"), moet hij:

1. Het stuur loslaten.
2. De auto uitstappen.
3. Naar het kantoor van de wegbeheerder (de kernel van het besturingssysteem) lopen.
4. Een formulier invullen (een systeemoproep doen).
5. Teruglopen naar de auto en weer instappen.

Omdat de auto zo snel is, is het wachten op die formulieren en het in- en uitstappen nu de echte rem op de snelheid. De auto staat bijna stil terwijl de chauffeur heen en weer rent.

🏭 Het Specifieke Probleem: De "Schoonmaakploeg"

In databases (zoals RocksDB, die veel wordt gebruikt door apps zoals Facebook of Instagram) wordt data opgeslagen in lagen, net als een stapel boeken. Als je veel schrijft, moet er regelmatig een schoonmaakploeg (de compaction) aan het werk.

Deze ploeg moet:

1. Duizenden kleine blokken data uit verschillende lagen lezen.
2. Ze sorteren en samenvoegen.
3. Ze weer op de schijf zetten.

In het oude systeem doet deze ploeg dit door duizenden keren naar het kantoor van de wegbeheerder te rennen voor elke kleine stap. Het is alsof je een berg boeken moet sorteren, maar elke keer als je één boek oppakt, moet je eerst een vergunning aanvragen bij de burgemeester. Het sorteren zelf gaat snel, maar het wachten op de vergunningen kost eeuwig.

💡 De Oplossing: RESYSTANCE (De "Weerstand" Breken)

De onderzoekers van de Universiteit Sogang hebben RESYSTANCE bedacht. De naam is een woordspeling op "Resistance" (Weerstand). Het doel is om de weerstand van die trage administratie te breken.

Hun oplossing bestaat uit twee slimme trucjes:

1. De "Super-chauffeur" (eBPF)

Ze gebruiken een technologie genaamd eBPF. Stel je dit voor als een super-gecertificeerde stagiair die direct in de wegbeheerder kantoor mag werken, maar die ook mag doen wat de chauffeur doet.

• In plaats dat de chauffeur (de database) buiten het kantoor blijft en steeds formulieren moet invullen, mag deze stagiair direct in het kantoor (de kernel) het werk doen.
• De stagiair is veilig: hij heeft een strenge controleur (de verifier) die kijkt of hij geen gekke dingen doet die de hele wegbeheerder laten crashen.
• Hierdoor hoeft de database niet meer constant het kantoor in en uit te rennen. Alles gebeurt binnen dezelfde muren.

2. De "Express-Post" (io_uring)

Voor het ophalen van de data gebruiken ze io_uring.

• Oude manier: De chauffeur loopt naar de post, pakt één pakketje, loopt terug, en doet dit duizend keer.
• Nieuwe manier: De chauffeur vult één groot formulier in met 100 pakketjes die hij tegelijk wil hebben. De post (de schijf) pakt ze allemaal tegelijk en levert ze in één keer af.
• Dit heet "asynchroon I/O": je vraagt om veel dingen, en je doet ondertussen andere werk, tot ze er zijn.

🛠️ Hoe werkt RESYSTANCE in de praktijk?

Stel je voor dat de schoonmaakploeg (compaction) nu werkt in een gespecialiseerde fabriekshal (de kernel) in plaats van in de open lucht.

1. De Opdracht: De database zegt: "Sorteer deze 1000 boeken."
2. De Aanpak: In plaats van één voor één te rennen, stuurt RESYSTANCE een groot commando naar de fabriekshal.
3. Het Werk: De "super-chauffeur" (eBPF) pakt alle boeken tegelijk op, sorteert ze op een snelle manier (zoals een min-heap of lineair zoeken, afhankelijk van hoeveel boeken er zijn) en legt ze netjes in een nieuwe stapel.
4. Het Resultaat: Omdat ze niet hoeven te rennen naar het kantoor, gaat het sorteren 50% sneller. Ze maken 99% minder administratieve fouten (systeemoproepen).

🏆 De Resultaten: Wat levert het op?

De onderzoekers hebben dit getest met zware taken (alsof je een hele bibliotheek in één keer moet herschikken).

• Snelheid: In situaties waar veel geschreven wordt, is de database tot 75% sneller geworden.
• Wachttijd: De tijd die wachtende gebruikers moeten wachten (de "latency") is met 40% gedaald.
• Geen nieuwe hardware: Je hoeft geen nieuwe, dure schijven te kopen. Het werkt gewoon op je huidige computer, maar dan met een slimme software-update.
• Veiligheid: Omdat het eBPF gebruikt, is het veilig. Het kan de computer niet laten crashen, omdat de strenge controleur alles checkt voordat het werk begint.

🎯 Conclusie in één zin

RESYSTANCE is als het geven van een paspoort aan je database, zodat hij niet meer hoeft te wachten in de rij bij de douane, maar direct door de snelste weg (de kernel) mag reizen om zijn werk te doen. Hierdoor wordt je computer veel sneller, zonder dat je ook maar één schroef hoeft te draaien.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "RESYSTANCE: Unleashing Hidden Performance of Compaction in LSM-trees via eBPF" in het Nederlands.

1. Probleemstelling

De paper identificeert een verschuiving van de I/O-fout in moderne databasesystemen. Door de komst van extreem snelle opslagapparaten (zoals NVMe SSD's) is de hardware niet langer de beperkende factor; de bottleneck is nu verplaatst naar de software-stack, specifiek de overhead van systeemoproepen (system calls) en contextswitchen tussen de gebruikersruimte en de kernelruimte.

Dit probleem is het meest acuut in NoSQL-databases die gebruikmaken van Log-Structured Merge-trees (LSM-trees), zoals RocksDB.

• De Compaction-fase: Tijdens het samenvoegen (compaction) van data-bestanden (SSTables) moet de database duizenden blokken lezen en herschrijven.
• Systeemoproep-explosie: Traditionele implementaties gebruiken een iteratieve aanpak waarbij voor elke data-blok een pread()-systeemoproep wordt gedaan. De analyse toont aan dat compaction verantwoordelijk is voor het overgrote deel van de systeemoproepen (bijvoorbeeld ~67.000 oproepen per operatie in vergelijking met slechts 0,5 voor een 'Put').
• Resultaat: Deze frequente overgangen tussen gebruikers- en kernelruimte veroorzaken significante CPU-overhead en latentie, wat de prestaties van de database beperkt ondanks de hoge snelheid van de onderliggende hardware.

2. Methodologie: RESYSTANCE

RESYSTANCE is een framework dat de kern-I/O-routines van de compaction-fase verplaatst naar de kernelruimte, zonder de bestaande LSM-tree-structuur of -algoritmen te wijzigen. Het combineert twee moderne Linux-technologieën: eBPF (extended Berkeley Packet Filter) en io_uring.

Kerncomponenten en Werkwijze:

1. eBPF voor Merge-Logica: In plaats van dat de gebruikersruimte de data leest en sorteert, wordt de merge-sort-logica (het samenvoegen van sleutels uit meerdere blokken) uitgevoerd door een eBPF-programma dat direct in de kernel draait. Dit elimineert de noodzaak voor contextswitchen tijdens de berekeningen.
2. io_uring voor Asynchrone I/O: RESYSTANCE gebruikt io_uring om asynchrone leesverzoeken voor meerdere data-blokken tegelijkertijd in te dienen. Dit maximaliseert de paralleliteit van de NVMe SSD en vermindert het aantal kernel-toegangspunten.
3. SST-Map: Omdat eBPF geen directe toegang heeft tot de metadata van de SSTables, bouwt de controller een "SST-Map" op in gedeeld geheugen. Deze map bevat de index, offset en grootte van de blokken die moeten worden samengevoegd, en dient als instructieboekje voor het eBPF-programma.
4. Architectuur:
   • De gebruiker vraagt ReadNextKV() aan.
   • De controller gebruikt io_uring om de benodigde blokken asynchroon te laden in de kernel.
   • Het eBPF-programma voert de merge-sort uit op deze data in de kernel en schrijft het resultaat naar een output-buffer.
   • De schrijfbewerking (WriteKV) blijft traditioneel in de gebruikersruimte, omdat schrijfbewerkingen minder frequent zijn en minder systeemoproepen genereren dan lezen.

Ontwerpdoelen en Uitdagingen:

• Veiligheid: eBPF heeft een strenge verifiër die oneindige lussen en ongeldige geheugentoegang verhindert. De auteurs hebben de verifiër aangepast om de instructielimiet te verhogen (van 1 miljoen) en toegang tot specifieke kernel-geheugenregio's toe te staan, zonder de algehele stabiliteit van de kernel te riskeren.
• Minimale Invasiviteit: Het systeem vereist geen herontwerp van de database-engine en geen nieuwe hardware. Het werkt als een laag bovenop de bestaande VFS (Virtual File System).
• Dynamische Algoritmen: Het framework ondersteunt het dynamisch wisselen van merge-algoritmen (bijv. lineair zoeken vs. min-heap) afhankelijk van het aantal bestanden, zonder de database te herstarten.

3. Belangrijkste Bijdragen

• Identificatie van de Bottleneck: Het paper kwantificeert dat compaction de dominante bron van systeemoproep-overhead is in LSM-tree-systemen.
• RESYSTANCE Framework: Een innovatieve implementatie die eBPF en io_uring combineert om de I/O-routes van compaction volledig naar de kernel te verplaatsen.
• Prestatieverbetering zonder Hardware: Het bereikt aanzienlijke prestatiewinst puur via software-optimalisatie, zonder de LSM-tree-architectuur te wijzigen of speciale hardware (zoals FPGA's) te vereisen.
• Open Source Implementatie: De code is beschikbaar voor RocksDB v10.1.3.

4. Resultaten

De evaluatie is uitgevoerd met db bench, YCSB en OLTP-werklasten (via Sysbench op MariaDB/MyRocks) op een server met een AMD Ryzen 9 CPU en een Samsung 990 PRO NVMe SSD.

Kernresultaten vergeleken met de baseline RocksDB:

• Systeemoproepen: Een reductie van 99% in het gemiddelde aantal systeemoproepen tijdens compaction.
• Compaction-tijd: Een verkorting van 50% in de uitvoeringstijd van compaction.
• Throughput:
  • Tot 75% hogere throughput in schrijfgewogen werklasten (FillRandom).
  • 22% hogere throughput in gemengde OLTP-werklasten (read-write).
• Latentie: Een reductie van 40% in de p99-latentie (99e percentiel) bij schrijfgewogen werklasten.
• Vergelijking met Kernel Bypass (SPDK): In tegenstelling tot SPDK (dat de kernel volledig omzeilt), behoudt RESYSTANCE de stabiliteit en functionaliteit van het besturingssysteem (zoals caching en scheduling) terwijl het toch de overhead van systeemoproepen elimineert. SPDK presteerde in deze specifieke compaction-scenario's minder goed door beperkingen in de BlobFS-cache.

5. Betekenis en Impact

RESYSTANCE bewijst dat het mogelijk is om de prestaties van gevestigde databasesystemen aanzienlijk te verbeteren door slimme integratie van kernel-technieken, zonder de complexiteit van volledige kernel-bypass-architecturen.

• Praktische toepasbaarheid: Omdat het geen wijzigingen vereist in de database-engine zelf of in de bestandsystemen, is het gemakkelijker te adopteren dan radicale architecturale veranderingen.
• Toekomstperspectief: Het paper opent de deur voor verdere optimalisaties van I/O-paden in databases via eBPF, waarbij de grens tussen gebruikers- en kernelruimte verder vervaagt voor specifieke, intensieve taken zoals data-migratie en samenvoeging.
• Stabiliteit: Door de beperkingen van de eBPF-verifiër te respecteren en aan te passen, biedt het een veilige route voor performance-verbetering die niet ten koste gaat van de systeemstabiliteit.

Kortom, RESYSTANCE "bevrijdt" de compaction-fase van de beperkingen van traditionele systeemoproepen, waardoor de volle snelheid van moderne NVMe-opslag kan worden benut.