2 ms·

:) 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, hav

:) 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.

josephg 7y ago
Oh cool! GitHub link?
- marknadal 7y ago
  https://github.com/amark/gun 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 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 https://gun.eco/docs/Counter ). Rich text also grow-only. Happy to expand on anything else, too!
  - canadaduane 7y ago
    Keep up the awesome work! I've been watching gun on the sidelines, and look forward to its eventual domination ;)

josephg 7y ago

Oh cool! GitHub link?

marknadal 7y ago
https://github.com/amark/gun 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 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 https://gun.eco/docs/Counter ). Rich text also grow-only. Happy to expand on anything else, too!
- canadaduane 7y ago
  Keep up the awesome work! I've been watching gun on the sidelines, and look forward to its eventual domination ;)