Hacker News Reader

Comment by cbm-vic-20 | Hacker News Reader

The article sets up a scenario where two people are editing a document, but have conflicting changes: "If Alice fixes a missing letter in a word while Bob removes the whole word, that’s a conflict."

The article then goes into some examples of CRDTs and their merge operation, and the examples are pretty straightforward: take the maximum of two values, or take one with a more recent timestamp, etc.

But what about the motivating example? What should a merge function do with the inputs "change the third word from 'affect' to 'effect'" and "delete the third word"? In other words, how does the function know which of these operations "wins"? It could ask a user for a manual resolution, but is there a reasonable way for a function to make this determination itself? Maybe deletes are more powerful than word changes, so the delete wins.

View on HN

The "conflict-free" part of the name is misleading. The conflict "resolution" means having some deterministic algorithm such that all nodes eventually converge to the same state, but it won't necessarily mean that the end state looks like it's conflict-free to a human. The algorithm you choose to implement will determine what happens in the editing case imagined; various answers are possible, perhaps most of which would be classified as conflicting changes by a human who looked at the final result. The pitch for CRDTs is "we won't trouble you with the replication details and will eventually converge all the changes. The tradeoff is that sometimes we'll do the wrong thing."

That tradeoff is fine for some things but not others. There's a reason why git et al require human intervention for merge conflicts.

The article is doing a classic bait-and-switch: start with a motivating example then dodge the original question without pointing out that CRDTs may be a very bad choice for collaborative editing. E.g. maybe it's bad for code and legalese but fine for company-issued blog posts.

I think people who haven't worked on problems like this have much higher expectations than people who have.

If you have worked on problems like this, you're very happy to converge on the same state and have no expectation that multiple concurrent editors will be happy with the result. Or even that one of them will be happy with the result.

You wouldn't use this in a situation like version control where you have to certify a state as being acceptable to one or multiple users.

to add on to that, it is that the resolution is the same regardless of the order in which the nodes get the information that led to the conflict so there is no "out of sync". your resolution strategy could involve considering the potential conflict unresolved until a resolution element is created (but then you have to figure out what to do if you get more than one of those.. its conflicts all the way down!)

Yes, it's impossible for a distributed system to figure out the collaborative intent when it sees conflicting changes... Even the people who made the changes may not 'know' what is the correct way to resolve the conflict... For that to happen, people involved would have to communicate and agree on either option or they would have to agree on a compromise. This problem cannot be solved automatically because computers cannot read minds (yet).

This is why I like using granular data structures where each value can be updated in an all-or-nothing manner and if one person's change overwrites another, the person whose change was overwritten will just assume that the other person made an update shortly after and the amount overwritten is minimal.

I think the really interesting problem in this space is designing UIs and data structures that, on the one hand, capture as much user intent as possible, but, more importantly, make it easier for users to manage conflicts.

I.e., if there's a tricky conflict, the app need not resolve it at all. Rather, it should provide, by default, a nice way for the user to manage the resolution as part of the normal workflow.

Or, phrased another way, conflicts aren't conflicts. Parallel, "conflicting" edits are simply a state of affairs that is inherent to the process, and are still reflected in the data structure after merging all edits.

How this would actually look would probably vary from domain to domain. But my general philosophy on this stuff is that if complexity is real and potentially important to the user, the software should expose the complexity and enable the user to manage it, not force a simplification that hides something important.

For CRUD applications with real-time updates, I find that updating individual fields as opposed to overwriting the entire record works sufficiently well. It can be dome relatively cheaply using WebSockets. Would be overkill to use HTTP to update individual fields (as each request carries redundant headers) but WebSocket frames are very lightweight. I've built a serverless platform on this principle and it helps to simplify the frontend components.

CRDTs really provide a nice formalism for reasoning about design choices in this space, almost more so than being a practical solution in and of themselves. For your example operational transformations have long been used as the way to go.

My experience of CRDTs is it rapidly descends into a question of defining if two things are in fact equal or merely look equal. i.e. if two people concurrently add "this is a new item" to a set did they create two separate items or the same thing?

Is the answer clearer if you consider two changes, A to B and A to X? The conflict free result is to change A to BX, distribute this to every node, and let the people decide. (This is what Automerge does?)

(Deleting a word is just changing it from word to ~word~ with the option to render conflict free deletions as empty space.)

There is no objectively correct way to do the merge, but there are ways that are obviously wrong.

I think it's your job as a designer to encode which update should win. In case of equivalent updates like writing to a field they suggest 'last update wins" strategy.

For words, if a word is a single unit in your system, delete obviously beats amendment.

This only works for very simple cases where there is already an existing strategy, but I have yet to see strategies for more complicated cases, especially ones where you also need to preserve some kind of consistency. Ultimately this boils down to "write your own CRDT", where CRDT is no longer a tool but just a definition to satisfy.

> suggest 'last update wins" strategy.

Hmm, last update as it's received by a central server? Last update according to the time on the device doing committing the update? The rabbit hole just keeps going, for each decision you get multiple new edge cases with unintended behavior...

CRDTs mostly have a time notions like Lamport clocks, vector clocks, ... not actual device time => see more here: https://adamwulf.me/2021/05/distributed-clocks-and-crdts/

All of which have their own weaknesses. And all of them can suffer the split brain scenario.

And all but the last one fundamentally have lots of edge cases with e.g. high-latency sync

CRDTs are not a solved problem as of today, there is no perfect solution in the current state-of-the-art, it's still a field with quite some active research.

It's most likely causality-based time, not the time per an atomic clock.

Sounds like a job for a block chain!

I mean your example is a classic case.

And there are different algos, for diamondtypes:

Once a character is seen by clients any delete of it wins, algos like diamond types reconstruct each clients stream.

So in the case of DT, effect is absolutely gone, two clients deleting the e and one client deleted the ffects, and they both started at the same causal slice, but the A is a good question. You might just end up with an A.

In the case of multiple inserts in the same position dt uses the client ids lexical sort for ordering to reduce text interleaving.

Other crdt approaches may be positional or last write wins, in which case you may end up with nothing.

Besides being an amazing project loro crdts documentation and blog covers a lot of this stuff and names the specific algos they use.

Reply on news.ycombinator.com