Ich lag falsch. CRDT ist die Zukunft.

 (josephg.com)
24 Punkte von xguru 2020-10-05 | 10 Kommentare | Auf WhatsApp teilen

Ein Google-Wave-Entwickler erzählt über Conflict-free Replicated Data Types

→ CRDT: eine Datenstruktur, die in Echtzeit-Kollaborationstools gleichzeitiges Bearbeiten unterstützt

  • Wave basierte auf OT (Operational Transform): Es wird eine chronologische Liste aller Änderungen gespeichert. Das ist wie ein git rebase in Echtzeit.

  • Eines der Probleme von OT ist, dass ein zentralisierter Server bzw. eine zentrale DB nötig ist

→ Das ist vermutlich auch der Grund, warum in Google Docs (ebenfalls OT-basiert), wenn sich viele Menschen in einem Dokument sammeln, die Meldung erscheint: „Dieses Dokument ist überlastet und kann nicht bearbeitet werden“?

→ Umgehen lässt sich das durch Aufteilen des Dokuments oder durch Retry-Loops bei DB-Transaktionen (das Serialisierungsproblem wird damit an die DB delegiert)

→ Aber das ist nicht perfekt. In Wave haben viele Personen gleichzeitig editiert, und es funktionierte zwar, hatte aber viele Bugs. Es war zu komplex.

  • Der Aufstieg von CRDT

→ Der von Wave verwendete Algorithmus wurde 1995 erfunden. Es wurde weiter daran geforscht, OT zuverlässig zum Laufen zu bringen, aber CRDT ist vielversprechender.

→ CRDT verfolgt einen anderen Ansatz und ermöglicht Echtzeit-Bearbeitung ohne zentrale DB

→ Die früher kritisierten Punkte Geschwindigkeit/Kapazität/Funktionen/Komplexität haben sich alle verbessert

  • Geschwindigkeit: Moderne CRDTs (Automerge / RGA oder y.js / YATA) ermöglichen heute Abfragen in log(n)

  • Kapazität: Martins Columnar-Encoding kann ungefähr mit dem 1,5- bis 2-Fachen der Dokumentgröße speichern.

  • Funktionen: Theoretisch sind Rewinding und Replaying möglich. Natürlich hat das bisher noch niemand implementiert.

  • Komplexität: Implementierungen von CRDT sind zwar wohl größer als die von OT, aber der Unterschied ist nicht groß

→ Diese Verbesserungen sollen bald in Automerge verfügbar sein

  • Für Echtzeit-Editing werden OT und verwandte Arbeiten traurigerweise wohl nicht mehr nötig sein

→ Alle Funktionen von OT lassen sich in CRDT unterbringen, aber umgekehrt ist das nicht möglich

→ Der Vorteil von OT ist, dass es gut zu zentralisierter Software passt, aber verteilte Algorithmen funktionieren auch in zentralisierten Ansätzen gut

→ Hochwertige CRDTs, die in WASM laufen, werden schneller sein als OT-Implementierungen in JS

  • Jetzt ist der Zeitpunkt gekommen, schlanke und schnelle CRDTs zu bauen.

→ Der akademische Teil ist nahezu abgeschlossen, jetzt ist der Zeitpunkt für großartige kick-ass-Implementierungen gekommen

Verwandte Beiträge

10 Kommentare

 
hackerwins 2020-10-05

Ich bin Hong Young-taek und entwickle das Projekt Yorkie.

Auch Yorkie, ein Dokumentenspeicher für Apps zur gemeinsamen Bearbeitung, basiert auf CRDT.

https://github.com/yorkie-team/yorkie
 
iolothebard 2020-10-05

Ich lag falsch. CRDT ist die Zukunft.

Mit OT kann man Undo/Redo quasi kostenlos mitnehmen ... bei CRDT bleibt nur der Weg über Snapshots ...
 
xguru 2020-10-05

Bei Automerge unterstützt bereits die Bibliothek selbst undo/redo. Für die Implementierenden ist das wahrscheinlich schwierig, aber aus Sicht derjenigen, die die Bibliothek nutzen, na ja, haha.
 
ffdd270 2020-10-05

https://www.notion.so/sihawn/CRDT-1dc1af26d60144c09eadd178e0ae6e0d

Ich hatte die vollständige Übersetzung schon gemacht, aber dann vergessen, sie hochzuladen ;_; Ich habe sie einmal auf Basis von Papago durchgelesen und nur die Stellen angepasst, die unnatürlich klangen. Falls ihr wissen möchtet, wie sich der Gesamteindruck liest, schaut bitte in den obigen Link~

Um es im Kommentarfenster zu posten, ist es ... viel zu lang ;_; Deshalb stelle ich es euch als Notion-Link zur Verfügung.
 
ffdd270 2020-10-05

Wenn ich so darüber nachdenke, könnte auch Notion CRDT verwenden!
 
xguru 2020-10-05

Google Wave/Google Docs/MS Office365 verwenden OT

Figma/Apple Notes sowie Riak/Redis usw. verwenden CRDT
 
xguru 2020-10-05

Wie funktioniert die Multi-User-Technologie von Figma? https://de.news.hada.io/topic?id=814
 
xguru 2020-10-05

Das im Beitrag verlinkte Video des Automerge-Entwicklers Martin Kleppmann, "CRDTs: The Hard Parts", erklärt das wirklich sehr gut.

Am Anfang werden OT und CRDT gut miteinander verglichen und erklärt. Im späteren Teil geht es dann tiefer in die Implementierung von CRDTs.

https://www.youtube.com/watch?v=x7drE24geUw

Eine CRDT-Bibliothek, die man verwendet, wenn man mit JS Kollaborationstools baut
 
xguru 2020-10-05

Ich lag falsch. CRDT ist die Zukunft.

Towards collaboration system: Vom OT-Algorithmus zu einem CRDT-System

https://deview.kr/2013/detail.nhn?topicSeq=66

Unter den Präsentationen aus Korea ist dies wohl fast die einzige, die sich mit CRDT beschäftigt.
 
hackerwins 2020-10-06

Herr Hyeongeol, der diese Präsentation gehalten hat, hat das im Text erwähnte RGA entwickelt.

Auch Yorkie hat den Listendatentyp auf Basis von RGA implementiert.

https://github.com/yorkie-team/yorkie/issues/2