It's a CRDT in Rust and it uses a lot of similar ideas. Raph and I had a plan for how to make it fast and memory efficient in very similar ways to your implementation. I think the piece I got working during my internship hits most of the memory efficiency goals like using a Rope and segment list representation. However we put off some of the speed optimizations you've done, like using a range tree instead of a Vec of ranges. I think it also uses a different style of algorithm without any parents.
We never finished the optimizing and polished it up, so it's awesome that there's now an optimized text CRDT in Rust people can use!
Oooohhhh no I haven’t read that - thanks for the link! I feel embarrassed to say this but I knew about Xi editor years ago but I totally forgot to go read & learn about your crdt implementation when I was learning about Yjs and automerge and others. I’ll have a read.
And thanks for writing such an in depth article. It’s really valuable going forward. Maybe it’s addressed in your write up but are there any plans for that code, or has everyone moved on? I’d love to have a zoom chat about it and hear about your experiences at some point if you’d be willing.
Hi josephg, I'm a CRDT researcher. This is great to see so much work around CRDT nowadays!
Some optimizations whom you discuss are already proposed by some papers and implementations.
For instance, LogootSplit [1] proposes an implementation based on an AVL tree with extra metadatas to get a range tree. LogootSplit proposes also a block-wise approach that stores strings instead of individual characters. Xray [2], an experimental editor built by Github and written in Rust, uses a copy-on-write B-tree. Teletype [3] uses a splay tree to speedup local insertions/deletions based on the observation that a user performs several edits on the same region.
Cool! It'd be interesting to see those CRDT implementations added to Kevin Jahns' CRDT Benchmarks page[1]. The LogootSplit paper looks interesting. It looks like xray is abandoned, and I'm not sure about teletype. Though teletype's CRDT looks to be entirely implemented in javascript[2]? If the authors are around I'd love to see some benchmarks so we can compare approaches and learn what actually works well.
And I'm not surprised these techniques have been invented before. Realising a tree is an appropriate data structure here is a pretty obvious step if you have a mind for data structures.
To name it, I often find myself feeling defensive when people read my work and respond with a bunch of links to academic papers. Its probably totally unfair and a complete projection from my side, but I hear a voice in my head reword your comment to instead say something awful like: "Cool, but everything you did was done before. Even if they didn't make any of their work practical, usable or good they still published first and you obviously didn't do a good enough literature review if you didn't know that." And I feel an unfair defensiveness arise in me as a result that wants to find excuses to dismiss the work, even if the work might be otherwise interesting.
Its hard to compare their benchmark results because they used synthetic randomized editing traces, which always have different performance profiles than real edits for this stuff. Their own university gathered some great real world data in an earlier study. It would have been much more instructive if that data set was used here. At a glance their RAM usage looks to be about 2 orders of magnitude worse than diamond-types or yjs. And their CPU usage... ?? I can't tell because they have no tables of results. Just some hard to read charts with log scales, so you can't even really eyeball the figures. So its really hard to tell if their work ends up performance-competitive without spending a couple days getting their enterprise style java code running with a better data set. Do you think thats worth doing?
Yes, xray was abandoned and teletype is written in JS.
I understand your point and as a researcher and engineer I know your feeling. I took some cautions by using "Some optimizations". I value engineering as much as research and I'm bothered when I heard any side telling the other side that their work is worthless. Your work and the work of Kevin Jahns are very valuable and could improve the way that researchers and engineers do benchmarks.
This is still hard for me to determine when position-based list CRDT (Logoot, LogootSPlit, ...) are better than tombstone-based list CRDT (RGA, RgaSplit, Yata, ...). It could be worth to assess that.
3 year ago I started an update of LogootSplit. The new CRDT is named Dotted LogootSplit [1] and enables delta-synchronizations. The work is not finished: I had other priorities such as writing my thesis... I have to perform some benchmark. However I'm more interested in the hypothetical advantages of Dotted LogootSplit regarding synchronization over unreliable networks. From an engineering point-of-view, I'm using a partially-persistent-capable AVL tree [2]. Eventually I would like to switch to a partially-persistent-capable b-tree. Unfortunately writing a paper is very time consuming, and time is missing.
I still stick with JS/TS because in my viewpoint Wasm is not mature yet. Ideally, I would like to use a language that compiles both to JS and Wasm. Several years ago I welcomed Rust with a lot of enthusiasm. Now I'm doubtful about Rust due to the inherent complexity of the language.
Cool! What do you think is missing from wasm for maturity? It seems great for something like CRDTs, since the code is reasonably self contained. I hear you about rust - I'm not convinced it'll ever be as popular as java / C# / JS for exactly that reason. But rust doesn't need to be that popular for me to enjoy it, or for the people who use my software to reap the speed & safety benefits.
I'll have to take a read of LogootSplit. I suspect most / all list CRDTs can work with this approach (using a list internally and doing an insertion sort). But I don't know enough about how logoot / logootsplit works to know!
And I really hear you about writing papers taking time. That blog post we're talking about here took nearly a month of time in aggregate to write. I wrote the initial draft in about 2 days, but editing and adding diagrams and everything was exhausting. There's still more work I could have put into it before publishing - I anticipated some of the things people were confused by in this thread. But at the end of the day, published > perfect and I have code to write as well!
> To name it, I often find myself feeling defensive when people read my work and respond with a bunch of links to academic papers. Its probably totally unfair and a complete projection from my side, but I hear a voice in my head reword your comment to instead say something awful like: "Cool, but everything you did was done before. Even if they didn't make any of their work practical, usable or good they still published first and you obviously didn't do a good enough literature review if you didn't know that." And I feel an unfair defensiveness arise in me as a result that wants to find excuses to dismiss the work, even if the work might be otherwise interesting.
I've followed your work for a longtime (since chipmunk-js days), and that is a very honest self assessment
> Yjs does one more thing to improve performance. Humans usually type in runs of characters. So when we type "hello" in a document, instead of storing ['h','e','l','l,'o'], Yjs just stores: ['hello']. [...] This is the same information, just stored more compactly.
Isn't this not just the same information when faced with multiple editors? In the first implementation, if I pause to think after typing 'hel', another editor might be able to interject with 'd' to finish the word in another way.
In my view, these data structures are only "the same information" if you provide for a reasonably-sized, fixed quantum of synchronization. The merging makes sense if e.g. you batch changes every one or two seconds. It makes less sense if you would otherwise stream changes to the coordinating agent as they happen, even with latency.
I didn't explain this well but the transformation is lossless. No data is lost from compressing like this. It has no impact on the concurrency protocol or network protocol; it just impacts how the data is stored locally.
If we need to, we could split the run back out again into individual characters without losing information. And that does happen - we do that if something later gets inserted into the middle of the run of characters. Pausing doesn't help. Even the same user could later type something in the middle of a word they'd typed previously.
This limits what we can run-length encode. The code in diamond only run-length encodes items when they are:
- Typed sequentially in time
- And sequentially in insert location (position 10, 11, 12, 13, ...)
- And either all of the characters have been deleted or none of them have been deleted
Notice the other fields in that example in the post. Each subsequent character has:
- An id field = the previous id + 1
- A parent field = the id of the previous item
- The same value for isDeleted
If any of this stuff didn't match, the run would be split up.
Instead of storing those fields individually, we can store the id and parent of the first item, an isDeleted flag and a length field. Thats all the information we actually need to store. With yjs style entries (which is what diamond-types actually implements), the code is here if you can make heads or tails of it. The poorly named "truncate" method splits an item in two. Spans are only extended if can_append() returns true: https://github.com/josephg/diamond-types/blob/c4d24499b70a23...
With real data from Martin's editing trace, 182 000 inserted characters get compacted down to 12 500 list items. Which is still pretty good - thats 14x fewer entries. And it means performance doesn't stutter when large paste events happen.
I have a related question to this, if you’re storing [“hello”] as one chunk, what happens when you perform an edit to say adding an extra [“e”] after the [“e”]? In the unoptimised structure I know you can just add the new [“e”] as a child of the original [“e”]. So here would you then delete the chunk [“hello”] and split it into two halves like [“he”] and [“llo”]?
Yes exactly. You replace the chunk with “he” and “llo” then insert the extra item in the middle. The result is [“he”, “e”, “llo”]. The code to do all this inline in a b-tree is pretty hairy but it works pretty well!
Ah, I see. I had thought that the consolidation gave a batched update with a single ID, so 'h' + 'ell' + 'o' would have IDs of 1, 2, and 3 respectively. That would have made an editing conflict in the middle of 'ell' impossible.
Ah that makes sense! Concurrent changes are one thing, but concurrent changes are rare. The big problem if we did it that way is that it would become impossible to insert in the middle of "ell", because we wouldn't be able to name any of those internal positions.
To get around that we assign a sequential ID for every inserted character, regardless of how they're typed or stored. Typing "hello" would assign IDs 1-5 even if you paste "hello" from the clipboard.
The chunking should depend entirely on the network synchronization. If synchronization is editing-debounced, then chunking could be applied rather safely.
I did use the performance branch. And I had a chat with a few people in the automerge community about the performance numbers I was seeing long before I published to see if I was doing anything wrong. I tested a few different versions of automerge but in this test there wasn’t much performance difference between 0.12, 1.0.x-preview versions (which are built from the merged performance branch) and I tried the unreleased automerge-rs. When I ran my tests timing numbers for automerge ranged from about 5m with the old non performance branch down to about 4m20s or so with automerge-rs. Still far from Yjs’s 0.9 seconds.
I just checked and it looks like automerge 1.0.1-preview-4 has landed. I wrote the post benchmarking preview-2. I’ve been knee deep in diamond types lately and haven’t been watching. Fingers crossed there’s some more performance improvements in the pipeline. I’d love to do a follow up in 6 months showing much improved performance.
Great post! I had no idea that list CRDTs could actually be fast because I read the papers showing how they were impractical. Thanks for investigating and writing this up — please accept my offer of a legitimate academic credential.
It seeems that the issue of reproducibility in computer science where no gigantic/proprietary datasets are needed should not be a problem by simply publishing repository with the code. Are there any forces present that make it so rare in practice?
Credit where its due, the academics did publish the code they wrote on github. But I don't know if anyone - reviewers or readers - actually took the time to read it. Let alone understand why it throws doubt on the paper's conclusions.
Usually, (at least in my specific niche of the computer science field,) if the code is published it's only published after the paper has been reviewed. This is partly to preserve anonymity during the review process, and also because usually the code isn't seen as "part of the paper" (i.e. "the paper should stand on its own"). Although I agree that you could argue that for papers about benchmarks, the code should definitely be considered an essential part of the paper.
Just want to make sure if something's a possible typo or I'm getting it all wrong :)
Quote:
"But how do we figure out which character goes first? We could just sort using their agent IDs or something. But argh, if we do that the document could end up as abcX, even though Mike inserted X before the b. That would be really confusing."
Since the conflict is only between the children of (seph, 0) the only possibilities are, either ending up with "aXbc" or "abXc" right? Or is there a legitimate possibility of ending up with "abcX" ?
I'm assuming we'll apply a common sorting logic only to clashing siblings.
Good question. That part of the article could probably use another diagram to explain it.
The resulting document is generated by doing a depth-first prefix traversal of the tree. The ambiguity comes because "b" and "X" are both direct children of "a". So its not clear how they should be ordered relative to each other. Because "c" is a child of "b" in this example, the "X" can't appear between the "c" and "b". The only valid orderings are, as I said, "aXbc" or "abcX". But without knowing how "b" and "X" should be ordered, its ambiguous which one to use.
Let me know if thats still confusing! This stuff is hard to explain without a whiteboard.
I've been following your work for years (and I'm actually neck-deep in a ShareDB project right now) so I just want to say thank you for all of your contributions! I especially enjoyed this post.
I love high level systems languages like C/++ and Rust… but everything you said about JavaScript being slow is the same thing assembly programmers experience when optimizing high level systems languages.
In general, when I see C code and I’m asked to speed it up, I always use “100x” as my target baseline.
Whoa thats a really impressive baseline to reach for when optimizing C code! I'd love to hear some war stories.
As you can probably tell from my article, most of my skill at this stuff is from hard won tricks I've picked up over the years - like reducing heap allocations and packing memory for cache coherency. There's probably lots of things I just haven't learned because I haven't discovered it on my own.
Do you have a blog, or any recommendations for stuff to read by you or others?
I learned low level programming while at Intel, working with one of their performance teams; so, nothing written. In general, though, assembly is more expressive than higher level languages; it lets you “tighten up” the code the computer executes, reducing work & bandwidth.
Specifically, a guy named Mike Abrash taught me some of this stuff, and he’s got some books explaining the theory in terms of practice.
I believe that I understood the code tagged as follow
> (But don't be alarmed if this looks confusing - we could probably fit everyone on the planet who understands this code today into a small meeting room.)
and the follow up reading confirm what I believed about this code
Terminology nit: cache coherence refers to CPU cache implementation behaviours at hw level in presence of concurrent access from multiple cores. Data locality or cache friendly data layout could work better here.
The most useful application I see is moving toward building local first software[1].
And as for optimizations, my approach is surprisingly non systematic. I think about the program on the whole, and think through & investigate where all the time is being spent. There's usually ways to restructure things so the hottest code path runs faster. Sometimes that involves changing data structures or languages. Sometimes it just needs early returns for common cases, or inlining string libraries and things like that to avoid allocations.
Sometimes it helps to imagine yourself going through by hand the drudgery the computer is doing. If I was actually doing that boring work by hand, there's almost always ways I'd start taking short cuts. All thats left then is programming those shortcut into the computer.
Oh that’s cool!! Did you use json-ot for that? I haven’t touched that code in years and it’s delightful people are actively maintaining it and using it to make cool stuff.
If you’re interested in learning more about Yjs’s internals, I interviewed Kevin for 3 hours on zoom and got him to take me through Yjs’s code. He’s a great guy.
Drifting off-topic but I've wondered this myself - I've been interested in CRDTs in a "read the news" way but not a "this rises to something I'm going to implement" way.
Perhaps it's blindingly obvious to all here, so no one mentions it: Thinking about more practical and real-world problems seems like collaboration on on more complex/structured data. Today, it seems one would still have to transform that data to a large flat string underneath, and implement an editor that only performs edits that maintain the integrity of the higher-level object, while the flat string provides collaboration features. Perhaps it's possible to implement an XML schema known to the editor so all insertions/deletions keep the document syntactically correct.
I wonder if there's some other way to either generalize on top of "big string" or create another base model (somehow?)
> Today, it seems one would still have to transform that data to a large flat string underneath, and implement an editor that only performs edits that maintain the integrity of the higher-level object, while the flat string provides collaboration features.
Lots of people think this and have mentioned it over the years, but its a dangerous idea. The way concurrent edits are handled makes it really easy for the automatic merging algorithms to mess up the syntax of your XML / JSON content. And thats really hard for non-programmers to fix.
The right answer for this stuff is to just make CRDTs which support other data types, the same way we did for OT with ot-types[1]. We need CRDT code for lists + text (working now - text is just a list of characters). And rich-text and JSON. And that'd cover 99% of the use cases. I'm tackling strings first in diamond-types because its probably the hardest case; but I want to have native support for other data structures soon too.
Yjs and automerge already do this. They have support for plain text, XML and arbitrary JSON structures.
The simplest implementation for JSON structures + tuples is probably shelf[2], which is so simple you can implement it in about 25 lines of javascript. Shelf doesn't support lists, but combining shelf with the list code I already have in diamond-types is probably going to be good enough for most applications.
[2] Shelf's description + code is here: https://braid.org/algorithms/shelf . Or you can watch the video of Greg (shelf's author) discussing the algorithm here: https://braid.org/meeting-8 . Kevin Jahns (Yjs's author) is in that recording too, and he's super jazzed about how simple and beautiful shelf is.
First of all, thank you for the amazing read! I thoroughly enjoyed the entire article, and it gave me a new perspective on the feasibility of CRDTs for real world applications performance-wise.
Though I am curious now to hear your thoughts on the conflict resolution side of the equation for complex data structures like deeply nested JSON.
The biggest takeaway I got from Martin's talk on the topic from a few years ago was that while CRDTs are theoretically guaranteed to eventually converge, the resulting converged state might not make any sense to applications that need to consume and act on that state [1].
It seemed like a pretty fundamental challenge to using CRDTs to store arbitrary application state to me at the time, but I imagine the field has progressed immensely since then, so would love to hear any insights you might have around strategies that could be used to alleviate or at least work around this challenge if I wanted to build a CRDT-based app today.
I’m not sure how much the field has improved - good chance there’s some new papers I haven’t read. But I think it’s pretty doable. For all the talk of concurrent editing, the reality is that having multiple users edit the same value at the same time in most applications is incredibly rare. It’s rare enough that concurrent editing is just basically broken in most web apps and nobody seems to mind or talk about it. For structured / database data, the best effort merges of current systems (or doing simple last writer wins stuff) is a fine solution in 95% of applications.
But ideally we want something like the semantics of ot-json-1 [1] which supports arbitrary move operations. This is necessary if you wanted to implement a program like workflowy on top of a crdt. Martin thinks this is possible in a crdt by sort of embedding part of an OT system and doing transform, but I don’t feel very satisfied with that answer either.
The other thing I would love to see solved is how you would add git style conflicts into a crdt. The best effort merging strategy of most OT & CRDT systems is fine for real-time editing but it isn’t what you want when merging distant branches.
Automerge today supports arbitrary json data, inserts, deletes and local moves. I think that’s plenty for the data model in 99% of software. I think most software that fits well into a classical database model should be reasonably straightforward to adapt.
I’m not sure if that answers your question but yeah, I’m thinking about this stuff too.
Thanks for the great post. Indeed, as a former scientist myself, I can say you have to take everything you read with a grain of salt. I've seen inside the sausage factory, and concluded that YMMV.
> The other thing I would love to see solved is how you would add git style conflicts into a crdt. The best effort merging strategy of most OT & CRDT systems is fine for real-time editing but it isn’t what you want when merging distant branches.
I found this comment very interesting. I have been playing with the idea of 3-way merging CRDTs, similar to the git approach. Have even used this type of branching in commercial software I work on for handling concurrent changes to files.
Be very interested to know if any efforts are being made on this in the CRDT community. (I'm more of an interested onlooker. I use a lot of the same concepts in my software, but not rigorously.)
CRDT is a general concept, editing text is just one possible application. If you have a stronger datatype, great, you can build operations on top of it to implement a CRDT system, depending on its properties.
It would be a little bit strange to build a CRDT system on top of a more traditional data system. CRDTs solve problems at the network layer at enormous cost basically everything else. If you're not using them there, I can't quite understand what they're doing for you?
AFAIK Wave and ShareJS both used OT (which the paper that this article referred to was also attempting to benchmark).
FWIW, I am myself also curious about this (the question of comparing CRDT to non-CRDT solutions): I found OT beautiful, but never really felt CRDT had the same feeling of elegance; and so I am downright fascinated to see the person I have always seen as a "god of OT" deciding to forsake it and move to CRDTs going forward. Are they really that great? Is there something simple I am missing for the explanation for why they are so much better? (Is it maybe that they can support arbitrary merging without a sequencer to linearize the edits? Honestly, my question probably sucks a bit as I haven't spent any time thinking about OT or CRDT in at least three years--and even then only once since a few years before that, as I have had other things to spend most of my mental energy on recently--and so I am failing to remember the details of my use cases or the tradeoffs I saw or the implementation issues I felt were easy/hard.)
Do you want a centralized server to control the data? Then just use OT. Do you want users to control the data, and have your server essentially just be a forever-present user? Then use CRDT.
CRDTs certainly do have a mathematical elegance to them.
Yep, this is the best practical advice at the moment. Well, for list CRDTs. State CRDTs (like a counter) are small and fast, and kinda better than OT in every way.
List ("operation based") CRDTs and OT systems are "equivalent" in a very academic sense that nobody really talks about or understands. Its really not obvious unless you've been staring at this stuff for years but the equivalence is there:
You can make a CRDT out of any OT system by just shipping the entire history of operations to each peer. List CRDTs essentially do that, with a whole lot of tricks to compress that data set and use it without needing to linearly scan.
And you can convert the other way too. You can add a "rename" operation into a list CRDT which assigns a new name to each element currently in the document. Before the rename operation document "hello" might have IDs [a4, b2, b3, b1, a5]. The rename operation changes the IDs to [c1, c2, c3, c4, c5]. When an operation happens you specify the version and the ID at that version of the predecessor (eg c2). The insert happens there. Then you need a method to take the ID at one version and "transform" it to the ID of the same item at a different version. Do the rename operation implicitly after every change, and viola! You now have OT semantics. "Insert after c1" means "Insert after position 1".
OT systems have one big advantage which is that you don't have to ship the CRDT state to every peer. With a rename operation, we can add back the operational simplicity of OT systems into a CRDT. But the code is (and always will be) much more complicated. So I think OT makes sense for strictly server-client systems.
You can also have a hybrid server, which talks CRDT to full peers on the network but just does OT when talking to browser clients and things like that. We talked about this at our public braid meeting at the start of the week. The discussion about this stuff starts about 30 minutes in: https://braid.org/meeting-15
> OT systems have one big advantage which is that you don't have to ship the CRDT state to every peer... You can also have a hybrid server, which talks CRDT to full peers on the network but just does OT when talking to browser clients and things like that.
Could you clarify what you mean? Assuming your CRDT is defined in terms of "operations" that contain (at minimum) an identifier+sequence tuple, zero or more references to other operations, and a value (as they are in this article) then there's no reason why you couldn't just ship a batch of individual operations to other clients when something changes rather than the whole state, since each operation is defined in absolute terms.
In other words, if you start with [A4="a", B2="b", B3="c", B1="d", A5="e"] at site A, and it gets turned into [A4="a", B2="b", B4="f", B3="c", B1="d", A5="e"] following a change from B, you can ship something like B4="f"->B2 to C as long as C's CRDT has synced up to version vector A5|B3. (And if it hasn't synced up yet, and you're not using a transport with causal delivery guarantees, the change could be cached at C until its dependencies have arrived.)
I don't think there's any need to transition to an OT system or to add renames in order to get this delta-shipping benefit: all the data you need is already there, unless I'm missing something. (But maybe you're describing something else?)
Yes, my point was that the peer needs to translate a user’s insert of “insert f at position 3” into “insert f between ID B2 and B3”. To do that, you need the “crdt chum” - you basically need that peer to know the ID of every item in the document. This data compresses well, but it’s still annoying to ship around and complex to manage. OT doesn’t need any of that.
> And you can convert the other way too. You can add a "rename" operation into a list CRDT which assigns a new name to each element currently in the document.
Operations in a CRDT must be commutative for merge/update to be well-defined, so it's not immediately clear how a "rename" operation can be expected to work properly.
When optimizing `findItem`, did you consider storing the original index of each item on itself and using that as a starting point?
Obviously this might move later (maybe it can only increase?), but usually not by much, so I would guess it would make an efficient starting point / be immediately correct 99% of the time?
Looks like you already have 2 good solutions to this though (start from index of recent edits and range tree).
