3 ms·

Prolly: A content-addressed ordered map built on prolly trees

56 points by forhappy 2mo ago

deleted 2mo ago
[deleted]
forhappy 2mo ago
I’ve been working on Prolly, a Rust implementation of a content-addressed ordered map built on prolly tree(intro from dolthub https://www.dolthub.com/docs/architecture/storage-engine/prolly-tree/ https://www.dolthub.com/docs/architecture/storage-engine/pro...) A prolly tree is similar to a B+ tree, but its node boundaries are determined by the data rather than by insertion order. Each node is addressed by the hash of its contents, and updates create a new root while sharing unchanged nodes with older versions. This makes it useful when an application needs more than basic key/value storage: cheap snapshots, efficient diffs, three-way merges, deduplication, and incremental sync between replicas. Some use cases I’m exploring include local-first applications, versioned database indexes, Git-like filesystem snapshots, agent memory and event logs, and reproducible RAG indexes where the exact data snapshot used for an answer can be recorded. It’s a storage primitive rather than a complete database. The goal is to provide the ordered-map layer and let applications choose their own storage backend, data model, and conflict policy. The project is still evolving, and I’d appreciate feedback—especially about real-world use cases, the API, and what is missing.
- lifty 2mo ago
  Great primitive, I’m a big fan of prolly trees! You mentioned git like filesystem snapshots? How would you retrofit that on an existing filesystem? Or you’re talking about writing a new one?
  - forhappy 2mo ago
    Thank you for your kind words, yes, I do have lots of ideas on top of prolly, actually I'm building some of them like crab(a serverless git remote, will be open-source soon), compass(a versioned code graph https://compass.crab.build/ https://compass.crab.build/), trail(a low-level version control tooling for AI agent https://github.com/crabbuild/trail https://github.com/crabbuild/trail) silo(a versioned S3 client to make S3-compatible bucket version-controllable https://github.com/crabbuild/silo https://github.com/crabbuild/silo) Prolly is a building block, there are sooo many use cases, I have the cookbook how developers can utilize prolly tree in their projects: https://github.com/crabbuild/prolly/blob/main/docs/cookbook.md https://github.com/crabbuild/prolly/blob/main/docs/cookbook....
- dtkav 2mo ago
  Thank you for sharing this. I've been looking into prolly trees for relay.md - I'll try swapping this in and see if i can provide any perspective for real world CRDT use cases. I'm happy to see the various key policies.
  - forhappy 2mo ago
    I'd be super happy to collaborate, let me know if you have any feedbacks ;)
rfgplk 2mo ago
Is there any reason why you only target sse2 for simd acceleration? You're leaving a lot of performance on the table.
- forhappy 2mo ago
  [dead]
deleted 2mo ago
[deleted]
iamwil 2mo ago
This is pretty neat. How long did it take for you to implement the core basics? Upon insertion do you incrementally build the tree, or do you rebuild it from scratch? How did you ensure the distribution of nodes was about the same with the chunker?
- forhappy 2mo ago
  I started learning and implementing the prolly tree since December 2025, the current one crabbuild/prolly might be the 4th or 5th prolly tree implementation ;)
  - iamwil 2mo ago
    That's great. I spent the majority of my time at the Recurse Center doing a first implementation. The full rebuild version of an insert is trivial. The incremental version took most of the time.
ferrow 2mo ago
[flagged]
conartist6 2mo ago
I'm working on a similar prolly implementation, but for Javascript. I just used the JS splice() contract for the main API abstraction. It maps perfectly onto prolly trees since it already allows bulk insertion and deletion: https://github.com/bablr-lang/agast-helpers/blob/7225f30e5e5075199c806b001e1e329eb655027d/lib/tags.js#L720 https://github.com/bablr-lang/agast-helpers/blob/7225f30e5e5... Prolly trees have some funky properties too, for example deleting a value from a prolly tree can cause it to end up having more nodes than it started with..!! (So too can inserting a value result in fewer tree nodes)
- conartist6 2mo ago
  Actually the insertion and deletion quirk may just be my trees because I do the probabilistic splitting between values rather than on them as usual
  - deleted 2mo ago
    [deleted]
  - whizzter 2mo ago
    Dolt had an interesting article on the subject, basically to get it more reliable in terms of similar size distribution they basically had a split threshhold function that shrunk by the current size, i did a bit of experimentation with statistics collection on a similar splitter and it was a bit of fiddling to get right in terms of how it should behave but it seemed to be possible to tune to specific block sizes.
    - conartist6 1mo ago
      Yeah I've read that article many times. I don't have such a mechanism at the moment. I'm not sure if I will until I run some of my own experiments. I also have much smaller nodes than Dolt generally, and where they only hash keys to balance the tree, I also allow the value to influence the tree structure.
timsehn 2mo ago
I’m the author of the linked Prolly Tree article and I launched a prolly tree visualizer last week. Conveniently: https://www.prollytree.com https://www.prollytree.com
- forhappy 2mo ago
  Your articles taught me all the prolly tree knowledge, thank you so much :)

