Einigkeit ohne Abstimmung: CRDTs und die Kunst der konfliktfreien Replikation

Der Aufhänger: Zwei Menschen, ein Einkaufszettel, kein Netz

Stell dir vor, du und dein Partner teilt euch eine Einkaufsliste in einer App. Du sitzt in der U-Bahn ohne Empfang und streichst „Milch" von der Liste, weil ihr noch welche habt. Gleichzeitig, im Supermarkt und ebenfalls mit wackeligem Netz, fügt dein Partner „Milch" hinzu, weil er sie nicht mehr im Kühlschrank gesehen hat. Zehn Minuten später haben beide Geräte wieder Verbindung. Was passiert?

In einem naiven System gewinnt, wer zuletzt schreibt – und je nach Zufall der Netzwerklaufzeiten ist „Milch" danach entweder auf der Liste oder nicht, ohne dass irgendjemand nachvollziehen kann, warum. Im schlimmeren Fall überschreibt eine Synchronisation die andere komplett, und die halbe Liste verschwindet. Jeder, der schon einmal ein Dokument doppelt bearbeitet und dann eine „Konfliktkopie (2)" im Ordner gefunden hat, kennt das Gefühl.

Dieses banale Beispiel enthält eines der tiefsten Probleme der verteilten Datenverarbeitung: Wie können mehrere Repliken derselben Daten gleichzeitig, unabhängig und offline verändert werden – und trotzdem garantiert zum selben, sinnvollen Endzustand finden, sobald sie sich wiedersehen? Die klassische Antwort lautet: Koordination. Man lässt die Repliken abstimmen, wählt einen Anführer, erzwingt eine Reihenfolge. Das ist die Welt des verteilten Konsenses – mächtig, aber teuer, langsam und unter Netzpartitionen schlicht blockiert.

Es gibt eine radikal andere Antwort. Sie besagt: Wenn wir unsere Datentypen mathematisch geschickt genug bauen, brauchen wir überhaupt keine Koordination. Konflikte lösen sich nicht durch Abstimmung, sondern durch Konstruktion – sie können gar nicht erst entstehen. Diese Datentypen heißen Conflict-free Replicated Data Types, kurz CRDTs. Dieser Artikel nimmt dich mit von der Intuition über die überraschend elegante Mathematik dahinter bis zu den Systemen, in denen CRDTs heute Milliarden Operationen pro Tag zusammenführen – von Redis über Riak bis zu den kollaborativen Editoren, in denen vielleicht gerade dieser Text geschrieben wurde.

Teil 1: Warum Einigung normalerweise so teuer ist

Das CAP-Dilemma in einem Satz

Eric Brewers CAP-Theorem, 2002 von Gilbert und Lynch formal bewiesen, stellt jedes verteilte System vor eine unbequeme Wahl. Wenn das Netz partitioniert ist – wenn also zwei Teile des Systems einander nicht mehr erreichen können, was in der Praxis unvermeidlich ist –, dann muss man sich zwischen zwei Übeln entscheiden: Entweder man verweigert Schreibzugriffe, bis die Verbindung wieder steht (Konsistenz vor Verfügbarkeit, „CP"), oder man akzeptiert Schreibzugriffe auf beiden Seiten und riskiert, dass die Zustände auseinanderlaufen (Verfügbarkeit vor Konsistenz, „AP").

Systeme, die auf Konsens setzen – etcd, ZooKeeper, alles, was auf Paxos oder Raft aufbaut –, wählen konsequent die erste Option. Sie garantieren, dass es immer nur eine Wahrheit gibt, aber sie erkaufen das mit Latenz (jede Entscheidung braucht mindestens eine Netzwerk-Rundreise zu einer Mehrheit) und mit Blockaden während einer Partition. Das ist genau richtig für eine Bankbuchung oder die Wahl eines Cluster-Anführers. Für eine Einkaufsliste, einen Chat-Zähler oder ein gemeinsames Dokument ist es fast absurd: Niemand möchte, dass sich seine Notiz-App aufhängt, nur weil das WLAN im Zug schlecht ist.

