CRDTs are pretty rad, I’m really excited to see what the future might hold for them particularly around development
Usually people find that there are simpler/better ways to get the job done.
I think they’re better left as an implementation detail at this point.
CRDTs can do one magic trick no other technology solutions can do: They can let users collaboratively edit without needing a centralized server. And this works between users, between devices or between processes.
Its just, most of the time that doesn't matter. Servers are cheap, and big companies frankly seem to love it when we're dependent on their infrastructure.
I want CRDTs for more "personal computing". I want my data to be shared between my devices seamlessly. And I want that to keep working even when I can't contact google's computers. I also really like something about Git - which is the fact that my computers are first class citizens in a repository. Unlike Google Docs, if github ever goes down, I don't lose any data and I can still get my work done, and collaborate with my teammates.
All software should work like that. I'm fighting to make CRDTs work well so we can bring that future within reach.
At the beginning of that period I made and sold a startup on having a dead simple sync strategy, by myself, while I watched 3 funded competitors try to build sync, fail and go under. I had no funding and no CS education, I was a waiter.
In any case, you can't use a text "automerger" to collaboratively edit JSON text. (Whats an "automerger"?)
To understand why, suppose we had an empty (JSON) list: []. Two users concurrently inserted two items, "a" and "b". If those inserts get translated into string inserts, you end up with a JSON string containing ["a""b"] - which is a syntax error!
The trick to making this work correctly is that the CRDT / OT system needs to understand that you're editing a list. Don't collaboratively edit the JSON string. Collaboratively edit a list then JSON.stringify the result.
Related HN thread: https://news.ycombinator.com/item?id=29433896
AFAIK the best production-ready CRDT solution for text is Yjs [0], and in some specific cases, the result of the merge might be something unexpected (one example [1]). However, there is research-quality CRDT called Peritext [2] which is specifically designed to handle styled text in an intuitive way, so the merge is more predictable.
[0]: https://github.com/yjs/yjs
I've worked on a few different sync engines for mobile apps over the years, it's also a matter of user expectations in consumer apps. Users expect to seamlessly pick up where they left off on another device and the absence of an intermediary server makes that difficult.
The downside is you sort of have the worst of both worlds in terms of complexity. You need a working, performant CRDT and a working centralized server. But I think its a great model that we (as an industry) should explore more.
Here's all the ways I know for dealing with write conflicts in a distributed systems:
- Last write wins, AKA I'm going to pretend I've solved the problem and just randomly lose data
- Record all versions of the data, pick an arbitrary winner, store a revision, and surface it to the user if there's a conflict (the CouchDB strategy, I don't know anything else using this)
- Model your data so it's append only (events, maybe) then merge just becomes a set union of all the different nodes[0]
So including CRDTs, that's my general taxonomy of solutions to this problem. Are there more?
[0] Working on a prototype for this right now, if anyone has done similar work I'd love to pick your brain, email in profile.
My understanding is that "CRDT" really just means that you've defined how you're going to resolve conflicts consistently (see criteria in s2.2 of the paper above).
But if CRDTs really are a kind of a meta-language for resolving conflicts in a sane way - whether the CRDT is a single record or a whole data store - that's a nice thought. The CouchDB CRDT could be defined.
- Associativity: (A + B) + C == A + (B + C)
- Commutativity: A + B == B + A
- Idempotency: A + A = A
- Closure: Every merge result is a valid merge argument
- (perhaps a few others; it’s been a while since I read the original papers)
As long as your merge operator has all of these properties, you get the strong eventual consistency result that makes CRDTs a useful abstraction: Any two users that have received versions including the same updates will reconstruct the document in the same way, even if the actual set of versions seen differs.
Might have to re-read the papers with this thought in mind. It did seem like there was a duality there but I kind of dismissed it.
You can store that set of operations just as easily in a file or in a database table. (Though the table will take a bit more space on disk because you can't be quite as clever).
To generate the data value itself, you can either replay all the operations from scratch (which is not as bad as it sounds), or store a cached copy of the data at some version and use that. You can think about it as, the operations give you history, tell you how to merge in remote changes and contain the data remote peers need to sync. The data itself is the value you read out & display.
There's nothing special about the data itself. You can store all that data in a flat file, or a database table, or in a few arrays in memory. The fancy part is (usually) how you merge changes together.
Operation-based CRDT's are a bit different, these require commutativity and associativity. So you would be dealing with a multiset of reported operations.
https://hagit.net.technion.ac.il/files/2015/09/popl168gf-att...
What I'm more worried about is that we will prove that 'interesting text merges' are not all commutative. Though one trick we keep doing in spaces where things are proven impossible is that we cheat by creating tools that disallow or discourage the intractable scenarios. That could, for instance, lead to a generation of programming languages with a strange file structure that makes most workflows commutative.
That may sound strange or terrible to some people, but it's been my opinion for a number of years now that most of our coding conventions boil down to issues of avoiding merge conflicts, so a language that enforced a stronger form of conflict avoidance would be an 'opinionated' language but within the realm of the sorts of things we already put up with. Maybe no stranger than pure functional or Actor based languages, for instance.