Nezha: A Key-Value Separated Distributed Store with Optimized Raft Integration

Dit paper introduceert Nezha, een gedistribueerde key-value opslagsysteem dat door innovatieve integratie van key-value scheiding met Raft en een herontworpen persistence-strategie significante prestatieverbeteringen bereikt terwijl het sterke consistentie garandeert.

De kern

🚀 Nezha: De Slimme Koerier die Dubbelwerk Vermeedt

Stel je voor dat je een gigantisch postkantoor runt (een gedistribueerde opslagsysteem) waar miljoenen mensen brieven (data) in en uit sturen. Om ervoor te zorgen dat niemand een brief kwijtraakt en iedereen dezelfde versie van de waarheid heeft, werken jullie samen met een strikt protocol: Raft.

In de traditionele wereld van dit postkantoor gebeurt er echter iets raars: elke brief wordt drie keer in het archief geplakt voordat hij zelfs maar wordt afgeleverd. Dat is inefficiënt, kost veel tijd en verslijt je papier (schijfruimte) enorm.

Nezha is een nieuw systeem dat dit probleem oplost door slim te werken. Het scheidt de "naam" van de brief van de "inhoud" en zorgt dat alles maar één keer hoeft te worden opgeslagen.

---

1. Het Probleem: De "Drie-Voudige" Bureaucratie 📝📝📝

In een normaal systeem (zoals etcd of TiKV) moet een schrijfbewerking (een Put-request) drie keer naar de harde schijf:

1. De Raft-log: Om te zeggen: "Ik heb deze brief ontvangen en alle collega's zijn het ermee eens."
2. De WAL (Write-Ahead Log): Om te zeggen: "Ik ga deze brief nu in mijn eigen archief zetten."
3. Het Archief zelf: Om de daadwerkelijke data op te slaan.

De Analogie:
Stel je voor dat je een waardevol schilderij (de data) moet opslaan.

• Eerst moet je een kopie maken voor de verzekering (Raft-log).
• Dan moet je een kopie maken voor de administratie (WAL).
• En tenslotte hang je het schilderij op in de muur (Opslag).
  Als het schilderij groot is (grote data), is dit drie keer heen en weer lopen met een zwaar pakketje. Dat is traag en kost veel energie.

2. De Oplossing: Nezha en de "Naam vs. Inhoud" Strategie 🧠✨

Nezha introduceert een concept genaamd Key-Value Separation (Scheiding van Naam en Inhoud).

Hoe werkt het?
In plaats van het hele schilderij drie keer te kopiëren, doet Nezha het volgende:

• De Naam (Key) en een Korte verwijzing (een coördinaat of "offset") worden opgeslagen in het Raft-systeem.
• Het Grote schilderij (Value) wordt maar één keer opgeslagen in een speciaal, langwerpig archief (ValueLog).

De Analogie:
Stel je voor dat je in een bibliotheek bent.

• Oude manier: Je leent een dikke encyclopedie. De bibliothecaris schrijft de titel in drie verschillende boeken, maakt drie kopieën van de titel, en legt het boek pas dan in het rek.
• Nezha manier: De bibliothecaris schrijft alleen de titel en een klein kaartje met het reknummer in het hoofdregister. Het boek zelf ligt al in het rek. Als iemand het boek wil, kijkt hij alleen naar het kaartje en loopt hij direct naar het rek.

Dit betekent dat Nezha de zware data (de inhoud) maar één keer hoeft te schrijven, in plaats van drie keer.

3. Het Nieuwe Uitdaging: De "Vuilnisbak" (Garbage Collection) 🗑️

Er is een klein nadeel aan deze slimme methode. Omdat de inhoud verspreid ligt in het archief (niet netjes op volgorde), kan het zoeken naar een specifiek item soms wat rommelig zijn, alsof je in een grote hoop losse bladen moet zoeken.

Om dit op te lossen, heeft Nezha een slimme vuilnisbak (Garbage Collection of GC) ontwikkeld die begrijpt hoe Raft werkt.

De Analogie:
Stel je voor dat je een lange rol film hebt (de ValueLog) waar nieuwe scènes aan het einde worden toegevoegd. Oude scènes worden soms overschreven of verplaatst.

• Oude systemen: Als je een scène wilt zien, moet je door de hele rol film draaien.
• Nezha: Het systeem heeft een index (een inhoudsopgave). Als je een scène wilt, slaat het systeem eerst een index bij (de "Key").
• Tijdens het opruimen (GC): Soms moet Nezha de film herschikken om ruimte te maken. Normaal zou dit het hele postkantoor stilleggen. Maar Nezha heeft een drie-fasen plan:
  1. Voor het opruimen: Alles gaat naar de oude stapel.
  2. Tijdens het opruimen: Nieuwe brieven gaan naar een nieuwe stapel, terwijl de oude stapel in de achtergrond wordt herschikt. Niemand merkt het verschil!
  3. Na het opruimen: De oude stapel wordt weggegooid en de nieuwe, netjes gesorteerde stapel wordt de nieuwe standaard.

