摘要
许多现有的区块链并不能充分解决分布式系统应用程序的所有特征,并且受到严重的架构限制,从而导致性能和机密性问题。虽然最近获得许可的区块链系统试图克服这些限制,但它们的重点主要集中在没有争用的工作负载上,即没有冲突的交易。在本文中,我们介绍了OXII,这是一种允许区块链支持并发执行的分布式应用程序的新范式。OXII专为具有(不同程度)争用的工作负载而设计。然后我们介绍ParBlockchain,这是一个专门在OXII范式中设计的许可区块链。使用一系列基准对ParBlockchain的评估表明,它在具有任何竞争程度的工作负载中的性能优于最先进的许可区块链系统。
索引词——区块链、许可、共识、依赖graph、争用
I. 引言
区块链是一种分布式数据结构,用于记录由许多节点维护的交易而无需中央权威[12]。在区块链中,节点在不受信任的参与者组成的大型网络中就它们的共享状态达成一致。区块链最初是为比特币加密货币[28]设计的,然而,最近的系统专注于其独特的功能,例如透明度、出处、容错和真实性,以支持广泛的分布式应用程序。比特币和其他加密货币是无需许可的区块链。在无需许可的区块链中,网络是公开的,任何人都可以在没有特定身份的情况下参与。另一方面,许多其他分布式应用程序,例如供应链管理[23]和医疗保健[6],部署在由一组已知的、已识别的节点组成的许可区块链上,这些节点仍然不完全相互信任。
分布式应用程序具有不同的特征,需要由许可的区块链系统解决。此类应用程序在吞吐量和延迟方面需要高性能,例如,金融应用程序需要以非常低的延迟每秒处理数万个请求。分布式应用程序也可能具有高争用的工作负载,即冲突交易。在这些工作负载下,多个交易同时对一些流行记录执行冲突操作。这些冲突交易可能属于单个应用程序,甚至属于使用共享数据存储的一组应用程序。虽然交易的顺序执行可以防止任何可能的不一致,但它会对性能和可扩展性产生不利影响。此外,在许多应用程序中都需要数据的机密性。在区块链中,每个应用程序的逻辑都可以编写为智能合约,如以太坊[3]所示。智能合约是一种计算机程序,一旦建立和部署就可以自行执行。由于智能合约包含应用程序的逻辑,因此可能需要限制对此类合约的访问。加密技术用于实现机密性,但是此类技术的大量开销使它们不切实际[5]。
现有的许可区块链,例如 Tendermint [25] 和 Multichain [21],大多采用顺序执行范式,其中节点使用共识协议就交易块的总顺序达成一致,然后交易以相同的顺序执行 所有节点顺序。由于在所有节点上顺序执行交易,这种范式存在性能问题,并且由于每个节点都访问每个智能合约,因此也存在机密性问题。另一方面,Hyperledger Fabric[5]通过切换执行和排序阶段的顺序,为许可区块链提供了一种新范式。在Hyperledger Fabric中,不同应用程序的事务首先并行执行,然后由一组节点组成的排序服务使用共识协议就所有事务的总顺序建立协议。Fabric通过限制对智能合约的访问来解决机密性问题,并通过并行执行交易来提高性能。但是,在工作负载中存在任何争用的情况下,它必须忽略对区块链性能产生负面影响的冲突交易的影响。
在本文中,我们介绍了OXII:一种用于许可区块链的命令执行范式。OXII主要用于支持分布式应用程序处理具有一定程度竞争的工作负载。OXII由排序节点和代理节点组成。Orderers 就不同应用的交易顺序建立协议,构建交易区块,并为区块内的交易生成依赖graph。依赖graph一方面根据交易之间的冲突给出部分顺序,另一方面通过允许并行执行非冲突交易来实现更高的并发性。每个应用程序的一组代理称为执行器,然后负责执行该应用程序的交易。
然后,我们介绍ParBlockchain,一个专门在OXII范式中设计的许可的区块链系统。ParBlockchain在排序和执行阶段处理交易。在排序阶段,交易在依赖graph中排序并放入块中。在执行阶段,每个应用程序的执行者按照依赖graph执行对应应用程序的交易。只要保留依赖graph中交易的部分顺序,就可以并行执行不同应用程序的交易。
本文的一个关键贡献是展示了区块链系统如何有效地处理具有冲突交易的工作负载,而无需回滚(中止)已处理的交易或按顺序执行所有交易。本文做出以下贡献:
- OXII,一种新的许可区块链范例,支持并发执行的分布式应用程序。OXII 使用基于依赖graph的并发控制技术来检测交易之间可能的冲突,并确保交易的有效执行,同时仍然允许并行执行非冲突交易。
- ParBlockchain,一个专门在OXII范式中设计的许可区块链系统。实验表明,任何竞争程度的工作负载都将从ParBlockchain中受益。
本文的其余部分安排如下。第二节简要描述了当前的区块链范式及其局限性。OXII范式在第三节中介绍。第四节介绍了ParBlockchain,这是一个专门在OXII范式中设计的许可区块链系统。第五部分显示了绩效评估。第六节介绍了相关工作,第七节总结了论文。
II. 背景
技术区块链是一种分布式数据结构,用于记录由许多节点维护的交易而无需中央授权[12]。区块链使用状态机复制 (SMR) 在节点上复制数据。状态机复制是一种通过复制服务器来实现容错服务的技术[26]。在状态机复制模型中,副本同意传入请求的顺序,然后以相同的顺序执行请求。状态机复制方法已在不同的同步和异步网络中使用,以容忍崩溃、恶意或两者兼而有之的故障。 在崩溃失败模型中,副本可能会因停止而失败,也可能会重新启动,但是,它们可能不会串通、撒谎或以其他方式试图破坏协议。相反,在拜占庭故障模型中,故障节点可能表现出任意的、潜在的恶意行为。
区块链使用异步容错协议来建立共识。由于区块链中的节点可能会出现恶意行为,因此区块链主要使用拜占庭容错协议来达成共识。
一般来说,“排序”和“执行”是任何容错系统的两个主要任务。容错协议主要遵循顺序执行范式,其中网络首先对交易进行排序,然后在所有节点上以相同的顺序依次执行它们。
现有的区块链系统可以分为两大类:无许可的区块链系统,例如以太坊(基于PoS的共识)[3]和许可的区块链系统,例如Tendermint(具有BFT类型的共识)[25]。
无许可区块链是公开的,任何人都可以在没有特定身份的情况下参与。无许可区块链主要遵循顺序执行范式,节点验证交易,将交易放入块中,并尝试解决一些密码难题。解决难题的幸运节点将块多播到所有节点。当一个节点接收到一个交易块时,它会验证谜题的解决方案以及该块中的所有交易。然后,节点按顺序执行块内的交易。这种范式要求所有节点执行每个交易,并且所有交易都是确定性的。
图 1(a) 显示了无许可区块链的交易流程。 当对等点从客户端接收交易时,在步骤 1 中,对等点验证交易,将它们放入块中,并尝试解决密码难题。 如果对等点很幸运(图中的 p3)并且比其他对等点先解决了难题,它会将块多播给所有对等点。 然后所有节点验证区块及其交易(步骤 3),依次执行交易(步骤 4),最后更新它们各自的账本副本。 请注意,如果多个对等方同时解决难题,则会在区块链中发生分叉。 但是,一旦将一个块添加到任何一个分叉分支,网络中的节点就会加入最长的链。
另一方面,许可的区块链由一组已知的、已识别但彼此不完全信任的节点组成。在许可区块链中,由于节点是已知和识别的,因此可以使用传统的共识协议对请求进行排序[11]。
许可的区块链可以遵循顺序执行或执行顺序范式。在按顺序执行的许可区块链中,如图 1(b) 所示,一组对等点(可能是所有对等点)验证交易,就交易的总顺序达成一致,将它们放入块中并将它们多播到 所有节点。 然后每个节点验证区块,使用“智能合约”执行交易,并更新账本。智能合约是一种计算机程序,一旦建立和部署就可以自行执行。智能合约类似于数据库触发器,其中一旦满足某些条件或条款,就会触发合约的逻辑执行。它们具有支持实时更新、执行准确、人工干预少等优点。
在命令执行许可区块链中,类似于命令执行无许可区块链,每个智能合约都在每个节点上运行。智能合约包括应用程序的逻辑,可能需要限制对此类合约的访问。虽然密码技术用于实现机密性,但此类技术的大量开销使它们不切实际[5]。 此外,每个节点上的顺序执行交易降低了区块链在吞吐量和延迟方面的性能。

