prollipop 🍭

A modded Prolly-tree implementation in Typescript.

Features

• Async-iterable mutator - changes can be applied as a stream :o
• Efficient diff - yields node and bucket diffs!
• Powerful cursor api - climb 🌳s like a pro

Project Status

I AM REWRITING THE MUTATOR AND TESTS AFTER FINDING SOME BUGS.

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. Need to add abort signals and timeouts.

Data-structure

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

mods:

• (number, uint8array) tuples for keys
• right-side backbone
• key-defined, normalized boundaries instead of rolling-hash

Install

npm install prollipop

Build

pnpm install && pnpm build

Usage

See usage.test.ts!!!

API docs

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

• Range-Based Set Reconciliation

  • author: Doug Hoyte
  • relevance: Negantrophy section uses [number, hash] tuples as keys

Additional Resources:

• https://github.com/ipld/ipld/blob/prolly-trees/specs/advanced-data-layouts/prollytree/spec.md
• https://github.com/mikeal/prolly-trees