Deterministisch simulatietesten in celld: het verkennen van uitvoeringsvolgordes en het reproduceren van bugs

We bouwen aan celld, een runtime voor Cloudflare Workers- en Durable Objects-applicaties op eigen machines. Het kan draaien met een S3-compatibele object store als enige externe service-afhankelijkheid.

celld is een gedistribueerd systeem. Het betrouwbaar maken van gedistribueerde systemen is moeilijk, mede omdat we onbedoeld kunnen vertrouwen op aannames die in de praktijk niet standhouden, zelfs als we de valkuilen kennen. Peter Deutschs The Eight Fallacies of Distributed Computing somt acht van deze aannames op, waaronder "Het netwerk is betrouwbaar" en "Latentie is nul."

Een bug kan afhangen van een specifieke volgorde van vertraagde berichten, mislukte schrijfacties en het herstarten van nodes. Deze gebeurtenissen kunnen bij een volgende testrun in een andere volgorde plaatsvinden, waardoor de fout moeilijk te reproduceren is. We moeten in staat zijn om een falende run te herhalen, zodat we de oorzaak kunnen onderzoeken en kunnen controleren of een voorgestelde oplossing het probleem daadwerkelijk oplost.

Dat is de reden waarom we gebruikmaken van deterministic simulation testing (DST). Onze simulator is nog in ontwikkeling en is niet opgenomen in de publieke repository van celld, maar heeft al voorheen onbekende bugs gevonden. In dit artikel leggen we uit hoe DST werkt in celld en hoe het ons hielp om een van deze bugs te vinden, te reproduceren en op te lossen.

Hoe DST werkt in celld

DST draait de productiecode van celld in een omgeving die wordt gecontroleerd door een simulator.

Een cell in celld voert applicatiecode uit en heeft zijn eigen SQLite-database. Terwijl cells hun werk doen, handelt celld gebeurtenissen af, zoals inkomende verzoeken, voltooide opslagoperaties en het afgaan van timers. De code die de volgende gebeurtenis selecteert, is gescheiden van de code die deze afhandelt. Hierdoor kan de simulator de volgorde van gebeurtenissen beheren, terwijl dezelfde event-handling code wordt gebruikt als in productie.

De simulator controleert ook wanneer asynchrone taken worden uitgevoerd en hoe de object storage reageert. De simulator kan een schrijfactie vertragen of laten mislukken. Het kan de gesimuleerde tijd vooruitspoelen zonder te wachten tot de werkelijke tijd is verstreken. We gebruiken deze controle om te testen hoe tijdsafhankelijk gedrag, zoals retries en alarmen, interageert met andere gebeurtenissen.

We configureren welke verzoeken en fouten de simulator mag verkennen. Binnen die grenzen gebruikt de simulator willekeurige keuzes om verzoeken te genereren, te bepalen wat er vervolgens wordt uitgevoerd, te beslissen of opslagoperaties slagen of falen, en te kiezen welke fouten op welk moment optreden.

Een seed is de startwaarde voor de random-number generator. Met dezelfde code, instellingen en seed krijgen we dezelfde volgorde, tussenliggende statussen en resultaten. We kunnen verschillende runs verkennen door de seed te wijzigen, en vervolgens een falende run herhalen om te achterhalen waar het misging.

Na elke actie gebruikt een checker de waargenomen responsen en opgeslagen data om invariants te testen: condities die we definiëren en waaraan het systeem gedurende een hele run moet voldoen. De test initialiseert celld met de gesimuleerde omgeving en verkent vervolgens acties tot aan een geconfigureerde limiet. In pseudocode:

const simulation = createSimulation({ settings, seed });
for (let step = 0; step < settings.maxActions; step++) {
  const candidates = simulation.availableActions();
  if (candidates.length === 0) {
    checkCompletion(simulation);
    break;
  }
  const action = simulation.choose(candidates);
  simulation.run(action);
  checkInvariants(simulation);
}

