Using CRDTs for multiplayer text editing
zed.dev
zed.dev
“I come to the conclusion that the CRDT is not pulling its (considerable) weight. When I think about a future evolution of xi-editor, I see a much brighter future with a simpler, largely synchronous model, that still of course has enough revision tracking to get good results with asynchronous peers like the language server.”
[1]https://github.com/xi-editor/xi-editor/issues/1187#issuecomm...
Peritext[1] is the only one that came close to solving rich-text, but even that one left out important aspect of rich-text editing like handling list & table operations as "work to be done later".
For people interested on why it's difficult to build CRDTs for richtext, here's a piece I wrote a year back: https://writer.zohopublic.com/writer/published/grcwy5c699d67...
Related HN discussion: https://news.ycombinator.com/item?id=29433896
Yrs developer here:
- Yjs/Yrs have support for formatting attributes[1]. The matter if format attributes conflict resolution behaves as user desired is a subject to discussion (which is a common thing re. CRDTs and their trade offs), but its behaviour is consistent, convergent and algorithm itself works fast. This feature is in fact used in many rich text editors using Yjs bindings.
- Embedding non-string elements in text is supported as well.
- While syntax trees are not supported out of the box (AFAIK this CRDT is still being researched), Yjs also support XML nodes with attributes and nested children, which may be used for similar effects in some scenarios.
> Even long edit histories barely compare to the memory savings Zed obtains from not being built with Electron.
I got a good chuckle out of this. Speaking of performance, I think it’s I nteresting that ms word and google docs are still using OT rather than CRDT. The goog version seems to work well but I have had nothing but frustration with ms word. Bad merges and weird states are typical, particularly from the fat client.
Anyone else interested in the background of OT vs CRDT might find this thread useful: https://news.ycombinator.com/item?id=18191867
Argh not getting this stuff right is really frustrating. I've been working on collaborative editing for over a decade now, and I still can't implement any of these algorithms correctly without the help of a fuzz testing. But fuzz testing done right finds all of these problems! There's no excuse!
Fuzzers work so well here because all of these algorithms have a clear correctness criteria: After syncing, state should always converge to the same result. So its pretty easy to write code which does this in a loop:
1. Generates some random changes on some fake "peers"
2. Picks 2 peers at random and sync their changes, using your new fancy synchronization algorithm
3. Assert that the state has converged between the peers
I've been working on this stuff for over a decade. I've implemented dozens of these algorithms. And every single time I write a fuzzy boi to check my work I find convergence bugs. Playing whack-a-mole with a fuzzer is a rite of passage for implementing systems like this.
When your fuzzer runs all night, you should never have lingering convergence bugs like you're describing with Word.
As an example, here's a simple fuzzer for a reference list CRDT implementation: https://github.com/josephg/reference-crdts/blob/9f4f9c3a97b4...
The code is so small it almost fits on my laptop screen.
One nice thing about fuzz testing is that it tests both the concepts and the specific implementation. Probably 70% of bugs my fuzzers have found over the years are edge cases my code is handling incorrectly. If I made a “pure” model of my sync engine, wouldn’t I also, still, need to prove my actual implementation matches that model?
Open to correction though, it's been a while since I dug into the differences in these approaches & my memory is imperfect.
Source: I have been etherpad's maintainer for two years.
All the main text editing CRDT algorithms around today solve this no problem. (Yjs, automerge, diamond types, etc).
It’s an ordering problem that comes from some of the simpler ordering algorithms. For Diamond types I’m using a variant of Yjs’s ordering. But even RGA doesn’t have this problem because each character’s insert location is specified by naming the character immediately to the left when that character was typed.
This repository implements a few different list CRDTs using an insertion sort approach, where the algorithm scans for the appropriate location every time an insert happens. This is the scanning function for RGA (automerge’s algorithm):
https://github.com/josephg/reference-crdts/blob/fed747255df9...
And this is an interactive visualisation of how diamond types works (which uses Yjs’s algorithm instead), complete with run-length encoding: https://home.seph.codes/public/diamond-vis/
In practice, many CRDT libraries nowadays (eg. Yjs and Automerge) are using structures that don't come with interleaving issues.
Re. other purpose projects - Yjs/Yrs main target are sequential data structures (text, arrays), but it also has support for maps and xml-like elements. In general you can build most data structures with it. I agree that it would be nice to have some other applications in demos though.
[1] https://docs.yjs.dev/yjs-in-the-wild [2] https://github.com/yjs/yjs-demos
That being said I would use CRDTs for any greenfield collaboration project.
So, I don't think this is a reflection on the merits of CRDTs versus operational transforms as much as it is a reflection on the ecosystem and the history of the codebase.
Much more complex though. (~3k loc for a good, high performance text crdt merging algorithm, vs 300 loc for a good text OT algorithm.)
But I'm probably wrong in at least one way! Hoping to learn.
[0] https://link.springer.com/chapter/10.1007/978-3-662-43352-2_...
Usually the difference is that operational transform algorithms create an ordered global list of all the changes (typically on a centralized server). They flatten operations using a heuristic "transform" function.
CRDTs don't reorder the changes, but guarantee that when all changes are merged (in any order) the final result would be the same. For example, MAX() is a complete CRDT merging function.
But the distinction gets much more blurry at the edges. You can make OT algorithms which work without a central server, and CRDTs which use operation reordering to guarantee merge consistency.
[1] https://en.wikipedia.org/wiki/Operational_transformation
I'm currently struggling with moving document merge use-case to Yjs while leveraging it's updates for efficient real-time rebasing. It's insert/delete world view (state based) seems to make this practically impossible.
CRDTs aren't that complex on the surface - this messy file[1] implements 4 different list CRDT algorithms in a few hundred lines of code. And CRDTs are pretty simple for JSON structures, which is not at all true for OT algorithms.
But text CRDTs in particular need a whole lot more thought around optimization because of how locations work. Locations in list/text CRDTs generally work by giving every item a globally-unique ID and referencing that ID with every change. So, inserts work by saying "Insert between ID xxx and yyy". But, if you have a text document which needs to store a GUID for every keystroke which has ever happened, disk and memory usage becomes crazy bad. And if you don't have a clever indexing strategy, looking up IDs will bottleneck your program.
In diamond types (my CRDT), I solve that with a pancake stack of optimizations which all feed into each other. Ids are (agent, sequence number) pairs so I can run-length encode them. Internally those IDs get flattened into integers, and I use a special hand-written b-tree which internally run-length encodes all the items it stores. I've iterated on Yjs's file format to get the file size down to ~0.05 bytes of overhead per inserted character in some real world data sets, which is wild given each inserted character needs to store about 8 different fields. (Insert position, ID (agent + seq), parents, the inserted character, and so on).
CRDTs aren't that complex. Making them small and fast is the challenge. Automerge has been around for years and still takes hundreds of megabytes of ram to process a simple editing trace for a 10 page text document. Even in their rust implementation. Diamond types is orders of magnitude faster, and uses ~1M of RAM for the same test.
The current version of diamond types is many times faster than any OT algorithm I've written in the past thanks to all those optimizations. Now that I've been down this road, I could optimize an OT algorithm in the same way if necessary, but you don't really need to.
Other kinds of CRDTs don't need these optimizations. (Eg the sort you'd use for a normal database). There's two reasons: 1. When editing text, you make an edit with each keystroke. So you have a lot of edits. 2. Merging list items correctly is orders of magnitude more complex than merging a database entry. If you just want CRDTs for editing a database of records, that'd probably only take a few dozen lines.
[1] https://github.com/josephg/reference-crdts/blob/main/crdts.t...
https://github.com/josephg/reference-crdts
Seems to have good density of explanatory comments.
(Seph, if you're reading this, I don't know you but Angelo has had good things to say. :)
Given the interest in CRDTs, it'd be a great help if someone wants to do a much more interactive exploration of those algorithms. I feel like there's an interactive guide just waiting to be written which could help people understand this stuff.
Sorry for the hassle.
https://www.ookla.com/articles/gaming-cities-lowest-latency-...
(The picture has the name wrong. Maybe intentionally, as some kind of typo which one wants to edit out, hinting at multiple people editing a document?)
Traditional databases (e.g. sql databases and key-value stores) treat the database as a blob of data. This makes multi-player updates very difficult, as reconciling differences in real-time is a hard problem, hence the invention of CRDTs. My new database, however, treats the data as a series of events. In the example of a text editor, the stream of events might be something like: User 1 connected, User 1 pressed key a, User 2 connected, User 2 pressed b, User 1 disconnected, etc.
In addition to the stream of events, application developers also provide an "engine" that converts the stream of events into a blob of data. The engine runs locally on each connected client. When a client connects to the database, they fetch the engine from the database server. The client then receives the stream of events from the database server in real-time. When a client generates an event, it gets inserted into the local engine immediately and also gets broadcasted to the server. The server then broadcasts the event to other connected clients.
The most important part that makes this work comes from a technique called rollback netcode. Events in the stream are ordered and undo-able. When a connected client generates an event, they insert it into their local engine immediately, but other clients are also generating events simultaneously. If all clients optimistically inserted events locally, the event order would differ across clients. To solve this, the engine automatically will undo events when new events come in from the server. The engine then applies the received event in its proper place and reapplies all the undone events on top. The result is that all users have a consistent view of the data.
The logic of an engine looks something like this:
1) When User X connected, set X's cursor position to offset 0.
2) When User X types a letter, insert text at User X's cursor offset and increase User X's cursor offset by 1. Also increment the cursor offset of all other connected users if their cursor offset is > User X's.
And that's it for a basic insert-only text editor. You can see that applying all the events in order yields the correct state. Adding a moveable cursor and the ability to remove text is also trivial. Basically just the opposite of 1 and 2 above. The whole engine can be implemented in like 100 lines of code and is very easy to reason about.
Your approach with cursors is clever, that part I haven’t seen elsewhere.
The appeal of CRDTs is:
> 1. The application can update any replica independently, concurrently and without coordinating with other replicas.
Along with some other important points. See https://en.wikipedia.org/wiki/Conflict-free_replicated_data_...
The featured article also talks about this in detail.
Doesn't the whole process assume that whenever any edit is done (insertion/deleteion/un-/redo) that the edit _eventually_ reaches all participants?
So if a single edit is believed to be delivered to all, but actually never made it to a single participant, who resends it? And if it's not resent, then the participants state is inconsistent from now on, no?
Edit:autocorrect
If you’ve used Git you’ve been using a CRDT (with manual pulls and manual merges). A better CRDT would do both automatically.
Actually, that cleared it up, thank you :)
It just sounds like a recipe for a Sketch situation where it's really just a Mac app and web (and other platforms) is a second class citizen.