Zusammenwachsen ohne Absprache – CRDTs und die Mathematik der konfliktfreien Replikation

Der Aufhänger

Stellen Sie sich vor, drei Menschen tippen gleichzeitig im selben Dokument. Einer sitzt im ICE mit abbrechendem Funkloch, einer im Büro, einer am Küchentisch mit WLAN, das sekundenweise weg ist. Niemand fragt vorher um Erlaubnis, niemand wartet auf einen zentralen Server, der die Reihenfolge festlegt. Trotzdem sehen am Ende alle drei dasselbe Dokument – und zwar nicht ungefähr dasselbe, sondern Zeichen für Zeichen identisch. Kein „Bearbeitungskonflikt", kein Dialog „Version A oder Version B behalten?", keine verlorene Änderung.

Aus Sicht der klassischen Theorie verteilter Systeme klingt das nach einem Widerspruch. Wenn mehrere Kopien derselben Daten unabhängig und gleichzeitig verändert werden dürfen, ohne sich abzusprechen, dann entstehen im Allgemeinen Inkonsistenzen, die sich nachträglich nicht mehr sauber auflösen lassen. Um Datenintegrität wiederherzustellen, muss man dann Änderungen verwerfen – ganz oder teilweise. Genau deshalb dreht sich ein großer Teil der Forschung darum, wie man solche gleichzeitigen Änderungen verhindert: durch Sperren, durch Konsens, durch einen Anführer, der die Reihenfolge diktiert.

CRDTs – Conflict-free Replicated Data Types, konfliktfreie replizierte Datentypen – gehen den umgekehrten Weg. Sie erlauben jede Änderung sofort, überall, ohne Koordination, und garantieren trotzdem, dass alle Kopien am Ende konvergieren. Das Bemerkenswerte daran ist nicht ein cleverer Trick, sondern eine mathematische Einsicht: Wenn man die Zusammenführungs-Operation so entwirft, dass sie bestimmte algebraische Eigenschaften erfüllt, dann kann es gar keinen unauflösbaren Konflikt mehr geben. Die Konvergenz ist dann kein Glücksfall, sondern ein Theorem.

Dieser Artikel erklärt, warum Replikation ohne Koordination normalerweise weh tut, welche mathematische Idee CRDTs dieses Problem entziehen, wie die beiden Grundbauweisen funktionieren, welche konkreten Datentypen es gibt – vom simplen Zähler bis zum kollaborativen Texteditor – und wo die Grenzen und Missverständnisse liegen. Am Ende sollten Sie CRDTs nicht als Zauberei sehen, sondern als das, was sie sind: angewandte Verbandstheorie im Dienst der Cloud.

Das Kernproblem: warum geteilte Daten weh tun

Sobald Daten an mehr als einem Ort liegen, muss man sich entscheiden, was passiert, wenn zwei Orte gleichzeitig etwas anderes über denselben Wert glauben. Das ist keine Randfrage, sondern der harte Kern der verteilten Datenhaltung.

Das berühmteste Werkzeug, um darüber nachzudenken, ist das CAP-Theorem von Eric Brewer: Bei einer Netzwerkpartition – also wenn Teile des Systems einander nicht erreichen können – muss man sich zwischen Consistency (alle sehen denselben, aktuellsten Wert) und Availability (jeder Knoten antwortet weiterhin) entscheiden. Man kann bei einer Partition nicht beides zugleich haben. Klassische, stark konsistente Systeme wählen Konsistenz: Sie verweigern im Zweifel die Antwort oder blockieren, bis wieder Einigkeit herrscht. Das ist der Weg von verteiltem Konsens, wie ihn Paxos und Raft beschreiben – nachzulesen im Vault-Artikel über verteilten Konsens.

Für viele Anwendungen ist diese Verweigerung aber inakzeptabel. Ein Warenkorb, der nicht funktioniert, wenn kurz das Netz zuckt; eine Notiz-App, die offline nichts speichert; ein Chat, der bei Netzwerkschwankungen einfriert – all das verliert Nutzer. Deshalb wählt eine große und praktisch wichtige Klasse von Systemen den anderen Weg: Availability vor sofortiger Konsistenz. Dieser Ansatz heißt optimistische Replikation. Jede Kopie akzeptiert Änderungen sofort und lokal; die Abstimmung zwischen den Kopien geschieht später, asynchron, im Hintergrund. Das Versprechen lautet nicht „immer gleich", sondern „irgendwann gleich" – eventuelle Konsistenz (eventual consistency).