Hier is een actie iets dat de simulator kan voortzetten: het afleveren van een verzoek, het laten lopen van een taak, het vooruitspoelen van de gesimuleerde klok of het voltooien van een opslagoperatie. Als er geen acties beschikbaar zijn, controleert de test de voltooiingsvoorwaarden, zoals of alle geplande verzoeken zijn afgerond.

Voorbeeld van een uitvoeringsvolgorde

Wanneer we kijken naar een scenario waarin Cell A een rij in SQLite heeft ingevoegd, zien we hoe data naar de object storage wordt geschreven voordat celld een bevestiging ontvangt. In die tussenpoos kunnen andere verzoeken of achtergrondtaken worden uitgevoerd, terwijl celld nog wacht om succes terug te melden aan de client. Bugs kunnen ontstaan wanneer deze operaties op onverwachte manieren worden afgewisseld.

Een vereenvoudigd overzicht van een succesvolle request verloopt als volgt:

  1. De databasewijzigingen uploaden: celld stuurt een batch SQLite-wijzigingen naar de object storage. De gesimuleerde object store ontvangt de data, maar de schrijfactie is nog niet voltooid.
  2. De schrijfactie naar object storage voltooien: De simulator zorgt dat de schrijfactie effect heeft. De data is opgeslagen, maar het succesresultaat is nog niet geleverd aan celld.
  3. Het resultaat afleveren en wachtend werk hervatten: Nadat het opslagresultaat arriveert, hervat celld de uitvoering en bevestigt dat de databasewijzigingen duurzaam zijn opgeslagen.
  4. Een succesvolle respons terugsturen: Nadat celld de laatste controles heeft voltooid, wordt de respons verzonden. De client ontvangt een succesmelding voor de rij-insertie.

Een alarm-race die de simulator vond

Een alarm plant in dat een cell op een specifiek tijdstip applicatiecode moet uitvoeren. De cell hoeft niet tot dat moment in het geheugen te blijven: celld kan een inactieve cell uitladen om ruimte te maken voor anderen en deze weer laden op tijd voor het alarm.

De geplande tijd van het alarm wordt opgeslagen in de SQLite-database van de cell. Als de cell is uitgeladen, zou het zoeken naar het alarm via SQLite betekenen dat de database opnieuw geopend moet worden. Omdat dit voor elke cell te duur zou zijn, scant celld in plaats daarvan wake entries in de object storage. Elke entry identificeert een cell en het moment waarop deze gereactiveerd moet worden. Zodra de cell actief is, leest celld de geplande tijd uit SQLite om te bepalen wanneer het alarm precies moet afgaan.

Ten tijde van deze bug hergebruikte celld wake entries om het aantal schrijfacties naar de object storage te verminderen. Bijvoorbeeld: een applicatie kon een alarm voor 10:00 verwijderen en vervolgens een nieuw alarm instellen voor 10:05. Als de wake entry voor 10:00 nog aanwezig was, kon celld deze hergebruiken om de cell om 10:00 te reactiveren, wat vroeg genoeg is voor het nieuwe alarm. Zodra de cell actief was, zou celld de tijd 10:05 uit SQLite lezen en tot die tijd wachten. [^1]

Het verwijderen van het 10:00-alarm wist de geplande tijd in SQLite. Zodra die wijziging is opgeslagen in de object storage, stuurt celld een succesmelding naar de client. Een aparte opruimtaak verwijdert de 10:00 wake entry pas later, zodat de client niet hoeft te wachten op deze extra opslagoperatie. De client kan dus het 10:05-alarm instellen terwijl de oude opruiming nog wacht om te worden uitgevoerd.

Nadat celld bevestigt dat het 10:05-alarm is ingesteld, moet er een wake entry overblijven die de cell uiterlijk om 10:05 kan reactiveren. De simulator controleert of dit waar blijft totdat het alarm afgaat of wordt geannuleerd.

De volgorde van de race-conditie

