交易并行

1 名词解释

1.1 DAG

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

2 模块架构

其中主要流程包括：

3 重要流程

3.1 交易DAG构建

3.1.1 DAG数据结构

方案中所用到的DAG数据结构如下： 其中： - 顶点（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. 将交易数量作为最大顶点数量初始化一个DAG实例；
  3. 按序读出所有交易，如果一笔交易是可并行交易，则解析其冲突域，并检查是否有之前的交易与该交易冲突，如果有，则在相应交易间构造依赖边；若该交易不可并行，则认为其必须在前序的所有交易都执行完后才能执行，因此在该交易与其所有前序交易间建立一条依赖边。

3.2 DAG执行流程

流程如下：

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