Causal Trees | Hacker News Reader

Causal Trees

farley.ai

235 pointssno629 comments

Another 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).

That is true, but I think the CT paper frames the algorithm in a much clearer way than the RGA paper does. It’s a pleasure to read.

RGA is a terrible name. It sounds more like some sort of new alternative to B-Trees than a concurrent data structure.

How 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.

I 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/

"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."

Thanks 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.

I'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

[1] https://practal.com/recursivetext/

[2] https://martin.kleppmann.com/papers/list-move-papoc20.pdf

[3] https://redux.js.org/usage/structuring-reducers/normalizing-...

Sounds 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.

Ok, thank you, appreciate the "here be dragons"!

Definitely interested in how you achieved another 2-10x over the btree approach. I want surprised that btree was as effective as it was, but I’d be curious to know how you squeezed a bit more out of it.

The btree works great, and has barely changed. I made it faster with two tricks:

1. I made my own rope library (jumprope) using skip lists. Jumprope is about 2x faster than ropey on its own. And I have a wrapper around the skip list (called “JumpropeBuf” in code) which buffers a single incoming write before touching the skip list. This improves raw replay performance over ropey by 10-20x iirc.

2. Text (“sequence”) CRDTs replicate a list / tree of fancy “crdt items” (items with origin left / origin right / etc). This special data structure needs to be available both to parse incoming edits and generate local edits.

Turns out that’s not the only way you can build systems like this. Diamond types now just stores the list of original edits. [(Edit X: insert “X” position 12, parent versions Y, Z), …]. Then we recompute just enough of the crdt structure on the fly when merging changes.

This has a bunch of benefits - it makes it possible to prune old changes, it lowers memory usage (you can just stream writes to disk). The network and disk formats aren’t dependant on some weird crdt structure that might change next week. (Yjs? RGA? Fugue?). File size is also smaller.

And the best bit: linear traces don’t need the btree step at all. Linear traces go as fast as the rope. Which - as I said above, is really really fast. Even when there are some concurrent edits and the btree is created, any time the document state converges on all peers we can discard all the crdt items we generated so far and start again. Btrees are O(log n). This change essentially keeps resetting n, which gives a constant size performance improvement.

The downside is that the code to merge changes is more complex now. And it’s slower for super complex traces (think dozens of concurrent branches in git).

I’m writing a paper at the moment about the algorithm. Should be up in a month or two.

In 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-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

This 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.

> 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.

CRDTs solve the problem of concurrent updates bij users.

And offline edits from concurrent users

I'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.

The 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.

>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.

> even if application level consistency constraints are violated.

I think, in theory at least, it should be possible to encode the application level constrains into the CRDT merging algorithm. Like how two edits making different (but overlapping) spans bold are fine to merge into one bold span, but i.e highlighting with different colors are not.

Of course the merge will never be "perfect", as it is impossible to encode all human wishes into the CRDT, but I think there is a lot of room to improve when it comes to merging non-text data.

I don't think it is theoretically possible, but even if it was, it would be tantamount to inventing one or more new CRDTs per application. Each begin/end transaction block would become its own research project.

I don't know what CRDT stands for, can anyone tell me?

Conflict-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.

What does SoundCloud need CRDTs for?

I grep'd Soundcloud, then clicked the <a href> wrapping it, it linked here: https://github.com/soundcloud/roshi

(tl;Dr: time-series event storage via a LWW-element-set)

Yeah 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?

if you like CRDTs, have a look at pijul version control.

Conflict-Free Replicated Data Type

You posted this 2 times in 3 hours. By the way, Your connection is not private.

Reply on news.ycombinator.com