Parallel transaction execution within blocks

[Voxelot]

One of the key benefits of fuel's transaction format and architecture is the capability to parallelize transactions execution. This issue is intended to cover the initial design and considerations for implementing parallel execution, but will likely be comprised of many smaller tasks. This design is subject to change based on feedback and discovery.

Scheduling

Transactions are schedule-able for parallelization according to their input and output UTXOs, which could be considered as a resource access list. If any resource overlap exists between transactions, then those will need to be grouped and executed sequentially. Any subsequent overlapping transactions will be added to this concurrency grouping.

Resource overlap conditions:

• Matching contract ID
• Coin input that depends on another unprocessed output.

This diagram illustrates the optimal grouping of transactions. Also note in Group B, transactions which have no direct dependency on each other will still need to be ordered within the same group if there is a transitive dependency between them.

Gas Limits & Block Capacity

In traditional blockchain architectures, each block has a total gas limit which is used to bound execution time. However, a single global limit doesn't take into account the level of concurrency. If the block gas limit is set based upon the desired execution deadline for single threaded execution, then the overall throughput would not be increased by making execution parallel. Similarly, if the gas limit of a block is taken simply as the single threaded limit * number of cores, this may allow blocks to exceed their desired execution deadline if all the transactions are combined into one concurrency group due to shared resource access.

In order to correctly bound execution time, our block gas limit should be considered as the limit per concurrency group. A max concurrency limit should also be provided as a consensus rule. If there are more concurrency groups than the concurrency limit, then those groups should be recombined to meet the concurrency restriction. If there's no way to fit all the transactions into the maximum number of concurrency groups without exceeding the per group gas limit when validating a block, it will be considered invalid.

Transaction Selection & Packing

Transaction selection should seek to fully saturate each concurrency group in a way that maximizes the overall fee collected from a block. A fully optimal solution may involve a more complicated variant of the knapsack problem which has to factor in dependencies between transactions. To avoid this overhead, the selection process could greedily select transactions based on gas price. Greedy selection would attempt to pack all concurrency groups by taking transactions in order of their gas price. It would then need to skip over transactions that contain resource overlap with full concurrency groups.

Risks

Deterministic Packing

It's possible that some sequencers with better block packing strategies may produce blocks that can't be validated by others. If the validator can't find the same packing structure as the sequencer, it may not be able to fit the per group gas limit.

This may require each sequencer to include the execution schedule they used within the block. For example, instead of making each block contain a flat list of transactions, it could contain a list of lists of transactions. With each sub-list corresponding to a concurrency group. This would alleviate the requirement for validators repack the transactions into groups with the risk of not finding a solution to the per group gas limit.

Implementation

Block Execution high-level (executor)

• Extract concurrency groups from the block ( Vec<Vec<Transaction>> )
  • The coinbase mint transaction should always reside in the first concurrency group
• Verify that each group doesn't exceed the block gas limit
• Each concurrency group should be sent to a threadpool worker groups.map(|txs: Vec<Transaction>| spawn_blocking(execute(txs)))
• Each worker returns an uncommitted execution result (status, database transaction & processed fees)
• Each execution result is checked for any failures, fees are totalled, and database transactions combined into a single transaction.
• Coinbase amount updated based on total fees collected
• Yields a single execution result with the aggregate changes from each concurrency group.

Selection changes (txpool)

• Takes as input the concurrency level and max gas per group
• Greedily takes transactions ordered by gas price
  • Skip if transaction depends on resources which haven't been previously committed or included in a prior resource group
  • If transaction has a resource overlap with a concurrency group
    • add to the concurrency group if this won't exceed the group gas limit
    • otherwise skip
  • If no overlap exists, add to the concurrency group with the least amount of gas
    • skip if no groups can fit the transaction

[mitchmindtree]

Nice job on getting all this down @Voxelot! Sounding good to me.

W.r.t. selection implementation: Perhaps we should consider maintaining a DAG representing transaction resource dependency as transactions enter the txpool?

Then when we're ready to select TXs, we can find the strongly connected components of the DAG to find all synchronous TX batches.

Next, rather than just greedily taking transactions by gas price, we could greedily take slices from the synchronous TX batches by gas price for our concurrency group bin-packing, knowing ahead of time that we can't encounter any resource conflict.

[Voxelot]

We actually use a DAG in the txpool already for resource dependencies :)

In our current instantiation of the txpool, transactions are required to have a descending gas price as the depth increases between coin dependencies. This constraint helps to ensure that selecting transactions in order by gas price will also be ordered in terms of their dependency on each other. However, this has some downsides. For example, in Ethereum you can cancel a previous pending transaction by submitting another one with the same nonce and a higher gas price. This works by making miners choose the higher price transaction, which then invalidates the nonce on the pending tx with the lower price. If a gas price has to be descending based on depth, this makes the tx difficult to cancel if the price is already at its maximum limit. It also means that long transaction sequences may have to underprice their transactions, causing that subtree to be ignored by miners.

For selecting transactions from the tree in batches, are you implying that it would slice through the subset of connected nodes until the gas price of the next element in the sequence is lower than other unconnected nodes OR the group gas limit is reached? This may allow us to do away with the constraint that requires descending gas prices.

[Dentosal]

Looks good, very detailed and comprehensive. Some questions:

• How does this relate to parallel predicate execution? Do we need separate concurrency limits for that?
• Can you censor/delay a tx by repeatedly sending a slightly higher-gas-price but low-gas-limit transactions that confict with it? Is this an issue?
• There are some possible optimizations over greedy transaction selection, do want to consider those? Especially if we don't require deterministic selection process. We can go ahead with the greedy algo and experiment with this later.

[xgreenx]

Blocked by https://github.com/FuelLabs/fuel-core/issues/1189 and https://github.com/FuelLabs/fuel-core/issues/1229