Lazy downloading of data in try-runtime-cli

[kianenigma]

One of the main drawbacks of try-runtime for production chains is that it is very slow to download.

We made good amount of changes in #12537 to improve this a bit, but it is still not enough.

In this branch, I tried to make the lazy-download work by integrating it into the remote-externalities as a new backend. But this proved to be too messy. Perhaps someone can re-try this better and do it better than my try.

Alternatively, we always have the option to achieve this by overwriting host functions. But I am not sure how to achieve this. On paper, this is a simpler approach

@cheme @bkchr I am sure both of you are too busy, but you might be able to shed some light into which direction is reasonable to make.

[cheme]

I remember we try to think about it a bit and it was not straightforward.

My first idea was that the read access should use light client calls (over trie query).

Doing it this way allows the client to keep his change and accessed node on a local memory db, so no session persistence would be needed on the host.

IIRC the granularity might be a bit thin (one query for a single value access), and some primitives
are missing.
Light iteration rpc would be needed (which we almost got for warpsync).
A rpc for doing root would be needed, alas this would only work for the first block, as for next blocks the trie will be in a different starte than the remote.
So basically to avoid this, on every call we would need to pass all previous change from previous block processing which will grow bigger and bigger, and also return a light client proof bigger every time. We could also do the storage root calculation on the client side and use an rpc to fetch the trie nodes that are missing locally.

So a different direction (I think it is the one you start taking in your branch) is to assume we do not support correct root and trie, and just download the values
on rpc, then the storage root rpc is not needed anymore, we just build root from the current storage (a next_key rpc would still be needed).

Calls to externality first check if we got a previous query persisted or a change in layer (so probably need to store Option for a key), and if never queried then access it.
Calls to next_key are a bit more complex here: we need to keep trace of all the range that where already fetched, but nothing impossible.

And of course a third possibility could be to just have a rpc that return encoded trie node for a given hash, and plug it in a modified memorydb, the granularity really seems to small, but then we do not have redundant data in light client proofs.

My opinion here is: to get something quickly the second version should be achievable, even if next_key persistence might be a bit messy (I remember storing this on an experimental branch aka keeping trace of a range of accesses, it was not really the clearest code), but the first version is more interesting generally (light primitives could be interesting and it produces correct storage root).

Trying to get an acceptable solution do do storage root with the first version (that would not require a lot of changes as input and very redundant proof as a result), one can just query all the modified nodes that where not previously queried (removed values and modified values that where not accessed).
Then with those node the storage root should be doable except in the case of a removed node that is on a branch with a single child, which would need to access manually the unique child node (then child node should be queried as in the third solution).
Same thing with first solution, redundant nodes in proof could be avoided by passing the depth of the last known node (or the first unknown node hash), but this would not be the most straightforward to put in place.

Also this assume we want stateless rpc, going statefull one could just use a remote state machine backend that we update between each blocks.

[bkchr]

I don't think we need proofs here. I mean we just want to do some testing and you are also running this testing against some own local node.

As we are only downloading data for a particular block, is it really so hard to cache this stuff and keep up with what we already have downloaded? I mean we have support for downloading stuff with the same prefix (which is essentially what we need for iterations) in pages. When the last page is empty, we are done. And we can cache all this stuff and maybe already do another request in the background while we are returning one value to the runtime.