3 ms·
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
by lifty 7mo ago
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 https://github.com/storacha/pail) and prolly trees you can check https://github.com/fireproof-storage/fireproof https://github.com/fireproof-storage/fireproof
- josephg 7mo agoThose 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 https://www.youtube.com/watch?v=neRuBAPAsE0
- lifty 7mo agoProlly 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!