As of today, the multi-core processor architecture has become a major trend in the industry, as parallelization technology can fully utilize the potential of CPUs. ABEYCHAIN’s Parallelizing Transaction Execution mechanism uses the advantages of multi-core processors to the fullest by enabling transactions in blocks to be executed in parallel as much as possible.
The traditional transaction execution mechanism works mostly as such: transactions are read one by one from the block. After each transaction is executed, the state machine will move to the next state until all transactions are executed sequentially, as shown in the following figure:
It is obvious that this method of transaction execution is not very performance optimal. Even if the two transactions do not intersect, they can only be executed sequentially. In practical applications, splitting unrelated transactions and executing them in parallel will greatly optimize execution efficiency.
Issue 1: how to ensure that all nodes can reach the same state after execution in the same block?
In the traditional transaction execution mechanism, each time a transaction is executed, the state root will change once. After all transactions are executed, the final state root represents the current state of the blockchain.
When transactions are executed in parallel, the traditional method of calculating state root will no longer be applicable. The transactions need to be executed first, and the history of the state change of each transaction is recorded afterwards.
After all transactions are executed, a state root is calculated based on these historical records. This ensures that even if the transaction is executed in parallel, the final consensus node can still reach consensus.
Issue 2: how to recognize if there is dependency between two transactions?
If two transactions have no actual dependency between each other but are deemed so, this will cause unnecessary loss of performance efficiency. On the contrary, if the two transactions rewrite the state of the same account but are executed in parallel, the final state of the account may be uncertain. Therefore, the determination of dependency is an important issue that affects performance and even indicates whether the blockchain can work normally.
We can easily tell whether two transactions are dependent by observing the address of the sender and receiver, such as the following example transactions: A→B, C→D, D→E. Here, you can see that transaction D→E depends on the result of transaction C→D, but transaction A→B has little relationship with the other two transactions, therefore can be executed in parallel.
This analysis is correct in a blockchain that only supports simple transactions, but it may not be as accurate once it is placed in a Turing-complete blockchain that runs smart contracts – because it is impossible to know exactly what is in the transaction contract written by the user. Transaction A->B seems to have nothing to do with the account status of C and D. However, in reality party A is a special account. When each transaction is transferred through A’s account, transaction fees must be deducted from party C’s account first. In this scenario, all three transactions are actually related, so they cannot be executed in parallel.
In order to resolve this type of situation, we adopt a trial and error method. Specific steps are as such:
- Preparing: convert all transactions to “message” type;
- Grouping: group transactions according to associated address;
- Executing: execute each transaction group in parallel;
- Check for conflicts: check whether the transaction groups are in conflict according to returned results. If there is a conflict, roll back the conflicting transactions, then regroup and re-execute.
- Collect results: collect the execution results of each group, update the tree, and generate the state root
With the above method, transaction-related issues in parallel transactions can be resolved. Of course, inaccurate initial grouping, transaction rollback may still cause performance inefficiency at times. But in most cases, transactions are irrelevant. It is feasible to accurately group and execute transactions in parallel to improve transaction execution efficiency.
在多核处理器架构已经成为主流的今天，利用并行化技术充分挖掘CPU潜力是行之有效的方案。ABEY Chain设计并实现了Parallelizing Transaction Execution ，它能充分发挥多核处理器优势，使区块中的交易能够尽可能并行执行。
在传统的交易执行方案中，每执行一笔交易，state root便发生一次变迁，所有交易执行完后，最终的state root就代表了当前区块链的状态。
当交易被并行且乱序执行后，传统计算state root的方式显然不再适用。需要先执行交易，将每笔交易对状态的改变历史记录下来，待所有交易执行完后，再根据这些历史记录再算出一个state root，由此就可以保证即使并行执行交易，最后共识节点仍然能够达成一致。
- check conflict，根据返回的结果检查交易组是否冲突，如果冲突，则就滚冲突的交易并重新分组并行执行，
- collect result，收集各组执行结果，更新trie，并生成state root