Und genau hier lauert das Problem. „Irgendwann gleich" ist ein schwaches Versprechen. Es sagt nur: Wenn keine neuen Änderungen mehr kommen und alle Nachrichten irgendwann ankommen, sollen die Kopien konvergieren. Es sagt nicht, wie. In der Praxis muss dann eine Konfliktauflösung her, und die ist oft hässlich: „Last write wins" mit einer Uhr, die zwischen Rechnern nie perfekt synchron läuft; manuelle Auswahl durch den Nutzer; oder – wie bei Amazons frühem Dynamo-Warenkorb berüchtigt – das Wiederauferstehen bereits gelöschter Artikel, weil die Zusammenführung schlicht die Vereinigung nahm. Eventuelle Konsistenz ohne saubere Semantik ist ein Versprechen, das man mit Ad-hoc-Heuristiken einlösen muss, und jede Heuristik hat ihre Kanten, an denen Daten stumm verschwinden oder falsch wieder auftauchen.

Die Frage, die CRDTs stellen, ist deshalb präziser: Gibt es eine Teilklasse von Datenstrukturen, bei der die Zusammenführung gleichzeitiger Änderungen immer eindeutig, immer verlustfrei und immer ohne Rückfrage funktioniert? Die Antwort ist ja – und sie ist überraschend elegant.

Die Idee: Konsistenz durch Struktur statt durch Absprache

Formal definiert wurden CRDTs 2011 von Marc Shapiro, Nuno Preguiça, Carlos Baquero und Marek Zawirski, aufbauend auf früheren Arbeiten unter anderem von Baquero und Moura aus den späten 1990er-Jahren. Ihre zentrale Begriffsschöpfung ist die starke eventuelle Konsistenz (Strong Eventual Consistency, SEC).

Der Unterschied zur gewöhnlichen eventuellen Konsistenz ist entscheidend. Gewöhnliche eventuelle Konsistenz sagt nur: Irgendwann werden die Kopien gleich sein – vorausgesetzt, eine Konfliktauflösung sorgt dafür. Starke eventuelle Konsistenz verschärft das zu einer viel härteren Zusage: Zwei Kopien, die dieselbe Menge an Änderungen gesehen haben, sind sofort im selben Zustand – unabhängig von der Reihenfolge, in der die Änderungen eingetroffen sind, und unabhängig davon, ob manche doppelt ankamen. Es gibt keinen Konfliktauflösungs-Schritt mehr, weil es keinen Konflikt gibt. Die Reihenfolge ist egal. Duplikate sind egal. Verzögerungen sind egal.

Wie kann das sein? Die Antwort liegt in der Algebra. Shapiro und Kollegen zeigten: Wenn der Zustand einer Kopie ein Element eines sogenannten Halbverbands (join-semilattice) ist und die Zusammenführung zweier Zustände die kleinste obere Schranke (das join) bildet, dann konvergieren die Kopien zwangsläufig. Konkret muss die Zusammenführungs-Funktion drei Eigenschaften erfüllen:

• Kommutativität: merge(a, b) = merge(b, a). Die Reihenfolge, in der zwei Zustände verschmelzen, spielt keine Rolle. Das erledigt das Problem der Nachrichtenreihenfolge.
• Assoziativität: merge(merge(a, b), c) = merge(a, merge(b, c)). Es ist egal, wie man Zustände gruppiert. Das erledigt das Problem, dass verschiedene Kopien Updates in verschiedenen Bündeln erhalten.
• Idempotenz: merge(a, a) = a. Denselben Zustand zweimal einzumischen ändert nichts. Das erledigt das Problem doppelt zugestellter Nachrichten.

Diese drei Eigenschaften zusammen sind exakt das, was einen Halbverband ausmacht. Und weil sie erfüllt sind, ist der zusammengeführte Zustand invariant gegenüber Umsortierung, Umgruppierung und Duplizierung von Nachrichten. Das ist der ganze Zaubertrick: Man verlangt nicht mehr, dass das Netzwerk sich ordentlich benimmt. Man baut die Datenstruktur so, dass ihr das schlechte Benehmen des Netzwerks nichts anhaben kann.

