Elke snelle write-operatie verplaatst het werk naar een andere plek

Deze keuzes koppelen latentie direct aan duurzaamheid. Bevestigen na het kopiëren naar het geheugen is snel, maar bij een crash van de machine gaat de data verloren. Wachten op een lokale SSD overleeft een proces- of kernelcrash, maar niet het verlies van het apparaat of de host zelf. Remote storage of meerdere databaseservers kunnen meer storingen overleven, maar voegen netwerkverkeer en kopieertijd toe aan elke schrijfactie.

Sommige systemen wachten bij fdatasync() op één SSD die is aangesloten op de database-host, terwijl andere een netwerkvolume presenteren via dezelfde NVMe-interface en wachten op een remote storage service. De naam van de syscall is hetzelfde, maar de latentie en de fouten die de data overleeft, verschillen fundamenteel.

Nieuwere storage-ontwerpen rondom object storage maken deze keuze bijzonder interessant. Veel van deze systemen plaatsen onveranderlijke (immutable) gesorteerde bestanden in object storage, gebruiken een lokale NVMe SSD voor een write-ahead log (WAL) of cache, en organiseren data met een log-structured merge tree (LSM) layout. Object storage is een fantastische bouwsteen omdat de storage service verantwoordelijk is voor de duurzame kopieën, terwijl de compute-laag kan komen en gaan. Bovendien voorkomt het schrijven van nieuwe immutable bestanden dat er kleine, willekeurige updates moeten worden gedaan op gedeelde disk-pagina's.

Na een succesvolle object PUT is de storage service verantwoordelijk voor de beloofde duurzaamheid van die bytes. De database moet echter nog steeds beslissen welke versie actueel is, deze beslissing vastleggen zodat andere machines dit kunnen zien, leesacties versnellen, oude versies verwijderen en herstellen na een crash. Een lokale write-ahead log kan schrijfacties versnellen, maar dan moet de database bepalen of het verlies van die lokale kopie acceptabel is, of dat er eerst een andere kopie moet bestaan voordat succes wordt gemeld.

In deze context gebruik ik 'client PUT' voor het key-value request naar de database, en 'object PUT' voor het HTTP-request naar de object storage. Door deze writes strikt te scheiden, is het makkelijker om één client PUT te volgen door het geheugen, een lokale SSD, remote storage en een duurzame meerderheid van databaseservers. Wanneer ik een zeer lage latentie zie bij een operatie, wil ik weten welke andere operatie daarvoor 'betaalt', wat er nog verloren kan gaan na bevestiging, en hoeveel onafgeronde opschoonwerkzaamheden het systeem kan tolereren.

Voor een append-only key-value store hanteer ik de volgende kostenstructuur:

Operatie	Werk voor bevestiging (success)
GET	O(key bytes + returned bytes), 1 index lookup en 1 read voor de waarde.
PUT	O(key bytes + payload bytes), 1 pass over de payload voor hashing, 1 WAL append, en 1 fdatasync() gedeeld met andere writes.
DELETE	O(key bytes), voeg 1 delete-record toe.

Deze kosten zijn aantrekkelijk omdat een normaal request nooit elk bewaard object scant of de volledige write-historie doorloopt, en omdat een grotere waarde logischerwijs meer kost dan een kleinere waarde. Deze lage kosten zijn mogelijk omdat een index elke key direct koppelt aan de nieuwste waarde (voor GET), meerdere PUT-requests één device flush kunnen delen, en DELETE simpelweg vastlegt dat een waarde 'dood' is zonder de oude bytes direct te verwijderen. De PUT is de plek waar het beste te zien is hoe dit werk wordt verplaatst.

Hoe een client PUT een lokale SSD bereikt

Hier gaat het om een host-lokale NVMe SSD, die direct aan dezelfde host als de database is gekoppeld en niet via een remote storage service wordt bereikt. Zodra een write is gesynchroniseerd, overleeft deze een proces- of kernelcrash, maar het verlies van de SSD of de host kan de data nog steeds vernietigen.

