Perform Catchup jobs chronologically

[nholland94]

Currently, the Catchup mechanism works by requesting missing blocks in chunks, backwards from some disconnected block we want to connect to our local Transition Frontier. This is a natural way to traverse the chain since it is the direction of the block pointers, however, it would be better if we were to perform the Catchup jobs in chronological order and add them to the Transition Frontier in chunks as we go. We will need to be sure to be careful in how we design the Breadcrumb Builder under this scheme since the Breadcrumb Builder will now need to be aware of still ongoing interdependent jobs in a similar way to how the Catchup Scheduler tracks dependencies.

This is a mild improvement on the daemon, so it is not a terribly high priority. The main effect of doing this would be to allow nodes to remaining more up to date with the the Transition Frontier of others on the network while there are still ongoing Catchup jobs.

[emberian]

Some more detail here:

The catchup scheduler is responsible for fetching the dependencies of new blocks. If we receive a block and don't already have its parent block stored in the frontier, the catchup scheduler starts "watching" that block (watch function). This includes setting a timeout. If the timeout fires before the parent block is learned, it triggers a "catchup job". The catchup scheduler collects all of the watched blocks in a map from parent hash -> list of direct children (collected_transitions field), to try and avoid triggering extra catchup jobs unnecessarily. The transition processor calls the notify function for every transition inserted into the frontier, at which point the catchup scheduler will look to see if the new transition satisfies the dependencies of the watched blocks, and if it does, sends them off to the breadcrumb builder. If the timeout fires, Ledger_catchup is used to download the missing transitions from other nodes, and those get sent to the breadcrumb builder.

The breadcrumb builder is responsible for applying the "staged ledger diffs", a very expensive operation, in the background to produce a full "breadcrumb". A breadcrumb is an "unpacked transition". Transitions include a diff from the previous state to the state they represent, and the breadcrumb includes the result of applying that diff. A "initial validated" transition can have a staged ledger diff that will fail to apply, but we can't know that until we try and apply it and we can't apply it until we have the parent state. So the breadcrumb builder takes in a tree of transitions and produces the corresponding tree of breadcrumbs, under the assumption that the parent state of the root of the tree is available in the transition frontier.

The ledger_catchup module takes as input a list of trees (a "forest") of all the relevant collected transitions. Each tree has the missing transition as the parent of its root the transition. It downloads the state hashes of the transitions connecting back to the root of the frontier (or the start of the root history? I'm not exactly sure. A bunch of state hashes for sure) and then uses those state hashes as identifiers to download the missing transitions. Once all of the transitions have been downloaded, the completed tree of initially validated transitions get sent off to the breadcrumb builder.

Closing this issue will require slightly changing the structure of how this communication works. Instead of sending complete trees around, once ledger_catchup takes over it should write each available transition immediately.

There is a complication: if the breadcrumb builder fails to apply a diff, we should cancel all the other work happening to download any distance children of that transition.

[nholland94]

A couple of extra details to note:

The transition processor calls the notify function for every transition inserted into the frontier, at which point the catchup scheduler will look to see if the new transition satisfies the dependencies of the watched blocks, and if it does, sends them off to the breadcrumb builder.

It also takes into account the case that we have received a dependency that does not fully connect our subtree to the frontier, and does so in a concatenative way. More concretely, take the chain A -> B -> C -> {D, E}. Assume our frontier has A, and we have active catchup jobs for D and E. If we receive C, we will remove the catchup waits for D and E and put a new wait on C. When we fire off the job for C (if we do not receive B in time), we will then fire a job to catchup to the entire subtree of C -> {D, E}.

So the breadcrumb builder takes in a tree of transitions and produces the corresponding tree of breadcrumbs, under the assumption that the parent state of the root of the tree is available in the transition frontier.

Important to note here that is submits this tree all at once to the processor rather than submitting each breadcrumb one at a time. This keeps the pressure on the processor lower, allowing it to handle network blocks more regularly without significant slowdown during catchup.

It downloads the state hashes of the transitions connecting back to the root of the frontier (or the start of the root history? I'm not exactly sure. A bunch of state hashes for sure) and then uses those state hashes as identifiers to download the missing transitions.

Currently, it just always downloads K state hashes. This is inefficient and should be changed as part of this chronological work, but it guarantees that we only every need to make one request. The missing transitions are then downloaded in chunks of a configurable size.

Closing this issue will require slightly changing the structure of how this communication works. Instead of sending complete trees around, once ledger_catchup takes over it should write each available transition immediately.

In order to keep pressure on the processor low during catchup, I think it needs to write chunks of subtrees at once, rather than one breadcrumb at a time. This also fits into the context that we download the missing blocks in chunks as well, so it may not be that difficult, though it will require a change to how we download missing blocks. (perhaps downloading missing blocks by providing a list of state hashes makes the most sense here so that the client can determine the ordering).

There is a complication: if the breadcrumb builder fails to apply a diff, we should cancel all the other work happening to download any distance children of that transition.

We can leverage the Unprocessed_transition_cache here. It can provide subscriptions to whether or not blocks have been determined to be invalid. Sorry, I forgot about this last we spoke on this topic.

[aneesharaines]

Changes are now extending to breadcrumb builder.

[aneesharaines]

@yutongz5 to setup a discussion about the approach with the team