Merkelized BTree store

[ValarDragon]

Background

Building a Merkelized BTree store with a key value interface, parameterized for a target fan-in factor of 1024 or so, and large leaves bundled together will significantly help improve efficiency of features like generalized accumulation stores / Orderbooks.

Suggested Design

There are two reasons for merkelization:

• Light client queryability
• State sync ability / guaranteeing the same state across all nodes.

There is a lot of state that is made light client queryable that should not be. Right now we suffer high write overhead due to the merkelization and bad disk layout of IAVL / binary search trees in general. (Technically fixable for a binary tree, but a large undertaking)

We can solve a lot of this by making a merkle tree that is much more light client unfriendly, to intentionally dissuade light client usecases (useful as an API surface property), and has a simpler data storage back-end implementation. (You technically can make these better for binary trees, but its a larger implementation task)

Implementation steps

• [ ] Explore DB backends. The end state years from now, would be a combined BTree w/ merkelization implementation on disk, but this is a massive engineering task. We should for now just write to a more backend.
  • I suggest we write to an SQL database due to other optimizations that exist, and that having multiple quickly iterable indexes will be very easy.
  • Is there an SQL interface wrapper thats standard in golang which we can use?
• [ ] Build merkelized BTree on-top of DB backend, with a Commit interface for writing
• [ ] Build this to work with store interface
• [ ] Think about how we do historical data storage (Thankfully we don't have to store historical merkelization metadata)
• [ ] Benchmark operation times vs IAVL
• [ ] Work on getting the custom integration into the SDK root multistore
• [ ] Work on Statesync / snapshotting integration

cc @giunatale

[p0mvn]

Is this available? I would be happy to work on / help with this once this is a priority

[giunatale]

The plan was for me to start working on it but any help/contribution I think is very welcome! I guess it would depend on the level of priority and what @ValarDragon has in mind :)