Eventual Consistency – und ihr wunder Punkt

Die AP-Welt wählt Verfügbarkeit. Ihr Versprechen heißt Eventual Consistency (eventuelle Konsistenz): Wenn keine neuen Updates mehr kommen, werden irgendwann alle Repliken denselben Zustand erreichen. Amazons berühmtes Dynamo-Paper (2007) machte dieses Modell für die Industrie salonfähig und steht im Hintergrund vieler späterer Artikel in diesem Vault, von Consistent Hashing bis zu den Merkle-Bäumen der Anti-Entropie.

Der wunde Punkt steckt im Wörtchen „irgendwann". Klassische Eventual Consistency sagt dass die Repliken konvergieren, aber nicht wie. Wenn zwei konkurrierende Schreibvorgänge auf denselben Schlüssel treffen, entsteht ein Konflikt, und irgendjemand muss ihn auflösen. Dynamo reichte diese Aufgabe oft an die Anwendung weiter: Es speicherte beide Versionen als „Siblings" und ließ den Client entscheiden. Das ist ehrlich, aber unbequem – und wenn man es falsch macht, verliert man Daten. Die naivste Auflösung, Last-Writer-Wins (der spätere Zeitstempel gewinnt), ist bequem, aber verwirft stillschweigend Schreibvorgänge, und bei ungenauen Uhren gewinnt manchmal buchstäblich die falsche Version.

Die entscheidende Frage lautet also nicht „konvergieren wir?", sondern „konvergieren wir deterministisch, automatisch und ohne Datenverlust?". Genau hier setzen CRDTs an.

Teil 2: Strong Eventual Consistency – ein stärkeres Versprechen

2011 formalisierten Marc Shapiro, Nuno Preguiça, Carlos Baquero und Marek Zawirski in zwei zusammengehörigen Arbeiten – dem umfassenden INRIA-Forschungsbericht und der prägnanten Konferenzfassung auf der SSS 2011 – ein Konsistenzmodell, das schärfer ist als bloße Eventual Consistency. Sie nannten es Strong Eventual Consistency (SEC). Die Definition besteht aus zwei Teilen:

Eventual Delivery (eventuelle Zustellung): Jedes Update, das eine korrekte Replik anwendet, wird schließlich von allen korrekten Repliken angewendet.

Convergence / Strong Convergence (starke Konvergenz): Zwei korrekte Repliken, die dieselbe Menge an Updates gesehen haben, befinden sich im äquivalenten Zustand – sofort, deterministisch, ohne weitere Kommunikation.

Der Unterschied zur klassischen Eventual Consistency ist subtil, aber fundamental. Klassische EC erlaubt, dass Repliken vorübergehend divergieren und der Konflikt später durch Rollback oder Konsens aufgelöst wird. SEC verbietet Konflikte im Sinne von Rollbacks vollständig: Sobald zwei Repliken dieselben Updates kennen, sind sie garantiert gleich. Es gibt kein „Aushandeln", kein Zurückrollen, keine Sondersitzung. Ein Datentyp, der SEC erfüllt, ist ein CRDT.

Die zwei Wege zum selben Ziel

Shapiro und Kollegen zeigten, dass es zwei komplementäre Konstruktionsprinzipien gibt, die beide SEC garantieren – und die sich (bemerkenswerterweise) gegenseitig emulieren können.

