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

Dit paper introduceert O³-LSM, een nieuw LSM-KVS-architectuur die de schrijfprestaties in gedissegeerde opslag maximaliseert door middel van een driedelige offloading-strategie die memtables, flushes en compaction omvat, wat resulteert in aanzienlijke verbeteringen in doorvoersnelheid en latentie ten opzichte van bestaande systemen.

De kern

Stel je voor dat je een enorme bibliotheek beheert waar mensen constant boeken (data) in en uit moeten halen. In de traditionele wereld van databases (zoals LSM-KVS, de technologie achter veel cloud-applicaties), werkt dit als volgt:

1. De Schrijftafel (Memtable): Nieuwe boeken komen eerst op een kleine, snelle schrijftafel in de kantoorruimte (de computer).
2. De Opslag (Disk/Storage): Als de tafel vol zit, moet je de boeken in dozen verpakken en naar een groot, traag magazijn in de kelder sturen.
3. Het Probleem: In de moderne "ontkoppelde" datacenters (waar rekenkracht en opslag los van elkaar staan), is die kelder erg ver weg. Het duurt lang om boeken naar de kelder te brengen. Bovendien is de schrijftafel in het kantoor erg klein. Zodra hij vol zit, moet je wachten tot je de boeken verstuurt voordat je nieuwe boeken kunt ontvangen. Dit zorgt voor een enorme file.

De auteurs van dit paper, O3-LSM, hebben een slimme oplossing bedacht om deze file op te lossen. Ze introduceren een tussenlaag: een gigantische, gedeelde "werkruimte" (Disaggregated Memory) die sneller is dan de kelder, maar iets trager dan de schrijftafel.

Hier is hoe hun oplossing werkt, vertaald naar alledaagse taal:

1. De Drie-Lagen Offloading (Het "Drie-Trapssysteem")

In plaats van alleen de compactering (het sorteren van oude dozen) uit te besteden, doen ze drie dingen tegelijk:

• Lagen 1: De Uitgebreide Schrijftafel (Memtable Offloading)

  • Het probleem: De schrijftafel in het kantoor is te klein.
  • De oplossing: Ze gebruiken de grote, gedeelde werkruimte als een tussenopslag. Zodra de lokale tafel vol is, schuiven ze de boeken niet direct naar de kelder, maar eerst naar deze werkruimte.
  • De slimme truc: Normaal gesproken zou het overbrengen van boeken naar die werkruimte veel tijd kosten omdat de boeken in losse stukjes zitten die opnieuw samengesteld moeten worden. O3-LSM verpakt de boeken in één strakke, rechthoekige doos (een "DM-Optimized Memtable") voordat ze vertrekken. Zo kunnen ze ze razendsnel over de kabels schuiven zonder dat ze in de werkruimte opnieuw hoeven te worden gebouwd.

• Lagen 2: De Slimme Verzenddienst (Collaborative Flush Offloading)

  • Het probleem: Als de boeken in de werkruimte klaar zijn om naar de kelder te gaan, moet het kantoorpersoneel ze weer terugtrekken, inpakken en versturen. Dit kost tijd en blokkeert het kantoor.
  • De oplossing: Ze maken een slimme dispatchdienst. Een centrale "planner" kijkt wie er in het hele gebouw (in de werkruimte of andere kantoren) tijd en kracht heeft om de boeken naar de kelder te brengen.
  • Het resultaat: Het kantoorpersoneel hoeft de boeken niet zelf terug te halen. Iemand anders doet het voor ze, terwijl het kantoor alweer nieuwe boeken kan ontvangen. Dit versnelt het proces enorm.

• Lagen 3: De Deelbare Dozen (Shard-Level Optimization)

  • Het probleem: Als je 100 boeken tegelijk naar de kelder stuurt, ontstaat er een file bij de poort.
  • De oplossing: Ze splitsen de boeken in kleine groepjes (shards) op basis van hun titel (bijv. alle boeken die beginnen met 'A', 'B', 'C'...).
  • Het resultaat: In plaats van één grote vrachtwagen die langzaam rijdt, hebben ze nu 10 kleine bestelbusjes die parallel kunnen rijden. Ze kunnen ook boeken uit verschillende dozen die bij elkaar horen (bijv. alle 'A'-boeken) direct samenvoegen tot één nieuwe doos in de kelder. Dit voorkomt dat de kelder overbelast raakt met rommelige dozen.

2. De "Zoekhulp" (Cache-Enhanced Read Delegation)

Soms moet je een boek uit de werkruimte terugvinden.

