[Epic]: IAVL v2 implementation

[kocubinski]

This issue tracks IAVL v2's SQLite backed implementation, including briefs of milestones hit (past), in progress work (present), overall strategy and near-term pending items (future).

main dev branch: https://github.com/cosmos/iavl/tree/v2-alpha6

Benchmarks and Tests

Benchmarks demonstrating the performance of IAVL v2 are implemented, the steps below will reproduce them. The dataset used is specified as OsmoLikeMany, which approximates the state of osmosis's application.db in mid Sept 2023.

# Generate an IAVL v2 tree at initial version 1 and save to disk
❯ go run ./cmd gen tree --db /tmp/iavl-v2 --limit 1 --type osmo-like-many
...
Nov  9 13:03:50 DBG db=tree count=46,600,000 dur=383ms rate=522,711 module=batch path=/tmp/iavl-v2/ibc
Nov  9 13:04:38 INF last version=1 hash=e169c479e811275a5b9cca72ca615ce4582f8eeba75b73969fa990e0bc9c02bb

# Create a snapshot of tree state for fast loading in tests
❯ go run ./cmd snapshot --db /tmp/iavl-v2 --version 1
...
Nov  9 13:32:27 INF flush total=46,799,999 batch=200,000 dur=1.153s wr/s=173,461 path=ibc
Nov  9 13:32:27 INF creating index on snapshot_1 path=/tmp/iavl-v2/ibc

# Generate the input data for the benchmark
❯ mkdir -p /tmp/osmo-like-many/v2 && go run ./cmd gen emit --start 2 --limit 5000 --type osmo-like-many --out /tmp/osmo-like-many/v2
Nov  9 12:32:14 INF fast forward version=1 nodes=5,000,000
...
Nov  9 12:32:28 INF version=7 nodes=46,000,000
...
last file written: /tmp/osmo-like-many/v2/00-00000144.pb.gz

# Run a benchmark which loads the snapshot then ingests the above data
❯ go test -v -run TestOsmoLike_HotStart
...
Nov  9 13:41:37 INF open file: 00-00000041.pb.gz module=compact path=/tmp/osmo-like-many/v2
leaves=27,500,000 time=3.934s last=63,553 μ=62,834 version=1431 Δhit=0 Δmiss=509,398 alloc=13 GB gc=31
writes: cnt=203,371 wr/s=370,202 dur/wr=2.701µs dur=549ms
queries=502,260 q/s=103,703 dur/q=9.642µs dur=4.843s leaf-q=502,256 branch-q=0 leaf-miss=0

# Rollback the tree state to version 1
❯ go run ./cmd rollback --path /tmp/iavl-v2 --version 1
...
Nov  9 13:44:31 INF revert db /tmp/iavl-v2/wasm to version 1

Similar benchmark tests against IAVL v0 and IAVL v1 (see https://github.com/cosmos/iavl-bench) were run, throughput is ~60x faster than v0 and 12x v1.

• [ ] Create an abbreviated CI friendly version of the above test
• [ ] General clean up and organization of tests for CI runs

TestTree_Hash validates the root hash consistency with iavl v0 in a mode closer to historical mode (see below).

General

• [x] Changelog storage (leaf set/delete)
• [x] Multitree PoC demonstrating concurrent SaveVersion and LoadSnapshot
  • Most users will probably use the existing logic in the store package, but this is useful for benchmarks.
• [x] Configurable state storage mode (leaf values/no leaf values) for both store v1 and v2 compatibility.
• [ ] Optimize mmap and cache sizes for leaf and tree tables from benchmarks
• [ ] Storage support for out of consensus metadata like latest version, commit info (possibly others) so that existing application.db is fully deprecated in store v1 with iavl v2.
• [ ] async commit. Defer the i/o required for writing to disk to a background thread and fail on the next SaveVersion if this failed. MemIAVL has shown that this strategy works very well, since the state machine will take much longer to process block n+1 than time spent in commit of block n.

Latest Mode

Latest mode is the fastest and most memory intensive operating of mode of IAVL v2. In this mode either the entire tree is stored in a memory, or all branch nodes (leaves excluded).

• [x] Leaf eviction filter
• [x] No evictions (retain entire tree in memory)
• [x] Checkpoint sharding
• [ ] #856

Historical Mode

Historical mode approximates current behavior in IAVL v0 and v1 where all branch and leaf nodes are saved to disk at every version. Primary use cases are nodes supporting historical proofs or full archive nodes.

• [ ] Deferred index creation mode (higher throughput, no proofs until checkpoint)
• [ ] Immediate index mode (proofs immediately available for past versions, slower writes)

Snapshot

• [x] Pre-order snapshot
• [x] Pre-order restore
• [x] #852
• [x] Post-order restore

Pruning

Discussions in the store v2 working group are split on the efficiency of both approaches below. Orphan tracking is more time efficient and less space efficient, a tree diff is more space efficient but less time efficient. Benchmarks comparing both are needed.

• [ ] Orphan tracking (IAVL v0 design)
• [x] #855
• [ ] Benchmarks of both approaches

Migration

• [ ] Naive stop the world, all at once migration to snapshot
  • In progress, working with pre-order snapshots.
• [ ] Double-write with cutover strategy to support online migration from iavl v0.

Osmosis integration

There is no better test than mainnet integration. To support adoption and highlight any issues in IAVL v2 a PoC of integration into an osmosis node is in progress so that mainnet benchmarks may be obtained. This will inform current and future development.

Osmosis forked Cosmos SDK with IAVL v2 patch: https://github.com/cosmos/cosmos-sdk/tree/kocubinski/osmosis-iavl-v2 Osmosis with the above patch: https://github.com/01builders/osmosis/tree/kocubinski/iavl-v2

Status

mainnet is syncing but panics at snapshot (not yet implemented).

TODO

• [x] Collect block time metrics for comparison with IAVL v0
• [ ] Call SaveVersion concurrently
• [ ] Collect tree.Metrics and log set/get/delete metrics per tree
• [ ] Make sure the concurrent queryings allowed

[tac0turtle]

We talked on the team call about supporting import for preorder and post order to enable usage of iavlv2 in existing networks, but for new networks it would only be an export of preorder to simplify the code in the long run.