Enjoyed the article! As someone who's worked on bits of collaborative software (and is currently helping build one at work), I'd caution people from using CRDTs in general. A central server is the right tool for the job in most cases; there are certain things that are difficult to handle with CRDTs, like permissions and acquiring locks on objects.
Edit: I had an excerpt here which I completely misread. Sorry.
Permissions can be handled with capability systems. Keyhive [0] is the furthest along on this. I've also made my own prototype [1] showing how certificate capabilities can be composed with CRDTs.
Last-Write-Win CRDTs are nice, but I wish the article talked about where CRDT really shine, which is when the state truly converge in a non-destructive way, for example:
1) Counters
While not really useful, they demonstrate this well:
- mutations are +n and -n
- their order do not matter
- converging the state is a matter of applying the operations of remote peers locally
2) Append-only data structures
Useful for accounting, or replication of time-series/logs with no master/slave relationship between nodes (where writes would be accepted only on a "master" node).
- the only mutation is "append"
- converging the state is applying the peers operations then sorting by timestamp
EDIT: add more
3) Multi Value registers (and maps)
Similar to Last-Write-Win registers (and maps), but all writes are kept, the value becomes a set of concurrent values.
4) Many more...
Each is useful for specific use cases. And since not everybody is making collaborative tools, but many are working on distributed systems, I think it's worth it to mention this.
On another note, the article talks about state based CRDTs, where you need to share the whole state. In the examples I gave above, they are operation based CRDTs, where you need to share the operations done on the state and recompute it when needed.
Delta-CRDTs are an optimization over state based CRDTs where you share state diffs instead of the whole state (described in this paper: https://arxiv.org/pdf/1603.01529 ).
I haven't dug into this deeply, but to me CRDTs look like a P2P data structure abstracted to the programming language variable level. The article says they shine when you don't want a central server. But most communication libraries already handle authentication and multiple peers well — and if you designate one peer as canonical (via leader election), conflict resolution is solved. I'm curious what use cases make avoiding a central server worth the paradigm shift. That said, it's a choice of approach — some may prefer the CRDT paradig
I've spent a lot of time studying CRDTs & order theory in the last year & will publish an article too. Local-first apps are not easy to build, complex data structures (say, calendar repetitions with exceptions) become harder to model. Everything must converge automatically while clients can branch off.
In general, you don't really get to compact tombstones meaningfully without consensus so you really are pushing at least remnants of the entire log around to each client indefinitely. You also can't easily upgrade your db you're stuck looking after legacy data structures indefinitely - or you have to impose arbitrary cut off points.
List CRDTs - which text CRDTs are built from are probably unavoidable except for really really simple applications. Over the last 15 years they have evolved, roughly: WOOT (paper) -> RGA (paper) -> YATA (paper) / YJS (js + later rust port) -> Peritext (paper) / Automerge (rust/js/swift) -> Loro (Rust/js). Cola (rust) is another recent one. The big libs (yjs, automerge, loro) offer full doc models.
Mostly the later ones improve on space, time & intent capture (not interleaving concurrent requests).
The same few guys (Martin Kleppman, Kevin Jahns, Joseph Gentle, probably others) pop up all over the more recent optimisations.
Regarding the growing log in CRDTs, it doesn't have to be that way. Most of these popular CRDT libs use Merkle DAG only to build up the log of the changes. But there is a better way, you can combine a Merkle DAG for ordering + prolly trees for storing the actual state of the data. That gives you total ordering, an easy way to prune old data when you choose to, and an easy way to sync. Look into fireproof for how this is combined.
Regarding distributed schemas, I agree, there's a lot of complexity there but it's worth looking into projects like https://www.inkandswitch.com/cambria/ and https://github.com/grafana/thema, which try to solve the problem. It's a young space though. If anyone else knows about similar projects or efforts, please let me know. Very interested in the space.
The tombstone problem is exactly why I built DocNode. You're right that you can't compact them without consensus, so DocNode just doesn't create them. It assumes a server decides the order, which is already the case in 99% of collaborative apps. The result: a doc stays the same size whether it was edited once or a thousand times. Yjs for the same doc grows every time someone types, pastes, or undoes. Check it out: https://docukit.dev
The "central server is usually right" framing holds until you hit cases where ordering matters and latency is non-negotiable. We ran into this building conversation stores for AI agents where concurrent turns need to converge without a strict lock - last-write-wins breaks fast when two agents update shared state mid-session. Hybrid approach: OT for the ordered log, CRDT-style semantics for ephemeral state. Not elegant but it works.
14 comments
[ 2.8 ms ] story [ 36.7 ms ] threadEdit: I had an excerpt here which I completely misread. Sorry.
[0] https://www.inkandswitch.com/keyhive/notebook/
[1] https://spritely.institute/news/composing-capability-securit...
An interactive intro to CRDTs - https://news.ycombinator.com/item?id=37764581 - Oct 2023 (130 comments)
Also a really well written piece.
1) Counters
While not really useful, they demonstrate this well:
2) Append-only data structuresUseful for accounting, or replication of time-series/logs with no master/slave relationship between nodes (where writes would be accepted only on a "master" node).
EDIT: add more3) Multi Value registers (and maps)
Similar to Last-Write-Win registers (and maps), but all writes are kept, the value becomes a set of concurrent values.
4) Many more...
Each is useful for specific use cases. And since not everybody is making collaborative tools, but many are working on distributed systems, I think it's worth it to mention this.
On another note, the article talks about state based CRDTs, where you need to share the whole state. In the examples I gave above, they are operation based CRDTs, where you need to share the operations done on the state and recompute it when needed.
For example, in the Elixir ecosystem, we have Horde ( https://hexdocs.pm/horde/readme.html ) which allows distributing a worker pool over multiple nodes, it's backed by DeltaCrdt ( https://hexdocs.pm/delta_crdt/DeltaCrdt.html ).
Delta-CRDTs are an optimization over state based CRDTs where you share state diffs instead of the whole state (described in this paper: https://arxiv.org/pdf/1603.01529 ).
In general, you don't really get to compact tombstones meaningfully without consensus so you really are pushing at least remnants of the entire log around to each client indefinitely. You also can't easily upgrade your db you're stuck looking after legacy data structures indefinitely - or you have to impose arbitrary cut off points.
List CRDTs - which text CRDTs are built from are probably unavoidable except for really really simple applications. Over the last 15 years they have evolved, roughly: WOOT (paper) -> RGA (paper) -> YATA (paper) / YJS (js + later rust port) -> Peritext (paper) / Automerge (rust/js/swift) -> Loro (Rust/js). Cola (rust) is another recent one. The big libs (yjs, automerge, loro) offer full doc models.
Mostly the later ones improve on space, time & intent capture (not interleaving concurrent requests).
The same few guys (Martin Kleppman, Kevin Jahns, Joseph Gentle, probably others) pop up all over the more recent optimisations.
Regarding distributed schemas, I agree, there's a lot of complexity there but it's worth looking into projects like https://www.inkandswitch.com/cambria/ and https://github.com/grafana/thema, which try to solve the problem. It's a young space though. If anyone else knows about similar projects or efforts, please let me know. Very interested in the space.
It would be interesting to try again now.