4 ms·

People Keep Inventing Prolly Trees

191 points by lifty 1y ago

deleted 1y ago
[deleted]
compressedgas 1y ago
This article does not mention Jumbostore (Kave Eshghi, Mark Lillibridge, Lawrence Wilcock, Guillaume Belrose, and Rycharde Hawkes) which used content defined chunking recursively on the chunk list of a content defined chunked file in 2007. This is exactly what a Prolly Tree is.
- lawlessone 1y ago
  Amazing! all these people reinvented my SuperMegaTree!
- aboodman 1y ago
  I was aware of this kind of structure when I coined 'prolly tree'. It's the same thing bup was doing, which I referenced in our design docs: https://github.com/attic-labs/noms/blob/master/doc/intro.md#basics https://github.com/attic-labs/noms/blob/master/doc/intro.md#... The reason I thought a new name was warranted is that a prolly tree stores structured data (a sorted set of k/v pairs, like a b-tree), not blob data. And it has the same interface and utility as a b-tree. Is it a huge difference? No. A pretty minor adaptation of an existing idea. But still different enough to warrant a different name IMO.
  - compressedgas 1y ago
    My use of "exactly" was an overstatement. The important difference is that internal nodes in a prolly tree contain not only the hashes of the child nodes but also the index keys as is done in a B-tree. The divisions at each level however similarly are decided by the application of content defined chunking method to the entire level of the tree.
ChadNauseam 1y ago
Haha, this is funny. I've been obsessed with rolling-hash based chunking since I read about it in the dat paper. I didn't realize there was a tree version, but it is a natural extension. I have a related cryptosystem that I came up with, but is so obvious I'm sure someone else has invented it first. The idea is to back up a file like so: first, do a rolling-hash based chunking, then encrypt each chunk where the key is the hash of that chunk. Then, upload the chunks to the server, along with a file (encrypted by your personal key) that contains the information needed to decrypt each chunk and reassemble them. If multiple users used this strategy, any files they have in common would result in the same chunks being uploaded. This would let the server provider deduplicate those files (saving space), without giving the server provider the ability to read the files. (Unless they already know exactly which file they're looking for, and just want to test whether you're storing it.) Tangent: why is it that downloading a large file is such a bad experience on the internet? If you lose internet halfway through, the connection is closed and you're just screwed. I don't think it should be a requirement, but it would be nice if there was some protocol understood by browsers and web servers that would be able to break-up and re-assemble a download request into a prolly tree, so I could pick up downloading where I left off, or only download what changed since the last time I downloaded something.
- nicoburns 1y ago
  Bittorrent is the protocol you're looking for. Unfortunately not widely adopted for the use cases you are talking about.
- wakawaka28 1y ago
  I think the cost of processing stuff that way would far exceed the cost of downloading the entire file again. You can already resume downloads from a byte offset if the server supports it, and that probably covers 99% of the cases where you would actually want to resume a download of a single file. Partial updates are rarely possible for large files anyway, as they are often compressed. If the host wants to make partial updates make sense then they could serve over rsync.
- theLiminator 1y ago
  Sounds similar to IPFS.
iamwil 1y ago
Anyone know if editing a prolly tree requires reconstructing the entire tree from the leaves again? All the examples I've ever seen in a wild reconstruct from the bottom up. Presumably, you can leave the untouched leaves intact, and the reconstruct parent nodes whose hashes have changed due to the changed leaves. I ended up doing an implementation of this, and wondered if it's of any interest or value to others?
- aboodman 1y ago
  I am confused by this question. Both noms and dolt, and presumably most other prolly tree implementations do what you propose. if they didn't, inserts would be terribly slow.
  - iamwil 1y ago
    That’s what I figured, and answers my question.
