广州 seo的网站合肥电子网站建设

当前位置： 首页 > news >正文

广州 seo的网站,合肥电子网站建设,茶叶网站建设模板,wordpress加黑字体长安链采用高效的并行调度方式执行交易#xff0c;了解长安链交易调度、冲突检测和DAG构建流程有助于开发者更好地理解长安链并行调度的运行机制#xff0c;帮助开发者编写高质量、低冲突的智能合约#xff0c;更好地构建区块链应用。 上一篇内容我们说明了长安链交易调度、…长安链采用高效的并行调度方式执行交易了解长安链交易调度、冲突检测和DAG构建流程有助于开发者更好地理解长安链并行调度的运行机制帮助开发者编写高质量、低冲突的智能合约更好地构建区块链应用。 上一篇内容我们说明了长安链交易调度、冲突检测流程本篇内容我们将进一步介绍长安链中DAG构建和从节点执行流程。 一、  概述 前一篇文章介绍了长安链中交易调度和交易冲突检测的流程及机制确保主节点对所有交易的执行结果都是“正确的”。但是在交易调度执行过程中有一些交易是有前后依赖关系的主节点需要告诉从节点哪些交易需要按照主节点的执行顺序等前置交易执行完后才能执行哪些交易可以并行执行的这些内容将在本文进行介绍确保从节点按照主节点的执行顺序对交易进行执行进而得到一致的世界状态。 二、  DAG构造流程 前一篇文章已经介绍了在交易并行调度和执行过程中如何保障单笔交易能够正确执行。但是通过主节点交易冲突检测后交易的执行顺序将会形成依赖如前一篇文章中例子所示tx1经过调度后需要在tx0后面执行。 因此为了保证其他从节点也能按照同样的顺序对区块中的交易进行执行最终各个节点形成一致的世界状态就需要主节点根据交易的读写集为区块中的交易构建DAG有向无环图并将DAG放入区块中等其他从节点收到区块后直接按照区块中的DAG对交易进行执行从而保障各个节点对交易执行的有序性。 图2.1 调度后的交易顺序 我们假设主节点调度执行完后Snapshot的ExecutedTxs中交易的顺序按照上图所示依次为tx0tx1tx2和tx3下面我们将基于上面这个例子介绍构建DAG的具体流程。

1. 构建读集写集字典、读集写集位置索引 图2.2 按照上述四笔交易构建的读写集字典和读写集位置索引 先介绍这四个结构的含义 读集字段和写集字典数据结构是个字典即map。 ● 字典中的键是交易读集或写集中的key ● 字典中的值是交易编号这个编号指的是在ExecutedTxs中的索引从0开始即0表示tx01表示tx12表示tx23表示tx3 ● 整个字典的含义是这个key被那些交易读或者写了 读集位置索引和写集位置索引数据结构是个二维数组。 ● 二维数组中行头表示的是交易索引列头表示的是整个区块中的交易读写或者写集的key ● 二位数组中的值是在这笔交易之前读集字典或者写集字典中有前几笔交易引用了该key ● 二维数组的含义表示的是某笔交易中的key被读集字典或者写集字典中前几笔交易读过或者写过 具体构造流程 按照ExecutedTxs中tx0tx1tx2和tx3中的交易顺序分别根据每笔交易的读写集信息计算上述四个结构中的值。 对读集的处理方式
2.  先填写readPos根据readDict判断是否之前有交易的读集引用过该key如果有则将readDict此key对应的元素个数len写入readPos对应的位置
3.  再填写writePos根据writeDict判断是否之前有交易的写集引用过该key如果有则将writeDict此key对应的元素个数len写入writePos对应的位置
4.  将此交易索引写入readDict中对应的key处 对写集的处理方式
5.  先填写writePos根据writeDict判断是否之前有交易的写集引用过该key如果有则将writeDict此key对应的元素个数len写入writePos对应的位置
6.  再填写readPos根据readDict判断是否之前有交易的读集引用过该key如果有则将readDict此key对应的元素个数len写入readPos对应的位置
7.  将此交易索引写入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表示tx01表示tx12表示tx23表示tx3 ● 字典中的值是交易编号 ● 整个字典的含义是这个这笔交易与哪些交易冲突只有那些冲突交易都执行完了这笔交易才能够执行 累计冲突位图和直接冲突位图数据结构是个位图每一个交易都会构建一个累积冲突位图和直接冲突位图 ● 累计冲突位图表示的是与本交易累计冲突的交易累计冲突位图的作用是如果某笔交易B与交易A存在读写和写写冲突那么交易B将与所有索引在交易A之前且和交易A存在写写冲突的交易都存在冲突那这样只需要标识出交易B与交易A存在读写冲突即可注意此处主要利用了写写交易之间本身存在冲突的特性对于写读冲突则需要全量检测因为读读交易不存在冲突但是这些读交易与此笔写交易都存在冲突 ● 直接冲突位图表示的是与本交易直接冲突的交易用于计算DAG中的字典值 具体构造流程 按照ExecutedTxs中tx0tx1tx2和tx3中的交易顺序根据上一步骤构建的图3.2中读集字典、写集字典、读集位置索引和写集位置索引四个结构通过位图高效地检索出来哪些交易是与该交易是冲突的。 对读集的处理方式 只需要判断读写冲突因为读读不存在冲突。
8.  先看读集的key在writeDict中是否被其他交易进行了写操作如果有的话则通过writePos明确出来有哪些交易(假设是txn-1, txn, txn1)在这笔交易之前写过这个key那些交易都与此交易存在读写冲突
9.  因为与本交易存在读写冲突的txn-1, txn, txn1这几笔交易本身存在写写冲突所以只需要将对应的最后一笔 txn1的累计冲突位图加入本交易的累计冲突位图将txn1这笔交易加入本交易的直接冲突位图即可。因为标识出本交易与txn1冲突后本质上也标识出了与txn-1, txn同样存在冲突 对写集的处理方式 需要判断写写冲突和写读冲突。
10.  先判断写写冲突看写集中的key在writeDict中是否被其他交易进行了写操作如果有的话则通过writePos明确出来有哪些交易(假设是txn-1, txn, txn1)在这笔交易之前写过这个key
11.  同上述读写冲突检测方式一样因为txn-1, txn, txn1之间本身存在写写冲突只需要将对应的最后一笔 txn1的累计冲突位图加入本交易的累计冲突位图将txn1这笔交易加入本交易的直接冲突位图即可
12.  再判断写读冲突看写集中的key在readDict中是否被其他交易进行了读操作如果有的话则通过readPos明确出来有哪些交易(假设是txn-1, txn, txn1)在这笔交易之前读过这个key
13.  这里因为readPos中反应出来的是在这笔交易之前对此key进行过读的交易而这些读的交易之间不存在冲突所以需要将txn-1, txn, txn1三个交易各自的累计冲突位图加入到本交易的累计冲突位图将txn-1, txn, txn1三笔交易加入本交易的直接冲突位图 最后对这笔交易的读集和写集都进行处理后根据直接冲突位图计算出这笔交易在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中的顺序对交易执行即可。那什么情况下从节点单独执行的时间会比主节点调度执行的时间还长 答案写写冲突场景下主节点并行执行从节点串行执行。