区块链全方位的并行处理
背 景
PTE（Parallel Transaction Executor，一种基于 DAG 模型的并行交易执行器）的引入，使 FISCO BCOS 具备了并行执行交易的能力，显著提升了节点交易处理的效率。
BCOS中交易并行
- 名词解释
1.1. DAG
一个无环的有向图称做有向无环图（Directed Acyclic Graph），简称DAG图。在一批交易中，可以通过一定方法识别出每笔交易需要占用的互斥资源，再根据交易在Block中的顺序及互斥资源的占用关系构造出一个交易依赖DAG图，如下图所示，凡是入度为0（无被依赖的前序任务）的交易均可以并行执行。如下图所示，基于左图的原始交易列表的顺序进行拓扑排序后，可以得到右图的交易DAG。
- 模块架构
1 2 3 4 5 6 7 8 | 其中主要流程包括： 用户直接或间接通过SDK发起交易。交易可以是能够并行执行的交易和不能并行执行的交易； 交易进入节点的交易池中，等待打包； 交易被Sealer打包为区块，经过共识后，发送至BlockVerifier进行验证； BlockVerifier根据区块中的交易列表生成交易DAG； BlockVerifier构造执行上下文，并行执行交易DAG； 区块验证通过后，区块上链。 |
|---|
- 重要流程
3.1. 交易DAG构建
3.1.1. DAG数据结构
方案中所用到的DAG数据结构如下：
其中：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | 顶点（Vertex） inDegree用于存储顶点当前的入度; outEdge用于保存该顶点的出边信息，具体为所有出边所连顶点的ID列表。 DAG： vtxs是用于存储DAG中所有节点的列表； topLevel是一个并发队列，用于存储当前入度为0的节点ID，执行时供多个线程并发访问； totalVtxs：顶点总数 totalConsume：已经执行过的顶点总数； void init(uint32_t _maxSize)：初始化一个最大顶点数为maxSize的DAG； void addEdge(ID from, ID to)：在顶点from和to之间建立一条有向边； void generate()：根据已有的边和顶点构造出一个DAG结构； ID waitPop(bool needWait)：等待从topLevel中取出一个入度为0的节点； void clear()：清除DAG中所有的节点与边信息。 TxDAG: dag：DAG实例 exeCnt：已经执行过的交易计数； totalParaTxs：并行交易总数； txs：并行交易列表 bool hasFinished()：若整个DAG已经执行完毕，返回true，否则返回false; void executeUnit()：取出一个没有上层依赖的交易并执行； |
|---|
3.1.2. 交易DAG构造流程
流程如下：
1 2 3 | 从打包好的区块从取出区块中的所有交易； 将交易数量作为最大顶点数量初始化一个DAG实例； 按序读出所有交易，如果一笔交易是可并行交易，则解析其冲突域，并检查是否有之前的交易与该交易冲突，如果有，则在相应交易间构造依赖边；若该交易不可并行，则认为其必须在前序的所有交易都执行完后才能执行，因此在该交易与其所有前序交易间建立一条依赖边。 |
|---|
3.2. DAG执行流程
流程如下：
1 2 | 主线程会首先根据硬件核数初始化一个相应大小的线程组，若获取硬件核数失败，则不创建其他线程； 当DAG尚未执行完毕时，线程循环等待从DAG中pop出入度为0的交易。若成功取出待执行的交易，则执行该交易，执行完后将后续的依赖任务的入度减1，若有交易入度被减至0，则将该交易加入topLevel中；若失败，则表示DAG已经执行完毕，线程退出。 |
|---|
瓶颈
对这个阶段性结果，我们并不满足，继续深入挖掘发现，FISCO BCOS 的整体 TPS 仍有较大提升空间。 用木桶打个比方：如果参与节点的交易处理所有模块构成木桶，交易执行只是组成整个木桶的一块木板，根据短板理论，一只木桶能盛多少水取决于桶壁上最矮的那块，同理，FISCO BCOS 的性能也由速度最慢的组件决定。
尽管 PTE 取得了理论上极高的性能容量，但是 FISCO BCOS 的整体性能仍然会被其他模块较慢的交易处理速度所掣肘。为了能够最大化利用计算资源以进一步提高交易处理能力，在 FISCO BCOS 中全面推进并行化改造势在必行。
数据分析
根据并行程序设计的『分析→分解→设计→验证』四步走原则，首先需定位出系统中仍存在的性能瓶颈的精确位置，才能更深入地对任务进行分解，并设计相应的并行化策略。使用自顶向下分析法，我们将交易处理流程分为四个模块进行性能分析，这四个模块分别是：
区块解码（decode）：
区块在节点间共识或同步时需要从一个节点发送至另一个节点，这个过程中，区块以 RLP 编码的形式在网络间传输。节点收到区块编码后，需要先进行解码，将区块还原为内存中的二进制对象，然后才能做进一步处理。
交易验签（verify）：
交易在发送之前由发送者进行签名，签名得到的数据可以分为 (v, r, s) 三部分，验签的主要工作便是在收到交易或交易执行前，从 (v, r, s) 数据中还原出交易发送者的公钥，以验证交易发送者的身份。
交易执行（execute）：
执行区块中的所有交易，更新区块链状态。
数据落盘（commit）：
区块执行完成后，需要将区块及相关数据写入磁盘中，进行持久化保存。
以包含 2500 笔预编译转账合约交易的区块为测试对象，在我们的测试环境中，各阶段的平均耗时分布如下图所示：
从图中可以看出，2500 笔交易的执行时间已经被缩短到了 50 毫秒以内，可以证明 PTE 对 FISCO BCOS 交易执行阶段的优化是行之有效的。但图中也暴露出了非常明显的问题：其他阶段的用时远远高于交易执行的用时，导致交易执行带来的性能优势被严重抵消，PTE 无法发挥出其应有的价值。
早在 1967 年，计算机体系结构领域的元老 Amdahl 提出的以他名字命名的定律，便已经向我们阐明了衡量处理器并行计算后效率提升能力的经验法则：
其中，SpeedUp 为加速比，Ws 是程序的串行分量，Wp 是程序中的并行分量，N 为 CPU 数量。可以看出，在工作总量恒定的情况下，可并行部分代码占比越多，系统的整体性能越高。我们需要把思维从线性模型中抽离出来，继续细分整个处理流程，找出执行时间最长的程序热点，对这些代码段进行并行化从而将所有瓶颈逐个击破，这才是使通过并行化获得最大性能提升的最好办法。
根因拆解
- 串行的区块解码 区块解码主要性能问题出在 RLP 编码方法本身。RLP 全称是递归的长度前缀编码，是一种用长度作为前缀标明编码对象中元素个数的编码方法。如下图所示，RLP 编码的开头即是此编码中的对象个数（Object num）。在个数后，是相应个数的对象（Object）。递归地，每个对象，也是 RLP 编码，其格式也与下图相同。
需要特别注意的是，在 RLP 编码中。每个 Object 的字节大小是不固定的，Object num 只表示 Object 的个数，不表示 Object 的字节长度。
RLP 通过一种长度前缀与递归结合的方式，理论上可编码任意个数的对象。下图是一个区块的 RLP 编码，在对区块进行编码时，先递归至最底层，对多个 sealer 进行编码，多个 sealer 被编码并加上长度前缀后，编码成为一串 RLP 编码（sealerList），此编码又作为一个对象，被编入上层的一串 RLP 编码（blockHeader）中。此后层层递归，最后编码成为区块的 RLP 编码。由于 RLP 编码是递归的，在编码前，无法获知编码后的长度。
解码时，由于 RLP 编码中每个对象的长度不确定，且 RLP 编码只记录了对象的个数，没记录对象的字节长度，若要获取其中的一个编码对象，必须递归解码其前序的所有对象，在解码前序的对象后，才能访问到需要访问的编码对象的字节位置。例如在上图中，若需要访问区块中的第 0 笔交易，即 tx0，必须先将 blockHeader 解码，而 blockHeader 的解码，需要再次递归，把 parentHash，stateRoot 直至 sealerList 都解码出来。
解码区块最重要的目的是解码出包含在区块中的交易，而交易的编码都是互相独立的，但在 RLP 特殊的编码方式下，解码一笔交易的必要条件是解码出上一笔交易，交易的解码任务之间环环相扣，形成了一种链式的依赖关系。需要指出的是，这种解码方式并不是 RLP 的缺陷，RLP 的设计目标之一本就是尽量减少空间占用，充分利用好每一个字节，虽然编解码变得低效了些，但编码的紧凑度却是有目共睹，因此这种编码方式本质上还是一种时间换空间的权衡结果。
由于历史原因，FISCO BCOS 中使用了 RLP 编码作为多处信息交换协议，贸然换用其他并行化友好的序列化方案可能会带来较大的开发负担。基于这一考虑，我们决定在原有的 RLP 编解码方案稍作修改，通过为每个被编码的元素添加额外的位置偏移信息，便可以做到并行解码 RLP 的同时不会改动大量原有代码。
- 交易验签 & 数据落盘开销大 通过对交易验签和数据落盘部分的代码进行拆解，我们发现两者的主要功能都集中在一个耗时巨大的 for 循环。交易验签负责按序取出交易，然后从交易的签名数据中取出 (v, r, s) 数据，并从中还原出交易发送者的公钥，其中，还原公钥这一步，由于涉及密码学算法，因此耗时不少；数据落盘负责从缓存中逐个取出交易相关数据，将其编码为 JSON 字符串后写入磁盘，由于 JSON 编码过程本身效率比较低，因此也是性能损失的重灾区。
两者代码分别如下所示：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | // 交易验签 for(int i = 0; i < transactions.size(); ++i) { tx = transactions[i]; v, r, s = tx.getSignature(); publicKey = recover(v, r, s); // 从 (v, r, s) 中复原出发送者公钥 ... } 复制代码 // 数据落盘 for(int i = 0; i < datas.size(); ++i) { data = datas[i]; jsonStr = jsonEncode(data); // 将数据编码为 JSON 字符串进行存储 db.commit(jsonStr); ... } |
|---|
两个过程共有的特点是，它们均是将同样的操作应用到数据结构中不同的部分，对于这种类型的问题，可以直接使用数据级并行进行改造。所谓数据级并行，即是将数据作为划分对象，通过将数据划分为大小近似相等的片段，通过在多个线程上对不同的数据片段上进行操作，达到并行处理数据集的目的。
数据级并行唯一的附加要求是任务之间彼此独立，毫无疑问，在 FISCO BCOS 的实现中，交易验签和数据落盘均满足这一要求。
优化实践
- 区块解码并行化 改造过程中，我们在系统中使用的普通 RLP 编码的基础上，加入了 offset 字段，用以索引每个 Object 的位置。如下图所示，改造后编码格式的开头，仍然是对象的个数（Object num），但是在个数字段后，是一个记录对象偏移量的数组（Offsets）。
数组中的每个元素有着固定的长度。因此要读取某个 Offset 的值，只需向访问数组一样，根据 Offset 的序号直接索引便可以进行随机访问。在 Offsets 后，是与 RLP 编码相同的对象列表。相应序号的 Offset，指向相应序号的对象的 RLP 编码字节位置。因此，任意解码一个对象，只需要根据对象的序号，找到其偏移量，再根据偏移量，就可定位到相应对象的 RLP 编码字节位置。
编码流程也进行了重新设计。流程本身仍然基于递归的思路，对于输入的对象数组，首先将对象数组的大小编码在输出编码的开头处，若数组大小超过 1，则按序逐个取出待编码对象并缓存其递归编码，并在 Offsets 数组中记录该对象的偏移位置，待数组遍历完后，将缓存的对象编码第一次性取出并附加至输出编码末尾；若数组大小为 1，则递归对其编码并写入输出编码的末尾，结束递归。
编码流程的伪代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | Rlps = RLP(); // Output，初始时为空 void encode(objs) //Input: objs = 待编码对象的数组 { offset = 0; codes = []; objNum = objs.size() Rlps.push(objNum) if objNum > 1 { for obj in objs { rlp = encode(obj); // 递归调用编码方法 Rlps.push(offset); offset += rlp.size(); codes.add(rlp); // 缓存递归编码的结果 } for x in codes { Rlps.push(x); } } else { rlp = encode(objs[0]); Rlps.push(rlp); } } |
|---|
偏移量的引入使解码模块能够对元素编码进行随机访问。Offsets 的数组范围可以在多个线程间均摊，从而每个线程可以并行访问对象数组的不同部分，分别进行解码。由于是只读访问，这种并行方式是线程安全的，仅需最后再对输出进行汇总即可。
解码流程的伪代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | Objs decode(RLP Rlps) { objNum = Rlps.objNum； // 获取对象个数 outputs = [] // 输出的对象数组 if objNum > 1 { parallel for i = 0 to objNum { offset = Rlps.offsets[i]; code = Rlps.objs[offset]; x = decode(code); outputs.add(x); // 有序插入 outputs } } else { outputs.add(decode(Rlps.objs[0])); } return outputs; } |
|---|
- 交易验签 & 数据落盘并行化 对于数据级并行，业内已有多种成熟的多线程编程模型。虽然 Pthread 这类显式的多线程编程模型能够提供对线程进行更精细的控制，但是需要我们对线程通信、同步拥有娴熟的驾驭技巧。实现的复杂度越高，犯错的几率越大，日后代码维护的难度也相应增加。我们的主要目标仅仅对密集型循环进行并行化，因此在满足需求的前提下，Keep It Simple & Stupid 才是我们的编码原则，因此我们使用隐式的编程模型来达成我们的目的。
经过再三权衡，我们在市面上众多隐式多线程编程模型中，选择了来自 Intel 的线程构建块（Thread Building Blocks，TBB）开源库。在数据级并行方面，TBB 算是老手，TBB 运行时系统不仅屏蔽了底层工作线程的实现细节，还能够根据任务量自动在处理器间平衡工作负载，从而充分利用底层 CPU 资源。
使用 TBB 后，交易验签和数据落盘的代码如下所示：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | // 并行交易验签 tbb::parallel_for(tbb::blocked_range<size_t>(0, transactions.size()), & { for(int i = _range.begin(); i != _range.end(); ++i) { tx = transactions[i]; v, r, s = tx.getSignature(); publicKey = recover(v, r, s); // 从 (v, r, s) 中复原出发送者公钥 ... } }); // 并行数据落盘 tbb::parallel_for(tbb::blocked_range<size_t>(0, transactions.size()), & { for(int i = _range.begin(); i != _range.end(); ++i) { data = datas[i]; jsonStr = jsonEncode(data); // 将数据编码为 JSON 字符串进行存储 db.commit(jsonStr); ... } }); |
|---|
可以看到，除了使用 TBB 提供的 tbb::parallel_for 进行并行循环和 tbb::blocked_range 引用数据分片外，循环体内的代码几乎没有任何变化，接近 C++ 原生语法正是 TBB 的特点。TBB 提供了抽象层级较高的并行接口，如 parallel_for、parallel_for_each 这类泛型并行算法，从而使得改造能够较为容易地进行。同时，TBB 不依赖任何语言或编译器，只要有能支持 ISO C++ 标准的编译器，便有 TBB 的用武之地。
当然，使用 TBB 并不是完全没有额外负担，比如线程间安全还是需要开发人员的仔细分析来保证，但 TBB 考虑周到，提供了一套方便的工具来辅助我们解决线程间互斥的问题，如原子变量、线程局部存储和并行容器等，这些并行工具同样被广泛地应用在 FISCO BCOS 中，为 FISCO BCOS 的稳定运行保驾护航。
压力测试的结果表明，FISCO BCOS 的交易处理能力，相较于并行化改造之前，成功提升了 1.74 倍，基本达到了这个环节的预期效果。
但是我们也深深明白，性能优化之路漫漫，木桶最短的一板总是交替出现，并行之道在于，通过反复的分析、拆解、量化和优化，使得各模块互相配合齐头并进，整个系统达到优雅的平衡，而最优解总是在“跳一跳”才能够得着的地方。