Blockchain-Enpowered Cooperative Resource Allocation Scheme for Computing First Network
-
摘要:
随着AI内容生成、多媒体处理、VR视频等对于计算资源有着极大需求的互联网服务的快速发展，在可以遇见的将来，计算资源将成为网络中的稀缺资源.算力网络通过将算力作为网络基本单元之一来实现算力的网络化，为这些计算敏感的应用提供了行之有效的解决方案.得益于来自云—边—端等节点的计算资源，算力网络能够为大规模用户提供弹性泛在的计算调度.尽管算力网络具有广泛的应用前景，如何实现在这些地理分布的计算节点之间高效调度，计算资源对于算力网络的性能至关重要.提出了一种区块链赋能的资源调度（blockchain empowered resource allocation，BCERA）算法.不同于现有的资源调度方法，BCERA依赖于一个区块链结构来实现分布式、高效的计算资源调度.特别地，有别于现有的区块链结构，BCERA中的区块链节点通过求解任务调度优化问题来实现区块链的共识，从而在避免共识所带来的额外开销和时延的同时，还能提升系统的可扩展性和鲁棒性.计算资源调度问题被建模为一个马尔可夫决策过程（Markov decision process，MDP）并通过强化学习方法来求解.除此之外，还设计了一个激励机制以鼓励计算节点贡献资源支持算力网络的运转.实验结果表明，所提出的方法能够有效提高资源调度性能.
Abstract:With the fast rapid growth of the Internet services such as AI content generation, multimedia processing, VR vidio etc., with huge demand for computation resources, it is forseen that the computing will become scarce resources in the near future. Computation first network (CFN) conceptualizes networked computing and puts the computation as the primitive of the network, which becomes a promising solution for various computation intensive applications. CFN provides ubiquitous computation access thanks to the resources offered by various computation unit from the cloud, edge and end users’ equipments. Despite its promising, how to offload the continuous arrival computation tasks to various geo-distributed computation units in CFN is of importance to the CFN performance. In this paper, we propose a blockchain empowered resource allocation (BCERA) for CFN. In BCERA, blockchain plays a key role for the task offloading, including recording the resource usage, optimization of the resource allocation. Specifically, we redesign the consensus mechanism in blockchain and allow the blockchain nodes to reach agreement via solving the resource allocation problem in FCN. This resource allocation problem is formulated as a Markov decision process (MDP) and blockchain nodes use the reinforcement learning methods to search the optimum. Besides, considering the resources may be offered from different parties, an incentive mechanism is also presented to encourage the computation units to provide their resources. We conduct a series simulation tests based on our designed blockchain platform to show how BCERA outperforms the state-of-art solutions.
-
区块链起源于比特币，经过10余年的发展，凭借其去中心化、不可篡改、透明性、可追溯等特性得到了迅猛发展. 整体而言，区块链是以数据库为底层数据存储依托，借助P2P对等网络进行信息通信，依靠密码学实现权益保障和隐私保护，通过分布式共识机制达成一致性，从而构建价值交换体系[1]. 区块链早期主要聚集数字货币领域，随着技术的不断完备和发展，目前正应用于溯源、跟踪、取证等多种场景.
区块链按照读写权限的开放程度，可分为公有链、私有链和联盟链. 公有链允许任何节点参与链的读写和维护，具有较强去中心化特征，尤以比特币[2]和以太坊[3]等为代表；私有链由单个区块链服务客户使用，仅有授权的节点才能接入，并按照规制参与和读写数据；联盟链是仅允许联盟内部节点参与链的读写与维护的区块链，具有较弱的去中心化特征，相比于公有链，联盟链具有处理速度快、松散共识、隐私性好等优点，目前在商品溯源、版权存证等领域已有广泛应用.
联盟链发展至今，Hyperledger Fabric[4-5]（以下简称Fabric）一直是其中应用最为广泛的代表方案，它的模块化和通用设计适应于多种企业级应用，得到了学术界和产业界的广泛关注.
Fabric采用“执行—排序—验证”（execute-order-validate，EOV）[6]三段式架构，将智能合约与共识信任分离，提高了合约信任的灵活性以及系统的可扩展性，但同时也加剧了并发事务冲突问题[7-9]. 区块中的冲突事务在验证阶段被检测并标记为无效，但限于区块达成共识后不可更改，冲突事务仍执行上链操作. 如此以来，既降低了系统吞吐量又增加了延迟，同时被标记为无效的事务占用了系统的存储空间，耗费计算资源. 因此如何有效减少Fabric中的并发冲突[10-14]事务，成为目前国内外研究的焦点问题.
针对该问题，一些现有工作进行了初步探索. Xu等人[11]设计了一种包含锁机制和账本存储的LMLS方法来改善“写-写”并发冲突，引入Redis数据库来实现锁定机制，然而该方法难以解决“双花”问题，且锁定机制的引入在并发环境下事务执行效率低下. Nasirifard等人[12]提出将非冲突复制数据结构（CRDT）集成到Fabric中用于解决并发冲突问题，将冲突事务的事务值在提交到账本之前通过CRDT技术自动合并. 然而由于合并CRDT会引入额外时间开销，从而会导致更高的提交延迟. Sharma等人[13]提出了Fabric++，其通过事务冲突循环检测以及事务提前中止解决高并发场景下块内冲突问题. 然而对事务冲突图执行循环检测的方式对计算性能提出了更高的要求，无法适应于工业生产环境[15-16]. 同时Fabric++在块间冲突问题的解决上无法处理多客户端发起的并发冲突事务[17]. FabricSharp[18]从细粒度出发提出了事务重排序方案，以依赖图的形式检测循环冲突，然而该方案未能考虑块间冲突场景且依赖图的检测算法，时间复杂度较高，节点规模较大时耗时过长.
综上所述，以Fabric和FabricCRDT为代表的传统方案常采用悲观并发控制的方式来解决冲突，存在高并发场景下事务处理时间过长、效率较低等问题；以Fabric++和FabricSharp为代表的优化方案，存在块内冲突检测复杂度过高、块间冲突有待优化等问题. 为此，本文提出了Fabric-HT优化方法，在区块内提出高效的冲突检测和避免算法；并在块间引入冲突检测方案，将块间冲突检测提前至排序阶段完成，从块内、块间2个维度进一步提升Fabric性能.
首先，我们基于已有研究工作，对冲突事务的形成原因进行了充分的理论分析和实验佐证. 根据形成原因的不同分为2种情形：区块内冲突与区块间冲突，并分别针对这2类冲突提出了优化方法. 在保证不改变原有架构的基础上实现提高系统吞吐量和并发性能的目的. 具体而言，本文的主要贡献有3点：
1）针对区块内冲突问题，设计了一种高效事务调度机制. 面向块内冲突事务提出了依赖关系链和并发事务危险结构条件，中止少量事务消除冲突并生成无冲突事务的执行序列.
2）针对区块间冲突问题，系统性提出相关解决方案，建立以“推送-匹配”为核心的冲突事务避免机制. 该机制可在线性时间内完成冲突事务的匹配性检测，保证链上空间的合理利用.
3）为验证Fabric-HT方案的有效性，在多种工作负载场景下开展大量实验. 结果表明所提方案与其他代表性方案相比，在改善吞吐量、降低无效事务、节约存储空间等方面具有明显优势.
1. 相关工作
作为联盟链的典型代表，Fabric近年来得到广泛关注，存在许多致力于其性能优化的工作. Thakkar等人[16]提出了Fabric的性能基准，研究各种配置参数对事务吞吐量和延迟的影响，并指出当下存在的3个性能瓶颈 ：背书策略验证、块中事务的顺序策略验证、状态验证和提交. Gorenflo等人[17]提出了Fast-Fabric，使Fabric每秒能够处理2万个事务. 同时关注了共识机制之外的性能瓶颈：将事务ID从数据块中分离，降低Kafka共识的吞吐量；利用基于内存的哈希表取代世界存储状态，加快数据访问；使用线程并行处理验证过程. Xu等人[19]提出了一种计算不同网络结构（如区块大小、块间隔等）下事务延迟的理论模型，确定Fabric存在的一些性能瓶颈，并提出可行性建议. Sousa等人[20]为Fabric设计并实现了BFT-SMART，使排序服务阶段可以每秒处理多达10000个事务且在0.5 s内不可撤销的区块链中写入1个事务. Nakaike等人[21]关注账本访问和数据存储所引发的性能瓶颈，提出关闭LevelDB数据压缩机制、执行联合访问查询、调整数据库大小等方法. Raman等人[22]研究了在使用区块链存储大数据集时，使用有损压缩来降低Fabric背书节点和记账节点之间共享状态的通信成本，然而有损压缩在区块链中的适用场景极其有限. Dinh等人[23]使用衡量私有区块链性能的工具BlockBench来研究区块链的性能，并比较Fabric、以太坊和Parity的性能优劣. 虽然上述研究针对Fabric结构、事务验证、共识机制等方面进行了优化，但很多优化结果仍不理想.
并发冲突问题作为分布式系统中的研究热点，在区块链同样有着深远影响. 现有很多研究针对Fabric中的并发冲突提出了一些解决方案. Xu等人[11]设计了一种包含锁机制和账本存储的LMLS方法来改善“写-写”并发冲突，引入Redis数据库来实现锁定机制. 然而该方法无法解决区块链中著名的双花问题. Nasirifard等人[12]将近年来提出的非冲突复制数据类型（CRDT）集成到Fabric中用于解决并发冲突问题，对于冲突事务的事务值在提交到账本之前，通过CRDT技术自动合并，成功合并所有冲突事务. 然而由于合并CRDT会引入额外时间开销，从而会导致更高的提交延迟. Meir等人[24]提出了一种新的无锁方法用于提供事务隔离. 该方法利用Savepoint作为事务之间的边界，使用它来检测模拟的事务是否违反并发提交事务的边界，当检测到事务违例时中止事务模拟. 虽然该方法能够有效检测冲突事务，但对冲突事务的处理并不友好. Zhang等人[25]能够有效解决同一客户端发起的多笔交易事务之间引发的冲突，通过将冲突事务放入缓存队列中来避免无效交易的产生. 然而该方法并未考虑高并发场景下多客户端间交易引发的冲突问题，存在一定局限性. Sharma等人[13]提出了Fabric++，通过引入事务重排序机制以及事务提前中止可有效解决高并发场景下块内冲突问题，然而对事务冲突图执行循环检测的方式对计算性能提出了更高的要求无法适应于工业生产环境[15-16]，易造成更多有效事务的流失. Ruan等人[18]从细粒度出发提出了事务重排序方案，以依赖图的形式检测循环冲突，然而方案未能考量块间冲突场景且依赖图的检测算法受节点规模的增大表现出疲软性.
与上述现有优化方案相比，Fabric-HT根据冲突成因的不同，分别从区块内和区块间2个角度提出不同的优化方案，保证以提前中止最小数量的冲突事务实现非冲突事务成块的目的，且不改变原有功能的架构设计，具有较好兼容性.
2. 背景知识
Fabric是目前最具代表性的联盟链系统之一，已形成了强大可持续社区和繁荣生态系统. Fabric目前已经广泛应用于金融、保险、医疗、供应链等行业[26-27]. 此处简要介绍Fabric节点类型以及EOV架构下的事务执行流程.
2.1 节点类型
Fabric网络主要由3类节点组成：
1）客户端. 客户端是用户向Fabric网络发送请求的接口，是事务的发起者，通常通过软件开发包与平台通信.
2）Peer节点. Fabric主要包含背书节点、主节点、记账节点3类Peer节点. 背书节点负责模拟执行交易提案并签名背书；主节点负责与排序服务通信并在节点间传播区块数据；记账节点负责验证交易合法性并提交账本，维护交易记录.
3）排序节点. 排序节点负责为网络中所有合法交易进行全局排序，并将一批排序后的交易组合生成区块结构. 所有客户端提交的事务都需要进入排序服务阶段生成区块.
2.2 事务执行流程
按照Fabric的EOV架构的设计思想，Fabric将整个事务流程分为执行、排序、验证3个阶段. 下面介绍各阶段处理过程.
1）执行阶段. 此阶段又名背书阶段，客户端向背书节点提交交易提案并请求背书，背书节点的选择由背书策略决定. 背书节点负责检查提案消息并模拟执行. 检查通过后，背书节点将启动链码容器模拟执行交易提案，并将模拟结果暂时保存在交易模拟容器中，等待排序达成共识和交易验证，而不是直接更新到账本中，交易模拟结果采用状态数据读写集记录交易造成的状态变更结果. 背书节点将提案响应消息及模拟结果返回给客户端.
2）排序阶段. 一旦客户端接收到满足背书策略的响应消息后，会创建一个事务. 该事务包含有效载荷、元数据等内容，并将其发送给排序节点，受信任的排序服务将所有收到的事务按照一致性协议（共识机制）建立全局顺序，并按照出块规则将事务切割并打包成一定数量的区块. 默认情况下，事务基本按照到达服务的时间戳排序.
3）验证阶段. 首先组织中的记账节点负责验证排序后的交易数据，检查交易结构格式的正确性，调用校验系统链码（validation system chain code，VSCC）验证交易背书签名是否满足指定的背书策略；其次执行多版本并发控制（multi-version concurrency control，MVCC）检查交易数据读写集的版本冲突等，将冲突事务标记为无效. 验证完成后保存所有的区块数据到区块数据文件中，将最新的有效交易数据更新到状态数据库；最后将区块数据中经过背书的有效交易数据保存到历史数据库.
图1展示了3个事务T1, T2, T3从发起到上链的3阶段流程. 事务由客户端发起，在节点A和节点B上背书，客户端收集足够数量的背书响应后交由排序服务，在Kafka共识后生成区块，最后进入验证阶段，节点A和节点B分别验证区块，并将有效事务提交账本执行上链.
![]()
图 1 3阶段事务流①客户端形成事务提案；②将事务提案提交给多个背书节点；③多个背书节点返回背书结果；④客户端在接受到满足背书策略的响应消息后，将形成一个事务并提交给排序节点；⑤排序节点事务提交给排序服务，排序服务将所有收到的事务按照一致性协议（共识机制）建立全局顺序；⑥排序节点按照出块规则切割并打包成一定数量的区块；⑦排序节点将区块分发给多个组织的记账节点；⑧记账节点负责验证排序后的交易数据；⑨记账节点将区块数据中经过背书的有效交易数据保存到历史数据库.Figure 1. Three-phase transaction flow2.3 事务读写集
Fabric采用基于KV键值对的状态数据模型KV-Ledger作为账本. 账本支持读取状态数据、写状态数据和删除状态数据. 背书节点收到客户端发送的待处理事务提案后，首先模拟事务提案执行并签名背书. 提案模拟结果以读写集的形式返回给客户端. 一个事务的读写集由2部分组成：
1）读集合〈键，版本〉. 读集合中包括一个键列表和对应键的版本号.
2）写集合〈键，是否删除，值〉. 写集合中包含最终要提交给账本的键值对以及是否删除标记.
在验证阶段，记账节点会基于本地状态数据库对区块中所包含的交易执行MVCC检查，用于验证交易结果中读集合是否有效. 具体方法为读集合中的键和版本与当前状态中的键和版本进行比较. 如果版本不匹配，事务将被标记为无效. 最终将有效交易添加到更新账本操作中. 尽管存在标记的无效交易，但Fabric不会将其剔除掉，依然将其和有效交易共同上链.
2.4 事务间依赖关系
事务间依赖关系反映了不同事务之间的关联性. 并发事务间可能造成冲突的依赖关系有3种[18,28-34] ：
1）Tiw:r→Tj（写读依赖）. Ti写入数据xi，并且Tj在之后读取xi. 则事务Ti和Tj构成写读依赖关系. Ti应在Tj之前序列化.
2）Tir:w→Tj（读写反依赖）. Ti首先读取数据xi，而Tj在之后更新该数据为xi+1. 则事务Ti和Tj构成读写反依赖关系. Ti应在Tj之前序列化.
3）Tiw:w→Tj（写写依赖）. Ti写入数据xi，并且Tj在之后更新该数据为xi+1. 事务Ti和Tj构成写写依赖关系.
以上3种依赖关系通过事务重排序，可以有效解决冲突问题. 当并发事务间的依赖关系较为复杂时，易构成循环依赖，此类问题无法通过事务重排序解决.
4）Tir:w→Tjw:r→Ti（循环依赖）. Ti读取数据xi，而Tj在此之后更新该数据为xi+1. 与此同时Tj写入数据yi，并且Ti在之后读取yi，Ti和Tj就构成了循环依赖.
3. 问题剖析
本节主要介绍影响Fabric系统吞吐量的2种主要冲突类型：区块内冲突和区块间冲突. 同时对冲突原因进行理论分析.
3.1 区块内冲突
区块内冲突是指同一区块内的不同事务读写集合之间的冲突，发生于构造区块时将对同一键操作的事务划分到同一区块中. 为了方便阐述冲突的形成原因，此处举例说明. 假设在区块链的状态数据库中已存储2个数据K1和K2，它们的初始版本和键值都为V0和ValueA，图2展示了在并发场景下同一区块X内有T1，T2，T3共3个事务依序执行的过程，每个事务有自己单独的读写集列表，首先T1事务把键K1和K2的值分别做出了更新ValueA→ValueB，使它们的版本都更新到了V1，并通过了事务检测. 其次继续验证T2事务，执行MVCC检测时发现K1的版本V0≠V1，冲突检测不通过，T2事务被标记为无效事务. 同理验证T3事务时发现K2的版本V0≠V1，因此也被标记为无效事务. 类似这种在同一区块内先读后写的情况下，造成键版本更新使靠后事务的读集合无法通过MVCC冲突检测的状况，我们称之为区块内冲突.
区块内冲突的根本原因在于并发环境下同一区块内2个事务对相同键的先写后读. 写事务的提交更新了当前数据库中该元组的版本，造成靠后事务的读集合版本较低且验证不通过. 此类冲突问题在数据库系统中表现为读写反依赖.
3.2 区块间冲突
与区块内冲突不同，区块间冲突是发生在不同区块之间. 这是由于EOV架构的天然特性，使得事务的模拟执行与验证提交之间存在较大延迟，导致靠后的区块中事务出现脏读，最终引发读写冲突. 如图3所示，有2个事务T1和T2. 首先T1和T2依次背书，获得的K1的版本都为V0，当T1背书之后进入排序，在构造区块以及验证阶段，更新了K1的值，并将K1的版本V0更新为V1，然而此时T2模拟结果的读集合K1仍旧处于V0版本，直到提交账本之前并不会检测到这个过时的读取. 在后续验证阶段MVCC检测时T2无法通过，被标记为无效.
4. Fabric-HT方案设计
基于对上述2类事务间冲突原因的分析和判断，分别提出针对块内和块间的2种优化方案，这2种方案可在排序节点上同时运行.
针对块内冲突，提出了一种块内冲突事务调度机制. 首先提出一种2维链式结构“依赖关系链”；其次分析了构成冲突问题的3种事务间依赖关系，并提出了中止事务的危险结构条件；最后借助“依赖关系链”对事务队列依次执行危险结构检测和中止.
针对区块间冲突，由于块间事务存在一定延迟，无法在同一时段内解决此类问题. 为此，方案设计在排序节点建立缓存区，通过“推送”机制将区块链上的数据推送到缓存区，在排序阶段提前监测区块间事务间可能发生的冲突. 对于监测出的冲突事务，由客户端重新发起和上链.
4.1 块内冲突事务调度机制
调度机制通过合理中止事务，将剩余非冲突事务重排序以构造非冲突事务序列. 首先，提出“事务块”“读写块”“依赖关系链”等数据结构，将包含读写集的事务序列转换为2维链式结构. 其次，分析并发环境下造成冲突的3种依赖关系，提出了无法通过循环依赖检测的危险结构条件. 最后，基于危险结构条件对块内事务执行串行检测和调度，实现块内无冲突事务上链.
4.1.1 数据结构定义
首先给出“事务块”“读写块”“依赖关系链”等相关结构.
“事务块”的示例如图4所示，事务块中包含的具体信息有：Tx_N表示了当前事务唯一的ID. TimeStamp表示当前事务的预提交时间戳，该时间戳模拟了实际的事务提交时间. Head作为事务链的头部，指向事务所包含的读写块. Tx_prev指针和Tx_next指针分别指向当前事务的前置事务和后置事务（事务前置与后置关系由共识确定），该事务信息用于算法3中依赖关系链剪枝时使用.
“读/写块”由事务的读/写集衍生而来，对读/写块内容的分析，可反映各事务间的依赖关系. 其中Tx_N表示当前读/写块隶属的事务. DataKey表示当前读/写块访问的键，该信息的设定是为了缩短后期检测算法的计算时间. AccessMode用于区分当前读/写块的访问模式（读操作或写操作）. Order为当前事务所处事务集中的顺序. EndTime为当前事务的读/写集在执行阶段（或背书阶段）的完成时间，用于反映并发事务间不同读/写集的先后关系. 键链中各节点由前向指针Key_prev和后向指针Key_next链接而成. 事务链中各节点由前向指针Chain_prev和后向指针Chain_next链接而成.
如图4所示，左侧的“访问键集”由哈希值组成，该值由各事务访问值对应的键的哈希值构成. 顶端的“事务集”由共识后的事务集构成. 我们定义了一种2维链式结构，由事务链（纵向）和键链（横向）2种链构成. 事务链由每个事务按照“先读后写”的顺序指向该事务的各个读/写块，用于辅助算法3计算各个事务的时间戳；键链由不同事务访问的数据键计算出的映射值，按照“先读后写”的顺序指向对该键访问的各个读/写块. 键链通过访问读/写块来构造各个事务间的依赖关系，辅助计算单个读写操作的重要时间戳.
4.1.2 构造依赖关系链
下面介绍依赖关系链的2个算法，其中算法2是算法1的组成部分.
算法1. 依赖关系链构造算法.
输入： 事务集Tall；
输出： 访问键集KeySet〈Map of Ki , Head〉，事务集Tc-plus.
① ConstructChain(Tc)；
② Tc, Tnon-c =NCTDissociate(Tall)；
/*非冲突事务抽离*/
③ CurrentTxLink = null；
④ for Ti in Tc
/*初始化全量事务集Ti-plus，生成事务块*/
⑤ Ti-plus. Tx_prev = CurrentTxLink；
⑥ CurrentTxLink. Tx_next = Ti-plus；
⑦ CurrentTxLink = Ti-plus；
⑧ link = Ti-plus. Head；
⑨ end for
⑩ for Ri in Ti. ReadSet
/*遍历读集，增加读块*/
⑪ RWblock=ConstructRWBlock (Tx_N= Ti. Tx_ N, DateKey=Ri. key, AccessMode=‘r’, order=Tc. index, EndTime =Ri. time)； /*键链和事务链块插入算法*/
⑫ AddBlock (RWblock, link, KeySet)；
⑬ end for
⑭ for Ri in Ti. WriteSet
/*遍历写集，增加写块*/
⑮ RWblock = ConstructRWBlock(Tx_N=
Ti. Tx_N, DateKey=Ri. key, AccessMode=
‘w’,order=Tc. index,EndTime=Ri. time)；
/*键链和事务链块插入算法*/
⑯ AddBlock(RWblock, link, KeySet)；
⑰ end for
⑱ return KeySet, Tc-plus.
算法1给出了依赖关系链的构造过程，遍历冲突事务集得到依赖关系链中的键链和事务链. 主要包含3个步骤：
1）事务预处理. 算法1中行②作用是将共识后生成的总事务集中的非冲突事务抽离. 非冲突事务采取前置操作，冲突事务作为输入，经过算法1行①~②后消除冲突. 非冲突事务的抽离，可以减少依赖关系链的空间占用，同时降低检测算法的计算开销.
2）生成事务块. 算法1中行③~⑨表示遍历冲突集Tc，生成初始化全量事务集Tc-plus. Tc-plus包含各个事务生成的事务块，其通过指针Tx_prev和指针Tx_next链接. 以当前时间赋值TimeStamp模拟提交阶段的事务时间戳.
3）键链和事务链插入块. 遍历冲突事务的读/写集（ReadSet,WriteSet）初始化读/写块. 如算法1中行⑩~⑯所示，按照“读集生成的读块在前，写集生成的写块在后”的规则，依次将读/写块加入键链和事务链. 行⑱返回访问键集和事务集作为算法3的输入.
算法2. 基于键链和事务链的块插入算法.
输入： 读/写块RWblock，事务链指向link，访问键集KeySet；
输出： 访问键集KeySet〈Map of Ki , Head〉，事务集Tc-plus.
① AddBlock (RWblock, link, KeySet)；
② if (Map of RWblock. DataKey) not in KeySet
/*将该键添加至访问键集KeySet*/
③ end if
④ if (RWblock. AccessMode == ‘r’)
⑤ 根据当前键链指向赋值读/写块Key_next
和Key_prev；
⑥ 键链插入块，遵循“读集生成的读块在
前”原则；
⑦ else
⑧ 获取访问键指向keylink；
⑨ 遍历找到keylink尾部节点；
⑩ RWblock. Key_next = null；
⑪ RWblock. Key_prev = Keylink；
⑫ Keylink. next = RWblock；
⑬ link. next = RWblock；
/*事务链插入块*/
⑭ RWblock. Chain_prev=link；
⑮ link = link. next；
⑯ RWblock. Chain_next = null；
⑰ end if
⑱ return KeySet, Tc-plus.
算法2对应算法1中函数AddBlock，主要涉及读/写块加入键链和事务链的过程. 为优化此计算过程，在算法2中提出了“读集生成的读块在前，写集生成的写块在后”的块插入规则. 在读集生成块的基础上，访问同一键链上写集生成块时面向同一搜索方向提高了计算效率.
为了便于理解后续调度机制，我们给出一个示例. 该示例包含5个事务以及每个事务的读集合与写集合. 如表1、表2所示. 示例集合Tall={T1,T2,T3,T4,T5}，表中值为1表示该事务包含对此键的读操作或者写操作.
表 1 块内冲突事务的读集合Table 1. Read-Set of Inter-Block Conflicting Transactions事务 K1 K2 K3 K4 K5 T1 1 0 0 1 0 T2 0 1 0 0 0 T3 0 0 1 0 0 T4 0 0 0 0 0 T5 0 0 0 0 1 表 2 块内冲突事务的写集合Table 2. Write-Set of Inter-Block Conflicting Transactions事务 K1 K2 K3 K4 K5 T1 0 0 0 0 0 T2 1 0 0 0 0 T3 0 1 0 0 0 T4 0 0 1 1 0 T5 0 0 0 0 0 总事务集Tall划分为冲突事务集Tc={T1,T2,T3,T4}与非冲突事务集Tnon−c={T5}.Tnon−c事务集前置且不参与后续调度机制. Tnon−c事务集内事务顺序仍遵循Kafka共识协议生成的逻辑顺序. 根据依赖关系链构造算法，Tc事务集输入后得到图4所示的依赖关系链结构.
需要说明的是，依赖关系链的相关算法在排序节点中运行. 以排序节点共识后的事务集为原型数据构造依赖关系链，不仅兼容了原有的共识算法，而且也为后续冲突事务危险结构检测提供数据支撑.
4.1.3 危险结构检测和处理算法
受串行安全网[35]思想启发，我们提出危险结构检测算法，检测冲突集Tc中构成了依赖循环需要中止的事务，在中止部分事务后经事务调度，可对块内非冲突事务合理排序.
在介绍检查算法前，先引出事务间依赖关系、2个定义和1个定理作为预备知识.
定义1. 前驱事务与后驱事务. 假设事务集Tc中存在依赖关系，形如 Tix:x→Tjx:x→Tk（x取w或r）. 称Ti是Tk的前驱事务，表示为：Ti=pre×(Tk)；Tk是Ti的后驱事务，表示为：Tk=suc×(Ti). 且在该示例中，Ti是Tj的直接前驱事务，表示为：Ti=pre×(Tj). 当事务集构成循环依赖时，形如Tix:x→Tjx:x→Ti，称Tj既是Ti的前驱事务又是Ti的后驱事务.
定义2. 危险结构. 危险结构是指根据事务的依赖关系判断该事务是否存在成环风险的一种结构.
我们定义了3个时间戳，用于检测当前事务是否构成危险结构. 时间戳的定义结合了依赖关系链中读/写块间的关联性.
1）事务T的模拟提交时间戳c(T). 由于算法检测在排序阶段执行，无法获取实际的事务提交时间戳. 因此Fabric-HT在依赖关系链的事务块中定义了TimeStamp模拟提交时间戳，该时间戳作用于区分各个事务的提交顺序以及中止事务的判断，而不作为实际提交时间. TimeStamp在事务块初始化时赋值.
2）事务T的已提交最小前驱事务TP的模拟提交时间戳π(T). 已提交最小前驱意味着事务TP需满足式（1）~（3）：
TP=pre×(T)； (1) TP.TimeStamp<T.TimeStamp； (2) TP.TimeStamp= min(c(T),pre×(T).TimeStamp). (3) 3）事务T的直接后驱事务TS的模拟提交时间戳ρ(T). 需要注意的是，与c(T)和π(T)不同，事务T可能存在多个直接后驱事务从而产生多个ρ(T). 因此在实际的计算中ρ(T)优先取小于c(T)的最大值（见算法3）. 而已提交直接后驱事务TS需满足式（4）~（6）：
TS=suc(T)； (4) TS.TimeStamp<T.TimeStamp； (5) TS.TimeStamp=max(suc×(T).TimeStamp). (6) 定理1. 在事务间依赖关系中，当事务T及其已提交最小前驱事务TP确定时，即c(P)=π(T)<c(T). 如果存在事务T的直接后驱事务TS使事务T满足π(T)≤ρ(T)<c(T)时，则事务T的依赖关系构成危险结构. 其中π(T)=c(P),ρ(T)=c(S). 即若事务集中存在循环依赖关系，则必然存在危险结构.
证明. 假设环内所有事务Ti都不满足条件π(Ti)≤ρ(Ti)<c(Ti)，即危险结构不存在. 那么环内事务Ti必然满足以下2种条件之一（需要注意的是c(T)≠ρ(T)，因为不存在同时提交的2个事务）.
1）ρ(Ti)<π(Ti)<c(Ti)，即存在事务Ti的直接后驱事务Tj在事务Ti之前提交，且提交时间戳小于事务Ti的已提交最小前驱事务Tk. 然而根据π(T)定义得到：Tk.TimeStamp=min(c(Ti),pre×(Ti).TimeStamp)，且当事务间构成循环时，根据定义3，满足Tj=pre×(Ti)，即Tj.TimeStamp≥min(pre×(Ti).TimeStamp). 所以ρ(Ti)≥c(Ti)，与前置条件相悖.
2）π(Ti)<c(Ti)<ρ(Ti)，即存在事务Ti的直接后驱事务Tj在事务Ti之后提交，即c(Ti)<c(Tj). 假设被检测事务Ti为当前循环内最晚提交事务，则不满足条件c(Ti)<c(Tj)，与前置条件相悖.
因此若事务集Tc中存在循环依赖关系，则必然存在事务Ti满足危险结构检测. 证毕.
算法3. 危险结构检测和处理算法.
输入： 访问键集KeySet〈Map of Ki , Head〉，事务集Tc-plus；
输出： 非冲突事务集Tf.
① SerialDetectionAlgorithm(KeySet, Tc-plus)；
② Init(G)；
/*初始化无环依赖图，初始化边和节点*/
③ for Tiin Tc-plus
④ c(Ti)=Ti. TimeStamp；
ρ(Ti)=−∞；
π(Ti)=+∞；
link= Ti. Head；
/*初始化参数*/
⑤ 纵向遍历单个事务链link；
⑥ if (link. AccessMode == ‘r’)
⑦ 向后遍历键链寻找写集依赖；
⑧ else if (写读依赖)
更新π(Ti)；
在G中添加依赖边；
⑨ else if (读写反依赖)
更新ρ(Ti)，在G中添加依赖边；
⑩ else if (写写依赖)
按照First Commiter Wins规则；
⑪ else
⑫ 向前遍历键链寻找读集依赖；
⑬ if (写读依赖)
更新ρ(Ti)；
在G中添加依赖边；
⑭ else if (读写反依赖)
更新π(Ti)；
在G中添加依赖边；
⑮ else if (写写依赖)
按照First Commiter Wins规则；
⑯ end if
⑰ end if
⑱ end for
⑲ if (π(Ti)>ρ(Ti)) /*危险结构测试*/
中止 Ti； /*中止事务*/
删除在G中的 Ti；
Pruning(Tc-plus)； /*剪枝优化*/
end if
⑳ Tf = Topical (G)； /*事务重排序*/
㉑ return Tf.
如算法3所示，我们在依赖关系链的基础上提出了EOV架构下的危险结构检测算法. 从事务集中初始事务出发，依次判断当前事务是否满足危险结构条件. 若满足，则中止该事务且删除无环依赖图中该事务的节点和依赖边. 同时为了优化计算规模以及降低事务中止率，对依赖关系链进行剪枝，删除该事务在键链和事务链上的节点.
在算法3中：1）当检测当前读/写块为读集生成的块时，依据键链后指向Key_next寻找写集生成的块. 根据当前读/写集的模拟时间戳判断2个事务的依赖关系，若为写读依赖，则更新π(Ti)；若为读写反依赖，则更新ρ(Ti). 如算法3中行⑦~⑫所示. 2）当检测当前读/写块为写集生成的块时，依据键链前指向Key_prev寻找读集生成的块. 根据当前读/写集的模拟时间戳判断2个事务的依赖关系，若为读写反依赖，则更新π(Ti)；若为写读依赖，则更新ρ(Ti)，如算法3中行⑬~⑭所示. 最终算法执行结果集返回无环依赖图G用于事务可串行化处理.
为了便于理解定理1在算法3中的应用，给出如下示例说明. 以表1~2为例，冲突事务集Tc={T1,T2,T3,T4}根据危险结构检测算法依次执行. 根据依赖关系链中事务读/写块可得到图5（a）中的事务间依赖关系. 首先计算事务T1，c(T1)= T1. TimeStamp. 因找不到事务T1的已提交最小前驱事务P，π(T1)初始值不变. 事务T1的直接后驱事务为T2，因此ρ(T1)=c(T2). 综上ρ(T1)<π(T1)不满足危险结构条件. 同理分别计算事务T2,T3,T4. 当计算事务T4时，c(T4)= T4. TimeStamp. 事务T1的已提交最小前驱事务为T1，因此π(T4)=c(T1). 事务T1的直接后驱事务为T1，因此ρ(T4)=c(T1). 综上π(T4)=ρ(T4)<c(T4)满足危险结构条件，事务T4被中止，其他事务不再构成依赖循环关系.
1）剪枝优化. 在危险结构检测算法中，当事务因满足危险结构检测而被中止时，该事务的依赖关系将不具备参考性. 因为事务中止，该事务与其他事务的冲突问题也将中止. 以图5（b）为例，当事务T3被中止时，事务T4已不构成循环依赖关系. 假设在事务T4检测前保留T3信息，则π(T4)=c(T1)=ρ(T4)<c(T4)满足危险结构条件，造成错误中止事务. 因此在事务检测过程中的剪枝优化一方面可以避免错误中止事务，另一方面降低了事务计算规模. 剪枝优化算法在依赖关系链上执行，当该事务满足危险结构条件时，事务链依据Tx_prev和Tx_next前后指向完成剪枝操作，键链依据Key_prev和Key_next前后指向完成剪枝操作.
2）事务重排序. 区块内事务调度机制执行危险结构检测算法对构成循环依赖的事务提前中止，剩余事务构成有向无环依赖图. 有向无环依赖图的构造确保了后续可以通过事务重排序来解决事务间冲突问题. Fabric-HT引入拓扑排序[36]来建立冲突事务间的非冲突序列.
4.1.4 算法复杂度分析
区块内事务调度机制由2部分组成：构造依赖关系链和执行危险结构检测算法. 假设区块内有n个事务，每个事务有m个读写集（一般性假设）. 则这2部分的空间复杂度均为O(n×m). 在时间复杂度方面，以事务为基本单位时，构造依赖关系链和危险结构检测算法的时间复杂度都为O(n)；以读/写块为基本单位时，构造依赖关系链的时间复杂度为O(m)，而危险结构检测算法的时间复杂度为O(n×m2). 随着冲突事务的增多，该算法的耗时不会出现显著性变化. 这也取决于区块链系统本身的特殊逻辑，在一定时间内只允许固定数量的事务或固定大小的区块执行上链操作. 因此参与调度机制的事务始终在一个可控的范围之内.
4.2 块间冲突事务避免机制
如第3节所述，由于事务的模拟执行与验证提交之间存在较大延迟引发了区块间冲突，此类冲突问题无法通过事务重排序解决，因此我们提出了以“推送-匹配”为核心的区块间事务避免机制. 在排序节点中引入缓存区，可以在区块生成前对事务提前进行冲突检测，并根据冲突检测结果决定该事务是否加入区块. 整个冲突事务避免机制分3个阶段：上链数据“推送”缓存区、冲突事务匹配检测和冲突事务重新提交.
4.2.1 方案设计
在排序节点设置缓存区，缓存区的作用为检测当前排序节点中是否包含冲突事务，对冲突事务执行提前事务中止，严格限制冲突事务参与后续区块的生成. 缓存区的内容与相连主节点内的状态数据库内容保持同步. 为了减少空间消耗，缓存区内仅保留键和版本用作冲突检测，缓存区采用key-value数据库.
4.2.1.1 上链数据推送缓存区
当区块验证通过在主节点数据库中更新时，主节点将推送最新数据版本至缓存区用于块间事务冲突检测. 缓存区将被动更新数据.
自旋检测算法为在联盟链的去中心化和不可信的环境中单一主节点的数据推送存在可信问题时，通过排序服务节点对推送数据进行核验. 算法具体流程为：当排序服务节点接收到单一主节点推送的上链数据后，将进入自旋状态，持续向其他主节点发起上链数据推送请求；在请求阈值内，若排序服务节点接受到其他主节点的请求数据，则进行多节点数据一致性匹配，若匹配通过，执行后续冲突事务检测流程；若不通过或阈值内未能收到其他主节点请求，则跳过此次冲突事务避免机制.
4.2.1.2 冲突事务匹配检测
假设当前待检测队列中存在某个事务的读集合〈K1,VersionA〉和缓存区内数据〈K1,VersionB〉，如果VersionA<VersionB，则该事务为无效事务. 在排序节点接收到客户端发送的事务后，该事务加入检测队列中等候冲突检测，无法通过冲突检测的事务被标记为无效事务，等候重新提交.
区块间冲突的事务可能来自不同客户端. 考虑到多客户端引发并发冲突的可能. 我们将缓存区部署在排序服务而不是客户端. 整个冲突检测流程分4步完成，对应图6所示.
1）排序节点接收客户端发送的事务提案.
2）对收到的事务执行冲突事务检测，缓存区更新当前缓存内容，检测当前事务是否存在过时读集. 检测方式按照无效事务检测规则.
3）无效事务执行提前中止.
4）未发生冲突事务参与区块的生成，并被排序节点发送给组织内负责接收的主节点.
4.2.1.3 冲突事务重新提交
为了不破坏事务的原子性，对无法通过冲突检测的无效事务执行事务提前中止，并由排序节点通知客户端重新发起. 重新发起的事务语义不变，重新进入执行—排序—验证流程. 区块间冲突避免机制可以很好地检测靠后区块内的冲突事务，实施提前事务中止并通知客户端重新发起.
4.2.2 举例说明
为了便于理解区块间事务避免机制，此处给出一个示例说明. 假设当前区块链系统中有2个邻接区块10001和10002，所含冲突事务信息如表3所示.
表 3 区块间冲突事务示例Table 3. Example of Inter-Block Conflict Transaction区块 所含事务 读/写集合 执行结果 10001 T1 〈K1, ValueA〉
〈K1, Version1〉〈K1, Version2〉 10002 T2 〈K1，Version1〉 冲突 由于事务模拟阶段与验证阶段间的延迟，区块10002中事务T2在区块10001中事务T1提交之前模拟运行，所以K1的读集合为旧版本Version1. 区块10001和10002按照生成顺序依次进入区块间冲突检测流程. 前置区块的上链结果更新状态数据库且影响后置区块的检测结果，具体执行步骤为：
1）T1进入排序服务阶段.
2）缓存区刷新，请求最新键版本数据：K1最新版本为Version1.
3）T1通过事务检测机制，K1版本更新至Version2，生成区块10001.
4）区块10001经组织记账节点验证通过，执行上链操作.
5）T2进入排序服务阶段.
6）缓存区刷新，请求最新键版本数据：K1最新版本为Version2.
7）T2符合无效事务定义，无法通过事务检测，执行提前事务中止.
8）通知客户端重新发起T2.
4.2.3 算法时间复杂度
整个冲突事务避免机制的运行时间复杂度为O(n)，空间度为O(n)，n为客户端提交事务的数量.
5. 实验及分析
为验证Fabric-HT方案的有效性，开展实验并与基准Fabric、最新的Fabric++[13]和FabricSharp[18]等方案进行对比，围绕关键指标，在不同场景下开展实验评估工作.
5.1 实验设置及环境
本文实验场景包含3个组织，每个组织包含3个对等节点，节点通过Docker容器部署. 采用Kafka共识机制，并使用LevelDB作为状态数据库. 实验环境共由11台服务器组成，每台服务器含4核CPU （Intel Xeon 2.2 GHz），12 GB RAM，均安装有Fabric V1.4.8，并运行在Ubuntu 16.04 LTS环境下. Fabric-HT其他相关实验参数如表4所示.
表 4 实验参数设置Table 4. Experimental Parameters Settings实验参数 取值 通道数量 1 每个通道的客户端数量 4 每秒每个客户端触发的事务提案数 512 事务提案完成的最长持续时间/s 90 形成一个区块的最长时间/s 1 每个区块的最大容量/MB 2 实验在Smallbank工作负载和自定义工作负载情况下进行研究. 这2种负载的测试在Caliper和BlockBench[23]测试框架下展开.
在Smallbank工作负载下，1个交易可从1万个账号中读写4个账号，调整热门账号（表示并发环境下，该账号同时存在读操作和写操作）的比例以确保每次操作都有一定概率访问到热门账号. 此工作负载是开源平台OLTP的代表性工作负载之一，广泛应用于Fabric系统的性能测试.
自定义工作负载侧重于调整读写比例观察各方案的优势场景.在自定义工作负载下，如表5所示，设置10000个账号用于读写操作，事务包含的读写操作规模介于4和8之间. 选择读取热门账号的概率HR=10%, 20%, 40%；写入访问账号概率HW=5%, 10%；热门账号比例HSS=1%, 2%, 3%时工作负载探究各方案的性能表现.
表 5 工作负载设置Table 5. Workload Settings实验参数 取值 账号数量 10000 每个事务的读写操作量 4，8 选择读热门账号的概率HR/% 10，20，40 选择写热门账号的概率HW/% 5，10 热门账号比例HSS/% 1，2，3 为便于阐述和实验对比，本文所提优化方案为：
1）Fabric-HT-Ⅰ. 基于区块内冲突的事务调度机制在Fabric系统中独立运行.
2）Fabric-HT-Ⅱ. 基于区块间冲突的事务避免机制在Fabric系统中独立运行.
3）Fabric-HT-Ⅰ+Ⅱ. 上述2种优化方案在Fabric系统中并行运行.
其中Fabric-HT-Ⅰ和Fabric-HT-Ⅱ方案均属独立优化方案，在排序节点可单独运行或同时运行.
5.2 评价指标
为了对比不同工作负载下区块链系统的性能，我们引入了4个评价指标：
1）每秒平均成功事务数（average number of successful transactions per second，TPS）. TPS用于衡量区块链系统的吞吐量，表示一段时间内组织内记账节点每秒平均上链的事务数量[37]，是衡量区块链系统性能的重要指标. 具体计算方法为
TPS=1Ln∑i=1mn∑j=1Tij， (7) 其中L表示衡量周期，由于每秒上链成功事务数的高度集中性，即同一区块内所有事务同时上链，所以统计每秒上链事务数不具有代表性，选取一段时间内平均成功上链事务数可以有效衡量该指标. n表示L时间内上链的区块数，mn表示第n个区块内的事务数，Tij衡量第i个区块中第j个事务是否成功，如成功，Tij=1，不成功，Tij=0.
2）平均事务执行时间（average transaction execution time，TET）. TET表示事务从客户端发起，经过背书、排序，直至最后上链所经历的平均延迟，反映区块链系统处理事务的效率. 具体计算方法为
TET=1nn∑i=1Ti， (8) 其中，n为事务的数量，Ti 为第i个事务从发起到上链所经历的延迟.
3）事务中止率（transaction abort rate，TAR）. TAR表示一段时间内被中止的冲突事务数与全部事务数的比值，反映了区块链系统对冲突事务的处理能力. 事务中止率越低，系统处理冲突的能力越高. 具体计算方法为
TAR=Cn∑i=1Totali+C， (9) 其中，C为某时间内被中止的事务总数，n为某时间内生成的区块数，Totali为第i个区块内事务总数.
4）无效事务空间占用率（invalid transaction space occupancy rate，ITS）. ITS表示在区块链系统中所有无效事务占用的存储空间与所有区块占用的存储空间的比值. 本指标反映了各方案节约存储空间的能力. ITS值越低，表明方案在节约空间方面的能力越高. 具体计算方法为
ITS=n∑i=1mn∑j=1Tsjin∑i=1Blocki， (10) 其中，Tsji表示第i个区块中第j个事务的大小，Blocki表示第i个区块的大小，n表示测试区块的个数,mn表示第n个区块中无效事务的个数.
5.3 实验结果分析
围绕TPS、TET、TAR、ITS等指标，研究各对比方案在区块大小、冲突事务占比、通道数量和客户端数量、区块数量等不同参数取值下的性能对比情况. 4个指标和4种变化参数设计总共16种情况. 由于部分实验结果接近，为使内容简洁我们挑选并列出代表性结果.
5.3.1 区块大小的影响
为评估区块大小对系统性能的影响，以2的整数倍为步长将区块容纳事务数从32提升至2048[23]，并观察成功上链事务数以及无效事务的比例. 使用Smallbank工作负载进行测试，并初始化100000个用户，在满足写事务比例为95%、冲突事务比例为20%的条件下编写事务用例.
图7（a）显示了运行期间的TPS. 当区块内事务数量从32增至1024时，各方案的TPS都呈现明显增长. 首先，Fabric-HT-I+II区块大小提升最为明显. 实验观察到在事务数量达到1024时，TPS不再出现显著增长，区块达到饱和状态. 其次，Fabric-HT-I，Fabric++，FabricSharp的优化效果也较为明显，单独的区块内的事务优化方案Fabric-HT-I的处理能力较弱，与Fabric++接近. 再次，Fabric-HT-II略优于Fabric，最高TPS可达825. 最后，Fabric由于未考虑冲突事务处理，在区块大小为1024笔事务时TPS仅为738，为最低.
图7（b）展示了在区块内事务数量递增的情况下，TAR的变化情况. 如图所示，当区块内并发事务指数增长时，各优化方案TAR呈增长趋势. 相比于Fabric++和FabricSharp，Fabric-HT-I+II具有更好的处理性能，TAR较Fabric++最高可降低20%，较FabricSharp最高可降低14%. 此外，由于Fabric不涉及冲突事务处理机制，因此此处未列出TAR.
5.3.2 冲突事务比重（RW）的影响
在冲突事务比例变化时，考察各对比方案成功事务吞吐量和平均延迟情况. 实验用例设置读事务比例为50%，其他参数设置如表6所示. 测试事务用例满足Zipf分布. 工作负载采用Smallbank，其中Zipf分布的倾斜参数从0增长至2.0，以步长0.4设置不同程度的事务冲突，小倾斜参数意味者低事务冲突比重.
表 6 Zipf分布倾斜参数对应冲突事务比重Table 6. Zipf Distribution Skew Parameter Corresponds to the Proportion of Conflict TransactionZipf分布倾斜参数α 冲突事务比重/% 0 0 0.4 20 0.8 40 1.2 60 1.6 80 2.0 100 图8展示在各个冲突事务比重下，TPS以及TET的变化趋势. 如图7（a）所示，各方案TPS均随冲突事务比重的增加而减少. 其中Fabric的TPS下降尤为明显. 其次，Fabric-HT-Ⅱ虽然相对于Fabric有所提升，但较其他优化方案仍有差距. Fabric-HT-Ⅰ+Ⅱ在高并发冲突环境下仍能保持较高TPS. 当冲突事务比重在0%~100%间变化时，Fabric-HT-Ⅰ+Ⅱ将Fabric的TPS提高了1.23~9.51倍，将Fabric++和FabricSharp的TPS分别平均提高了1.33倍和1.18倍.
![]()
图 8 冲突事务比重对TPS和TET的影响Figure 8. Impact of proportion of conflict transactions on TPS and TET图8（b）展示了冲突事务比重变化时事务的TET. 与Fabric相比，Fabric++，FabricSharp，Fabric-HT-Ⅰ，Fabric-HT-Ⅱ，Fabric-HT-Ⅰ+Ⅱ都表现出了更高的延迟，这是由于它们需要额外的处理时间来解决冲突事务，且随着冲突事务比例的增加，TET也在显著提高. 而Fabric本身没有相关处理机制，所以TET并未在图中给出.
实验观察到，在冲突事务比重由40%提升到60%时，TET降低，表现为更优的效果，更多的冲突事务被中止在排序服务节点，不再参与后续区块的生成以及上链过程，因此TET出现抖动，但该抖动不具备通用参考性. 实验仍旧以对比相同事务集下不同优化方案的优劣作为重要指标.
值得注意的是，在冲突事务比重达到40%后，Fabric-HT-Ⅰ+Ⅱ比Fabric++和FabricSharp具备更为明显的低延迟表现，更适应于处理高并发环境下冲突事务密集度较高的场景. Fabric-HT-Ⅰ+Ⅱ能够获得该收益的原因取决于其可以大规模处理并发事务，对区块内事务规模不作限制，提高了事务处理效率.
研究高冲突场景下不同读写操作比重下的系统优化情况. 如图9所示，展示了事务读写操作比重（HR，HW）以及冲突事务比重（RW）改变时，Fabric和Fabric-HT-Ⅰ+Ⅱ的测试结果. Fabric-HT-Ⅰ+Ⅱ显著提高了系统TPS，尤其在RW=8，HR=40%，HW=10%，HSS=1%的配置下，TPS高达Fabric的2.4倍.
![]()
图 9 36种不同配置Fabric和Fabric-HT-I+II的TPS对比Figure 9. Comparison of Fabric and Fabric-HT-I+II under 36 different configurations for TPS5.3.3 通道数量和客户端数量的影响
此前实验采用单个通道和4个客户端提交事务. 为研究Fabric-HT的鲁棒性[18]，我们调整通道数量和客户端数量，观察它们对TPS的影响.
首先，实验调整通道数量观察对TPS的影响. 如图10所示，通道数量从1增加到8. 为节省计算资源，每个通道使用2个客户端发起交易提案. 当通道数量在1~4之间增长时，各方案TPS均在增长. Fabric-HT-Ⅰ，Fabric-HT-Ⅱ，Fabric-HT-Ⅰ+Ⅱ在多链环境下表现出良好的可扩展性和健壮性. 当通道数量达到8后，由于通道间竞争资源，导致失败事务的数量增加，进而引起TPS下降. 然而，Fabric-HT-Ⅰ+Ⅱ仍具有最好性能.
实验同时研究单通道中客户端数量的变化，如客户端数量从1增加到8对TPS的影响. 图11展示了当单通道客户端数量处于1~4时，Fabric-HT-Ⅰ+Ⅱ的TPS随客户端数量增加而提高. 当单通道客户端数量增长到8时，TPS明显下降，这是由于客户端数量增加引起资源竞争加剧，造成无效事务增加所致. 此时Fabric-HT-Ⅰ+Ⅱ仍具有最好的性能.
5.3.4 区块数量的影响
随着区块数量的不断增加，对区块链节点而言链上数据所需存储空间也在增大.
图12展示了随着区块链系统中区块数量的增加ITS的变化. 从图中可以看出，区块数量从10增长到35时，Fabric无效事务造成的空间损耗较为突出，其余方案均有改进，且Fabric-HT-Ⅰ+Ⅱ表现出最优的性能，能有效节省存储空间. 这源于我们在区块内冲突中通过事务重排序降低无效事务的数量，以及通过缓存区冲突检测实现对区块间无效事务的提前中止.
6. 讨 论
Fabric-HT除通过有效解决并发冲突提高TPS外，同时具有3点优势：
1）节省存储空间. 并发冲突事务的解决，极大地提高了上链事务的成功率，且有效事务比例的提高减少了链上存储资源的浪费. 当基准区块链系统Fabric链上的无效事务占比维持在40%以下时，Fabric-HT链上无效事务占比维持在15%以下，极大地节省了存储空间.
2）有效防范攻击. 当系统内某时刻处于不同位置的恶意节点针对某一个账户或节点发动DDoS攻击[28-29]时，服务器中充斥着大量同类信息，消耗网络带宽或系统资源，可能导致系统瘫痪[30]. 冲突事务检测机制可以很好地防范此类攻击，在排序服务阶段对事务语义执行提前检查，对检测不通过的事务执行提前中止，使其无法进入后续流程影响上链操作. Fabric-HT将此类问题在构建区块前解决，一定程度上提高了区块链系统的安全性.
3）检测速度快. 现有方案往往将冲突图分解为多个循环，贪婪地中止环内的冲突事务. 该方法虽然可以解决大多数场景下的冲突问题但检测冲突事务时间较长，严重限制了并发事务规模. 本文的危险结构检测算法确定了以时间戳为基础、以依赖关系链为阶梯的危险结构检测方式，在以事务为单位的线性时间内判断冲突事务是否应该中止.
7. 结 论
针对Fabric并发冲突影响性能的问题，本文提出一种综合考虑块内冲突和块间冲突的区块链性能优化方案Fabric-HT. 针对区块内事务冲突，提出了一种事务调度算法，根据区块内冲突事务集构造依赖关系链，并以依赖关系链为基础提出了危险结构检测算法. 针对区块间冲突问题，由于区块间事务的延迟性，通过在排序服务部分构造缓存区，建立冲突事务检测机制. 实验结果表明，Fabric-HT在吞吐量、事务中止率、事务平均执行时间、无效事务空间占用率等方面，均优于对比方案. 此外，Fabric-HT也表现出较好的鲁棒性和抗攻击能力.
作者贡献声明：吴海博和刘辉完成相关文献资料调研和分析以及论文撰写；孙毅参与相关方案的交流和指导；李俊指导论文撰写.
-
[1] Wang Shiqiang, Tuor T, Salonidis T, et al. Adaptive federated learning in resource constrained edge computing systems[J]. IEEE Journal on Selected Areas in Communications, 2021, 37(4): 1205−1221
[2] Chen Xingyan, Xu Changqiao, Wang Mu, et al. Augmented queue-based transmission and transcoding optimization for livecast services based on cloud-edge-crowd integration[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2021, 31(11): 4470−4484 doi: 10.1109/TCSVT.2020.3047859
[3] Huang Yutao, Wang Feng, Wang Fangxin, , et al. A hybrid device-edge-cloud execution framework for mobile deep learning applications[C] //Proc of the IEEE Conf on Computer Communications Workshops (INFOCOM WKSHPS). IEEE, 2019: 1−7
[4] He Yinghu, Ren Jinke, Yu Guanding et al. D2D communications meet mobile edge computing for enhanced computation capacity in cellular networks[J]. IEEE Transactions on Wireless Communications, 2019, 40(12): 3485−3500
[5] Wen Jinming, Ren Chao and Sangaiah A. K. energy-efficient device-to-device edge computing network: An approach offloading both traffic and computation[J]. IEEE Communications Magazine, 2018, 56(9): 96−102 doi: 10.1109/MCOM.2018.1701054
[6] Zhang Kaiqing, Yang Zhuoran, Baar T. Multi-agent reinforcement learning: A selective overview of theories and algorithms[J]. Handbook of Reinforcement Learning and Control, 2021, 325: 321−384
[7] Yagan D, Tham C K. Coordinated reinforcement learning for decentralized optimal control[C] //Proc of the IEEE Int Symp on Approximate Dynamic Programming & Reinforcement Learning. Piscataway, NJ: IEEE, 2007: 296−302
[8] Zavodovski A, Bayhan S, Mohan N, et al. DeCloud: Truthful decentralized double auction for edge clouds[C] //Proc of the Int Conf on Distributed Computing Systems (ICDCS). Piscataway, NJ: IEEE, 2019: 1−7
[9] Weng Jiasi, Weng Jian, Zhang Jilian, et al. DeepChain: Auditable and privacy-preserving deep learning with blockchain-based incentive[J]. IEEE Transactions on Dependable and Secure Computing, 2021, 18(5): 2438−2455
[10] Qu Yongyang, Pokhrel S R, Garg S, et al. A Blockchained federated learning framework for cognitive computing in industry 4.0 Networks[J]. IEEE Transactions on Industrial Informatics, 2020, 17(4): 2964−2973
[11] Cheng Hongju, Hu Qiaohong, Zhang Xiaoqi, Trusted resource allocation based on smart contracts for blockchain-enabled Internet of Things [J]. IEEE Internet of Things Journal, 11(9): 7904−7915, 2021
[12] Decusatis C, Lotay K. Secure, decentralized energy resource management using the Ethereum blockchain[C] //Proc of the 2018 17th IEEE Int Conf on Trust, Security and Privacy in Computing and Communications. Piscataway, NJ: IEEE, 2018: 1907−1913
[13] Miguel, Castro, Barbara, et al. Fault tolerance and proactive recovery[J]. ACM Transactions on Computer Systems, 2002, 20(4): 398−461 doi: 10.1145/571637.571640
[14] Xing Hong, Liu Liang, Xu Jie, et al. Joint task assignment and resource allocation for D2D-enabled mobile-edge computing[J]. IEEE Transactions on Communications, 2019, 67(6): 4193−4207 doi: 10.1109/TCOMM.2019.2903088
[15] Wu Huaming, Zhang Ziru, Guan Chang, et al. Collaborate edge and cloud computing with distributed deep learning for smart city Internet of things[J]. IEEE Internet of Things Journal, 2021, 7(9): 8099−8110
[16] Yi Deliang, Zhou Xin, Wen Yonggang, et al. Efficient compute-intensive job allocation in data centers via deep reinforcement learning[J]. IEEE Transactions on Parallel and Distributed Systems, 2020, 31(6): 1474−1485 doi: 10.1109/TPDS.2020.2968427
[17] Chen Xianfu, Zhang Honggang, Wu Celimuge, et al. Optimized computation offloading performance in virtual edge computing systems via deep reinforcement learning[J]. IEEE Internet of Things Journal, 2018, 6(3): 4005−4018
[18] Zhang Yutong, Di Boya, Zheng Zijie, et al. Distributed multi-cloud multi-access edge computing by multi-agent reinforcement learning[J]. IEEE Transactions on Wireless Communications, 2021, 20(4): 2565−2578 doi: 10.1109/TWC.2020.3043038
[19] Liu Chubo, Tang Fan, Hu Yikun, et al. Distributed task migration optimization in MEC by extending multi-agent deep reinforcement learning approach[J]. IEEE Transactions on Parallel and Distributed Systems, 2020, 32(7): 1603−1614
[20] Wang Xiumin, Chen Xiaoming, Wu Weiwei. Towards truthful auction mechanisms for task assignment in mobile device clouds[C] //Proc of IEEE Conf on Computer Communications. Piscataway, NJ: IEEE, 2017: 1−9
[21] Deng Yang, Han Tao, Zhang Ning. FLeX: Trading edge computing resources for federated learning via blockchain[C] //Proc of the IEEE Conf on Computer Communications Workshops (INFOCOM WKSHPS). Piscataway, NJ: IEEE, 2021: 1−7
[22] Sun Wen, Liu Jiajia, Yue Yanlin. et al. Joint resource allocation and incentive design for blockchain-based mobile edge computing[J]. IEEE Transactions on Wireless Communications, 2021, 19(9): 6050−6064
[23] Qin Zhenquan, Ye Jin, Meng Jie, et al. Privacy-preserving blockchain-based federated learning for marine Internet of things[J]. IEEE Transactions on Computational Social Systems, 2021, 9(1): 159−173
[24] Bai Fenhua, Shen Tao, Yu Zhuo, et al. Trustworthy blockchain-empowered collaborative edge computing-as-a-service scheduling and data sharing in the IIoE[J]. IEEE Internet of Things Journal, 2022, 9(16): 14752−14766 doi: 10.1109/JIOT.2021.3058125
[25] Wang Mu, Xu Changqiao, Chen Xingyan, et al. BC-mobile device cloud: A blockchain-based decentralized truthful framework for mobile device cloud[J]. IEEE Transactions on Industrial Informatics, 2020, 17(2): 1208−1219
[26] Wu Huaming, Wolter K, Jiao Pengfei, et. al. EEDTO: An energy-efficient dynamic task offloading algorithm for blockchain-enabled IoT-edge-cloud orchestrated computing[J]. IEEE Internet of Things Journal, 2021, 8(4): 2163−2176 doi: 10.1109/JIOT.2020.3033521
[27] Neely, Michael J. Stochastic network optimization with application to communication and queueing systems[J]. Synthesis Lectures on Communication Networks, 2010, 3(1): Article No.211
[28] Lin Bing, Huang Yinhao, Zhang Jianshan, et al. Cost-driven off-loading for DNN-based applications over cloud, edge, and end devices[J]. IEEE Transactions on Industrial Informatics, 2020, 16(8): 5456−5466 doi: 10.1109/TII.2019.2961237
[29] Ale L, Zhang Ning, Fang Xiaojie, et al. Delay-aware and energy-efficient computation offloading in mobile edge computing using deep reinforcement learning[J]. IEEE Transactions on Cognitive Communications and Networking, 2021, 7(3): 881−892 doi: 10.1109/TCCN.2021.3066619
[30] Sutton R S, Mcallester D, Singh S, et al. Policy Dradient Methods for Reinforcement Learning with Function Approximation[M] //Cambridge, MA: MIT Press, 1999
[31] Jang I, Choo S J, Kim M, et al. The Software-defined vehicular Cloud: A new level of sharing the road[J]. IEEE Vehicular Technology Magazine, 2017, 12(2): 77−88
[32] Tang Ming, Wong V. Deep reinforcement learning for task offloading in mobile edge computing systems[J]. IEEE Transactions on Mobile Computing, 2022, 21(6): 1985−1977 doi: 10.1109/TMC.2020.3036871
[33] Min Minghui, Xiao Liang, Chen Ye, et al. Learning-based computation offloading for IoT devices with energy harvesting, 10.48550/arXiv. 1712.08768 [P], 2017
-
期刊类型引用(3)
1. 刘同娟，蔡晓东. 基于区块链与物联网技术的农产品信息溯源体系研究. 物流科技. 2024(24): 44-50 . 
百度学术
2. 李硕，王馨爽. 多场景融合的码号数据分发架构及关键技术研究. 数据通信. 2024(06): 1-3+11 . 百度学术
3. 王宇能，石搏. AI赋能农产品营销供应链追溯系统研究. 北斗与空间信息应用技术. 2024(03): 22-26 . 百度学术
其他类型引用(2)
下载:
计量
- 文章访问数: 390
- HTML全文浏览量: 127
- PDF下载量: 222
- 被引次数: 5
