目前，区块链技术最大的限制是其串行数据结构 ——块必须逐一处理——这从根本上限制了区块链的吞吐量。虽然在应用层面上，各种区块链项目已经改变了模式，但比特币和以太坊作为区块链的创始人，仍然致力于解决扩展问题。

在保持区块链分散化的初衷下，比特币扩容方案一般可分为区块派和隔离派。区块派主要通过增加单个区块容量和单个矿工可处理的交易量来提高整体处理速度；隔离派主张建立闪电网络，通过将小额交易转移到闪电网络来提高链速度，然而，区块派和隔离派的方案都无法摆脱区块链串行数据结构的影响，最终将达到扩展的上限。以太坊在比特币的基础上增加了图灵完整的智能合约，催生了1CO，但其创始人V神本人也一直在解决拓展性问题，目前V神相对倾心PoS和分片两种方案，选择PoS存在集中隐患，但分片尚未实现。

几年来，随着行业的快速发展，许多区块链项目和链应用应用应运而生，但每条链都是独立、垂直、封闭的系统。不同的区块链之间有障碍，就像孤岛一样。价值不能自由快速流通，生态不能对接，系统不能生长，区块链处于散沙状态。为此，如最近出现的cosmos、polkadot，它们都是解决跨链问题的项目，但由于数据结构设计是异构网络环境，通过IBC协议链交互、链结构环境和中继器机制使跨链协作差，存在异步特性带来的低效风险，哈希锁定不支持多货币智能合同，无法从本质上解决跨链互联问题。

区块链本质上是一个不断更新的分布式共享账簿，由多方参与，共同维护。多节点的公平参与使区块链具有分散的特点，但为了提高交易速度，如EOS采用的PoS共识牺牲了分散化，分散化是区块链长期扩张、确保安全可篡改、存储共识和价值的最基本特征。分散的区块链只能解决当前的问题，而不能真正进行长期的价值发展。

从上面我们可以看出，区块链的各种扩展实际上都受到其串行结构本身的制约，块必须逐一出现理。这就像车辆在单车道驾驶，受制于道路难拓，一旦车辆增多，无论车速多快，最终都会产生拥堵。用并行来解决拓展性问题，也并不是难以相见的迷思：无论是电信领域从对讲单机传输到CDMA时代，或是计算机从单核CPU到多核CPU，用并行解决拓展性问题是必然选择。

并行结构中，各子链可以在不影响数据一致性的前提下，根据容量需求动态的增加或减少数量。具体来说，即用户可在链上自定义分片触发条件，当达到条件时，链资源可以便捷的在子链负载过载触发机制达到的情况下开展子链分片及收拢，实现在事务增多时，必要的条件下并行出块，保证链层性能，使得底层事务处理速度不受事务容量的影响。

除以上对于单条子链运用动态分片满足性能要求外，对于整个并行区块链系统通过多链并行使区块链系统资源得到无限的拓展性；同时通过非对抗性性记账方式，避免恶性节点竞争及算力浪费，且不存有特权节点，实现完全去中心化，保证系统的公平，同样保证无限资源聚集效应，使得系统具有永久拓展性。

在并行区块链系统下，可实现天然跨链，使得链与链之间可以实现互通，进行交互，将原来如“局域网”一般相互隔离的区块链连成一张可以无限拓展的大网。最直观的表现，就是两条链上的权益或资产价值转化，不再需要中心化交易所来完成；跨链的信息交互，就是信息的传递，在不改变原链结构的前提下，实现信息从一条链到另一条链上的传递。

未来，当区块链进而大规模、商业化落地使用的时候，并行链的天然跨链技术特性的优势将凸显出来。其不仅能实现不同链之间资产的自由流通，更重要的是能够无限释放不同链的潜力，让更多的用户参与，使更多的链可以连通，最终形成一个真正的大生态。

这样具有无限拓展性和跨链互联性的并行区块链系统才具有了成为区块链底层操作系统的资格和成为下一代价值互联网络的雏形。

现在并行链项目，经常用主链、侧链、父链、子链等名词来代替并行链，其实他们与并行链有着天壤之别。侧链和主链的界定，一定程度上说明主链地位独一无二，这就无法保证多链平等一致等特征。

其次，目前大部分主链+侧链的结构中，基本都在上演侧链拿主链的秘方随意开店，并声称自己是主链的侧店，而是否和主链事务账务一致，无从查证。这更像是花开两朵，各表一枝的分叉；而不是并行运行下，身处一个时空维度的并行区块链。

从以上诸多伪并行链的例子上可以看出，要想真正架构并行区块链系统，必须首先解决各链之间的通讯问题，实现链链之间的并行一致性，这样才能保证每条子链在独立运行的同时，又构成了一个互通互联的并行区块链系统。

而目前成功研发出这一适用于并行系统算法的有一个名为Paralism的项目。据了解，Paralism被称为全球首家并行区块链创新项目，是并行区块链支撑的数字经济平台。Paralism将区块链从线性串行升维到并行系统，具有了以上所提到的动态分片功能、无限扩展性和跨链互联性，更重要的是，它发明了世界上现有唯一适用于并行区块链系统且完全去中心化的共识算法，并已获得授权。

从官网可知，项目从2016年起步。其从区块链原有架构出发，认为区块链发展的一个重要擎制仍是基础设施，只有在底层高效运转且可拓展的基础上，区块链商业应用才能发展和落地，区块链才能担纲未来价值互联的基础技术。

