[merkledb] Prefetch Missing Trie Nodes Not Found in Cache

[patrick-ogrady]

This may allow us to use more disk bandwidth rather than more memory (which may be a good balance for some networks).

The EVM supports this by pre-executing all txs on the parent state.

[patrick-ogrady]

This could be done when marking that a key has been modified (we could async check all intermediate nodes are present).

We wouldn't necessarily need to do this on the read path because we would just be reading values directly.

[patrick-ogrady]

According to @dboehm-avalabs, this can be accomplished using logic already implemented in "GetProof".

[patrick-ogrady]

We should stop prefetching paths as soon as we are done executing txs (as we will already fetch in root gen) to avoid duplicate fetches?

[patrick-ogrady]

If we split trie node cache vs value cache, this should make it much faster. Right now, lock contention on trie path prefetch (specifically the node cache) slows things down.

[dboehm-avalabs]

Playing with some improvements in https://github.com/ava-labs/avalanchego/tree/NodeReduction that could help with this.

[patrick-ogrady]

With Coaxium, this could be made even more aggressive and we could populate the cache for intermediate nodes before execution even starts (we just wouldn't know which are modified).

[patrick-ogrady]

Example implementation: ava-labs/coreth#372