Comment by josephg
6 years ago
I disagree. I think OT systems are way simpler to reason about, because they’re just an extension of event sourcing. Also CRDTs type implementations have been trailing OT algorithms in terms of features forever. OT got JSON editing support first, and JSON1 (the OT algorithm I linked above) also supports arbitrary tree reparenting, which as far as I know is missing from all CRDT algorithms. That’s needed to implement apps like workflowy, where you can drag trees around.
CRDT algorithms have documents which grow without bound. With OT, the documents are always minimal and it’s easy to reason about (and implement) trimming operations.
CRDTs are a better tool for distributed applications, but for server client stuff OT works fine.
:) 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!
1 reply →
Well, CRDTs were born to simplify reasoning. You can't really claim that OT is simpler. And performance of both is implementation specific with similar theoretical bounds. But, of course, CRDTs are much more general and foundational.