5 ms·

CRDTs solve merge conflicts by construction, because they necessarily don't permit merge conflicts in the first place.

by kiitos 2y ago

bombela 2y ago
Alright, try this in Google Doc. Two users simultaneously select the same word, and replace it by a different word each. You might end up with: "apple" -> "carrot orange" Sure it technically merged, and did not lose data. But you still need humans to reconcile the final state anyways. Worse, you might not even notice that you need to cleanup.
- deleted 2y ago
  [deleted]
- vlovich123 2y ago
  Bad example. Google docs doesn’t use CRDTs but uses OT instead. CRDTs may handle your scenario just fine depending on how they decide to handle this scenario. The easier scenario that is independent of the specific algorithm is the one I described (have follow up comments describing it in more explicit detail) where you have a logical meta instruction within the document and then the document is updated based on outdated meta instructions offline but when they come back online the meta instructions were changed. Then there’s not even a merge conflict to really worry about.
  - mattarm 2y ago
    > Bad example. Google docs doesn’t use CRDTs but uses OT instead. CRDTs may handle your scenario just fine depending on how they decide to handle this scenario. The CRDT may pick one or the other replacement word, but who is to say that either choice is correct? Perhaps including both words is correct. > Then there’s not even a merge conflict... Agree, this is what CRDTs are all about. > ...to really worry about. I think it is important to make clear that CRDTs do not "solve" the merging problem, they merely make it possible to solve in a deterministic way across replicas. Often, CRDTs do not capture higher level schema invariants, and so a "conflict free" CRDT merge can produce an invalid state for a particular application. There is also the example above, where at the application level, one particular merge outcome may be preferred over another. So, it isn't as simple as having nothing to worry about. When using CRDTs, often, there are some pretty subtle things that must be worried about. :-)
    - vlovich123 2y ago
      Yup 100% agreed.
    - kiitos 2y ago
      > The CRDT may pick one or the other replacement word, but who is to say that either choice is correct? You, as the application developer. > I think it is important to make clear that CRDTs do not "solve" the merging problem They literally do, in the context in which they are defined. Which is about data consistency, not semantic correctness. > Often, CRDTs do not capture higher level schema invariants, CRDTs never capture higher level schema invariants. Just like TCP doesn't enforce HTTP session authentication. Orthogonal concerns.
xnorswap 2y ago
By definition they don't have conflicts in the technical sense of the word, but they can easily get into bad states after a merge. It's not technically a conflict since there is a path forward, but the resulting output can be nonsensical. For example you could employ a strategy where given two concurrent edits, the merge "randomly*" picks one of the two edits for each property/fact, and abandons the other. That's a construction of a conflict free replicated data type, but it says nothing of the quality of the final result. Ultimately, the quality comes down to how well you can produce merge strategies for your domain. * "Randomly" in a deterministic way, e.g. by comparing a hashes of transaction IDs or similar.
- kiitos 2y ago
  > By definition they don't have conflicts in the technical sense of the word... ...which is the sense that we're talking about, when we talk about CRDTs.
  - Dylan16807 2y ago
    When someone goes into detail about correct versus convergent, they are explaining how the technical sense is not what people really want, and you bluntly replying that it's solved (because it's technically solved) is unhelpful at best and misleading at worse.
    - kiitos 2y ago
      A CRDT is a purely technical construct! Correctness (in terms of merge conflicts) is well-defined in that context and it's orthogonal to any kind of semantic/application definition! This is a bonkers conversation. It's like claiming integer division isn't correct because 5/2 should be 2.5 instead of 2.

CRDTs solve merge conflicts by construction, because they necessarily don't permit merge conflicts in the first place.

by kiitos 2y ago

CRDTs solve merge conflicts by construction, because they necessarily don't permit merge conflicts in the first place.

Alright, try this in Google Doc. Two users simultaneously select the same word, and replace it by a different word each. You might end up with: "apple" -> "carrot orange" Sure it technically merged, and did not lose data. But you still need humans to reconcile the final state anyways. Worse, you might not even notice that you need to cleanup.

deleted 2y ago
[deleted]
vlovich123 2y ago
Bad example. Google docs doesn’t use CRDTs but uses OT instead. CRDTs may handle your scenario just fine depending on how they decide to handle this scenario. The easier scenario that is independent of the specific algorithm is the one I described (have follow up comments describing it in more explicit detail) where you have a logical meta instruction within the document and then the document is updated based on outdated meta instructions offline but when they come back online the meta instructions were changed. Then there’s not even a merge conflict to really worry about.
- mattarm 2y ago
  > Bad example. Google docs doesn’t use CRDTs but uses OT instead. CRDTs may handle your scenario just fine depending on how they decide to handle this scenario. The CRDT may pick one or the other replacement word, but who is to say that either choice is correct? Perhaps including both words is correct. > Then there’s not even a merge conflict... Agree, this is what CRDTs are all about. > ...to really worry about. I think it is important to make clear that CRDTs do not "solve" the merging problem, they merely make it possible to solve in a deterministic way across replicas. Often, CRDTs do not capture higher level schema invariants, and so a "conflict free" CRDT merge can produce an invalid state for a particular application. There is also the example above, where at the application level, one particular merge outcome may be preferred over another. So, it isn't as simple as having nothing to worry about. When using CRDTs, often, there are some pretty subtle things that must be worried about. :-)
  - vlovich123 2y ago
    Yup 100% agreed.
  - kiitos 2y ago
    > The CRDT may pick one or the other replacement word, but who is to say that either choice is correct? You, as the application developer. > I think it is important to make clear that CRDTs do not "solve" the merging problem They literally do, in the context in which they are defined. Which is about data consistency, not semantic correctness. > Often, CRDTs do not capture higher level schema invariants, CRDTs never capture higher level schema invariants. Just like TCP doesn't enforce HTTP session authentication. Orthogonal concerns.

xnorswap 2y ago

By definition they don't have conflicts in the technical sense of the word, but they can easily get into bad states after a merge. It's not technically a conflict since there is a path forward, but the resulting output can be nonsensical. For example you could employ a strategy where given two concurrent edits, the merge "randomly*" picks one of the two edits for each property/fact, and abandons the other. That's a construction of a conflict free replicated data type, but it says nothing of the quality of the final result. Ultimately, the quality comes down to how well you can produce merge strategies for your domain. * "Randomly" in a deterministic way, e.g. by comparing a hashes of transaction IDs or similar.

kiitos 2y ago
> By definition they don't have conflicts in the technical sense of the word... ...which is the sense that we're talking about, when we talk about CRDTs.
- Dylan16807 2y ago
  When someone goes into detail about correct versus convergent, they are explaining how the technical sense is not what people really want, and you bluntly replying that it's solved (because it's technically solved) is unhelpful at best and misleading at worse.
  - kiitos 2y ago
    A CRDT is a purely technical construct! Correctness (in terms of merge conflicts) is well-defined in that context and it's orthogonal to any kind of semantic/application definition! This is a bonkers conversation. It's like claiming integer division isn't correct because 5/2 should be 2.5 instead of 2.