2018年12月，Paralism底层技术团队超块链提交的并行区块链基础技术获得国家授权，此类区块链专利国家级背书在并行链圈鲜见。对于并行区块链而言，最关键的是解决链与链之间的通讯和数据一致性的问题，这也是诸多采用主链+侧链结构并行区块链所存在的核心问题。

超块链自行研发了Buddy共识算法，不同于dPoS的权利为上、也不似PoW的资源浪费，是唯一适用多链环境、完全去中心化的共识算法。具体通过有同样上链请求之间的节点互证来形成共识，使所有节点可以同时参与、并行出块，满足了并行链之间形成系统级全局共识的需求，并且保证了节点之间的对等位置，实现了真正的去中心化，避免特权节点和算力浪费及两者对于网络扩展的影响。

目前，解决扩容度、交互性、个性化、安全性等诸多硬需求，且是由真正的并行区块链技术支撑的数字经济平台Paralism（http://www.paralism.com）已经上线运行。

一链一资产、一链一应用，并行链无限拓容可以做到；发布媲美比特币、各类稳定币等数字资产，可以一键自助式高效发行。破除价值孤岛，链接全球范围数字资产，Buddy共识满足跨链交互，而且，并行链为区块链小白提供了自助开发工具、适配行业需要的自定义共识，并行链的多样性与独立性，让全世界资产及权益在链上尽情传输跳动。

无论在性能上，还是在用户规模上，现在入场做价值链接及工具基础设施提供商，Paralism都以其核心并行区块链技术呈现强大潜力。正如风险投资家马克·安德森在《华盛顿邮报》的一篇采访中所说那样，“在 20 年后，我们就会像讨论今天的互联网一样讨论区块链”。而这里的并行区块链支撑的Paralism有望引领区块链所支撑的价值互联的未来。

区块链(blockchain)可以看成是一种新型的分布式事务处理系统,其与传统的分布式事务处理系统主要有 2 点不同:

• (1) 区块链节点是允许互相不受信任的,故每个节点需独立维护着一份与其它节点一致的账本,即一串 前后相连的区块(block).

• (2) 对于新区块中的智能合约交易,区块链中的每个节点都将在各自的环境中执行一遍.

智能合约(smart contract)是由用户定义并部署在区块链上的代码,类似于编程语言中的类(class)，包含了一批共享数据对象和函数,可以通过函数操作数据对象,以向用户提供一些复杂功能.这些数据代表了当 前智能合约的状态,而所有智能合约的状态则构成了当前节点的区块链状态

交易(transaction)又称为事务,是用户从区块链外部调用智能合约的指令,每个交易都可以指定其要调用 的智能合约函数和本次调用输入的参数值.

如果两个并行执行的智能合约交易访问了同一个共享数据对象,并且至少其中一个执行了写操作,那么这 两个合约交易就会产生冲突. 在这种情况下,必须等待前一个合约交易执行完毕,后一个合约交易才能执 行.

如果两个智能合约交易是冲突的,那么它们之间存在依赖关系. 对于一个智能合约交易 Tx, ω(Tx)代表一 组写操作,ρ(Tx)代表一组读作,timestamp(Tx)代表创建该交易的时间戳.如果两个交易 Txi 和 Txj 存在依赖关 系 Txi→Txj,当且仅当 timestamp (Txi) < timestamp (Txj)和下面的至少一个条件同时成立: 因此,判断同一时刻两个合约交易能否被并行执行,就是判断这两个智能合约交易的读写集是否存在交集, 交集为空的合约交易可以被并行执行.

以太坊等区块链的智能合约执行模型可以抽象分为 2 个阶段.

阶段 1 是出块阶段

出块节点选取一批新的智能合约交易,然后串行执行这批交易调用的智能合约以得到 区块链的最终状态(final state), 最终生成一个包含这批交易和区块链最终状态的新区块.

阶段 2 是验证阶段

验证节点接收到新区块时,重新串行执行这批智能合约交易,并将自己节点生成的最终 状态和出块节点生成的最终状态进行比对,如果一致,则接受该区块,如果不一致,则丢弃该区块

以太坊等区块链执行智能合约的特点可归结如下:

(1) 一个区块包含多个智能合约交易,类似于批处理; (2) 一个区块中的交易是按照顺序串行执行的,类似于状态机; (3) 执行过程中包含对共享账本的读写操作; (4) 每个节点都需要完全执行一遍区块中的智能合约交易.出块节点必须执行这批智能合约交易,才能生成一个完整的新区块.验证节点必须重新执行新区块中的智能合约交易,才能验证该区块的有效性; (5) 区块中的智能合约交易被执行完毕时,每个节点的最终状态应该一致.

在一个区块中,不同的交易可能调用了同一个智能合约.如果直接并行执行这些交易,则可能对智能合约 的共享数据对象进行存在冲突的读写,从而出现丢失更新、脏读等问题,导致最终的执行结果错误.

如图所示,智能合约交易 Tx1 和 Tx2 被并行执行,其中 Tx1 表示将用户 X 的账户增加 10 元,Tx2 表示将用 户 X 的账户增加 20 元.在 Time 1 时刻,Tx1 和 Tx2 读取到的 X 的值均为 100.在 Time 2 时刻,Tx2 执行了写入操作,X 的值被更新为 120.在 Time 3 时刻,Tx1 执行了写入操作,X 的值被更新为 110.显然,并行执行 Tx1 和 Tx2 生成的结 果是错误的.

验证一个区块的有效性需要确定性地执行智能合约交易,验证节点才能产生和出块节点一样的最终状 态.以不同的串行化顺序执行存在冲突的交易,这将可能导致不同节点得到不一致的区块链最终状态.

