See also automerge [1], discussed at the end. They are currently working on performance improvements [2]. Quoting from the repo, "automerge is a library of data structures for building collaborative applications in JavaScript:
* You can have a copy of the application state locally on several devices (which may belong to the same user, or to different users). Each user can independently update the application state on their local device, even while offline, and save the state to local disk.
* (Similar to git, which allows you to edit files and commit changes offline.)
* When a network connection is available, Automerge figures out which changes need to be synced from one device to another, and brings them into the same state. (Similar to git, which lets you push your own changes, and pull changes from other developers, when you are online.)
* If the state was changed concurrently on different devices, Automerge automatically merges the changes together cleanly, so that everybody ends up in the same state, and no changes are lost. (Different from git: no merge conflicts to resolve!)"
What does no merge conflicts to resolve even mean? Isn’t it fundamentally impossible to have both no merge conflicts and have meaningful data.
Incase of a conflict you can either keep the most recent change or both changes. But like got keeps both changes with <<<< HEAD and theirs markers the code is now invalid and won’t compile. Suppose both the changes were kept without conflict resolution, now you have two things that may interfere with each other.
I’ve had git mess up by trying to do an auto merge and still breaking the logic.
So I don’t think there is a golden algorithms. Just a bunch of trade offs like any other problem.
The talk makes it clear, "no conflict" in CRDT sense is that states update, even ordered differently will converge to the same state.
For practical sense, it is last-write-win baked in the the CRDT design (you can choose alternatives, but it has to be in the CRDT design, not something pluggable).
Yes, but the question is whether the semantics is meaningful for the application (e.g. text editing). I can also make string concatenation commutative by generalizing the concept of strings to multisets, but it is not given that this structure is useful for the applications where strings are needed.
> Yes, but the question is whether the semantics is meaningful for the application (e.g. text editing).
CRDTs are building blocks for larger systems. They themselves need to be composed into higher level constructs.
I think this is the crux of the CRDT, it assists the application designer in creating an algebra over the domain model such that state can get updated w/o having a single representation of that state space. It pushes that complexity back down, so that we can reason about it in serial code.
CRDT's and operational transforms are most useful for live, online editing. Each client sees a nearly up-to-date version of the document and any differences due to network lag are relatively small.
The idea is that normally each user will see other users' edits as they happen. They are trying to cooperate, not stomp on each other's edits. So long as the merge is reasonably intuitive, it can be fixed manually if it's not exactly what the authors wanted.
CRDT's aren't very good for writing code asynchronously, since you probably want each version to compile and pass tests, and sometimes do code review as well. Git works better for that. But they could be sort-of-okay for pair programming, though it might be an overly-complicated solution and better to use some kind of remote desktop.
I have done remote pair programming many times though and in that case it’s perfectly ok, because you’re communicating with the other person/people and can let each other know if you will break something.
For that use case, I can see this being very useful.
While you could do real-time collaboration on code edits with this tool (and I've done that with some success via pair coding, where you commit them to git after your shared edits are complete), this tool isn't strictly about code. It's about any shared content at all. Think google docs, but for any data, with offline/online sync. The offline/online sync might not be great for simultaneous edits, but in a shared "project" of say, field research data, the combination offline/online sync and soft-realtime shared documents at any hierarchy level layer is a nice "don't need to think about it generally" approach.
I'm not sure which kind of CRDT these are, but since all edits are part of history, as in git, you're not going to lose history if someone DOES inadvertently stomp on someone else's edits.
If so, what’s different? Better algorithms, assuming fewer collaborators and/or less frequent updates? Or is my understanding that these are similar in functionality incorrect?
Google Wave’s algorithm is now used by Google Docs, it’s Operational Transformation (OT) [1]. You can approximately view it as a special form of CRDT but the theory underpinning each have separate origins.
OT is efficient and fast at real-time editing with a central server, whereas CRDTs are more capable in distributed/p2p scenarios but bring significant overhead as they store a lot of metadata.
My understanding is that most specifications for OT have obscure failure cases if a central server is not used. Some papers have fixed these issues to enable fully P2P OT, but IIRC the resulting ops require similar amounts of metadata per-change as sequence CRDTs.
Interesting. I thought that OT implementations require peers to have at least one authoritative view of the transformations somewhere, and then distribute different operation sequences (after transformed) to different node. That, in simplest way, would imply a central server (otherwise you will have an alternative method to communicate the authoritative view between peers, which sort of defeat the purpose).
Yes. There do exist peer-to-peer OT algorithms, however they have not become popular in any production websites.
The popular production systems (such as Google Wave and Docs) are based on the Jupiter style of operational transform, which features a single central server, with a single line of time. The clients try to send their edits to the server as the most-recent edit. If they fail, for instance because another client has made an edit, then they rebase their edit on the new most-recent version, and then try to submit it again.
Keep in mind that OT and CRDT aren't actually algorithms -- they are perspectives from which a programmer might try to think of an algorithm.
The Operational Transform perspective says "think about how you can transform your edits (aka operations) so that they work when applied in a different order, on a peer with a different history of time.
The CRDT perspective says "think about how you can formulate your data structures so that you can apply any edit in any order."
In practice, programmers who took OT perspective were able to create mostly-working systems pretty easily. But getting full consistency (aka correctness) was very difficult, because it was difficult to think of all the ways in which multiple operations could interleave and affect one another, especially without the constraint of a central. Thus, it took many, many academic papers before anyone succeeded in coming up with a fully P2P algorithm that resulted in consistent synchronization after arbitrary edits.
This frustrated many of the academics enough for them to change their perspective. The first step towards this was a system called WOOT, which stands for "With-Out Operational Transform", where the researchers explicitly gave up on their old perspective, and started thinking along the CRDT paradigm.
The CRDT paradigm made it easy to get fully-consistent peer-to-peer systems. However, it has remained elusive to make one that's performant enough to be used in practice. They tend to require holding onto the entire history of all operations that have ever occurred, and each operation itself tends to require 10x or 100x overhead. Thus, you can edit a small text document and quickly end up with megabytes of data for a small string of text.
But there's a third paradigm here that isn't discussed as much -- Version Control. Think about git. It provides a DAG of versions over time, that branch and fork, and a way to consistently merge any two versions. From this perspective, it turns out that OT is the discovery of the rebase operation, and CRDT is the discovery of multi-way merge in a DVCS. OT people have been trying to simplify complicated merges by doing clever rebasing. This is much easier with a central server, and it happens to allow you to clean up old history more easily, which saves a lot of memory, making it useful in production systems.
In practice, I think that these three perspectives are all going in the same direction. If you build an OT system, and then try to make it fully consistent and peer-to-peer, you end up with CRDT algorithms. If you build a CRDT, and want more flexibility in memory requirements, a great approach is to throw a server into the mix and rebase (aka transform some operations). And git already has "operational transform" and "CRDT" algorithms in it.
My personal interest is in unifying these algorithms in the https://braid.news project. We have a unified protocol that allows OT and CRDT systems to communicate with one another, and we've got some great new algorithms for pruning old history in a fully-p2p network that I expect to release this summer.
So this is either represented as a delete followed by an insert (delete one character at offset N, insert "m" at offset N), or as a replace (atomically replace character at offset N with "m").
For an atomic replace operation, CRDT algorithms will solve this by having the last write win. What CRDTs give you here is a guarantee that the order is the same for every participant. So if you're building a collaborative text editor, for example, either everyone will either see "moo" or everyone will see "boo".
For a delete + insert, it might not be atomic, in which case only the delete will "conflict". Since you both deleted at the same time, it's not actually a conflict (you both did the same thing), and the result will be either "mboo" or "bmoo". But again, it will the same for everyone.
Interesting. What about the seqeunce "Alice deletes f, Bob replaces f with b, Alice inserts m"? I guess it doesn't matter, as long as all implementations do the same thing.
git could easily take an approach like this too, but there are obvious reasons why it doesn't. It feels like the people designing this algorithm believe the text being worked on is less important than source code.
I don't see how it's possible. I get Alice's changes, I spend 3 hours working on them, I get Bob's changes. The algorithm might be able to resolve these three sets of changes consistently according to its rules, but I've got no faith that the meaning of the text would survive the process.
CRDTs work best for high-contention situations such as online text editing (think Google Docs) where the conflict resolution can be seen right away and addressed by the user.
For offline sync, where someone edits a text document for an hour and then syncs, you're right: You can end up with something unintended, since each participant is editing based on ("branching off") a snapshot. For example, if I deleted a whole paragraph, and you edited it, what should the end result be? But at least the end result will be consistent in the sense that all participants end up seeing the same thing, though semantically it may be wrong.
Note that CRDTs go beyond just text. CRDTs can be used to represent arbitrary data structures and operations on them: Array s (insert, delete, append, etc.), numbers(increment, decrement, etc.), dictionaries (insert, delete), etc. A great implementation of this is Automerge [1].
That makes sense, and is reasonable. Thank you for taking the time to explain. I am now wondering about the space where CRDTs and databases overlap.
(Very unformed thoughts follow) We're used to databases storing the system's current state. If we're lucky, we're writing changes to the database, rather than just the current state, so we can reconstruct the system's state at any point in the past. What would a database that not only stores changes but also resolves conflicts look like, I wonder. A database where CRDT was a column type, I guess.
Further thought: A list of deltas in a database is reversable - you can wind back to see what the database state was 3 weeks ago. Can you reverse a CRDT?
I'm not sure why I keep coming back to this. Maybe because it's a new structure I've never thought about before. Maybe I'll have to implement one, just to get a feel for them.
> either everyone will either see "moo" or everyone will see "boo"
That seems in conflict with the claim elsewhere in this discussion that this works offline, too (https://news.ycombinator.com/item?id=23802495)
I guess everyone will eventually either see “moo” or “boo”?
So, literally a change nobody wanted? Seems like it would not work in any real sense. I change it to moo and as a line checking something on it. You change it to boo and add a line, as well. Congrats, now neither of our additional lines makes sense...
This really feels like a solution in search of problems.
> Congrats, now neither of our additional lines makes sense...
What would you expect to happen? That one persons input is ignored? That’s hardly expected for that person. If anything, it’s much more confusing. This way, both people see both Ed it a and can react appropriately. If they both remove the same thing, then no problem, if they keep stomping on each other’s work, then they need to communicate anyway.
The important thing isn’t that you ended up with something neither of you wanted but that it’s consistent for all people. You see the exact same thing they see.
> This really feels like a solution in search of problems.
Hardly. As someone who once wrote a collaborative editor as a you project long ago, this seems really useful to me. I’ve also worked on mobile sync (multiple devices that could be edited offline syncing with the online version) and again this would have been really beneficial as the solution being used wasn’t great at all.
Don't ignore, but just like I expect my car to not start of I don't have my foot where it is supposed to be, I'd expect there editor to indicate to me that my edit could not go through.
And I think I wasn't clear. Collaborative editors at the character level feel like the solution that is a misfire. Doing the same things at a higher level of abstraction works. Merge in document changes in remote sections. Code merges with git work reasonably. None are bullet proof, and I expect conflicts at a level lower than paragraph to almost always need an audit. Certainly lower than the line level.
This is how google docs works and this problem doesn’t come up much in practice. The reason is that usually when you’re collaboratively editing a document you do so in real-time. If we both see one another’s cursor on the same content, we pay extra attention and make sure our edits make sense.
For offline edits (eg multiple developers working on independent features in a codebase), generating merge conflicts is probably more appropriate. OT and CRDTs can be written that generate merge conflicts in cases like this - it’s an implementation detail. It’s just that most algorithms are written first and foremost with real-time collaborative editing in mind. And again, in the real-time collaborative editing case, merge conflicts aren’t what users want.
I recently did realtime collaborative editing of the same file with a Visual Studio Code plugin and have also often used Google Docs and its really not an issue in practice. If it were to suddenly stop me to notify me that there was a conflict, that would be a very jarring and unpleasant workflow.
As josephg says, you don’t want merge conflicts in realtime editing and for offline editing, a git merge conflict resolution style is probably more appropriate.
It’s an extremely valuable solution to a very real problem. Surely you must have tried Google Docs? The “mboo” is an indication that the two editors have different ideas about where they’re going. In a typical setup both editors will see that someone else has their cursor in the same place in the document, and they will very quickly see that a conflict has happened. Now they can coordinate on how to resolve it. It’s not a problem, but a desirable step in the process of two people working together on something that isn’t finished.
I've seen all to often where people don't see the conflict because it allowed them to continue.
Such that editing a Google doc is easily up there with many other experiences I don't like. Taking the act of editing, that used to just be single user and forcing it into distributed tricks from the get go.
Yes, collaboration is distributed. And sometimes it is nice to both be working at the same place/time. Usually, though, a batch process is easier to reason about and execute.
A text editor could easily highlight passages where concurrent changes were made. (Perhaps only if a heuristic indicates that the merged change doesn’t make any sense.) The metadata is all there.
That's the best failure mode you can expect for the average user without diving into the usability pit that is git - both changes are kept and it's obvious to users that there is a merge conflict. Otherwise, one update would just eat the other silently, leaving one side confused and the other oblivious.
Things are always sequenced. One will win, and the other will have to redo their change on top. Partially applying the change at the word level just seems way too fraught with false edits. It is already a source of a lot of bugs at the file and project level.
But one person edited the word foo. The other edited a weird that no longer exists. I get why this feels like a clever combination of the edits. But I'm struggling to see how doing this at the character level makes any sense.
Consider instead that you could do this at the byte level, with equally off results.
At higher levels, this trick sounds useful. But you pick your abstraction height where all conflicts should just go back to the user.
So, people edit the same document, but at different paragraphs? Fine. They edit the same paragraph? Almost certainly a problem. No different than code.
Different strategies have different tradeoffs and work better for different use cases. If you have multiple people interactively editing the same document (i.e. syncs are happening regularly), it can feel more natural to err on the side of applying each user's edits and letting the humans work it out, rather than flagging a conflict that must be resolved before proceeding. When using Google Docs I've had the occasional awkward "after you, no after YOU" moment while trying to edit the same text, but it's pretty rare. You obviously wouldn't want to use this same approach for asynchronous/offline collaboration, where more explicit conflict resolution like a VCS offers is necessary.
The place where this kind of character-level approach actually does start to fall apart is when users can make larger structural changes to the document with single actions -- reordering lists, cutting and pasting chunks of text, etc. There are other options for that.
* You can have a copy of the application state locally on several devices (which may belong to the same user, or to different users). Each user can independently update the application state on their local device, even while offline, and save the state to local disk.
* (Similar to git, which allows you to edit files and commit changes offline.)
* When a network connection is available, Automerge figures out which changes need to be synced from one device to another, and brings them into the same state. (Similar to git, which lets you push your own changes, and pull changes from other developers, when you are online.)
* If the state was changed concurrently on different devices, Automerge automatically merges the changes together cleanly, so that everybody ends up in the same state, and no changes are lost. (Different from git: no merge conflicts to resolve!)"
[1] https://github.com/automerge/automerge [2] https://github.com/automerge/automerge/pull/253