go-ds-crdt VS verneuil

I forgot: key-value store using MD-CRDTs was implemented here: https://github.com/ipfs/go-ds-crdt

The trickiest part was not the CRDT, but the DAG traversal with multiple workers processing parallel updates on multiple branches and switching CRDT-DAG roots as they finish branches.

In https://github.com/ipfs/go-ds-crdt, every node in the Merkle DAG has a "Priority" field. When adding a new head, this is set to (maximum of the priorities of the children)+1.

Thus, this priority represents the current depth (or height) of the DAG at each node. It is sort of a timestamp and you could use a timestamp, or whatever helps you sort. In the case of concurrent writes, the write with highest priority wins. If we have concurrent writes of same priority, then things are sorted by CID.

The idea here is that in general, a node that is lagging behind or not syncing would have a dag with less depth, therefore its writes would have less priority when they conflict with writes from others that have built deeper DAGs. But this is after all an implementation choice, and the fact that a DAG is deeper does not mean that the last write on a key happened "later".

The idea of DAG-embedded CRDTs is far from new and was introduced here:

https://arxiv.org/abs/2004.00107 (I'm among the authors)

Unfortunately, the verification that the author proposes (not accepting new updates until the dag below is verified) will need a lot of caveats for real world usage.

Currently we use these CRDTs for a key value database of 40M+ keys in a deployment of ipfs-cluster, which uses https://github.com/ipfs/go-ds-crdt .

Not 100% the thing, but potentially related work in this area:

https://github.com/ipfs/go-ds-crdt

(See link to paper, and links to other projects in it, like OrbitDB).

It'd be process wide. If you want an example can check out the example using a vfs here. There's an explicit passing of vfs there and an implicit usage of it. https://github.com/backtrace-labs/verneuil/blob/main/examples/rusqlite_integration.rs

It doesn't even have to be WAL-based system. Backtrace Labs has a SQLite virtual file system (VFS) called Verneuil that works similarly but works with the rollback journal instead of the WAL.

https://github.com/backtrace-labs/verneuil/ is one way to address the diffing / read replica part of the problem. I believe it's compatible with gossipping: most of the data is in small content-addressed chunks, with small manifests that tell clients what chunks to fetch and how to reassemble them to recreate a sqlite database. There's already client-side caching to persistent storage, and chunks can be fetched on demand.

Sharing replication data P2P, while retaining the simplicity of a single authoritative writer per database, is explicitly part of the project's long-term goals!