reference-crdts

m: how do you correctly handle inserts? We need to insert new items in the list in the correct location, as if we inserted into a tree then flattened it afterwards. But it turns out that this translation is quite simple in practice. Its like ~10-20 lines of code. Interestingly, the fugue paper first describes fugue (as a tree). Then it identifies & fixes a problem in the algorithm to produce fuguemax. If you do the list insertion order translation on both fugue and fuguemax, fugue ends up with an extra if() statement that causes this problem. If you remove that if statement, you get the (better) fuguemax algorithm. This transformation results in much better performance, and much lower memory usage. Counter-intuitively, you get another order of magnitude improved performance if you then store this flattened list once more in a b-tree. If you're curious, here's the equivalent insertion code for fuguemax, rga and yjs. These are all fuzz tested against their upstream reference implementations to verify equivalence. Fugue is also somewhere in this file, if you want to compare. Here's FugueMax[1]: https://github.com/josephg/reference-crdts/blob/c53947408770... RGA: https://github.com/josephg/reference-crdts/blob/c53947408770... And Yjs: https://github.com/josephg/reference-crdts/blob/c53947408770... As I said, I didn't come up with this idea. Kevin Jahns figured out this trick for Yjs. I adapted it to the other algorithms. [1] Fuguemax is called "yjsmod" in this repository because this code predates the fugue paper. It turns out our algorithms are equivalent.

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.

es 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://home.seph.codes/public/diamond-vis/

that up - yjs does the same thing in 1 second. But I don't think javascript will ever run as fast as optimized rust code. The b-tree in diamond types is used for merging. If you're merging 2 branches, we need to map insert locations from the incoming branch into positions in the target (merged) branch. As items are inserted, the mapping changes dynamically. The benchmark I've been using for this is how long it takes to replay (and re-merge) all the changes in the most edited file in the nodejs git repository. That file has just shy of 1M single character insert / delete operations. If you're curious, the causal graph of changes looks like this[2]. Currently it takes 250ms to re-merge the entire causal graph. This is much slower than I'd like, but we can cache the merged positions in about 4kb on disk or something so we only need to do it once. I also want to replace the b-tree with a skip list. I think that'll make the code faster and smaller. A gap buffer in javascript might work ok... if you're keen, I'd love to see that benchmark. The code to port is here: [3] > Undo support -> In which case, you only have to stack / remember the set of commands and not have to store the state on every change. I'm not sure if this overlaps with the data structure choice, other than implementation details. Yeah, I basically never store a snapshot of the state. Not on every change. Not really at all. Everything involves sending around patches. But you can't just roll back the changes when you undo. Eg: I type "aaa" at position 0 (the start of the document). You type "bbb" at the start of the document. The document is now "bbbaaa". I hit undo. What should happen? Surely, we delete the "aaa" - now at position 3. Translating from position 0 to position 3 is essentially the same algorithm we need to run in order to merge. > I was just looking into TypedArrays. I tried optimizing a physics library a few years ago by putting everything in typedarrays and it was weirdly slower than using raw javascript arrays. I have no idea why - but maybe thats fixed now. TypedArrays are useful, but they're no panacea. You could probably write a custom b-tree on top of a typedarray in javascript if you really want to - assuming your data also fits into typedarrays. But at that point you may as well just use wasm. It'll be way faster and more ergonomic. [1] https://github.com/josephg/reference-crdts [2] https://home.seph.codes/public/node_graph.svg [3] https://github.com/josephg/diamond-types/tree/master/src/lis...