如图所示,出块节点对并行执行的串行化执行顺序是先执行 Tx1,再执行 Tx2,共享数据对象 a 最终的值是 20.而验证节点对并行执行的串行化执行顺序是先执行 Tx2,再执行 Tx1,共享数据对象 a 最终的值是 10.显然,验 证节点与出块节点分别得到了不一致的区块链最终状态,因此验证节点会丢弃该区块.

为解决并行执行智能合约交易可能引发的问题,实现智能合约的并行执行存在如下 2 项关键任务.

智能合约交易能否被正确地并行执行的关键在于识别出交易集中具有依赖关系的冲突交易.区块链中执行智能合约类似于多线程操作共享内存中的对象,并行执行的多个智能合约交易可能操作了同一个共享数 据对象,从而产生数据竞争,出现丢失更新和脏读等问题.同时,因为用来编写智能合约的 Solidity等语言是图 灵完备的,直接识别出冲突的合约交易是不太可能的

区块链中每个节点的最终状态必须保持一致,因此要求所有节点都能以等价的执行顺序正确地并行执行 同一批智能合约交易.生成等价的执行顺序的关键在于对冲突的交易拥有相同的串行化执行顺序, 这确保了 各个节点并行执行智能合约交易时能够将其中冲突的交易按某种相同的顺序串行执行.如果验证节点只 是简单地重新并行执行新区块中的智能合约交易,则可能会产生不同的串行化执行顺序和不同的区块链最终 状态,从而导致新区块验证失败.因此,所有节点都应该确保其并行执行的串行化顺序是等价的.

一个无环的有向图称做有向无环图（Directed Acyclic Graph），简称DAG图。在一批交易中，可以通过一定方法识别出每笔交易需要占用的互斥资源，再根据交易在Block中的顺序及互斥资源的占用关系构造出一个交易依赖DAG图，如下图所示，凡是入度为0（无被依赖的前序任务）的交易均可以并行执行。如下图所示，基于左图的原始交易列表的顺序进行拓扑排序后，可以得到右图的交易DAG。

DAG最初出现是为了解决区块链的效率问题。比特币的效率一直比较低，基于工作量证明共识下的出块机制是一个原因，由于链式的存储结构，整个网络中同时只能有一条链，导致出块无法并发执行。

针对此问题，Nxt社区提出改变区块的链式存储结构，变成区块DAG。在区块打包时间不变的情况下，网络中可以并行打包N个区块，网络中的交易就可以容纳N倍。但此种方式仍停留在类似侧链的解决思路，不同的链存储不同类型的交易，这样降低出现双花的可能，在之后某个节点需要合并的时候，几个分支再归并到一个区块。

Nxt社区提出的DAG of blocks

换一种思路，上述方案都属于有区块的情况，无论是在比特币还是以太坊中，我们都会提到出块速度这样的概念，比特币每十分钟出一个块，6 个出块确认需要一个小时，以太坊好很多，但是出块速度也要十几秒。能否舍弃区块的概念呢？ 2015年社区提出DAGCoin的概念，把区块和交易融合到了一起。回想下比特币网络中区块和交易的概念，很多笔交易先打包到区块中，区块和区块之间通过 PreHash 来维护全网的交易顺序。而 DAGCoin 的思路是让每一笔交易直接参与维护全网的交易顺序。这样交易被发起后直接跳过打包区块的阶段，直接融入全网，如此达到无区块效果，且连打包交易出块的时间都省去了。如前所述， DAG 最初跟区块链的结合就是为了解决效率问题，现在不用打包确认，交易发起后直接进入确认网络，理论上效率自然会提高很多。

效率问题：传统区块链技术基于区块，比特币的效率一直比较低，由于 BlockChain 链式的存储结构，整个网络同时只能有一条单链，基于 PoW 共识机制出块无法并发执行。

确定性问题：比特币和以太坊存在 51% 算力攻击问题，基于 PoW 共识的最大问题隐患，就是没有一个确定的不可更改的最终状态；如果某群体控制 51% 算力，并发起攻击，比特币体系一定会崩溃；考虑到现实世界中的矿工集团，以及正在快速发展量子计算机的逆天算力，这种危险现实中会存在。

中心化问题：基于区块的PoW共识中，矿工一方面可以形成集中化的矿场集团，另一方面，获得打包交易权的矿工拥有巨大权力，可以选择哪些交易进入区块，哪些交易不被处理，甚至可以只打包符合自己利益的交易，这样的风险目前已经是事实存在。

能耗问题：由于传统区块链基于PoW算力工作量证明，达成共识机制，比特币的挖矿能耗已经与阿根廷整个国家的耗电量持平，IMF和多国政府对虚拟货币挖矿能源消耗持批评态度。Digiconomist 数据表明：全球挖矿业务总计，每年产生约 2.9 亿吨碳排放。

单元：区块链组成单元是Block（区块），DAG组成单元是TX（交易）。

拓扑：区块链是由Block区块组成的单链，只能按出块时间同步依次写入，类似于单核单线程CPU；DAG是由交易单元组成的网络，可以异步并发写入交易，类似于多核多线程CPU。

粒度：区块链每个区块单元记录多个用户的多笔交易， DAG 每个单元记录单个用户交易。

DAG 区块链与传统区块链工作机制的不同之处在于，后者需要矿工完成工作量证明（PoW）来执行每一笔交易，而 DAG 区块链能摆脱区块链的限制来完成这样的操作。不同的是，在 DAG 区块链中一笔交易接着另外一笔，这意味着一笔交易能够对下一笔交易提供证明，由此一直排序下去。这些交易之间的连接就是 DAG，就像区块通过哈希值来向整条区块链提供它们的名字一样。

