6 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 [...] 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.
- nkohari 10y ago
  There are several CRDT algorithms (LSEQ, Logoot, WOOT, Treedoc) that try to properly solve the merging solution (your outcome #2) while still retaining the intent of the edits of each user. Their implementations differ, but the general idea is that each character (or chunk of characters) is assigned a key that can be ordered. When new text is added, it's given a key that is derived from the key of some adjacent text. As a result, the merge is the best-possible approximation of the intent of the edits.
  - jamesdsadler 10y ago
    Yes, I think we are in agreement. The algorithm can use heuristics to produce a best-effort pleasing result that captures user intent but if two users want opposite things to happen it has to fall back to a tie breaker. In an extreme example, if the CRDT state-space was 1-bit and user A wants to make it a 0 and user B wants to make it a 1 a choice must be made by the algorithm.
    - nkohari 10y ago
zamalek 10y ago
Figure 4: replica p had the intent of deleting the node while replica q wanted to tick it. The final outcome is not what either human intended. Replica p would see their action partially reverted, replica q might not be able to discern their action in the list (or outright undone if the application skips invalid records). Consider storing a single value in a document: { "A": 1 } Q updates it to 2, P simultaneously updates it to 3. What is the correct outcome? Interactive consensus would be required even if humans were doing this by hand; unless quantum, there exists no accurate merge. That's not to say that CRDTs are useless, just not as grandiose as "automatic and accurate."
- rdtsc 10y ago
  It seems in this case it might be {"A" : [2, 3]} This kind of stuff is useful if users explicitly understand and design their application to expect this kind of stuff. It might not be possible always. But note, that there is still a good value in all the servers which got the same conflicts ending with the same result. As opposed to say server1: picking {"A" : 2} and server2 {"A" : 3}. Now something can be built on top of it given it understand and accounts for how merges happen.

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.

nkohari 10y ago
There are several CRDT algorithms (LSEQ, Logoot, WOOT, Treedoc) that try to properly solve the merging solution (your outcome #2) while still retaining the intent of the edits of each user. Their implementations differ, but the general idea is that each character (or chunk of characters) is assigned a key that can be ordered. When new text is added, it's given a key that is derived from the key of some adjacent text. As a result, the merge is the best-possible approximation of the intent of the edits.
- jamesdsadler 10y ago
  Yes, I think we are in agreement. The algorithm can use heuristics to produce a best-effort pleasing result that captures user intent but if two users want opposite things to happen it has to fall back to a tie breaker. In an extreme example, if the CRDT state-space was 1-bit and user A wants to make it a 0 and user B wants to make it a 1 a choice must be made by the algorithm.
  - nkohari 10y ago

zamalek 10y ago

Figure 4: replica p had the intent of deleting the node while replica q wanted to tick it. The final outcome is not what either human intended. Replica p would see their action partially reverted, replica q might not be able to discern their action in the list (or outright undone if the application skips invalid records). Consider storing a single value in a document: { "A": 1 } Q updates it to 2, P simultaneously updates it to 3. What is the correct outcome? Interactive consensus would be required even if humans were doing this by hand; unless quantum, there exists no accurate merge. That's not to say that CRDTs are useless, just not as grandiose as "automatic and accurate."

rdtsc 10y ago
It seems in this case it might be {"A" : [2, 3]} This kind of stuff is useful if users explicitly understand and design their application to expect this kind of stuff. It might not be possible always. But note, that there is still a good value in all the servers which got the same conflicts ending with the same result. As opposed to say server1: picking {"A" : 2} and server2 {"A" : 3}. Now something can be built on top of it given it understand and accounts for how merges happen.