• Het oude probleem: Je moet door de hele werkruimte lopen, elk boek controleren. Dat is traag.
• De nieuwe oplossing: Ze hebben een kleine, slimme lijst (cache) bij de poort.
  • Als je een boek zoekt dat vaak wordt gevraagd, staat het adres direct op je lijstje. Je rent er direct naartoe (snel!).
  • Als het niet op de lijst staat, stuur je een boodschapper naar de werkruimte met de vraag: "Zoek dit boek voor mij en stuur het terug." De werkruimte doet het zware zoekwerk, zodat jij niet zelf hoeft te rennen.

Waarom is dit zo belangrijk?

In de testresultaten van het paper zien we dat dit systeem:

• 4,5 keer sneller schrijft dan de huidige beste systemen.
• 5,2 keer sneller is bij het zoeken van reeksen boeken.
• De wachttijden (latency) met 76% verlaagt.

Kortom:
O3-LSM is als het bouwen van een super-efficiënt logistiek systeem voor een bibliotheek. Door de schrijftafel uit te breiden met een slimme tussenlaag, het verzendwerk te delegeren aan de snelste persoon in het gebouw, en de vracht in kleine, parallelle pakketjes te verdelen, wordt de hele bibliotheek veel sneller en rustiger. Het lost het grootste probleem van moderne cloud-databases op: de file die ontstaat als je te veel data te snel wilt opslaan.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "O3-LSM: Maximizing Disaggregated LSM Write Performance via Three-Layer Offloading" in het Nederlands.

Probleemstelling

Log-Structured Merge-tree (LSM) Key-Value Stores (zoals RocksDB) zijn geoptimaliseerd voor schrijfsnelheid, maar in Disaggregated Data Centers (DDC) ontstaan nieuwe knelpunten. In een DDC-architectuur zijn rekenkracht (Compute Nodes, CN), opslag (Disaggregated Storage, DS) en geheugen (Disaggregated Memory, DM) gescheiden.

Bestaande oplossingen voor disaggregated LSM-KVS (zoals Disaggregated-RocksDB, CaaS-LSM) lossen het probleem van schrijfstallingen voornamelijk op door compaction offloading (het samenvoegen van bestanden) naar de opslaglaag of andere knooppunten te verplaatsen. Echter, dit lost de fundamentele beperkingen van de schrijfpad niet op:

1. Beperkt schrijfbuffergeheugen: Compute nodes hebben vaak te weinig RAM om grote memtables (schrijfbuffers) te houden, wat leidt tot frequente flushes.
2. Trage flush-operaties: Het flushen van memtables naar de opslag (DS) via het netwerk is traag en veroorzaakt I/O-concurrentie met andere processen.
3. L0-compaction bottleneck: Als te veel bestanden in het laagste niveau (L0) terechtkomen, moet de database wachten op het samenvoegen hiervan, wat schrijfstallingen veroorzaakt.

Een simpele oplossing zou zijn om memtables naar het gedeelde Disaggregated Memory (DM) te verplaatsen als tijdelijke opslag. Het paper identificeert echter drie kritieke uitdagingen bij deze "naïeve" aanpak:

• Hoge kosten voor verplaatsing en reconstructie: Memtables zijn vaak pointer-gebaseerd (bijv. skip-lists). Het overzetten naar DM en het herbouwen van pointers is traag en kostbaar.
• Inefficiënte flush: Omdat DM geen logische flush-functionaliteit heeft (sorteren, comprimeren, SST-bestanden bouwen), moeten memtables terug naar de CN worden gehaald om te worden geflushed, wat extra netwerktrips en serialisatie-overhead introduceert.
• Trage zoekopdrachten: Het doorzoeken van pointer-gebaseerde memtables in DM via RDMA leidt tot hoge latentie door meerdere round-trips.

Methodologie: O3-LSM Architectuur

O3-LSM introduceert een fundamenteel nieuwe architectuur die drie lagen van offloading combineert om de schrijfprestaties te maximaliseren:

1. Memtable Offloading (naar DM).
2. Flush Offloading (naar willekeurige knooppunten).
3. Compaction Offloading (bestaande techniek).

De kerninnovaties zijn:

1. DM-Optimized Memtable (DM-OT)

Om de kosten van het verplaatsen van pointer-gebaseerde structuren te vermijden, herschrijft O3-LSM de memtable-structuur:

• Scheiding van Index en Data: De memtable wordt opgesplitst in een Index-block (bevat alleen pointers naar de skip-list) en een KV-block (bevat de sleutel-waarde paren in een continu, lineair blok zonder pointers).
• Efficiëntie: Het KV-block kan direct naar DM worden overgedragen zonder reconstructie. Alleen de index moet lokaal worden aangepast met de nieuwe basisadres-offsets van het KV-block in DM. Dit maakt de overdracht een goedkope memcpy-achtige operatie.

