flâneur

Merklizing the key/value store for fun and profit | Joel Gustafson

joelgustafson.com · 8,385 words · saved by 1 readers

Suppose you and I each have a local key/value store. We suspect our key/value stores have mostly the same contents, but that there might be a few differences: a couple entries that you have that I don’t, that I have that you don’t, or conflicting values for the same key. What’s the best way for us to compare the content of our databases and identify the differences? Naively, I could send you all of my entries, and you can send me all of your entries. Or I could send you all of my entries, and you could iterate over them and just send me back the diff. But this is still linear in the number of entries. If you and I care enough about making diffs efficient, we can both maintain a special kind of merkle tree called a Prolly Tree that allows us to skip large sections of shared entries and identify conflicts in logarithmic time. This “merkle syncing” capability is a powerful and versatile peer-to-peer primitive and can be used as a natural persistence layer for CRDT systems, an “rsync for k

--> Merklizing the key/value store for fun and profit | Joel Gustafson Merklizing the key/value store for fun and profit Joel Gustafson / Posts / 2023-05-04 Suppose you and I each have a local key/value store. We suspect our key/value stores have mostly the same contents, but that there might be a few differences: a couple entries that you have that I don’t, that I have that you don’t, or conflicting values for the same key. What’s the best way for us to compare the content of our databases and identify the differences? Naively, I could send you all of my entries, and you can send me all of yo

saved by

related reading