图1. 区块链的现有范式
与顺序执行范式相比,Hyperledger Fabric [5] 通过切换执行顺序和排序为许可区块链提供了一种新范式。执行顺序范式在 Eve [22] 中首次在拜占庭容错SMR的背景下提出。在Eve中,节点并发执行交易,然后使用共识协议验证它们是否都达到相同的输出状态。事实上,Eve使用乐观并发控制 (OCC) [24] 通过假设冲突很少的低数据争用。
Hyperledger Fabric 使用类似的策略; 客户端向称为背书者(有权访问智能合约的节点)的子集发送请求。每个背书者执行请求并将结果发送回客户端。当客户端收到足够的背书(由某个背书策略指定)时,它会组装一个包含所有背书的交易并将其发送给一些指定的(排序)对等方,以建立所有交易的总顺序。这组节点在交易上建立共识,创建块,并将它们广播到每个节点。最后,每个对等点通过检查背书策略和读写冲突来验证接收到的块中的交易,然后更新分类帐。由于验证阶段发生在最后,因此该范例称为执行订单验证。图1(c) 展示了Fabric中的交易流程。请注意,在 Fabric 中,共识协议是可插拔的,系统可以使用崩溃容错协议,例如Paxos[27],拜占庭容错协议,例如PBFT [13],或任何其他协议。
虽然Fabric通过在指定的节点子集(背书者)上执行每个交易来解决机密性问题,并通过并行执行交易(而不是像命令执行范例那样按顺序执行)来提高区块链的性能,由于其高中止率,它在具有高争用的工作负载上表现不佳,即一个块中的许多冲突交易。
如果两个交易访问相同的数据并且其中一个是写操作,则它们会发生冲突。 在这种情况下,执行交易的顺序很重要,事实上,一个块中后面的交易必须等待前面的交易先执行。因此,如果两个冲突的交易并行执行,则结果无效。尽管Fabric通过检查验证阶段(最后阶段)的冲突并忽略无效交易的影响来保证正确性,但此类冲突大大降低了区块链的性能。
III. OXII范式
在本节中,我们将介绍OXII,一种用于许可区块链的新订单执行范式。OXII主要用于支持具有高争用工作负载的分布式应用程序。
OXII由异步分布式网络中的一组节点组成,其中每个节点具有以下角色之一:
- 客户端发送要由区块链执行的操作。
- 订购者就所有交易的总顺序达成一致。
- 执行者验证和执行交易。
OXII中的节点集用表示,其中是排序者,其中是执行者。
OXII支持在区块链上并发运行的分布式应用程序。对于每个应用程序,包括该应用程序(智能合约)逻辑的程序代码安装在称为应用程序代理的(非空)执行节点子集上。我们使用来表示应用程序集(id)和Σ(Ai)Σ\left(A_i\right)来指定每个应用程序AiA_i的非空代理集,其中Σ:A→2E−∅Σ:{\char"391}→2^E-∅ 。区块链中的每个对等点都知道每个应用程序的代理和订购者集。
每对对等点都与点对点双向通信通道相连。 网络链接是成对认证的,这保证了拜占庭节点不能伪造来自正确节点的消息,即如果节点ii 在来自节点jj的传入链路中接收到消息mm,则节点jj必须事先向ii发送消息mm。
A. Orderers
检查访问、对请求排序、构建块、生成依赖图和多播块是OXII范式中orderer的主要服务。由于在区块链上运行多个应用程序并且每个应用程序可能有自己的一组客户端,因此排序者充当受信任的实体来限制对未经授权的客户端发送的请求的处理。如果客户端无权对请求的应用程序执行操作,排序者只需丢弃该请求。订购者还检查请求的签名以确保其有效性。

图2. OXII范式的组成部分
订购者使用异步容错协议来建立共识。容错协议使用状态机复制算法[26],其中副本同意传入请求的顺序。该算法必须满足两个主要属性,(1)安全性:所有正确的节点以相同的顺序接收相同的请求,以及(2)活跃性:所有正确的客户端请求最终都会被排序。Fischer等人[19]表明,在节点可能发生故障的异步系统中,共识没有既安全又有效的解决方案。基于这种不可能的结果,大多数容错协议在没有任何同步假设的情况下满足安全性,并考虑同步假设来满足活性。
OXII与Fabric [5]类似,使用可插拔的共识协议进行排序,从而产生模块化范式。根据网络和对等点的特性,OXII可能采用拜占庭、崩溃或混合容错协议。订购者的数量还取决于使用的协议和网络中同时发生的最大故障数。例如,崩溃容错协议,例如Paxos [27],在使用2f+12f+1个节点的异步网络中保证安全性(一致性),以克服拜占庭容错协议中任何ff个节点的同时崩溃故障,例如,PBFT [13],需要3f+13f+1个节点来在ff个恶意节点存在的情况下提供安全性。
此外,订购者无权访问任何智能合约或应用程序状态,也不参与交易的执行。这使得排序者独立于其他对等方并适应不断变化的环境。订购者将多个交易批处理成块。通过使数据传输更有效,尤其是在地理分布式环境中,将交易批量处理成块可以提高区块链的性能。它还摊销了密码学的成本。批处理过程是确定性的,因此在所有订购者处产生相同的块。
图2显示了OXII范式的组件。可以看出,客户端发送请求(交易)以由不同的应用程序执行。这里,交易T1T_1和T3T_3用于某个应用程序A1A_1,而T2T_2,T4T_4和T5T_5用于另一个应用程序A2A_2。排序者,即o1,o2,o3o_1,o_2,o_3和o4o_4,然后对交易进行排序并将它们放入一个块中。在图中,排序者使用PBFT[13]对请求进行排序。生成的块包含五个交易,按 [T1,T5,T4,T3,T2T_1,T_5,T_4,T_3,T_2] 排序。
接下来,排序者为区块内的交易生成“依赖graph”。为了生成依赖graph,需要先验了解交易的读写集。每个交易由一系列读取和写入组成,每次访问一条记录。这里我们假设read-set和write-set是预先声明的,或者可以通过静态分析从交易中获取,例如,交易中涉及的所有记录都通过其主键访问。请注意,即使该假设不成立,系统也可以使用其他技术,例如推测执行[18]来获取每个交易的读取集和写入集。
给定交易TT,ω(T)ω\left(T\right)和ρ(T)ρ\left(T\right) 分别用于表示写入和读取的记录集。每个交易TT还与时间戳ts(T)ts\left(T\right)相关联,其中对于块内的每两个交易TiT_i和TjT_j,TiT_i出现在TjT_j之前,ts(Ti)<ts(Tj)ts\left(T_i\right)<ts\left(T_j\right)。
我们定义“排序依赖关系”以显示来自相同或不同应用程序的两个交易之间可能存在的冲突。如果两个交易访问相同的数据并且其中一个是写操作,则它们会发生冲突。
定义:给定两个交易TiT_i和TjT_j 。当且仅当ts(j)>ts(i)ts\left(j\right)>ts\left(i\right)并且以下条件之一成立时,排序依赖 Ti>TjT_i>T_j存在:
- ρ(Ti)∩ω(Tj)≠∅ρ\left(T_i\right)∩ω\left(T_j\right)\ne∅
- ω(Ti)∩ρ(Tj)≠∅ω\left(T_i\right)∩ρ\left(T_j\right)\ne∅
- ω(Ti)∩ω(Tj)≠∅ω\left(T_i\right)∩ω\left(T_j\right)\ne∅
定义:给定一个交易块,该块的依赖graph是一个有向图G=(T,Ɛ)G=\left(T,{\char"0190}\right),其中 T 是块内的交易集,Ɛ={(Ti,Tj)∣TiTj}{\char"0190}=\left\{\left(T_i,T_j\right)|T_iT_j\right\}
我们使用图2中的例子来说明依赖graph的构建过程。可以看出,该块由五个交易组成,顺序为[T1,T5,T4,T3,T2]\left[T_1,T_5,T_4,T_3,T_2\right],即ts(T1)<ts(T5)<ts(T4)<ts(T3)<ts(T2)ts\left(T_1\right)<ts\left(T_5\right)<ts\left(T_4\right)<ts\left(T_3\right)<ts\left(T_2\right)。由于T4T_4读取由较早交易T1T_1写入的数据项bb,因此存在排序依赖关系T1>T4T_1>T_4,因此(T1,T4)\left(T_1,T_4\right)是依赖关系图的一条边。类似地,T2T_2写入数据项dd,该数据项也由T5T_5写入(T5>T2)\lparen T_5>T_2),T3T_3写入数据项ee,该数据项由T5T_5读取(T5>T3)\lparen T_5>T_3)(T5>T3)(T_5>T_3) 。结果,边(T5,T2)\left(T_5,T_2\right) 和(T5,T3)\left(T_5,T_3\right)也在图中。
执行者可以使用构建的图来管理交易的执行。特别是,依赖graph中不相互连接的交易,例如T1T_1和T2T_2,可以由独立的执行线程同时处理。
依赖graph生成器是OXII范式中的一个独立模块。因此,它也可以适应多版本的数据库系统[8]。在多版本数据库中,每次写入都会创建一个数据项的新版本,读取会根据相应交易在块(日志)中的位置定向到正确的版本。由于写入不会相互覆盖,因此系统可以更灵活地管理读取和写入的顺序。因此,对于一个块中TiT_i出现在TjT_j之前的任何两个交易TiT_i和TjT_j,TiT_i和TjT_j可以同时写入相同的数据项,或者TiT_{_i}读取和TjT_j写入相同的数据项。 但是,如果TiT_i想写和TjT_j想读同一个数据项,它们就不能并行执行。
应该注意的是,在某些依赖graph构建方法中,例如DGCC [33],交易被分解为交易组件,这允许系统在操作级别并行执行。OXII中的依赖graph生成器模块也可以用类似的方式设计。
依赖graph有两个主要好处。首先,与执行顺序范例相比,它通过暴露交易之间的冲突来降低中止率。回想一下,冲突交易会降低执行顺序范例的性能,因为如果同时执行两个冲突交易,系统必须中止后面的交易。依赖graph根据交易之间的冲突给出一个偏序,只要交易按照与依赖graph一致的顺序执行,结果就是有效的。其次,依赖graph可以实现更高的并发性。由于依赖graph提供了块内交易之间的部分顺序,因此非冲突交易仍然可以并行执行。与按顺序执行事务的传统顺序执行范式相比,这种并行性提高了OXII范式的性能。
当生成依赖graph时,排序者将包含块及其依赖graph的消息multicast给所有执行者。根据所采用的共识协议,领导者或所有排序者multicast消息。
B. 执行者
执行和验证交易,更新账本和区块链状态,以及在执行交易后multicast区块链状态是executor peer的主要服务。OXII中的执行者对应于 Hyperledger [5] 中的endorser。每个executor peer维护三个主要组件:(1)区块链分类账,(2)区块链状态,以及(3)一些智能合约。
区块链账本是一种仅附加的数据结构,以哈希链的形式记录所有交易。 当一个交易块被执行和验证时,每个执行者节点都会将该块附加到其账本副本中。
每个执行器节点是一个或多个应用程序的代理,其中每个应用程序的智能合约(即实现应用程序逻辑的程序代码)安装在节点上。当执行者从排序者那里收到一个区块时,它会检查区块内交易的应用。如果执行者是任何交易的代理,它会按照依赖graph在相应的智能合约上执行交易。 实际上,执行者确认依赖交易的顺序,并行执行独立交易。最后,它将执行结果(更新的区块链状态)多播给所有其他对等方。
对于执行者不是交易代理的块中的每个交易,执行者等待匹配从指定数量的执行者更新,他们是交易的代理,在提交之前 更新。 这些数字由系统决定并为所有执行者所知(类似于 Hyperledger 中的背书策略)。我们使用τ(A)τ\left(A\right)来表示应用程序AA的事务所需的匹配更新次数。
在图2中,执行节点e1e_1和e2e_2是应用程序A1A_1的代理(具有交易T1T_1和T3T_3),执行节点e3e_3和e4e_4是应用程序A2A_2的代理(具有交易T2T_2、T4T_4和T5T_5)。