Ein Bild dafür: Denken Sie an das Maximum zweier Zahlen. max(3, 5) = max(5, 3) (kommutativ), max(max(3,5),2) = max(3,max(5,2)) (assoziativ), max(5,5) = 5 (idempotent). Egal in welcher Reihenfolge und wie oft Sie Zahlen ins Maximum werfen – das Ergebnis ist immer dieselbe größte Zahl. Ein CRDT ist im Kern nichts anderes als eine sorgfältig konstruierte Verallgemeinerung dieses Prinzips auf reichhaltigere Datentypen: Zähler, Mengen, Register, Listen, ganze Textdokumente.

Das einfachste denkbare CRDT illustriert das perfekt: ein Ereignis-Flag, das nur von falsch auf wahr springen kann. „Wahr" heißt: Das Ereignis ist mindestens einmal eingetreten. Ein einmal eingetretenes Ereignis kann nicht un-eintreten. Die Zusammenführung lautet schlicht „wahr gewinnt". Egal, welche Kopie das Ereignis sah und welche nicht, egal in welcher Reihenfolge man mischt – das Ergebnis ist immer dasselbe. Ein Bit, ein Verband, garantierte Konvergenz.

Zwei Wege zum selben Ziel: Zustand und Operation

Es gibt zwei grundlegende Bauweisen für CRDTs, und sie unterscheiden sich darin, was zwischen den Kopien über das Netz geschickt wird.

Zustandsbasierte CRDTs (CvRDTs)

Zustandsbasierte CRDTs – auch convergent replicated data types oder CvRDTs genannt – schicken bei jeder Synchronisation ihren kompletten lokalen Zustand an andere Kopien. Der Empfänger führt den empfangenen Zustand per merge in seinen eigenen ein. Damit das konvergiert, müssen merge die drei genannten Verbandseigenschaften erfüllen und die lokale Update-Funktion muss den Zustand bezüglich der Verbandsordnung monoton wachsen lassen.

Der große Vorteil: Die Anforderungen an das Netz sind minimal. Ein simples Gossip-Protokoll genügt – Kopien tauschen gelegentlich ihren Zustand aus, Nachrichten dürfen verloren gehen, doppelt ankommen, in beliebiger Reihenfolge eintreffen. Weil merge assoziativ ist, enthält das Verschmelzen mit dem Zustand einer Kopie automatisch alle je auf dieser Kopie gemachten Änderungen. Der Nachteil: Man überträgt womöglich große Zustände, obwohl sich nur wenig geändert hat.

Operationsbasierte CRDTs (CmRDTs)

Operationsbasierte CRDTs – commutative replicated data types oder CmRDTs – kennen gar keine merge-Funktion. Statt Zuständen übertragen sie die Operationen selbst und wenden sie bei jeder Kopie an. Statt „mein Zähler steht jetzt bei 42" sendet man „addiere 10". Die Operationen müssen kommutativ sein; Idempotenz wird nicht verlangt, dafür aber eine stärkere Annahme über das Netz: Jede Operation muss genau einmal und in kausaler Reihenfolge bei jeder Kopie ankommen – nicht verloren, nicht dupliziert.

Der Vorteil: Operationen sind meist winzig verglichen mit dem Gesamtzustand, also spart man Bandbreite – besonders, wenn viele Kopien wenig ändern. Der Preis: Man braucht eine zuverlässige, kausal ordnende Zustellinfrastruktur. Kausale Reihenfolge bedeutet, dass eine Operation, die logisch von einer anderen abhängt, nie vor dieser ankommt – ein Konzept, das eng mit der logischen Zeit verwandt ist, wie sie auch Spanners TrueTime auf andere Weise beherrscht (siehe Vault-Artikel).

Die beiden Ansätze sind theoretisch gleichmächtig – jeder kann den anderen nachbilden. In der Praxis wählt man je nach Netz und Datentyp. Zustandsbasiert ist robuster und einfacher zu implementieren, operationsbasiert ist sparsamer.

Delta-CRDTs: das Beste aus beiden Welten

