A popular solution to local-first sync is a CRDT (conflict-free replicated data type). These are cool data structures that can automatically merge in changes made offline, while ensuring that all clients eventually agree on the state.
CRDTs are great, but...
Conversation
By allowing any change to merge in no matter when it was made, CRDTs struggle with strong integrity constraints (foreign key, uniqueness, etc.). They also don't usually allow transactions.
1
3
And if you're thinking "well, I'm not a bank, I don't need transactions": the paper has a cute example of an instance where even a *photo manager* needs to maintain transactional consistency.
1
7
I'm pretty sure there's a Greenspun-type law here: any program built on top of a non-transactional database will eventually grow an ad hoc, informally-specified, bug-ridden, slow implementation of half of a transactional database.
So what can we do? It's in the title!
1
8
Instead of forcing everything to merge, "merge what you can, fork what you can't".
If an offline change doesn't conflict with anything, great, merge it! If it does: keep both versions around. We call this the "forking histories model".
1
4
When I talk to programmers about this, they mostly ask "isn't this just git?"
I'd argue that git is an instance of the forking histories model for the data structure of plain text that gets compared and merged via diff/patch.
But most data is not text!
1
3
The second half of our paper is a proposal that we called TreeDB, which is an instance of forking histories model for structured data. It's basically git, but replacing plain text diffing with *conflict sets*, a technique that we lifted from multi-version concurrency control.
1
5
We took our conflict set definition ~verbatim from FoundationDB!
One cool thing that gives you is an existence proof of how powerful they are: my team at Apple built an entire relational database where all the transactions were defined by conflict sets!
1
5
This was just a workshop paper with a cool proposal, not an implementation.
If you're interested in forking histories/TreeDB, whether to prove theorems about it or try implementing it, I want to talk to you! I will seriously talk your ear off about this stuff if you let me. 😅
3
1
5
Replying to
Have you seen ? pijul.org/manual/theory.
Looks like they took a similar approach. Conflicts are explicit, but unlike git they are first class, and don’t impede any work or unrelated merges.
1
1
No, I haven’t! This looks closely related. Thanks for the pointer!
This Tweet was deleted by the Tweet author. Learn more
This Tweet was deleted by the Tweet author. Learn more
Show replies