CRDT-Wörterbuch: Ein praxisnaher Leitfaden für verteilte Datenstrukturen

• CRDT (Conflict-free Replicated Data Type) ist eine verteilte Datenstruktur, die konsistente Datenzusammenführung ohne Koordination auch bei Netzwerkpartitionen oder gleichzeitigen Änderungen ermöglicht
• Wenn die Datenzusammenführung kommutativ, assoziativ und idempotent ist, konvergieren alle Replikate schließlich zum gleichen Zustand
• Zu den repräsentativen Formen gehören G-Counter, PN-Counter, G-Set, 2P-Set, OR-Set, LWW-Register, MV-Register, RGA, WOOT, Logoot usw., die jeweils unterschiedliche Anforderungen an Hinzufügen, Löschen, erneutes Hinzufügen und Reihenfolgeerhalt abdecken
• Delta CRDT erhöht die Effizienz, indem statt des gesamten Zustands nur Änderungen übertragen werden, und Garbage Collection ist eine zentrale Herausforderung zur Lösung des Problems wachsender Metadaten
• CRDT ist keine perfekte Lösung, wird aber als starke Option für Systeme bewertet, in denen Verfügbarkeit wichtiger ist als sofortige Konsistenz

---

Grundkonzepte von CRDT

• CRDT ist eine Datenstruktur, die in verteilten Umgebungen auch bei gleichzeitigen Änderungen ohne Koordination zusammengeführt werden kann
  • Wenn die Merge-Operation kommutativ (commutative), assoziativ (associative) und idempotent ist, konvergieren alle Replikate zum gleichen Zustand
• Es basiert auf dem Konzept eines Lattice (Verband/Gitter), sodass der Zustand immer nur „nach oben“ fortschreitet
  • Beispiel: Ein G-Counter führt die Zählerstände der einzelnen Replikate per max zusammen und garantiert so eine verlustfreie Summierung
• Bei CRDT gibt es zwei Ansätze: State-based (CvRDT) und Operation-based (CmRDT)
  • CvRDT führt den gesamten Zustand zusammen, CmRDT propagiert Operationen

Wichtige CRDT-Typen

• G-Counter: Zähler, der nur erhöht werden kann; summiert die Werte aller Replikate
• PN-Counter: Unterstützt Zählen in beide Richtungen durch die Kombination von G-Countern für Erhöhung und Verringerung
• G-Set: Menge, zu der nur hinzugefügt werden kann
• 2P-Set: Hinzufügen und Löschen möglich, aber kein erneutes Hinzufügen
• LWW-Element-Set: Der jüngste Vorgang gewinnt auf Basis von Zeitstempeln
• OR-Set: Verwendet eindeutige Tags und führt gleichzeitige Hinzufügungen ohne Datenverlust zusammen, mit Add-wins-Verhalten
• LWW-Register / MV-Register: Zur Speicherung eines einzelnen Werts; LWW hat einen einzelnen Gewinner, MV behält alle gleichzeitigen Werte bei
• OR-Map: Eine Map-Struktur, die OR-Sets pro Schlüssel kombiniert
• RGA / WOOT / Logoot / LSEQ: CRDTs für geordnete Sequenzdaten
  • RGA ist baumbasiert, WOOT basiert auf bidirektionalen Referenzen, Logoot/LSEQ auf Positions-Identifikatoren

Fortgeschrittene CRDT-Konzepte

• Causal CRDTs: Verfolgen Kausalbeziehungen mit Versionsvektoren und ermöglichen präzisere Konflikterkennung
• Delta CRDTs: Verbessern die Netzwerkeffizienz, indem statt des gesamten Zustands nur Änderungen (Deltas) übertragen werden
• Tree CRDTs: Unterstützen die Replikation hierarchischer Datenstrukturen (z. B. Dateisysteme), wobei Eltern-Kind-Beziehungen erhalten bleiben müssen
• Observed-Remove Shopping Cart: Beispiel für einen E-Commerce-Warenkorb, der OR-Set und PN-Counter kombiniert

Das Garbage-Collection-Problem

