Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Merklizing the key/value store for fun and profit

joelgustafson.com

Post reply on HN
Print view View original

11–18 of 18 posts

Re: Merklizing the key/value store for fun and profit

#11

Post by FpUser »

usr1106 wrote: post #3

As someone following German politics I had to read the headline twice :) Haven't seen it used without tree. (Yes, the spelling is not the same, but we are talking associations, not exact science.)

LOL. I also thought of Merkel when looking at the title.

Re: Merklizing the key/value store for fun and profit

#12

Post by jchanimal »

If you are excited about these data structures you might be interested in my new database engine using prolly trees and designed to be used by React developers.

Blog: https://fireproof.storage/posts/from-mlops-to-point-of-sale:...

React hook: https://use-fireproof.com

Re: Merklizing the key/value store for fun and profit

#13

Post by joelg »

noctune wrote: post #7

Wouldn't it be simpler to use a trie over the hashes instead? It seems to me like it would have the properties desired here. I think the parent/child rule described here might actually result in some kind of trie.

The difference is that a trie over the hashes doesn't preserve lexicographical key ordering or support range queries, which are typically expected from key/value stores. But you're right - if you just need `get` / `set` / `delete`, you could just do that!

Re: Merklizing the key/value store for fun and profit

#14

Post by Solvency »

Does anyone know how a tool like Figma or Miro handle conflict resolution or synchronization so efficiently in real-time? For example: the position of a simple colored box being manipulated by 2 or more people at the same time. Is this article even remotely relevant for such a use case?

Re: Merklizing the key/value store for fun and profit

#15

Post by wereHamster »

Solvency wrote: post #14

Does anyone know how a tool like Figma or Miro handle conflict resolution or synchronization so efficiently in real-time? For example: the position of a simple colored box being manipulated by 2 or more people at the same time. Is this article even remotely relevant for such a use case?

For collaborative editing you basically have two systems how to synchronize changes: CRDT or OT. Figma chose CRDT. They wrote two blog posts about it:

https://www.figma.com/blog/how-figmas-multiplayer-technology...

https://www.figma.com/blog/making-multiplayer-more-reliable/

Re: Merklizing the key/value store for fun and profit

#16

Post by themoonisachees »

Question:since doing this requires hashing your entire tree, what are the implications of doing this hashing operation on possibly millions of entries (which I'm estimating is the scale at which comparing linearly really start being noticably slow)?

I'm guessing you need to choose a hashing function correctly, but is hashing 2n elements then comparing in log(n) actually that much faster than comparing in n? Evidently, with the right settings yes, or we wouldn't be here, but I'm just wondering if the hashing step doesn't actually end up costing a lot more than we think by saying "oh we just hash it"

Re: Merklizing the key/value store for fun and profit

#17

Post by [deleted] »

themoonisachees wrote: post #16

Question:since doing this requires hashing your entire tree, what are the implications of doing this hashing operation on possibly millions of entries (which I'm estimating is the scale at which comparing linearly really start being noticably slow)? I'm guessing you need to choose a hashing function correctly, but is hashing 2n elements then comparing in log(n) actually that much faster than comparing in n? Evidently…

[deleted]

Re: Merklizing the key/value store for fun and profit

#18

Post by joelg »

themoonisachees wrote: post #16

Question:since doing this requires hashing your entire tree, what are the implications of doing this hashing operation on possibly millions of entries (which I'm estimating is the scale at which comparing linearly really start being noticably slow)? I'm guessing you need to choose a hashing function correctly, but is hashing 2n elements then comparing in log(n) actually that much faster than comparing in n? Evidently…

The merkle tree is persisted, and updating it is only log(n). You only have to "hash 2n elements" once, and then incrementally maintain it. It's negligible overhead for free log(n) diffing.
Post reply on HN