The Prolly Tree Finally Escapes the Database

Prolly trees have a strange history: they may be the most independently reinvented data structure of the last two decades, yet you've probably never called one directly. Avery Pennarun's bup backup tool built one without naming it in 2009. The Noms team at Attic Labs coined the term in 2015. Inria researchers rediscovered the idea as "Merkle Search Trees" in 2019, and a DePaul group did it again in 2020 as "Content-Defined Merkle Trees." Each time, the structure got buried inside a product — Dolt's version-controlled SQL database, Bluesky's AT Protocol repositories, XetHub's dedup layer that Hugging Face now uses to store model weights.

Prolly, a Rust crate that hit the Hacker News front page this week, makes a different bet: ship the data structure itself, the way you'd grab a B-tree or an LSM engine off the shelf. That's the actually interesting part of this release — not the tree, which is well-trodden by now, but the packaging.

Why this structure keeps getting reinvented

A prolly tree is what you get when you build a B-tree but pick node boundaries with a rolling hash over the content instead of by fill factor, then address every node by the hash of its bytes. Three properties fall out. The tree is history-independent: the same key-value pairs produce byte-identical trees no matter what order you inserted them in, so two replicas that converge on the same data converge on the same root hash. Diffing two versions costs time proportional to the size of the difference, not the size of the data, because identical subtrees share identical hashes and can be skipped wholesale. And "snapshot" becomes a pointer copy — old roots keep working, and unchanged chunks are shared between versions.

That combination is exactly what you want for versioned data, sync protocols, and verifiable reads, which is why four separate groups arrived at it independently. Dolt's engineers wrote a whole essay series about the phenomenon last year, arguing the structure is the inevitable next step once Merkle trees and content-defined chunking exist in the same brain. The demand is real; the problem has been that every implementation was welded to its host system. If you wanted prolly-tree semantics in your own app, your options were embedding an entire SQL database, adopting a federated social protocol, or writing one from scratch — and people demonstrably kept choosing "from scratch."

What the crate actually gives you

Prolly (published as prolly-map, currently v0.7.0) exposes an immutable ordered map over byte keys. Every mutation rewrites only the touched path and hands you a new Tree handle — a root CID plus chunking config — while nodes live in a pluggable store. Node identity is the SHA-256 of deterministic node bytes; chunk boundaries come from xxHash64 content-defined chunking. On top of that base it layers the operations that make the structure worth having: structural diff, three-way merge with pluggable conflict resolution, CRDT-style merge strategies, and Merkle proofs that let a client verify a key, range, or prefix against a root hash without trusting the server that answered the query.

The store abstraction is where the local-first use case gets concrete. A memory store and SQLite store are built in, RocksDB is optional, and async adapters exist for Postgres, Redis, Turso, DynamoDB, and others. Because structure is content-derived, a client and server holding different versions can exchange just the chunks whose hashes differ — sync as set-reconciliation over CIDs rather than an operation log. For agent event logs, versioned config, or offline-first document stores, that's a primitive you currently have to hand-roll or borrow from a much bigger system.

The caveats are real

Now the skeptical read. This is a pre-1.0 crate from a pseudonymous org, with a modest star count and — per its own README — serialization formats still subject to breaking changes. And the surface area is enormous for something this young: seven-plus database backends, WASM and UniFFI bindings, HMAC-enveloped proof bundles, a GlueSQL integration, even approximate-nearest-neighbor indexing for vector workloads. Mature storage libraries earn that breadth over years; here it reads like scope arriving faster than hardening. The parts of a storage engine that hurt — compaction, garbage collection of unreachable chunks, pathological chunking distributions — are exactly the parts Dolt spent years tuning (their big contribution over Noms was reshaping chunk-size variance, which the original rolling-hash formulation gets badly wrong). None of that is disqualifying, but it's the difference between a great primitive and a production dependency.

There are also inherent trade-offs no implementation escapes. Writes pay a chunking tax over a plain B-tree. Immutability means every update allocates new nodes, so without a GC story your store only grows. And the HN thread surfaced a fun sharp edge from a parallel JavaScript implementation: deleting a key can leave you with more nodes than you started with, because boundaries shift.

Where this lands

My take: the primitive graduating to library status is the genuinely significant part, and it was overdue — the reinvention count proves the demand. If you're building local-first sync, versioned agent memory, or anything that needs cheap snapshots and verifiable reads, prolly trees are very likely the right shape, and this crate is now the lowest-friction way to try them in Rust: cargo add prolly-map, start with the SQLite store, and treat the diff/merge/proof core as the product. What I wouldn't do yet is bet a production system on the long tail of features, or on format stability before 1.0. Pin your version, plan for a migration, and watch whether the project narrows its focus — that, more than the star count, will tell you if this becomes the sled of versioned data or the fifth group to invent a prolly tree and the first to abandon one in public.