• CRDTs akkumulieren zur Sicherstellung der Konvergenz kontinuierlich Metadaten, wodurch ein Problem unbegrenzten Wachstums entsteht
  • Beispiel: Tags im OR-Set, Tombstones in RGA
• Es gibt verschiedene Strategien wie zeitbasierte Ablauffristen, konsensbasiertes Löschen, kausales Tracking auf Basis von Versionsvektoren, Obergrenzen für Metadaten sowie Checkpoints/Rebase
• Jede Methode erfordert einen Kompromiss zwischen Sicherheit (Verhinderung von Zombie-Wiederherstellung) und Speichereffizienz

Performance- und Auswahlleitfaden

• Die Speicher- und Zeitkomplexität der einzelnen CRDT-Typen variiert je nach Anzahl der Replikate, Elemente und Tags
  • G-/PN-Counter sind proportional zur Zahl der Replikate, OR-Set proportional zur Zahl der Tags, RGA akkumuliert Tombstones
• Delta CRDT kann die Merge-Performance deutlich verbessern
• Auswahlkriterien:
  • Nur Hinzufügen erforderlich → G-Counter, G-Set
  • Löschen erforderlich, erneutes Hinzufügen nicht nötig → 2P-Set
  • LWW akzeptabel → LWW-Set/Register
  • Gleichzeitige Änderungen beibehalten → OR-Set, MV-Register
  • Reihenfolgeerhalt erforderlich → RGA, Logoot
  • Verschachtelte Struktur → OR-Map

Fazit

• CRDT garantiert Konvergenz ohne Koordination, hat jedoch zunehmende Metadaten und Komplexität als Nachteile
• Es ist nützlich in Systemen mit Priorität auf Verfügbarkeit, und jedes CRDT ist für einen bestimmten Problemtyp optimiert
• In der Praxis wird es parallel zu traditionellen Datenbanken eingesetzt, wobei eine Garbage-Collection-Strategie unverzichtbar ist
• Ein „perfektes CRDT“ gibt es nicht; entscheidend ist die anwendungsbezogene Auswahl

[GN⁺]

Hacker-News-Kommentar

• Einer der interessanten Punkte an CRDTs ist, dass es sich nicht einfach um eine Bibliothek aus mehreren kombinierten Low-Level-CRDTs handelt
  Zum Beispiel ist Automerge selbst ein vollständiges CRDT und garantiert durch mathematische Beweise Konsistenz auch unter Nebenläufigkeit
  Das Automerge-Team verifiziert das Design mit Theorem-Provern wie Isabelle und zielt mit modernen Performance-Techniken aus der Datenbankwelt auf eine schnelle und korrekte Implementierung ab
  Wenn man ein SaaS mit Echtzeit-Kollaboration baut, etwa Notion oder Figma, kann man kollaborative Datenstrukturen direkt einsetzen, ohne die komplexe Theorie verstehen zu müssen
  Als Backend reicht ein einfacher Key-Value-Store, und im Frontend genügt eine einzige Bibliothek

  • Automerge bietet nicht nur in Rust, sondern auch in Javascript und C hervorragende APIs
    Ich habe selbst eine Redis-basierte Automerge-Bibliothek gebaut und konnte mit Pub/Sub einen vollständigen Server für kontinuierliche Synchronisation implementieren
    Mit der WebSocket-Funktion von Webdis habe ich außerdem schnell eine Demo zur Dokumentsynchronisation zwischen mehreren Browsern fertiggestellt
  • Automerge ist großartig, wirkt aber immer noch stark akademisch geprägt
    Wer bessere DX und eine CRDT-basierte Full-Stack-DB möchte, dem empfehle ich Triplit.dev. Die Entwicklung ist etwas langsamer geworden, aber der Funktionsumfang ist inzwischen weitgehend vollständig
  • Dass Automerge ein vollständiges CRDT ist, überrascht mich nicht
    Ich persönlich mag auch Loro, aber es ist immer noch dokumentbasiert und hat daher keine gute Query Engine. Um die gewünschten Daten zu bekommen, muss man bestimmte verschachtelte Elemente direkt angeben
  • Dass Automerge kein Self-Hosting unterstützt, ist für viele Anwendungen eine fatale Einschränkung

