Store: Write regression tests & more benchmarks/tests

[tac0turtle]

• Write regression tests so that if we migrate to a new tree we know that the previous semantics are met
• Write more tests for things like concurrency and where we are unsure about how things work (TBD)
• Add more benchmarks if needed to properly bench and follow changes in the store

[ethanfrey]

A few points I would like to add. Not "regressions" but undefined / non-determinstic behavior I am aware of.

When committing a multi-store, the order of committing each sub-store is random. If you change the write order within an iavl tree, that will change the hash. Now, in theory, each sub-store is it's own iavl store, so random write order between stores shouldn't have an effect, but this can make actually debugging out of order writes with tracestore near impossible and may introduce non-determinism.

Some invariants we should enforce:

• Given a use case of multiple cache writes (see below)
• AppHash of substores should be constant (defined in test)
• AppHash of multistore should be constant (defined in test)
• Ordering of writes (eg tracestore output) is constant (defined in test, same in every run)

In the current codebase, hash matches for all cases I know of (but not sure it holds with fuzzing). But write order is random between substores, which makes tracing near impossible and is playing with fire with modules that are order-dependent hashes.

Some example scenarios:

All have 3 stores: apple, banana, carrot

1. Write 2 items (different keys/value) to each of the 3 stores, directly on multi-store
2. One level cache wrap, write same items to each store, commit to multi-store, should match 1
3. One level cache wrap, write these values, second cache wrap, write some new value, overwrite some values, commit second cache wrap, delete 1 item in banana and carrot, commit this cache wrap
4. Total of three levels like (3)
5. Like 3 but after committing the second level cache wrap, make another second level cache wrap, read 4 keys that exist, overwrite 2, and rollback that cache, before continuing as in (3). Should match 3 (revert and reads should have no effect)

[tac0turtle]

@facundomedica what is the status of this? saw two prs but not sure when we can close this or move forward