减少 90% 陈旧读数量，性能提升 3 倍！华中科大团队提出图式区块链高效事务执行机制 ErlangShen苹果Vision Pro将在2月2日在美上市 1月19日开启预购自有品牌寻差异化 本土零售迈向下一站亲民版“卫士” 哈弗猛龙迎首次OTA升级：5项功能优化！移动影像终极天花板！一图看懂OPPO Find X7 Ultra：5999元起国服回归仍无期！暴雪游戏官博复活系乌龙：微博自动赠送会员O

ESCI, EI 收录期刊，专注电子信息前沿

Doi: 10.11999/JEIT230874

基金项目 : 国家重点研发计划 ( 2021YFB2700700 ) ，湖北省重点研发计划 ( 2021BEA164 )

摘要：

基于有向无环图 ( DAG ) 的图式区块链能够显著提升系统性能，已成为近年来业界的研究热点。相较于传统串行化的链式区块链，图式区块链可在单位时间内并发处理大量事务从而提升吞吐量。随着事务量的激增，图式区块链面临事务执行效率低的瓶颈问题，即海量事务执行对状态数据访问的需求大幅增加，导致高昂的输入 / 输出 ( I/O ) 开销。

实现低 I/O 访问主要包括两方面的全新挑战：一方面，图式区块链若直接采用传统的事务预取机制，将因执行逻辑不一致引入大量的陈旧读；另一方面，针对不同账户的状态访问会在默克尔树的高层节点中造成重复的 I/O 开销。

为此，本文设计基于流水线的图式区块链高效事务执行机制— ErlangShen，包括 Epoch 粒度的状态预取机制和默克尔高层路径缓存机制来分别减少陈旧读的数量和重复的 I/O 开销。具体而言，ErlangShen 充分分析并利用了事务访问频次的冷热特征，将访问热事务的逻辑执行与冷事务的状态预取并行化，以避免状态预取对事务执行的影响。

此外，为了进一步提升事务执行的吞吐量，根据访问冷热状态事务的特性设计了定制化的并发控制方法。实验结果表明，ErlangShen 机制能够减少约 90% 的陈旧读数量，与最新图式区块链事务处理机制 Nezha 相比，可将性能提升 3～4 倍。

1 背景与动机

去中心化应用（如去中心化金融（Decentralized Finance, DeFi）等）的高速发展和区块链对传统行业的赋能，这对区块链系统的性能和可扩展性提出了新的要求。业界就此提出了具有性能优势的基于有向无环图（Directed Acyclic Graph, DAG）结构的图式区块链。如图 1 所示，图式区块链在一个 Epoch（Epoch 指的是生成一个区块的时间周期）内打包并生成多个有效区块，其天然的并行结构打破了传统链式区块链的性能限制。然而，随着事务量的激增，图式区块链面临事务执行效率低的瓶颈问题，即海量事务执行对状态数据访问的需求大幅增加，导致高昂的 I/O 开销，从而影响系统整体的吞吐量。

事务执行可细分为逻辑执行和状态访问，状态访问通过磁盘 I/O 来获取逻辑执行所需的状态，由于事务执行的逻辑执行和状态访问分别消耗 CPU 和 I/O 资源，故而可以将逻辑执行与状态访问进行解耦，以便在事务执行的过程中，所需状态能够在内存中获取，从而解决事务执行的 I/O 瓶颈问题。传统链式区块链的解决方案采用事务粒度的状态预取机制。然而，事务粒度的状态预取会因为智能合约模拟执行与实际执的行逻辑不一致或事务在区块中的顺序不确定而产生陈旧读的问题。在图式区块链中，采用事务粒度的状态预取机制会导致陈旧读的数量成倍增加（如图 2），所以本文采用了 Epoch 粒度的状态预取机制。然而，Epoch 粒度的状态预取需等待上一个 Epoch 的状态完全提交后才能进行，而图式区块链需要预取大量的账户状态，这可能在事务执行前无法完成，导致事务执行被状态预取所阻塞。

此外，主流的区块链系统一般将状态以默克尔帕特里夏字典树（Merkle Patricia Trie, MPT）的形式存储在 LevelDB 中。这导致状态的读取和提交都需要从 MPT 的根节点依次向下寻找，直至叶子节点，所以相近的账户地址在状态访问的过程中会在 MPT 高层路径结点上进行重复重复的 I/O 操作 . 此外，随着系统中账户数量的不断增长，MPT 也会不断扩展，使得访问叶子节点需途径更多的中间节点，导致状态访问需要数次乃至几十次 I/O 操作，重复的 I/O 操作导致状态获取的时延急剧上升（如图 3）。