Zustandsbasierte CRDTs (state-based, CvRDT – „convergent"): Jede Replik hält ihren vollständigen Zustand. Um zu synchronisieren, schickt eine Replik ihren gesamten Zustand an eine andere, und die empfangende Replik führt beide Zustände mit einer merge-Funktion zusammen. Die Konvergenz ist garantiert, wenn drei Bedingungen erfüllt sind: Die möglichen Zustände bilden einen Halbverband (dazu gleich mehr), lokale Updates lassen den Zustand im Sinne dieses Verbandes nur „wachsen" (Monotonie), und merge berechnet die kleinste obere Schranke zweier Zustände. Der große Vorteil: Das Netzwerk darf Nachrichten beliebig verlieren, doppeln oder umordnen – solange der Zustand ab und zu ankommt, konvergiert das System.

Operationsbasierte CRDTs (operation-based, CmRDT – „commutative"): Statt ganzer Zustände werden einzelne Operationen übertragen (etwa „füge X hinzu" oder „erhöhe um 3"). Jede Replik wendet Operationen an, sobald sie eintreffen. Die Konvergenz ist garantiert, wenn konkurrierende Operationen kommutieren – also in beliebiger Reihenfolge dasselbe Ergebnis liefern. Der Preis dafür ist eine stärkere Anforderung an das Netzwerk: Operationen müssen zuverlässig und in kausaler Reihenfolge genau einmal zugestellt werden (oder mehrfach, wenn sie zusätzlich idempotent sind). Man braucht also eine verlässliche Broadcast-Schicht. Wer sich fragt, wie „kausale Reihenfolge" präzise definiert wird, findet die Antwort bei den Vektoruhren aus Lamport-Zeitstempeln und Vektoruhren – sie sind das Fundament, auf dem operationsbasierte CRDTs stehen.

Der Trade-off ist praktisch: Zustandsbasierte CRDTs sind robust gegenüber einem miesen Netz, verschicken aber potenziell viel Ballast (den ganzen Zustand). Operationsbasierte CRDTs sind sparsam, verlangen aber mehr von der Zustellschicht. Eine spätere Innovation, die Delta-State-CRDTs von Almeida, Shoker und Baquero (2016), verbindet beide Welten: Man überträgt nur die kleinen „Deltas", die sich seit der letzten Synchronisation geändert haben, behält aber die Robustheit des zustandsbasierten Ansatzes.

Die Mathematik dahinter: der Halbverband

Warum funktioniert das überhaupt? Die Antwort ist eine der schönsten Ideen der ganzen Geschichte, und sie stammt aus der Ordnungstheorie. Der zustandsbasierte Ansatz verlangt, dass die möglichen Zustände einen Join-Halbverband (join-semilattice) bilden. Das klingt abschreckend, ist aber eine simple Struktur: eine Menge mit einer Ordnung, in der je zwei Elemente eine eindeutige kleinste obere Schranke (den „Join") besitzen. Die merge-Funktion ist genau dieser Join.

Damit Konvergenz garantiert ist, muss der Join drei algebraische Eigenschaften haben:

Kommutativität: merge(a, b) = merge(b, a). Die Reihenfolge, in der Zustände zusammengeführt werden, ist egal.

Assoziativität: merge(a, merge(b, c)) = merge(merge(a, b), c). Die Gruppierung ist egal.

Idempotenz: merge(a, a) = a. Dieselbe Information zweimal einzuspielen ändert nichts.

Diese drei Eigenschaften sind exakt das Gegengift gegen die drei Gemeinheiten eines realen Netzwerks: Kommutativität besiegt Umordnung, Assoziativität besiegt beliebige Gruppierung von Batches, und Idempotenz besiegt Duplikate. Ein Netzwerk kann Nachrichten in falscher Reihenfolge, gebündelt und mehrfach zustellen – dem Halbverband ist das gleichgültig. Solange der Zustand nur „nach oben" wandert und merge die kleinste obere Schranke bildet, landen alle Repliken zwangsläufig am selben Punkt. Konvergenz ist hier kein glücklicher Zufall, sondern ein mathematisches Theorem.

Teil 3: Der Zoo der Datentypen – vom Zähler zur Menge

Theorie wird greifbar an Beispielen. Sehen wir uns die kanonischen CRDTs an, geordnet von einfach nach subtil.

G-Counter – der wachsende Zähler

Der Grow-only Counter zählt nur aufwärts (Likes, Seitenaufrufe, verkaufte Tickets). Der naive Ansatz – eine einzige Zahl, die jede Replik erhöht – scheitert sofort: Wenn zwei Repliken unabhängig von 5 auf 6 gehen und dann mergen, ist das Ergebnis 6 statt der korrekten 7. Der Trick: Jede Replik führt ihren eigenen Teilzähler in einem Vektor, indexiert nach Replik-ID. Eine Replik erhöht nur ihren eigenen Eintrag. Der merge nimmt elementweise das Maximum der beiden Vektoren, und der Wert des Zählers ist die Summe aller Einträge. Elementweises Maximum ist offensichtlich kommutativ, assoziativ und idempotent – der G-Counter ist ein sauberer Halbverband. (Wer genau hinsieht, erkennt die strukturelle Verwandtschaft zur Vektoruhr wieder.)

PN-Counter – auch abwärts

Ein Zähler, der auch dekrementieren kann, scheint das Maximum-Prinzip zu brechen (Dekremente „wachsen" nicht). Die Lösung ist verblüffend einfach: Man nimmt zwei G-Counter, einen für alle Inkremente (P) und einen für alle Dekremente (N). Der Wert ist Summe(P) − Summe(N). Beide Teile wachsen monoton, der Halbverband bleibt intakt. Dieses Muster – „ein negatives Ereignis als eigenes positives Ereignis modellieren" – ist einer der wiederkehrenden Denktricks der CRDT-Welt.

G-Set und 2P-Set – Mengen und ihr Löschproblem

Eine Grow-only Set ist trivial: Elemente kann man nur hinzufügen, merge ist die Vereinigung. Vereinigung ist kommutativ, assoziativ, idempotent – fertig.

Das Problem beginnt beim Löschen. Die Two-Phase Set (2P-Set) kombiniert zwei G-Sets: eine Menge der hinzugefügten Elemente (A) und eine Tombstone-Menge der entfernten (R). Ein Element gilt als vorhanden, wenn es in A und nicht in R ist. Das funktioniert – hat aber zwei hässliche Eigenschaften: Ein einmal gelöschtes Element kann nie wieder hinzugefügt werden (es steht für immer in R), und die Tombstones wachsen unbegrenzt. Das 2P-Set ist ein Lehrstück dafür, dass eine Konstruktion konvergieren und trotzdem eine unbrauchbare Semantik haben kann.

LWW-Register und Multi-Value-Register

Ein Register hält einen einzelnen Wert. Das Last-Writer-Wins-Register hängt an jeden Schreibvorgang einen Zeitstempel und behält beim merge den mit dem höheren Zeitstempel (bei Gleichstand entscheidet ein deterministischer Tie-Break, etwa die Replik-ID). Es konvergiert garantiert, verwirft aber bei echten gleichzeitigen Schreibvorgängen stillschweigend einen davon. Die Alternative ist das Multi-Value-Register (MV-Register): Es behält bei echter Nebenläufigkeit beide Werte und reicht die Entscheidung an die Anwendung weiter – genau das „Sibling"-Modell aus Dynamo, nun aber sauber formalisiert.

OR-Set – die Menge, die man richtig löschen kann

Der Höhepunkt des Mengen-Designs ist die Observed-Remove Set (OR-Set). Ihre Idee löst das Wiederhinzufügen-Problem des 2P-Sets elegant: Jedes add versieht das Element mit einem eindeutigen, verborgenen Tag (einer Art unsichtbarer Seriennummer). Ein remove entfernt nicht „das Element", sondern nur genau die Tags, die es bereits gesehen hat. Fügt eine andere Replik dasselbe Element gleichzeitig mit einem neuen Tag hinzu, überlebt dieser neue Tag das nebenläufige Löschen – das Element bleibt in der Menge. Man nennt das Add-Wins-Semantik: Bei einem gleichzeitigen Add und Remove desselben Elements gewinnt das Add.

Das ist nicht „richtiger" als die Gegenvariante (Remove-Wins), aber es ist eine explizite, nachvollziehbare Entscheidung – und genau das ist der entscheidende Fortschritt gegenüber dem Zufall von Last-Writer-Wins. Bieniusa und Kollegen zeigten 2012 eine optimierte OR-Set, die den Metadaten-Ballast der Tags drastisch reduziert und damit den praktischen Einsatz ermöglichte. Kombiniert man mehrere solcher Bausteine, entstehen zusammengesetzte Strukturen wie Maps (Riaks Datentypen), in denen die Werte selbst wieder CRDTs sind.

Teil 4: Der schwierigste Fall – kollaboratives Editieren

Zähler und Mengen sind ungeordnet. Text aber ist eine geordnete Sequenz, und Ordnung ist der Endgegner der konfliktfreien Replikation. Wenn zwei Autoren gleichzeitig an verschiedenen Stellen tippen, dürfen sich die Einfügungen nicht gegenseitig überschreiben, und die relative Reihenfolge der Zeichen muss überall gleich rekonstruiert werden – ohne zentrale Instanz.

Warum Positionen als Zahlen nicht reichen

Die naive Idee, jedes Zeichen an einer Indexposition zu speichern, scheitert sofort: Fügt Replik A ein Zeichen an Position 3 ein, verschieben sich alle folgenden Indizes, und Replik Bs gleichzeitige Einfügung an „Position 5" landet an der falschen Stelle. Die Lösung aller Sequenz-CRDTs ist dieselbe Grundidee: Jedes Zeichen bekommt einen stabilen, eindeutigen Identifikator, der seine Position relativ zu den Nachbarn festlegt und sich nie mehr ändert. Zwischen zwei beliebige Identifikatoren muss sich immer ein neuer einfügen lassen – man braucht also dichte, unendlich teilbare Positionsbezeichner, oft in Form von Bruchzahlen oder Pfaden in einem Baum.

Ein Stammbaum der Algorithmen

Die Familie ist groß und in gut zwei Jahrzehnten gewachsen: WOOT (2006) als früher Pionier, Treedoc und Logoot mit baum- bzw. positionsbasierten Identifikatoren, LSEQ mit einer cleveren Strategie, die die Identifikatoren kurz hält, RGA (Replicated Growable Array) mit zeitstempelbasierter Verkettung und schließlich YATA, der Algorithmus hinter der heute sehr populären Bibliothek Yjs von Kevin Jahns. Bemerkenswert ist, dass sich das Verschmelzungsverhalten von YATA und RGA im Kern gleicht.

Zwei Projekte prägen die Praxis: Yjs ist auf schnelles Text-Editing optimiert und genießt einen Ruf für hohe Performance; Automerge von Martin Kleppmann und Mitarbeitern implementiert einen vollständigen JSON-CRDT, nutzt eine kompakte spaltenorientierte Kodierung und wurde für Geschwindigkeit in Rust neu geschrieben. Für Rich Text – also Text mit Formatierung – entwickelten Litt, Kleppmann und Kollegen 2022 Peritext, das Formatierungsspannen konfliktfrei mit dem Text zusammenführt.

Die Interleaving-Anomalie – eine ehrliche Warnung

CRDTs garantieren Konvergenz, aber nicht immer ein menschlich sinnvolles Ergebnis. Ein bekanntes Problem ist das Interleaving: Wenn zwei Autoren gleichzeitig an derselben Stelle ganze Wörter einfügen, können manche Algorithmen die Zeichen der beiden Beiträge verschränken – aus „Hallo" und „Servus" wird im Extremfall ein unlesbarer Buchstabensalat, obwohl alle Repliken brav konvergieren. Kleppmann und Kollegen analysierten diese Anomalien 2019 und in „The Art of the Fugue" (2023) im Detail. Die Lehre ist wichtig: Konvergenz ist notwendig, aber nicht hinreichend für gute kollaborative Semantik. Die Wahl des Algorithmus bleibt eine Design-Entscheidung mit spürbaren Konsequenzen für den Nutzer.

Eine oft missverstandene Fußnote: Figma

Es wird gern behauptet, kollaborative Design-Tools wie Figma liefen auf CRDTs. Das ist nicht ganz richtig, und weil Präzision hier zählt: Figmas Multiplayer-Technik ist von CRDT-Ideen inspiriert, aber kein reines Peer-to-Peer-CRDT. Figma nutzt einen zentralen Server als Autorität und pro Objekteigenschaft eine Last-Writer-Wins-artige Auflösung. Ich bin der Meinung, dass dieses Beispiel die wichtigste praktische Erkenntnis illustriert: Wer einen zentralen Server ohnehin hat, braucht die volle Maschinerie eines CRDT oft nicht – die konfliktfreie Konstruktion entfaltet ihren größten Wert dort, wo es keine verlässliche zentrale Instanz gibt, etwa bei Offline-First-Apps und echter Peer-to-Peer-Synchronisation.

Teil 5: Die tiefere Wahrheit – das CALM-Theorem

Warum funktionieren CRDTs eigentlich, und wo genau liegt ihre Grenze? Die überraschend allgemeine Antwort gibt das CALM-Theorem – Consistency As Logical Monotonicity. Joseph Hellerstein skizzierte es in seiner PODS-Keynote 2010, gemeinsam mit Peter Alvaro formalisierte und popularisierte er es später (die viel gelesene Fassung „Keeping CALM: When Distributed Consistency Is Easy" erschien 2019 als Preprint und 2020 in den Communications of the ACM).

Das Theorem sagt in einem Satz: Ein Problem besitzt genau dann eine konsistente, koordinationsfreie verteilte Implementierung, wenn es monoton ist. „Monoton" bedeutet grob: Neue Information kann eine einmal getroffene Aussage nur bestätigen oder ergänzen, aber nie widerrufen. Ein monotones Programm zieht nur Schlüsse, die durch spätere Daten nicht mehr zurückgenommen werden müssen.

Das ist die begriffliche Klammer um alles bisher Gesagte. Ein Join-Halbverband ist die algebraische Verkörperung von Monotonie: Der Zustand wandert nur „nach oben", nie zurück. CRDTs sind damit nichts anderes als die datentyp-gewordene Umsetzung des CALM-Prinzips. Und CALM erklärt zugleich die harte Grenze: Nicht-monotone Probleme – solche, bei denen eine spätere Information eine frühere Entscheidung ungültig machen kann – lassen sich nicht koordinationsfrei lösen. Für sie braucht es zwingend Konsens.

Das ist keine akademische Spitzfindigkeit, sondern der Kompass für die Architektur. CALM ist die konstruktive, positive Kehrseite der eher negativen Botschaft des CAP-Theorems: CAP sagt, was nicht geht; CALM sagt, wann genau es doch geht. Wo ein Problem monoton formuliert werden kann, darf man auf Koordination verzichten und CRDTs einsetzen. Wo es das nicht kann – dazu gleich mehr –, führt kein Weg an Abstimmung vorbei.

Teil 6: CRDTs in freier Wildbahn

Die Theorie ist elegant, aber CRDTs sind längst Produktionsrealität und führen täglich enorme Mengen an Operationen zusammen.

Riak von Basho war um 2012/2013 einer der ersten Produktionsspeicher, der CRDTs zu erstklassigen Datentypen machte: Zähler, Mengen, Register, Flags und Maps. Riak ersetzte damit sein altes, mühsames „Sibling"-Konfliktmodell durch automatisch verschmelzende Typen und nutzte intern Delta-Techniken, um Bandbreite zu sparen.

Redis Enterprise bietet mit den Active-Active-Datenbanken (Conflict-free Replicated Databases, CRDBs) geografisch verteilte Repliken, die alle lokal schreibbar sind. Unter der Haube kombiniert Redis Vektoruhren mit CRDT-Semantik und garantiert genau die Strong Eventual Consistency aus Teil 2: Werte können kurzzeitig zwischen Rechenzentren differieren, konvergieren aber deterministisch. Zähler und Mengen sind hier native CRDT-Typen.

Im Bereich der lokalen und kollaborativen Software sind Automerge und Yjs die tragenden Säulen für Offline-First- und Echtzeit-Anwendungen. Sie machen das ursprüngliche Versprechen wahr: bearbeiten ohne Netz, synchronisieren ohne Konflikt. Andere Datenbanken wie Azure Cosmos DB bieten bei Multi-Region-Schreibzugriffen verwandte, CRDT-nahe Auflösungsstrategien an, ohne notwendigerweise reine CRDTs zu sein.

Die Kosten und Grenzen – der ehrliche Teil

CRDTs sind kein Allheilmittel, und ein guter Architekt kennt den Preis.

Metadaten-Ballast und Garbage Collection. Tags, Zeitstempel und vor allem Tombstones (Grabsteine für gelöschte Elemente) sammeln sich an. Sie ganz zu entfernen ist heikel, weil man sicher sein muss, dass wirklich jede Replik die Löschung gesehen hat – und diese Sicherheit („kausale Stabilität") herzustellen, verlangt manchmal genau jene Koordination, die man vermeiden wollte. Die Garbage Collection von CRDT-Metadaten ist ein aktives, nicht triviales Forschungs- und Engineering-Thema.

Konvergenz ist nicht Korrektheit. Das ist die wichtigste Einschränkung überhaupt. CRDTs garantieren, dass alle Repliken denselben Zustand erreichen – nicht, dass dieser Zustand jede Geschäftsregel einhält. Das klassische Gegenbeispiel ist ein Bankkonto mit der Invariante „Saldo darf nie negativ werden". Wenn zwei Repliken gleichzeitig eine Abhebung erlauben, weil jede lokal noch Deckung sieht, konvergiert das PN-Counter-Konto sauber – auf einen verbotenen negativen Wert. Solche globalen Invarianten und Eindeutigkeitsbedingungen (etwa „dieser Benutzername darf nur einmal vergeben werden") sind nicht-monoton und fallen damit direkt unter das Verdikt des CALM-Theorems: Sie brauchen Koordination. Kein CRDT der Welt kann das umgehen.

Semantik will bewusst gewählt sein. Add-Wins oder Remove-Wins? Behalten wir bei gleichzeitigen Schreibvorgängen beide Werte oder nur einen? Diese Fragen haben keine universell richtige Antwort; sie hängen von der Anwendung ab. CRDTs zwingen den Entwickler, diese Entscheidungen explizit zu treffen – was ein Segen ist, aber eben auch Denkarbeit verlangt.

Frameworks und Vergleich

Zustands- vs. operationsbasiert

Die drei algebraischen Gebote (zustandsbasiert)

Der Datentyp-Zoo auf einen Blick

Erkenntnis zum Mitnehmen

Die zentrale Einsicht der CRDTs ist eine Umkehrung der üblichen Denkrichtung. Normalerweise fragen wir: „Wie lösen wir Konflikte, wenn sie auftreten?" CRDTs fragen: „Wie bauen wir Daten so, dass Konflikte gar nicht erst entstehen können?" Der Schlüssel ist, den Preis der Verlässlichkeit von der Laufzeit in die Struktur zu verschieben – von teurer Koordination im Betrieb hin zu einer einmaligen, sorgfältigen mathematischen Konstruktion des Datentyps.

Für die Praxis heißt das: Bevor du für ein Feature reflexhaft nach Locks, Transaktionen oder einem Konsens-Cluster greifst, stelle die CALM-Frage – ist mein Problem monoton? Kann jede Operation nur „hinzufügen", nie „widerrufen"? Falls ja, kannst du wahrscheinlich auf Koordination verzichten, die Latenz drücken und echte Offline-Fähigkeit gewinnen, indem du einen passenden CRDT wählst. Falls nein – wenn eine globale Invariante wie ein nicht-negativer Saldo oder eine Eindeutigkeitsbedingung im Spiel ist –, dann sagt dir dasselbe Theorem ehrlich, dass kein Trick der Welt dir die Koordination erspart. Diese Klarheit, wann man koordinieren muss und wann nicht, ist selbst dann wertvoll, wenn man am Ende gar kein CRDT einsetzt.

Eine Frage zum Nachdenken

Denk an ein System, das du kennst oder baust. Welche seiner Datenoperationen sind in Wahrheit monoton – reines Hinzufügen von Fakten, das nie zurückgenommen werden muss – und bei welchen hast du eine Nicht-Monotonie (ein „darf nur einmal", ein „nie darunter", ein „das Neue ersetzt das Alte") vielleicht unbewusst so behandelt, als bräuchte sie zwingend eine zentrale Wahrheit, obwohl sie sich auch monoton umformulieren ließe?

Querverweise im Vault

• Die Ordnung ohne Uhr: Lamport-Zeitstempel, Vektoruhren und die Kausalität verteilter Systeme – die kausale Ordnung und Vektoruhren, auf denen operationsbasierte CRDTs aufbauen.
• Wie Maschinen sich einig werden: Verteilter Konsens von FLP über Paxos zu Raft – der koordinationsbasierte Gegenpol; CRDTs sind der Versuch, ihn zu vermeiden.
• Das Logbuch der Wahrheit: Event Sourcing und CQRS verstehen – operationsbasierte CRDTs sind im Kern ein verteiltes, kommutatives Ereignis-Log.
• Der Ring, der die Last verteilt: Consistent Hashing und die Kunst des sanften Umzugs – Dynamo, die Heimat von Eventual Consistency und Siblings.
• Der Baum, der die Wahrheit verdichtet: Merkle-Bäume und die Kunst der effizienten Integritätsprüfung – Anti-Entropie, die Repliken effizient abgleicht.
• Schreiben statt Suchen – Log-Structured Merge-Trees und die Umkehrung der Datenbank – eine verwandte Speicher-Engine hinter Riak und Cassandra.

Quellen

• Shapiro, Preguiça, Baquero, Zawirski: Conflict-free Replicated Data Types, SSS 2011 (INRIA/LIP6): https://www.lip6.fr/Marc.Shapiro/papers/2011/CRDTs_SSS-2011.pdf
• Springer-Fassung (SSS 2011): https://link.springer.com/chapter/10.1007/978-3-642-24550-3_29
• Almeida, Shoker, Baquero: Delta State Replicated Data Types (2016): https://arxiv.org/pdf/1603.01529
• Bieniusa et al.: An optimized conflict-free replicated set (2012): https://arxiv.org/pdf/1210.3368
• Hellerstein, Alvaro: Keeping CALM: When Distributed Consistency Is Easy, CACM 2020 (arXiv 2019): https://arxiv.org/pdf/1901.01930 · https://cacm.acm.org/research/keeping-calm/
• Kleppmann et al.: The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing (2023): https://arxiv.org/pdf/2305.00583
• Litt, Kleppmann et al.: Peritext: A CRDT for Collaborative Rich Text Editing (2022): https://dspace.mit.edu/bitstream/handle/1721.1/147641/3555644.pdf
• Redis Docs: Active-Active geo-distributed Redis (CRDBs): https://redis.io/docs/latest/operate/rs/databases/active-active/
• Riak Docs: Concept: Data Types (CRDTs): https://docs.riak.com/riak/kv/2.2.3/learn/concepts/crdts/index.html
• CRDT.tech – Papierverzeichnis: https://crdt.tech/papers.html

← All articles