Konfliktfreie replizierte Datentypen (CRDTs) sind eine Klasse von Datenstrukturen, die eine nahtlose Zusammenarbeit und Datensynchronisierung in verteilten Systemen ermöglichen und kollaborative Aktualisierungen ohne Konflikte ermöglichen. CRDTs sind darauf ausgelegt, letztendliche Konsistenz über mehrere Datenreplikate hinweg zu erreichen und sicherzustellen, dass selbst bei unabhängigen Aktualisierungen alle Replikate in den gleichen Zustand konvergieren, ohne dass komplexe Konfliktlösungsmechanismen erforderlich sind.

In diesem Blog-Beitrag befassen wir uns mit CRDTs, untersuchen ihre Verwendung und Typen, verstehen, wie sie funktionieren, und lernen, wie man sie implementiert, wobei der Schwerpunkt auf JavaScript und der leistungsstarken Yjs-Bibliothek liegt.

Anwendungsfälle von CRDTs

CRDTs sind besonders nützlich in Szenarien, in denen Echtzeit-Zusammenarbeit und Offline-Unterstützung von entscheidender Bedeutung sind:

1. Kollaborative Texteditoren: Google Docs, Notion und Etherpad verwenden CRDT-ähnliche Strukturen für die Echtzeitbearbeitung.
2. Kollaborative Design-Tools: Figma, ein beliebtes webbasiertes Design-Tool, verwendet CRDTs, um die Zusammenarbeit bei Designprojekten in Echtzeit zu ermöglichen. Mehrere Designer können gleichzeitig an derselben Datei arbeiten, wobei Änderungen nahtlos von allen Benutzern synchronisiert werden.
3. Verteilte Datenbanken: RxDB und Riak verwenden CRDTs für eine konfliktfreie Replikation.
4. Multiplayer-Spiele: Zur Aufrechterhaltung eines konsistenten Spielstatus für alle Spieler.

Arten von CRDTs

Es gibt zwei Haupttypen von CRDTs:

1. Zustandsbasierte CRDTs: Diese replizieren den gesamten Zustand der Datenstruktur. Die Zusammenführung erfolgt durch Vergleichen und Abgleichen der Zustände verschiedener Replikate.
2. Operationsbasierte CRDTs: Diese replizieren die an der Datenstruktur durchgeführten Operationen. Die Zusammenführung erfolgt durch die kommutative Anwendung von Operationen aus verschiedenen Replikaten.

Wie CRDTs funktionieren

CRDTs (Conflict-free Replicated Data Types) arbeiten nach Prinzipien, die letztendliche Konsistenz über alle Replikate der Daten hinweg gewährleisten, selbst wenn gleichzeitig Aktualisierungen vorgenommen werden oder Netzwerkpartitionen auftreten. Lassen Sie uns tiefer in die Mechanik eintauchen:

Schlüsseleigenschaften

1. Kommutativität: Diese Eigenschaft stellt sicher, dass die Reihenfolge der Operationen keinen Einfluss auf das Endergebnis hat. Beispielsweise führt in einem Zähler CRDT das Erhöhen um 2 und dann um 3 zum gleichen Ergebnis wie das Erhöhen um 3 und dann um 2.
2. Assoziativität: Dies bedeutet, dass die Gruppierung von Operationen keine Rolle spielt. Wenn wir noch einmal das Gegenbeispiel verwenden, ist (1 2) 3 dasselbe wie 1 (2 3).
3. Idempotenz: Die mehrfache Anwendung derselben Operation hat die gleiche Wirkung wie die einmalige Anwendung. Dies ist entscheidend für den Umgang mit doppelten Nachrichten in verteilten Systemen.

Konfliktlösung

CRDTs lösen Konflikte automatisch durch Design:

• Bei zustandsbasierten CRDTs (CvRDTs) wird dies durch eine Zusammenführungsfunktion erreicht, die die Zustände zweier Replikate kombiniert. Diese Zusammenführungsfunktion muss kommutativ, assoziativ und idempotent sein.
• Bei operationsbasierten CRDTs (CmRDTs) sind Operationen kommutativ konzipiert, um sicherzustellen, dass ihre Anwendung in beliebiger Reihenfolge zum gleichen Endzustand führt.

Logische Uhren

Viele CRDT-Implementierungen verwenden logische Uhren (z. B. Versionsvektoren oder gepunktete Versionsvektoren), um den kausalen Verlauf von Vorgängen zu verfolgen. Dies hilft bei der Bestimmung der Reihenfolge gleichzeitiger Vorgänge und bei der Identifizierung, welche Aktualisierungen ein Replikat bereits gesehen hat.

Verwenden von CRDTs in JavaScript mit Yjs

Die Implementierung von CRDTs von Grund auf kann komplex sein. Es stehen jedoch Bibliotheken zur Verfügung, die den Prozess vereinfachen. Für JavaScript ist Yjs eine der beliebtesten CRDT-Bibliotheken. Es handelt sich um eine leistungsstarke CRDT-Implementierung, die verschiedene Datentypen unterstützt. Lassen Sie uns mit Yjs eine einfache Aufgabenlistenanwendung erstellen und simulieren, dass mehrere Benutzer im Speicher an demselben Dokument arbeiten.

Hier ist ein Beispiel für die Implementierung einer gemeinsamen Aufgabenliste mit Yjs:

Lassen Sie uns die erstellten Ydocs verwenden:

In diesem Beispiel erstellen wir zwei Yjs-Dokumente (ydoc1 und ydoc2), um zu simulieren, dass zwei Benutzer an derselben Aufgabenliste arbeiten. Jedes Dokument verfügt über eine eigene gemeinsame Karte für die Aufgaben.

Wir definieren Funktionen zum Hinzufügen, Aktualisieren und Löschen von Aufgaben sowie eine syncDocs-Funktion zum manuellen Synchronisieren des Status zwischen den beiden Dokumenten. Dies simuliert, was in einer Netzwerkumgebung passieren würde, in der Updates zwischen Clients ausgetauscht werden.

Abschluss

CRDTs bieten eine leistungsstarke Lösung für die Erstellung kollaborativer, verteilter Anwendungen, die nahtlos online und offline funktionieren können. Obwohl die zugrunde liegenden Konzepte komplex sein können, erleichtern Bibliotheken wie Yjs Entwicklern die Nutzung der Leistungsfähigkeit von CRDTs in ihren Anwendungen. Mit zunehmender Verbreitung verteilter Systeme wird das Verständnis und die Nutzung von CRDTs für Entwickler zu einer immer wertvolleren Fähigkeit.

Nützliche Links

1. Yjs
2. CRDT
3. Tiptap – Ein kollaborativer Texteditor