Are CRDTs suitable for shared editing? | Hacker News
CRDTs are often praised as the "holy grail" for building collaborative applications because they don't require a central authority to resolve sync conflicts. They open up new possibilities to scale the backend infrastructure and are also well-suited as a data-model for distributed apps that don't require a server at all.
However, several text editor developers report not to use them because they impose a too significant overhead.
Just recently, Marijn Haverbeke wrote about his considerations against using CRDTs as a data model for CodeMirror 6:
[..] the cost of such a representation is significant, and in the end, I judged the requirement for converging positions to be too obscure to justify that level of extra complexity and memory use. (source)
The Xi Editor used a CRDT as its data model to allow different processes (syntax highlighter, type checker, ..) to concurrently access the editor state without blocking the process. They reverted to a synchronous model because ..
[..] CRDT is not pulling its (considerable) weight. (source)
Apparently, everyone recognizes that CRDTs have a lot of potential, but concluded that the memory overhead of using them must be too expensive for real-world applications.
They bring up a fair point. Most CRDTs assign a unique ID to every character that was ever created in the document. In order to ensure that documents can always converge, the CRDT model preserves this metadata even when characters are deleted.
This seems to be particularly expensive in dynamic languages like JavaScript. Other languages allow you to efficiently represent all those characters and IDs in-memory using structs (e.g. C or Rust). In JavaScript, everything is represented as an Object - basically a key-value map that needs to keep track of all its keys and values. CRDTs assign multiple properties to every single character in the document to ensure conflict resolution. The memory overhead of merely representing a document as a CRDT could be immense.
Every user-interaction creates more metadata that the CRDT needs to retain in order to ensure conflict resolution. It is not uncommon that CRDTs create millions of objects to store all this metadata. The JavaScript engine manages these objects on the heap, checks if they are referenced, and, if possible, garbage collects them. Another major problem is that with an increasing number of object creations, the cost of creating additional objects increases exponentially. This is shown in the following graphic:
Average time to create one object increases with the number of objects on the heap
So the question arises if CRDTs are actually suitable for shared editing on the web, or if they impose a too significant cost to be viable in practice.
In case you don't know me, I'm the author of a CRDT implementation named Yjs, that is specifically designed for building shared editing applications on the web.
In this article, I will introduce you to a simple optimization for CRDTs and examine the exact performance trade-off of using Yjs for shared editing. I hope to convince you that the overhead is actually very small even for large documents with long edit histories.
Yjs is a framework for building collaborative applications using CRDTs as the data model. It has a growing ecosystem of extensions that enable shared editing using different editors (ProseMirror, Remirror, Quill, CodeMirror, ..), different networking technologies (WebSocket, WebRTC, Hyper, ..), and different persistence layers (IndexedDB, LevelDB, Redis, ..). Most shared editing solutions are tied to a specific editor and to a specific backend. With Yjs, you can make any of the supported editors collaborative and exchange document updates through your custom communication channel, over a peer-to-peer WebRTC network, or over a scalable server infrastructure. My vision for this project is that you can simply compose your collaborative application using the technologies that make sense for your project.
This is not just some cool prototypical side-project. Yjs is a battle-proven technology that is used by several companies to enable collaboration. I'm only mentioning my sponsors here: