Provisioner: Elastic Scaling

[eskimor]

Check how many cores are currently available for a parachain and fetch that many candidates for paras inherent - make dependency chain check.

[alindima]

will need to also take into account changes made for fixing: #3141

[alindima]

looking into this, there are two dependency checks that need to be done:

1. check the dependencies between the candidates already occupying the cores. It's quite tricky to do this dependency check in the provisioner, because we don't have access to the parent_head_data (which is part of the PVD). We can offload this to the prospective-parachains subsystem, and supply a required_path that is not neccesarily ordered. Prospective-parachains will order it for us. The alternative would be to keep fragment trees in the provisioner as well, which I don't want to do.
2. check that the candidates we propose for backing also form a chain. we don't need to do that because prospective-parachains only provides valid chains. And the runtime will also check this in paras_inherent. so we're good

[alindima]

1. check the dependencies between the candidates already occupying the cores. It's quite tricky to do this dependency check in the provisioner, because we don't have access to the parent_head_data (which is part of the PVD). We can offload this to the prospective-parachains subsystem, and supply a required_path that is not neccesarily ordered. Prospective-parachains will order it for us. The alternative would be to keep fragment trees in the provisioner as well, which I don't want to do.

For this, I think we could use a similar algorithm as suggested here: #3131 (comment)

[alindima]

an important question to answer here is what do we do with candidates that are not included within one relay chain block.

Say we have A->B->C that are backed and pending availability and 3 cores for this parachain. A and B are included.
Say there's also a valid candidate D that descends from B.

What do we do now? C is still pending availability but we get the chance to back a new block.
Should it be:

1. another block that descends from B (which is D). This could be valuable because C could get timed out of the core. This would also require that in the inclusion runtime module, when a candidate is made available, we free any cores that would otherwise lead to invalid transitions (there's no point in keeping C in the core if D was already included). However, if C gets included first, we wasted a core by backing D.
2. or a block that descends from C (being optimistic that C will get included). This could lead to having all other cores depend on the availability of C, which could stall progress until C gets included or timed out.

I think the best option is 1

[alindima]

thought about the above a bit more:

option 1 would basically enable on-chain forks for parachains. We'd need code in the runtime and the provisioner to account for forks and free cores that build on top of an old fork once a competing fork is included. It also kind of modifies the meaning of the candidate timeout.

I think the complexity is not justified for option 1

[sandreim]

Yes, we'd want to avoid creating more complexity given the current status quo. Assuming candidate timeouts are very unlikely, my best bet would be all or nothing approach:

• A, B, C get backed at RCB
• We start the onchain inclusion process for all cores of the para when any of the candidates become available.
• if only A, B have become available at RCB + 1, then we clear C's core (availability canceled/forced timeout) and only include A, B. Collators will have to rebuild on top of B and that is fine
• if only B or C is included, then yeah, the para has lost a relay chain slot but that's life

[alindima]

That's a good idea! Would sacrifice a bit of throughput in weird scenarios but is much less complex

[alindima]

I implemented a version of the policy described in option 2 above. See #3233 and read the PR description for a detailed explanation of the proposed runtime policy