并行执行研究：你需要知道的一切

前言 本研究对比了类似以太坊的实现系统，分析了实现交易并行执行的困难和可能性。 值得注意的是，本次研究分析的链都是基于Account模型设计方案，不包括UTXO方案。 研究对象 FISCO-BCOS，支持区块内并行执行交易验证的联盟链之一。 Khipu公链，以太坊协议的scala实现。 Aptos公链，移动虚拟机。 并行执行的困难 我们来看看传统的事务执行流程。 执行模块从区块中取出每笔交易并依次执行。 在执行过程中会修改最新的世界状态，然后在一次交易完成后将状态累加，达到出块完成后的最新世界状态。 下一个块的执行严格依赖于当前/上一个块的世界状态，因此，这种顺序的、单线程的执行过程不太适合并行执行。 下面，是目前以太坊并行执行方式的主要冲突： 如果两个线程同时处理一个地址账户的余额或其他属性，我们如何保证它与顺序处理的结果一致，即世界状态是否是一个确定的有限状态机？ Account Conflict： ：两个合约都修改了同一全局变量的存储。 同一地址的存储冲突 如果先部署了合约A，则合约B需要等到合约A部署完成后才能调用合约A。但是当交易并行时，没有这样的顺序，从而导致冲突。 跨合约调用冲突： 并行执行方案 FISCO-BCOS 抽象的 FISCO-BCOS 2.0在交易处理中采用图结构。开发人员基于有向无环图模型（DAG）设计了一个并行事务执行器（PTE）。 PTE可以帮助您充分利用多核处理器的优势，使区块中的交易尽可能并行执行。 同时为用户提供简单友好的编程接口，使用户不必关心并行实现的繁琐细节。 基准测试程序的实验结果表明，与传统的串行事务执行方案相比，在理想条件下运行在4核处理器上的PTE可以实现约200%~300%的性能提升，且计算提升与数量成正比的核心。 内核越多，性能越好。 总体方案 无环有向图通常称为有向无环图 (DAG)。 在一批交易中，识别出每笔交易占用的互斥资源；然后根据区块中交易的先后顺序和互斥资源的占用关系构造一个交易依赖的DAG。 如下图所示，入站度为0的所有事务（没有依赖的前置任务）都可以并行执行。右边的交易DAG可以根据左边的原始交易列表的顺序进行拓扑排序得到。 模块化架构 用户通过SDK直接或间接发起交易。 然后在节点之间同步交易，具有相同打包权限的节点调用封口器（TxPool）从（txpool）中取出一定数量的交易打包成一个区块。之后，块被发送到共识单元，为节点间共识做准备。 交易验证在达成共识之前执行，这是 PTE 开始其工作流程的地方。从架构图中可以看出，PTE首先按顺序读取区块中的交易，并将其输入到DAG Constructor中，DAG Constructor根据每笔交易的依赖关系构造出一个包含所有交易的交易DAG。 PTE 然后唤醒工作池。使用多个线程并行执行事务 DAG。 Joiner 暂停主线程，直到 DAG 已被工作池中的所有线程执行。此时，Joiner根据每笔交易的状态修改记录，计算出状态根和回执根，并将结果返回给上层的调用者。 区块被验证后，区块被上传到链上。交易执行后，如果各节点状态一致，则达成共识，将区块写入底层存储，永久记录在区块链上。 交易DAG构建过程 从打包块中取出块中的所有交易。 以事务数作为最大顶点数初始化一个 DAG 实例。 按顺序阅读所有交易。如果事务是可合并的，解决它的冲突字段并检查是否有任何以前的事务与它冲突。如果是，则在相应的交易之间构造一条依赖边。如果事务不可合并，则认为它必须在所有先前事务都已执行后执行，因此在事务与其所有前任事务之间创建依赖边。 ：一旦创建了所有依赖边，它们就不能合并，只能顺序执行。 注意 DAG执行流程 主线程会先根据硬件核心数初始化一小组线程，如果硬件核心出现故障，则不会再创建其他线程。 当DAG未完成时，线程循环等待入度为0的就绪事务从DAG的waitPop方法中取出。如果成功取出要执行的交易，则执行该交易。如果失败，则 DAG 已完成执行，线程退出。 问题与解决方案 对于同一个区块，我们如何保证所有的节点都执行完毕，状态相同（三个根节点匹配）？ FISCO BCOS通过验证状态根、交易根、收据根三元组是否相等来判断状态是否一致。交易根是根据区块中的所有交易计算出的哈希值。 只要所有共识节点处理的是同一个区块数据，交易根一定是相同的，相对容易保证。关键是保证交易后生成的state和receipt root是一样的。 众所周知，在不同 CPU 内核上并行执行的指令之间的执行顺序是无法提前预测的，并行执行的事务也是如此。 在传统的交易执行方案中，每执行一次交易，状态根就会发生变化，并将变化后的状态根写入交易收据中。 所有交易执行完毕后，最终状态根代表区块链的当前状态。同时根据所有的交易收据计算一个收据根。 可以看出，在传统的实现中，状态根作为一个全局共享变量。 当交易并行且乱序执行时，传统的状态根计算不再适用，因为交易在不同的机器上以不同的顺序执行，最终的状态根无法保证一致，收据根也无法保证保持一致。 在FISCO BCOS中，首先并行执行交易，并记录每笔交易的状态变化历史。所有交易执行完毕后，根据历史计算出一个状态根。 同时，交易确认中的状态根成为所有交易执行完毕后的最终状态根，从而保证即使交易并行执行，共识节点仍能达成一致。 如何判断两个事务是否依赖？ 如果两个事务不依赖却被判断为依赖，会导致不必要的性能损失。反之，如果两笔交易都改写同一个账户的状态但并行执行，则账户的最终状态可能是不确定的。 因此，依赖关系的判定是影响性能甚至可以决定区块链能否正常工作的重要问题。 在一个简单的转账交易中，我们可以根据发送方和接收方的地址来判断两笔交易是否存在依赖关系。以下面三个转账交易为例，A→B、C→D、D→E。 很容易看出，D→E事务依赖于C→D事务的结果，而A→B事务与其他两个事务无关，因此可以并行执行。 这种分析在只支持简单转账的区块链中是正确的，但在运行智能合约的图灵完备区块链中可能就不那么准确了，因为我们不知道用户编写的转账合约到底发生了什么.这是可能发生的事情。 A→B的交易看似与C、D的账户状态无关，但在用户的底层实现中，A是一个特殊账户，必须从C的账户中扣除一定的手续费通过 A 的账户转账的每一笔钱。 在这个场景中，三个事务都是相关的，所以不能并行执行。如果按照之前的依赖分析方法来划分事务，势必会出错。 我们能否根据用户合约的内容，自动推断出交易中实际存在哪些依赖关系？答案是不。如前所述，静态分析很难分析契约依赖关系和执行过程。 在FISCO BCOS中，交易依赖的分配交给了更熟悉合约内容的开发者。具体来说，交易所依赖的互斥资源可以用一组字符串来表示。 FISCO BCOS将接口暴露给开发者，开发者以字符串的形式定义交易所依赖的资源，并告知链上的执行者。 执行者会根据开发者指定的交易依赖关系，自动将区块中的所有交易安排到交易DAG中。 例如，在一个简单的转账合约中，开发者简单地指定每笔转账交易的依赖为{发送方地址+接收方地址}。 更进一步，如果开发者在转账逻辑中引入了另一个第三方地址，则需要定义依赖为{发送方地址+接收方地址+第三方地址}。 这种做法直观、简单、通用，适用于所有智能合约，但也增加了开发者肩上的责任。 开发人员在指定事务依赖性时必须非常小心。如果依赖没有写对，后果不堪设想。 平行框架契约 为了方便开发者使用并行合约的框架，FISCO BCOS对合约编写做了一些规范。规格如下： 并行互斥 两个事务能否并行执行取决于两个事务是否互斥。互斥是指两个交易的存储变量集合的交集。 例如，在资产转移场景中，交易是用户之间的转移操作。 transfer(X, Y)表示用户X到用户Y的转账接口，互斥如下。 互斥参数：与合约接口中合约存储变量的“读/写”操作相关的参数。以传输接口transfer(X, Y)为例。 X 和 Y 是互斥参数。 互斥量：根据互斥量参数从一个事务中提取出的具体互斥量内容。以传输接口transfer(X, Y)为例。在使用该接口的A转账交易中，具体参数为transfer(A, B)，该操作的互斥量为[A, B]。对于另一个事务，调用transfer(A, C)，这个操作的mutex是[A, C]。 判断两个事务是否可以同时并行执行，就是判断两个事务的mutex是否相交。交集为空的事务可以并行执行。 FFISCO-BCOS提供了两种写并行合约的方式，预编译合约和solidity合约，这里只介绍后者。预编译合约也是如此。 Solidity 合约并行框架 要编写一个并行的 solidity 合约，最重要的是，只需将 ParallelContract.sol 作为您想要并行的合约的基类。调用 registerParallelFunction() 方法来注册可以并行化的接口。 并行合约代码如下： pragma solidity ^0.4.25; //Precompile the contract interface contract ParallelConfigPrecompiled { function registerParallelFunctionInternal(address, string, uint256) public returns (int); function unregisterParallelFunctionInternal(address, string) public returns (int); } //The parallel contract base class needs to be registered and the subcontract needs to be implement enable or disable interface contract ParallelContract { ParallelConfigPrecompiled precompiled = ParallelConfigPrecompiled(0x1006); function registerParallelFunction(string functionName, uint256 criticalSize) public { precompiled.registerParallelFunctionInternal(address(this), functionName, criticalSize); } function unregisterParallelFunction(string functionName) public { precompiled.unregisterParallelFunctionInternal(address(this), functionName); } function enableParallel() public; function disableParallel() public; } 以下示例是基于并行框架合约编写的转账合约： pragma solidity ^0.4.25; import "./ParallelContract.sol"; // Introduce ParallelContract.sol contract ParallelOk is ParallelContract // useParallelContract as a base class { // Contract implementation mapping (string => uint256) _balance; // Global mapping // The mutually exclusive variables from and to are the first two parameters at the beginning of transfer (). It can be seen that the contract requirements are still very strict, which will make users uncomfortable to write function transfer(string from, string to, uint256 num) public { _balance[from] -= num; // From is the key of the global mapping, and is a mutually exclusive parameter _balance[to] += num; //// To is the key of the global mapping, and is a mutually exclusive parameter } // The mutex variable name comes first as an argument to the beginning of set() function set(string name, uint256 num) public { _balance[name] = num; } function balanceOf(string name) public view returns (uint256) { return _balance[name]; } // Register contract interfaces that can be parallel function enableParallel() public { // The function definition string (note that there are no Spaces after ",") and the first few arguments are mutex arguments (mutex arguments must be first when designing a function) //The number 2 indicates that the first two are mutex parameters, and the system decodes the mutex according to the function signature and abi registerParallelFunction("transfer(string,string,uint256)", 2); // critical: string string // registerParallelFunction("set(string,uint256)", 1); // critical: string } // Deregister the parallel contract interface function disableParallel() public { unregisterParallelFunction("transfer(string,string,uint256)"); unregisterParallelFunction("set(string,uint256)"); } } 判断接口是否可以并行 并行合约接口必须满足： 没有调用外部合约。 没有调用其他函数接口。 确定互斥量参数 在对接口进行编程之前，确定接口的互斥参数。接口的互斥参数与全局变量互斥。确定互斥参数的规则如下： 如果通过接口访问全局映射，则映射的键为互斥参数。 如果接口访问的是全局数组，则数组下标为互斥参数。 如果接口访问的是简单类型的全局变量。一个简单类型的所有全局变量共享一个互斥量参数，并使用不同的变量名作为互斥量对象。 比如合约中有多个简单类型的全局变量，不同的接口访问不同的全局变量。 如果要并行不同的接口，需要在接口参数中定义一个互斥量参数，用修饰的全局变量来表示调用时使用哪个全局变量。 调用时，mutex参数主动传递修改后的全局变量“变量名”，标识本次交易的mutex。 如：如果 将 修饰为全局参数， 需要定义为 。调用时， 。使用变量名称 来指示此事务的互斥体是 。 setA(int x) globalA setA set(string aflag, int x) setA("globalA", 10) “globalA” globalA 确定参数类型和顺序 确定互斥参数后，根据规则确定参数类型和顺序。规则如下： 接口参数仅限于string、address、uint256、int256（后续会支持更多类型）。 互斥参数必须全部出现在接口参数中。 所有互斥参数都排在接口参数的首位。 可见，FISCO-BCOS的并行交易在很大程度上取决于用户编写的合约规范。 如果用户编写的合约规范不规范，系统就贸然进行并行执行，可能会造成账本的根本不一致。 奇普 抽象的 Khipu 认为，让用户在编写合约时无误地识别和标记会产生静态冲突的地址范围是不现实的。这与 FISCO-BCOS 的观点相反。 只有当确定性获取涉及到当前状态时，才能判断竞争条件是否会出现、出现在哪里以及在什么条件下出现。 这种判断，以目前的合约编程语言，使得对代码的静态分析几乎不可能得到完全正确无误的结果。 Khipu 已经为解决这个问题做出了更全面的尝试，并完成了一个实施过程。 总体方案 在 Khipu 中，同一个区块中的每笔交易都从前一个区块的世界状态开始，然后并行执行，记录了执行过程中沿着所有理想的经验路径遇到的上述三种竞争条件。 并行执行阶段之后是合并阶段，并行世界状态被一个接一个地合并。合并事务时，先从记录的静态条件判断自己是否与之前合并的竞争条件有冲突。 如果没有，直接合并。如果是这样，则从已合并的世界的先前状态开始再次执行交易。 最后合并的世界状态根据块的哈希值进行检查。这是最后一道防线。如果检查不正确，则放弃之前的合并并再次执行该块。 平行指数 在这里，Khipu 引入了一个并行度指标，即一个区块中可以直接合并结果而无需再次执行的交易比例。 Khipu 对以太坊从创建区块到最新区块的几天回放的观察表明，这个比例（并行度）平均可以达到 80%。 一般来说，如果计算任务可以完全并行化，那么单链的扩展性是无限的。因为你总是可以向一个节点添加更多的 CPU 内核。如果不是这种情况，则最大理论速率受安达尔定理限制： 系统加速的极限取决于不能并行化的部分的倒数。所以，如果你能并行化 99%，你就能加速 100 倍。但如果你只能实现 95% 的并行化，那么你最多只能快 20 倍。 在以太坊上的所有交易中，大约 80% 可以并行化，20% 不能并行化，因此 Khipu 的速度限制在 5 倍左右。 冲突标记 通过了解evm代码中的指令，发现有限数量的指令对storage创建了读写过程，所以可以将这些读写过程记录下来，形成一个读写集合，但是静态代码分析无法确保记录这些过程。 因此，在处理每个区块时，需要对每笔交易预执行一次。预执行过程告诉我们事务是对同一个账户还是存储进行读写，并为每个事务创建一个readSet和一个writeSet。 如果区块链中有100笔交易，那么这100笔交易可以通过线程池并行执行。每个合约都有相同的初始世界状态，在执行过程中会创建 100 个 readSets 和 writeSets，每个都有 100 个新状态。 当预执行结束后，开始下一阶段的处理。理想情况下，如果 100 个 readSet 和 writeSet 条目不冲突，那么它们可以直接合并，产生区块中所有交易的最终世界状态。然而，交易往往不是那么理想。 正确的处理方式是将第一个交易执行后的readSet和writeSet与第二个合约执行后的readSet和writeSet进行比较，看是否读写了同一个账户或存储。 如果是这样，则意味着这两项交易存在冲突。然后第二个事务将在第一个事务完成后开始并再次执行。 同样，随着合并状态机的继续，冲突集会不断累积，只要后续事务与前面的事务发生冲突，就会依次执行，直到所有事务执行完毕。 通过回放以太坊主网上的交易，发现在冲突比较多的地方，大部分都是同一个区块内的交易所，交易相互关联，这也符合这个流程。 一般流程 具体并行过程 阿普托斯 抽象的 Aptos 基于 Diem 的 Move 语言和 MoveVM 构建，以创建支持并行执行的高吞吐量链。 Aptos 的方法是检测关联，同时对用户/开发人员透明。 也就是说，交易不需要明确说明它们使用状态的哪一部分（内存位置）。 总体方案 Aptos 使用了一种名为 Block-STM 的软件事务内存的修改版本，并基于 STM 实现了其并行执行引擎。 Block- Block-STM使用MVCC（Multi-version Concurrency Control）来避免写-写冲突。所有对同一位置的写入都与它们的版本一起存储，其中包含它们的 TX-ID 和写入 tx 被重新执行的次数。 当事务 (tx) 读取内存位置的值时，它会获取在 tx 之前从 MVCC 写入该位置的值以及关联的版本，以确定是否存在读/写冲突。 在 Block-STM 中，事务在块内预先排序，并在执行期间在处理器线程之间划分以并行执行。在并行执行中，假设没有依赖关系来执行事务。 记录事务修改的内存位置。执行后，验证所有交易结果。在验证过程中，如果发现一个事务访问了被前一个事务修改过的内存位置，则该事务无效。 刷新交易结果，然后重新执行交易。重复此过程，直到块中的所有交易都已执行。当使用多个处理器内核时，Block-STM 可加快执行速度。加速取决于事务的相互依赖程度。 可以看出Aptos使用的方案和上面提到的Khipu大致相似，但是在实现上有一些区别，具体如下： Khipu 对区块内交易使用并行执行和顺序验证。但是，Aptos 对区块内的交易实现了并行执行和验证。这两种方案各有利弊。 Khipu实现简单，效率略低。 Aptos通过Block-STM在多线程中使用同步和信号操作，效率高但代码实现难度大。 由于 Move 原生支持全局资源寻址，Aptos 会在有利于并行执行的情况下对交易进行重新排序，甚至跨区块。 Aptos声称该方案不仅可以提高并行效率，还可以解决MEV问题。不过，这是否会影响用户体验还有待考量。 Aptos 在执行过程中将生成的写集存储在内存中以实现最大执行速度，然后将其用作下一个要执行的块的缓存。任何重复的写入只需要写入一次稳定内存。 基准测试 Aptos在block-STM集成后做了相应的benchmark，比较了一个Block of 10k transactions的顺序执行和并行执行。对比结果如下： 从上图可以看出，Block STM在32个线程并行的情况下实现了比顺序执行快16倍，在高争用情况下快了8倍以上。 结论 通过以上对比分析可以得出结论，部分方案需要用户在编写合约时按照既定规则写入存储，以便通过静态和动态分析找到依赖关系。 Solana 和 Sui 使用类似的方案，但用户感知不同。该方案本质上是一种存储模型的改变，以获得更好的分析结果。 Khipu 和 Aptos 是用户不可知的方案。并行执行的开销不在开发人员身上，他们在编写合约时不需要考虑这一点。 虚拟机在执行前动态分析依赖关系，实现无依赖关系的并行执行。 这很难实现，并行度在一定程度上取决于交易的账户划分。当存在大量事务冲突时，通过不断地重新执行，性能会显着下降。 Aptos 提到他们将在未来对用户编写的合约进行优化，以更好地分析依赖关系，从而实现更快的执行。 简单地将基于串行的方案修改为并行方案，可以在公链环境下带来3~16倍的交易吞吐量提升，如果能结合大区块和大gas limit，L2吞吐量将得到进一步优化，潜力约为100 次。 从工程角度来看，从实现和效率上看，OlaVM很可能会采用Khipu方案加定制存储模型的方案，在提升性能的同时避免引入Block-STM带来的复杂性，有利于更好的工程优化。 参考 FISCO-BCOS Github, FISCO-BCOS Khipu GitHub, GitHub - khipu-io/khipu: 一个基于以太坊的企业区块链平台 Aptos GitHub, GitHub - aptos-labs/aptos-core：Aptos 是第 1 层区块链，旨在通过更好的技术和用户体验支持区块链的广泛使用。 关于我们 Sin7y 成立于 2021 年，由一流的区块链开发者提供支持，是一个项目孵化器和区块链技术研究团队，探索最重要和最前沿的技术，包括 EVM、Layer2、跨链、隐私计算、自主支付解决方案等. 我们目前正在开发一种与 EVM 兼容、快速且可扩展的 ZKVM，称为 OlaVM。如果您有兴趣与我们交谈，请随时加入我们的 或发送电子邮件至 联系我们。 TG 群组 contact@sin7y.com