长安链并行调度机制（2）：DAG构建和从节点执行流程

长安链采用高效的并行调度方式执行交易，了解长安链交易调度、冲突检测和DAG构建流程有助于开发者更好地理解长安链并行调度的运行机制，帮助开发者编写高质量、低冲突的智能合约，更好地构建区块链应用。

上一篇内容我们说明了长安链交易调度、冲突检测流程，本篇内容我们将进一步介绍长安链中DAG构建和从节点执行流程。

一、  概述

前一篇文章介绍了长安链中交易调度和交易冲突检测的流程及机制，确保主节点对所有交易的执行结果都是“正确的”。但是，在交易调度执行过程中，有一些交易是有前后依赖关系的，主节点需要告诉从节点，哪些交易需要按照主节点的执行顺序，等前置交易执行完后才能执行，哪些交易可以并行执行的，这些内容将在本文进行介绍，确保从节点按照主节点的执行顺序对交易进行执行，进而得到一致的世界状态。

二、  DAG构造流程

前一篇文章已经介绍了在交易并行调度和执行过程中，如何保障单笔交易能够正确执行。但是，通过主节点交易冲突检测后，交易的执行顺序将会形成依赖，如前一篇文章中例子所示，tx1经过调度后需要在tx0后面执行。

因此，为了保证其他从节点也能按照同样的顺序对区块中的交易进行执行，最终各个节点形成一致的世界状态，就需要主节点根据交易的读写集为区块中的交易构建DAG（有向无环图），并将DAG放入区块中，等其他从节点收到区块后，直接按照区块中的DAG对交易进行执行，从而保障各个节点对交易执行的有序性。

图2.1 调度后的交易顺序

我们假设主节点调度执行完后，Snapshot的ExecutedTxs中交易的顺序按照上图所示，依次为tx0，tx1，tx2和tx3，下面我们将基于上面这个例子介绍构建DAG的具体流程。

1. 构建读集写集字典、读集写集位置索引

图2.2 按照上述四笔交易构建的读写集字典和读写集位置索引

先介绍这四个结构的含义：

读集字段和写集字典：数据结构是个字典，即map。

● 字典中的键是交易读集或写集中的key；

● 字典中的值是交易编号，这个编号指的是在ExecutedTxs中的索引，从0开始，即0表示tx0，1表示tx1，2表示tx2，3表示tx3；

● 整个字典的含义是这个key被那些交易读或者写了；

读集位置索引和写集位置索引：数据结构是个二维数组。

● 二维数组中行头表示的是交易索引，列头表示的是整个区块中的交易读写或者写集的key；

● 二位数组中的值是在这笔交易之前，读集字典或者写集字典中有前几笔交易引用了该key；

● 二维数组的含义表示的是某笔交易中的key，被读集字典或者写集字典中前几笔交易读过或者写过；

具体构造流程：

按照ExecutedTxs中tx0，tx1，tx2和tx3中的交易顺序，分别根据每笔交易的读写集信息计算上述四个结构中的值。

对读集的处理方式：

1.  先填写readPos，根据readDict判断是否之前有交易的读集引用过该key，如果有则将readDict此key对应的元素个数len写入readPos对应的位置；

2.  再填写writePos，根据writeDict判断是否之前有交易的写集引用过该key，如果有则将writeDict此key对应的元素个数len写入writePos对应的位置；

3.  将此交易索引写入readDict中对应的key处；

对写集的处理方式：

1.  先填写writePos，根据writeDict判断是否之前有交易的写集引用过该key，如果有则将writeDict此key对应的元素个数len写入writePos对应的位置；

2.  再填写readPos，根据readDict判断是否之前有交易的读集引用过该key，如果有则将readDict此key对应的元素个数len写入readPos对应的位置；

3.  将此交易索引写入writeDict中对应的key处；

以其中的tx0和tx1为例，将相关信息填入上述四个结构中的图例如下所示，先填写tx0的信息，再继续填写tx1的信息。

图2.3 tx0的读写集填入上述四个结构流程图

图2.4 tx1的读写集填入上述四个结构流程图

大家感兴趣的话，可以在图2.4基础上继续将tx2和tx3的读写集信息填入上述四个结构，最终将会得到图2.2。填写好构建DAG的物料图后，我们将开始实际构建DAG。

2、  构建DAG

图 2.5 DAG构建流程图

同理，先介绍三个结构的含义：

DAG：数据结构是个字典，即map。

● 字典中的键表示的是交易编号，代表的是交易，这个编号同样指的是在ExecutedTxs中的索引，从0开始，即0表示tx0，1表示tx1，2表示tx2，3表示tx3；

