[HN Gopher] Causal Trees
___________________________________________________________________
Causal Trees
Author : sno6
Score : 207 points
Date : 2023-12-16 03:55 UTC (19 hours ago)
(HTM) web link (www.farley.ai)
(TXT) w3m dump (www.farley.ai)
| jasonjmcghee wrote:
| 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.
| shoarek wrote:
| You posted this 2 times in 3 hours. By the way, Your connection
| is not private.
| bytearray wrote:
| 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.
| zogrodea wrote:
| 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."
| josephg wrote:
| 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.
| practal wrote:
| 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-...
| josephg wrote:
| 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.
| mattarm wrote:
| 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.
| josephg wrote:
| 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.
| mweidner wrote:
| 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
| alephnan wrote:
| > 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 wrote:
| CRDTs solve the problem of concurrent updates bij users.
| tomaskafka wrote:
| And offline edits from concurrent users
| OskarS wrote:
| 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.
| josephg wrote:
| 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.
| fauigerzigerk wrote:
| _> 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.
| filleokus wrote:
| > 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.
| fauigerzigerk wrote:
| 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.
| CodeGroyper wrote:
| I don't know what CRDT stands for, can anyone tell me?
| OskarS wrote:
| 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.
| cma wrote:
| Conflict-Free Replicated Data Type
| mweidner wrote:
| 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).
| archagon wrote:
| 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.
| euroderf wrote:
| if you like CRDTs, have a look at pijul version control.
| andai wrote:
| What does SoundCloud need CRDTs for?
| refulgentis wrote:
| 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)
___________________________________________________________________
(page generated 2023-12-16 23:01 UTC)