Mergeable replicated data types – Part I
blog.acolyer.org
blog.acolyer.org
And if you ignore operations, many datatypes reduce down to very simple mathematical objects. For example even though set and priority queues are very different in code, they both only need membership (R_mem) to fully specify because you can rebuild a priority queue knowing just the members. To specify a list/queue/stack, you only need to additionally know ordering (they denote this relationship as R_ob for "occurs before").
The advantage of converting a datatype (bijectively) to this relational domain is that you can essentially do "state-based" merging. You only need to define: how to convert to the relational domain, how to merge within that domain (which is still rich enough for you to specify relational invariants you need preserved), and how to convert back to the concrete datatype. Contrast this with operation-based syncing, where you would need a quadratic explosion of definitions for how any two operations should merge together. Here you don't even need to handle any particular operation individually (e.g., if it works for push_front, you will likely get push_back for free). Essentially it is saying the semantics of an operation is captured by the delta caused to the characteristic relations of the datatype.
Without them, you have to use either explicit synchronisation which is a bad idea if you want local-first software (doesn't work offline, needs to be done even when editing disjoint bits of the file, etc.) or something like CRDTs. Now there is a great paper by Victor Gomes, Martin Kleppmann, and Dominic Mulligan that proves (in a proof assistant!) that pretty much all other alternatives that do not use strong consistency is flawed in edge cases.
As for triviality of the operations, I know for a fact that Martin Kleppmann has a paper in the works that show (and prove) how to do tree move efficiently as a CRDT. That means you can basically do arbitrary edits on JSON. Hopefully, that should clear up any confusion about for which applications it might be useful.
> The point is often you don't need to. If you use Google docs, the chances are you will be editing it disjointly most of the time and occasionally you'll edit the same bit of the document. Then you don't really care if what comes out is a meaningful sentence, but that all parties involved (regardless in which order they see the operations) see the same version of the document so that they can fix it. That's what CRDTs buy you.
Ok, so the hope is that semantic conflicts are rare and if they do happen, users can easily see them and promptly correct them. I guess this works well if the invariants are local and synchronization is fairly frequent (i.e. on the scale of seconds, not weeks).
> That means you can basically do arbitrary edits on JSON. Hopefully, that should clear up any confusion about for which applications it might be useful.
Not quite. Of course you can model everything in JSON, but the question remains as to how much additional implicit structure is needed atop the explicit tree-like structure that JSON provides and how easily this implicit structure is disturbed by merges.
As a more concrete example, Apple Notes edits tables and resolves conflicts via CRDTs. Now for editing tables in a word processor, you can have multiple users moving, adding, and deleting columns, in addition to editing the text within a cell. (One user adds a row, another adds a column. One user deletes a column and another moves it. etc.)
If you just naively represent this as a list of lists, the semantics expected by the user breaks. (One user adds a row, another adds a column, and you have a short row with cells in the wrong place.)
Apple ended up representing the columns as an ordered set of ids (piecing this together from other CRDTs) the rows as a second ordered set of ids, and then the text blobs as a map of column id, to a map of row id to a text crdt object. With the additional assumption that any "missing" text is in the blank, initial state. (I might have this transposed, it's from memory, but that's the basic idea.)
It works, and works well, but a lot of thought and effort was put into modeling the domain as CRDTs to capture the required semantics.
(Here, for ordered set, you can use a list CRDT, drop duplicates, and tack on an add-only set of tombstones to keep move/delete conflicts from resurrecting rows/columns.)
Yes, I need convergance, but I also need to ensure application invariants are maintained.
I agree with parent that a CRDT isn't that useful for local-first software unless you can encode arbitrarily complex programmatic logic in the transitions. That way I as a developer have control over how merges happen globally and all invariants. It's too complex to reason about otherwise.
It's not clear to me if this paper gives me what I'm looking for -- I'm looking forward to digging into it.
There are other approaches to CRDTs that I'm more excited about: Statebox (https://github.com/mochi/statebox) from years ago is a CRDT that encodes arbitrary transitions and converges by rewinding and replaying in a consistent order. This is basically the same trick blockchains typically do to merge forks. Radicle (https://radicle.xyz/) is another related approach.
I think things like this are the better path forward for local-first software, personally.
0
/ \
+1 / \ +2
/ \
1 2
\ /
\ /
\ /
3 <= correct result
0
/|\
/ | \
/ | \
/ | \
/ | \
+1 / |+100 \ +2
/ | \
1 100 2
\ / \ /
\ / \ /
\ / \ /
101 102
\ /
\ /
\ /
203 <= incorrect result, 100 is accounted for twice.
It is accounted for twice because the lowest
common ancestor is '0'.
The problem I should have started with is that regular LCAs are not useable for conflict resolution because there can be multiple different LCAs.
For example, in the graph at https://cs.stackexchange.com/questions/72538/lowest-single-c... which LCA do you use to merge 3 and 4?
So you have to use some sort of "unique LCA", which is 0 in the example I gave. But even that does not work as I showed in 2nd example.
0
/\
+1 / \ +2
/ \
1 2
| \ / |
| \/ |
| /\ |
| / \ |
3 3
| \ / |
| \/ |
| /\ |
| / \ |
? ?
Basically the problem is that the merge operation isn't idempotent, hence it doesn't define a semilattice, which seems to be what you want if you want to ensure consistency even over distributed systems.
They could have easily fixed this by picking a better merge operation such as a union or maximum, but it's not encouraging when someone picks an illustrative example that doesn't quite work.
I'm not entirely convinced that the merge for the 'counter' always works if you've got a single LCA though. It seems like it should obviously work, but I'm a bit concerned given that you can easily create a counter example where the formula doesn't work if you allow for multiple LCA. So somehow having a single LCA is vital for the formula to work and it's not entirely obvious to me why.
Anyway if you end up just calculating something equivalent to the union of the history (+some interpretation) then you're probably fine.
If you're referring to having multiple roots, there are two solutions:
(a) define your 3-way-merge primitive (the non-recursive version) to support merging two states against an imaginary "zero" that acts as the single root. So in the counter version you can imagine that everything "actually" starts from 0.
(b) arrange your application so there are never multiple roots. In some cases this not really a constraint, usually one single person starts a document and it doesn't make sense to merge something else in later. In some other cases (group chats, tree histories like git) this is probably not acceptable and you will need (a). But in the examples I just gave, a reasonable (a) is fairly straightforward to think of.
It's a bit tricky to show that the 3-way merge always works fine if you've got a single least common ancestor. But yeah it looks like you're fine because any update that both have in common will also have reached the LCA (this was the insight I was missing that explains why a single LCA works and multiple LCA do not if you naively apply the 3-way-merge).
You can have some replica that has 100, merge with an other replica and get 101. Then an other replica that also had the same 100 merge with an other replica and get 102.
Then when 101 and 102 merge, the lowest common ancestor is still 0, so you get 203.
Super cool, I first used the library back in 2015-ish and I remember being blown away by how innovative and unique it was.
I'm working on a serverless, distributed P2P compute network that's basically a PubSub event queue/job system using some hacks on top of Dat protocol right now for a side project.
Do you think I might be able to use or leverage GUN instead?
Yeah, absolutely. Tho DAT is one of the better ones. Do you need mutability? That is probably the biggest differentiator.
Either way, you should come chat about it on http://chat.gun.eco/ super friendly active community discussing stuff like this all the time. :)