在传统块链式区块链中，每笔交易都要花费不少时间，而对于 DAG 区块链来说，交易时间将变得微不足道。由于每笔交易都与下一笔交易相连，且矿工被排除在外，交易时长会随着越来越多用户加入系统而缩短。

在DAG系统中，剔除矿工的设置能够避免像区块链系统中某一个矿池集合全网50%算力的威胁，与双重攻击的隐忧。没有了区块链中的工作量证明共识机制，DAG 的交易指令能够极快地扩散通知至全网，大部分双重支付的攻击尝试将会被系统捕捉到并立即拒绝执行。

和以太坊相比，DAG 网络虽然不具备智能合约强制执行的特性，但它能为用户提供一个相对简单、清晰易辨的架构，以太坊的系统则要复杂许多。这不仅使得用户能更容易去理解 DAG 区块链上的虚拟货币什么时候以及怎样进行支付，而非依靠着一个满是程序员和合约的世界。从这个角度来看，可以把 DAG 网络看成是一个智能合约缺席执行者和旁观者的版本。

如果DAG区块链能得到更为广泛的应用，它在几乎每个级别都能显露出比传统区块链更优的特性。在目前区块链系统中，随着交易时长这样的问题显现出来，DAG区块链势必将受到越来越广泛的关注。

基于静态分析的并行执行模型主要分为 2 个模块,资源占用隔离模块和并行执行模块.如图所示,资源占用隔离模块采用静态分析方法,根据智能合约源代码（或其它辅助信息）里对共享数据对象的定义,提取每个 交易将占用的资源集合.然后通过交易依赖图方法或者资源互斥分组方法记录交易间的依赖关系.并行执行模 块可以根据机器的 CPU 核数初始化对应数量的线程,不同的线程并行执行交易依赖图中不存在依赖关系的交 易(或不同的分组),同时无需担心在执行过程中会发生任何冲突.

交易依赖图通常使用有向无环图(DAG)表示,其记录了一个区块内所有交易的依赖关系,使用顶点代表交 易,使用有向边代表 2 个交易间的依赖关系,即执行顺序.

基于交易依赖图,区块链节点可以并行执行那些无依赖关系的合约交易.

(1)区块链节点首先根据机器的 CPU 核心数初始化一个相应大小的线程池.

(2)入度为 0 的合约交易允许被不同的线程直接并行执行,如图中 的 Tx1、Tx2 和 Tx3,这个过程是安全的,因为它们没有任何依赖的前驱交易.

(3)执行完毕后,如果被执行的合约交 易所在顶点的出度不为 0,则消除以该顶点为起点的有向边,以该有向边为终点的顶点的入度同时减一.

(4)重复 第 2 步和第 3 步直到区块中全部合约交易都被执行完毕.

资源互斥分组方法根据合约交易访问的共享资源集合,发现共享资源的占用关系,从而将合约交易按照共 享资源的占用关系划分到不同的组中.访问相同共享资源的合约交易将被划分到同一个分组中,即每个分组的 内部都是存在冲突的合约交易.同时,每个分组之间的交易都是不冲突的,因为它们之间不存在任何共享资源的 交集.

可以通过生成一个资源依赖图(无向图)求得所有分组.如图所示,每个顶点代表一个共享资源,若一个交 易占用了 2 个不同的共享资源,这两个资源的顶点之间将会生成一条无向边.互相冲突的交易将会组成一个连 通分量,每一个连通分量代表了一个独立的分组,因此可以使用并查集,求得所有互斥的分组

区块链节点可以采用数据库中的并发控制技术试探地并行执行所有合约交易,以此 来保证并行执行的正确性.

锁(locking)是一种悲观的并发控制方法,智能合约交易执行时对某个共享数据对象进行操作(读操作或写 操作),都会对其请求加锁,只要加锁成功,就拥有了对该共享数据对象的控制权.若是排它锁,则在其释放前,其它 智能合约交易不能再对该共享数据对象进行读取和修改;若是共享锁,则在其释放前,其它智能合约交易只能对 该共享数据对象进行读取,但不能修改.

多版本并发控制(MVCC)是一种可以解决读写冲突的无锁并发控制策略,即使存在读写冲突,也可以实现 不加锁的非阻塞并发读.每个智能合约交易在执行写操作时不会直接覆盖数据项,而是会保留数据项的每个版 本.每个读操作都可以读取到其想要读取版本的数据,因此可以避免因为读太迟而导致的交易冲突.总之,读操 作不用阻塞写操作,写操作不用阻塞读操作,多版本并发控制有效减少了交易冲突.

软件事务内存(STM)作为一种新型的并行编程模式,相较锁机制存在代码复杂度高和易死锁等问题,STM 允许开发者将一组需要访问共享内存的操作封装成一个事务,然后以原子操作的方式运行.该事务满足原子 性和独立性,原子性要求这组操作要么都执行成功,要么都不执行.独立性意味着这组操作所做的更新仅在成功 提交时才对共享内存可见,因此,多个事务可以并行执行,具有乐观性质.

节点间并行执行模型是指通过让区块链节点在交易处理架构“排序-执行-验证-提交”的某个过程并行以 提高区块链系统的吞吐率,其主要包含 2 种并行方法,一是让将“执行交易”置于“排序交易”之前,通过让不 同的区块链节点并行执行来自不同客户端的交易,以提高区块链系统的处理能力.二是针对于全网节点在某一 时刻具有确定的待执行交易集的区块链,让出块节点和验证节点在智能合约交易的执行阶段并行,从而提高区 块链系统的吞吐率.

