CRDTs: The Hard Parts [video]
martin.kleppmann.com
martin.kleppmann.com
* 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
[3] https://automerge.github.io/pushpin/ [4] https://www.inkandswitch.com/capstone-manuscript.html
This really feels like a solution in search of problems.
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.
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.
But, the point is that you get a marked conflict. And take it back to the users.
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.
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.
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.
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.
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.
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.
I guess everyone will eventually either see “moo” or “boo”?
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.
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].
(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.
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.
For that use case, I can see this being very useful.
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.
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.
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?
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.
1) https://en.m.wikipedia.org/wiki/Operational_transformation
My OT knowledge isn't deep; perhaps in practice, some implementations like Google docs use an authoritative node?
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.
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.
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).
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.
Columnar formats have their upsides and downsides, though.
[1]: http://archagon.net/blog/2018/03/24/data-laced-with-history/
[2]: http://replicated.cc
Oo, it sounds like you have some interesting thoughts. Could you elaborate?
Seems like it could get unwieldy very fast. Especially, in the face of a bad actor spamming a document with updates.
I've considered using CRDTs in a few projects now, but the requirement to keep a running log of updates forever has ruled them out. I've ended up using other less sound (more prone to failure), but more practical methods of doing sync.
Perhaps, I'm missing something. Wouldn't be the first time.
Are there alternatives without this requirement, or that would at least allow a cap on the update log?
Could you share the alternative methods that you’ve used?
Plenty of room for problems to arise, but it did not require keeping a log of updates. My use cases did not require real-time collaboration and the structure of the document was known beforehand, though.
If you have code available in the public domain, I’d love to see it.
The linked video makes a clear distinction that OT and CRDT are different, as OT has the idea of a centralised coordinator to ensure consistency by mutating the proposed, conflicting operations whereas CRDT uses commutativity to attempt to make conflicting operations an inaccessible state
It's true that the most popular OT systems have a central server -- but there exist OT algorithms without a central server.
It's also true that CRDT algorithms tend to require too much memory usage to be practical -- but there exist CRDT algorithms with bounded memory.
There are even algorithms that can be equally called OT and CRDT.
Historically, what happened was that the OT research community couldn't solve consistency without adding tombstones into their data structures that recorded deletions (and generally kept these deletion marks around forever). They called these "tombstones." People didn't like that you had to keep them around forever, but they seemed to solve the problem.
Over time, some researchers decided to just keep more things around forever, and promoted the idea that you don't need to do as much transforming of operations if you just preserved all operations in a spatial data structure, not just the tombstones, but everything. They came up with a new name this style: CRDT.
But in fact, the technical definition of a CRDT actually fits OT algorithms quite well. A CRDT just means that you can accept any operation at any time. That's what a good OT system also needs to do. So there isn't a technical distinction between an OT or a CRDT. They each define a set of features, and your synchronizer can possess OT features, and it can possess CRDT features.
It's possible to construct a pathological case where it's impossible to soundly GC the CRDT state, and where you have to keep around an arbitrarily long list of per-agent updates or list of agents forever, but that shouldn't be the normative case.
For example, the automerge library linked elsewhere on this thread requires it.
My understanding (flawed) is that you need to keep all the changes on the server because you never know how long it's been since a client has pulled/pushed changes to a document.
I guess arbitrary limits based on number of updates or time can be imposed, but I haven't seen libraries that do that.
Thanks.
That may be easy coordinating servers that are almost always online, but it's definitely not easy for desktop/mobile clients that go offline for long periods (and sometimes don't come back).
I do that with my OT collaborative editor.
Here's a very simple example: If there are only 5 users concurrently editing a document and each user has seen operations o1...oN, then you can safely compress the data for o1...oN.
Depending on the CRDT type you may not need to store any log at all. For an add-only set, for example, you only need to store the elements.
I think what's harder to solve is the metadata overhead problem. Most CRDT based text editors have a huge per-character overhead. As Martin mentioned, Automerge used to have a overhead of ~200bytes per character, but using a new binary encoding format they were able to reduce the overhead down to 1.5-7 bytes per character. (https://speakerdeck.com/ept/crdts-the-hard-parts?slide=67).
It seems the hard part about CRDT is choosing the correct commutative function, as merging two operations in line with user intent is non-trivial. Would it be possible to use a combination of superposition (Please correct me if this word is wrong) and pruning to derive user intent?
The idea being that instead of combine being (A, A): A (A commutative semigroup), couldn’t we represent the operation as (A, A): Set[A] and have a way of showing the user set results in a way that their next operation shows us the “correct” interpretation.
He’s doing this implicitly with the file tree example, wherein operations that don’t create trees usually defy user expectations (Symlinks aside), so he decides to prune those choices from the result Set[A] before introducing a heuristic to further prune the set. There’s still an issue of users having opposite intent, but at that point it just seems like we need to introduce “Set pruning” or “Superposition collapse” operations as a user-level primitive and then rely on recursion to resolve the possible nesting of these result sets.
Does this riff with anyone / does anyone have further thoughts on this formulation?
[1] Section 3.2ish of https://hal.inria.fr/inria-00555588/document
The core part is separating the "merge" from the "resolve" state. Merging state can be done in a variety of ways, so in the default formulation there seems to be a focus on making the "merge" operation also "resolve" to only one value, when really there could be multiple formally valid merges that the client may desire (Which is part of the difficulty that the video notes as he proposes a variety of possible file system mutations for a set of two uncoordinated operations).
The cleanest clarification of my thought process is similar to the following:
Given the operation Merge(4, 2), I could propose that there are two valid ways to perform this merge, addition and multiplication. This means the result would be either 6 or 8. The act of returning a single value (6 or 8) changes that proposal into a statement, though, which is the "resolve".
One subversion of this restriction is to return a set of all possible results for the operations we think are valid, so {6, 8}. At this point, the user can say (Either explicitly or implicitly) "I actually want 6" and we resolve it to the single value of {6}. There are also special cases like Merge(2, 2), where this whole situation is especially ergonomic because the merge operations are equivalent.
There are problems, of course, with this approach.
One issue is the need to categorize all possible operations the user may think are valid for Merge(4,2). If the user intended to do division, the result set proposed above will not include the state that they would expect. Still, this seems more general now, as we just need to gather the set of operations that the user may think are valid instead of assuming which one is valid. There's also a ranking problem that then exists at the UX level, as we need to find a way to cleanly propose this set of alternatives.
Another issue is, of course, exists if both users propose conflicting resolutions (Actor1 says "I want multiplication" and Actor2 says "I want addition"). This is the issue with decoupling the "merge" and "resolve" steps, as now we may cause a fork in the model which causes a fundamental divergence of the collaborator's data.
Failing that, you've just kicked the can down the road. Consider two users A and B who make conflicting edits, and so wind up being presented with one of these choices. If they choose different options, and then make further edits, what do they see of each others' subsequent edits, and how do you explain the whole branched history to user C, who was out to lunch while this happened?
Properly consistent can still mean utterly confusing.
For example, in this talk he discusses the problems with moving items in a list as a pair of delete+insert operations. Then proposes adding a move operation to the CRDT that solves some of these problems.
I do wonder if in practice OT isn't a simpler solution for most applications. He mentions the differences in the beginning of the presentation and the main advantage of CRDTs is that they don't need a central server. It seems to me that for e.g. a web app you have a central server anyway so all the extra complexity of CRDTs isn't needed. I know almost nothing about this though, so would love for someone more knowledgeable to explain why I might be wrong.
For multi server/database web-apps, CRDTs might be useful because they reduce the centralization required for collaboration, and increase the fault tolerance. In a load balanced web app, different clients could connect to different servers/databases and stil achieve eventual consistency when those back-end systems sync up. If any of those systems go down, in theory traffic could be routed to other systems seamlessly.
[1] https://twitter.com/ollermi/status/1279067350269124609?s=21
As a side question, have any new algorithms been developed over the last decade that have significantly improved automatic source branch merging?
> In that paper, and in Pijul, the definition of a file is slightly expanded, to included these cases, and “artificially add” all pushouts of all possible patches to the space of files.
> The resulting structure is a graph of byte chunks (which can be for instance binary blocks, lines, or smaller parts, such as indentation).
> The relation between them, described by the graph edges, is the order in which they appear in the files. This graph acts as a “cache” of applied patches.
From: https://pijul.com/model/#pushouts-and-distributed-algorithms
The paper is they mention is the same one in GP's linked article.
A Categorical Theory of Patches - https://arxiv.org/abs/1311.3903
(I am joking of course)
Rough notes are here:
https://docs.google.com/document/d/1p1K3sxgKGYMEBH72r-lnP9Gn...
[0]: https://github.com/anchpop/crdts [1]: https://github.com/yjs/yjs
Darn, and just after I'd implemented it myself in terrible beginner Rust! I might get started reimplementing it using your tool :)
One idea comes to my mind (a bit out of topic): as we can store the complete editing history in a document (even including mouse movements) with a fairly small overhead using the ideas of automerge, would this be useful for distinguishing texts that are generated by machines and by humans? Or to detect plagiarism?
The solution then becomes really simple: You insert your cursor where you want to edit. You wait for the text and/or background of that paragraph to change color. Light green would do nicely.
Other users will see that paragraph turn red.
The paragraph is now under your control. If someone else desires to edit a sentence in YOUR paragraph that sentence changes color again and the side bar displays a dialog allowing you (the owner) to 1) hand over the paragraph to the new author, 2) hand over only that sentence or 3) ignore the request.
Dumb software wins!
You simply do not assign 2 people to a task that can only be done by a single person.
It is like a system where 2 people can poor coffee into the same cup at the same time. We deal with the cup overflowing with some drainage (marvel at our creation of course!) but then 12 people put sugar in the cup. Solution: we overflow the cup further to dilute it! We solve the mobility issue by spilling a bit more coffee out of the cup and whip the bottom with just the right type of towel or napkin. The only problem that remains is both drinking from it at the same time.
You can also write comments above or under the section if it absolutely needs to be corrected immediately.
I wonder if there’s some free YouTube transcription service... even just showing the captions would work.
Oh, hm. It’s not on YouTube anyway.
I found that the last 4-5 references listed in the link are pretty accessible, and most of the diagrams from the talk are taken from one of the papers by Kleppmann.
The section on moving items in a list makes my mind jump to Causal Trees (≈RGA). The problem here is that a) we need the concept of a list bucket or slot, and b) we also need to preserve the sequential integrity of runs of items as in text editing. In CT/RGA, each letter/item is simultaneously a list bucket and its contents. I wonder if this problem could be solved by adding a "reanchor" op that moves the "contents" (and some/all children) of a letter op to the "bucket" of another letter op?
Each reanchor op would have the job of "moving" a subtree of text to a new parent bucket. (Under the hood, the subtree would obviously remain topologically unchanged for convergence purposes, but the reanchor op would inform how the tree is parsed and turned into a user-visible list or string.) First, the reanchor op would need to reference the start and end letter/item ops in a given subtree; and second, the reanchor op would need to reference the letter/item op into whose bucket the subtree contents will be moved. If the set of subtrees for a range of text/items contains multiple independent subtrees, they would each need their own reanchor op. Concurrent moves of the same subtree would be resolved as LWW, similar to the Kleppmann proposal.
Let's say you have a graph for string "ABCD" that looks roughly like this, sans metadata:
+---+
| A |
++-++
| |
v--+ +--v
+---+ +---+
| B | | C |
+---+ +-+-+
|
v
+-+-+
| D |
+---+
+---+
| A +<---------+
++-++ |
| | |
v--+ +--v |
+---+ +---+ |
| B | | C +<---+ |
+---+ +-+-+ | |
| | |
v | |
+-+-+ ++-++
| D +<--+ m |
+---+ +---+
We can get cycles with this scheme, but as far as strings or lists are concerned, this doesn't actually matter, since the parent references aren't reflected in the output (as they would be with an explicit tree data structure). If, concurrently to this, another device wanted to move "A" after "C", the merged graph would look like this:
+---+ +---+
| m +-->+ A +<---------+
+-+-+ ++-++ |
| | | |
| v--+ +--v |
| +---+ +---+ |
| | B | | C +<---+ |
| +---+ +-+-+ | |
+---------^ | | |
v | |
+-+-+ ++-++
| D +<--+ m |
+---+ +---+
This is just a sketch, not sure if it would actually work in practice. Pain points are a) moving multiple subtrees in a somewhat atomic way (when the range to be moved covers more than a single run of items), b) sane results when overlapping ranges are moved concurrently, c) moving items to a bucket whose contents had already been moved before, and d) parsing performance, especially given the fact that we'll now have ops (and their children) whose contents might end up in arbitrary places in the output string or list. Might just end up with a slow, confusing, and labyrinthine data structure.
There's also the question of intent: does the user want to move a range of items to the slot currently occupied by a different item, or do they want to move that range to the right of that item? Lists of notes will want the former, while strings will usually want the latter. Perhaps the reanchor op could explicitly differentiate between these two cases.
Another fun case is two concurrent range moves in which the destination of the first move falls within the second move's source range, and the destination of the second move falls within the first move's source range. How do you handle this?
I expect that any algorithm solving this problem will need a formal proof of correctness, because it's very easy to miss edge cases when using informal reasoning.
can you elaborate why? are these sentences fundamentally wrong? they dont appear so.
+1 from me on Martin's book, btw. One of the best technical books I've ever read.
And it turns out that most services that I find myself working on these days are distributed systems, so having a healthy respect for all the ways things can break is a useful place to be.