5 ms·

It is impossible to have accurate conflict-free replicated data. Unless the users are given the opportunity to manually resolve conflicts, it will never be 100%

It is impossible to have accurate conflict-free replicated data. Unless the users are given the opportunity to manually resolve conflicts, it will never be 100% accurate - Incorrect data will creep in from time to time (but at least the incorrect data will be consistent across all nodes). The root of the problem is that the system cannot understand the collaborative intent of concurrent users - If you have 2 users who made a change at the same time (without being aware of each other); you have to account for the fact that maybe UserB would have behaved differently if they had been aware of UserA's input (which happened at the same time while one or both users were offline). If the user has been offline for a while - Many such conflicts could arise (maybe by the time the internet comes back on, the user is looking at a completely different page than the one they made the change on) and it's tedious to make the user resolve them all manually. Also with this approach, it tends to force you to keep a copy/cache of all the data in your entire app (for that logged-in user) on the frontend - If you have a big app with lots of pages, that could consume a lot of memory. There are cases where the best solution is to simply tell the user "Sorry, you do not have an internet connection at the moment, so you cannot modify this data" rather than giving them a false sense that the data are correctly backed up in the cloud. I think with CRDTs, it's really important to inform the user when they are offline and when their data are not synced/backed up in the cloud (so they don't get any bad surprises when the internet suddenly comes back on). CRDTs are good where the accuracy of the data is not critical (E.g. bank transactions). One could argue that they improve the user experience, but at the core, developers like them because they make life easier.

pjc50 10y ago
CRDTs are good where the accuracy of the data is not critical (E.g. bank transactions). It's interesting you say that given that banking invented eventual consistency with manual reconciliation of exceptions, in the form of the cheque.
jorangreef 10y ago
"It is impossible to have accurate conflict-free replicated data. Unless the users are given the opportunity to manually resolve conflicts, it will never be 100% accurate [...] The root of the problem is that the system cannot understand the collaborative intent of concurrent users" CRDTs are usually designed to model user intent. You just need to pick the right CRDT for your use-case. From there, the CRDT will resolve conflicts automatically and accurately. Your statement regarding impossibility would be true of operational transformation, but certainly not of CRDTs.
- btrask 10y ago
  The problem is that the user's data itself needs to be conflict-free. For example, no programming language models its source code as a CRDT, so DVCSes will always produce merge conflicts (or worse, silently broken merges). CRDTs are a fundamentally leaky abstraction. That doesn't mean they're bad, and the payoff of offline modification is very tempting. It just means they're hard to use.
  - jorangreef 10y ago
    "The problem is that the user's data itself needs to be conflict-free" The user's data needs to support being modeled by a series of commutative operations. "CRDTs are a fundamentally leaky abstraction" Are non-commutative data types less fundamentally leaky than commutative data types?
  - Jweb_Guru 10y ago
    In what sense are CRDTs "leaky"? Do you mean that they aren't composable in the way linearizable registers ostensibly are? It turns out that partially commutative monoids combined with invariants can form "logically atomic specifications" that emulate linearizability, and are thus composable: http://plv.mpi-sws.org/iris/paper.pdf http://plv.mpi-sws.org/iris/paper.pdf. And there are ways to get consistent reads out of CRDTs, too: http://www.cs.indiana.edu/~lkuper/papers/threshold-queries-draft.pdf http://www.cs.indiana.edu/~lkuper/papers/threshold-queries-d.... I'm not saying that all CRDTs fall into this framework, but it's at least nonobvious to me.
