CausalLog CRDT

[tantaman]

https://vlcn.io/blog/crdt-substrate outlines how to create a causal log and traverse it so all peers have the same state.

Now that I'm finally implementing #181 today so users can declare CRRs via:

CREATE VIRTUAL TABLE foo USING CLSet

we can start adding more CRDT types to back tables.

E.g.,

CREATE VIRTUAL TABLE foo USING CausalLog
CREATE VIRTUAL TABLE foo USING DeleteWinsSet
CREATE VIRTUAL TABLE foo USING AddWinsSet
...

CausalLog would be a nice way to back tables as it gives us a better audit trail and the user some extra flexibility on merge semantics.

Implementation

We can do it two ways (maybe we even support both).

One way --

CREATE VIRTUAL TABLE todo_schema USING CausalLog (
  id PRIMARY KEY,
  content TEXT,
  complete INT
);

which creates:

1. the todo table with the desired schema
2. a companion table to track events about the todo table

CREATE TABLE todo_companion (
  event_id,
  item_id ID_of<todo>,
  event ANY
);

CREATE TABLE todo_event_edges (
  parent_id,
  event_id
);

and a view? or vtab? to do a deterministic traversal of events.

The onus is on the user to create event types and process them to build current state. Given that, maybe we only provide a log structure and nothing about the base item table.

Other way --

We could come up with the events ourselves in a similar way to sqlite.org/undoredo.html