受启发于数据库中乐观并发控制机制,Hyperledger Fabric提出了 一种新的交易处理架构“执行-排序-验证-提交”.这种新架构中,合约交易的排序和执行是分开的,并且将“执 行交易”置于“排序交易”之前.本文将可以执行交易的节点称为执行节点(如 Hyperledger Fabric 中的背书节 点和 XuperChain中的全节点),负责排序出块的节点仍然称为出块节点(如 Hyperledger Fabric 中的排序服务 和 XuperChain 中的矿工节点).

XuperChain 同样采用了“执行-排序-验证-提交”架构.如图所示,客户端首先向一个执行节点提交包含 智能合约执行参数的预执行请求(Hyperledger Fabric 中称为模拟执行);该执行节点基于当前区块链状态进行模拟执行,此过程并不修改该执行节点的区块链账本状态,然后将读写集返回给客户端;客户端组装一个包含该读 写集的交易,发送给区块链网络;出块节点收集和排序一批交易以生成一个新区块,并将其广播给所有执行节 点;执行节点验证新区块的有效性,并更新本地的区块链账本状态.

显然,一个执行节点除了自身可以并行处理不同的预执行请求,还能与其它执行节点并行处理更多的来自 不同客户端的预执行请求,这是一种并行能力的放大.

采用 PoW 共识机制的区块链,所有节点都在争夺出块权,并不能确定哪个节点是此时的出块节点,每个节 点打包的交易集是不同的,具有随机性.因此,验证节点必须在出块节点生成新区块之后才能知道需要执行的 交易集,即验证阶段的交易执行一定位于出块阶段的交易执行之后.但对于许可链,节点间是互相信任的,可以 由专门的节点(可以是出块节点)选择一批新交易进行排序,再广播给其它节点执行.

如图所示,因为交易集和出块节点在此刻是确定的,那么可以让所有节点(包括出块节点和验证节点)同 时执行交易集,等待出块节点执行完所有智能合约交易之后,出块节点将包含执行结果的新区块广播给其它节 点,其它节点通过比较自己的区块链最终状态和出块节点的区块链最终状态是否一致以判断出块节点生成的 新区块的有效性.

这种出块节点和验证节点并行的方式,让验证节点不必等待出块节点将智能合约交易执行 完毕就可以开始执行这批智能合约交易,这极大地缩短了验证阶段的耗时.

分治并行执行模型如图所示,负载划分模块根据一定的规则,将全部的合约交易划分为不同的子集,并 分配到不同的子链进行执行.因为子链之间是并行的,从而提高了整个区块链系统的吞吐率.

分片方法(sharding) 是一种被给予厚望的并行方案, 其能够对网络中的计算资源实现更有效的管理.分片方法将整个区块链根据一定规则划分成多个子集,每个子集被称为一个分片(shard),每个分片具 有独立的状态和账本.区块链网络中所有新交易将按照规则分配到不同的分片中,分片间并行执行这些交易.由 于每个分片只需要处理一部分交易,因此增加了整个区块链系统的吞吐量.在比特币、以太坊等传统区块链中, 增加节点的数量只会增加系统的安全性,但不会增加系统的吞吐率.与此不同的是,采用分片方法的区块链因为 分片数量的增加,其交易处理的并行度也将线性增加.

通道方法(channel)被开源的企业级许可链平台 Hyperledger Fabric采用,具有极佳的保密性和可伸缩 性.比如在一个供应链金融的区块链网络中,参与方包括核心企业、供应商、银行和物流企业等.不同的参与方 各自运行一个区块链节点.显然,该区块链提供的金融服务不需要物流企业的节点参与共识和保存账本数据.同 时,该区块链提供的物流服务也不需要金融机构的节点参与共识和保存账本数据.通道方法允许需要进行私有 交易的成员与业务竞争者或其他受限制的成员在同一个区块链网络中共存.

通道相当于某几个网络成员之间进行通信的私有“子网”,每个通道都维护着自己的账本数据.在模拟执行阶段,每个背书节点只接收和执行在其通道内有权限的客户端发起的交易提案.在排序阶段, 排序服务为每个通道创建单独的区块.在验证阶段,节点只接收在同一个通道上的区块进行验证.在提交更新阶 段,验证通过的区块只会追加到在同一个通道的节点的账本.可以发现,Hyperledger Fabric 的通道隔离模型类似 于其它区块链的分链模型,通道为交易处理的各个方面都带来固有的并行性

分区方法被王嘉平等提出的 Monoxide 区块链采用.如图所示,系统会被分为多个区域(zones),每个分 区被称为一个异步共识区.每个异步共识区都拥有自己的区块链账本、状态数据库等,能够在各自的分区内完 成交易的处理和区块的共识.不同的合约交易会根据规则映射到某个分区进行处理,不同分区的合约交易因此 可以被并行执行,从而提高了整个区块链系统的吞吐率.分治并行执行模型都会存在因为算力稀释导致子链安 全性下降的问题. 这是因为每个子链只是由系统中的部分节点运行.对于区块链来说,越多的节点参与共识, 黑客聚集大于 51%算力的难度就越大,系统就越安全.与其它分治并行执行模型不同的是,王嘉平等提出了“连 弩挖矿”方法以应对算力稀释导致的安全性下降问题