• Der Artikel war eine gute Zusammenfassung von den Grundlagen bis zu fortgeschrittenen Konzepten von CRDTs
  Zur Info: Riak wird weiterhin als OpenRiak gepflegt

  • Von OpenRiak habe ich gerade zum ersten Mal gehört, und es freut mich, dort frühere Kollegen beteiligt zu sehen. Basho war wirklich eine Gruppe herausragender Engineers

• Ich habe in den letzten zwei Jahren selbst an CRDTs gearbeitet, dabei aber festgestellt, dass es zu viele Trade-offs gibt, und bin am Ende auf ein ID-basiertes OT-Framework umgestiegen
  Ich werde diesen Dienstag Docnode.dev launchen. Ich würde mich über Feedback freuen
  Künftig plane ich außerdem einen CRDT-Modus für Situationen, in denen P2P nötig ist

  • Mich würde interessieren, welche Trade-offs am problematischsten waren

• CRDTs oder OT sollen Situationen lösen, in denen mehrere Personen gleichzeitig denselben Absatz bearbeiten, aber in der Praxis kommt so etwas fast nie vor

  • Systeme ohne solche Funktionen führen aber oft dazu, dass Cursor sich im selben Satz überlagern und dadurch Inhalte verloren gehen oder Zeit verschwendet wird

• Das in diesem Artikel erwähnte OR-Set ähnelt der Merge-Methode, die Monotone schon ab 2005 verwendet hat
  Weiteres dazu findet sich in der MarkMerge-Dokumentation

• CRDTs sind immer noch ein Bereich, den man selbst implementieren muss
  Ich habe vor zwei Monaten, inspiriert von diamond types, selbst eine sequenzbasierte CRDT-Engine gebaut
  Ich habe AI um Hilfe gebeten, aber bei solchen logikzentrierten Problemen war sie überhaupt keine Hilfe
  Ich habe das Gefühl, dass wir Blackbox-Tests brauchen, um zu überprüfen, ob LLMs neue Logik tatsächlich verstehen können

  • Mich würde interessieren, warum man nicht einfach etwas wie Loro verwendet

• Der Artikel war großartig, aber ich finde, ein Glossar braucht unbedingt einen Index

• Ich frage mich, ob CRDTs am Ende nicht einfach Merge-Konflikte aus der DB in die Anwendungslogik verschieben

  • CRDTs können auch innerhalb der DB entworfen werden. Genau das war bei Riak das Ziel
    Wenn sie korrekt geschrieben sind, ist automatische Konfliktauflösung möglich, unabhängig davon, in welcher Schicht sie liegen
  • Ich entwerfe ebenfalls eine Graph-DB, die CRDT-Techniken in PostgreSQL einsetzt
    Das größte Problem war die Behandlung von UNIQUE-/PRIMARY-KEY-Konflikten
    Das lässt sich lösen, indem man jedem Server einen ID-Namespace zuweist und beim ersten Erstellen den Sieger bestimmt; bei Konflikten wird der Name geändert oder der Eintrag gelöscht
    Mit einem EAV-Schema lässt sich Graph-Traversal in SQL mithilfe von rekursiven CTEs leicht umsetzen
    Allerdings hat PostgreSQL keinen ANY-Typ, wodurch sich Objekte mit sehr unterschiedlichen Eigenschaften nur schwer darstellen lassen, und auch FOREIGN-KEY-Funktionalität muss man selbst implementieren
    Trotzdem eignet sich die EAV-Struktur gut für Meta-Schema-Designs wie Vererbung
    Es wäre schön, wenn man in PostgreSQL CRDT-Typen direkt definieren könnte, aber derzeit lassen sich Monoid-Operationen nicht einschränken
    Letztlich müssen CRDTs für Nicht-Schlüssel-Spalten in der Anwendungsschicht behandelt werden
    Kurz gesagt: CRDTs lassen sich auch innerhalb eines RDBMS implementieren, aber je nachdem, wo die Business-Logik liegen soll, fällt der Ansatz unterschiedlich aus