Willow store

[rklaehn]

After a lot of discussion with Aljoscha last week I have decided to implement the willow store roughly as proposed in https://github.com/AljoschaMeyer/kv_3d_storage

TLDR: this has the upside that it is possible to quickly query 3d ranges, as well as (this is the point where it is superior to the radix tree) querying 3d ranges sorted by any of the 3 primary dimensions path, time and subspace.

The downside compared to the radix tree is that insertion requires roughly O(log n) path comparisons, and path comparisons itself are not constant time and can be expensive. Also, the paths are stored as a whole, unlike in a radix tree where they are prefix compressed. Prefix deletion will need a naive implementation where you just iterate and delete over everything below a prefix.

My current approach is to implement the tree query ops for a generic X, Y, Z (currently using u64 for testing), then implement insert and delete. Operations are tested using proptest property based testing.

I am currently working on this in a separate repository https://github.com/n0-computer/willow-store/tree/3d

Operations

• [x] summary(3drange)
  • [x] operation
  • [x] proptest
• [x] iterate_unordered(3drange)
  • [x] operation
  • [x] proptest
• [x] iterate_ordered(3drange, order) // order is xyz, yzx, zxy
  • [x] operation
  • [x] proptest
• [x] get
  • [x] operation
  • [x] proptest
• [x] batch build from vec
  • [x] operation
  • [x] proptest
• [x] insert (amortized log n with worst case n)
• [x] delete (amortized log n with worst case n)
• [ ] (stretch goal) tree merge
• [ ] (stretch goal) efficient retain like op

Plumbing

• [x] rank computation based on key
• [x] cheap (preferably zero copy) way to go from NodeData to db content
• [x] redb store impl

Docs

• [x] Data structure documented
• [x] Serialization format documented

[matheus23]

Prefix deletion will need a naive implementation where you just iterate and delete over everything below a prefix.

Doesn't this have to happen on every insert? I.e. prefix deletion is exactly the same as inserting a tombstone at a prefix?

[rklaehn]

Doesn't this have to happen on every insert? I.e. prefix deletion is exactly the same as inserting a tombstone at a prefix?

Not sure what you mean with the tombstone, but yes, every insert will mean a query for possibly affected child nodes, iterating over them, and deleting those that have to go.

~Two~three reasons for why this might not be quite as bad as it sounds:

• in many (most?) cases the node you insert will be a leaf, so the query will return zero affected elements
• for non-leaf queries initially will implement this as just iterate then delete, but longer term this can be done with a fn similar to retain that just filters the tree efficiently instead of deleting one by one
• when writing to a DB, it often almost does not matter that much how much you change, just how many times you have to call sync. Unless it is a really huge change. So maybe this won't be that bad.

[AljoschaMeyer]

Another thought to keep in mind about naive prefix deletion vs more efficient radix-tree-based implementations: notifying subscribers about deletions might turn this into an O(n) (for n deleted entries) anyways. O-notation might be less important here than actual running times, but still, could be helpful to keep this in mind from the start.