侧链方法同样被许多区块链采用以实现智能合约交易并行执行.aelf 是一个基于多级侧链的并行化区块 链框架,其主链负责统一规划和索引,侧链独立运行,每条侧链专门负责一项功能服务.不同功能服务的合约 交易可以在所属的侧链上并行执行,因此得以提高整个区块链系统的合约交易执行效率.同时,侧链可以通过主 链的验证以实现跨链交互.此外,每个子链中采用了资源互斥分组方法,交易集会根据冲突关系被划分为多个分 组,同组内的合约交易串行执行,不同组的合约交易并行执行.

群组方法被 FISCO BCOS用来实现其分治并行执行模型.每个区块链节点都可以根据实际业务关系,自 由组成多个群组.如图所示,每个群组拥有一个属于自己的独立账本,其交易处理、数据存储和区块共识都是 与其它群组相互隔离的.这种架构在保障隐私性的同时,允许不同群组间的交易合约可以被并行执行,从而提高了整个区块链系统的处理能力.

区块链世界中，交易是组成事务的基本单元。交易吞吐量很大程度上能限制或拓宽区块链业务的适用场景，愈高的吞吐量，意味着区块链能够支持愈广的适用范围和愈大的用户规模。当前，反映交易吞吐量的TPS（Transaction per Second，每秒交易数量）是评估性能的热点指标。为了提高TPS，业界提出了层出不穷的优化方案，殊途同归，各种优化手段的最终聚焦点，均是尽可能提高交易的并行处理能力，降低交易全流程的处理时间。

在多核处理器架构已经成为主流的今天，利用并行化技术充分挖掘CPU潜力是行之有效的方案。FISCO BCOS 2.0 中设计了一种基于DAG模型的并行交易执行器（PTE，Parallel Transaction Executor）。

PTE能充分发挥多核处理器优势，使区块中的交易能够尽可能并行执行；同时对用户提供简单友好的编程接口，使用户不必关心繁琐的并行实现细节。基准测试程序的实验结果表明：相较于传统的串行交易执行方案，理想状况下4核处理器上运行的PTE能够实现约200%~300%的性能提升，且计算方面的提升跟核数成正比，核数越多性能越高。

PTE为助力FISCO BCOS性能腾飞奠定了坚实基础，本文将全面介绍PTE的设计思路及实现方案，主要包括以下内容：

背景：传统方案的性能瓶颈与DAG并行模型的介绍 设计思路：PTE应用到FISCO BCOS中时遇到的问题以及解决方案 架构设计：应用PTE后FISCO BCOS的架构及核心流程 核心算法：介绍主要用到的数据结构与主要算法 性能测评：分别给出PTE的性能与可扩展性测试结果

FISCO BCOS交易处理模块可以被抽象为一个基于交易的状态机。在FISCO BCOS中，『状态』即是指区块链中所有账户的状态，而『基于交易』即是指FISCO BCOS将交易作为状态迁移函数，并根据交易内容从旧的状态更新为新的状态。FISCO BCOS从创世块状态开始，不断收集网络上发生的交易并打包为区块，并在所有参与共识的节点间执行区块中的交易。当一个区块内的交易在多个共识节点上执行完成且状态一致，则我们称在该块上达成了共识，并将该区块永久记录在区块链中。

从上述区块链的打包→共识→存储过程中可以看到，执行区块中的所有交易是区块上链的必经之路。传统交易执行方案是：执行单元从待共识的区块逐条读出交易，执行完每一笔交易后，状态机都会迁移至下一个状态，直到所有交易都被串行执行完成，如下图所示：

显而易见，这种交易执行方式对性能并不友好。即使两笔交易没有交集，也只能按照先后顺序依次执行。就交易间的关系而言，既然一维的『线』结构有这般痛点，那何不把目光投向二维的『图』结构呢？

在实际应用中，根据每笔交易执行时需要使用的互斥资源（互斥意味着对资源的排他性使用，比如在上述转账问题互斥资源中，指的就是各个账户的余额状态）， 我们可以组织出一张交易依赖关系图，为防止交易依赖关系在图中成环，我们可以规定交易列表中牵涉到相同的互斥资源，且排序靠后的交易，必须等待靠前的交易完成后才被执行，由此得到的输出便是一张反映交易依赖关系的有向无环图，即交易DAG。

如下图所示，左侧的6笔转账交易可以组织为右侧的DAG形式：

在交易DAG中，入度为0的交易是没有任何依赖项、可以被立即投入运行的就绪交易。当就绪交易的数量大于1时，就绪交易可以被分散至多个CPU核心上并行执行。当一笔交易执行完，依赖于该交易的所有交易的入度减1，随着交易不断被执行，就绪交易也源源不断被产生。在极限情况下，假如构造出的交易DAG层数为1 （即所有交易均是没有依赖项的独立交易），则交易整体执行速度的提升倍数将直接取决于处理器的核心数量n，此时若n大于区块内的交易数，则区块内所有交易的执行时间与单笔交易执行的时间相同。

理论上拥有如此让人无法拒绝的优美特性的交易DAG模型，该如何应用至FISCO BCOS中？

要应用交易DAG模型，我们面临的首要问题便是：对于同一个区块，如何确保所有节点执行完后能够达到同一状态，这是一个关乎到区块链能否正常出块的关键问题。

FISCO BCOS采用验证(state root, transaction root, receipt root)三元组是否相等的方式，来判断状态是否达成一致。transaction root是根据区块内的所有交易算出的一个哈希值，只要所有共识节点处理的区块数据相同，则transaction root必定相同，这点比较容易保证，因此重点在于如何保证交易执行后生成的state和receipt root也相同。

