How Dolt Stores Table Data (2020) | Hacker News Reader

How Dolt Stores Table Data (2020)

dolthub.com

35 pointsburntcaramel12 comments

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.

[1] https://github.com/attic-labs/

[2] https://github.com/attic-labs/noms/blob/master/doc/intro.md#...

2020 you mean.

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?

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.

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/

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?

Reply on news.ycombinator.com