图3. ParBlockchain中的交易流程
IV. PARBLOCKCHAIN
在本节中,我们将介绍ParBlockchain,这是一种专门在OXII范式中设计的许可区块链。我们首先对ParBlockchain进行总结,然后详细解释排序和执行阶段。
A. ParBlockchain概述
ParBlockchain是执行分布式应用程序的许可区块链。ParBlockchain是在OXII范式中设计的。特别是,ParBlockchain执行客户端请求的正常情况操作如下。
客户端向排序节点发送请求,排序节点之间运行共识算法以就交易顺序达成一致。然后排序者构建一个交易块并为该块内的交易生成一个依赖graph。
生成依赖graph后,该块连同图一起被多播到所有执行程序节点。执行者是块内某些交易的代理,执行相应的交易并将结果(即数据存储中的更新记录)multicast到每个执行者节点。网络中的每个执行程序节点都等待执行程序提供所需数量的匹配结果,以更新分类帐和区块链状态(数据存储)。每个应用程序所需的匹配结果数量由系统确定,并且对于不同的应用程序可能会有所不同。
ParBlockchain中的交易流程如图3所示,其中p3p_3、p4p_4和p5p_5是排序节点,p1p_1、p2p_2和p6p_6是执行节点,其中p1p_1和p2p_2是请求的代理。在接收到来自客户端的请求后,排序者对请求进行排序,将它们放入一个块中,为该块生成依赖关系graph,并将该块与图一起多播到所有执行程序节点。相应应用程序的代理(p1p_1和p2p_2)执行交易并将区块链的更新状态multicast到其他执行节点。在收到每个交易所需数量的匹配消息后,每个执行者通过更新区块链状态来提交(或中止)交易。该块也附加到分类帐中。
B. 排序阶段
排序阶段的目标是为所有提交的交易建立一个总订单。客户端cc通过发送消息<REQUEST,op,A,tsc,c>σc<REQUEST,op,A,ts_{_c},c>_{σc}给它认为是主要的排序节点pp(启动共识算法的排序节点)来请求某个应用程序AA的操作操作。这里,tscts_c是客户端的时间戳,整个消息都使用签名σcσ_c进行签名。我们使用客户端的时间戳来对每个客户端的请求进行完全排序,并确保执行客户端请求的语义完全一次。
收到客户端请求后,主排序者pp会检查签名以确保其有效,确保客户端被允许向应用程序AA发送请求(访问控制),然后通过将请求多播给其他排序者来启动共识算法。根据使用的共识协议,订购者之间会发生几轮通信以建立交易的总订单。
一旦订购者就交易的顺序达成一致,他们就会将交易放入一个区块中。将多个交易批处理成块提高了广播协议的吞吐量。块具有预定义的最大大小、最大交易数以及自收到新块的第一个交易以来生成块所需的最长时间。当满足这三个条件中的任何一个时,块已满。由于交易是按顺序接收的,因此前两个条件是确定性的。第三种情况,为了保证所有orderer的出块相同,primary在最后一个请求的共识步骤中发送cutblock消息。
当一个块产生时,排序者为该块生成一个依赖graph,如第III-A节所述。生成依赖graph需要先验了解交易的读写集。在这里,我们假设请求的操作包括读集和写集。
构建graph时,每个排序节点oo向所有执行节点多播一条消息<NEWBLOCK,n,B,G(B),A,o,h>σo<NEWBLOCK,n,B,G\left(B\right),A,o,h>_{σo},其中nn是块的序号,BB是由以下组成的块 请求消息,G(B)G\left(B\right)是BB的依赖graph,AA是在块中有交易的应用程序集,h=H(B′)h=H\left(B^{\prime}\right)其中 H(.)H\left(.\right)表示加密哈希函数,B′B^{\prime}是块序列号为n−1n-1 。
C. 执行阶段
对应用程序的每个请求都在指定的一组执行者(即该应用程序的代理)上执行。在收到来自某个排序者oo的新块消息<NEWBLOCK,n,B,G(B),A,o,h>σo<NEWBLOCK,n,B,G\left(B\right),A,o,h>_{σo}后,执行者ee检查签名和哈希是否有效并记录该消息。它还检查集合AA以查看该块是否包含任何需要由节点执行的交易,即应用程序Ai∈AA_i∈A使得e∈Σ(Ai)e∈Σ\left(A_i\right)。
当执行者节点收到指定数量的匹配新区块消息时,例如,如果共识协议是PBFT,则为f+1f+1条消息,它将新区块标记为有效区块并进入执行阶段。执行阶段由三个同时运行的过程组成:(1)按照依赖graph执行交易,(2)将包含执行结果的提交消息multicast到其他执行器节点,以及(3)从足够数量的执行器节点接收到提交消息后更新区块链状态。

