3 ms·

Can you share any insight on latency? I feel that, while a prolly tree has the same big O bounds as a BTree, there are extremely large constant factors involved

by j-pb 3y ago

Can you share any insight on latency? I feel that, while a prolly tree has the same big O bounds as a BTree, there are extremely large constant factors involved. In the benchmark of their new storage engine that they published on their blog they had read operations take 3us and write operations take 96 us for in-memory workloads. That's an order of magnitude slower than what I get from a persistent trie implementation that uses unicity to achieve node hashability (instead of the other way around as in a prolly tree).[1] I could imagine that this becomes less pronounced in the durable on-disk case, as storage bandwidth and latency become the dominating factors? 1: https://github.com/triblesspace/tribles-rust/blob/master/src/patch.rs https://github.com/triblesspace/tribles-rust/blob/master/src...

iamwil 3y ago
Can you comment more on how you use persistent tries with unicity? And what do you mean by "the other way around"? I can't speak to latency fully as of yet. But in my own incremental implementation of a Prolly Tree, it appears to have the same Big-O bounds as a Btree (as you said). But I can see there are places that it has to do a bit more work. - Given the nature of merkle tree nodes identified by their hash, you have to go do look ups, rather than just following pointers. - The tree has to touch a swath of nodes from the bottom up, due to potential rebalancing. Unlike a Btree, where you just change a single node seam from root to leaf, even with splits and merges. - Prolly Trees are constructed from the bottom up, where you have to traverse across a layer. To find the next sibling, you sometimes have to travel up to the parents and come back down--hence subject to the occasional height traversal in the worse case. This doesn't happen often, especially if the cascading effect on insertion I talked about doesn't happen. But like you said, maybe there are other factors that dominate the latency equation. It's hard for me to say at this point. Relevant post: https://motherduck.com/blog/perf-is-not-enough/ https://motherduck.com/blog/perf-is-not-enough/
- j-pb 3y ago
  Disclaimer up front: I somewhat agree with the performance sentiment towards databases, however I feel that index performance is a different thing, because it gives you a larger budget for features further up the chain that make a meaningful non-performance difference for users, e.g. dynamic skew estimation and adaptation saving you from manual performance tuning. To make an additional performance point about my use-case, the work I linked is not competing with on-disk databases but with in-memory datastructures like nested hash-maps and I would argue the points from the article that you linked in that scenario, but with the scales adjusted appropriately (think ns and us instead of us and ms). To answer the question, prolly trees have a deterministic structure based on the chunking properties of their hash function. So their deterministic structure is a result of using a hash to identify nodes, and only implicitly defined over the contained keys (by rolling the hash over the leafs). Tries on the other hand, by virtue of being prefix trees, have a structure that is deterministic and directly based on the keys that they contain. This also allows you to compute a hash for each node (determined by they key range it represents) but because hashing is now orthogonal to the structure, you can choose tradeoffs more flexibly. You can for example use an incremental hash function [1], which in my case is SipHash for the leaves and xor as a combiner (Note the importance of using a keyed hash function like SipHash when XOR is used as a combiner, see the XHASH attack in [1].) So whenever a child is updated the new node hash can be maintained as `node.hash = (node.hash xor old_child.hash) xor new_child.hash)`. The original Nom author actually considered PATRICA Tries and HAMTs, but dismissed unhashed prefix-tries due to bad performance. I didn't run into this yet in my use-case however, and I suspect that the overhead of string interning, indirection vs direct pointers, and more expensive hash-functions, will always outweigh in the in-memory case. I'm still very interested in using prolly trees in the on-disk case, hence my question about latency :D 1: https://cseweb.ucsd.edu//~Mihir/papers/inchash.pdf https://cseweb.ucsd.edu//~Mihir/papers/inchash.pdf 2: https://github.com/attic-labs/noms/blob/master/doc/intro.md#some-properties-of-prolly-trees https://github.com/attic-labs/noms/blob/master/doc/intro.md#... BTW can you point me to where the "unicit" term originates from? a quick google search only ever shows it used in your writings :D
  - iamwil 3y ago
    Ah, thanks for the explanation. Some quick follow ups: Oh, so an incremental hash function is where you don't have to hash the entire thing again, but you can use the combiner (xor) to "remove" the old_child.hash and "add" the new_child.hash? And you use this to decrease the cost of hashing? Huh, I didn't make up the term "unicit". I read it somewhere, presumably from Aaron Boodman, who invented the Prolly Tree.
    - j-pb 3y ago
      Exactly! The xor combiner is somewhat special in that it is self inverse, so a xor b xor a = b. This property doesn't hold for the other combiners, so for any other combiner ⊙ you would need to compute the inverse `old_child_hash^-1` for the removed hash so that `new_hash = old_hash ⊙ old_child_hash^-1 ⊙ new_child_hash`. Although I feel like I should re-iterate that the xor-combiner (in the paper termed XHASH) does not produce a cryptographic hash in any way and to quote the paper "Indeed, it is not even one-way". For my use case this means that you can only perform set operations in O(|common-prefix|) time with trusted peers and I actually don't expose the hash beyond the process itself. You can ofc ingest data from untrusted peers, that's why the randomization function (the function used for the keys/leafs) is keyed, with a key that is choosen randomly at library initalisation. In my case I'm storing hashes in the branch-nodes, but re-compute hashes for the leafs, so when performing set operations between two tries you often don't have to compute any hash. I didn't mean to imply that, I was just hoping to find a new root for research paper exploration, but even if you did it would be fine, it's a property that should have it's own name, I personally call them "deterministic"-trees :D.

