A Conflict-Free Replicated JSON Datatype • Hacker News Board

Re: A Conflict-Free Replicated JSON Datatype

#21

Post by nkohari » Wed, Aug 17, 2016, 12:56 PM UTC

espadrine wrote: post #4

> Our principle of not losing input due to concurrent modifications appears reasonable, but as illustrated in Figure 4, it leads to merged document states that may be surprising to application programmers who are more familiar with sequential programs . That decision is a bit odd to me. Not only do they show that their merge system can produce data that the application considers invalid, it can even convert a string…

I've been doing some tinkering in this area lately, and I was also looking for an explanation of the string editing mechanics in this algorithm.

The hardest part there is retaining the intent of the simultaneous edits -- the I in the "PCI Consistency model" as described by the WOOT paper. Previous algorithms (LSEQ, WOOT, Doctree, Logoot, etc.) devoted to simultaneous conflict-free editing of text have solved this through relatively complex key generation strategies. I've only done a cursory read of this paper, but this algorithm doesn't seem to implement an alternative solution.

Re: A Conflict-Free Replicated JSON Datatype

#22

Post by nkohari » Wed, Aug 17, 2016, 1:02 PM UTC

jamesdsadler wrote: post #18

_urga wrote: post #14

Earlier quoted context omitted.

"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 resol…

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 t…

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.

Re: A Conflict-Free Replicated JSON Datatype

#23

Post by jamesdsadler » Wed, Aug 17, 2016, 1:29 PM UTC

nkohari wrote: post #22

jamesdsadler wrote: post #18

Earlier quoted context omitted.

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 t…

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.…

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.

Re: A Conflict-Free Replicated JSON Datatype

#24

Post by disordinary » Wed, Aug 17, 2016, 1:33 PM UTC

adrianratnapala wrote: post #9

vidarh wrote: post #5

Earlier quoted context omitted.

> That decision is a bit odd to me. Not only do they show that their merge system can produce data that the application considers invalid, it can even convert a string to a list without having any operation creating a list explicitly. It's hard to see good alternatives there. If you move from a single editor to concurrent edits without very strict ordering guarantees or a transactional system, you will need to deal w…

For this you would want a type / schema that explicitly represented the conflicts at the right level of granularity and helped applications resolve them. Whereas producing an object the pretends to be conflict free, but has some fields that might or might not change type is the worst of both worlds.

Exactly, if there are conflicts that have to be resolved then it's not conflict-free.

Re: A Conflict-Free Replicated JSON Datatype

#25

Post by disordinary » Wed, Aug 17, 2016, 1:37 PM UTC

jondubois wrote: post #8

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 wh…

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

Re: A Conflict-Free Replicated JSON Datatype

#26

Post by clemensnk » Wed, Aug 17, 2016, 1:50 PM UTC

ianstormtaylor wrote: post #7

Related: does anyone know any other good resources for architecting and building OT/CRDT for nested data structures like HTML or JSON? Ideally projects with working examples even?

We do OT on HTML (or rather the DOM) in the Webstrates (http://www.webstrates.net) project. We use ShareJS (now ShareDB) and represent and store the DOM as a JSON document.

Re: A Conflict-Free Replicated JSON Datatype

#27

Post by nkohari » Wed, Aug 17, 2016, 1:53 PM UTC

jamesdsadler wrote: post #23

nkohari wrote: post #22

Earlier quoted context omitted.

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.…

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.

Right, exactly. The key question is whether the algorithm's resolution heuristic takes into account the intent of the edit, and I'm not sure the algorithm in the article makes an effort to do that. (Not saying it doesn't, I just don't understand how it does, if it does.)

Re: A Conflict-Free Replicated JSON Datatype

#28

Post by _urga » Wed, Aug 17, 2016, 1:54 PM UTC

disordinary wrote: post #25

jondubois wrote: post #8

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 wh…

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

"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.

Re: A Conflict-Free Replicated JSON Datatype

#29

Post by _urga » Wed, Aug 17, 2016, 2:14 PM UTC

btrask wrote: post #17

_urga wrote: post #14

Earlier quoted context omitted.

"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 resol…

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.

"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?

Re: A Conflict-Free Replicated JSON Datatype

#30

Post by _urga » Wed, Aug 17, 2016, 2:24 PM UTC

jamesdsadler wrote: post #18

_urga wrote: post #14

Earlier quoted context omitted.

"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 resol…

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 t…

"To the extent that CRDTs are conflict-free"

There is no "extent" to which CRDTs are conflict free, CRDTs are by definition always 100% conflict free.

"No matter what the consensus system used be it CRDTs or OT"

CRDTs and OT are worlds apart. CRDTs are guaranteed to be conflict free, whereas OT is generally too complicated and unproven to offer that guarantee at all.

"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"

There are actually many more possible outcomes than those you listed, so that with CRDTs designed explicitly for collaborative string editing you can provide perfect intent-preserving merges to the user. There is an excellent paper on preserving intent, see "Replicated abstract data types: Building blocks for collaborative applications" (http://dl.acm.org/citation.cfm?id=1931272")