如果执行者节点不是区块内任何交易的代理,则该节点成为被动节点,仅运行第三个过程来更新区块链状态。但是,如果一个节点是区块中某个交易应用程序的代理,它会运行所有三个程序;根据依赖graph执行相应的交易,multicast结果,并更新区块链状态。
只有当依赖graph中的所有“前身”都已提交时,才能执行交易。我们定义函数PrePre和SucSuc来分别表示依赖graph中节点的前驱和后继集。
更正式地说,给定一个依赖graphG=(T,E)G=\left(T,E\right),以及TT中的一个节点(交易)xx,Pre(x)={y∣(y,x)∈Ɛ}Pre\left(x\right)=\lbrace y|\left(y,x\right)∈{\char"0190}\rbrace 和Suc(x)={y∣x,y∈Ɛ}Suc\left(x\right)=\left\{y|x,y∈{\char"0190}\right\}。
节点ee上的执行过程如算法1所示。一个空集WeW_e 被启动以保留将由执行者ee执行的所有交易,即ee是应用这些交易的代理。Set XeX_e存储ee执行的交易,CeC_e保存已提交的交易。对于WeW_e中的每一个交易xx,过程都会检查xx的前驱,如果xx没有前驱,或者它的所有前驱都被ee执行或提交,则交易xx准备好执行,因此触发执行线程。
要根据交易的应用程序多播执行结果,可能会发生三种不同的情况。如果一个块中的所有事务都属于同一个应用程序,则代理ee执行依赖graph之后的所有交易,并将提交消息<COMMIT,S,e>σe<COMMIT,S,e>_{σ_e}多播到所有其他执行程序节点。在这里,SS表示区块链的状态,由一组对(x,r)\left(x,r\right)组成,其中xx是交易 (id),rr是在数据存储上执行xx所产生的更新记录集。请注意,如果交易xx无效,则执行者将(x,abort)\left(x,\text{abort}\right)放入SS。
如果一个块中的交易是针对不同应用程序的,但每个应用程序的交易访问一组不相交的记录,代理仍然可以独立执行相应的交易,并将包含所有结果的单个提交消息多播到其他执行器节点。
在这种情况下,依赖graph是断开的,可以分解为不同的组件,其中每个组件的交易都是针对同一个应用程序的,并且没有连接任何两个组件的边。
但是,如果两个应用程序的交易之间存在一些依赖关系,则这两个应用程序的代理无法独立执行事务。 事实上,一个应用程序的代理必须等待其他应用程序的代理执行所有事务并发送提交消息。 在这种情况下,可能会发生死锁。
图4显示了一个包含七个交易T1T_1到T7T_7的块的三个依赖关系graph。在图 4(a) 中,所有七个交易都属于同一个应用程序A1A_1。因此,应用程序 A1 的代理可以执行依赖graph之后的交易,并在所有交易都执行时将所有交易的结果一起多播。在图4(b) 中,虽然交易属于不同的应用程序(T2T_2、T3T_3、T5T_5和T7T_7用于应用程序A1A_1和T1T_1,T4T_4和T6T_6用于应用程序A2A_2),但应用程序A1A_1的交易与申请A2A_2的交易。因此,代理仍然可以独立执行并在其交易执行完成后多播结果。然而,在图4(c)中,由于两个应用程序的事务之间存在一些依赖关系,代理不能独立执行它们的交易。例如,要执行交易T2T_2,应用程序A2A_2的代理需要A1A_1的代理对交易T5T_5的执行结果。同理,交易T4T_4在提交交易T6T_6的执行结果之前不能执行。
为了防止出现死锁情况,一种可能性是代理在每个交易的执行完成后立即发送提交消息。虽然这种方法解决了阻塞问题,但交换的提交消息的数量会很大。实际上,如果一个块包含nn个交易并且每个应用程序平均有mm个代理,那么该块将总共有n⋅mn\cdot m个交换的提交消息。
一种更有效的方法是在其他一些代理需要执行结果时发送提交消息。基本上,代理不断执行交易并收集结果,直到属于其他应用程序的一些其他交易需要执行交易的结果。此时,代理会生成一个提交消息,其中包括所有执行交易的结果,并将其多播到所有执行器节点。在收到来自执行程序的提交消息后,节点验证签名并记录该消息。一旦节点接收到交易的指定数量的匹配结果,结果就会反映在数据存储中,并且交易被标记为已提交。
算法2给出了节点ee上的多播过程。 启动一个空集XeX_e来存储执行交易的结果。当一个交易xx的执行完成时,执行结果(x,r)\left(x,r\right)被添加到XeX_e中,交易xx从等待的交易WeW_e中被移除。

