PlatON并行计算技术实现

在PlatON之前的版本中，验证人不论是打包区块还是验证区块，区块中的交易均采用串行方式执行，并且在计算MPT树root（hash）时，从根节点依次往下采用递归方式算出树根，从算法层面分析也属于“串行”计算root。

以上两种“串行计算”，无法充分利用硬件多核优势。其实在执行交易和计算root过程中，没有“依赖关系”的计算步骤完全可以并行执行，再将并行计算结果汇总成最终结果。

在PlatON0.13.0底层版本中，实现了通过有向无环图（DAG）技术完成交易并行和并行计算root。DAG图是数据结构中最为复杂的一种，由一组顶点和一组能够将两个顶点相连的边组成。 据测试，交易并行TPS优于交易串行版本，整体性能有30%左右的提升。

交易并行

区块中的交易是按顺序打包的，这就要求彼此有依赖关系的交易要保持和打包顺序相同的顺序，而对于彼此没有依赖的交易其实是可以并行执行的。可以借助有向无环图解析交易的依赖关系。

串行交易顺序与并行交易DAG

技术术语

顶点：图中的一个点

边：连接两个顶点的线段叫做边，edge

度数：由一个顶点出发，有几条边就称该顶点有几度，或者该顶点的度数是几，degree

路径：通过边来连接，按顺序的从一个顶点到另一个顶点中间经过的顶点集合

简单路径：没有重复顶点的路径

环：至少含有一条边，并且起点和终点都是同一个顶点的路径

出度：由一个顶点出发的边的总数

入度：指向一个顶点的边的总数

可以根据原始交易列表的执行顺序，通过交易的发起地址和接收地址，识别出交易之间的依赖关系，可以构造出一个交易的依赖DAG图，凡是入度为0（无被依赖的前序交易）的交易均可以并行执行。

并行计算root

通过深入了解 MPT 的数据结构，发现叶子节点是可以并行计算 hash 的, 且 MPT 正好与 DAG 类似, 可以把 MPT 转换为 DAG 做并行计算。

假设插入以下数据:

生成MPT树如下图，该MPT树可生成相应的DAG图，入度为0的节点可以并行计算hash。

性能对比

针对串行、并行版本，分别采用5000账户对25验证节点（机器配置为4核8G）进行转账压测，性能数据如下：

并行版本性能明显优于串行版本，PlatON也会在保证安全性与稳定性的同时不断完善性能指标，为用户提供更优质的服务。