Redesign the IAVL tree with pruning in mind

[zmanian]

When we original designed the IAVL tree, the application state did not prune old state and all versions were kept in memory.

The current default behavior is that we prune we keep the last 100 versions and prune the 101st version. If the application has a the behavior of having "hot" keys that updated on every block, this effective doubles the disk i/o.

At the moment, I think the biggest improvement in IAVL i/o performance is that we introduce awareness of the pruning strategy into the IAVL tree so that generally we don't write values to the database except at snapshot heights.

If pruning is disabled, all values are persisted to the database.

[yutianwu]

If we do not write values to database every block, that will improve throughput dramatically. But we need to replay all blocks from latest saved state when we restart node.

do we have a plan to do this

[zmanian]

yeah this would be need.

IF there is a graceful shutdown, we just flush to disk before we shutdown but block replay would be great for recovery in a panic

[zmanian]

See #150

[yutianwu]

Actually, if we do save LastCommit when we do not save IAVL state, then blocks will be replayed automatically for the difference between state height and block height. A graceful shutdown will surely help to save the replay work.

So besides the IAVL change you mentioned, we also need to do some changes on cosmos Commit stage.

[AdityaSripal]

Currently working on this by building on top of loom PR (#150).

Current design

MutableTree has extra fields:

// Pruning fields
keepEvery  int64n // Saves version to disk periodically
keepRecent int64  // Saves recent versions in memory

NodeDB has extra fields:

memDb    dbm.DB     // Memory node storage.
memBatch dbm.Batch  // Batched writing buffer for memDB.

On SaveRoot, the IAVL checks if the version should be persisted to disk (version % keepEvery == 0)

If version is not going to be persisted to disk, the version is simply saved in memDB
If version is persisted to disk, the version is written to memDB and levelDB

When version n is saved, version n - keepRecent is deleted from memDB. Thus, memDB always contains keepRecent versions of the tree.

Orphans:

Save orphan to memDB under o|toVersion|fromVersion.

If there exists snapshot version snapVersion s.t. fromVersion < snapVersion < toVersion, save orphan to disk as well under o|snapVersion|fromVersion.
NOTE: in unlikely event, that two snapshot versions exist between fromVersion and toVersion, we use closest snapshot version that is less than toVersion

Can then simply use the old delete algorithm with some minor simplifications/optimizations

Open Questions:

1. Currently recently persisted versions exist both in memDB and levelDB. This is so that retreiving a recently persisted version is fast. However, it introduces minor duplication (not a problem in any sane pruning strategy).

2. Currently recent versions are saved to memDB. Is this better than simply storing in a map key => *Node like loom currently does? I'm not sure what the tradeoffs are.
   Decision: Decided to go with using memDB since it already implements DB interface (iterating, etc). Also, could switch out memDB for something else later so long as it respects DB interface.

3. Now that memDB acts as a recent version "cache" for levelDB, need to specify the use (if any) for LRU cache. My thinking is that this will be used to cache old nodes (version < latest - keepRecent) that are frequently called by GetNode. But have to make sure that LRU cache's purpose is strictly defined (when does a node get added to cache?) and enforced.

4. Currently all traverse functions traverse over single levelDB. This will have to be refactored to allow traversing over levelDB, memDB, or both. Should replace all current traversal calls with the appropriate new traversal function.
   Currently implementing:

5. We can flush any versions in memDB to disk in event of graceful shutdown, how do we restart node correctly?
   Current thinking: Regardless of whether there is a graceful shutdown or not, on recovery, we reverse-iterate for the latestVersion stored on disk (and refill memDB if necessary).

from conversation with @jackzampolin

[zmanian]

For recovery, Tendermint store metadata on the LastCommit and then replays all past block. Tendermint will need to know how to back up to last save commit and then replay.

Current thinking is that isn't necessarily hard.

[jackzampolin]

Sounds like you should write up an approach for points 3 and 4 above and we can get some feedback on those.

[tac0turtle]

This is closed with PR correct @AdityaSripal

[tac0turtle]

Reopening this as a potential work scope for future iavl work.

[tac0turtle]

closing this as the goal is referenced in #140