CRDT steht für Conflict-free Replicated Data Type (konfliktfreier replizierter Datentyp): Eine Datenstruktur, die auf mehreren Repliken unabhängig verändert werden kann und ohne zentrale Koordination automatisch wieder in denselben Zustand konvergiert. Der Begriff und die systematische Theorie stammen von Marc Shapiro, Nuno Preguiça, Carlos Baquero und Marek Zawirski („A Comprehensive Study of Convergent and Commutative Replicated Data Types", 2011).
Die Grundidee
Normale Datenstrukturen sind nicht für Replikation gebaut: Zwei Geräte, die gleichzeitig denselben Zähler erhöhen, erzeugen einen Konflikt, den ein Server erst nachträglich auflösen muss. Ein CRDT definiert seine Operationen so, dass sie kommutativ (Reihenfolge egal) und idempotent (Wiederholung schadet nicht) sind. Dadurch liefert jede Zusammenführung aller Repliken — egal in welcher Reihenfolge — dasselbe Ergebnis: Eventual Consistency mit mathematisch garantierter Konvergenz.
Zwei Familien
- CvRDT (state-based / convergent): Repliken tauschen ihren kompletten Zustand aus; ein Merge-Vorgang verbindet beide Zustände über eine Join-Operation. Robust gegen Nachrichtenverlust, dafür größere Übertragungen.
- CmRDT (operation-based / commutative): Repliken tauschen nur Operationen aus, die kommutativ angewendet werden. Effizienter, benötigt aber zuverlässige Übertragung (genau einmal).
Bekannte CRDT-Bausteine
- G-Counter (nur erhöhbarer Zähler) und PN-Counter (erhöhen und senken über zwei getrennte Zähler)
- G-Set (nur hinzufügbare Menge) und OR-Set (Menge mit Löschen durch tombstones)
- LWW-Register (Last-Writer-Wins: der Wert mit dem höchsten Zeitstempel gewinnt)
- Text-CRDTs (Sequenz-Datentypen für kollaboratives Editieren, z.B. RGA oder YATA)
Einsatz in der Praxis
CRDTs stecken in verteilten Datenbanken (Riak, Redis Enterprise Active-Active), in kollaborativen Editoren wie Figma oder den Bibliotheken Automerge und Yjs (lokale Apps mit Offline-Fähigkeit) sowie in Werkzeugen für hochverfügbare Multiplayer-Anwendungen. Sie sind der Gegenentwurf zu Konsens-Algorithmen wie Paxos oder Raft: Konsens koordiniert vor der Entscheidung über einen gemeinsamen Wert, CRDTs verzichten ganz auf Koordination und verschmelzen die Ergebnisse nachträglich — ein klarer CAP-Theorem-Kompromiss zugunsten von Verfügbarkeit. Session-Garantien wie Read-Your-Writes und Monotonic Reads ergänzen CRDTs, wenn zusätzlich die eigene Sicht stabil bleiben soll; in Datenbank-Clustern und Shard-Umgebungen sind beide Ansätze kombinierbar.