然后,该过程检查依赖graph中xx的所有后继节点。如果xx的任何后继节点属于与xx的应用不同的应用,则交易xx的执行结果可能会被其他代理需要,因此必须发生多播。为此,节点ee从XeX_e中删除所有存储的结果并将它们放入提交消息中,并将提交消息多播到所有其他执行程序节点。
例如,在图4(c)中,在执行交易T5T_5时,由于T5T_5有一个属于另一个应用程序的后继节点T2T_2,因此执行者节点将包括T5T_5的执行结果的提交消息多播给所有其他执行者节点。请注意,如果T1T_1已经执行,则执行者节点也会将T1T_1的执行结果放入提交消息中。类似地,当T6T_6的执行完成时,执行者节点多播一个提交消息,其中包括T6T_6的执行结果和任何其他已执行但尚未multicast的交易。

最后,更新过程从其他执行者节点接收提交消息并更新区块链状态。
节点ee上的更新过程在算法3中给出。该过程首先为块中的每个交易xx初始化一个空集Re(x)R_e\left(x\right)。它还初始化一个空集CeC_e以收集已提交的交易。当节点ee收到来自某个执行者nn的提交消息<COMMIT,S,n>σn<COMMIT,S,n>_{σn}时,它会检查签名是否有效,然后检查集合SS。回想一下,SS由交易对及其执行结果组成。对于每一对(x,r)\left(x,r\right),它首先检查节点nn是否是交易xx应用的代理,然后是一对(r,n)\left(r,n\right),即执行结果和Re(x)R_e\left(x\right)的执行者。假设AA是xx的应用程序,如果Re(x)R_e\left(x\right)中匹配的元组数等于τ(A)τ\left(A\right),即交易应用程序的指定消息数,则执行结果有效,可以提交。结果,该过程更新区块链状态(数据存储)并将交易xx添加到已提交的交易CeC_e。