- jamesdsadler 10y ago
  To the extent that CRDTs are conflict-free it only means that two edits can commute (be applied in any order) and every party that has applied the same set of edits will produce the same result. At the low-level that the CRDT is operating on there will be no conflicts. But that does not mean that the user never perceives there to be conflicts. No matter what the consensus system used be it CRDTs or OT at some point the converge operation has to impose a total ordering to pick a "winner" in the case of conflicting user edits. If editing a block of text and two users try to replace the same word with another word there are a number of possible outcomes 1) One of the edits "wins" 2) The word is replaced by the concatenation of each user's replacement. 3) Nobody wins and the edit is reverted. In all cases at least one party perceives to themselves to have "lost". But it generally doesn't matter because humans doing the editing will make repairs to nonsensical edits in real time. There has to be a tie-breaker when multiple users try to make different edits to the same region of text. At least that's my current understanding.
amelius 10y ago
If the system is based on merging, then in general it is not a good solution. It works in a lot of cases (see git), but essentially, on every merge the algorithm does a "hmm, how did these changes happen?" instead of taking into account the semantics in a rigorous way. But in many practical situations, merging can be considered a very useful "hack".
disordinary 10y ago
The most important thing is to display the content to every user and allow them to update the intent if the CRDT rules are incorrect for that use case. Therefore the most important thing is not the fact that it's conflict-free, it's that it builds exactly the same document for all users no matter what order the operations are applied in (if it's operations based, rather than merge based).
- jorangreef 10y ago
  "the most important thing is not the fact that it's conflict-free" CRDT is actually an acronym for both "Conflict-free replicated data type" and "Commutative replicated data type". Both properties are provided by a CRDT by definition. Both properties are equally important. "(if it's operations based, rather than merge based)" CRDTs are commutative by definition irrespective of whether they are operation based or state based.
  - skybrian 10y ago
    As I understand it, sometimes they do this via techniques roughly similar to inserting change markers (that is, remember both versions). The change may technically be "conflict free" according to the algorithm's definition, but from the user's point of view, the merge has not been completed until you pick which version to keep. Informally, each place we need to manually do a merge can be considered an unresolved conflict according to an alternate definition of "conflict".
    - jorangreef 10y ago
      If you need to pick a version, then it's not a CRDT. Normally, you would use the right CRDT to fit the problem space, provided the problem space can be modeled using commutative operations. CRDTs require the problem space to be defined in terms of commutative operations. That's just a requirement of the data structure, just like binary search requires a sorted list. If that requirement is met, then there would be no conflicts and no merges by design. That's the beauty of CRDTs. They are perfect for multi-master distributed settings. You wouldn't use a CRDT to store the raw contents of an Excel document or a Javascript file, since those file formats were not designed to be modeled using commutative operations. I think that's the use case you have in mind? For that you would need manual merges, regardless of the data structure or binary string you use to represent the document.
arielb1 10y ago
If you have an API on a shared data structure, either you have distributed locking or you have conflicts. Distributed locking sucks, but CRDTs only prevent conflicts from messing up your data structure, not from existing.

pjc50 10y ago

CRDTs are good where the accuracy of the data is not critical (E.g. bank transactions). It's interesting you say that given that banking invented eventual consistency with manual reconciliation of exceptions, in the form of the cheque.

jorangreef 10y ago

"It is impossible to have accurate conflict-free replicated data. Unless the users are given the opportunity to manually resolve conflicts, it will never be 100% accurate [...] The root of the problem is that the system cannot understand the collaborative intent of concurrent users" CRDTs are usually designed to model user intent. You just need to pick the right CRDT for your use-case. From there, the CRDT will resolve conflicts automatically and accurately. Your statement regarding impossibility would be true of operational transformation, but certainly not of CRDTs.

btrask 10y ago
The problem is that the user's data itself needs to be conflict-free. For example, no programming language models its source code as a CRDT, so DVCSes will always produce merge conflicts (or worse, silently broken merges). CRDTs are a fundamentally leaky abstraction. That doesn't mean they're bad, and the payoff of offline modification is very tempting. It just means they're hard to use.
- jorangreef 10y ago
  "The problem is that the user's data itself needs to be conflict-free" The user's data needs to support being modeled by a series of commutative operations. "CRDTs are a fundamentally leaky abstraction" Are non-commutative data types less fundamentally leaky than commutative data types?
- Jweb_Guru 10y ago
  In what sense are CRDTs "leaky"? Do you mean that they aren't composable in the way linearizable registers ostensibly are? It turns out that partially commutative monoids combined with invariants can form "logically atomic specifications" that emulate linearizability, and are thus composable: http://plv.mpi-sws.org/iris/paper.pdf http://plv.mpi-sws.org/iris/paper.pdf. And there are ways to get consistent reads out of CRDTs, too: http://www.cs.indiana.edu/~lkuper/papers/threshold-queries-draft.pdf http://www.cs.indiana.edu/~lkuper/papers/threshold-queries-d.... I'm not saying that all CRDTs fall into this framework, but it's at least nonobvious to me.
jamesdsadler 10y ago
To the extent that CRDTs are conflict-free it only means that two edits can commute (be applied in any order) and every party that has applied the same set of edits will produce the same result. At the low-level that the CRDT is operating on there will be no conflicts. But that does not mean that the user never perceives there to be conflicts. No matter what the consensus system used be it CRDTs or OT at some point the converge operation has to impose a total ordering to pick a "winner" in the case of conflicting user edits. If editing a block of text and two users try to replace the same word with another word there are a number of possible outcomes 1) One of the edits "wins" 2) The word is replaced by the concatenation of each user's replacement. 3) Nobody wins and the edit is reverted. In all cases at least one party perceives to themselves to have "lost". But it generally doesn't matter because humans doing the editing will make repairs to nonsensical edits in real time. There has to be a tie-breaker when multiple users try to make different edits to the same region of text. At least that's my current understanding.

