How Dolt Stores Table Data (2020)(dolthub.com)
dolthub.com
How Dolt Stores Table Data (2020)
https://www.dolthub.com/blog/2020-04-01-how-dolt-stores-table-data/
3 comments
2020 you mean.
You just sent me into an small crisis wondering when that 2023 thing happened :D
You just sent me into an small crisis wondering when that 2023 thing happened :D
Me too :-)
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?
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.
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.
[deleted]
Yup, there are several solutions you can employ.
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/
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/
I wonder if the founders realise that "dolt" is slang for a "stupid person"?
So is “git” — that’s the joke.
I couldn't tell if it was an "L" or and "I", as in doIt.
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?
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?
[deleted]
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.
[1] https://github.com/attic-labs/
[2] https://github.com/attic-labs/noms/blob/master/doc/intro.md#...