A light exploration of collaborative editing and synchronization algorithms
An important feature of Ardoq is that multiple users can edit the same model, i.e. a directed multi-graph. Changes from one user need to be propagated to the others and merged into their models. Collaborative editing (primarily of text) has reportedly been researched for 30 years and is still under active development. Here I share my field notes from learning about it briefly, without much tidying.
Most of the research has been done in the domain of collaborative text editing, which is not the same as editing a graph, but still plenty useful. I am sure there are many approaches but the two most popular ones are Operational Transformation (OT - based on a set of operations (objects describing changes: insert, delete, set attribute) and algorithms that transform these operations accordingly) and Conflict-Free Replicated Data Type (CRDT). TinyMCE’s To OT or CRDT, that is the question is a good, brief introduction. Key points:
OT requires an active connection to a server (TP2, which doesn’t, is too complex)
CRDT is capable of working peer-to-peer with end-to-end encryption
CRDT, contrary to OT, “generally doesn’t need to transform the change itself, only the position of the change” [which, I guess, makes it simpler]
[bold highlight mine] in OT we can define a "split text node" [..] Whereas in CRDT, the changes are more data-focussed and it becomes very clinical. ⇒ “OT trades complexity for the ability to capture the intent; CRDT has less complexity but can only guarantee all clients end with the same data - however that data might not be the intended structure, or even valid for your schema.”
So CRDT are simpler to an extent and do not require a central server but are not so well suited to resolving conflicts in structured data, because they are not so good at preserving the intent of the change. (Though a future research might bring a solution to that.)
A quote from somewhere: “OT comes with the disadvantage that existing OT frameworks are very tailored to the specific requirements of a certain application (e.g. rich text editing)”
Braid - a proposal for a new version of HTTP that transforms it from a state transfer protocol into a state synchronization protocol. Braid puts the power of Operational Transform and CRDTs onto the web, … . There is an implementation in JS and few other languages are in progress.
CRDT.tech describes CRDTs and links to a number of papers and other resources and its implementations page has a list of General-purpose CRDT libraries such as GUN, a graph CRDT (and a p2p JS DB), Yjs, Clojure/Script Schism - with data transfer over WebSockets and/or WebRTC & more. Also lists Distributed databases, file systems, text editors, and more.
The 2016 paper Specification and Complexity of Collaborative Text Editing provides "a precise specification of a replicated list object which models the core functionality of replicated systems for collaborative text editing." Mentions OT and CRDTs but claims "specifications of their desired behavior [17,28] have so far been informal and imprecise, [..]" (thought that might have changed since 2016).
CKEditor’s Lessons learned from creating a rich-text editor with real-time collaboration (2018) and why they too picked OT over CRDTs - a rich resource.
CRDTs are used eg. by Redis and Facebook Apollo
They extended the text-focused OT to provide algorithms and operations that work for a tree data structure. Added operations included rename (e.g. ul → ol), split, merge, wrap, unwrap, insert text (vs. insert element).
Further extensions - a graveyard root for deleted nodes, ops to work on ranges inst. of individual nodes for efficiency, breaking an op into multiple, …
Tag1's Evaluating real-time collaborative editing solutions for a top Fortune 50 company - about OT vs CRTD, and choosing Yjs over CKEDitor / ShareDB / …:
“Unfortunately, implementing OT sucks. There’s a million algorithms with different tradeoffs, mostly trapped in academic papers. The algorithms are really hard and time consuming to implement correctly. […] Wave took 2 years to write and if we rewrote it today, it would take almost as long to write a second time.”
— Joseph Gentle
a former engineer on the Google Wave product and creator of ShareDB [which uses OT]"The key distinction between OT and CRDT is as follows: Consider an edit operation in which a user inserts a word at character position 5 in the document. In operational transformation, if another user adds 5 characters to the start of the document, the insertion is moved to position 10. While this is highly effective for simple plain text documents, complex hierarchical trees such as the document object model (DOM) present significant challenges. CRDT, meanwhile, assigns a unique identifier to every character, and all state transformations are applied relatively to objects in the distributed system. Rather than identifying the place of insertion based on character count, the character at that place of insertion retains the same identifier regardless of where it is relocated to within the document."
ShareDB - - a realtime database backend based on Operational Transformation (OT) of JSON documents. It is the realtime backend for the DerbyJS web application framework.
Yjs - shared data types for building collaborative software like Google Docs and Figma. Yjs is a CRDT implementation that exposes its internal data structure as shared types. Shared types are common data types like Map or Array with superpowers: changes are automatically distributed to other peers and merged without merge conflicts. Yjs is network agnostic (p2p!), supports many existing rich text editors, offline editing, version snapshots, undo/redo and shared cursors.
Other
This Differential Synchronization algorithm (implemented by the JSON diffsync tool) looks interesting, aiming to solve the problem of event passing.
Event passing is also a simple technique. It relies on capturing all user actions and mirroring them across the network to other users. […] A practical challenge with event passing synchronization is that all user actions must be captured.
Perhaps interesting: Towards Trustworthy Collaborative Editing - "we elaborate on how to adapt Byzantine fault tolerance (BFT) mechanisms to enhance the trustworthiness of such applications. It is apparent that traditional BFT algorithms cannot be used directly because it would dictate that all updates submitted by participants be applied sequentially, which would defeat the purpose of collaborative editing."