NVMe definieert de interface voor commando's naar een apparaat, maar zegt niets over waar de storage zich bevindt of welke fouten de data overleeft. Een remote block volume kan namelijk ook verschijnen als een NVMe-apparaat, ook al gaat elke write over een netwerk. Een latentiecijfer voor NVMe is incompleet zonder het bevestigingspunt: stopte de timer na het kopiëren naar het geheugen, na synchronisatie van één lokale SSD, of nadat een remote volume de write bevestigde?

Een lokale WAL is verleidelijk vanwege het grote verschil in latentie. Terwijl een remote object PUT enkele milliseconden kan duren, kan een lokale fdatasync() op 1 ms of zelfs 0,1 ms zitten. Dit kan een factor 50 tot 64 sneller zijn. Hoewel dit een reëel benchmarkresultaat is, is het geen eigenschap van elk NVMe-apparaat en overleven de twee paden verschillende soorten storingen.

De lokale write scheidt het kopiëren van bytes naar het geheugen van het duurzaam maken ervan. Een write-ahead log (WAL) is een geordend register van wijzigingen dat de database na een crash kan herhalen (replay). In een gebufferde implementatie verloopt een client PUT als volgt:

1. De client PUT komt binnen bij de storage engine.
2. De storage engine schrijft naar de kernel page cache. (Op dit punt kan write() al terugkeren, maar de data is nog niet duurzaam).
3. Via fdatasync() worden pagina's weggeschreven en wordt de device cache geflusht naar de host-lokale SSD.
4. Pas nu wordt succes teruggestuurd naar de client.

Op Linux kopieert write() bytes meestal naar de page cache; de kernel markeert deze pagina's als 'dirty' en schrijft ze later naar het apparaat. Een procesexit wist de page cache niet, maar een kernelcrash of machineverlies wel.

fdatasync() wacht op de bestandsdata en de metadata die nodig is om deze terug te vinden. fsync() flusht daarnaast ook andere metadata van het bestand. Het aanmaken of hernoemen van een bestand kan betekenen dat de directory gesynchroniseerd moet worden, omdat de inhoud en de directory-entry aparte schrijfacties zijn.

ODIRECT en iouring veranderen dit duurzaamheidspunt niet. ODIRECT omzeilt de page cache en iouring maakt I/O efficiënter, maar geen van beide maakt een niet-gesynchroniseerde write plotseling duurzame data. De filesystem en het apparaat moeten nog steeds de writes en flushes voltooien voordat de API kan bevestigen dat de data een crash overleeft.

Er is altijd een risico dat fdatasync() vlak voor het verbreken van de verbinding klaar is: de WAL is committed, maar de client ontvangt nooit de bevestiging. De client kan een operatie-ID meesturen met de PUT en bij een retry hetzelfde ID gebruiken om het resultaat op te vragen. Snellere hardware verkort dit window, maar verwijdert de ambiguïteit niet.

Eén flush kan meerdere schrijfacties dekken

Het aanroepen van fdatasync() na elke kleine client PUT is eenvoudig te begrijpen, maar de doorvoer wordt dan beperkt door het aantal flushes dat het apparaat kan verwerken. Een seriële flush van 1 ms staat ongeveer 1.000 flushes per seconde toe, zelfs als het apparaat veel meer bytes zou kunnen streamen.

De WAL-writer kan een dure flush delen door records in een huidige batch te plaatsen en deze te sluiten na een vast aantal bytes, writes of tijdseenheden. Het systeem onthoudt de laatste byte in die batch, roept fdatasync() aan op het WAL-bestand, en bevestigt vervolgens succes aan alle writers binnen die positie. Writes die na het sluiten van de batch arriveren, wachten op de volgende flush.

Door flushes te delen, blijft de duurzaamheid gelijk (de writes overleven dezelfde fouten), maar verbetert de doorvoer. Er zijn echter trade-offs: de eerste request in een batch wacht het langst, een flush-fout doet de hele batch falen, en een timed-out request kan bytes bevatten die later alsnog op disk terechtkomen.

