Add List CRDTs - Githubissues

composablesys / collabs

Collabs library monorepo

https://collabs.readthedocs.io/

Apache License 2.0

253 stars 11 forks source link

Add List CRDTs #28

Closed mweidner037 closed 3 years ago

mweidner037 commented 3 years ago

We need at least a basic list (sequence) CRDT for JSON. Possibly we could make a wrapper around Yjs, since that is reasonably optimized, and I don't expect we can build list CRDTs in a way that is compositional or somehow nicer than current approaches.

mweidner037 commented 3 years ago

Draft interfaces (no implementations yet): https://github.com/composablesys/compoventuals/commit/539e639b39475b46aa3e35a54fd358fcd4030902 IAtomicList matches the simple interface used by Legion, but I think Automerge might have more flexibility - see the TODOs in the docstrings.

mweidner037 commented 3 years ago

Should check out Yjs's list interface for comparison

mweidner037 commented 3 years ago

Basic list: https://github.com/composablesys/compoventuals/pull/46 I'd like to also implement LSeq or some variant, that is practical at least for standard LtR text editing. This should only require extending StatelessTreeSource (see NaiveList).

mweidner037 commented 3 years ago

[ ] LSeq / some variant of tree-based dense timestamps that doesn't give linear efficiency on LtR editing
[x] Text editing Crdt that is more efficient than using a per-character LwwRegister in a MapCrdt (although the LwwRegister approach is how it work naively when using JSON, so perhaps we should benchmark that as well?).

mweidner037 commented 3 years ago

Closing for now, although optimized implementations are still needed