prollipop 🍭

A modded Prolly-tree implementation in Typescript.

Features

• Efficient diff - yields entry and bucket diffs!
• Powerful cursor api - climb 🌳s like a pro
• Structural validation - codec is aware of tree context

Project Status

It's in a decent state but have not done performance analysis. API breaks will result in major version change.

I haven't tested with non-local blockstores. Things may not work well with networked blockstores.

Data-structure

This package implements a modded prolly-tree in Typescript. Most relevant code is in src/mutate.ts and src/diff.ts.

mods:

• right-side backbone
• key-defined boundaries instead of rolling-hash

Install

npm install prollipop

Build

pnpm install && pnpm build

Usage

See usage.test.ts!!!

API docs

Example database

Learning Resources:

As you can see from the list below, a lot of ideas have been stolen from the Dolt project's blog so be sure to check them out!

• Prolly Trees

  • author: Tim Sehn
  • implementation: dolt
  • relevance: great introduction to prolly-trees

• Prolly Tree PoC and technical writeup

  • author: ABresting
  • implementation: Prolly-tree-Waku-Message
  • relevance: Custom implementation of prolly-tree with right side backbone

• Merklizing the key/value store for fun and profit

  • author: Joel Gustafson
  • implementation: okra-js
  • relevance: content-defined merkle trees: A node is the first child of its parent if u32(node.hash[0..4]) < (2^32 / Q).

• Efficient Diff on Prolly-trees

  • author: Aaron Son
  • implementation: dolt
  • relevance: excellent visual examples for prolly-tree diffs

• Only Consider Keys

  • author: Tim Sehn
  • implementation: dolt
  • relevance: only consider keys for chunk boundary, not keys + values

Additional Resources:

• https://github.com/canvasxyz/okra?tab=readme-ov-file#design
• https://github.com/ipld/ipld/blob/prolly-trees/specs/advanced-data-layouts/prollytree/spec.md
• https://github.com/mikeal/prolly-trees