Remove "dead" leaves

[bkchr]

When proposing new PoV blocks with a collator, it can happen that we are "stuck" as the relay chain for whatever reason doesn't include our blocks. After X blocks the collator will start to fail importing new blocks, because we have imported too many leaves.

Using paritytech/substrate#8533 we will be able to delete "dead" leaves.

We will require some criterias to decide wether a leave should be seen as "dead":

1. A block was not seconded, means we can directly remove it.
2. We have produced block X for relay chain block Y. Now we start producing for Y + N, means we should be able to remove all blocks we have produced/imported for Y.

[xlc]

I hope this can be done before Beyond the End of the Century 😅

[bkchr]

Maybe :P (I propose that you google this term :P)

[xlc]

One of our testnet RPC node crashed again due to this and looks like the only solution is to purge db and resync.

[davxy]

I think that could be a good idea to generalize the leaves pruning feature to Substrate and not limit it to Cumulus.

The idea is to allow the user to pragmatically set the lifetime of chain leaves in order to optionally prune the leaves that are assumed to be "dead".

This pruning strategy can be enabled where is more appropriate, for example to solve the current observed behavior in cumulus where new blocks are never accepted because we've saturated the max leaves per height limit (currently 32).

For the pruning criteria I see three options:

1. allow the user to specify the pruning criteria (e.g. via some closure) (more flexibility but less simplicity)
2. we decide what is the pruning criteria (e.g. leaf lifetime) (more simplicity less flexibility)
3. allow the user to specify the pruning criteria but also provide a default implementation (e.g. that uses leaf lifetime)

---

Pruning criteria using lifetime.

When a new leaf is added to the chain then we are going to start some kind of timer in order to limit the leaf lifespan.

The timer for a leaf 'L' is stopped if a child 'C' is added to 'L', in this case the timer is restarted for the new leaf 'C'.

If the lifetime for a leaf 'L' is over, then we are going to remove all its parents down to one of the following nodes
(assuming 'F' is the last finalized block):

1. If there are forks between 'L' and 'F', then we stop pruning nodes as soon as we reach one fork point.
   Example:

   F - B0 - B1
        \ - B2 - L
   

   In this case, if lifetime of 'L' is over, then we remove 'L' and 'B2'.
   We stop at 'B0' since there is another fork depending on it.

2. If there are no forks between 'L' and 'F', then we stop pruning at 'F' (excluded).

[skunert]

@davxy For the scenario described at the start of the issue, where we have reached the maximum allowed leaves at a given height, the timer-based solution you propose would be the same as just constantly deleting the oldest stall leaf, right? (because those will time out first)

[bkchr]

I would first start concentrating on Cumulus aka Parachains. For normal chains this can not really happen that easily that you build too many blocks on the same level (yes it is still possible, but much more unlikely then for Parachains). We have once seen this error on a Polkadot test net, because the chain selection rule had gone apeshit, but that was a bug. This issue is also not really that much about leaves, more about blocks on the same height. I just used the naming as it is being used in Substrate.