In xi, there are two issues. One is the cost of the CRDT representation, the other is whether it accurately represents what you're trying to do. Classical implementations of CRDT use a heavyweight node per character in the text, each with its own unique and permanent id. In my research in xi, it became clear to me that more compressed representations are possible, and the xi CRDT is one such: it is an "op" object per edit, but the string itself is just a string.
Lately there has been other work pursuing those compressed representations: Chronofold, I think Martin Kleppmann's automerge has some memory-efficiency work, and there are others.
But at least in the context of xi, this is not where things went wrong. As I've written about (and the author was kind enough to link), it's because CRDT merges aren't a good fit for the problems a code editor is trying to solve, particularly when the "collaborators" are automated processes such as language servers.
In human collaborative editing, it's important to preserve text that's being entered, even in the face of conflict. But when a peer is an automated service, it's much better to drop the edit on the floor and recompute. I'm simplifying here, as it depends on the service - some are history-insensitive, some are sensitive to a small window of history (in the case of automatically inserting indentation, etc), and (speculative) other services may be sensitive to more history.
In addition, the CRDT constrains the data model considerably. In other words, it's unfortunately not a clean abstraction where you can easily add higher level layers on top of the CRDT, but you always have to design those with the CRDT in mind (ie, everything still has to be a monotonic semi-lattice).
So, as with everything else, it's a tradeoff, and it's a question of weighing the pros and cons. I'm glad to see work being done to improve CRDT, but even with a very efficient representation and solid algorithms, the problems with CRDT would be enough for me not to use them in a code editor.
your GitHub comment about "Why CRDT didn't work out as well for collaborative editing in xi-editor" [1] was sent to me several times as an argument not to use CRDTs. I agree with you that CRDTs might be too complex for the way the xi-editor used it (although I loved the idea, and appreciate that you tried it).
But the title of the Hackernews post tells a very different story. So many people misunderstood WHY CRDTs didn't work out well for the xi-editor.
At the very least, my article shows that CRDTs are well suited for shared editing. You brought up some valid points why CRDTs are not well suited for having different editor components communicate with each other (language server, indentation, syntax highlighting, ..).
Although, I still think there is a lot of merit in using CRDTs as a data model for a code editor (or any kind of editor). Not for editor components concurrently modifying the editor model, but just as an collaboration-aware model.
• Marijn considered a CRDT as a data model for CodeMirror 6 because positions in collaborative software can be better expressed [2]. A position in the Yjs model is simply a reference to the unique id of the character.
• Even without collaboration, Yjs servers as a highly efficient selective Undo/Redo manager. Each item on the Undo/Redo stack just consumes a couple of bytes. Furthermore, most existing implementations don't support selective Undo/Redo. This is free when using Yjs as a data model.
• Some components can work in the background and annotate the CRDT model (not manipulate it). For example, a code analyzer that runs on a remote computer could annotate a function and notify the user about potential problems. The position of the annotation will still be valid if users modify the model concurrently in a distributed environment.
I'm not sure what to add. I definitely agree that CRDT is viable for collaborative editing, I'm just saying people need to be aware of the issues.
Regarding position and undo, these are problems that can also be solved just fine using OT techniques, and are (imho) simpler when there is a central authority that can order all revisions into a globally consistent sequence.
I think it's inevitable that people are going to misunderstand arguments, given the complexity of the underlying space and the paucity of good learning resources. So thanks for your writeup, it adds to the discussion.
Just to add my 2c, having written sharejs and sharedb and working on and off on OT systems for the past 10 years or so:
After playing with a simple implementation of Martin Kleppmann’s newest automerge work, I was wrong to doubt CRDTs. I’m seeing about 6M ops / second in a prototype text engine in rust. I have much more to say on this - probably a blog post more to say. But I think CRDTs are the future for many workloads, and I have a strong sense of despair seeing how much time I’ve wasted investing in approaches which won’t feature strongly in the future.
> I have a strong sense of despair seeing how much time I’ve wasted investing in approaches which won’t feature strongly in the future.
Your comment makes me sad on several levels..
Firstly, ShareJS and OT types was the first open framework to build collaborative applications on the web. Your work inspired me to work on shared editing - I just wanted it to work over WebRTC.
Until 2015, JavaScript engines implemented different garbage collection approaches that wouldn't allow efficient CRDT implementations (as they need to handle millions of objects).
The idea of distributed applications on the web just popped up a couple of years ago. WebRTC didn't even exist when you started ShareJS. Even Websockets were still a bit experimental. OT was the right technology at the time.
Lastly, I'd love for you to try out Yjs. The current JavaScript implementation handles 2.5 million operations / second. A Rust/C implementation would surely handle more than that as it is not limited by automatic garbage collection.
You can compare Automerge's current performance branch with Yjs' current implementation in [1]. To be fair, their implementation is not finished. If I understood correctly, they want to load the compressed format directly into memory. I played with this idea a few years ago and represented the Yjs model in an ArrayBuffer. This approach will improve load-time, but the performance will be intolerable in other aspects (e.g. when applying document updates, transforming the document to a String/JSON, or when computing diffs). The performance of Yjs is the result of more than five years research. I still have a couple of ideas to improve performance significantly. Although, my article clearly shows that it is definitely good enough now.
I think it would be interesting to approach this from the language mode side, insisting on structured buffers (syntax tree with rope leaves†). It is pretty rare that two clients (mode and user window, or two user windows) would lock a single large leaf, so you could just choose an authority/leader for each subtree, and have the leader explicitly and synchronously sequence the peon clients' edits.
Then, working backward from language specific modes, I could imagine a way to generalize this to free form text, by negotiating the split points with the authority (or not at all, in the case of free text being edited by one client).
Though I guess for now just making these completely synchronous across the whole buffer, as you have, is fine in most cases, and already a significant improvement vs some editors (looking at you, beloved Emacs).
† i.e. for js, you could imagine a tree of statements/blocks containing expressions (maybe incl. operator precedence); for Clojure you could imagine a plain syntax tree, for JSON you could imagine it being the literal JSON data (plus whitespace metadata).
> it's because CRDT merges aren't a good fit for the problems a code editor is trying to solve
I think you are not talking about CRDTs here. CRDTs are a pretty good fit for distributed systems that share state, which is what collaborative editing is underneath. It's just that semantically completely automatic conflict resolution is incompatible with human collaborative editing, which is pretty obvious, but for some reason plenty of research goes into trying to do just that.
I was trying to use a CRDT to share state between the GUI editor and the language server process. My attempt didn't work well, for reasons I've written about. I have no doubt it can be made to work, and the research towards that might be interesting.
Lately there has been other work pursuing those compressed representations: Chronofold, I think Martin Kleppmann's automerge has some memory-efficiency work, and there are others.
But at least in the context of xi, this is not where things went wrong. As I've written about (and the author was kind enough to link), it's because CRDT merges aren't a good fit for the problems a code editor is trying to solve, particularly when the "collaborators" are automated processes such as language servers.
In human collaborative editing, it's important to preserve text that's being entered, even in the face of conflict. But when a peer is an automated service, it's much better to drop the edit on the floor and recompute. I'm simplifying here, as it depends on the service - some are history-insensitive, some are sensitive to a small window of history (in the case of automatically inserting indentation, etc), and (speculative) other services may be sensitive to more history.
In addition, the CRDT constrains the data model considerably. In other words, it's unfortunately not a clean abstraction where you can easily add higher level layers on top of the CRDT, but you always have to design those with the CRDT in mind (ie, everything still has to be a monotonic semi-lattice).
So, as with everything else, it's a tradeoff, and it's a question of weighing the pros and cons. I'm glad to see work being done to improve CRDT, but even with a very efficient representation and solid algorithms, the problems with CRDT would be enough for me not to use them in a code editor.