Dit zorgt ervoor dat het systeem altijd beschikbaar blijft, zelfs terwijl het aan het opruimen is.

4. De Resultaten: Waarom is Nezha zo snel? 🚀📈

De onderzoekers hebben Nezha getest en de resultaten zijn indrukwekkend:

• Schrijven (Put): Omdat ze de data maar één keer hoeven te schrijven in plaats van drie keer, is het 460% sneller.
  • Vergelijking: Het is alsof je van een fiets op een Formule 1-auto stapt.
• Lezen (Get): Door de slimme index en de herschikking, is het 12,5% sneller dan traditionele systemen.
• Zoeken (Scan): Als je een groot aantal items achter elkaar wilt lezen, is Nezha 72,6% sneller.
  • Vergelijking: In plaats van door een rommelige zolder te zoeken, loop je Nezha gewoon langs een netjes gesorteerde boekenkast.

Samenvatting in één zin 🌟

Nezha is een slim postkantoor dat de "naam" en de "inhoud" van brieven scheidt, zodat het maar één keer hoeft te werken in plaats van drie keer, en dat tegelijkertijd zorgt dat het nooit stilvalt terwijl het opruimt.

Dit maakt het systeem extreem snel, bespaart veel schijfruimte en zorgt dat grote data-applicaties (zoals e-commerce of AI) veel efficiënter kunnen werken.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "Nezha: A Key-Value Separated Distributed Store with Optimized Raft Integration", geschreven in het Nederlands.

Probleemstelling

Distributed key-value stores (zoals die gebaseerd zijn op LSM-trees en het Raft-consensusprotocol) worden breed ingezet voor grote data-toepassingen. Echter, een kritiek prestatieprobleem is geïdentificeerd: redundante schrijfbewerkingen (I/O-overhead) door de overlap tussen persistentie-operaties van het consensusprotocol en de onderliggende opslag-engine.

In een traditionele Raft-gebaseerde systeem met een LSM-tree-engine moet elke schrijvoperatie minimaal drie keer naar de schijf worden geschreven om consistentie en duurzaamheid te garanderen:

1. Raft Log: Voor het consensusprotocol (waarde en metadata).
2. WAL (Write-Ahead Log) van de opslag-engine: Voor de LSM-tree.
3. Memtable naar SSTable: Tijdens het compaction-proces van de LSM-tree.

Deze "dubbele logging" (of zelfs drievoudige logging) leidt tot aanzienlijke schrijvversterking (write amplification) en vertraagt de systeemrespons, vooral bij grote waarden. Bestaande oplossingen zoals PASV of LSM-Raft lossen slechts een deel van dit probleem op (bijvoorbeeld door de WAL van de opslag-engine te verwijderen of follower-redundantie te verminderen), maar elimineren niet de redundantie op de leader-kant of de volledige keten.

Methodologie: Nezha

Om dit probleem op te lossen, stellen de auteurs Nezha voor, een nieuw gedistribueerd opslagsysteem dat sleutel-waarde scheiding (key-value separation) naadloos integreert met het Raft-protocol. De architectuur bestaat uit drie kerninnovaties:

1. KVS-Raft (Consensuslaag)

In plaats van de volledige waarde te repliceren via Raft en vervolgens in de opslag-engine te schrijven, gebruikt Nezha een aangepast protocol:

• Scheiding: De Raft-log bevat alleen de sleutel en een offset (wijzer) naar de waarde. De daadwerkelijke waarde wordt slechts één keer geschreven in een apart, append-only bestand genaamd ValueLog.
• Staatmachine: De Raft-staatmachine beheert alleen de lichtgewicht offset-mapping (sleutel $\to$ offset), niet de volledige waarde.
• Resultaat: Dit reduceert het aantal schrijfbewerkingen voor een waarde van minimaal drie naar één. De consistentie en veiligheidseigenschappen van Raft blijven intact.

2. Raft-bewust Garbage Collection (GC) Framework (Opslaglaag)

Sleutel-waarde scheiding introduceert een nadeel: leesprestaties (Get/Scan) kunnen verslechteren omdat waarden willekeurig in het ValueLog staan en niet gesorteerd zijn. Nezha lost dit op met een adaptief GC-systeem:

