Hacker News Reader

Comment by mrkeen | Hacker News Reader

I've looked at CRDTs, and the concept really appeals to me in the general case, but in the specific cases, my design always ends up being "keep-all-the-facts" about a particular item. But then you defer the problem of 'which facts can I throw away?'. It's like inventing a domain-specific GC.

I'd love to hear about any success cases people have had with CRDTs.

View on HN

There was an article on this website not so long ago about using CRDTs for collaborative editing and there was this silly example to show how leaky this abstraction can be. What if your have the word "color" and one user replaces it with "colour" and another deletes the word, what does the CRDT do in this case? Well it merges this two edits into "u". This sort of makes me skeptical of using CRDTs for user facing applications.

There isn’t a monolithic “CRDT” in the way you’re describing. CRDTs are, broadly, a kind of data structure that allows clients to eventually agree on a final state without coordination. An integer `max` function is a simple example of a CRDT.

The behavior the article found is peculiar to the particular CRDT algorithms they looked at. But they’re probably right that it’s impossible for all conflicting edits to “just work” (in general, not just with CRDTs). That doesn’t mean CRDTs are pointless; you could imagine an algorithm that attempts to detect such semantic conflicts so the application can present some sort of resolution UI.

Here’s the article, if interested (it’s very good): https://www.moment.dev/blog/lies-i-was-told-pt-1

> There isn’t a monolithic “CRDT” in the way you’re describing.

I can't blame people for thinking otherwise, pretty much every self-called "CRDT library" I've come across implements exactly one such data structure, maybe parameterized.

It's like writing a "semiring library" and it's simply (min, +).

It's still early, but we have a checkpointing system that works very well for us. And once you have checkpoints you can start dropping inconsequential transactions in between checkpoints, which you're right, can be considered GC. However, checkpointing is desirable anyway otherwise new users have to replay the transaction log from T=0 when they join, and that's impractical.

I've also had success with this method. "domain-specific GC" is a fitting term.

For me the main issue with CRDTs is that they have a fixed merge algorithm baked in - if you want to change how conflicts get resolved, you have to change the whole data structure.

I feel like the state-of-the-art here is slowly starting to change. I think CRDTs for too many years got too caught up in "conflict-free" as a "manifest destiny" sort of thing more than "hope and prayer" and thought they'd keep finding the right fixed merged algorithm for every situation. I started watching CRDTs from the perspective of source control and having a strong inkling that "data is always messy" and "conflicts are human" (conflicts are kind of inevitable in any structure trying to encode data made by people).

I've been thinking for a bit that it is probably about time the industry renamed that first C to something other than "conflict-free". There is no freedom from conflicts. There's conflict resistance, sure and CRDTs can provide in their various data structures a lot of conflict resistance. But at the end of the day if the data structure is meant to encode an application for humans, it needs every merge tool and review tool and audit tool it can offer to deal with those.

I think we're finally starting to see some of the light in the tunnel in the major CRDT efforts and we're finally leaving the detour of "no it must be conflict-free, we named it that so it must be true". I don't think any one library is yet delivering it at a good high level, but I have that feeling that "one of the next libraries" is maybe going to start getting the ergonomics of conflict handling right.

This seems right to me -- imagine being able to tag objects or sub-objects with conflict-resolution semantics in a more supported way (like LWW, edits from a human, edits from automation, human resolution required (with or without optimistic application of defaults, etc).

Throwing small language models into the mix could make merging less painful too — like having the system take its best guess at what you meant, apply it, and flag it for later review.

I just want some structure where it is conflict-free most of the time but I can write custom logic in certain situations that is used, sort of like an automated git merge conflict resolution function.

I've been running into this with automated regex edits. Our product (Relay [0]) makes Obsidian real-time collaborative using yjs, but I've been fighting with the automated processes that rewrites markdown links within notes.

The issue happens when a file is renamed by one client, and then all other clients pick up the rename and make the change to the local files on disk. Since every edit is broken down into delete/keep/insert runs, the automated process runs rapidly in all clients and can break the links.

I could limit the edits to just one client, but it feels clunky. Another thought I've had is to use ytext annotations, or just also store a ymap of the link metadata and only apply updates if they can meet some kind of check (kind of like schema validation for objects).

If anyone has a good mental model for modeling automated operations (especially find/replace) in ytext please let me know! (email in bio).

[0] https://system3.md/relay

Reply on news.ycombinator.com