De simulator ontdekte dat deze invariant wordt geschonden wanneer de oude opruiming wordt uitgevoerd nadat het 10:05-alarm is ingesteld:

  1. Het 10:00-alarm verwijderen: Het alarm is weg uit SQLite. De 10:00 wake entry blijft echter in de storage aanwezig omdat de opruimtaak nog niet is uitgevoerd.
  2. De verwijdering bevestigen: De client ontvangt een succesmelding voor het verwijderen van het alarm. De opruiming van de 10:00 wake entry wacht nog steeds.
  3. Eerst een 10:05-alarm instellen: Het 10:05-alarm hergebruikt de 10:00 wake entry; de cell kan vroeg wakker worden en wachten tot 10:05.
  4. De nieuwe instelling bevestigen: Het instellen van het 10:05-alarm slaagt. De hergebruikte 10:00 wake entry moet nu beschikbaar blijven.
  5. De vertraagde opruiming uitvoeren: De opruimtaak die gebaseerd is op de eerdere verwijdering, voert nu het verzoek uit om de 10:00 wake entry te verwijderen.
  6. De controle detecteert verloren wake-informatie: De 10:00 wake entry is verdwenen, ondanks dat het 10:05-alarm succesvol was ingesteld.

In deze run gaven zowel het verwijderen van het 10:00-alarm als het instellen van het nieuwe 10:05-alarm een succesmelding, terwijl de oude opruiming wachtte. Wanneer de simulator die opruiming uiteindelijk activeerde, verwijderde deze de 10:00 wake entry die het nieuwe alarm nog nodig had. De checker rapporteerde een schending van de invariant: het 10:05-alarm stond nog steeds in SQLite, maar er was geen wake entry meer om de cell te reactiveren.

Als de node zou herstarten vóór 10:05, zou de ontbrekende wake entry ervoor kunnen zorgen dat het alarm niet afgaat, ondanks de eerdere succesmelding. De simulator vond deze falende volgorde door verzoeken en openstaande taken te verkennen, zonder dat we een specifieke test hadden geschreven die deze volgorde voorschreef.

De race reproduceren en oplossen

We hebben de fout gereproduceerd door de run te herhalen met dezelfde code, instellingen en seed. Elke run stelde ons in staat om het exacte moment te inspecteren waarop de oude opruiming de benodigde wake entry verwijderde, zonder opnieuw te hoeven zoeken naar de falende volgorde.

Sindsdien hebben we het ontwerp van de wake entries gewijzigd. Elke nieuwe alarm-instelling krijgt nu zijn eigen entry in de object storage. Een vertraagde verwijdering van een ouder alarm kan alleen die oudere entry verwijderen, waardoor de nieuwe intact blijft. Oude entries worden verwijderd zodra celld heeft bevestigd dat ze niet langer nodig zijn.

We hebben de falende run omgezet in een regressietest die de requests en de volgorde van opruiming herhaalt. Deze test controleert of het nieuwe alarm een bruikbare wake entry behoudt. De regressietest controleert de invariant tijdens de gehele run, en niet alleen aan het einde. Als de wake entry zou verdwijnen en later weer zou worden hersteld, zou een controle van alleen de eindstatus de schending missen.

Wat volgt

De simulator is nog in ontwikkeling, maar heeft ons al geholpen om voorheen onbekende bugs in celld te vinden en op te lossen. Vervolgens zullen we meer combinaties van verzoeken, opslagfouten en node-restarts testen. Een voorbeeld hiervan is een node die herstart tijdens een storage-outage en nieuwe verzoeken ontvangt voordat de storage hersteld is.

We zullen ook checks toevoegen voor meer van de garanties van celld. Een schrijfactie die als succesvol is gemeld, moet bijvoorbeeld een node-restart overleven. Wanneer deze tests een bug vinden, kunnen we de fout reproduceren, oplossen en de volgorde bewaren als regressietest.

***

[^1]: Als celld de cell zou moeten uitladen terwijl hij wacht op 10:05, zou het eerst ervoor zorgen dat er een wake entry voor 10:05 aanwezig was.