SMT v0.4 potential wishlist

[musalbas]

Storage

• [ ] For value store, store the values by key, rather than path. (This will allow iterating over keys efficiently, as may be expected in Cosmos SDK store v1, though not for historical trees. We should determine if this is sufficient.)
• [ ] Store nodes as an n-ary tree using tiles, allow for more efficient updates to the tree.
• [ ] Store nodes in memory as an actual node tree, and only recompute the root when the tree is committed.

Versioning and pruning

• [ ] Enable the option to keep the historical versions of the tree.
• [ ] Add pruning support (i.e. only keep X historical versions) using reference-counting and a "deletion pending" database.
• [ ] Add rollback support using a journal.

Note: this would allow for O(1) reading of keys from the latest tree, but O(log(n)) for historical trees where n is the keys in the tree, unless versioning is also implemented for the value store. Note that IAVL's reads are always O(log(n)) anyway. Furthermore, rollbacks would be O(o) where o is the number of operations being rolled back (this is the same as Ethereum's state trie). We should understand Cosmos SDK store requirements for this.

Batching

• [ ] Add support for batch writes/commit. (https://github.com/celestiaorg/smt/issues/13)

Documentation

• [ ] Document storage layer architecture if tiling or pruning is added.
• [ ] Document tree algorithms in more detail than current specs, or move specs here.

[adlerjohn]

IMO batch writing is by far the most important of these features since it's critical for performance in all cases. The rest are more related to upstreaming into the Cosmos SDK or are still research questions. We could consider splitting these across a few releases instead of blocking on all of them.

[musalbas]

Agreed, though I'm also not sure batching needs to be implemented in this repo, as it can be in the MapStore implementation. However, for pruning, some concept of a version will be needed which may be related to a commit function/batching.

[musalbas]

Closing as new/pending information may invalidate this wishlist.