Correlation and Workload-Based Transaction Allocation Algorithm for Blockchain Sharding
Guixia Xiao, Normalia Samian, Winston K.G. Seah, Mohd Izuan Hafez Ninggal, Masnida Binti Hussin, Jyoti Sahni · 2024
Most existing transaction sharding technologies allocate transactions randomly or based on transaction addresses, leading to imbalanced workloads and high ratio of cross-shard transactions (CST). The uneven workload makes it impossible for blockchain to fully utilize resources for transaction processing, which degrades system throughput. CST incur additional overheads in communication, verification, and processing, increasing block confirmation latency. This paper proposes a blockchain sharding transaction allocation algorithm known as correlation and workload-based transaction allocation (CWTA) to address the above issues. CWTA regularly pumps a certain number of pending transactions from the transactions pool to establish a multiple-directed transaction graph (MDTG) and achieves faster allocation efficiency by quickly gathering the out-edges of each account based on MDTG. This process has successfully changed the distribution mode of transactions from one-by-one to group-by-group which depends on the correlation between the groups for current and upcoming workloads of each shard. CWTA has demonstrated its effectiveness through abundant transaction allocation results with 2-16 shards. Compared to similar existing work, CWTA can achieve a much more balanced transaction workload and less allocation time without increasing the CST ratio which denotes better scalability, and achieve better throughput.