Der offensichtliche Schwachpunkt zustandsbasierter CRDTs – das ständige Verschicken des kompletten Zustands – wurde mit Delta-State-CRDTs entschärft, eingeführt von Almeida, Shoker und Baquero (2015/2018). Die Idee: Statt des ganzen Zustands schickt man nur die jüngsten Änderungen als kleine Delta-Fragmente, die aber selbst wieder gültige Verbandselemente sind und per merge eingemischt werden. So erreicht man die Bandbreiten-Sparsamkeit der operationsbasierten Variante bei der robusten Semantik der zustandsbasierten. Die meisten produktiven Systeme – etwa Riak und Automerge – nutzen intern Delta-Techniken.

Der Werkzeugkasten: konkrete CRDTs

Die Theorie wird greifbar, wenn man sieht, wie einzelne Datentypen konstruiert sind. Ein wiederkehrendes Entwurfsmuster ist dabei: komplexe CRDTs aus einfacheren zusammensetzen.

Zähler

Ein naiver verteilter Zähler funktioniert nicht: Wenn zwei Kopien beide „von 5 auf 6" gehen und man ihre Zustände nimmt, gehen Erhöhungen verloren. Der G-Counter (grow-only counter) löst das, indem er jedem der n Knoten einen eigenen Slot in einem Array gibt. Knoten i erhöht nur P[i]. Der Wert ist die Summe aller Slots. Die Zusammenführung nimmt slotweise das Maximum – und weil jeder Knoten nur seinen eigenen Slot hochzählt, geht keine Erhöhung verloren. Kommutativ, assoziativ, idempotent: erfüllt.

Ein G-Counter kann nur wachsen. Will man auch dekrementieren, kombiniert man zwei G-Counter zum PN-Counter: einen für die Erhöhungen (P), einen für die Verringerungen (N). Der sichtbare Wert ist P minus N. Wichtig – und lehrreich – ist die Beobachtung: Der interne Zustand wächst immer monoton (beide Teilzähler steigen nur), auch wenn der nach außen sichtbare Wert fällt. Diese Trennung zwischen monoton wachsendem Innenleben und beliebig schwankendem Außenwert ist ein Kernprinzip vieler CRDTs.

Mengen

Bei Mengen wird es interessanter, weil Hinzufügen und Entfernen konkurrieren können. Die einfachste Variante, der G-Set, erlaubt nur Hinzufügen; die Zusammenführung ist die Vereinigung. Sauber, aber man kann nie etwas löschen.

Der 2P-Set (two-phase set) fügt eine zweite Menge hinzu – eine „Grabstein"-Menge (tombstone set) für Entferntes. Ein Element gilt als enthalten, wenn es in der Add-Menge, aber nicht in der Remove-Menge ist. Nachteil: Einmal entfernt, bleibt ein Element für immer entfernt – man kann es nicht wieder aufnehmen. Es gilt „remove gewinnt".

Der LWW-Element-Set (last-write-wins) hängt jedem Add und Remove einen Zeitstempel an. Ein Element ist enthalten, wenn sein jüngstes Add jünger ist als sein jüngstes Remove. Vorteil gegenüber 2P-Set: Elemente können nach dem Entfernen wieder aufgenommen werden. Nachteil: Man hängt von synchronisierten Uhren und einer Bias-Regel bei Gleichstand ab.

Die semantisch sauberste verbreitete Variante ist der OR-Set (observed-remove set). Statt Zeitstempeln nutzt er eindeutige Tags: Jedes Hinzufügen erzeugt ein neues, eindeutiges Tag. Ein Entfernen löscht nur genau die Tags, die es zum Zeitpunkt der Beobachtung sah. Ein Element ist enthalten, solange mindestens ein nicht entferntes Add-Tag existiert. Der entscheidende Vorteil: Wenn eine Kopie ein Element entfernt und eine andere es gleichzeitig neu hinzufügt, gewinnt das Hinzufügen – denn das neue Add-Tag hat die Entfernung nie „gesehen". Das entspricht der Intuition der meisten Nutzer viel besser als „remove gewinnt". Genau diese „add wins"-Semantik nutzt etwa der Wettanbieter bet365 in seiner Riak-basierten Datenhaltung.

Die folgende Tabelle fasst den Werkzeugkasten zusammen:

Aus Registern (LWW-Register oder Multi-Value-Register) und diesen Mengen setzt man dann Maps und schließlich ganze Objektbäume zusammen – die Grundlage für Dokumentdatenbanken wie Riak oder für JSON-artige Strukturen in Automerge.

Die harten Teile: Text und Reihenfolge

Zähler und Mengen sind der leichte Teil. Der schwierige – und historisch der eigentliche Motor der CRDT-Forschung, denn CRDTs entstanden aus dem kollaborativen Editieren – ist die geordnete Sequenz: eine Liste, in die an beliebiger Stelle eingefügt und gelöscht wird, während mehrere Autoren gleichzeitig arbeiten. Genau das braucht ein Texteditor.

Das Problem: Positionen als Indizes (Zeichen 5, Zeichen 6 …) funktionieren nicht, weil ein gleichzeitiges Einfügen an früherer Stelle alle nachfolgenden Indizes verschiebt. Die CRDT-Antwort ist, jedem Zeichen eine unveränderliche, eindeutige Position zu geben, die zwischen zwei bestehenden Positionen liegen kann – eine dichte, total geordnete Menge von Bezeichnern. Bekannte Sequenz-CRDTs heißen Treedoc, RGA (Replicated Growable Array), WOOT, Logoot, LSEQ und YATA. Sie unterscheiden sich darin, wie sie diese Positions-Bezeichner erzeugen: als Pfade in einem Baum, als Bruchzahlen zwischen Nachbarn, als verkettete Vorgänger-Referenzen.

Ein Löschen wird dabei meist nicht als echtes Entfernen realisiert, sondern als Grabstein – das Zeichen bleibt als „gelöscht" markiert erhalten, damit gleichzeitige Verweise darauf nicht ins Leere greifen. Das ist korrekt, kostet aber Speicher, weshalb ausgefeilte Implementierungen Grabsteine später aufräumen oder von vornherein kompakter kodieren.

Die Interleaving-Anomalie

Dass ein CRDT konvergiert, heißt nicht, dass das Ergebnis sinnvoll ist. Martin Kleppmann und Kollegen (Gomes, Mulligan, Beresford) haben 2019 eine subtile, aber wichtige Klasse von Fehlern beschrieben: die Interleaving-Anomalie. Wenn zwei Autoren gleichzeitig an derselben Stelle jeweils ein Wort einfügen – etwa „Alice" und „Charlie" – kann ein naives Sequenz-CRDT die Zeichen ineinander verschränken und „Al Ciharcliee" produzieren statt „Alice Charlie" oder „Charlie Alice". Beide Kopien konvergieren zu diesem Kauderwelsch – konsistent, aber unbrauchbar.

Die Forschung zeigte: Logoot, LSEQ, Treedoc und WOOT sind für diese Anomalie anfällig; RGA zeigt eine schwächere Form nur beim Rückwärtstippen. Weidner und Kleppmann bewiesen später sogar, dass es keine List-CRDTs geben kann, die jede Form der Verschränkung vermeiden, und schlugen mit Fugue ein CRDT vor, das das Interleaving zumindest minimiert. Das ist ein schönes Beispiel dafür, dass mathematische Konvergenz nur die halbe Miete ist – die Semantik muss auch der menschlichen Erwartung entsprechen.

Der Wettlauf um Geschwindigkeit

Lange galten CRDTs für Text als theoretisch elegant, aber praktisch zu langsam und speicherhungrig. Das hat sich gedreht. Industrielle Implementierungen schlagen akademische deutlich, weil sie aggressiv optimieren und realistischer testen. Der Vorreiter ist Yjs von Kevin Jahns, das statt eines Baums eine flache, doppelt verkettete Liste nutzt und dadurch enorme Durchsätze erreicht (Größenordnung Zehntausende bis Hunderttausende Operationen pro Sekunde). Sephs berühmte Blog-Serie „CRDTs go brrr" und die moderne Automerge-2.0-Version zeigten, dass eine viertel Million Tastenanschläge in unter einer Sekunde verarbeitet werden können. Damit sind CRDTs für Text endgültig praxistauglich.

Aus der Praxis: wo CRDTs bereits arbeiten

CRDTs sind längst keine Laboridee mehr. Eine Auswahl:

Riak ist eine verteilte NoSQL-Datenbank, die CRDTs (Riak Data Types) als erstklassige Bürger anbietet. Das prominenteste Beispiel: League of Legends nutzt Riaks CRDTs für seinen Ingame-Chat, der 7,5 Millionen gleichzeitige Nutzer und rund 11.000 Nachrichten pro Sekunde bewältigt. Der Wettanbieter bet365 speichert hunderte Megabyte in Riaks OR-Set-Implementierung.

Redis bietet mit „CRDT-enabled databases" (Active-Active-Geo-Replikation) CRDT-Datentypen für global verteilte Schreibzugriffe. SoundCloud veröffentlichte Roshi, einen auf Redis aufgebauten LWW-Element-Set-CRDT für den Aktivitäts-Stream. Auch Azure Cosmos DB kennt CRDT-Datentypen.

Apple verwendet CRDTs in der Notizen-App, um Offline-Bearbeitungen zwischen Geräten zu synchronisieren – die interne Klasse heißt bezeichnenderweise TTMergeableString. TomTom synchronisiert Navigationsdaten zwischen den Geräten eines Nutzers per CRDT. Das Fluid Framework von Microsoft und Teletype für den Atom-Editor bauen kollaborative Echtzeit-Bearbeitung auf CRDTs.

Ein interessanter Grenzfall ist Figma: Es nutzt kein reines CRDT, sondern ein server-autoritatives Last-Writer-Wins-Schema pro Eigenschaft und fractional indexing für geordnete Sequenzen – eine bewusste Design-Entscheidung, die zeigt, dass CRDT-Ideen (LWW-Register, dichte Positionsbezeichner) auch außerhalb reiner CRDT-Systeme prägend sind.

Der vielleicht wichtigste Trend heißt Local-First Software – ein von Kleppmanns Gruppe geprägter Begriff für Anwendungen, deren Daten primär lokal auf dem Gerät leben und bei denen Synchronisation ein Zusatz ist, nicht die Voraussetzung. CRDTs sind das technische Fundament dieser Bewegung, weil sie Offline-Arbeit, sofortige Reaktion und spätere konfliktfreie Zusammenführung ermöglichen. Bibliotheken wie Yjs, Automerge und das neuere Loro treiben diese Idee 2026 in immer mehr Anwendungen.

Grenzen und Missverständnisse

So elegant CRDTs sind – sie sind kein Allheilmittel, und ein paar Missverständnisse halten sich hartnäckig.

CRDTs „lösen" keine Konflikte, sie definieren sie weg. Ein CRDT garantiert, dass alle Kopien zum selben Zustand konvergieren. Es garantiert nicht, dass dieser Zustand der ist, den ein Nutzer gewollt hätte. „Add wins" oder „last write wins" sind Entwurfsentscheidungen mit semantischen Konsequenzen. Bei zwei gleichzeitigen Änderungen desselben Kontostands etwa führt „last write wins" schlicht zum Verlust einer Buchung. CRDTs verschieben das Problem von „technischer Divergenz" zu „semantischer Angemessenheit" – lösen es aber nicht per se.

CRDTs können keine globalen Invarianten erzwingen. Weil jede Kopie ohne Absprache schreibt, kann kein CRDT eine Bedingung wie „der Kontostand darf nie negativ werden" oder „dieser Nutzername darf nur einmal existieren" garantieren. Solche Eindeutigkeits- und Grenzwert-Bedingungen brauchen Koordination – also doch wieder Konsens. CRDTs und Konsens sind keine Konkurrenten, sondern zwei Werkzeuge für zwei unterschiedliche Problemklassen.

Metadaten wachsen. Grabsteine, eindeutige Tags, Positionsbezeichner, Versionsvektoren – all das kostet Speicher, oft mehr als die eigentlichen Nutzdaten. Ein großer Teil der CRDT-Forschung dreht sich darum, diesen Overhead zu begrenzen (optimierte OR-Sets, Delta-Techniken, Grabstein-Bereinigung). Ich bin der Meinung, dass genau dieser Metadaten-Overhead – nicht die Rechenzeit – der wahre limitierende Faktor beim breiten Einsatz von CRDTs ist, auch wenn moderne Implementierungen ihn stark reduziert haben.

