State Cache

[i-norden]

Our db contains disperse state diffs, instead of a complete state trie at every block. For the purposes of queries such as getSlice, we need to generate complete state caches to reduce the query times. Generating a cache at every block would amount to enormous storage costs and negate the advantage of having state diffs. Instead, we will generate a state cache at every 2048 blocks. This reduces storage needs by a factor of 2048 while also reducing the maximum search space for getSlice queries to only 2048 blocks (instead of millions).

State cache algo:

1. Retrieve latest state cache and it's height (n).

• If there is none then n = 0 and the state cache is empty.

2. Retrieve header(s) at n+2048.

• If there is more than one header perform recursive +256 validation until we can resolve which header is valid.
• If we can't find any header at n+2048 we must wait for the sync to introduce one.
• If we can't validate any header at n+2048 we must mark that height for resync and wait for one.

3. Validate headers from n+2048 back to n (by following parent_hashes), producing a section of valid headers.

• If we are unable to validate a section from n+2048 to n, mark the heights where we are missing a valid header for resync and wait for them to be filled in.

4. From the section of valid headers collect the most recent state diff for every state path that exists at n+2048.
5. Apply these state diffs on top of the state cache at n to produce the new state cache at n+2048. Note that if n == 0 then the diffs are applied on top an empty cache.