Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A Conflict-Free Replicated JSON Datatype

arxiv.org

Post reply on HN
Print view View original

31–40 of 60 posts

Re: A Conflict-Free Replicated JSON Datatype

#31

Post by Jweb_Guru »

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.

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. And there are ways to get consistent reads out of CRDTs, too: 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.

Re: A Conflict-Free Replicated JSON Datatype

#32

Post by josephg »

_urga wrote: post #30
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…

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

> whereas OT is generally too complicated and unproven to offer that guarantee at all.

Citation needed.

I've built several production-level OT-based systems on top of ShareJS's JSON OT[1] code. The set of operations supported is guaranteed to be conflict-free and correct. We don't have AGDA proofs but we've used fuzzers to ferret out correctness bugs and its been about 2 years since a bug was found in the transform code. All in all, I'm very happy with the implementation.

Meanwhile, I don't believe a more generic JSON OT / CRDT system can be made conflict-free. (Well it can be conflict-free, but you'll lose data if it is). If you support arbitrary tree-level moves, you have the User A moves x into y's children, user B moves y into x's children problem. There are simply no good ways to resolve these operations without user intervention, or a lot more knowledge of the data structures at play.

[1] https://github.com/ottypes/json0

Re: A Conflict-Free Replicated JSON Datatype

#33

Post by tveita »

amelius wrote: post #6
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…

> String editing is brushed over in the paper. LaTeX source code is basically just a string. It would have been more interesting to see this applied to a hierarchical data-structure, such as HTML, where e.g. elements are nested inside markup nodes.

Reminds me of the operational transformation used in Wave.

http://www.codecommit.com/blog/java/understanding-and-applyi...

I see they mention it in the paper, saying the difference is that Wave requires a central server to impose a total ordering of operations.

Re: A Conflict-Free Replicated JSON Datatype

#34

Post by skybrian »

_urga wrote: post #28
disordinary wrote: post #25

Earlier quoted context omitted.

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

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

Re: A Conflict-Free Replicated JSON Datatype

#35

Post by zamalek »

_urga wrote: post #14
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…

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

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

Re: A Conflict-Free Replicated JSON Datatype

#36

Post by vidarh »

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.

They are presenting an algorithm, not a product, so any implementation would be free to make it available in a different way.

They specifically do address this point about how developers would deal with it in the conclusion of the paper.

Re: A Conflict-Free Replicated JSON Datatype

#37

Post by vidarh »

_urga wrote: post #30
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…

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

> so that with CRDTs designed explicitly for collaborative string editing you can provide perfect intent-preserving merges to the user.

I don't for a second believe this is event theoretically possible, given that if two people write collaboratively, it is not uncommon for the intent to change "mid stream" as a result of seeing the other person edit.

Add in some lag, and watch confusion ensue.

Re: A Conflict-Free Replicated JSON Datatype

#38

Post by nateps »

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?

Author of ShareDB (https://github.com/share/sharedb) here. ShareDB is a stable production JSON OT system that powers the entire backend for Lever (https://www.lever.co/). All of Lever's apps, backend services, migration scripts, etc. go through ShareDB. It scales horizontally; over 1000 companies use Lever, including companies with 1000s of employees, like Netflix and Yelp.

There are some simple examples in the repo to get you started. Please let us know if you have any questions getting going!

Re: A Conflict-Free Replicated JSON Datatype

#39

Post by nateps »

Kristine1975 wrote: post #19
amelius wrote: post #6

Earlier quoted context omitted.

> String editing is brushed over in the paper. LaTeX source code is basically just a string. It would have been more interesting to see this applied to a hierarchical data-structure, such as HTML, where e.g. elements are nested inside markup nodes.

LaTeX is also hierarchical, though. Some is explicit (environments) and some is implicit (\chapter, \section etc).

This is true. To preserve document validity and user intent, an algorithm designed for collaborative string editing will not always work correctly when applied to a markup document such as LaTeX, HTML, or Markdown directly.

It is similar to how you need a JSON type to represent the kinds of edits you can do to a JSON document rather than editing JSON text as a string. The kinds of edits done in text better map to editing a markup language like LaTeX or Markdown than JSON, so you are less likely to notice these issues right away. But if the type is designed specifically for the markup language, user intent will be better maintained through concurrent edits and the document will never end up in an invalid format.

Re: A Conflict-Free Replicated JSON Datatype

#40

Post by _urga »

josephg wrote: post #32
_urga wrote: post #30

Earlier quoted context omitted.

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

> whereas OT is generally too complicated and unproven to offer that guarantee at all. Citation needed. I've built several production-level OT-based systems on top of ShareJS's JSON OT[1] code. The set of operations supported is guaranteed to be conflict-free and correct. We don't have AGDA proofs but we've used fuzzers to ferret out correctness bugs and its been about 2 years since a bug was found in the transform c…

See: https://en.wikipedia.org/wiki/Operational_transformation#Cri...

"Due to the need to consider complicated case coverage, formal proofs are very complicated and error-prone, even for OT algorithms that only treat two characterwise primitives (insert and delete)" - Du Li & Rui Li - "An Admissibility-Based Operational Transformation Framework for Collaborative Editing Systems"

There's also an interesting comment there from the author of ShareJS, I think that might be you?

The other critical difference between CRDTs and OT is that CRDTs work offline, in a distributed setting, whereas OT cannot. OT requires a central online server to coordinate, which as far as I understand is the cause of the classic UI freeze in Google Docs whenever the network goes.

Post reply on HN