本帖最后由 中国计算机学会 于 2024-4-19 14:14 编辑
摘要—图式区块链具有并行特点，有效提升系统吞吐量，已成为区块链领域的重要发展趋势。随着链上数据量呈现爆炸式增长，现有图式区块链系统面临存储可扩展性瓶颈难题。本文阐述了区块链存储可扩展性的问题内涵，分析了研究现状与挑战，介绍了团队自主研发的可扩展图链存储系统的弹性数据模型、并发事务处理机制和高效可信查询方法。
肖 江（华中科技大学）
张世桀（华中科技大学）
周一帆（华中科技大学）
关键词 ：图式区块链 可扩展性 存储模型 事务处理 可信查询 引言 区块链是一种分布式数据存储新范式，能够在多主体“弱信任”环境中实现数据的一致存储、防篡改、可追溯。面向金融、电商等高频次、高并发应用需求，现有以比特币和以太坊为代表的链式区块链系统性能严重不足，交易速率仅为7~15 TPS（Transaction Per Second，每秒事务处理量）。为了提升系统吞吐量，图式区块链被提出，典型代表是学术界的Conflux[1]和工业界的IOTA[2]，吞吐量提升3个数量级。如图1所示，图式区块链具有并行特点，并发处理效率高、验证计算开销低，成为区块链领域的重要国际学术前沿。
图式区块链存储新模式 区块链存储是一种高可靠的分布式存储，系统中所有节点都存储全部副本数据，或称为完整历史数据，这种全副本特性使任何一个节点都无法篡改数据[3]，同时支持可追溯查询，然而这也导致存储开销高。相较于基于串行拓扑的链式区块链，图式区块链系统的底层存储采用并行拓扑结构，单位时间可并行处理多个区块，显著提升了系统吞吐量。但是，图式区块链系统的高并发特性，使单位时间存储的区块数量多、规模大，提升吞吐量的同时严重增加了存储开销。例如，当吞吐量达到2000 TPS时，全节点每年的存储开销高达15 TB。因此，图式区块链的存储可扩展性是制约其发展的关键科学问题。 图式区块链的存储可扩展性主要面临存储开销大、处理效率低、查询验证难等瓶颈难题。 区块链全量存储模型无法适应海量数据规模。采用传统的“纵向扩展”思路并不能有效缓解图式区块链的存储压力，因为增加单节点的存储资源，容易导致其成为“超级节点”。在异构节点环境下，能够存储如此大量数据的节点越来越少，使系统呈现集中化趋势，带来了安全隐患。而“横向扩展”也不适用于图式区块链系统，因为新增节点不仅需要存储新增的区块，还须同步存储所有的历史区块数据，无法缓解存储压力。 区块链存储性能受限于事务执行处理能力。高并发的图式区块链存储模型在一定程度上提升了存储性能，但其较为固定的拓扑结构导致系统无法面向众多应用的动态负载提供与之匹配的存储性能。因此，动态变化的图式区块链负载对构建弹性可扩展的图式存储模型提出了挑战。同时，图式区块链存储系统的高并发性加剧了数据访问的倾斜程度，使并发冲突事务呈现爆炸式增长。如何应对图式区块链中的大规模冲突事务，设计高效的并发控制与事务执行处理机制成为了重要挑战。 区块链查询的可验证性和高效性难以同时保证。可验证索引结构可以有效保证区块链查询检索的可验证性。然而，当前的链式区块链索引结构设计未充分考虑图式区块链的并行拓扑结构，图式区块链的并行出块模式增加了对多个并发区块进行查询验证的难度。此外，大量的并发冲突事务也会导致查询阻塞多，索引的验证与更新时延高、开销大。因此，如何面向高并发的图式存储模型设计高效可验证的查询索引机制是一项重大挑战。 国内外发展现状 本文从区块链存储优化技术、共识执行方法以及查询检索机制这三个方面介绍当前区块链存储可扩展性的主流解决方案。 区块链存储优化 在传统链式区块链存储模型中，每个区块创建回合仅有一个有效区块被提出，低效的串行出块模式严重制约了系统性能。为此，基于有向无环图（Directed Acyclic Graph，DAG）的图式区块链存储模型应运而生，即采用DAG拓扑结构组织历史交易或者区块以提升共识的并行性。现有图式区块链存储模型可分为朴素、基于主链和基于平行链三种。以IOTA为代表的朴素图式区块链采用以交易为粒度的存储模型，交易能够及时验证和上链，但是其拓扑结构的生长没有规则限制，无法确定交易全序。以Conflux[1]为代表的基于主链的图式区块链将所有的分叉区块组织成一个树图结构，并在其中选择一条权重最重的分叉作为主链，根据主链区块对其他区块的引用关系对其他区块进行确认和排序。在以Prism[4]为代表的基于平行链的图式区块链中，系统由若干条相对独立的单链相互引用形成，使用默克尔树（Merkle tree） 验证保证多链并发出块的安全性。上述图式存储模型虽然提升了共识性能，但带来了巨额的存储开销。 目前，国际学术界已对区块链可扩展存储进行了一系列探索和研究，但相关研究仅关注传统链式区块链，主要从系统协议层、数据编码层、存储引擎层进行优化。例如，华中科技大学提出了拼图式数据裁剪的系统协议层存储优化方案Jidar[5]，香港科技大学和中山大学分别提出了分片存储方案CoChain[6]和Pyramid[7]，微软印度研究院提出了轻量级移动区块链Blockene[8]，华东师范大学提出了面向数据编码层的存储引擎BFT-Store[9]，新加坡国立大学等提出了面向存储引擎层的ForkBase[10]等。 综上，现有图式区块链忽略了存储可扩展性的研究，难以应对高频次、高并发应用场景下的海量数据存储需求。同时，现有基于链式数据模型的可扩展存储方案主要面向链式结构中的一维依赖关系，无法适用于图式数据模型的多维依赖关系，因此难以应用到图式区块链系统中。 共识执行方法 面向图式区块链的共识算法未考虑并发事务处理带来的安全性问题，难以应对图式拓扑结构的动态性与高并发性带来的挑战。在共识算法方面，目前的一些研究工作主要利用图式拓扑的并发特性提升共识效率。香港科技大学提出了移动DAG分布式账本Mneme[11]，并设计了两种共识协议；以色列理工学院提出了一种融合DAG的拜占庭共识算法DAG-Rider[12]；新加坡国立大学提出了基于DAG结构的共识机制OHIE[13]；伦敦大学学院提出了数据广播与共识解耦的方法Narwhal[14]，以及最优轮次为两轮的改进可信广播协议；Aptos研究院提出了Bullshark[15]，针对DAG-Rider中共识轮次进行了优化，提高了共识机制在同步网络环境下的性能。这些面向图式区块链的共识算法忽略了对并发事务的处理，带来了安全性风险。 当前针对并发事务处理的研究工作主要面向的是链式区块链系统，优化目标包括提升事务处理效率和减少并发冲突两方面。为提升事务处理效率，布朗大学率先在智能合约并发执行方面进行了初步尝试，提出了一种可串行化的执行调度策略[16]；美国德克萨斯大学奥斯汀分校设计了一种面向公有链的事务处理方案RainBlock[17]；为减少并发事务冲突，德国萨尔大学提出了Fabric++[18]；新加坡国立大学等提出了一种并发控制方法FabricSharp[19]；宾夕法尼亚大学的FlexChain[20]以及公链项目Aptos提出的Block-STM[21]分别利用硬件资源与软件事务内存加速事务处理的执行流程。然而，传统链式事务处理方法受限于低效的串行链式结构，吞吐性能难以进一步扩展。华中科技大学团队提出了Nezha[22]，这是第一个面向图式区块链的并发事务处理机制，其通过挖掘的事务地址依赖关系提升并发控制效率，解决了图式区块链中事务冲突多的问题。 上述共识工作虽然在提升区块链系统性能方面取得了一定成效，但未考虑图式区块链拓扑结构动态增长对系统安全性的影响。此外，面向链式区块链存储模型的事务处理方法只能解决单个存储单元（如区块）内的冲突，无法应对图式拓扑中多个存储单元间的冲突，因此难以拓展到图式区块链系统中。 查询检索机制 区块链在金融、电子商务、供应链等应用领域中对交易数据查询有着迫切需求。现有关于区块链查询的研究工作主要针对传统链式拓扑，其目标可以分为提升查询效率和提供可验证查询功能两类。在提升查询效率方面，华东师范大学提出了SEBDB[23]，通过设计类SQL查询语句和索引结构提升查询效率；达姆施塔特工业大学（Technical University of Darmstadt）提出了BlockchainDB[24]，通过提供一个高效的查询接口方便用户进行查询请求。在提供可验证查询功能方面，香港浸会大学提出了Chameleon[25]和vChain+[26]，构建了两种可验证索引结构，分别实现关键字与布尔范围查询；华东师范大学提出的AuthQx[27]采用可信执行环境（Trusted Execution Environment，TEE）保证了查询过程的可验证性；华中科技大学针对多链溯源查询的可验证性问题提出了Vassago系统[28]，针对比特币历史交易数据的查询提出了轻量级可验证查询方法LVQ[29]。 综上，现有的区块链查询相关工作主要面向链式数据结构，针对图式数据模型的查询工作仍处于空白阶段。此外，现有的区块链高效查询相关工作虽有效提升了查询性能，但忽略了拜占庭网络环境中查询结果可验证的需求。可验证查询的相关工作依赖链式数据结构，难以推广到图式区块链系统中。 MorphDAG弹性可扩展图链存储系统
动态可扩展图式区块链分片存储模型 随着图式区块链系统吞吐量的提升，图式区块链的存储开销将大幅增加。传统状态分片存储机制通过并行存储处理多个分片的数据缓解存储压力，然而，其应用在图式区块链中仍面临两个关键难题：（1）如何设计动态分片机制以支持高效的跨分片交易处理；（2）如何设计跨分片验证方法以保证分片间的数据一致性。为此，我们提出了一种图式区块链动态存储模型SharDAG[31]。 如图3所示，SharDAG的核心思想是提出了基于跨分片替身账户缓存的自适应分片机制，根据实际的跨分片交易自适应地为资产接收者创建替身，所有跨分片的交易都可以在一个分片中处理，而无需跨分片通信。进一步地，为了保证这些“替身账户”被安全一致地聚合到原账户，我们提出了基于双模式的拜占庭容错跨分片验证机制，在保证了跨分片账户聚合消息传输和上链阶段的安全性和活性的同时，利用了图式区块链并发出块的特性，进一步降低了消息的上链延迟。实验结果表明，与基于国际前沿的BrokerChain分片机制的图式区块链相比，SharDAG可将吞吐量提升2.8倍；与未分片图式区块链BullShark相比，SharDAG可将存储开销降至13.3%，说明了SharDAG的高效跨分片事务处理能力和良好的存储可扩展性。
高效图式区块链事务处理方法 区块链众多应用场景中存在连续型事务的应用需求，连续型事务之间有着顺序依赖关系。然而，当前图式区块链在处理连续型事务时面临着事务依赖顺序与一致性难保证的难题。为此，我们提出了基于交互依赖存储模型的高效连续事务处理方法FLUID[32]。 FLUID的核心思想是以完整的连续事务作为数据模型单元代替单个事务，并在连续事务之间构建依赖关系，满足连续型事务处理的顺序性。如图4所示，我们首先建立了基于连续事务依赖跟踪的数据模型单元，每个交易子单元维护与前序交易的依赖关系。在完整的数据交易应用逻辑中，连续型事务将被强制按照交互依赖顺序执行、提交，连续型事务中独立的交易无法作为系统中的数据模型单元被后续交易连接。若存在有冲突的中间状态，将根据卖方确认的交易进行提交和丢弃。然后，我们提出了基于检查点的连续事务一致性验证机制。具体而言，先对数据模型单元进行校验和（checksum）计算，校验和融合了某个数据模型单元前序路径上的交易及路径信息，数据模型单元的校验和则是该顶点与其相连接顶点的校验和混合后的哈希，每个节点将在本地自行计算并维护所有交易的校验和。与图式区块链OHIE相比，FLUID可将连续事务处理的吞吐量性能提升1.5倍以上，将处理延迟降低两个数量级。
基于学习索引的高效可验证图式区块链查询机制 图式区块链的高并发区块特性使数据查询难以像传统链式结构那样依次遍历，根据图式结构采用广度优先或深度优先遍历策略存在查询效率低、验证难等问题。因此，我们提出基于纪元（epoch）间的学习索引和纪元内聚合布隆过滤器（Bloom filter）的高效可验证图式区块链查询机制Lever[33]。 Lever是针对图式区块链的时序数据特征，基于学习索引的高效查询机制设计的，加快了图式区块链数据的查询。如图5所示，当客户端向全节点发送查询请求时，全节点通过构建的学习索引快速定位查询数据所在的纪元区间。为了提升图式区块链纪元内区块的遍历速度，通过设计聚合布隆过滤器，快速过滤不存在查询数据的区块，提升查询效率。针对布隆过滤器可能存在的假阳性，采用排序默克尔树结构，客户端除了接收查询数据以外，会额外收到全节点返回的默克尔树分支作为可验证对象数据。该机制能够保证查询结果的高效性，并降低可验证对象的大小。实验结果表明，在不同区块数量下对CPU时间和查询延迟进行对比，相较于区块总计构建时间，学习索引的构建时间仅占1/104，相较于传统依次遍历方案，Lever的查询性能可以提升102倍。
未来展望 图式区块链系统的存储可扩展性研究已引起业界关注，其技术仍然面临诸多挑战。 支持数据要素可信流转的跨链区块链存储服务平台。需建立支持跨行业、跨领域的跨链可扩展区块链存储服务平台，打破多个区块链系统之间的信息互通壁垒，融合多链系统的存算能力，实现跨链数据要素的可信流转与共享存储，支撑数据资产等数据要素的确权、保护和价值传递，为数字经济高质量发展提供新动能和主引擎。 新硬件驱动的区块链高效存储执行方法。在图式区块链中，待处理的事务量成倍增长，状态数据急剧膨胀，当前软件层面的解决方案受限于系统的硬件资源难以进一步扩展系统的存储执行性能。因此，需融合NVM/RDMA/HTM等新型硬件的特性，对状态数据存储与事务执行进行软硬件协同优化，降低状态数据的存储开销以及访问磁盘的I/O开销，进一步提升存储执行效率。 融合人工智能的区块链异构数据智能查询技术。随着区块链应用场景的不断拓展与丰富，区块链数据呈现异构多源的特性，这对图式区块链系统支持的数据存储形式与查询功能提出了更高的要求。为支持多样化的数据存储形式与查询功能，需要探究人工智能赋能的异构多源数据查询索引机制，并实现丰富的链下数据库存储查询操作接口，以支撑需求多样、场景复杂的图式区块链上层应用。 ■
参考文献： [1] Li C, Li P, Zhou D, et al. A decentralized blockchain with high throughput and fast confirmation[C]// Proceedings of the 2020 USENIX Annual Technical Conference. 2020: 515-528. [3] Jin H, Xiao J. Towards trustworthy blockchain systems in the era of “Internet of value”: development, challenges, and future trends[J]. Science China Information Sciences, 2022, 65: 1-11. [4] Bagaria V, Kannan S, Tse D, et al. Prism: Deconstructing the blockchain to approach physical limits[C]// Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. 2019: 585-602. [5] Dai X, Xiao J, Yang W, et al. Jidar: A jigsaw-like data reduction approach without trust assumptions for bitcoin system[C]// Proceedings of the 2019 IEEE 39th International Conference on Distributed Computing Systems. 2019: 1317-1326. [6] Li M, Lin Y, Zhang J, et al. CoChain: High Concurrency Blockchain Sharding via Consensus on Consensus[C]// Proceedings of the 2023 IEEE International Conference on Computer Communications. 2023. [7] Hong Z, Guo S, Li P, et al. Pyramid: A layered sharding blockchain system[C]// Proceedings of the 2021 IEEE Conference on Computer Communications. 2021: 1-10. [8] Satija S, Mehra A, Singanamalla S, et al. Blockene: A high-throughput blockchain over mobile devices[C]// Proceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation. 2020: 567-582. [9] Qi X, Zhang Z, Jin C, et al. BFT-Store: Storage partition for permissioned blockchain via erasure coding[C]// Proceedings of the 2020 IEEE 36th International Conference on Data Engineering. 2020: 1926-1929. [10] Wang S, Dinh T T A, Lin Q, et al. Forkbase: An efficient storage engine for blockchain and forkable applications[C]// Proceedings of the VLDB Endowment. 2018: 1137-1150. [11] Chatzopoulos D, Gujar S, Faltings B, et al. Mneme: A mobile distributed ledger[C]// Proceedings of the 2020 IEEE International Conference on Computer Communications. 2020: 1897-1906. [12] Keidar I, Kokoris-Kogias E, Naor O, et al. All you need is dag[C]// Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. 2021: 165-175. [13] Yu H, Nikolić I, Hou R, et al. Ohie: Blockchain scaling made simple[C]// Proceedings of the 2020 IEEE Symposium on Security and Privacy. 2020: 90-105. [14] Danezis G, Kokoris-Kogias L, Sonnino A, et al. Narwhal and tusk: a dag-based mempool and efficient bft consensus[C]// Proceedings of the 17th European Conference on Computer Systems. 2022: 34-50. [15] Spiegelman A, Giridharan N, Sonnino A, et al. Bullshark: Dag bft protocols made practical[C]// Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. 2022: 2705-2718. [16] Dickerson T, Gazzillo P, Herlihy M, et al. Adding Concurrency to Smart Contracts[C]// Proceedings of the 2017 ACM Symposium on Principles of Distributed Computing. 2017: 303–312. [17] Ponnapalli S, Shah A, Banerjee S, et al. RainBlock: Faster Transaction Processing in Public Blockchains[C]// Proceedings of the 2021 USENIX Annual Technical Conference. 2021: 333-347. [18] Sharma A, Schuhknecht F M, Agrawal D, et al. Blurring the lines between blockchains and database systems: the case of hyperledger fabric[C]// Proceedings of the 2019 International Conference on Management of Data. 2019: 105-122. [19] Ruan P, Loghin D, Ta Q T, et al. A transactional perspective on execute-order-validate blockchains[C]// Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. 2020: 543-557. [20] Wu C, Amiri M J, Asch J, et al. FlexChain: an elastic disaggregated blockchain[C]// Proceedings of the 48th International Conference on Very Large Databases. 2022: 23-36. [21] Gelashvili R, Spiegelman A, Xiang Z, et al. Block-stm: Scaling blockchain execution by turning ordering curse to a performance blessing[C]// Proceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming. 2023: 232-244. [22] Xiao J, Zhang S, Zhang Z, et al. Nezha: Exploiting Concurrency for Transaction Processing in DAG-based Blockchains[C]// Proceedings of the 2022 IEEE 42nd International Conference on Distributed Computing Systems. 2022: 269-279. [23] Zhu Y, Zhang Z, Jin C, et al. SEBDB: semantics empowered blockchain database[C]// Proceedings of the 2019 IEEE 35th international conference on data engineering. 2019: 1820-1831. [24] El-Hindi M, Binnig C, Arasu A, et al. BlockchainDB: A shared database on blockchains[C]// Proceedings of the 45th International Conference on Very Large Databases. 2019:1597-1609. [25] Zhang C, Xu C, Wang H, et al. Authenticated keyword search in scalable hybrid-storage blockchains[C]// Proceedings of the 37th International Conference on Data Engineering. 2021: 996-1007. [26] Wang H, Xu C, Zhang C, et al. vChain+: Optimizing verifiable blockchain boolean range queries[C]// Proceedings of the 38th International Conference on Data Engineering. 2022: 1927-1940. [27] Shao Q, Pang S, Zhang Z, et al. Authenticated range query using SGX for blockchain light clients[C]// Proceedings of the 2020 International Conference on Database Systems for Advanced Applications. 2020: 306-321. [28] Han R, Xiao J, Dai X, et al. Vassago: Efficient and authenticated provenance query on multiple blockchains[C]// Proceedings of the 40th International Symposium on Reliable Distributed Systems. 2021: 132-142. [29] Dai X, Xiao J, Yang W, et al. LVQ: A lightweight verifiable query approach for transaction history in bitcoin[C]// Proceedings of the 40th International Conference on Distributed Computing Systems). 2020: 1020-1030. [30] Zhang S, Xiao J, Wu E, et al. MorphDAG: A Workload-aware Elastic DAG-based blockchain[J]//IEEE Transactions on Knowledge and Data Engineering, 2024 [31] Cheng F, Xiao J, Liu C, et al. SharDAG: Scaling DAG-Based Blockchains via Adaptive Sharding[c]//Proceedings of the 2024 IEEE 40th International Conference on Data Engineering, 2024 [32] Ni J, Xiao J, Zhang S, et al. FLUID: Towards Efficient Continuous Transaction Processing in DAG-based Blockchains[J]//IEEE Transactions on Knowledge and Data Engineering, vol. 35, no. 12, pp.12679-12692, December 01, 2023 [33] 常健，林立成，李彬弘，肖江*，金海. 基于学习索引的图式区块链高效可验证查询机制[J]. 计算机研究与发展, 2023, 60(11):2455-2468.
版权声明：中国计算机学会(CCF)拥有《中国计算机学会通讯》(CCCF)所刊登内容的所有版权，未经CCF允许，不得转载本刊文字及照片，否则被视为侵权。对于侵权行为，CCF将追究其法律责任。
| 
京公网安备 11010802032778号 )
发表于 2024-4-18 13:47:19