Ook moet er een limiet komen aan de queue van wachtende writes; anders kan een traag apparaat ervoor zorgen dat alle beschikbare memory wordt geconsumeerd. Bij hoge belasting vult een batch vaak natuurlijk terwijl de vorige flush nog loopt, waardoor extra wachten (om meer writes te verzamelen) latentie toevoegt zonder de doorvoer te verbeteren.

Schrijfacties buiten de database-host behouden

Bevestigen na een lokale fdatasync() haalt het request uit de tijd die de client moet wachten, maar verandert de betekenis van 'succes'. De nieuwste duurzame WAL-records bestaan nu op slechts één SSD in één database-host. Als die host verdwijnt voordat de records zijn geüpload, kan een vervangende node alleen de oudere remote kopie herstellen.

De database is nu stateful. Een scheduler kan de database niet zomaar naar een andere machine verplaatsen en ervan uitgaan dat alle bevestigde writes daar aanwezig zijn. Het systeem moet de SSD beschikbaar houden, een window van dataverlies accepteren, of een extra duurzame kopie maken vóór bevestiging.

De verschillende opties voor duurzaamheid hebben elk een ander impact op de latentie:

Bevestiging wacht op	Latentie bevat	Overleeft
Kopie naar page cache	Geheugenkopie	Proces-exit, maar geen kernelcrash of machineverlies.
fdatasync() naar lokale SSD	SSD write en cache flush	Proces- en kernelcrash, maar geen SSD- of hostverlies.
fdatasync() naar duurzaam netwerkvolume	Netwerk + kopieën door volume service	Verlies van database-host; verdere dekking afhankelijk van de service.
Succesvolle object PUT	HTTP request + kopieën door object service	Verlies van writer en host; verdere dekking afhankelijk van de service.
Duurzame WAL append op 2 van 3 servers	Netwerktransfer + disk sync op 2 servers	Verlies van 1 server, maar niet permanent verlies van 2 servers voor reparatie.

Bij object storage kan een service kopieën bewaren in één failure domain of deze verspreiden over meerdere domeinen. Beiden zijn remote object writes, maar ze overleven niet dezelfde outages. Een lokale WAL toevoegen creëert een nieuwe keuze: bevestigen na de lokale SSD write en de upload later doen, of wachten tot de object PUT is voltooid.

Het uitstellen van de upload houdt het schrijfpad kort, maar betekent dat bij verlies van de lokale SSD alle records na de laatste upload verloren gaan. De leeftijd van het oudste record dat wacht op upload bepaalt hoeveel recente data er risico loopt. Het voltooien van de object PUT vóór bevestiging sluit dit window, maar voegt de remote request-tijd toe aan elke write.

Batching vermindert het aantal requests, maar verandert niets aan wat er gebeurt als twee writers hetzelfde object updaten. Op S3 worden conditionele writes (zoals If-None-Match of If-Match) gebruikt om race-conditions te beheren.

Het repliceren van de WAL voegt coördinatie toe

Een gerepliceerde WAL transformeert één stateful host in bijvoorbeeld drie. Een client stuurt een PUT naar de leader, die de entry lokaal toevoegt en deze doorstuurt naar twee followers. Succes wordt teruggestuurd zodra de leader en één follower de write hebben gesynchroniseerd; de schrijfactie overleeft zo het verlies van één server. Vergeleken met een lokale SSD bevat elke commit nu een netwerktrip en een tweede device sync.

De servers moeten ook beslissen wie mag schrijven en welke writes zijn gecommit. Coördinatie kan extern gebeuren (een service die een writer aanwijst met een volgnummer), maar consensus-algoritmen zoals Raft integreren dit in de storage engine zelf. In Raft registreert de leader de huidige term en de positie in de log, en commit de write zodra een meerderheid deze op disk heeft bewaard.

Een veelvoorkomende shortcut is om followers te laten bevestigen vanuit het RAM. Dit is sneller, maar minder duurzaam: als machines samen herstarten of stroom verliezen, kunnen kopieën verdwijnen terwijl de client al 'succes' zag. Bovendien brengt replicatie extra verantwoordelijkheden met zich mee: leader elections, het repareren van logs na falen, en het monitoren van replicatie-delay. Geen van dit werk is zichtbaar in de latentie van een enkele, gezonde write.