56 points by forhappy 2mo ago

deleted 2mo ago

[deleted]

I’ve been working on Prolly, a Rust implementation of a content-addressed ordered map built on prolly tree(intro from dolthub https://www.dolthub.com/docs/architecture/storage-engine/prolly-tree/ https://www.dolthub.com/docs/architecture/storage-engine/pro...) A prolly tree is similar to a B+ tree, but its node boundaries are determined by the data rather than by insertion order. Each node is addressed by the hash of its contents, and updates create a new root while sharing unchanged nodes with older versions. This makes it useful when an application needs more than basic key/value storage: cheap snapshots, efficient diffs, three-way merges, deduplication, and incremental sync between replicas. Some use cases I’m exploring include local-first applications, versioned database indexes, Git-like filesystem snapshots, agent memory and event logs, and reproducible RAG indexes where the exact data snapshot used for an answer can be recorded. It’s a storage primitive rather than a complete database. The goal is to provide the ordered-map layer and let applications choose their own storage backend, data model, and conflict policy. The project is still evolving, and I’d appreciate feedback—especially about real-world use cases, the API, and what is missing.

lifty 2mo ago
Great primitive, I’m a big fan of prolly trees! You mentioned git like filesystem snapshots? How would you retrofit that on an existing filesystem? Or you’re talking about writing a new one?
- forhappy 2mo ago
  Thank you for your kind words, yes, I do have lots of ideas on top of prolly, actually I'm building some of them like crab(a serverless git remote, will be open-source soon), compass(a versioned code graph https://compass.crab.build/ https://compass.crab.build/), trail(a low-level version control tooling for AI agent https://github.com/crabbuild/trail https://github.com/crabbuild/trail) silo(a versioned S3 client to make S3-compatible bucket version-controllable https://github.com/crabbuild/silo https://github.com/crabbuild/silo) Prolly is a building block, there are sooo many use cases, I have the cookbook how developers can utilize prolly tree in their projects: https://github.com/crabbuild/prolly/blob/main/docs/cookbook.md https://github.com/crabbuild/prolly/blob/main/docs/cookbook....
dtkav 2mo ago
Thank you for sharing this. I've been looking into prolly trees for relay.md - I'll try swapping this in and see if i can provide any perspective for real world CRDT use cases. I'm happy to see the various key policies.
- forhappy 2mo ago
  I'd be super happy to collaborate, let me know if you have any feedbacks ;)

rfgplk 2mo ago

Is there any reason why you only target sse2 for simd acceleration? You're leaving a lot of performance on the table.

forhappy 2mo ago
[dead]

deleted 2mo ago

[deleted]

iamwil 2mo ago

This is pretty neat. How long did it take for you to implement the core basics? Upon insertion do you incrementally build the tree, or do you rebuild it from scratch? How did you ensure the distribution of nodes was about the same with the chunker?

forhappy 2mo ago
I started learning and implementing the prolly tree since December 2025, the current one crabbuild/prolly might be the 4th or 5th prolly tree implementation ;)
- iamwil 2mo ago
  That's great. I spent the majority of my time at the Recurse Center doing a first implementation. The full rebuild version of an insert is trivial. The incremental version took most of the time.

ferrow 2mo ago

[flagged]

conartist6 2mo ago

I'm working on a similar prolly implementation, but for Javascript. I just used the JS splice() contract for the main API abstraction. It maps perfectly onto prolly trees since it already allows bulk insertion and deletion: https://github.com/bablr-lang/agast-helpers/blob/7225f30e5e5075199c806b001e1e329eb655027d/lib/tags.js#L720 https://github.com/bablr-lang/agast-helpers/blob/7225f30e5e5... Prolly trees have some funky properties too, for example deleting a value from a prolly tree can cause it to end up having more nodes than it started with..!! (So too can inserting a value result in fewer tree nodes)

conartist6 2mo ago
Actually the insertion and deletion quirk may just be my trees because I do the probabilistic splitting between values rather than on them as usual
- deleted 2mo ago
  [deleted]
- whizzter 2mo ago
  Dolt had an interesting article on the subject, basically to get it more reliable in terms of similar size distribution they basically had a split threshhold function that shrunk by the current size, i did a bit of experimentation with statistics collection on a similar splitter and it was a bit of fiddling to get right in terms of how it should behave but it seemed to be possible to tune to specific block sizes.
  - conartist6 1mo ago
    Yeah I've read that article many times. I don't have such a mechanism at the moment. I'm not sure if I will until I run some of my own experiments. I also have much smaller nodes than Dolt generally, and where they only hash keys to balance the tree, I also allow the value to influence the tree structure.

timsehn 2mo ago

I’m the author of the linked Prolly Tree article and I launched a prolly tree visualizer last week. Conveniently: https://www.prollytree.com https://www.prollytree.com

forhappy 2mo ago
Your articles taught me all the prolly tree knowledge, thank you so much :)