amelius 10y ago

If the system is based on merging, then in general it is not a good solution. It works in a lot of cases (see git), but essentially, on every merge the algorithm does a "hmm, how did these changes happen?" instead of taking into account the semantics in a rigorous way. But in many practical situations, merging can be considered a very useful "hack".

disordinary 10y ago

The most important thing is to display the content to every user and allow them to update the intent if the CRDT rules are incorrect for that use case. Therefore the most important thing is not the fact that it's conflict-free, it's that it builds exactly the same document for all users no matter what order the operations are applied in (if it's operations based, rather than merge based).

jorangreef 10y ago
"the most important thing is not the fact that it's conflict-free" CRDT is actually an acronym for both "Conflict-free replicated data type" and "Commutative replicated data type". Both properties are provided by a CRDT by definition. Both properties are equally important. "(if it's operations based, rather than merge based)" CRDTs are commutative by definition irrespective of whether they are operation based or state based.
- skybrian 10y ago
  As I understand it, sometimes they do this via techniques roughly similar to inserting change markers (that is, remember both versions). The change may technically be "conflict free" according to the algorithm's definition, but from the user's point of view, the merge has not been completed until you pick which version to keep. Informally, each place we need to manually do a merge can be considered an unresolved conflict according to an alternate definition of "conflict".
  - jorangreef 10y ago
    If you need to pick a version, then it's not a CRDT. Normally, you would use the right CRDT to fit the problem space, provided the problem space can be modeled using commutative operations. CRDTs require the problem space to be defined in terms of commutative operations. That's just a requirement of the data structure, just like binary search requires a sorted list. If that requirement is met, then there would be no conflicts and no merges by design. That's the beauty of CRDTs. They are perfect for multi-master distributed settings. You wouldn't use a CRDT to store the raw contents of an Excel document or a Javascript file, since those file formats were not designed to be modeled using commutative operations. I think that's the use case you have in mind? For that you would need manual merges, regardless of the data structure or binary string you use to represent the document.

arielb1 10y ago

If you have an API on a shared data structure, either you have distributed locking or you have conflicts. Distributed locking sucks, but CRDTs only prevent conflicts from messing up your data structure, not from existing.