A Conflict-Free Replicated JSON Datatype • Hacker News Board

Re: A Conflict-Free Replicated JSON Datatype

#51

Post by nornagon » Wed, Aug 17, 2016, 6:59 PM UTC

_urga wrote: post #40

josephg wrote: post #32

Earlier quoted context omitted.

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

Designer & author of the JSON OT algorithm that underlies ShareJS/ShareDB here. I do not have a formal proof for any of the properties of the algorithm, but we have extensively fuzzed it and are confident in its correctness. I believe a proof of correctness is possible, merely tedious.

Re: A Conflict-Free Replicated JSON Datatype

#52

Post by arj » Wed, Aug 17, 2016, 7:11 PM UTC

nateps wrote: post #45

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…

We've been developing ShareDB ( https://github.com/share/sharedb ), a JSON OT system, and using it in production at Lever for 3 years now. CRDT has some strong advantages in decentralized applications with a need to avoid a central server. But in practice, web apps today do generally have a central server. I think the core advantages of OT over CRDTs are actually these practical concerns: being able to design transfo…

That last part is a good summary of CRDT versus OT.

Also nice project. I think a section on conflict handling would be a good addition to your README on github. It is the first thing I look for when looking at systems in this space :)

Re: A Conflict-Free Replicated JSON Datatype

#53

Post by cwmma » Wed, Aug 17, 2016, 7:18 PM UTC

so from reading the comments, am I correct that with an object like this

{"key":1}

if one user changes it to be

{"key":2}

while the other at the same time changes it to be

{"key":3}

and another user changes it to

{"key":[2, 3]}

it's impossible to tell if there was a conflict between the first 2 users or the third user just made an update

Re: A Conflict-Free Replicated JSON Datatype

#54

Post by marknadal » Wed, Aug 17, 2016, 7:53 PM UTC

I am the author of a CRDT database that can store JSON.

Here are Kyle Kingsbury's (Aphyr) thoughts on it: https://twitter.com/aphyr/status/646302398575587332 .

In response to the OT comments here in the thread, people should be aware that OT is not P2P or decentralized. The algorithm in the paper is, however, and so is GUN (https://github.com/amark/gun) .

Probably more important to the discussion, is that it IS possible to implement collaborative rich text editing on top of P2P CRDT systems. Although I do not know of any yet, I am working towards one which uses a linked-list DAG, early demo: https://www.youtube.com/watch?v=rci89p0o2wQ .

Re: A Conflict-Free Replicated JSON Datatype

#55

Post by rdtsc » Wed, Aug 17, 2016, 8:28 PM UTC

zamalek wrote: post #35

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

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

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.

Re: A Conflict-Free Replicated JSON Datatype

#56

Post by jamesdsadler » Wed, Aug 17, 2016, 11:05 PM UTC

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

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

CRDTs are always conflict-free. I am not disagreeing with that. I was trying to draw attention to the fact that just because the CRDT always commutes does not mean that a user does not perceive there to have been a conflict - out of a multiple contradictory edits the commute operation will ensure only one succeeds. So yes, the CRDT itself is conflict free, but it wasn't my point.

They aren't magic. The deal with tie breakers when they have to. I've seen posts where suggestions of building a CRDT-based source control system are being bandied around with claims that there will be no conflicts - sure, there won't be. Will the code make sense or even compile - probably not.

A conflict to a CRDT is one thing and a conflict to a user is something else entirely.

Re: A Conflict-Free Replicated JSON Datatype

#57

Post by _urga » Thu, Aug 18, 2016, 7:44 AM UTC

skybrian wrote: post #34

_urga wrote: post #28

Earlier quoted context omitted.

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

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.

Re: A Conflict-Free Replicated JSON Datatype

#58

Post by josephg » Thu, Aug 18, 2016, 12:35 PM UTC

_urga wrote: post #40

josephg wrote: post #32

Earlier quoted context omitted.

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

Yes thats me! For what its worth, I no longer believe that wave would take 2 years to implement now - mostly because of advances in web frameworks and web browsers. When wave was written we didn't have websockets, IE9 was quite a new browser. We've come a really long way in the last few years.

Working offline and working in a distributed setting are two different properties.

OT can work very well offline - the client and server just buffer ops and you do reconciliation. Some OT algorithms experience O(n*m) performance when the client comes back online (n client ops, m server ops), though the constant is quite low, you can make the client do the work. But you can do better - a better designed text reconciliation system can do O(nlog(n) + mlog(m)) if I remember correctly - which is quite usable in real systems and very competitive with CRDTs.)

P2P is much harder. I've got a sketch for a system that would use OT in a P2P setting, but in many ways its a poor man's CRDT. That said, the downside of CRDTs is that they grow unbounded as you make more modifications. Which would work great for documents that are written then discarded (like a HN thread). But it would work much less well for long lived, frequently written documents (like a server status dashboard). You can fix that using fancy coordination algorithms, but if you're going down that path you're back to sketching out an overcomplicated OT system.

There's lots of fun space to explore there - but not enough actual useful systems being made for production use.

Re: A Conflict-Free Replicated JSON Datatype

#59

Post by nicolagreco » Sun, Aug 21, 2016, 9:50 AM UTC

vidarh wrote: post #43

nkohari wrote: post #21

Earlier quoted context omitted.

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

It's not trying to do string editing at all. It's operating on JSON de-serialized to maps and lists. String editing isn't a valid operation on the data model they specify. You can replace a string value with another. Section 3.3 outlines the allowed operations, which basically allows you to obtain an iterator, move it, insert, delete and retrieve keys and values. You could certainly model string editing in it, by put…

wouldn't a string just be a list of chars?

Re: A Conflict-Free Replicated JSON Datatype

#60

Post by tracnar » Mon, Aug 22, 2016, 1:27 PM UTC

nateps wrote: post #45

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…

We've been developing ShareDB ( https://github.com/share/sharedb ), a JSON OT system, and using it in production at Lever for 3 years now. CRDT has some strong advantages in decentralized applications with a need to avoid a central server. But in practice, web apps today do generally have a central server. I think the core advantages of OT over CRDTs are actually these practical concerns: being able to design transfo…

Have you read the SwiftCloud paper? https://pages.lip6.fr/Marek.Zawirski/papers/SwiftCloud-RR-83...

It's about using a centralized cloud infrastructure in conjunction with CRDTs. This allows to fix some of the issues you mention (pruning of operation history, stricter versioning, no need to push operations, ...).

Of course it complicates the implementation but it's quite interesting.