CRDTs ermöglichen es Replikaten, auseinanderzulaufen und dennoch ohne Sperren zu konvergieren

Die Bearbeitung durch mehrere Nutzer steht vor einem grundlegenden Problem: Wenn zwei Personen dasselbe Dokument offline oder über verschiedene Verbindungen bearbeiten, ändern sich beide Kopien, und jemand muss sie in Einklang bringen. Herkömmliche Ansätze sperren entweder Teile des Dokuments – was die Zusammenarbeit blockiert – oder verwenden operationale Transformation, deren Zustandskombinationen explodieren und deren Korrektheit bekanntermaßen schwer zu beweisen ist.

Im Jahr 2011 schlugen Marc Shapiro und Kollegen konfliktfreie replizierte Datentypen (CRDTs) vor: Datenstrukturen, die so konstruiert sind, dass gleichzeitige Aktualisierungen kommutieren. Wenn jede Aktualisierung kommutiert und Zusammenführungen assoziativ sind, können auseinandergelaufene Replikate in beliebiger Reihenfolge zusammengeführt werden und konvergieren dennoch zu einem identischen Zustand – ohne zentrale Koordination und ohne Konfliktdialog. Register, Zähler, Mengen und Texteditoren lassen sich alle auf diese Weise aufbauen.

Die Theorie verfestigte sich in den folgenden Jahren: Das OpSets-Papier von 2018 von Martin Kleppmann und Kollegen schuf ein ausführbares Framework, das replizierte Datentyp-Algorithmen mechanisch verifiziert, legte eine Korrektheitseigenschaft für kollaborativen Text offen, die mehrere veröffentlichte Algorithmen verletzten, und spezifizierte eine atomare Verschiebeoperation, die zuvor ohne Sperren für unmöglich gehalten wurde.

Produktionssysteme übernahmen die Idee. Figmas Multiplayer-Engine ist ausdrücklich von der CRDT-Forschung inspiriert: Ihr serverautoritatives Design pro Eigenschaft funktioniert wie ein Last-Writer-Wins-Register und wurde gewählt, nachdem das Unternehmen operationale Transformation als unnötig komplex verworfen hatte. Redis, Riak und Cosmos DB liefern CRDT-basierte Datentypen aus, und Apples Notes verwendet CRDTs, um Offline-Änderungen zwischen Geräten zu synchronisieren.

Den Datentyp durch sein Design zusammenführungs-kommutativ machen

Kommutative Zusammenführungen machen das Ergebnis unabhängig von der Reihenfolge der Aktualisierungen

Replikate können offline bearbeitet werden und ohne zentrale Autorität konvergieren

Mechanische Verifikation ersetzte handgewedelte Korrektheitsbeweise

Produkte im Figma-Stil erhielten Echtzeit-Zusammenarbeit ohne die Komplexität von OT

Wenn die Koordination der Engpass ist, gestalte die Daten so um, dass Koordination unnötig wird: Wähle Operationen, deren Ergebnisse reihenfolgeunabhängig sind, und gleichzeitige Nutzer erhalten Konsistenz gratis.

CRDTs sind heute die Standardantwort für Offline-First-Zusammenarbeit und -Replikation: Figmas Multiplayer-Synchronisierung, Apple Notes, die Datentypen von Redis und Riak sowie Peer-to-Peer-Bearbeitungswerkzeuge bauen auf der Idee auf, und die Forschungslinie setzt sich mit den schwierigen Teilen der Textbearbeitung, Baumverschiebungen und byzantinischen Szenarien fort.