Snelle leesacties vereisen een index en opschoning

Het kunnen herhalen van de WAL na een crash maakt een GET niet automatisch goedkoop. Het scannen van de volledige WAL voor elke read zou betekenen dat de kosten groeien met de historie. Daarom houdt de engine een aparte lookup bij van elke key naar de nieuwste waarde of disk-locatie.

De complexiteit $\text{O}(\text{key bytes} + \text{returned bytes})$ gaat ervan uit dat de engine al weet waar de huidige waarde staat:

• Hash index: Snelle lookup, maar geen volgorde.
• B-tree: Ondersteunt geordende reads en range scans, maar voegt werk toe naarmate de boom hoger wordt (page updates, splits).
• LSM (Log-Structured Merge tree): Schrijft recente keys in het geheugen en gesorteerde bestanden, om deze later samen te voegen (merge) en opnieuw te schrijven.

Een LSM en multi-version concurrency control (MVCC) kunnen samen bestaan. De LSM regelt hoe keys door het geheugen en bestanden bewegen; MVCC regelt welke versies zichtbaar zijn voor readers en writers. Beide algoritmen laten 'oude' bytes achter na een logische delete of vervanging. Een $\text{O}(\text{key bytes})$ delete kan simpelweg een record toevoegen, maar het daadwerkelijk vrijmaken van de oude waarde vereist later zwaar werk: indexen lezen, actuele waarden kopiëren naar nieuwe bestanden en oude bestanden verwijderen.

Big O toont groei, niet de latentie van duurzaamheid

Een client PUT blijft $\text{O}(\text{key bytes} + \text{payload bytes})$, ongeacht of deze stopt bij een lokale SSD, een object service of een meerderheid van servers. Big O vertelt ons hoe het werk groeit als de key of waarde groter wordt, maar het maskeert het verschil tussen een device flush, een remote HTTP-request en een netwerk roundtrip met twee device flushes.

Request path	Groei (Big O)	Werk dat Big O maskeert
PUT naar lokale WAL	$\text{O}(\text{key bytes} + \text{payload bytes})$	1 WAL append en een deel van 1 lokale fdatasync().
PUT naar object storage	$\text{O}(\text{key bytes} + \text{payload bytes})$	Netwerk roundtrip en bevestiging door de service (gedeeld bij batching).
PUT naar gerepliceerde WAL	$\text{O}(\text{key bytes} + \text{payload bytes})$	Netwerktransfer en duurzame WAL append op een meerderheid van servers.

Voor GET en DELETE sluiten deze bounds uit dat er tijdens een normale read elk object wordt gelist of de volledige WAL wordt gereplayd. Ze zeggen echter niets over of het vaste werk microseconden of milliseconden duurt. Daarom moet een latentieresultaat altijd vergezeld gaan van het bevestigingspunt en het percentiel.

Ook het uitgestelde werk heeft limieten nodig. Een WAL-bestand heeft een maximale grootte, en opschoonprocessen hebben byte-limieten nodig zodat ze na een crash kunnen hervatten. Zonder deze limieten maskeert de "goedkope" request-path simpelweg een queue die oneindig blijft groeien.

LLM's maken het makkelijker om de uploader of de cleanup loop te schrijven, maar ze beslissen niet hoeveel onafgerond werk een systeem mag bewaren of wanneer writes vertraagd moeten worden. De beslissingen over wanneer succes veilig is om terug te sturen en wat een timeout betekent, moeten nog steeds handmatig worden ontworpen en getest rondom fdatasync(), het actueel maken van objecten en het kopiëren van writes naar een meerderheid van servers.

Het volgen van de write-flow maakt de trade-offs inzichtelijk: het snellere pad stopt na minder werk en overleeft minder fouten, terwijl het verschuiven van de bevestiging naar een later moment meer duurzaamheid koopt, maar de database verantwoordelijk maakt voor coördinatie, reparatie en opschoning. Cijfers voor GET, PUT en DELETE zijn pas nuttig als deze keuzes er expliciet bij staan.