Some invalid transactions removed from the pool should be revalidated

[tomusdrw]

During block authorship we attempt to detect invalid transactions that are still in the pool.
Since pool is being cleaned asynchronously, it is a completely legal and valid situation - in the front of the ready queue we have transactions that just got included to recently imported/authored block.
However the transactions that are detected invalid are removed from the pool via remove_invalid call.
That in turn causes the entire subtree of transactions to be removed (i.e. all transactions that depend on the invalid ones), as we assume that since their predecessor is invalid they are going to be invalid too.

As an example, let's imagine we have a following set of transactions in the pool (coming from the same sender):

tx(nonce=1)
tx(2)
tx(3)
tx(4)

1. now, we import a block that contains tx(1), but don't clear the pool.
2. If we attempt to produce another block, tx(1) will cause InvalidTransaction::Stale error to be returned, hence we will mark it as invalid.
3. Next we will try to execute tx(2), but it will obviously succeed.
4. Then imagine that tx(3) does not fit to the block - we finish up block authoring and should resume the next block starting off with including tx(3).
5. However remove_invalid(tx(1)) will cause the entire subtree originating in tx(1) to be removed from the pool, so tx(3) and tx(4) will no longer be there.

Solution

There are two ways to solve that issue:

1. Either attempt to resubmit transactions that were not directly invalid, but just transitevly (tx(2),tx(3),tx(4) in the example)
2. Or remove only invalid transactions reported directly, not their subtrees - this may leave some more invalid transactions in the pool, but they should just be detected on next attempts.

I'd vote for option (2), cause it's more suited for frame-based runtimes, since most likely the transactions left in the pool are still valid. We can possibly implement both solutions and have that configurable as well.

[tomusdrw]

CC @NikVolf let me know if you want to tackle this one.

[NikVolf]

now, we import a block that contains tx(1), but don't clear the pool.

(1) why we don't clear the pool, then?

(2) I think we go with variant 2, but we can differentiate and don't remove subtree when transaction is Stale and remove subtree when it is invalid for other reason.

[tomusdrw]

(1) we do that asynchronously currently, and we don't really know when the notification task will be picked up.

(2) Yeah that sounds reasonable too.

[NikVolf]

(1) But notification about previously imported block should be picked up long before we start constructing block on top of it. Maybe we should make sure that imported transactions are removed as fast as possible, and then we can avoid fixing something that not broken?

[NikVolf]

(1) We remove all known transactions from the pool as soon as we receive import notification

So what makes you think the whole story is the issue?

[NikVolf]

(1) If new block construction starts immediately, i.e. when transaction pool is still processing notification from the imported block, we can make part the removes known transaction synchronous (move this outside of async block). Another solution is too just note known tags synchronously and never include corresponding transaction in ready iterator.

[tomusdrw]

maintain function in the code that you linked is being called after we receive notification from import_notification_stream, right? This means that block authorship and maintenance are separate tokio tasks and run indepedently on the same runtime. It also means that either of those tasks can be "starved" for a while and just don't run. That creates the race condition described above.

I observed the issue in tests when working on #5121 but it also explains behaviour that was seen by @shawntabrizi when working on benchmarks.
Basically it will happen if we try to produce blocks very fast (for instance --dev chain) and the starvation of maintenance happens.

Another solution is too just note known tags synchronously and never include corresponding transaction in ready iterator.

Yup, I've been thinking about that too - like quickly skipping transactions that are known to be in chain in ReadyIterator.

I'm not strong on any of those solutions, so whoever picks this issue up should be free to choose whatever they prefer and works best.