众所周知，对于在不同CPU核心上并行执行的指令，指令间的执行顺序无法提前预测，并行执行的交易也存在同样情况。在传统的交易执行方案中，每执行一笔交易，state root便发生一次变迁，同时将变迁后的state root写入交易回执中，所有交易执行完后，最终的state root就代表了当前区块链的状态，同时再根据所有交易回执计算出一个receipt root。

可以看出，在传统的执行方案中，state root扮演着一个类似全局共享变量的角色。当交易被并行且乱序执行后，传统计算state root的方式显然不再适用，这是因为在不同的机器上，交易的执行顺序一般不同，此时无法保证最后的state root能够一致，同理，receipt root也无法保证一致。

在FISCO BCOS中，我们采用的解决方案是先执行交易，将每笔交易对状态的改变历史记录下来，待所有交易执行完后，再根据这些历史记录再算出一个state root，同时，交易回执中的state root，也全部变为所有交易执行完后最终的state root，由此就可以保证即使并行执行交易，最后共识节点仍然能够达成一致。

搞定状态问题后，下一个问题便是：如何判断两笔交易之间是否存在依赖关系？

若两笔交易本来无依赖关系但被判定为有，则会导致不必要的性能损失；反之，如果这两笔交易会改写同一个账户的状态却被并行执行了，则该账户最后的状态可能是不确定的。因此，依赖关系的判定是影响性能甚至能决定区块链能否正常工作的重要问题。

在简单的转账交易中，我们可以根据转账的发送者和接受者的地址，来判断两笔交易是否有依赖关系，比如如下3笔转账交易：A→B，C→D，D→E，可以很容易看出，交易D→E依赖于交易C→D的结果，但是交易A→B和其他两笔交易没有什么关系，因此可以并行执行。

这种分析在只支持简单转账的区块链中是正确的，但是一旦放到图灵完备、运行智能合约的区块链中，则可能不那么准确，因为我们无法准确知道用户编写的转账合约中到底有什么操作，可能出现的情况是：A->B的交易看似与C、D的账户状态无关，但是在用户的底层实现中，A是特殊账户，通过A账户每转出每一笔钱必须要先从C账户中扣除一定手续费。在这种场景下，3笔交易均有关联，则它们之间无法使用并行的方式执行，若还按照先前的依赖分析方法对交易进行划分，则必定会掉坑。

我们能否做到根据用户的合约内容自动推导出交易中实际存在哪些依赖项？答案是不太靠谱。我们很难去追踪用户合约中到底操作了什么数据，即使做到也需要花费不小的成本，这和我们优化性能的目标相去甚远。

综上，我们决定在FISCO BCOS中，将交易依赖关系的指定工作交给更熟悉合约内容的开发者。具体地说，交易依赖的互斥资源可以由一组字符串表示，FISCO BCOS暴露接口给到开发者，开发者以字符串形式定义交易依赖的资源，告知链上执行器，执行器则会根据开发者指定的交易依赖项，自动将区块中的所有交易排列为交易DAG。比如在简单转账合约中，开发者仅需指定每笔转账交易的依赖项是｛发送者地址+接收者地址｝。进一步地，如开发者在转账逻辑中引入了另一个第三方地址，那么依赖项就需要定义为｛发送者地址+接受者地址+第三方地址｝了。

这种方式实现起来较为直观简单，也比较通用，适用于所有智能合约，但也相应增加了开发者肩上的责任，开发者在指定交易依赖项时必须十分小心，如果依赖项没有写正确，后果无法预料。指定依赖项的相关接口会在后续文章中给出使用教程，本文暂且假定所有谈论到的交易依赖项都是明确无误的。

解决完上面两个比较重要的问题后，还剩下一些较为细节的工程问题：比如并行交易能否和非并行交易混合到一起执行？怎么保证资源字符串的全局唯一性？

答案也不复杂，前者可通过将非并行交易作为屏障（barrier）插入到交易DAG中——即我们认为，它即依赖于它的所有前序交易，同时又被它的所有后序交易依赖——来实现；后者可以通过在开发者指定的交易依赖项中，加入标识合约的特殊标志位解决。由于这些问题并不影响PTE的根本设计，本文暂不展开。

万事俱备，带着全新交易执行引擎PTE的FISCO BCOS已经呼之欲出。

搭载PTE的FISCO BCOS架构图：

整个架构的核心流程如下：

用户通过SDK等客户端将交易发送至节点，此处的交易既可以是可并行执行的交易，也可以是不能并行执行的交易。随后交易在节点间同步，同时拥有打包权的节点调用打包器（Sealer），从交易池（Tx Pool）中取出一定量交易并将其打包成一个区块。此后，区块被发送至共识单元（Consensus）准备进行节点间共识。

共识前需要执行区块中的交易，此处便是PTE施展威力之处。从架构图中可以看到，PTE首先按序读取区块中的交易，并输入到DAG构造器（DAG Constructor）中，DAG构造器会根据每笔交易的依赖项，构造出一个包含所有交易的交易DAG，PTE随后唤醒工作线程池，使用多个线程并行执行交易DAG。汇合器（Joiner）负责挂起主线程，直到工作线程池中所有线程将DAG执行完毕，此时Joiner负责根据各个交易对状态的修改记录计算state root及receipt root，并将执行结果返回至上层调用者。

在交易执行完成后，若各个节点状态一致，则达成共识，区块随即写入底层存储（Storage），被永久记录于区块链上。

