Implement Default SC

[alexanderbez]

See #17226 for implementation details and ideas. The current proposal is to borrow ideas from memIAVL and tweak things to make them more performant and ergonomic, which also fits the SC API

[tac0turtle]

are we pulling memiavl into a repo in the cosmos org or rewriting it?

[alexanderbez]

I'd like for @kocubinski and @cool-develope to provide their thoughts here on that.

From my POV, I believe we should bring it into the cosmos org no matter what.

Now as for re-writing, my mental model is that we're probably better off porting the existing Cronos version of memIAVL with all our improvements, fixes, and benchmarks.

[cool-develope]

I'd like to rewrite it since I can see it is far away from the current store v2 design.

[kocubinski]

I think MemIAVL should continue to be what its README says it is: Alternative IAVL Implementation.

cosmos/iavl would be better off evolving to include the performance improvement strategies which MemIAVL uses without the tight coupling to its implementation. These strategies (common to many production-grade databases) are:

• Push writes to a WAL, pin in cache, and flush at checkpoints. Implemented as periodic full snapshots in MemIAVL.
• A in-memory page cache. MemIAVL splits this cache into pinned/dirty nodes, MemNode, and mmap snapshotted nodes PersistentNode
• A performant, well-researched storage format. (MemIAVL uses a custom format to layout an AVL tree on disk)

The storage format/backend is not swappable in MemIAVL, but imo should be. For page cache, AFAIK in MemIAVL, it's not possible to limit the dirty cache size between snapshots, which could lead to unpredictable memory usage, and mmap at the OS level is an abstraction away, and memory caps are not easily controllable there either.

For a storage format I doubt we'll ever beat LSM for writes or sequential reads given the iavl-v1 node key format and the upper bound on SC size in store v2. If all we did was introduce a WAL, a memory bounded cache with second chance or Clock page replacement, and infrequent full checkpoints we'd have the same improvements.

I prototyped some of this in https://github.com/cosmos/iavl/tree/avlite and produced a benchmark with good results.

Maybe we should also wait for an answer in historic proof feasibility and performance against periodic full backups, since this requires replaying and rebuilding the tree in memory to obtain a proof.

[tac0turtle]

@cool-develope is iavl v1 integrated?

[cool-develope]

yes, for the current SC API (PoC)

[alexanderbez]

Do you feel that is sufficient to close this issue then @cool-develope?

[cool-develope]

yeah, if we agree with creating a new issue for memiavl integration and separating the pruning and snapshotting from the SC.

[alexanderbez]

@cool-develope please close this when ready 👍

[cool-develope]

iavl V1 integration is ready