Interfaces RFC: General idea, types

[mweidner037]

Short version

I've defined some interfaces for Crdts and would like feedback. There is one issue for each interface/type, plus this issue for discussion of the general idea & organization (e.g. which types are present). Please leave comments on the appropriate issue, or if you prefer, make new issues or PRs for specific problems. Issues are linked below.

Full version

Introduction

One of the changes I started in https://github.com/composablesys/compoventuals/pull/89 was to better organize the Crdt implementations, by providing one interface for each plain type that we make a Crdt out of, and having each Crdt implement the interface corresponding to its plain type. This is inspired by the Map, List, etc. interfaces in Java Collections.

My hope is that these interfaces have a few helpful effects:

• Crdts which represent the same plain type, just with different semantics, share a common API. This makes it easier to transfer knowledge from one implementation to another, or to swap out one implementation for another if you need to change semantics.
• Implementations are more discoverable, since you can start with the plain type you want, find its interface, and then look for implementations of that interface.
• One can make generic constructions that build a Crdt from any implementation of a given interface, e.g., a PlainMap<K, V> that uses any Register<V> to resolve conflicts between concurrent set operations.

Since these interfaces affect every Crdt and a lot of the user experience, it's important to get them "right", and any feedback would be very helpful for this.

We also have to decide which implementations to include, especially for the collection types, which have lots of possibilities.

Interfaces

• Register<T>: An opaque plain value of type T. Issue: https://github.com/composablesys/compoventuals/issues/100
• Boolean: A boolean value. Issue: https://github.com/composablesys/compoventuals/issues/101
• Number: A number value. Issue: https://github.com/composablesys/compoventuals/issues/103
• Collections (Set, Map, List): see next section.
  • Sets issue: https://github.com/composablesys/compoventuals/issues/104
  • Maps issue: https://github.com/composablesys/compoventuals/issues/105
  • Lists issue: https://github.com/composablesys/compoventuals/issues/106
• JSON is TBD.

Collections

For each of {Set, Map, List}, there are two interfaces:

• A "Plain" version (e.g. PlainSet), which is a collection of opaque plain values. These values can be set and get, but not internally mutated.
• A "Crdt" version (e.g. CrdtSet), which represents a collection of mutable values. In reality, it is a collection of value Crdts. Those Crdts can not be set directly; instead, you use their operations to mutate the represented value. E.g., a CrdtMap<string, Number> is the Crdt version of an ordinary Map<string, number>, where instead of setting values directly, you mutate them using Number.add operations.

Implementations

Some of the interfaces, especially the collections, have multiple possible implementations. Different implementations of the same interface differ in their conflict-resolution semantics, which also affect efficiency.

Each issue above discusses the planned implementations for that interface, and I would appreciate feedback on these as well. My main danger is probably adding too many implementations, some with questionable utility - it's tempting to include every feasible semantic & optimization, but too many classes might overwhelm users.

[mweidner037]

First bullet: goes against usual workflow that interface determines semantics. Need to make this clear in the docs. (Especially for weird semantics, e.g., violating sequential.)

[mweidner037]

For JSON: for now I will just leave the implementations, without a specific interface.

[mweidner037]

To mitigate possible doc overload from many implementations: have a static "of" method on each interface that returns a reasonable default implementation. E.g. AddWinsSet for non-Crdt types; restorable (non-GCing) YjsCrdtSet for Crdt types, using the Crdt constructor itself as the valueConstructor. I think this should be possible by declaring e.g.

const CSet = {
    of(...) { ... }
}

in addition the CSet interface.

[mweidner037]

In general, implementations not supporting a method (e.g. delete, clear) should throw an error instead of silently ignoring it, analogous to Java Collection's UnsupportedOperationException.

[mweidner037]

Need to remember to remove methods no longer needed (e.g. CSet.keys()).

[mweidner037]

Also remember to override default implementations when you can do them faster (in particular, searching methods on Crdt collections, like CList.indexOf).