2. Collaborative Flush Offloading

In plaats dat de eigenaar van de memtable (de CN) deze terug moet halen om te flushen, wordt het flush-proces gedecoupeerd:

• Flush Scheduler: Een centrale scheduler (of gedistribueerd mechanisme) bewaakt de belasting van alle CN's en DM-knooppunten.
• Dynamische Toewijzing: De scheduler kiest het meest geschikte knooppunt (een andere CN of een DM-knooppunt met voldoende CPU/I/O) om de flush uit te voeren.
• Protocollen: Een lichtgewicht protocol (met fases: Prepare, Assign, Execute, Finalize) zorgt voor de overdracht van metadata en de uitvoering van de flush op het gekozen knooppunt, waardoor de oorspronkelijke CN niet geblokkeerd wordt.

3. Asynchrone Sharding (Shard-Level Optimization)

Om parallelisme te vergroten en de L0-compaction-problematiek op te lossen:

• Sharding: Elke memtable wordt opgesplitst in meerdere niet-overlappende shards op basis van sleutelbereiken (key-ranges).
• Parallelle Transfer: Deze shards kunnen asynchroon en parallel naar DM worden overgedragen.
• Shard-Level Flush: Bij het flushen worden shards met hetzelfde sleutelbereik uit verschillende memtables samengevoegd. Dit combineert het flushen met de L0-compaction, wat resulteert in minder overlappende bestanden in L0 en minder write-stalls.

4. Cache-Enhanced Read Delegation

Om de hoge latentie bij het lezen van memtables in DM te verminderen:

• Key-Offset Cache: Een kleine cache op de CN houdt bij welke sleutels in welke DM-offset zitten.
• Adaptieve Strategie:
  • Cache Hit: Directe ophaal via One-sided RDMA_READ (geen CPU op DM nodig).
  • Cache Miss: De zoekopdracht wordt gedelegeerd naar een worker op de DM via Two-sided RDMA_SEND, waar de DM-CPU de skip-list doorzoekt en het resultaat terugstuurt. Dit vermindert het aantal netwerk-round-trips aanzienlijk.

Kernresultaten

O3-LSM is geïmplementeerd als een fork van RocksDB v8.2.0 en getest op CloudLab tegen state-of-the-art baselines (Disaggregated-RocksDB, CaaS-LSM, Nova-LSM).

• Schrijfsnelheid: Tot 4.5x hogere doorvoer bij willekeurige schrijftaken (Random Write) en tot 76% lagere P99 latentie.
• Leessnelheid: Tot 1.8x hogere doorvoer bij puntzoekopdrachten en 5.2x hogere doorvoer bij bereikzoekopdrachten (Range Queries).
• Real-world Applicatie: In een test met Kvrocks (een Redis-achtige KVS) werd een doorvoerverbetering van 3.4x en een P99-latentiereductie van 54% bereikt.
• Stabiliteit: O3-LSM toont een veel stabielere doorvoer over de tijd zonder de pieken en dalen die bij andere systemen voorkomen door write-stalls.
• Netwerkverkeer: Door het verdelen van flush-taken over meerdere knooppunten en het gebruik van sharding, worden netwerkpieken (bursty traffic) aanzienlijk afgevlakt.

Betekenis en Impact

Dit paper is significant omdat het voor het eerst een complete LSM-KVS-architectuur presenteert die Disaggregated Memory (DM) effectief gebruikt als een uitbreiding van de schrijfbuffer, zonder de prestatie-voordelen van lokale geheugen te verliezen.

• Oplossing voor een hardnekkig probleem: Het adresseert de "write bottleneck" in disaggregated systemen die door eerdere oplossingen (alleen compaction offloading) niet werd opgelost.
• Architecturale Innovatie: De combinatie van een DM-vriendelijke datastructuur, een collaboratief flush-systeem en sharding biedt een blauwdruk voor het optimaliseren van persistente databases in cloud-omgevingen.
• Toekomstbestendigheid: De ontwerpprincipes zijn onafhankelijk van het specifieke interconnect (RDMA of CXL), wat de toepasbaarheid vergroot voor toekomstige datacenter-architecturen.

Kortom, O3-LSM bewijst dat door slimme offloading van memtables, flush-operaties en het gebruik van caching, disaggregated storage systemen niet alleen schaalbaar, maar ook extreem performant kunnen zijn.