4 ms·

CRDT's largely can't rectify merge conflicts... what CRDT's can do is make your merges convergent. If I auto-merged your Git code using a blunt policy I don't k

CRDT's largely can't rectify merge conflicts... what CRDT's can do is make your merges convergent. If I auto-merged your Git code using a blunt policy I don't know if you'd reach for "correct" as your first description as opposed to "convergent". The longer you're offline the more you have to explain to your users the circumstances where they might need to do manual data cleanup or expect creative merging policy. No matter what tech you're using.

ErikBjare 2y ago
This is true if you're working with documents edited by different devices, but many CRDTs do not and can indeed be not only "convergent" but also "correct". How SSB works is a good example.
- vlovich123 2y ago
  Can’t find what SSB is. Can you clarify? But yes, it’s possible there are applications that can constrain the set of operations such that the merged result is also correct. I was just highlighting that CRDTs are trotted out as a catch all when a) it’s just a way of thinking about the problem rather than an actual algorithm (eg while there’s a lot of CRDT work for document editing, that work has to be done for scratch for any other problem domain) b) you have to modify your problem constrains and solution such that merge results are correct. B is a very very hard problem in a distributed system even if you ignore the challenge of a which itself is quite hard. I wouldn’t trust anything in this space too much without a TLA+ proof that it’s correct (unless it’s something low stakes like document editing).
  - endgame 2y ago
    I think SSB is "Secure Scuttlebutt": http://ssbc.github.io/ssb-db/ http://ssbc.github.io/ssb-db/
  - threatofrain 2y ago
    Some of our most important DB sync'ing algorithms were only very recently verified. It was okay to run the whole world's systems, including hospitals and armed forces this way. Very very few industry algos receive formal verification.
kiitos 2y ago
CRDTs solve merge conflicts by construction, because they necessarily don't permit merge conflicts in the first place.
- 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. :-)

ErikBjare 2y ago

This is true if you're working with documents edited by different devices, but many CRDTs do not and can indeed be not only "convergent" but also "correct". How SSB works is a good example.

vlovich123 2y ago
Can’t find what SSB is. Can you clarify? But yes, it’s possible there are applications that can constrain the set of operations such that the merged result is also correct. I was just highlighting that CRDTs are trotted out as a catch all when a) it’s just a way of thinking about the problem rather than an actual algorithm (eg while there’s a lot of CRDT work for document editing, that work has to be done for scratch for any other problem domain) b) you have to modify your problem constrains and solution such that merge results are correct. B is a very very hard problem in a distributed system even if you ignore the challenge of a which itself is quite hard. I wouldn’t trust anything in this space too much without a TLA+ proof that it’s correct (unless it’s something low stakes like document editing).
- endgame 2y ago
  I think SSB is "Secure Scuttlebutt": http://ssbc.github.io/ssb-db/ http://ssbc.github.io/ssb-db/
- threatofrain 2y ago
  Some of our most important DB sync'ing algorithms were only very recently verified. It was okay to run the whole world's systems, including hospitals and armed forces this way. Very very few industry algos receive formal verification.

kiitos 2y ago

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

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. :-)