交易DAG的数据结构如下图所示：

Vertex类为最基础里的类型，在交易DAG中，每一个Vertex实例都表征一笔交易。Vertex类包含：

• inDegree：表示该顶点的入度
• outEdges：用于存储该节点的出边信息，即所有出边所连顶点的ID列表

DAG类用于对DAG的顶点与边关系进行封装，并提供操作DAG的接口，其包含：

• vtxs：Vertex数组
• topLevel：包含所有入度为0的顶点的队列，由于在执行过程中topLevel会动态变化且会被多个线程访问，因此其需要一个能够支持线程安全访问的容器
• void init(int32_t size)接口：根据传入的size初始化一个包含相应数量顶点的DAG结构
• addEdge(ID from, ID to)接口：用于在顶点from和顶点to之间建立边关系，具体地说，将顶点to的ID加入顶点from的outEdges中
• void generate()接口：当所有的边关系录入完毕后，调用该方法以初始化topLevel成员
• ID waitPop()接口：从topLevel中获取一个入度为0的顶点ID

TxDAG类是DAG类更上一层的封装，是DAG与交易之间建立联系的桥梁，其包含：

• dag：持有的DAG类实例
• exeCnt：已执行过的交易总数
• totalTxs：交易总数
• txs：区块中的交易列表

从打包好的区块从取出区块中的所有交易； 将交易数量作为最大顶点数量初始化一个DAG实例； 按序读出所有交易，如果一笔交易是可并行交易，则解析其冲突域，并检查是否有之前的交易与该交易冲突，如果有，则在相应交易间构造依赖边； 若该交易不可并行，则认为其必须在前序的所有交易都执行完后才能执行，因此在该交易与其所有前序交易间建立一条依赖边。

DAG构造器在构造交易DAG时，会首先将totalTxs成员的值设置为区块中的交易总数，并依据交易总数对dag对象进行初始化，dag会在vtxs中为每笔交易生成一个位置关系一一对应的顶点实例。随后，初始化一个空的资源映射表criticalFields，并按序逐个扫描每笔交易。

对于某笔交易tx，DAG构造器会在其解析出该交易的所有依赖项，对于每个依赖项均会去criticalFields中查询，如果对于某个依赖项d，有前序交易也依赖于该依赖项，则在这两笔交易间建边，并更新criticalFields中d的映射项为tx的ID。

交易DAG构造流程的伪代码如下所示：

criticalFields ← map<string, ID>();
totalTxs ← txs.size();
dag.init(txs.size());
for id ← 0 to txs.size() by 1 do
  tx ← txs[id];
  dependencies ← 解析出tx的依赖项;
  for d in dependencies do
    if d in criticalFields then
        dag.addEdge(id, criticalFields[d]);
      end
    criticalFields[d] = id;
    end
  end
end
dag.generate();
Copy to clipboard

主线程会首先根据硬件核数初始化一个相应大小的线程组，若获取硬件核数失败，则不创建其他线程； 当DAG尚未执行完毕时，线程循环等待从DAG中pop出入度为0的交易。 若成功取出待执行的交易，则执行该交易，执行完后将后续的依赖任务的入度减1，若有交易入度被减至0，则将该交易加入topLevel中； 若失败，则表示DAG已经执行完毕，线程退出。

PTE在被创建时，会根据配置生成一个用于执行交易DAG的工作线程池，线程池的大小默认等于CPU的逻辑核心数，此线程池的生命周期与PTE的生命周期相同。工作线程会不断调用dag对象的waitPop方法以取出入度为0的就绪交易并执行，执行后该交易的所有后序依赖任务的入度减1，若有交易的入度被减至0，则将该交易加入到topLevel中。循环上述过程，直到交易DAG执行完毕。

交易DAG执行流程的伪代码如下所示：

while exeCnt < totalTxs do
  id ← dag.waitPop();
  tx ← txs[id];
  执行tx;
  exeCnt ← exeCnt + 1;
  for txID in dag.vtxs[id].outEdges do
    dag.vtxs[txID].inDegree ← dag.vtxs[txID].inDegree - 1;
    if dag.vtxs[txID].inDegree == 0 then
      dag.topLevel.push(txID)
    end
  end
end    
Copy to clipboard

我们选用了2个基准测试程序，用以测试PTE给FISCO BCOS的性能带来了怎样的变化，它们分别是基于预编译框架实现的转账合约和基于Solidity语言编写的转账合约，两份合约代码的路径分别为：

FISCO-BCOS/libprecompiled/extension/DagTransferPrecompiled.cpp

web3sdk/src/test/resources/contract/ParallelOk.sol

我们使用一条单节点链进行测试，因为我们主要关注PTE的交易处理性能，因此并不考虑网络、存储的延迟带来的影响。

测试环境的基本硬件信息如下表所示：

性能测试部分，我们主要测试PTE和串行交易执行方式（Serial）在各个测试程序下的交易处理能力。可以看到，相对于串行执行方式，PTE从左至右分别实现了2.91和2.69倍的加速比。无论是对于预编译合约还是Solidity合约，PTE均有着不俗的性能表现。

可扩展性测试部分，我们主要测试PTE在不同CPU核心数下的交易处理能力，使用的基准测试程序是基于预编译框架实现的转账合约。可以看到，随着核数增加，PTE的交易吞吐量呈近似线性递增。但是同时也能看到，随着核数在增加，性能增长的幅度在放缓，这是因为随着核数增加线程间调度及同步的开销也会增大。

对这个阶段性结果，我们并不满足，继续深