6 ms·

TLDR: Local-first software is powered by CRDTs. If you want to learn more about CRDTs, check out: - https://github.com/automerge/automerge https://github.com

TLDR: Local-first software is powered by CRDTs. If you want to learn more about CRDTs, check out: - https://github.com/automerge/automerge https://github.com/automerge/automerge (author's project, legit) - https://www.youtube.com/watch?v=yCcWpzY8dIA https://www.youtube.com/watch?v=yCcWpzY8dIA (deep technical talk) - https://gun.eco/distributed/matters.html https://gun.eco/distributed/matters.html (my Cartoon Explainer)

josephg 7y ago
OT also works fine for this sort of stuff. OT algorithms are easier to implement ([1] for an implementation I wrote of OT over arbitrary JSON structures). OT just requires a central source of truth / a central authority. For local first stuff depending on how you design it you can have one of those - in the form of your server. [1] https://github.com/josephg/json1 https://github.com/josephg/json1
- marknadal 7y ago
  Your work originally inspired me to get into this stuff. :) <3 thanks so much for your amazing contributions to OSS.
- zzzcpan 7y ago
  OT are inferior to CRDTs in every single way. In 2019 people shouldn't even be looking at OT.
  - josephg 7y 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.
    - marknadal 7y 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.
      - 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!
        7y ago

josephg 7y ago

OT also works fine for this sort of stuff. OT algorithms are easier to implement ([1] for an implementation I wrote of OT over arbitrary JSON structures). OT just requires a central source of truth / a central authority. For local first stuff depending on how you design it you can have one of those - in the form of your server. [1] https://github.com/josephg/json1 https://github.com/josephg/json1

marknadal 7y ago
Your work originally inspired me to get into this stuff. :) <3 thanks so much for your amazing contributions to OSS.
zzzcpan 7y ago
OT are inferior to CRDTs in every single way. In 2019 people shouldn't even be looking at OT.
- josephg 7y 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.
  - marknadal 7y 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.
    - 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!
        7y ago