gritzko 1y ago
Prolly Trees are Merkle-fied B-trees, essentially. I am working on related things[r], using Merkle-fied LSM trees. Ink&Switch do things that very closely resemble Merklefied LSM[h], although they are not exactly LSM. I would not be surprised if someone else is doing something similar in parallel. The tricks are very similar to Prollies, but LSM instead of B-trees. That reminds me my younger years when I "invented" the Causal Tree[c] data structure. It was later reinvented as RGA (Replicated Growable Array [a]), Timestamped Insertion Tree and, I believe, YATA. All seem to be variations of a very very old revision control data structure named "weave"[w]. Recently I improved CT to the degree that warranted a new algorithm name (DISCONT [d]). Fundamentally the same, but much cheaper. Probably, we should see all these "inventions" as improvements. All the Computer Science basics seem to have been invented in the 70s, 80s the latest. [w]: https://docs.rs/weave/latest/weave/ https://docs.rs/weave/latest/weave/ [r]: https://github.com/gritzko/librdx https://github.com/gritzko/librdx [d]: https://github.com/gritzko/go-rdx/blob/main/DISCOUNT.md https://github.com/gritzko/go-rdx/blob/main/DISCOUNT.md [h]: https://www.inkandswitch.com/keyhive/notebook/05/ https://www.inkandswitch.com/keyhive/notebook/05/ [c]: https://dl.acm.org/doi/10.1145/1832772.1832777 https://dl.acm.org/doi/10.1145/1832772.1832777 [a]: https://pages.lip6.fr/Marc.Shapiro/papers/RR-7687.pdf https://pages.lip6.fr/Marc.Shapiro/papers/RR-7687.pdf links to the authors of RGA
- lifty 1y ago
  This is the first time I hear about librdx and Chotki, very cool projects. I skimmed over both projects but I haven't seen much written about conflict resolution. Does it mean that last write wins based on version vectors?
  - gritzko 1y ago
    I am a (co)author. Conflict resolution is CRDT in all cases. FIRST (Float Int Reference String Term): Last-Write-Wins based on the timestamp, PLEX: - Tuples: per-entry LWW or recursive, - Linear: DISCONT (CT/RGA type), - Eulerian: per-key LWW or recursive, - Multiplexed (version vectors, counters): per-author LWW or recursive.
zombot 1y ago
What the hell does "probabilistically balanced" mean?
- timsehn 1y ago
  We actually wrote another blog about this because I had the same question. I am the CEO of DoltHub so I can have my engineers write stuff to explain it to me :-) https://www.dolthub.com/blog/2025-06-26-prolly-tree-balance/ https://www.dolthub.com/blog/2025-06-26-prolly-tree-balance/
- moomin 1y ago
  It means the balancing is content-dependent, and is normally balanced, but certain edge-case inputs may result in sub-optimal behaviour.
  - zombot 1y ago
    What is probabilistic about that? It sounds deterministic.
    - mcherm 1y ago
      The specific behavior of the hash function (including the salt you chose). Choosing a different hash function (or a different salt) would result in a different breakdown into chunks. In principle, if your data were specially crafted to exploit the specific hash function (and salt) you could get an aberrant case like 1 million entries in a single b-tree node or a million b-tree nodes with just one entry. But unless you intentionally exploit the hash function the chance of this is vanishingly small.
    - moomin 1y ago
      It's a term of art. We say the same thing about quicksort being "usually" O(n log n)
    - judofyr 1y ago
      The opposite of probabilistic is not deterministic in this context. This is not about «drawing a random number», but rather that balancing is dependent on the input data. «With high probability» here means «majority of the possible input data leads to a balanced structure». If it was not probabilistic then the balancing would be guaranteed in all cases. This typically means that it somehow stores balancing information somewhere so that it can detect when something is unbalanced and repair it. In this data structure we’re just hashing the content without really caring about the current balance and then it turns out that for most inputs it will be fine.
wmanley 1y ago
Here's apenwarr's description of the same data structure from 2009: https://apenwarr.ca/log/20091004 https://apenwarr.ca/log/20091004 . Here's a post to the git mailing list from Martin Uecker describing the same from 2005: https://lore.kernel.org/git/20050416173702.GA12605@macavity/ https://lore.kernel.org/git/20050416173702.GA12605@macavity/ . From the tone of the email it sounds like he didn't consider the idea new at that point: > The chunk boundaries should be determined deterministically from local properties of the data. Use a rolling checksum over some small window and split the file it it hits a special value (0). This is what the rsyncable patch to zlib does. He calls it a merkle hash tree. Edit: here's one that's one day earlier from C. Scott Ananian: https://lore.kernel.org/git/Pine.LNX.4.61.0504151232160.27637@cag.csail.mit.edu/ https://lore.kernel.org/git/Pine.LNX.4.61.0504151232160.2763... > We already have the rsync algorithm which can scan through a file and efficiently tell which existing chunks match (portions of) it, using a rolling checksum. (Here's a refresher: http://samba.anu.edu.au/rsync/tech_report/node2.html http://samba.anu.edu.au/rsync/tech_report/node2.html ). Why not treat the 'chunk' as the fundamental unit, and compose files from chunks?
elric 1y ago
How do people find specialised data structure that they aren't already aware of? Stumbling across random blog posts and reading the odd book on data structures can't be the optimal way. Is there a way to search for a structure by properties? E.g. O(1) lookups, O(log(n)) inserts or better, navigates like a tree (just making this up), etc?
- Loranubi 1y ago
  I was trying to catalog them at some point in a reasonably structured way https://github.com/Dobatymo/data-algos/ https://github.com/Dobatymo/data-algos/ https://github.com/Dobatymo/data-algos/blob/master/data-structures.md https://github.com/Dobatymo/data-algos/blob/master/data-stru... But it's a lot of work and I didn't update it for a while.
