Hacker News Reader

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

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?

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.

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.

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.

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

It's main consideration appears to be to make changes in a way that makes sense for a tree consisting of maps and lists without ever losing user input. If you look at their diagram with examples you get the gist of their resulting heuristics, which basically boils down to "only delete if a user explicitly deleted, otherwise keep both values if users try to set the same value to two different things", "if two complex values (maps,list) have been updated, recursively merge them", pretty much.

It will cause stuff that users will perceive as conflicts, and that may even appear to be totally illogical (one of their examples leaves an object that appears to be in a broken state, because one side deleted it, and the other side updated a single attribute, leading the map to continue to exist, but with only the one updated attribute) so there's probably room for improvement, though the rules are simple enough that many of these could be resolved at application level by just carefully deciding what operation to provide.

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

> 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

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.

FWIW, Google Docs can be used offline (both in its Chrome-based and native-app-based incarnations).

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.

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.

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

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

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

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.

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.

If you have an API on a shared data structure, either you have distributed locking or you have conflicts. Distributed locking sucks, but CRDTs only prevent conflicts from messing up your data structure, not from existing.

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.

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

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.

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