ErlangShen: Efficient Transaction Execution Mechanism for Graphical Blockchain Based on Pipeline with Low Access Cost
-
摘要: 基于有向无环图(DAG)的图式区块链能够显著提升系统性能，已成为近年来业界的研究热点。相较于传统串行化的链式区块链，图式区块链可在单位时间内并发处理大量事务从而提升吞吐量。随着事务量的激增，图式区块链面临事务执行效率低的瓶颈问题，即海量事务执行对状态数据访问的需求大幅增加，导致高昂的输入/输出(I/O)开销。实现低I/O访问主要包括两方面的全新挑战：一方面，图式区块链若直接采用传统的事务预取机制，将因执行逻辑不一致引入大量的陈旧读；另一方面，针对不同账户的状态访问会在默克尔树的高层节点中造成重复的I/O开销。为此，本文设计基于流水线的图式区块链高效事务执行机制—ErlangShen，包括Epoch粒度的状态预取机制和默克尔高层路径缓存机制来分别减少陈旧读的数量和重复的I/O开销。具体而言，ErlangShen充分分析并利用了事务访问频次的冷热特征，将访问热事务的逻辑执行与冷事务的状态预取并行化，以避免状态预取对事务执行的影响。此外，为了进一步提升事务执行的吞吐量，根据访问冷热状态事务的特性设计了定制化的并发控制方法。实验结果表明，ErlangShen机制能够减少约90%的陈旧读数量，与最新图式区块链事务处理机制Nezha相比，可将性能提升3～4倍。Abstract: Directed Acyclic Graph(DAG)-based blockchain can significantly improve system performance and have become a research topic in both academia and industry. Compared with the traditional chain-based blockchains with serialization, DAG-based blockchains can process multiple blocks concurrently to package significant transactions into the chain. With the surge in transaction throughput, DAG-based blockchain faces the issue of low transaction execution efficiency, i.e., the demand for state data access for massive transaction execution increases dramatically, resulting in high Input/Output(I/O) overhead. Enabling low I/O state access mainly encounters two new challenges. On the one hand, if DAG-based blockchain directly adopts the traditional state prefetch mechanism, it will introduce a large number of stale reads due to inconsistent execution logic. On the other hand, state access for different accounts causes duplicate I/O overhead in the upper nodes of the Merkle tree. To this end, an efficient transaction execution mechanism based on pipelining – ErlangShen is designed, including the epoch granularity state prefetch mechanism and Merkle high-level path buffer mechanism to reduce the number of stale reads and duplicate I/O overhead, respectively. Specifically, ErlangShen leverages the complicated logic and severe conflicts of transactions accessing hotspot states to parallelize the execution of hotspot transactions and the prefetch of states accessed by cold transactions, to avoid the implication of the state prefetching on the transaction execution. Furthermore, the customized concurrency control methods is designed according to the data access pattern of hotspot and cold states to further improve the system throughput. Experimental results show that ErlangShen can reduce the number of stale reads by about 90% and improve transaction processing performance by 3～4x compared to Nezha, the state-of-the-art DAG-based blockchain transaction processing solution.
-
[1] ZETZSCHE D A, ARNER D W, and BUCKLEY R P. Decentralized finance[J]. Journal of Financial Regulation, 2020, 6(2): 172–203. doi: 10.1093/jfr/fjaa010. [2] 郝敏, 叶东东, 余荣, 等. 区块链赋能的6G零信任车联网可信接入方案[J]. 电子与信息学报, 2022, 44(9): 3004–3013. doi: 10.11999/JEIT220370.HAO Min, YE Dongdong, YU Rong, et al. Blockchain empowered trustworthy access scheme for 6G zero-trust vehicular networks[J]. Journal of Electronics & Information Technology, 2022, 44(9): 3004–3013. doi: 10.11999/JEIT220370. [3] 张海波, 徐蓬勃, 王汝言, 等. 区块链下基于蛛网模型的新能源汽车能源交易机制研究[J]. 电子与信息学报. doi: 10.11999/JEIT221386.ZHANG Haibo, XU Pengbo, WANG Ruyan, et al. Research on energy trading mechanism of new energy vehicles based on cobweb model under blockchain[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT221386. [4] 潘晨, 刘志强, 刘振, 等. 区块链可扩展性研究: 问题与方法[J]. 计算机研究与发展, 2018, 55(10): 2099–2110. doi: 10.7544/issn1000-1239.2018.20180440.PAN Chen, LIU Zhiqiang, LIU Zhen, et al. Research on scalability of blockchain technology: Problems and methods[J]. Journal of Computer Research and Development, 2018, 55(10): 2099–2110. doi: 10.7544/issn1000-1239.2018.20180440. [5] NAKAMOTO S. Bitcoin: A peer-to-peer electronic cash system[EB/OL]. https://bitcoin.org/bitcoin.pdf, 2023. [6] BAIRD L. The swirlds hashgraph consensus algorithm: Fair, fast, byzantine fault tolerance[EB/OL]. https://www.swirlds.com/downloads/SWIRLDS-TR-2016-01.pdf, 2016. [7] LEMAHIEU C. Nano: A feeless distributed cryptocurrency network[EB/OL]. https://content.nano.org/whitepaper/Nano_Whitepaper_en.pdf, 2018. [8] Taraxa whitepaper[EB/OL]. https://docs.taraxa.io/tech-whitepaper/abstract, 2023. [9] Aleph zero whitepaper[EB/OL]. https://docs.alephzero.org/aleph-zero/explore/whitepapers, 2023. [10] CHOI S M, PARK J, NGUYEN Q, et al. Fantom: A scalable framework for asynchronous distributed systems[EB/OL]. https://doi.org/10.48550/arXiv.1810.10360, 2018. [11] LI Chenxing, LI Peilun, ZHOU Dong, et al. A decentralized blockchain with high throughput and fast confirmation[C]. 2020 USENIX Annual Technical Conference, 2020: 515–528. [12] YU Haifeng, NIKOLIĆ I, HOU Ruomu, et al. OHIE: Blockchain scaling made simple[C]. 2020 IEEE Symposium on Security and Privacy, San Francisco, USA, 2020: 90–105. doi: 10.1109/SP40000.2020.00008. [13] XU Jie, CHENG Yingying, WANG Cong, et al. Occam: A secure and adaptive scaling scheme for permissionless blockchain[C]. 2021 IEEE 41st International Conference on Distributed Computing Systems, Washington, USA, 2021: 618–628. doi: 10.1109/ICDCS51616.2021.00065. [14] 高政风, 郑继来, 汤舒扬, 等. 基于DAG的分布式账本共识机制研究[J]. 软件学报, 2020, 31(4): 1124–1142. doi: 10.3969/j.issn.1000-9825.2020.04.018.GAO Zhengfeng, ZHENG Jilai, TANG Shuyang, et al. State-of-the-art survey of consensus mechanisms on DAG-based distributed ledger[J]. Journal of Software, 2020, 31(4): 1124–1142. doi: 10.3969/j.issn.1000-9825.2020.04.018. [15] KEIDAR I, KOKORIS-KOGIAS E, NAOR O, et al. All you need is DAG[C]. 2021 ACM Symposium on Principles of Distributed Computing, Italy, 2021: 165–175. doi: 10.1145/3465084.3467905. [16] SPIEGELMAN A, GIRIDHARAN N, SONNINO A, et al. Bullshark: DAG BFT protocols made practical[C]. 2022 ACM SIGSAC Conference on Computer and Communications Security, Los Angeles, USA, 2022: 2705–2718. doi: 10.1145/3548606.3559361. [17] DANEZIS G, KOKORIS-KOGIAS L, SONNINO A, et al. Narwhal and tusk: A DAG-based mempool and efficient BFT consensus[C]. 17th European Conference on Computer Systems, Rennes, France, 2022: 34–50. doi: 10.1145/3492321.3519594. [18] 陈友荣, 章阳, 陈浩, 等. 面向车联网异构节点的区块链高效一致性共识算法研究[J]. 电子与信息学报, 2022, 44(1): 314–323. doi: 10.11999/JEIT201065.CHEN Yourong, ZHANG Yang, CHEN Hao, et al. Efficient consistency consensus algorithm of blockchain for heterogeneous nodes in the internet of vehicles[J]. Journal of Electronics & Information Technology, 2022, 44(1): 314–323. doi: 10.11999/JEIT201065. [19] POPOV S. The tangle[EB/OL]. http://cryptoverze.s3.us-east-2.amazonaws.com/wp-content/uploads/2018/11/10012054/IOTA-MIOTA-Whitepaper.pdf, 2017. [20] SOMPOLINSKY V, LEWENBERG Y, and ZOHAR A. SPECTRE: A fast and scalable cryptocurrency protocol[J]. IACR Cryptology ePrint Archive, 2016, 2016: 1159. [21] BAGARIA V, KANNAN S, TSE D, et al. Prism: Deconstructing the blockchain to approach physical limits[C]. 2019 ACM SIGSAC Conference on Computer and Communications Security, London, UK, 2019: 585–602. doi: 10.1145/3319535.3363213. [22] WOOD G. Ethereum Yellow Paper: A formal specification of Ethereum, a programmable blockchain[EB/OL]. https://ethereum.github.io/yellowpaper/paper.pdf, 2023. [23] ANDROULAKI E, BARGER A, BORTNIKOV V, et al. Hyperledger fabric: A distributed operating system for permissioned blockchains[C]. 13th European Conference on Computer Systems, Porto, Portugal, 2018: 30. doi: 10.1145/3190508.3190538. [24] PENG Zeshun, ZHANG Yanfeng, XU Qian, et al. NeuChain: A fast permissioned blockchain system with deterministic ordering[J]. Proceedings of the VLDB Endowment, 2022, 15(11): 2585–2598. doi: 10.14778/35517 93.3551816. [25] KIM J Y, LEE J, KOO Y, et al. Ethanos: Efficient bootstrapping for full nodes on account-based blockchain[C]. 16th European Conference on Computer Systems, UK, 2021: 99–113. doi: 10.1145/3447786.3456231. [26] LI Chenxing, BEILLAHI S M, YANG Guang, et al. LVMT: An efficient authenticated storage for blockchain[C]. 17th USENIX Symposium on Operating Systems Design and Implementation, Boston, USA, 2023: 135–153. [27] PONNAPALLI S, SHAH A, BANERJEE S, et al. RainBlock: Faster transaction processing in public blockchains[C]. 2021 USENIX Annual Technical Conference, 2021: 333–347. [28] TAFT R, MANSOUR E, SERAFINI M, et al. E-store: Fine-grained elastic partitioning for distributed transaction processing systems[J]. Proceedings of the VLDB Endowment, 2014, 8(3): 245–256. doi: 10.14778/2735508.2735514. [29] XIAO Jiang, ZHANG Shijie, ZHANG Zhiwei, et al. Nezha: Exploiting concurrency for transaction processing in DAG-based blockchains[C]. IEEE 42nd International Conference on Distributed Computing Systems, Bologna, Italy, 2022: 269–279. doi: 10.1109/ICDCS54860.2022.00034. [30] THOMSON A, DIAMOND T, WENG Shuchun, et al. Calvin: Fast distributed transactions for partitioned database systems[C]. 2012 ACM SIGMOD International Conference on Management of Data, Scottsdale, USA, 2012: 1–12. doi: 10.1145/2213836.2213838. [31] CHEN Zhihao, QI Xiaodong, DU Xiaofan, et al. PEEP: A parallel execution engine for permissioned blockchain systems[C]. 26th International Conference on Database Systems for Advanced Applications, Taipei, China, 2021: 341–357. doi: 10.1007/978-3-030-73200-4_24. [32] Ethereum browser[EB/OL]. https://etherscan.io/chart/address, 2023. -
下载:
图(12)
计量
- 文章访问数: 230
- HTML全文浏览量: 103
- PDF下载量: 50
- 被引次数: 0
