PlatON并行计算技术实现

来源:爱站网时间:2020-07-17编辑:网友分享
在PlatON之前的版本中,验证人不论是打包区块还是验证区块,区块中的交易均采用串行方式执行,并且在计算MPT树root(hash)时,从根节点依次往下采用递归方式算出树根,从算法层面分析也属于“串行”计算root。

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

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

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

交易并行

 

 

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

 

 

 

技术术语

顶点:图中的一个点
边:连接两个顶点的线段叫做边,edge
度数:由一个顶点出发,有几条边就称该顶点有几度,或者该顶点的度数是几,degree
路径:通过边来连接,按顺序的从一个顶点到另一个顶点中间经过的顶点集合
简单路径:没有重复顶点的路径
环:至少含有一条边,并且起点和终点都是同一个顶点的路径
出度:由一个顶点出发的边的总数
入度:指向一个顶点的边的总数  

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

并行计算root

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

假设插入以下数据:  

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

性能对比

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

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

上一篇:imToken转账成功却没到账是怎么回事?

下一篇:Truffle以太坊合约部署实战

您可能感兴趣的文章

相关阅读

查看更多 >