5 ms·
Causal Trees
- jasonjmcghee 3y agoThis is a really fun post. Really appreciate the time you put into it! Quick note: on mobile, the text inputs for the clients is forcing all the text to be very tiny, and you need to manually zoom in to read it.
- shoarek 3y agoYou posted this 2 times in 3 hours. By the way, Your connection is not private.
- bytearray 3y agoHow does the performance of Causal Trees compare to other CRDT implementations, especially in scenarios with a high frequency of concurrent updates? It seems like a promising approach for collaborative text apps, but I'm curious about its scalability and real-world performance.
- zogrodea 3y agoI don't have any experience with this, but the use of flat arrays (rather than unbalanced trees) in Yjs sped things up considerably according to this long and interesting blog post below. https://josephg.com/blog/crdts-go-brrr/ https://josephg.com/blog/crdts-go-brrr/ "We can use a flat array to store everything, rather than an unbalanced tree. This makes everything smaller and faster for the computer to process."
- josephg 3y agoThanks for linking my post. I really need to write a followup at some point - we’ve gotten another 2-10x speed up from when I ran those benchmarks, depending on how you measure it. I still stand by what I wrote in that blog post. Using lists rather than trees is still a good approach. And it’s super simple to implement too. You can have a working crdt in a few dozen lines of code. I’m happy to answer questions if anyone is curious about this stuff. Ive been working to implement and optimise CRDTs for years at this point. Increasingly I’m seeing it as a solved problem.
- practal 3y agoI've read up on CRDTs over the last two months or so (and I've come across your very helpful posts as well, of course), because I am building a collaborative editor for Practal [0]. In particular, I've invented a new simple text format for this which I call Recursive teXt (RX) [1]. The idea is to just develop a CRDT for RX. RX is naturally structured as a tree, and it seems to make sense to model a document as an A of blocks, a block as an A of lines and blocks, and a line as an A of characters. Here "A of" stands for some sort of CRDT array based on inserting via predecessor (and successor?). Each A-object (document, block, line) is referenced by its own id and stored in a purely functional tree (similar to how Redux would do it [3], and I think Automerge does it similarly). Would be great to get your opinion on this design choice, maybe you see some obvious (or not so obvious) problems with it. One problem seems to be one that Kleppmann points out in [2, end of section 4], when you press enter in the middle of a line, so that a line is split into two lines, you have to deal with that in a special way. Similarly with splitting/joining blocks. [0] https://practal.com https://practal.com [1] https://practal.com/recursivetext/ https://practal.com/recursivetext/ [2] https://martin.kleppmann.com/papers/list-move-papoc20.pdf https://martin.kleppmann.com/papers/list-move-papoc20.pdf [3] https://redux.js.org/usage/structuring-reducers/normalizing-state-shape https://redux.js.org/usage/structuring-reducers/normalizing-...
- josephg 3y agoSounds like a very neat approach! > One problem seems to be one that Kleppmann points out in [2, end of section 4], when you press enter in the middle of a line, so that a line is split into two lines, you have to deal with that in a special way. Similarly with splitting/joining blocks. I was about to mention this problem. We ran into this with Google wave. The initial document model (based on an xml tree) used <line> tags for lines. We hit exactly this problem - if you press enter in the middle of a line while someone is concurrently editing that line, how does it handle those changes? The initial code had special split and join operations but nobody could figure out how to make split and join work correctly in an OT system. Wave was over a decade ago now. I don’t know if anyone has solved this problem - all the working systems that I know of bailed on this approach. It’s much easier if you just make newline characters be an item that can be inserted or deleted like any other character. And then make lines be a higher order concept. If you get this working (working = passing fuzz test suite), I’d love to hear about it. But the well trodden path of those who come before is to use newline characters instead.
- mweidner 3y agoIn my experience, this depends a lot more on the implementation than the CRDT algorithm. If you implement Causal Trees directly (as a tree with one node per char), it will be tolerably fast but use a lot of memory + storage. If you instead group chars into "runs" of sequentially-inserted chars and only store one Causal Tree node per run, it should be quite efficient. Yjs (a widely used text CRDT) describes these sort of opts here: https://blog.kevinjahns.de/are-crdts-suitable-for-shared-editing/ https://blog.kevinjahns.de/are-crdts-suitable-for-shared-edi... For a different tree-based CRDT, I did a head-to-head comparison of implementations that use a node-per-char (Fugue Simple) vs runs (Fugue), with results in Section 5 of this paper: https://arxiv.org/abs/2305.00583 https://arxiv.org/abs/2305.00583
- alephnan 3y ago> Don’t fret if you’re a fan of central authority though, Figma successfully uses CRDTs server-side to handle the collaborative aspects of their product, as well as Soundcloud and many others. Why bother with CRDTs if you’re doing server-side synchronization? MMORPGs can handle synchronizing thousands of users without problem.
- hnb2137 3y agoCRDTs solve the problem of concurrent updates bij users.
- tomaskafka 3y agoAnd offline edits from concurrent users
- OskarS 3y agoI've always wondered if it's a good trick for horizontal scaling as well. Like, if you have one server serving 1,000,000 clients, using a CRDT you could trivially split that up into 10 servers serving 100,000 clients each, and then have the ten servers be peers to each other.
- josephg 3y agoThe one “downside” compared to regular databases is that CRDTs use optimistic concurrency. If you want transaction support, or want multiple writers to block each other, CRDTs are a bad fit. They move conflict resolution to the point when reads happen rather than make writers fetch and retry. Still fine for a lot of use cases though.
- fauigerzigerk 3y ago>The one “downside” compared to regular databases is that CRDTs use optimistic concurrency. My understanding of the term "optimistic concurrency" is that a write operation can fail if the optimism turns out to be misplaced (so to speak). CRDTs on the other hand always merge deterministically and never fail, even if application level consistency constraints are violated. This is why CRDTs are rarely useful to me, but I can see how they may be useful in domains that can live with the very weak form of consistency guarantees that CRDTs can provide.
- CodeGroyper 3y agoI don't know what CRDT stands for, can anyone tell me?
- deleted 3y ago[deleted]
- OskarS 3y agoConflict-free Replicated Data Types. It's essentially a way to make Google Docs-style products which are resilient in the face of disconnects and reconnects and slow syncing. Think of it like Git, but all merge conflicts are resolved automatically and deterministically.
- cma 3y agoConflict-Free Replicated Data Type
- mweidner 3y agoAnother name for Causal Trees is "RGA" (Replicated Growable Array). They are ~identical algorithms that were published concurrently. E.g., Automerge uses RGA (https://automerge.org/docs/documents/#lists https://automerge.org/docs/documents/#lists).
- euroderf 3y agoif you like CRDTs, have a look at pijul version control.
- andai 3y agoWhat does SoundCloud need CRDTs for?
- refulgentis 3y agoI grep'd Soundcloud, then clicked the <a href> wrapping it, it linked here: https://github.com/soundcloud/roshi https://github.com/soundcloud/roshi (tl;Dr: time-series event storage via a LWW-element-set)
- andai 3y agoYeah I found this page and as a SoundCloud user I have no idea what this is about. So it's not some user facing collaborative music feature I didn't know about, it just gives them more consistent analytics?