💻 computer science

A Datalog Framework for Conflict-Free Replicated Data Types

Dit artikel introduceert een declaratief Datalog-framework dat conflict-vrije gerepliceerde datatypen (CRDT's) modelleert als uitvoerbare logische programma's om systematische specificatie, automatische analyse en eigenschap-gebaseerd testen van complexe concurrente collaboratieve applicaties mogelijk te maken.

Oorspronkelijke auteurs: Elena Yanakieva, Annette Bieniusa, Stefania Dumbrava

Gepubliceerd 2026-06-01

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Elena Yanakieva, Annette Bieniusa, Stefania Dumbrava

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je deel uitmaakt van een team dat een gigantisch, gedeeld digitaal LEGO-kasteel bouwt. Iedereen heeft zijn eigen exemplaar van het kasteel en kan op elk moment stenen toevoegen of verwijderen, zelfs als ze offline zijn of geen verbinding met het internet hebben. Het grote probleem is: wat gebeurt er wanneer twee mensen tegelijkertijd hetzelfde deel van het kasteel proberen te veranderen?

Als Persoon A een rode toren toevoegt terwijl Persoon B de basis van die toren verwijdert, blijft de toren dan staan? Verdwijnt hij? Of stort het hele kasteel in?

Dit artikel introduceert een nieuwe tool genaamd CRDTLog om ontwerpers te helpen de regels voor deze chaotische situaties uit te zoeken voordat ze de eigenlijke software bouwen. Zo werkt het, eenvoudig uitgelegd:

1. Het Probleem: De "Hij zei, zij zei" van digitale data

In de oude dagen moesten computers wachten tot iedereen het eens was voordat ze een wijziging konden doorvoeren. Maar in moderne apps (zoals collaboratieve tekenprogramma's of gedeelde documenten) moeten mensen offline kunnen werken en later synchroniseren. Dit creëert "conflicten".

Ontwikkelaars gebruiken meestal vooraf gemaakte bouwblokken die CRDT's worden genoemd (Conflict-free Replicated Data Types). Zie dit als LEGO-stenen met ingebouwde regels. Bijvoorbeeld een "Set"-steen die de regel heeft: "Als iemand een steen toevoegt en iemand anders verwijdert hem op hetzelfde moment, dan blijft de steen staan."

Het probleem is dat wanneer je deze CRDT-stenen aan elkaar klikt om complexe dingen te bouwen (zoals een graaf van verbonden knooppunten en randen), de regels vreemd kunnen worden. Je denkt misschien dat de regels op een bepaalde manier zullen werken, maar wanneer je ze aan elkaar klikt, kunnen ze een "zwevend uiteinde" creëren (een brug met geen land aan de andere kant) of onverwacht data verliezen.

2. De Oplossing: Een "Simulatie-zandbak" in Logica

De auteurs hebben een framework ontwikkeld genaamd CRDTLog. In plaats van complexe code te schrijven om deze regels te testen, gebruiken ze Datalog, wat een soort zeer strikt, logisch receptenboek is.

Beschouw Datalog als een simulator of een vluchtsimulator voor data:

De Input: Je voert de simulator een "geschiedenis" van gebeurtenissen (bijv. "Gebruiker 1 voegde een knooppunt toe," "Gebruiker 2 verwijderde een rand," "Gebruiker 3 voegde tegelijkertijd een rand toe").
De Regels: Je schrijft de regels op voor hoe de data zich zou moeten gedragen (de "Ideale Versie").
De Test: Je schrijft ook op hoe jouw specifieke combinatie van CRDT-stenen zich daadwerkelijk gedraagt (de "Echte Versie").
Het Resultaat: De simulator draait beide versies naast elkaar. Als de "Ideale" en de "Echte" versies eindigen met exact hetzelfde kasteel, is je ontwerp goed. Als ze verschillen, laat de simulator je precies zien waar de logica is gebroken.

3. Hoe ze het hebben getest: De Grafen-casestudy

Om te bewijzen dat hun tool werkt, hebben de auteurs een collaboratieve graaf getest (een netwerk van punten en lijnen, zoals een kaart of een sociaal netwerk). Ze keken naar twee verschillende manieren om verwijderingen af te handelen:

Scenario A (Isolate-Delete): Je kunt alleen een punt verwijderen als er geen lijnen aan vastzitten. Als iemand probeert een punt te verwijderen terwijl iemand anders er tegelijkertijd een lijn aan toevoegt, wint de lijn, en blijft het punt staan.
Scenario B (Detach-Delete): Als je een punt verwijdert, moeten alle lijnen die ermee verbonden zijn ook verdwijnen, zelfs als iemand anders op datzelfde moment probeerde een lijn toe te voegen.

Ze gebruikten CRDTLog om de "Ideale Regels" voor beide scenario's te bouwen. Daarna probeerden ze deze te bouwen met standaard CRDT-stenen.

De Ontdekking: Voor het "Detach-Delete"-scenario faalde een eenvoudige combinatie van stenen. Het creëerde "zwevende lijnen" (lijnen die aan niets vastzitten).
De Fix: CRDTLog liet hen precies zien waarom het faalde. Ze moesten de manier waarop ze de stenen aan elkaar klikten veranderen (door een andere transformatieregel te gebruiken) om de lijnen correct te laten verdwijnen.

4. Waarom dit ertoe doet

De auteurs beweren dat dit de eerste keer is dat Datalog systematisch is gebruikt om deze complexe datatypen te prototypen en te analyseren.

Het is als een blauwdrukcontrole: Voordat je beton stort voor een gebouw, controleer je de berekeningen. Deze tool controleert de "wiskunde" van je dataregels.
Het is snel: Ze hebben dit getest met duizenden gesimuleerde gebruikers en gebeurtenissen. De tool was snel genoeg om deze tests automatisch uit te voeren, wat bewijst dat je complexe logica kunt controleren zonder eerst een volledig, duur softwaresysteem te schrijven.
Het vangt verborgen bugs op: Het vond subtiele problemen waarbij standaard bouwblokken niet samenwerkten op de manier die ontwikkelaars verwachtten.

Samenvatting

Kortom, de auteurs hebben een logica-gebaseerde simulator gebouwd waarmee ontwikkelaars "wat als"-scenario's kunnen spelen met hun dataregels. Het helpt hen te zien of hun gekozen combinatie van digitale bouwstenen daadwerkelijk het kasteel zal creëren dat ze willen, of dat het zal eindigen met zwevende bruggen en ontbrekende muren. Ze bewezen dat dit werkt door succesvol een complexe collaboratieve grafische applicatie te debuggen.

Technische Samenvatting: Een Datalog-framework voor Conflict-Free Replicated Data Types

Probleemstelling

Gedistribueerde applicaties vertrouwen steeds vaker op local-first samenwerking, waardoor meerdere gebruikers gelijktijdig gedeelde gegevens kunnen bijwerken zonder globale coördinatie. Hoewel Conflict-Free Replicated Data Types (CRDT's) een mechanisme bieden voor deterministische convergentie en Strong Eventual Consistency (SEC), blijft het bouwen van complexe applicaties met deze types een uitdaging. Ontwikkelaars moeten vaak meerdere basis-CRDT's (bijv. sets, maps, sequenties) samenstellen om rijkere functionaliteiten te bereiken. Echter, conflictresolutiebeleid componeert niet voorspelbaar; subtiele concurrency-patronen kunnen ervoor zorgen dat samengestelde CRDT's convergeren naar staten die de beoogde applicatiesemantiek schenden.

Momenteel is er een gebrek aan expliciete, analyseerbare specificaties die verklaren waarom een bepaald concurrent resultaat ontstaat. Ontwikkelaars worstelen met het verifiëren of een specifieke CRDT-compositie daadwerkelijk de beoogde applicatielogica realiseert, met name wanneer zij te maken hebben met invarianten zoals de afwezigheid van zwevende randen (dangling edges) in collaboratieve grafen. Formele verificatie is vaak te kostbaar en vereist te veel expertise, terwijl ad-hoc testen complexe concurrency-gelegenheden kan missen.

Methodologie

De auteurs stellen CRDTLog voor, een declaratief framework geïmplementeerd in Datalog (specifiek met de Soufflé-engine) om de semantiek van CRDT's te specificeren, te prototypen en te analyseren. De kernmethodologie bestaat uit het modelleren van CRDT-semantiek als uitvoerbare logische programma's over operatiecontexten.

1. Operatiecontexten

Het framework neemt het model van Burckhardt voor gerepliceerde datatypen over en generaliseert dit. Een operatiecontext $C = (E, op, vis, ar)$ wordt gedefinieerd als een eindige event graph waarbij:

$E$ een verzameling events is.
$op$ events mapt naar verzamelingen operaties (wat de atomaire uitvoering van meerdere operaties per event mogelijk maakt).
$vis$ een acyclische zichtbaarheidsrelatie is (happens-before).
$ar$ een totale arbitrage-orde is (wordt alleen gebruikt wanneer de semantiek dit vereist, bijvoorbeeld last-writer-wins).

Een gerepliceerd datatype $F_X$ is een deterministische functie die een operatie en een context mapt naar een retourwaarde. In Datalog worden deze contexten gecodeerd als input-relaties (setEvent, vis, ar), en de resulterende staat wordt afgeleid als output-relaties.

2. Specificatieworkflow

Het framework ondersteunt een tweelaagse workflow voor ontwikkelaars:

Specification-Level Semantics (SLS): Een hoog niveau, declaratieve definitie van de beoogde applicatiefunctionaliteit, onafhankelijk van een specifieke CRDT-ontwerp. Dit wordt direct geschreven in Datalog-regels over de operatiecontext.
Implementation-Level Compositional Semantics (ICS): Een realisatie van de applicatie met behulp van een compositie van basis of geneste CRDT's. Dit omvat het definiëren van transformatieregels die applicatie-niveau operaties mappen naar component-niveau operaties.

Het framework maakt property-based testing mogelijk: gegeven een set gegenereerde gelijktijdige executies (operatiecontexten), controleert het systeem of de ICS convergeert naar dezelfde staat als de SLS. Als ze divergeren, moet de decompositie worden herzien.

3. Afhandeling van Geneste en Samengestelde CRDT's

Het framework ondersteunt:

Geneste CRDT's: Zoals Map⟨Set⟩. Omdat Datalog-engines zoals Soufflé geen dynamische module-instantiatie ondersteunen, codeert het framework geneste structuren met behulp van geïndexeerde sets waarbij de sleutel als scope-discriminator fungeert.
Samengestelde CRDT's: Complexe applicaties (bijv. collaboratieve grafen) worden gemodelleerd door ze te deconstrueren in eenvoudigere CRDT's (bijv. een Set voor knopen en een Map voor randen) en door transformatieregels te definiëren die conflictinductie afhandelen (bijv. ervoor zorgen dat een toevoeging van een rand een gelijktijdige verwijdering van een knoop verslaat).

Belangrijkste Bijdragen

Declaratief Framework: Een uitgebreid framework voor het specificeren van CRDT- en collaboratieve applicatiesemantiek gebaseerd op operatiecontexten, geïmplementeerd in Datalog.
CRDTLog Implementatie: Een systeem gebouwd op Soufflé dat een bibliotheek biedt van specificaties voor basis, geneste en samengestelde CRDT's, samen met tools om operatiecontexten te genereren en semantische uitkomsten te vergelijken.
Casestudy over Collaboratieve Grafen: Een gedetailleerde analyse van twee grafvarianten:
- Isolate-Delete (ID): Knopen kunnen alleen worden verwijderd als ze geïsoleerd zijn.
- Detach-Delete (DD): Het verwijderen van een knoop verwijdert alle incidentele randen.
  De studie laat zien hoe het framework niet-voor de hand liggende concurrency-gedragingen blootlegt, zoals hoe een naïeve decompositie van een DD-graaf met behulp van Map⟨Set⟩ kan leiden tot zwevende randen door conflicterende update-wins semantiek, wat een specifieke transformatiestrategie vereist (het gebruik van een platte set van edge-tuples) om de invariant te voldoen.
Empirische Evaluatie: Een systematische beoordeling van de semantische equivalentie tussen abstracte specificaties en samengestelde realisaties, naast schaalbaarheidsbenchmarks.

Experimentele Resultaten

De auteurs hebben het framework geëvalueerd met behulp van property-based testing op de ID- en DD-graficapplicaties:

Semantische Equivalentie (RQ1): Over 1.000 onafhankelijke executies voor acht verschillende configuraties (variërend in replica's en event-aantallen) produceerden de ICS en de SLS identieke observeerbare staten, wat de correctheid van de CRDT-composities valideert.
Schaalbaarheid:
- Grafengrootte: Naarmate het aantal knopen en randen toenam, werd de ICS-implementatie aanzienlijk sneller dan de SLS (tot wel een orde van grootte voor grote grafen), omdat de decompositie de regelcomplexiteit en join-groottes vermindert.
- Concurrency: Het verhogen van het aantal replica's (van 2 naar 16) had slechts een beperkte impact op de runtime, aangezien dit primair de structuur van de zichtbaarheidsrelatie beïnvloedt in plaats van de complexiteit van de regel-evaluatie.
- Event Volume: De evaluatiekosten schalen primair met het aantal events in de operatiecontext.
Incrementaliteit: Wanneer geïnstantieerd met DDlog (een incrementele Datalog-engine), ondersteunde het framework interactieve, stap-voor-stap verificatie. Hoewel het langzamer is dan Soufflé voor batchverwerking, bleef het praktisch voor kleine tot middelgrote contexten die geschikt zijn voor exploratief ontwerp.

Betekenis en Claims

Het artikel beweert de eerste studie te zijn die Datalog systematisch gebruikt als fundament voor het prototypen en analyseren van complexe CRDT's en hun composities.

De betekenis ligt in de verschuiving van de focus van het verifiëren van de correctheid van individuele CRDT's (zoals gedaan in werken zoals Peepul) naar het verifiëren van applicatie-niveau semantiek over composities heen. Door de semantische mismatches tussen de beoogde functionaliteit en de CRDT-composities expliciet, uitvoerbaar en weerlegbaar te maken, stelt het framework ontwikkelaars in staat om:

Alternatieve CRDT-decomposities te verkennen voordat zij zich vastleggen op een gedistribueerde implementatie.
Corner cases in gelijktijdige interacties systematisch te testen.
De semantische kern van conflictresolutie te isoleren van protocol- en engineeringkeuzes.

De auteurs hanteren een bescheiden standpunt door te merken dat hoewel hun prototype Soufflé gebruikt, de aanpak steunt op standaard Datalog-functies (recursie, gestratificeerde negatie, aggregaten) die beschikbaar zijn in veel engines. Zij erkennen dat de formele verificatie van gedistribueerde applicaties nog steeds een expert-niveau vereist en dat hun werk een lichtgewicht, systematisch testalternatief biedt tijdens de ontwerpfase. Toekomstig werk omvat het formaliseren van CRDTLog in een theorem prover voor machine-gecontroleerde bewijzen.