Comment by marknadal
6 years ago
:) I got arbitrary tree reparenting and mutable (and immutable!) state working in our CRDT, for about 4 years now. No unbounded growth!
Runs in production, having done 1TB p2p data in a day, on $99 hardware! Internet Archive and others use it.
I do agree tho, most CRDT implementations have just as many scaling and compaction problems as any append-only log system.
OT is worthwhile to understand.
Oh cool! GitHub link?
https://github.com/amark/gun
var a = {b: 1, c: {d: 2}, e: 3, f: {g: 4}};
a.c.z = a;
Every object has its own UUID, which makes circular references & sub-objects easy to reference.
a.c = (UUID pointer to c)
a.c.z = (UUID pointer to a)
a.f = (UUID pointer to f)
Now we can
(a.f.z = a.c) && (a.c = null)
c doesn't actually move, just the pointers on `a` and on f.
c now has a new parent (or could have 2 parents, since any graph is allowed).
Since everything is represented on disk/wire as a flat graph, all updates can be well defined as operations on `UUID.property = primitive/pointer` atomic changes in the CRDT.
This means there are only 7 operations to commute: (I hate switch statements, but someone helping me formalize the CRDT wanted it expressed this way)
https://jsbin.com/hedeqoxusa/edit?js,console (click run to see each operation applied)
You see order-of-operation doesn't matter.
Once merge has happened, history does not need to be preserved (no unbounded growth!) but it can if you want log/history.
Merged states can be stored as a flat graph on disk with a radix tree which allows for O(1) lookups on UUID+property pairs regardless of graph size.
There are some caveats though, of course:
Strongly Eventually Consistent, so don't use for banking.
Counter operations still grow-only but can be done in 12 lines ontop (see https://gun.eco/docs/Counter ). Rich text also grow-only.
Happy to expand on anything else, too!
Keep up the awesome work! I've been watching gun on the sidelines, and look forward to its eventual domination ;)