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

11–20 of 60 posts

Re: A Conflict-Free Replicated JSON Datatype

#11

Post by ergl »

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…

About garbage collection, there is some research done in that direction: Logoot [0] is a collaborative text editor that doesn't depend on tombstones.

[0]: https://hal.archives-ouvertes.fr/inria-00336191/

Re: A Conflict-Free Replicated JSON Datatype

#12

Post by jpallen »

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…

>> In fact, we wrote the LATEX source text of this paper using an experimental collaborative text editor that is based on our implementation of this CRDT. We are making the character-by-character editing trace of this document available as supplemental data of this paper

If anyone else wants to feel at the cutting edge of science, you can write your LaTeX paper collaboratively at https://www.sharelatex.com :P

I can't pretend we've got any original algorithms (we lean on ShareJS a lot, which is operational transform based), but we've got a few years and billions of key strokes of experience in making it robust and practical.

Re: A Conflict-Free Replicated JSON Datatype

#13

Post by pjc50 »

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…

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.

Re: A Conflict-Free Replicated JSON Datatype

#14

Post by _urga »

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 resolve conflicts automatically and accurately. Your statement regarding impossibility would be true of operational transformation, but certainly not of CRDTs.

Re: A Conflict-Free Replicated JSON Datatype

#15

Post by amelius »

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…

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

Re: A Conflict-Free Replicated JSON Datatype

#16

Post by btrask »

I developed a "general purpose" JSON-based CRDT[1] as a part of my content addressing system project. The idea was to have an "append-only tree", where subtrees could be used by individual applications for different purposes, for example as counters or mutable sets.

In retrospect, it didn't need to support recursion. A single-level append-only set is enough to be fully general and easier to perform indexing on. Using JSON was also overkill, since too much flexibility is bad for content-addressing.

[1] https://github.com/btrask/stronglink/blob/master/client/READ...

Re: A Conflict-Free Replicated JSON Datatype

#17

Post by btrask »

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

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.

Re: A Conflict-Free Replicated JSON Datatype

#18

Post by jamesdsadler »

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

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.

Re: A Conflict-Free Replicated JSON Datatype

#19

Post by Kristine1975 »

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.

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

Re: A Conflict-Free Replicated JSON Datatype

#20

Post by amelius »

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

You already indicate that the LaTeX model is not a "clean" hierarchy. So I highly doubt they modeled it like that in JSON, but it could be possible.
Post reply on HN