• Drie fasen: Het systeem verdeelt verwerking in Pre-GC, During-GC en Post-GC.
• Modulaire opslag:
  • Active Storage: Bevat ongesorteerde logs (voor nieuwe schrijfs).
  • New Storage: Een tijdelijke module die schrijfs opvangt tijdens GC om beschikbaarheid te garanderen.
  • Final Compacted Storage: Bevat gesorteerde, gecomprimeerde data met een hash-index.
• Dynamische balans: Het GC-proces herschikt verspreide waarden naar gesorteerde bestanden (gebaseerd op sleutels) en bouwt een hash-index op. Dit maximaliseert de leesprestaties voor zowel puntvragen (Point Queries) als bereikvragen (Range Queries) zonder de beschikbaarheid te verstoren.

3. Driefasen Verwerkingsmechanisme

Om correctheid te garanderen tijdens de GC-overgangen, worden lees- en schrijfbewerkingen anders behandeld:

• Schrijven (Put): Is onafhankelijk van de GC-fase; schrijfs gaan altijd naar de huidige actieve module.
• Lezen (Get/Scan): Is GC-bewust. Het systeem voert parallelle zoekopdrachten uit over meerdere opslagmodules (bijv. zowel de oude als de nieuwe data) en merge de resultaten, waarbij de nieuwste versie prioriteit krijgt. Dit zorgt voor consistente leesresultaten tijdens de optimalisatie.

Belangrijkste Bijdragen

1. Identificatie van Bottlenecks: Het paper toont aan dat redundant persistentie tussen consensus en opslag een fundamenteel prestatieprobleem is in moderne hardware-omgevingen.
2. KVS-Raft Protocol: Een nieuw consensusprotocol dat sleutel-waarde scheiding integreert, waardoor schrijvversterking drastisch wordt verminderd terwijl Raft's veiligheidseigenschappen behouden blijven.
3. Raft-aware GC: Een innovatief garbage collection framework dat de leesprestaties van sleutel-waarde gescheiden systemen verbetert door data te sorteren en te indexeren, specifiek ontworpen om in te spelen op de eisen van Raft.
4. Implementatie en Validatie: Een volledige prototype-implementatie in Go met uitgebreide experimentele evaluaties.

Resultaten

Experimentele resultaten tonen aanzienlijke prestatiewinsten ten opzichte van traditionele Raft-systemen (zoals RocksDB + Raft) en andere state-of-the-art oplossingen (PASV, LSM-Raft, TiKV):

• Schrijfprestaties (Put): Een gemiddelde doorvoerverhoging van 460,2%. Dit komt door het elimineren van de dubbele/triple schrijfbewerkingen.
• Leesprestaties (Get): Een gemiddelde doorvoerverhoging van 12,5%. Dit is opmerkelijk omdat sleutel-waarde scheiding normaal gesproken leesprestaties verlaagt; Nezha compenseert dit door de GC-mechanismen.
• Scan-prestaties (Range Queries): Een gemiddelde doorvoerverhoging van 72,6%. De gesorteerde datastructuur na GC maakt sequentiële I/O mogelijk, wat essentieel is voor bereikvragen.
• Schaalbaarheid: Nezha behoudt zijn prestatievoordeel bij toenemende clustergroottes (3 tot 7 knopen) en toont betere schaalbaarheid dan concurrenten.
• Hersteltijd: Door het gebruik van lichtgewicht offsets in de staatmachine is de hersteltijd na een crash 32-35% sneller dan in traditionele systemen.

Betekenis

Nezha vertegenwoordigt een paradigmaverschuiving in het ontwerp van gedistribueerde opslagsystemen. In plaats van consensus en opslag als losse lagen te behandelen, demonstreert het paper dat een co-design (samenwerking) tussen het consensusprotocol en de opslag-engine leidt tot radicale prestatieverbeteringen.

De belangrijkste implicaties zijn:

• Efficiëntie: Het elimineert de noodzaak voor redundante schrijfbewerkingen, wat direct leidt tot lagere kosten (minder I/O op NVMe SSD's) en hogere doorvoer.
• Veiligheid: Het bewijst dat agressieve optimalisaties (zoals het verwijderen van de WAL van de opslag-engine en het samenvoegen met Raft) veilig kunnen worden uitgevoerd zonder de garanties van het consensusprotocol te schenden.
• Toekomstbestendigheid: De architectuur is schaalbaar en geschikt voor cloud-native omgevingen waar kosten per opslag- en schrijfbewerking een kritieke factor zijn.

Kortom, Nezha biedt een robuuste oplossing voor het fundamentele dilemma tussen hoge consistentie en hoge prestaties in gedistribueerde key-value stores.