Lab note #041 Two flavors of Op-based CRDTs as a baseline

I've now implemented an Op-based and a Pure op-based CRDT. I couldn't quite make the leap before to merkle-based CRDTs. While vectors clocks are mechanically simple, I wasn't quite sure how they mapped to a merkle-DAG node if replica IDs weren't available. After seeing them in action, I'm fairly certain that any vector clock for an update that's concurrent with another vector clock at another replica maps to concurrent branches in a merkle-DAG

Pure op-based CRDTs are interesting. A critical insight in their design that contrasts with Op-based CRDTs is that if you standardize on the commutative operation on write, you don't need a custom handler for each type of CRDT. Because it's standardized on write, the state won't be in a final form needed by the end user. Hence you can construct the final view from the intermediate state on read.

It's also interesting in that it splits up its state into stable and unstable state. Stable state os a point in logical time where we know all replicas have caught up. Hence any events older than that can be tossed. This means we can keep the amount of metadata low as the replicas collaborate on the state.

The downside is that if a replica goes offline and never replies, then the remaining replicas can never advance the stable state. In that case, we can notify the remaining nodes to evict the unresponsive node. And when the unresponsive node comes back online, it'd have to reset its state to the latest agreed stable state.

One reason I want to move towards a merkle-CRDT is so I can maintain an immutable history of all events. But rather than pruning history as a default, I think I can opt for compression. This is the strategy that Git, Automerge, and Braid take, and it seems to work pretty well. And because merkle-DAGs are immutable, I can leverage structural sharing as well. Immutability should be an advantage for distributed systems, so it seems to make sense to bake it in as a default.

Another downside is common to State, Op, and Pure-op based CRDTs is the reliance on vector clocks that require a replica Id. These assume there's a fixed number of replicas collaborating and don't work very well if there's an unknown or constantly changing number of replicas advancing the state. It seems like merkle-CRDTs remove this restriction.

Two downsides I can currently see for a Merkle-based CRDT with a merkle clock is, first, clock comparisons require walking down the merkle-DAG to see whether one hash is an ancestor of another. This is potentially slower than walking the number of replicas, since we currently set no restriction on how long any replica can be offline. Hence, we could potentially be walking the entire history of the merkle-DAG. I think there are ways to mitigate this so that it's O(N log N) rather than O(N) where N is the number of hops from one hash to another.

Second, merge and diffs between its payload may take too long, depending on the data structure. However, given the implementation of Prolly Trees I have in hand, I don't expect this to be a significant problem.

Next, I'm going to start on the Merkle-CRDT implementation with a naive merkle clock comparison to see that it's working for basic data structures. And now, I have a pure-op based implementation to compare results against. So what we'll have at the end is an immutable data structure that can sync across replicas.