图4. 三个依赖关系graph
V. 实验评估
在本节中,我们进行了几个实验来评估许可区块链的不同范式。我们在第二部分讨论了许可区块链的两种现有范例:顺序执行(OX),其中请求被排序,然后在每个节点上顺序执行,以及由Hyperledger Fabric [5]引入的执行顺序验证(XOV)其中请求由每个应用程序的代理执行,由排序服务排序,并由每个对等方验证。我们实现了两个专门在OX和XOV范式中设计的许可区块链系统以及在OXII范式中设计的ParBlockchain。需要注意的是,我们对XOV的实现不同于Hyperledger Fabric系统。 Hyperledger是一个分布式操作系统,包含许多不是我们评估重点的组件。事实上,我们实验的目的是比较区块链系统的架构方面,因此,所有三个系统都是使用相同的编程语言(Java)实现的。为了公平比较,我们还尽可能为所有三个系统使用了类似的库和优化技术。
我们实现了一个简单的会计应用程序,其中每个客户都有多个帐户。每个账户可以看成一对(金额,PK),其中PK是账户所有者的公钥。客户可以发送请求,将资产从他们的一个或多个账户转移到其他账户。例如,客户cc发起的简单交易TT可能“将xx 个单位从账户1001转移到账户 1002''。
如果cc是账户1001的所有者并且账户余额至少为xx,则交易有效。这里交易TT的读集是ρ(T)={1001}ρ\left(T\right)=\left\{1001\right\},它的写集是ω(T)={1001,1002}ω\left(T\right)=\left\{1001,1002\right\}。一个交易可能读取和写入多条记录。
实验在 Amazon EC2 平台上进行。每个VM都是经过计算优化的c4.2xlarge,具有8个vCPU和15GM RAM,主频为3.50 GHz 的 Intel Xeon E5-2666 v3处理器。对于排序节点,类似于 Hyperledger [5],我们使用典型的Kafka排序节点设置,其中包含3个ZooKeeper 节点、4个Kafka代理和3个排序节点,所有这些都位于不同的虚拟机上。除非另有明确说明,否则总共有三个应用程序,每个应用程序都有一个单独的执行者(背书者)节点。
在报告吞吐量测量时,我们会使用越来越多的客户端在单个VM上运行,直到端到端吞吐量达到饱和,并声明吞吐量刚好低于饱和。吞吐量数字报告为在实验稳定状态期间测量的平均值。

