How does this compare to other prolly trees implementations?

[2color]

How do Prollopop compare to Okra and other implementations mentioned in the README?

[tabcat]

Name	Language	HashFn	Boundary Rule	Key Format
Dolt	go	sha2-512 (truncated to 20 bytes)	stateful key based	string
Okra	typescript and zig	blake3 (configurable length)	stateless node based	byte array
Prollipop	typescript	sha2-256	stateless key/level based	(number, byte array) tuple

These are the core differences.

Dolt and Okra are also much more mature than Prollipop. I haven't done any performance testing so assume Prollipop is quite slow. Also need to add more checks around ingesting remote blocks to prevent crashes or fail early when dag structure is incorrectly built.

Have been thinking about switching to blake3. It seems like a good option longterm. Using Robin Berjon's ideas, so buckets, aka chunks, are just cbor objects hashed with sha2-256 that look like { level, average, nodes }.

Having (number, byte array)s as keys lets you control order of nodes in the tree. If you don't want order then the number can just be 0 for everything. It was based off waku-org/research#78 and I'll probably use it as "a persistence layer for operation-based CRDT systems". I assume Okra has this feature as well since they mention it.

Dolt uses a boundary rule that is based on the number of nodes in the bucket so far. It tightens the mean size of buckets. I chose not to add this as I didn't like what it did to the structure of the tree. Okra looks at the hash of the node and if the hash is below a certain threshold creates a boundary. I was reading https://docs.dolthub.com/architecture/storage-engine/prolly-tree#only-consider-keys and liked the benefits they mention of only reading the key. I think this works for Dolt when they are just looking at the key because of their CDF threshold. To do this without looking at the number of nodes in the bucket so far, I hash the key with the level of the bucket.

Okra also uses a different system to fetch nodes which I haven't fully looked into. Every node at every level is indexed inside of a NodeStore. This allows for fetching keys from level 0 directly it looks like. Prollipop is using a blockstore and has to traverse each level to find the bucket the node is contained in.

I'll update with anything else that comes to mind or is brought to my attention. I don't claim to be an expert on either Dolt or Okra so some information may be incorrect. I've done my best to link sources.

[tabcat]

Also Prollipop has a really powerful Cursor API that might not be all that useful beyond how it's used in mutate and diff lol