This is from 2022. It is based on Noms [1], which is no longer maintained (they forked it).
I think the Noms doc linked from this article [2] is clearer than the article itself. That said I sill cannot turn my head around to grasp how this entire thing work tbh. I hope they wrote a peer reviewed paper to serve the audience better.
I never really understood Prolly Trees. With content-defined chunking (which is the only addition to regular b-trees), you always need a maximum size because it is possible for pathological content to not ever have a boundary (therefore you get one massive chunk, or for trees one massive branch node).
However once you have chunks of fixed size (the maximum) instead of content-defined sizes, changes to the content become non-local: a change in one part of the data might change an arbitrary number of following chunks/nodes.
Did they find a solution to that? Did they ignore it?
Some CDC implementations I have seen use a desired "average" chunk size value in addition to a minimum and maximum value. If the chunk exceeds the desired average size, the test for recognizing a byte sequence as a stop becomes more forgiving. Other solutions also retry previously processed sequences using the simpler threshold.
However, from what I've seen, these methods generally come at the cost of deduplication and/or speed. The most reliable method to avoid pathological cases seems to just be setting the min/max chunk size to a low/high enough value respectively.
If you're talking in a purely theoretical sense, I would assume that the possibility of changes affecting non-local chunks is inherent to CDC. With well-chosen parameters the likelihood of any but the closest chunks being affected just becomes low enough to be negligible.
The problem is that pathological cases are things like a repeating pattern (or repeating byte). Another issue is deliberate attacks: if a Dolt user can craft datasets for which single row changes translate to a duplication of the entire tree (and dataset), this becomes an obvious DOS vector for hosted Dolt platforms.
From what I've seen the likelihood of triggering a pathological case with real-world non-malicious data is actually low enough to be ignored, given that the rolling hash function is well-crafted. I do agree that crafting malicious data to break deduplication in Dolt should be relatively easy, but I do not see how this could lead to DOS on e.g. a hosted Dolt platform. If I understand correctly, your proposed attack would only affect the rate of deduplication and by extension disk space used, and I would expect a hosted Dolt platform to have strict disk-space limits or use storage-based billing.
Here's a more recent write-up on chunking that details some of them, but it mostly comes down to using a better hash function, and having a fail-safe max chunk size for truly pathological cases.
I really wonder what the memory overhead of the prolly tree is.
Using hashes as links isn't cheap especially with sha-512 wide hashes (I think they use 20bytes in reality?).
I'd estimate their fanout at between 50-200, which isn't that much either.
So my feeling is expensive nodes, combined with low-ish fanout => high cost of storage?
14 comments
[ 2.9 ms ] story [ 39.8 ms ] threadI think the Noms doc linked from this article [2] is clearer than the article itself. That said I sill cannot turn my head around to grasp how this entire thing work tbh. I hope they wrote a peer reviewed paper to serve the audience better.
[1] https://github.com/attic-labs/
[2] https://github.com/attic-labs/noms/blob/master/doc/intro.md#...
You just sent me into an small crisis wondering when that 2023 thing happened :D
However once you have chunks of fixed size (the maximum) instead of content-defined sizes, changes to the content become non-local: a change in one part of the data might change an arbitrary number of following chunks/nodes.
Did they find a solution to that? Did they ignore it?
However, from what I've seen, these methods generally come at the cost of deduplication and/or speed. The most reliable method to avoid pathological cases seems to just be setting the min/max chunk size to a low/high enough value respectively.
If you're talking in a purely theoretical sense, I would assume that the possibility of changes affecting non-local chunks is inherent to CDC. With well-chosen parameters the likelihood of any but the closest chunks being affected just becomes low enough to be negligible.
Here's a more recent write-up on chunking that details some of them, but it mostly comes down to using a better hash function, and having a fail-safe max chunk size for truly pathological cases.
https://www.dolthub.com/blog/2022-06-27-prolly-chunker/
Using hashes as links isn't cheap especially with sha-512 wide hashes (I think they use 20bytes in reality?). I'd estimate their fanout at between 50-200, which isn't that much either.
So my feeling is expensive nodes, combined with low-ish fanout => high cost of storage?