因此，实现图式区块链低 I/O 访问的事务执行的核心挑战是：1）解决状态预取导致的大量陈旧读与阻塞问题；2）降低状态树访问的重复 I/O 开销。ErlangShen 旨在提出一种基于流水线低 I/O 访问的图式区块链高效事务执行机制，主要包括 Epoch 粒度的状态预取机制、MPT 高层路径缓存机制和适应冷热事务的并发执行策略。其在一定程度上消除了 I/O 瓶颈对事务执行的影响并能有效提升事务执行的吞吐量。

2 设计与实现

2.1 图式区块链数据特征

本文对图式区块链中访问数据的冷热程度进行细致的分析（图 4），热事务所访问的账户总数约占整个 Epoch 的 65%，这意味着可以优先预取热事务所访问的状态，在执行热事务的同时预取冷事务所访问的状态，以并行化整个事务的访问与执行，从而构建基于流水线低 IO 访问的图式区块链高效事务执行机制。此外，为了解决状态访问过程中重复 I/O 操作的问题，ErlangShen 分别引入了 MPT 高层路径缓存机制。MPT 高层路径缓存机制先将账户地址按序排列，此时相邻的账户有着最长的公共路径，再进行顺序访问时即可在一定程度上消除重复 I/O 操作的问题。

2.2 系统架构

图 5 展示了 ErlangShen 处理事务的流程，包括两个模块和五个阶段。两个模块根据系统所使用的资源进行划分，分别为事务处理模块和状态存取模块，相辅相成实现系统资源的最大化利用。从整个事务处理流程来看，五个阶段分别为：排序、区块广播、热事务执行、冷事务执行以及状态的更新和提交。由于图式区块链无需在共识前执行事务，只需简单验证事务签名和区块哈希的正确性，所以可以将状态树的更新和状态的提交与共识并行，使整个处理流程不被状态提交的频繁 I/O 所阻塞。注意：状态树的更新是必须要在共识前完成的，状态树的更新会先在内存中完成序列化后批量更新到磁盘，只需要获取到 MPT 在内存中更新好的状态根即可，所以在打包区块的同时可以进行状态根的更新，后续的提交可以与共识并行，为了加速状态的更新和提交，可以利用冷事务的执行，进行部分热事务相关状态的更新。

2.3 基于 MPT 高层路径缓存的状态预取机制

MPT 是压缩前缀树（Patricia Trie ) 和默克尔树（Merkle Tree ) 的结合。如图 5 所示，如果两个或多个账户的地址具有公共前缀，那么访问这些地址的状态则会对公共前缀路径上的节点进行多次 I/O 操作，从而造成状态访问的效率低下。为了提升状态读取的效率，在内存中开辟了一个 MPT 树的缓冲区并采用的淘汰方法为最近最少使用算法（Least Recently Used, LRU）。如图 6 所示，假设当前的缓冲区大小仅能容纳 4 个树节点，如果按照 A, B, C, D 这样的访问顺序获取状态，扩展节点 1 与分支节点 2 会被重复访问；为了缓解重复的 I/O 访问开销，首先对访问的地址大小进行排序，形成 A, D, B, C 的访问顺序后再获取状态，则不会产生任何重复的 I/O 访问。

2.4 冷热事务各自的并发执行策略

与传统图式区块链一样，执行事务前需要确定事务的总顺序。如图 7 所示，每个矿工节点或全节点按照一定的规则（如区块哈希值后几位）对区块进行排序形成区块顺序，然后根据区块顺序依次将所有的事务排序形成事务全序并进一步划分为热事务序列和冷事务序列（默认事务在区块内有序）。在并发执行的过程中，只需保证冷热事务并发执行的结果与各自串行执行的结果一致即可。

本文使用确定性排序锁机制对热事务进行并发控制，以保证每个节点在执行完事务后世界状态的一致性。确定性排序锁机制分为两个部分：锁管理器和事务调度器。锁管理器为每个地址构建一个等待队列，初始时根据热事务序列和事务的读写集依次将事务置入相应的队列中。然后锁管理器从热事务序列中依次扫描热事务，如果某个事务能获取到所有它访问到的地址的锁，则将其标记为可执行并放入事务调度器中等待调度执行；如果未能获取到所有的锁，则需等待其他事务释放锁。

