[HN Gopher] People Keep Inventing Prolly Trees
___________________________________________________________________
People Keep Inventing Prolly Trees
Author : lifty
Score : 169 points
Date : 2025-06-28 20:01 UTC (3 days ago)
(HTM) web link (www.dolthub.com)
(TXT) w3m dump (www.dolthub.com)
| compressedgas wrote:
| 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 wrote:
| Amazing! all these people reinvented my SuperMegaTree!
| aboodman wrote:
| 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#...
|
| 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.
| ChadNauseam wrote:
| 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.
| wakawaka28 wrote:
| 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.
| nicoburns wrote:
| Bittorrent is the protocol you're looking for. Unfortunately
| not widely adopted for the use cases you are talking about.
| theLiminator wrote:
| Sounds similar to IPFS.
| Retr0id wrote:
| > If you lose internet halfway through, the connection is
| closed and you're just screwed. [...] it would be nice if there
| was some protocol understood by browsers and web servers
|
| HTTP Range Requests solve this without any clever logic, if
| mutually supported.
| motorest wrote:
| > HTTP Range Requests solve this without any clever logic, if
| mutually supported.
|
| Understated comment in the thread.
|
| The very first search hit on Google is none other than
| Mozilla's page on ranged requests.
|
| https://developer.mozilla.org/en-
| US/docs/Web/HTTP/Guides/Ran...
|
| Here's the leading summary from that page.
|
| > _An HTTP Range request asks the server to send parts of a
| resource back to a client. Range requests are useful for
| various clients, including media players that support random
| access, data tools that require only part of a large file,
| and download managers that let users pause and resume a
| download._
|
| Here's a RFC:
|
| https://datatracker.ietf.org/doc/html/rfc7233
| RainyDayTmrw wrote:
| AES-GCM-SIV[1] does something similar to your per chunk derived
| key, except that AES-GCM-SIV expects the key to be user-
| provided, and the IV is synthetic - hence Synthetic IV mode.
|
| What's your threat model? This has "interesting"[3] properties.
| For example, given a file, the provider can figure out who has
| the file. Or, given a file, an arbitrary user can figure out if
| some other user already has the file. Users may even be able to
| "teleport" files to each other, like the infamous Dropbox
| Dropship[2].
|
| I suspect why no one has tried this is many-fold: (1) Most
| providers want to store plaintext. Those few providers who
| don't want to store plaintext, whether for secrecy or
| deniability reasons, also don't want to store anything else
| correlatable, either. (2) Space is cheap. (3) Providers like
| being able to charge for space. Since providers sell space at a
| markup, they almost want you to use more space, not less.
|
| [1]: https://en.wikipedia.org/wiki/AES-GCM-SIV [2]:
| https://en.wikipedia.org/wiki/Dropship_(software) [3]:
| "Interesting" is not a word you want associated with your
| cryptography usage, to say the least.
| 1vuio0pswjnm7 wrote:
| "Tangent: why is it that downloading a large file is such a bad
| experience on the internet?"
|
| This comment could only come from someone who never downloaded
| large files from the internet in the 1990s.
|
| Feels like heaven to me downloading today.
|
| Watching video from YouTube, Facebook, etc., if accessed via
| those websites running their Javascripts, usually uses the
| Range header. Some people refer to the "breeak up and re-
| assembly" as "progressive download".
| HelloNurse wrote:
| Adding tangent to tangent, I recently experienced an
| unexpected modern counterpart of a 1990s large download:
| deleting about 120K emails from a GMail folder, then purging
| them for real by "emptying" the GMail "trash bin".
|
| The first phase was severely asynchronous, with a popup
| mentioning "the next few minutes", which turned out to be
| hours. Manually refreshing the page showed a cringeworthy
| deletion rate of about 500 messages per minute.
|
| But at least it worked; the second phase was more special,
| with plenty of arbitrary stopping and outright lies. After
| repeated purging attempts I finally got an empty bin
| achievement page on my phone but I found over 50K messages in
| the trash on my computer the next day, where every attempt to
| empty the trash showed a very slow progress dialog that
| reported completion but actually deleted only about 4K
| messages.
|
| I don't expect many JavaScript card castles of the complexity
| of GMail message handling to be tested on large jobs; at
| least old FTP and web servers were designed with high load
| and large files in mind.
| zokier wrote:
| Video streaming usually uses something like DASH/HLS and is
| fair bit more complicated than Range headers. Notably this
| means that downloading the video means reversing the
| streaming format and glueing the segments together.
| 1vuio0pswjnm7 wrote:
| In recent times, large video files could often be
| downloaded in the popular browsers by changing a URL path
| parameter like "r=1234567" to "r=0". I have downloaded many
| large videos that way.
|
| DASH is used sometimes, but not on the majority of videos I
| encounter. Of course this can change over time. The point
| is that downloading large files today, e.g., from YouTube,
| Facebook, etc., cf. downloading large files in the 90s
| where speeds were slower and interruptions were more
| common, has been relatively fast and easy by comparison,
| even though these websites might be changing how they serve
| these files behind the scenes and software developers
| gravitate toward complexity.
|
| Commercial "streaming", e.g., ESPN, etc., might be
| intentionally difficult to download and might involve
| "reversing" and "glueing" but that is not what I'm
| describing.
| vanderZwan wrote:
| > _the dat paper_
|
| What's the name of the paper you're alluding to? I'm not
| familiar with it and it sounds interesting
| aboodman wrote:
| https://github.com/dat-ecosystem-
| archive/whitepaper/blob/mas...
| vanderZwan wrote:
| Thank you!
| layer8 wrote:
| > This would let the server provider deduplicate those files
| (saving space), without giving the server provider the ability
| to read the files.
|
| This gives the service provider the ability to see who is
| storing the same files, however, which can be sensitive
| information. Moreover, once they know/decrypt a file for one
| user, they know that file for all users.
| rakoo wrote:
| It does sound similar to ideas in Tahoe-LAFS: https://tahoe-
| lafs.readthedocs.io/en/latest/architecture.htm...
|
| Which has already thought about attacks on the scheme you
| described: https://tahoe-
| lafs.org/hacktahoelafs/drew_perttula.html
| iamwil wrote:
| 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 wrote:
| 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 wrote:
| That's what I figured, and answers my question.
| gritzko wrote:
| 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/
|
| [r]: https://github.com/gritzko/librdx
|
| [d]: https://github.com/gritzko/go-rdx/blob/main/DISCOUNT.md
|
| [h]: https://www.inkandswitch.com/keyhive/notebook/05/
|
| [c]: https://dl.acm.org/doi/10.1145/1832772.1832777
|
| [a]: https://pages.lip6.fr/Marc.Shapiro/papers/RR-7687.pdf links
| to the authors of RGA
| lifty wrote:
| 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 wrote:
| 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 wrote:
| What the hell does "probabilistically balanced" mean?
| moomin wrote:
| It means the balancing is content-dependent, and is normally
| balanced, but certain edge-case inputs may result in sub-
| optimal behaviour.
| zombot wrote:
| What is probabilistic about that? It sounds deterministic.
| mcherm wrote:
| 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 wrote:
| It's a term of art. We say the same thing about quicksort
| being "usually" O(n log n)
| judofyr wrote:
| 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.
| stonemetal12 wrote:
| Like quicksort is O(N log N) on average but can degrade to
| O(N^2) in the worse case. The tree is balanced on average,
| but can degrade to not close to balanced in the worst case.
| wmanley wrote:
| Here's apenwarr's description of the same data structure from
| 2009: 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/ .
| 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.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 ). Why not
| treat the 'chunk' as the fundamental unit, and compose files from
| chunks?
| elric wrote:
| 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 wrote:
| 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/blob/master/data-stru...
| But it's a lot of work and I didn't update it for a while.
| hiAndrewQuinn wrote:
| 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 wrote:
| 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 wrote:
| > _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.
| jerf wrote:
| 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 wrote:
| 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 wrote:
| 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
___________________________________________________________________
(page generated 2025-07-01 23:02 UTC)