Kausale Zustellung ist eine reale Anforderung. Operationsbasierte CRDTs setzen ein Netz voraus, das Operationen genau einmal und kausal geordnet zustellt. Das ist nicht gratis; es braucht Sequenznummern, Versionsvektoren oder eine Middleware, die diese Garantien liefert.

Trotz dieser Grenzen bleibt der konzeptionelle Gewinn enorm: Für die große Klasse von Problemen, bei denen jede Kopie schreiben können soll und semantische „Verschmelzbarkeit" akzeptabel ist, verwandeln CRDTs ein hässliches Betriebsproblem in ein sauberes mathematisches.

Erkenntnis zum Mitnehmen

Die eigentliche Lehre von CRDTs reicht über verteilte Systeme hinaus. Sie lautet: Man kann eine schwierige Laufzeit-Garantie in eine einfache strukturelle Eigenschaft übersetzen. Statt zur Laufzeit mühsam sicherzustellen, dass Nachrichten in der richtigen Reihenfolge, ohne Duplikate und ohne Verlust ankommen, baut man die Datenstruktur einmal so, dass ihr Reihenfolge, Duplikate und Verlust egal sind. Die harte Arbeit wandert vom Betrieb in den Entwurf – und wird dort ein für alle Mal erledigt.

Praktisch heißt das: Wenn Sie das nächste Mal vor einem Synchronisationsproblem stehen – zwei Caches, zwei Geräte, zwei Rechenzentren, die denselben Wert halten –, fragen Sie zuerst, ob Ihre Daten sich als Verband modellieren lassen. Ist die Zusammenführung kommutativ, assoziativ und idempotent? Falls ja, brauchen Sie weder Sperren noch einen Anführer noch eine Konfliktauflösung – Sie brauchen nur ein merge, das ein join ist. Falls nein, wissen Sie sofort, dass Sie echte Koordination brauchen und können sich den Aufwand von Konsens bewusst leisten, statt ihn versehentlich zu umgehen.

CRDTs sind damit weniger eine Technologie als eine Denkweise: Suche nach der algebraischen Struktur, die dein Problem harmlos macht.

Reflexionsfrage

Welche Daten in Ihren eigenen Systemen behandeln Sie heute mit Sperren, Transaktionen oder „last write wins", obwohl sie sich in Wahrheit als konfliktfrei verschmelzbarer Verband modellieren ließen – und welche brauchen die Koordination wirklich, weil eine globale Invariant auf dem Spiel steht?

Querverweise im Vault

• Wie Maschinen sich einig werden: Verteilter Konsens von FLP über Paxos zu Raft – das Gegenstück zu CRDTs: wenn Koordination unvermeidlich ist.
• Der Ring, der die Last verteilt: Consistent Hashing und die Kunst des sanften Umzugs – wie man Daten überhaupt auf viele Kopien verteilt.
• Uhren, die ihre eigene Unsicherheit kennen: Google Spanner, TrueTime und die Beherrschung der Zeit in der Cloud – Zeit und kausale Ordnung in verteilten Systemen.
• Das Logbuch der Wahrheit: Event Sourcing und CQRS verstehen – Zustand als Ergebnis einer Operationsfolge, verwandt mit operationsbasierten CRDTs.

Quellen

• Shapiro, Preguiça, Baquero, Zawirski (2011): Conflict-Free Replicated Data Types, SSS 2011 – die formale Definition und der SEC-Beweis. https://hal.inria.fr/hal-00932836/file/CRDTs_SSS-2011.pdf
• Shapiro et al. (2011): A Comprehensive Study of Convergent and Commutative Replicated Data Types, INRIA RR-7506 – der ausführliche technische Bericht mit allen Datentypen.
• Wikipedia: Conflict-free replicated data type – aktueller Überblick über Bauweisen, Datentypen und Praxis. https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type
• Almeida, Shoker, Baquero (2018): Delta State Replicated Data Types, Journal of Parallel and Distributed Computing. https://arxiv.org/abs/1603.01529
• Kleppmann, Gomes, Mulligan, Beresford (2019): Interleaving anomalies in collaborative text editors, PaPoC 2019. https://martin.kleppmann.com/papers/interleaving-papoc19.pdf
• crdt.tech – kuratierte Sammlung von Papers und Implementierungen (Yjs, Automerge u. a.). https://crdt.tech/

← All articles