热事务并发执行会产生大量的冲突，而冷事务并发执行时几乎没有冲突，故而冷事务的并发执行需要探究如何最大化并发执行度以及并发调度的效率。本文提出了基于多事务序列的确定性依赖图来加速冷事务的处理。该依赖图是根据冷事务序列来构建的，如图 8 所示，与热事务并发的第一阶段相似，需为每个地址构建一个事务队列，首先根据冷事务序列和读写集将依次将事务置入相应的队列，然后根据每个队列为相邻的事务添加有向边和出入度，最后即可形成图 8 右图所示的依赖图。该依赖图在确保冷事务并发执行的结果与串行结果一致的同时，还能提升并发程度和并发调度效率。

2.5 系统实现

本文用 Golang 实现了 ErlangShen，包括执行层和数据存储层。为了支持智能合约事务，执行层中采用了 Ethereum 虚拟机（Ethereum Virtual Machine, EVM）并实现了基于 EVM 的读 / 写记录器。数据层采用了 Ethereum 的 MPT 来有效组织每个账户的状态，并采用 LevelDB 进行持久化存储。

3 实验结果

3.1 实验设置

实验负载选用了是区块高度为 1000W 的 Ethereum 的真实负载，其约有 1 × 108 的账户数量，在实验过程中能体现出状态访问的 I/O 对事务执行的影响。每个区块的大小设置为 200 个事务（区块间不包含相同的事务），区块的传播时延设置为 2 秒，每个实验测试 10 轮并取平均值。实验在一台配备了 6 核 12 线程 Intel Core i5-10400 的 CPU 和 16 GB 的内存以及 1 TB 的 SSD，SSD 顺序读取的速度最高可达 560 MB/s。

3.2 I/O 优化后的态读取性能

图 9 展示了状态读取时延和并行区块数量的关系。MPT 高层路径缓存和无内存缓存相比，状态获取的时延约能降低 90% 左右。这是因为在无缓存的情况下，树根到叶子节点路径上的所有节点都要从磁盘加载，导致了大量的重复 I/O 操作；而 MPT 高层路径缓存机制则可以从内存缓存中读取大部分节点，以减少重复的 I/O 操作来加速状态读取。

3.3 冷热事务各自并发策略的性能

首先是具有高争用性的热事务在确定性排序锁下并发执行的性能，相较于难以发挥多核机器性能的串行，如图 10 ( a ) 所示，确定性排序锁机制能够带来的加速倍数约为 2-3 倍。其次是冷事务在多事务序列的确定性依赖图下并发执行的性能，如图 10 ( b ) 所示，冷事务串行执行的吞吐量是热事务串行执行的 2-4 倍，冷事务并发执行是冷事务串行执行的 7-8 倍，但这也意味着并发执行过程中频繁的线程切换，使得在并行 64, 128 个区块数量时的加速倍数有所下降。

3.4 系统的整体性能

最后，实验对比了 ErlangShen 整个事务处理架构相比于串行执行和 Nezha 的性能提升（串行执行没有状态预取，Nezha 包含状态预取）。根据 OHIE 的探索，当并行区块数为 4-64 的情况时，设置区块传播时延为 2 秒；128 个并行区块时无需考虑区块传播时延的影响。串行执行的 TPS 约为 200，图 11 展示了 Nezha 和 ErlangShen 的性能对比，Nezha 以丢弃事务为代价来提升吞吐量，故而有效吞吐量较低。与 Nezha 相比，ErlangShen 可将性能提升 3-4 倍。

4 总结

作者团队针对图式区块链事务执行过程中的 I/O 瓶颈问题提出一种基于流水线低 IO 访问的图式区块链高效事务执行机制，主要包括 MPT 高层路径缓存机制和适应冷热事务的并发执行策略。其采用了 Epoch 粒度的状态预取机制，并将冷热事务所需状态的预取分开，实现了 I/O 和 CPU 的并行。实验结果表明，本文的解决方案优于传统的方案，不仅消除了 I/O 瓶颈对事务执行的影响还能有效的提升事务执行的吞吐量。

校对 | 融媒体工作室

审核 | 陈倩

本号发布信息旨在传播交流。如涉及文字、图片、版权等问题，请在 20 日内与本号联系，我们将第一时间处理。