- hiAndrewQuinn 1y ago
  My understanding is you basically just bash your head against the problem for long enough, and simultaneously have enough of a grounding in the fundamentals, that you just start to come up with it as the obvious next thing. In other words, there's no trick to it, just expertise, hard work, and an eye for what's relevant and what's irrelevant in the problem.
donatj 1y ago
It would probably help if they had a Wikipedia page. Someone who actually understands what they are should get on that. Googling "Prolly Trees", there's not much and this article is one of the top results.
inetknght 1y ago
> Sometimes an invention is not widely known because its creator doesn't realize they've created something novel: the design seemed obvious and intuitive to them. I never went to high school or college or anything. I can't tell you how many times I come up with something, only to discover years later that someone else came up with the same idea later (or sometimes earlier), branded it, and marketed it.
deleted 1y ago
[deleted]
jerf 1y ago
I kind of like data structures, because when you study them, and take them apart, and understand their pieces, rather than seeing the world as Prolly Trees here and Binary Trees there and Bloom Filters over there, you see a whole bunch of little tricks you can use, and when you collect a reasonably large bag of those tricks you can put them together in all sorts of ways. It's almost a pity computers are as fast as they are and they are so rarely needed because having "arrays" and "maps/dicts/associative arrays/whatever" solves so many problems so much faster than we need anyhow. I don't get to pull out the bag of tricks very often. But then again, when I do, it's because it's a life saver and the difference between success and failure, so maybe it all balances out.
- shadowgovt 1y ago
  It's fun to go look at the actual implementation of those primitives in languages and libraries and see how complex they can be under the hood. Some of them incorporate two or three algorithms and switch them on the fly based on profiling the incoming data. I remember being startled to learn that Cocoa's "NSString" supports ropes, caching of transforms, and I think even some translation primitives, all quietly switching on and off as needed. Developers have less control over the particulars (and may miss optimization opportunities if they can make guarantees about the shape of the problem) but it benefits the common case.
guywithahat 1y ago
One things an exec said at my old job I liked was “research is generally ~5-10 years behind industry”, and I see that seems to still be the case for prolly trees

191 points by lifty 1y ago

deleted 1y ago

[deleted]

This article does not mention Jumbostore (Kave Eshghi, Mark Lillibridge, Lawrence Wilcock, Guillaume Belrose, and Rycharde Hawkes) which used content defined chunking recursively on the chunk list of a content defined chunked file in 2007. This is exactly what a Prolly Tree is.

lawlessone 1y ago
Amazing! all these people reinvented my SuperMegaTree!
aboodman 1y ago
I was aware of this kind of structure when I coined 'prolly tree'. It's the same thing bup was doing, which I referenced in our design docs: https://github.com/attic-labs/noms/blob/master/doc/intro.md#basics https://github.com/attic-labs/noms/blob/master/doc/intro.md#... The reason I thought a new name was warranted is that a prolly tree stores structured data (a sorted set of k/v pairs, like a b-tree), not blob data. And it has the same interface and utility as a b-tree. Is it a huge difference? No. A pretty minor adaptation of an existing idea. But still different enough to warrant a different name IMO.
- compressedgas 1y ago
  My use of "exactly" was an overstatement. The important difference is that internal nodes in a prolly tree contain not only the hashes of the child nodes but also the index keys as is done in a B-tree. The divisions at each level however similarly are decided by the application of content defined chunking method to the entire level of the tree.

ChadNauseam 1y ago

Haha, this is funny. I've been obsessed with rolling-hash based chunking since I read about it in the dat paper. I didn't realize there was a tree version, but it is a natural extension. I have a related cryptosystem that I came up with, but is so obvious I'm sure someone else has invented it first. The idea is to back up a file like so: first, do a rolling-hash based chunking, then encrypt each chunk where the key is the hash of that chunk. Then, upload the chunks to the server, along with a file (encrypted by your personal key) that contains the information needed to decrypt each chunk and reassemble them. If multiple users used this strategy, any files they have in common would result in the same chunks being uploaded. This would let the server provider deduplicate those files (saving space), without giving the server provider the ability to read the files. (Unless they already know exactly which file they're looking for, and just want to test whether you're storing it.) Tangent: why is it that downloading a large file is such a bad experience on the internet? If you lose internet halfway through, the connection is closed and you're just screwed. I don't think it should be a requirement, but it would be nice if there was some protocol understood by browsers and web servers that would be able to break-up and re-assemble a download request into a prolly tree, so I could pick up downloading where I left off, or only download what changed since the last time I downloaded something.

