Parallel execution

[tomatoishealthy]

Rationale

At present, more and more blockchains are exploring parallel execution of transactions. Parallel execution can improve transaction processing capabilities and reduce gas fees.
Transaction execution and verification of traditional blockchains are usually performed serially. This is because in order to obtain a globally consistent state data set, it is necessary to ensure that the execution results of each transaction on each node are consistent. Serial execution is the simplest and most feasible way. However, with the continuous development of technology, some infra teams have made big progress in parallel execution. Here are some well-known projects and their sketch:

Aptos

Its parallel execution is called Block-STM, which adopts optimistic assumptions, executes transactions in parallel and performs conflict detection during execution

BscChain

Similar to Aptos, it also directly verifies transactions in blocks in parallel. But considering that the underlying storage of Move and EVM are different, there are some differences between the two in terms of transaction dispatch and conflict detection.

Polygon

Polygon has also conducted in-depth research on parallel execution. The main difference between the above two is that Polygon introduces a builder role (similar to ETH's MEV-builder / PBS). The builder is responsible for proposing blocks and generating the DAG of the transactions in the block, then appending this information to the meta of the block. The rest of the nodes directly process transactions in parallel through the DAG without needing additional conflict detection, which is theoretically more efficient.
However, this solution increases the complexity of the system due to the introduction of additional modules, and will also introduce a series of problems currently faced by Ethereum MEV-boost (such as arbitrage, bribery, attacks, etc.), and the incentives of the builder strategies are also need to consider to ensure stability and security of the network.

Ethereum

No substantial progress has been seen so far, but judging from the evolution of the existing Ethereum architecture, there is a high probability that the same route as Polygon will be adopted

TRON

The difference between TRON and the existing EVM chain: In addition to the TVM module which is EVM-compatible, TRON also has many independent native transaction types. The native transactions are classified into multiple categories, and the types may continue to be expanded in the future, so if TRON wants to achieve parallel execution, not only the TVM but also native transactions need to be considered.

The following are the points that need to be focused on:

• Benefits of parallel execution: Each chain has its own characteristics. Because Aptos uses the Move virtual machine, one feature of this virtual machine is that account data is independent, so optimistic execution theoretically will introduce greater benefits. But for EVM chains such as BSC and Polygon, hot contracts often occupy the main traffic on the chain. BSC claims that the transaction conflict rate on its chain is as high as 30%. TRON is currently the most popular chain for USDT circulation, and there are also hot contracts, so it needs to be confirmed the conflict rate of transactions on TRON, to confirm the value of parallel execution implemented on TRON
• The detailed parallel execution implementations of the above blockchains
• Parallel TVM: Considering that there is no big difference between TVM and EVM, the parallel execution strategy of TRON may be more biased towards BSC or polygon, not Aptos
• Parallel native transactions: It is necessary to sort out the parts of TRON native transactions that involve global state changes and try to eliminate them. For example, each transfer transaction will update the burn address, resulting that all transfer transactions cannot be executed in parallel
• Whether to adopt the builder module: The advantage is that the repeated calculations are unnecessary and higher performance is achieved with an external builder module to propose the block. The disadvantage is that additional complexity is introduced, which needs to be adapted in terms of security, economic model, compatibility, etc.

There are more details that need to be discussed. Hope more devs can join and make a deal.

Implementation

• TODO

Do you have ideas regarding the implementation of this feature?
Are you willing to implement this feature?

[asi90sp]

Ok

[jwrct]

At present, the maximum throughput of Tron's system is already quite high, and the current business volume is sufficient for Tron to cope with. So do we still need to consider implementing parallel execution of transactions, as it may require significant changes to the system? Of course, exploring performance improvements in the system is still commendable.

[lurais]

That sounds good, but to adopt the builder module shall be the final solution to improve the performance , as there is a certain limit of the hardware.

[tomatoishealthy]

At present, the maximum throughput of TRON's system is already quite high, and the current business volume is sufficient for Tron to cope with. So do we still need to consider implementing parallel execution of transactions, as it may require significant changes to the system? Of course, exploring performance improvements in the system is still commendable.

There are a few points to consider:

1. At present, the maximum TPS of TRON under the testnet is about 1k-3k (meaning that a single block may package 3K-9K transactions), depending on the complexity of the transaction. Considering that the TPS of the testnet is obtained under ideal conditions, there is a high probability that the TPS of the mainnet will not reach this level
2. The blockchain industry is currently on the rise, and more and more traditional businesses are migrating to the chain. According to the previous round of bull-bear comparison, the activity on TRON has increased by about 10X. We are currently in a bear market, the average number of transactions packaged in blocks on the TRON mainnet this year is about 300. According to a prediction based on previous data, if the activity on the chain in the next round of bull market increases by 10 times, the load on the mainnet will have a high probability of reaching the limit
3. Scaling has always been a core topic for the blockchain. Similar to the traditional Internet, the scaling is divided into horizontal scaling (such as rollup&sharding) and vertical scaling (such as parallel execution, hardware upgrade, etc.). Parallel execution should be more like vertical scaling. Horizontal scaling is another topic that needs to be discussed separately in another issue
4. Parallel execution is a relatively big topic, and there will be many changes involved, so it needs to be discussed and designed in advance

In summary, I think we should continue to work hard in both directions to ensure that TRON can always meet current and future market needs

Some references: tx statistics

[tomatoishealthy]

That sounds good, but to adopt the builder module shall be the final solution to improve the performance , as there is a certain limit of the hardware.

Partially agree.
For parallel execution, the builder model may have better performance, but it is more complicated and requires introducing some additional modules. The additional required modules should be discussed in the next stage.

There is always a bottleneck in the performance of a single node. Even if the builder model is adopted, the configuration of the builder node cannot make a good measurement standard. If the builder packs a very huge block, even if the fullnode uses parallel execution, it may not be able to validate the entire block in time.

Regardless of whether the builder model is used or not, some common modules are necessary for parallel execution, such as task dispatcher, conflict detection engine, multi-chain-fork memory management, etc. So I think we need to divide parallel execution into multiple stages, implement different modules in each stage, and determine whether to use the builder model based on experimental data

[tomatoishealthy]

Even if we cannot determine the final plan now, some work should be done.

• Architecture Research
  Parallel execution affects two logics: the sync stage and the proposal stage. At present, the parallel execution of Aptos takes effect in the sync stage and the proposal stage, while Polygon currently only takes effect in the sync stage, and BSC hopes to take effect in both stages, but parallel execution for the proposal stage has not yet been implemented in the current version. The principles of their design, the progress achieved, future plans, and the difficulties encountered in the implementation process require in-depth research, which has great value for TRON

• VM Research
  In theory, the optimization effect of parallel execution largely depends on the conflict rate of transactions. Aptos parallel execution adopts the assumption of optimistic execution, and claims that adopting an optimistic model is reasonable on Move, Polygon is inspired by Aptos, and BSC is an independent design. They all have different characteristics in detail. The VM layer of Aptos is Move, Polygon and BSC are EVM. Do the storage model and the way of reading and writing of the virtual machine have an impact on the implementation of the parallel execution engine? This may require a comparison between Move and EVM

• The order of transaction
  Unlike the EVM chain, TRON currently does not have an account nonce, and the ordering of transactions in the block is currently random, and does not use fee priority. If parallel execution is adopted, whether the transaction on-chain behavior is consistent with before is also an issue that needs attention: such as whether the transaction can be packaged into the block as before, the order of transaction packaging, etc.

• Global state and conflict rate
  TRON currently has a variety of transactions, and some transactions involve changes in the global state, which makes these transactions unable to be parallelized. The following things may need to be done

  • Sort out the logic of the global state changes in all types of current TRON transactions (the principle of judging transaction conflicts also needs to be discussed in depth)
  • Determine whether these logics can be optimized to avoid reading and writing of global state
  • Statistics of the current transaction conflict rate on TRON mainnet, then inferring the conflict rate after optimization

• Multi-fork state management
  TRON currently keeps the latest state data in memory and organizes them in a linked list, but it only keeps the data of the main fork, and does not store the state data of other forks, which indirectly leads to the inability to natively support parallel transaction state data reservation. Therefore, it may be necessary to refactor the existing in-memory database to support multi-fork data storage

• the effect of transaction cache
  There is a big difference between TRON and the above chains. TRON performs a transaction verification during the broadcast phase, and the data involved in the verification will be loaded into the cache. When the block is packaged, most of the data involved in the transaction is almost in the memory, so it also indirectly speeds up the performance of the block package. Based on this scenario, whether the performance improvement brought by parallel transactions will be as obvious as that of other chains is a topic that needs to be further discussed

At present, these are some key points that need to be followed up continuously. If there are new additions, I will continue to add them later. Anyone interested in parallel execution can participate in the discussion and even claim some of the work. Meanwhile, any valuable suggestion is welcome

[xxo1shine]

This is a good idea, the function implementation is a bit complicated, if it can be successfully implemented, there will be a big leap in performance, looking forward to the solution.

[tomatoishealthy]

Architecture Research

For BSC, their parallel execution v1 seems to not achieve a good performance, and they are planning the parallel execution v2 to improve the performance to an acceptable level.

Only as a personal opinion, the lifecycle of a transaction can be divided into three stages:

• Validation: If this stage just verifies signature/nonce/balance..., I think this stage can be executed parallelly as this stage doesn't do any state change.
• Execution: In this stage, transactions are ordered and there are dependencies between them, so there are huge challenges for parallel execution.
• Finalization: This stage will merge all the modifications of transactions into the world state.

BSC doesn't do well in the Execution stage, As the BEP130 describes Parallel 1.0 will not execution next transaction until the previous transaction finalized, seems they are not truly parallel execution. Maybe I'm wrong, but can't find more information from their design specification, more research should be done to confirm this speculation, and look forward to the design of V2.

We should dive into Aptos and Polygon deeply, also with Move&EVM, as they claimed that they all achieved a good improvement in performance.

[lurais]

As far as I know, aptos uses move to develop contracts as the resource model it uses can disperse the corresponding assets into multiple account storages, compared with the contract asset model used by evm, it can better support parallel transaction execution. The evm model stores all assets in a contract storage, which means that every time the state is modified, the method provided by the same contract needs to be called, which limits its transaction parallelism. Of course, these need further confirmation. I think the next step is reading about the details of these two implementations.

[tomatoishealthy]

For Aptos, the following is the description in the paper:

Check done: if 𝑉 and 𝐸 are empty and no other thread is performing a task, then return.
Find next task: Perform the task with the smallest transaction index 𝑡𝑥 in 𝑉 and 𝐸:

1. Execution task: Execute the next incarnation of 𝑡𝑥. If a value marked as estimate is read, abort execution and add 𝑡𝑥 back to 𝐸. Otherwise:
   • If there is a write to a memory location to which the previous finished incarnation of 𝑡𝑥 has not written, create validation tasks for all transactions ≥ 𝑡𝑥 that are not currently in 𝐸 or being executed and add them to 𝑉 .
   • Otherwise, create a validation task only for 𝑡𝑥 and add it to 𝑉 .
2. Validation task: Validate the last incarnation of 𝑡𝑥. If validation succeeds, continue. Otherwise, abort:
   • Mark every value (in the multi-versioned data-structure) written by the incarnation (that failed validation) as an estimate.
   • Create validation tasks for all transactions > 𝑡𝑥 that are not currently in 𝐸 or being executed and add them to 𝑉 .
   • Create an execution task for transaction 𝑡𝑥 with an incremented incarnation number, and add it to 𝐸.

I would like to make a detailed supplement to the above content. The following are all personal opinions and may contain misleading information.

Spec:

• incarnation: Each transaction may be executed multiple times due to conflicts. The incarnation represents the status of the transaction at the time of each execution, and each new incarnation uses a pair of a transaction index and an incarnation number to versioned
• incarnation version: a pair of a transaction index and an incarnation number
• read-set: Every incarnation maintains an individual read-set
• write-set: Incarnations share a global write-set (to be determined, why the read-set is individual and the write-set uses a shared memory[1])
• transaction order: every transaction marked an index which is its order in the block
• 𝐸: the set of transactions that need to be executed
• 𝑉: the set of transactions that require verification

Step 1:
All transactions are in 𝐸, then we can launch multiple tasks to execute them parallelly, All the reading data was marked in the read-set, and the updated data into the write-set for an incarnation, the data in the set is associated with an incarnation version, so we can detect whether a transaction read stale data or two transactions write conflict. For example, Tx1 updates the balance of accountA, and Tx2 depends on accountA as its input, we can detect the conflict by comparing the incarnation version of accountA in the read-set of Tx2 and the write-set of Tx1.

For getting the data that the incarnation needs, I think the task should query the write-set first, if not exist, then query the database to make sure the incarnation always can get the newest data, this also may be the reason why the write-set uses a shared memory.

Step 2:
Tx1 is the special case as there is no transaction in front of it, so it always can be executed successfully. For the common case, we should focus on the transactions behind it. After executing Tx2, we put Tx2 in 𝑉, get its read&write set, and then start the Validation task. How to determine whether Tx2 is valid? I think the validation process is as described above:

• checking whether there is stale data in the read-set of Tx2 by comparing it with the write-set of Tx1
• checking whether there is an overlap between the Tx2's write-set with Tx1's write-set.[2]
• Is there any other conditions to be checked?[3]

Step 3:
If Tx2 is valid, as we all know Tx1 is always valid, then we can determine that Tx1&Tx2 are finished and won't be reverted. There is a rule that how to determine a transaction won't be reverted, I think it should be:

• all transactions in front of it are valid successfully
• this transaction itself also is valid successfully

Step 4:
If Tx2 valid failed, then it's time to look back to the description of the Validation task in the paper. No more repetition here, the purpose of the three steps is to make sure the transactions afterward should be checked again. Tx2's write-set will be marked as estimate, Tx3 also should be re-valid(It is very important).

Tx2 should also be put into 𝐸 and re-execute, during the re-execution:

• if the task detects Tx2 has an estimate read(despite in this situation it's may impossible as Tx1 always success), the re-execution should be aborted.
• if the re-execution is successful
  • If there is a write to a memory location to which the previous finished incarnation of 𝑡𝑥1 has not written, create validation tasks for all transactions ≥ 𝑡𝑥 that are not currently in 𝐸 or being executed and add them to 𝑉: Re-valid is very reasonable for all afterward transactions because we can't know these transactions ever refer the stale data for the new memory location.
  • Otherwise, create a validation task only for 𝑡𝑥 and add it to 𝑉 .: This rule works depending on rule 2 of the Validation task. When Tx2 valid failed, a re-valid task was already created for Tx3, this task will check if Tx3 has any dependency on Tx2. if so, the re-valid task will also put Tx3 into 𝐸. So depending on the above conditions, if Tx2 does not write a new memory location, we can ensure that Tx3 will not have conflict with Tx2. This design also can reduce the cost of re-validation.

Remember: always re-valid not re-execute, if re-valid failed, then do re-execute.

Note: To achieve a better performance, the incarnation will mark the write-set as estimate immediately, and when the following incarnation does an execution task and reads the estimate data, it will also be aborted immediately to avoid a future failed validation.

There I have a question: Can Tx3 read the intermediate write-set data of Tx2 when Tx2 does not finish the execution task?[4]

The above is my rough understanding of Aptos STM. This is a supplement to the paper, and the detailed content also needs to refer to the paper

There are still many doubts that need to be studied in depth. The above square brackets are currently known doubts. I'll rephrase them with some extra doubts.

• [1] Why the read-set is individual and the write-set uses a shared memory?
• [2] How to determine whether a transaction is valid? checking whether there is an overlap between the current write-set with the previous write-set?
• [3] The same as above, Are there any other conditions to be checked?
• [4] Can an incarnation read the previous intermediate write-set data even when they do not finish the execution task?
• [5] What is the read&write-set data structure like, and how to ensure efficient memory and concurrent access?
• [6] How to maintain task threads for execution and verification, and how to schedule tasks efficiently？

[tomatoishealthy]

To reiterate a point: it is important to implement parallel execution only if it can actually bring benefits.

Whether parallel execution can really improve TPS, or whether the ratio of performance improvement is good enough, may need to be investigated in advance, otherwise it may end up being nothing.

TRON has one big difference from other chains: all transactions in the broadcast phase will be pre-executed and put into two queues, called: pendingQueue and repushQueue (the difference between the two queues is not the point, as long as you know the broadcast phase transactions are stored in these two queues)

Here are some important key points:

• When transactions are packaged into a block, the validator will obtain the transactions from the queues, re-execute and package them. There are two restrictions on packaging.
  • The total time limit is not allowed to exceed 750ms
  • Block size is not allowed to exceed 2M
• The current block interval is 3s, which means that in addition to block production, the remaining 2s+250ms can be used for transaction pre-execution, and all transactions in the queue are filled in at this stage.
• Due to pre-execution, the data is loaded into the cache, resulting in the transaction re-execution time during packaging being shorter than the broadcast verification phase.

Parallel execution is a huge project. In the first stage, it may only be used in the block production stage, which raises a question: based on cache reuse, whether the number of transactions processed serially within 750ms is less than 2s+250ms. If not, even if the transactions in the block generation process are executed in parallel, TPS will not be effectively improved.

This issue needs to be followed up, and relevant data will be posted to prove it later.

[lvs007]

I think that both 750ms and 2M sizes can be considered for optimization, provided of course that it is based on full justification and experimentation.