Hacker News Reader

Comment by lifty | Hacker News Reader

Regarding the growing log in CRDTs, it doesn't have to be that way. Most of these popular CRDT libs use Merkle DAG only to build up the log of the changes. But there is a better way, you can combine a Merkle DAG for ordering + prolly trees for storing the actual state of the data. That gives you total ordering, an easy way to prune old data when you choose to, and an easy way to sync. Look into fireproof for how this is combined.

Regarding distributed schemas, I agree, there's a lot of complexity there but it's worth looking into projects like https://www.inkandswitch.com/cambria/ and https://github.com/grafana/thema, which try to solve the problem. It's a young space though. If anyone else knows about similar projects or efforts, please let me know. Very interested in the space.

View on HN

Interesting! Do you mind explaining the idea in more detail?

As far as I understand, libraries like Automerge use the Merkle DAG to encode a document as an immutable bundle of state changes aka operation log + the causal ordering which enables conflict free merging between multiple peers. The final document is reconstructed by combining the state transitions. So the Merkle DAG is both the state and the causal relationship between mutations which allows the merge "magic".

Prolly trees allow you to store history independent data which is trivial to sync, diff and merge, regardless of insert order, merge order or originating peer. A Merkle DAG layered on top of prolly trees (event reference prolly tree roots) gives you causality so that peers can agree on a common view of history. So it's very useful because you can check integrity and travel in time, but you can keep as much of it as you want, because it's not necessary for constructing the current state. Prolly trees give you the current state and the easy syncing, diff,merge. So you can truncate the history as needed for your use case.

For a production ready implementation of prolly trees you can check Dolt. For a combination of Merkle DAG (https://github.com/storacha/pail) and prolly trees you can check https://github.com/fireproof-storage/fireproof

Those are lovely data structures and I know about them. But how are you planning on using those data structures? What CRDT are you building?

You might also be interested in Alex Good's Beelay algorithm: https://www.youtube.com/watch?v=neRuBAPAsE0

Prolly trees can act as CRDTs if you have a merge function that always merges and doesn’t block.

So my initial comment merely tried to make the point that there is a design space where you’re not stuck with the tradeoff of carrying the full Merkle DAG history just to be able to reconstruct the latest version of your document.

Thanks for the video, will check it out!

Reply on news.ycombinator.com