图5. 通过增加块大小来测量吞吐量/延迟
A. 选择块大小
影响吞吐量和延迟的一个重要参数是块大小。为了评估块大小对性能的影响,在这组实验中,假设交易具有相同的大小,我们将每个块中的交易数从10增加到1000。对于每个块大小,峰值吞吐量和测量相应的平均端到端延迟。如图5所示,通过将每个块的交易数增加到∼200,OXII的吞吐量会增加,但是,由于依赖graph生成所需的大量计算,任何进一步的增加都会降低吞吐量。类似地,通过将每个块的交易数增加到∼200,延迟减少。之后,向依赖graph中添加更多交易变得比多播块更耗时。因此,OXII能够在78毫秒内处理超过6000笔交易,每个区块处理 200 笔交易。在OX范式中,由于节点顺序执行交易,与执行时间相比,块创建时间可以忽略不计,因此除了第一个实验之外,增加每个块的交易数不会显着影响吞吐量和延迟。在XOV范式中,由于三个应用程序的执行者(背书者)可以并行执行交易,因此性能优于OX(峰值吞吐量是OX的两倍)。
然而,它的性能仍然远低于OXII,即XOV的峰值吞吐量是OXII峰值吞吐量的30%,因为OXII可以并行执行许多(而不仅仅是三个)非冲突交易。可以看出,XOV的峰值吞吐量是在每块约100个交易中获得的。
B. 具有争用的工作负载的性能
在下一组实验中,我们针对具有不同争用程度的工作负载测量所有三种范式的性能。我们考虑了无争用、低争用(20%冲突)、高争用(80%冲突)和完全争用工作负载,结果分别如图 6(a)-(d) 所示。请注意,第一个工作负载中每个块的依赖图没有边,而最后一个工作负载中每个块的依赖graph是一个链。在OX和OXII中,每个块有200个交易,对于XOV,我们不断更改块大小以找到其峰值吞吐量。
同一应用程序的交易或不同应用程序的交易之间可能会发生争用(如果它们访问共享数据)。在OX中,由于节点按顺序执行交易,因此这两种争用类型没有区别。同样在 XOV 中,由于执行是第一阶段,因此应用程序内或应用程序之间的争用没有太大区别,它们都会导致交易中止。然而,在OXII中,如第IV-C节所讨论的,对于跨应用程序的争用,不同应用程序的代理在执行一个交易块期间相互通信,从而影响性能。因此,在这组实验中,对于每个工作负载,我们报告了OX、XOV、OXII与应用程序内的冲突交易的性能,以及OXII与跨应用程序的冲突交易的性能(虚线)。
如前所述,在 OX范式中,交易是按顺序执行的。因此,OX的性能在不同的工作负载下保持不变。XOV可以并行执行3个(应用程序数量)交易,并且由于工作负载没有争用,因此执行结果是有效的。另一方面,OXII通过并行执行交易显着受益于无争用工作负载。如图6(a) 所示,OXII执行超过6000个交易,延迟小于80毫秒,而OX的峰值吞吐量是900个交易,延迟超过500毫秒。 XOV 还可以在 600 毫秒内执行大约1800个交易(与OXII相比,吞吐量减少70%,延迟减少7.5倍)。由于工作负载没有冲突交易,因此应用程序之间不存在争用。