● 字典中的值是交易编号；

● 整个字典的含义是这个这笔交易与哪些交易冲突，只有那些冲突交易都执行完了，这笔交易才能够执行；

累计冲突位图和直接冲突位图：数据结构是个位图，每一个交易都会构建一个累积冲突位图和直接冲突位图

● 累计冲突位图表示的是与本交易累计冲突的交易，累计冲突位图的作用是如果某笔交易B与交易A存在读写和写写冲突，那么交易B将与所有索引在交易A之前且和交易A存在写写冲突的交易都存在冲突，那这样只需要标识出交易B与交易A存在读写冲突即可，注意此处主要利用了写写交易之间本身存在冲突的特性，对于写读冲突则需要全量检测，因为读读交易不存在冲突，但是这些读交易与此笔写交易都存在冲突；

● 直接冲突位图表示的是与本交易直接冲突的交易，用于计算DAG中的字典值；

具体构造流程：

按照ExecutedTxs中tx0，tx1，tx2和tx3中的交易顺序，根据上一步骤构建的图3.2中读集字典、写集字典、读集位置索引和写集位置索引四个结构，通过位图高效地检索出来哪些交易是与该交易是冲突的。

对读集的处理方式：

只需要判断读写冲突，因为读读不存在冲突。

1.  先看读集的key在writeDict中是否被其他交易进行了写操作，如果有的话，则通过writePos明确出来有哪些交易(假设是txn-1, txn, txn+1)在这笔交易之前写过这个key，那些交易都与此交易存在读写冲突；

2.  因为与本交易存在读写冲突的txn-1, txn, txn+1这几笔交易本身存在写写冲突，所以只需要将对应的最后一笔 txn+1的累计冲突位图加入本交易的累计冲突位图，将txn+1这笔交易加入本交易的直接冲突位图即可。因为标识出本交易与txn+1冲突后，本质上也标识出了与txn-1, txn同样存在冲突；

对写集的处理方式：

需要判断写写冲突和写读冲突。

1.  先判断写写冲突，看写集中的key在writeDict中是否被其他交易进行了写操作，如果有的话，则通过writePos明确出来有哪些交易(假设是txn-1, txn, txn+1)在这笔交易之前写过这个key；

2.  同上述读写冲突检测方式一样，因为txn-1, txn, txn+1之间本身存在写写冲突，只需要将对应的最后一笔 txn+1的累计冲突位图加入本交易的累计冲突位图，将txn+1这笔交易加入本交易的直接冲突位图即可；

3.  再判断写读冲突，看写集中的key在readDict中是否被其他交易进行了读操作，如果有的话，则通过readPos明确出来有哪些交易(假设是txn-1, txn, txn+1)在这笔交易之前读过这个key；

4.  这里因为readPos中反应出来的是在这笔交易之前，对此key进行过读的交易，而这些读的交易之间不存在冲突，所以需要将txn-1, txn, txn+1三个交易各自的累计冲突位图加入到本交易的累计冲突位图，将txn-1, txn, txn+1三笔交易加入本交易的直接冲突位图；

最后，对这笔交易的读集和写集都进行处理后，根据直接冲突位图，计算出这笔交易在DAG中对应的冲突交易即可。

下面，以其中的tx0和tx1为例，将相关信息填入上述三个结构中的图例如下所示，先填写tx0的信息，再继续填写tx1的信息。

图 2.6 tx0的DAG计算流程图

图 2.7 tx1的DAG计算流程图

其他另外两笔交易可以按照上述逻辑自行计算其DAG的值，最终将会得到图2.5中的结果。

三、  DAG顺序执行流程

从节点收到区块后，直接按照区块中DAG描述的顺序，对交易执行即可，其执行结果和主节点的执行结果一定是一致的。

具体执行流程是：

● 并行执行不依赖其他交易的交易；

● 其他交易pop掉已经被执行的交易，如交易不再依赖其他交易即可执行；

● 直到所有交易均执行完即可；

图 3.1 从节点交易执行流程

上述例子中，初始tx0不依赖其他交易，可以直接执行；

随后，tx1和tx3 pop掉对tx0的依赖后，tx1可以继续执行；

最后，tx2和tx3 pop掉对tx1的依赖后，tx2和tx3可以并行执行。

四、  延伸思考

我们知道主节点在执行交易时，是调度+执行(先不算DAG构建时间，并且假设n笔交易并行执行是串行执行时间的1/n)，从节点只需要按照DAG中的顺序对交易执行即可。那什么情况下从节点单独执行的时间会比主节点调度+执行的时间还长？

答案：写写冲突场景下，主节点并行执行，从节点串行执行。