nicoburns 1y ago
Bittorrent is the protocol you're looking for. Unfortunately not widely adopted for the use cases you are talking about.
wakawaka28 1y ago
I think the cost of processing stuff that way would far exceed the cost of downloading the entire file again. You can already resume downloads from a byte offset if the server supports it, and that probably covers 99% of the cases where you would actually want to resume a download of a single file. Partial updates are rarely possible for large files anyway, as they are often compressed. If the host wants to make partial updates make sense then they could serve over rsync.
theLiminator 1y ago
Sounds similar to IPFS.

iamwil 1y ago

Anyone know if editing a prolly tree requires reconstructing the entire tree from the leaves again? All the examples I've ever seen in a wild reconstruct from the bottom up. Presumably, you can leave the untouched leaves intact, and the reconstruct parent nodes whose hashes have changed due to the changed leaves. I ended up doing an implementation of this, and wondered if it's of any interest or value to others?

aboodman 1y ago
I am confused by this question. Both noms and dolt, and presumably most other prolly tree implementations do what you propose. if they didn't, inserts would be terribly slow.
- iamwil 1y ago
  That’s what I figured, and answers my question.

gritzko 1y ago

Prolly Trees are Merkle-fied B-trees, essentially. I am working on related things[r], using Merkle-fied LSM trees. Ink&Switch do things that very closely resemble Merklefied LSM[h], although they are not exactly LSM. I would not be surprised if someone else is doing something similar in parallel. The tricks are very similar to Prollies, but LSM instead of B-trees. That reminds me my younger years when I "invented" the Causal Tree[c] data structure. It was later reinvented as RGA (Replicated Growable Array [a]), Timestamped Insertion Tree and, I believe, YATA. All seem to be variations of a very very old revision control data structure named "weave"[w]. Recently I improved CT to the degree that warranted a new algorithm name (DISCONT [d]). Fundamentally the same, but much cheaper. Probably, we should see all these "inventions" as improvements. All the Computer Science basics seem to have been invented in the 70s, 80s the latest. [w]: https://docs.rs/weave/latest/weave/ https://docs.rs/weave/latest/weave/ [r]: https://github.com/gritzko/librdx https://github.com/gritzko/librdx [d]: https://github.com/gritzko/go-rdx/blob/main/DISCOUNT.md https://github.com/gritzko/go-rdx/blob/main/DISCOUNT.md [h]: https://www.inkandswitch.com/keyhive/notebook/05/ https://www.inkandswitch.com/keyhive/notebook/05/ [c]: https://dl.acm.org/doi/10.1145/1832772.1832777 https://dl.acm.org/doi/10.1145/1832772.1832777 [a]: https://pages.lip6.fr/Marc.Shapiro/papers/RR-7687.pdf https://pages.lip6.fr/Marc.Shapiro/papers/RR-7687.pdf links to the authors of RGA

lifty 1y ago
This is the first time I hear about librdx and Chotki, very cool projects. I skimmed over both projects but I haven't seen much written about conflict resolution. Does it mean that last write wins based on version vectors?
- gritzko 1y ago
  I am a (co)author. Conflict resolution is CRDT in all cases. FIRST (Float Int Reference String Term): Last-Write-Wins based on the timestamp, PLEX: - Tuples: per-entry LWW or recursive, - Linear: DISCONT (CT/RGA type), - Eulerian: per-key LWW or recursive, - Multiplexed (version vectors, counters): per-author LWW or recursive.

zombot 1y ago

What the hell does "probabilistically balanced" mean?

timsehn 1y ago
We actually wrote another blog about this because I had the same question. I am the CEO of DoltHub so I can have my engineers write stuff to explain it to me :-) https://www.dolthub.com/blog/2025-06-26-prolly-tree-balance/ https://www.dolthub.com/blog/2025-06-26-prolly-tree-balance/
moomin 1y ago
It means the balancing is content-dependent, and is normally balanced, but certain edge-case inputs may result in sub-optimal behaviour.
- zombot 1y ago
  What is probabilistic about that? It sounds deterministic.
  - mcherm 1y ago
    The specific behavior of the hash function (including the salt you chose). Choosing a different hash function (or a different salt) would result in a different breakdown into chunks. In principle, if your data were specially crafted to exploit the specific hash function (and salt) you could get an aberrant case like 1 million entries in a single b-tree node or a million b-tree nodes with just one entry. But unless you intentionally exploit the hash function the chance of this is vanishingly small.
  - moomin 1y ago
    It's a term of art. We say the same thing about quicksort being "usually" O(n log n)
  - judofyr 1y ago
    The opposite of probabilistic is not deterministic in this context. This is not about «drawing a random number», but rather that balancing is dependent on the input data. «With high probability» here means «majority of the possible input data leads to a balanced structure». If it was not probabilistic then the balancing would be guaranteed in all cases. This typically means that it somehow stores balancing information somewhere so that it can detect when something is unbalanced and repair it. In this data structure we’re just hashing the content without really caring about the current balance and then it turns out that for most inputs it will be fine.