图6. 通过增加工作负载的竞争程度来测量吞吐量/延迟
通过增加争用程度(图6(b) 和图 6(c)),XOV 的吞吐量急剧下降,例如,高争用工作负载中XOV的峰值吞吐量约为其峰值吞吐量的25%在无争用工作负载中。这种减少是预期的,因为XOV在最后(最后阶段)验证并中止冲突交易。OXII的吞吐量也受到竞争程度增加的影响,但是,它仍然表现出比OX和XOV更好的性能,即OXII仍然能够在亚秒级延迟内处理1600个交易,而OX和XOV处理900个交易和350笔交易。由于不同应用程序的执行程序之间的通信轮次增加,处理跨应用程序争用的工作负载会降低OXII的性能。
在完全竞争的工作负载中,如图 6(d) 所示,OXII类似于OX,按顺序执行交易,但是由于依赖图生成开销,它的性能比OX差一些。另一方面,XOV范式的性能大大降低。由于一个块内的所有交易都发生冲突,它每个块只能提交一个交易(我们减小了XOV的块大小以记录其峰值吞吐量)。
在具有跨应用程序争用的完全争用工作负载中(图 6(d) 中的虚线),OXII具有高延迟和低吞吐量。这样的工作负载可以看作是一系列翻译,其中连续的交易属于不同的应用程序。因此,为了执行每个交易,需要一对执行者之间的消息交换。
C. 多个数据中心的可扩展性
在最后一组实验中,我们测量了区块链系统在多个数据中心上的可扩展性。为此,每次我们将一组节点(即客户端、订购者、执行者或非执行者)移动到 AWS 亚太(东京)区域数据中心,而将其他节点留在AWS美国西部区域数据中心。我们考虑无争用工作负载。结果如图7所示。
移动客户端对XOV范式的影响最大,因为在XOV中,客户端参与前两个阶段。实际上,它们将请求发送给执行者(背书者),接收背书,然后将背书发送给排序节点。而在OX和OXII中,客户端发送请求并且不参与协议的其他阶段。结果,如图7(a) 所示,XOV的延迟变得更大。

图7. 通过将一组节点移动到另一个数据中心来测量吞吐量/延迟
Orderer是所有三个区块链的核心部分;他们从客户端接收交易,就交易的顺序达成一致,将交易放入块中,并将块发送到每个节点。因此,如图7(b)所示,将它们移动到较远的数据中心会导致相当大的延迟。请注意,在OX中,节点的子集被视为排序者。
在最后两个实验中,我们将执行者(背书者)和非执行者节点移动到远端数据中心。由于OX范式中的节点之间没有这种分离,因此我们不进行这两个实验。移动执行器节点为XOV中的两个通信阶段(客户端到执行器和执行器到客户端)和OXII中的一个通信阶段(排序器到执行器)增加了延迟。请注意,当executor执行消息并从其他executor接收到足够数量的匹配结果时,该事务被视为已提交。此外,由于我们考虑的是无争用工作负载,因此不需要执行者之间的通信。最后,移动非执行节点对OXII的性能没有影响,因为非执行节点只被告知区块链状态。但在XOV中,非执行者会验证区块。结果如图7(c) 和图7(d) 所示。
VI. 相关工作
Order-execute范式广泛用于不同的许可区块链。采用订单执行范式的现有许可区块链的主要区别在于它们的排序例程。 Tendermint [25]的排序协议与原始PBFT有两个不同之处,首先,只有一部分节点参与共识协议,其次,在每个区块构建后更换领导者(领导者轮换)。Quorum[14] 作为基于以太坊 [3] 的许可区块链引入了基于Raft [29]的共识协议:众所周知的崩溃容错协议。Chain Core [1]、Multichain [21]、Hyperledger Iroha [4] 和 Corda [2] 是其他一些遵循订单执行范式的著名许可区块链。正如第二部分所讨论的,这些许可区块链主要受到性能和保密性问题的影响。Hyperledger Fabric [5] 是一个许可区块链,它采用Eve [22]引入的执行顺序(-验证)范式。Fabric首次在许可区块链的背景下展示了模块化设计、可插拔容错协议、基于策略的背书和非确定性执行。最近的几项研究试图提高Fabric [20]、[30]-[32]的性能。
我们利用了一些Fabric特性,例如OXII中的模块化设计和可插拔容错协议。然而,OXII是一个命令执行范式。此外,虽然Fabric在最后阶段(验证)检查可能导致交易中止的读写冲突,但OXII通过在第一阶段(排序)生成依赖关系图来确保正确的结果。因此,具有争用的工作负载从 OXII 中获益最多。除了排序协议之外,Fabric还需要四个通信阶段(客户端到背书者、背书者到客户端、客户端到排序者以及排序者到对等方),而OXII需要三个阶段(客户端到排序方、排序方到执行者、执行者到对等方)在更少的延迟。
BlockBench[15]提出了一个框架,用于根据吞吐量、延迟、可扩展性和容错性来比较不同区块链平台的性能。在[12]中,还介绍了一些关于其共识协议的许可区块链平台的调查。
我们的工作还与DBMS中的并发控制有关。并发控制是协调对数据的并发访问的活动[7]。并发控制协议主要保证原子性和隔离性。已经提出了许多用于并发控制的技术。基于锁的协议,例如两相锁 (2PL) [10]、[16],使用锁来控制对数据的访问。基于时间戳的协议[7]、[9]在处理之前分配一个全局时间戳,通过对时间戳排序,确定交易的执行顺序。乐观并发控制 (OCC) [24]和多版本并发控制 (MVCC) [8]是两种广泛使用的基于时间戳的协议。正如第三节所讨论的,依赖graph也被最近的几项研究用于并发控制[17]、[18]、[33]。
VII. 结论
在本文中,我们提出了OXII,一种用于许可区块链的命令执行范式,以支持并发执行的分布式应用程序。OXII能够处理具有冲突交易的工作负载,而无需回滚已处理的交易或顺序执行交易。OXII解决了单个应用程序的交易以及不同应用程序的交易之间的冲突。我们还介绍了ParBlockchain,这是一个专门在OXII范式中设计的许可区块链系统。我们的实验评估表明,在具有冲突交易的工作负载中,与订单执行和执行订单许可的区块链系统相比,ParBlockchain表现出更好的性能。
原文链接:https://arxiv.org/abs/1902.01457
---煤油灯科技victorlamp.com翻译整理---