by j-pb 3y ago

iamwil 3y ago

Can you comment more on how you use persistent tries with unicity? And what do you mean by "the other way around"? I can't speak to latency fully as of yet. But in my own incremental implementation of a Prolly Tree, it appears to have the same Big-O bounds as a Btree (as you said). But I can see there are places that it has to do a bit more work. - Given the nature of merkle tree nodes identified by their hash, you have to go do look ups, rather than just following pointers. - The tree has to touch a swath of nodes from the bottom up, due to potential rebalancing. Unlike a Btree, where you just change a single node seam from root to leaf, even with splits and merges. - Prolly Trees are constructed from the bottom up, where you have to traverse across a layer. To find the next sibling, you sometimes have to travel up to the parents and come back down--hence subject to the occasional height traversal in the worse case. This doesn't happen often, especially if the cascading effect on insertion I talked about doesn't happen. But like you said, maybe there are other factors that dominate the latency equation. It's hard for me to say at this point. Relevant post: https://motherduck.com/blog/perf-is-not-enough/ https://motherduck.com/blog/perf-is-not-enough/

j-pb 3y ago
Disclaimer up front: I somewhat agree with the performance sentiment towards databases, however I feel that index performance is a different thing, because it gives you a larger budget for features further up the chain that make a meaningful non-performance difference for users, e.g. dynamic skew estimation and adaptation saving you from manual performance tuning. To make an additional performance point about my use-case, the work I linked is not competing with on-disk databases but with in-memory datastructures like nested hash-maps and I would argue the points from the article that you linked in that scenario, but with the scales adjusted appropriately (think ns and us instead of us and ms). To answer the question, prolly trees have a deterministic structure based on the chunking properties of their hash function. So their deterministic structure is a result of using a hash to identify nodes, and only implicitly defined over the contained keys (by rolling the hash over the leafs). Tries on the other hand, by virtue of being prefix trees, have a structure that is deterministic and directly based on the keys that they contain. This also allows you to compute a hash for each node (determined by they key range it represents) but because hashing is now orthogonal to the structure, you can choose tradeoffs more flexibly. You can for example use an incremental hash function [1], which in my case is SipHash for the leaves and xor as a combiner (Note the importance of using a keyed hash function like SipHash when XOR is used as a combiner, see the XHASH attack in [1].) So whenever a child is updated the new node hash can be maintained as `node.hash = (node.hash xor old_child.hash) xor new_child.hash)`. The original Nom author actually considered PATRICA Tries and HAMTs, but dismissed unhashed prefix-tries due to bad performance. I didn't run into this yet in my use-case however, and I suspect that the overhead of string interning, indirection vs direct pointers, and more expensive hash-functions, will always outweigh in the in-memory case. I'm still very interested in using prolly trees in the on-disk case, hence my question about latency :D 1: https://cseweb.ucsd.edu//~Mihir/papers/inchash.pdf https://cseweb.ucsd.edu//~Mihir/papers/inchash.pdf 2: https://github.com/attic-labs/noms/blob/master/doc/intro.md#some-properties-of-prolly-trees https://github.com/attic-labs/noms/blob/master/doc/intro.md#... BTW can you point me to where the "unicit" term originates from? a quick google search only ever shows it used in your writings :D
- iamwil 3y ago
  Ah, thanks for the explanation. Some quick follow ups: Oh, so an incremental hash function is where you don't have to hash the entire thing again, but you can use the combiner (xor) to "remove" the old_child.hash and "add" the new_child.hash? And you use this to decrease the cost of hashing? Huh, I didn't make up the term "unicit". I read it somewhere, presumably from Aaron Boodman, who invented the Prolly Tree.
  - j-pb 3y ago
    Exactly! The xor combiner is somewhat special in that it is self inverse, so a xor b xor a = b. This property doesn't hold for the other combiners, so for any other combiner ⊙ you would need to compute the inverse `old_child_hash^-1` for the removed hash so that `new_hash = old_hash ⊙ old_child_hash^-1 ⊙ new_child_hash`. Although I feel like I should re-iterate that the xor-combiner (in the paper termed XHASH) does not produce a cryptographic hash in any way and to quote the paper "Indeed, it is not even one-way". For my use case this means that you can only perform set operations in O(|common-prefix|) time with trusted peers and I actually don't expose the hash beyond the process itself. You can ofc ingest data from untrusted peers, that's why the randomization function (the function used for the keys/leafs) is keyed, with a key that is choosen randomly at library initalisation. In my case I'm storing hashes in the branch-nodes, but re-compute hashes for the leafs, so when performing set operations between two tries you often don't have to compute any hash. I didn't mean to imply that, I was just hoping to find a new root for research paper exploration, but even if you did it would be fine, it's a property that should have it's own name, I personally call them "deterministic"-trees :D.