wmanley 1y ago

Here's apenwarr's description of the same data structure from 2009: https://apenwarr.ca/log/20091004 https://apenwarr.ca/log/20091004 . Here's a post to the git mailing list from Martin Uecker describing the same from 2005: https://lore.kernel.org/git/20050416173702.GA12605@macavity/ https://lore.kernel.org/git/20050416173702.GA12605@macavity/ . From the tone of the email it sounds like he didn't consider the idea new at that point: > The chunk boundaries should be determined deterministically from local properties of the data. Use a rolling checksum over some small window and split the file it it hits a special value (0). This is what the rsyncable patch to zlib does. He calls it a merkle hash tree. Edit: here's one that's one day earlier from C. Scott Ananian: https://lore.kernel.org/git/Pine.LNX.4.61.0504151232160.27637@cag.csail.mit.edu/ https://lore.kernel.org/git/Pine.LNX.4.61.0504151232160.2763... > We already have the rsync algorithm which can scan through a file and efficiently tell which existing chunks match (portions of) it, using a rolling checksum. (Here's a refresher: http://samba.anu.edu.au/rsync/tech_report/node2.html http://samba.anu.edu.au/rsync/tech_report/node2.html ). Why not treat the 'chunk' as the fundamental unit, and compose files from chunks?

elric 1y ago

How do people find specialised data structure that they aren't already aware of? Stumbling across random blog posts and reading the odd book on data structures can't be the optimal way. Is there a way to search for a structure by properties? E.g. O(1) lookups, O(log(n)) inserts or better, navigates like a tree (just making this up), etc?

Loranubi 1y ago
I was trying to catalog them at some point in a reasonably structured way https://github.com/Dobatymo/data-algos/ https://github.com/Dobatymo/data-algos/ https://github.com/Dobatymo/data-algos/blob/master/data-structures.md https://github.com/Dobatymo/data-algos/blob/master/data-stru... But it's a lot of work and I didn't update it for a while.
hiAndrewQuinn 1y ago
My understanding is you basically just bash your head against the problem for long enough, and simultaneously have enough of a grounding in the fundamentals, that you just start to come up with it as the obvious next thing. In other words, there's no trick to it, just expertise, hard work, and an eye for what's relevant and what's irrelevant in the problem.

donatj 1y ago

It would probably help if they had a Wikipedia page. Someone who actually understands what they are should get on that. Googling "Prolly Trees", there's not much and this article is one of the top results.

inetknght 1y ago

> Sometimes an invention is not widely known because its creator doesn't realize they've created something novel: the design seemed obvious and intuitive to them. I never went to high school or college or anything. I can't tell you how many times I come up with something, only to discover years later that someone else came up with the same idea later (or sometimes earlier), branded it, and marketed it.

deleted 1y ago

[deleted]

jerf 1y ago

I kind of like data structures, because when you study them, and take them apart, and understand their pieces, rather than seeing the world as Prolly Trees here and Binary Trees there and Bloom Filters over there, you see a whole bunch of little tricks you can use, and when you collect a reasonably large bag of those tricks you can put them together in all sorts of ways. It's almost a pity computers are as fast as they are and they are so rarely needed because having "arrays" and "maps/dicts/associative arrays/whatever" solves so many problems so much faster than we need anyhow. I don't get to pull out the bag of tricks very often. But then again, when I do, it's because it's a life saver and the difference between success and failure, so maybe it all balances out.

shadowgovt 1y ago
It's fun to go look at the actual implementation of those primitives in languages and libraries and see how complex they can be under the hood. Some of them incorporate two or three algorithms and switch them on the fly based on profiling the incoming data. I remember being startled to learn that Cocoa's "NSString" supports ropes, caching of transforms, and I think even some translation primitives, all quietly switching on and off as needed. Developers have less control over the particulars (and may miss optimization opportunities if they can make guarantees about the shape of the problem) but it benefits the common case.

guywithahat 1y ago

One things an exec said at my old job I liked was “research is generally ~5-10 years behind industry”, and I see that seems to still be the case for prolly trees