并行的核心是以多路径执行的方式提高执行层执行效率，而为了实现多路径执行，链则需要进行一系列如冲突检测和回滚机制以确保它们在不影响最终状态一致性的情况下并行执行，并对数据库进行一定程度的改良。
撰文：Tia，Techub News
区块链因其去中心化的设计而牺牲了效率，因此提升执行速度一直是急需解决的问题之一。区块链的「执行层」是处理每一笔交易并将其加入链中的关键部分。为了加速处理能力，在执行层进行提升成为核心策略之一，而并行执行正是这一方面的重要突破。
传统的区块链通常采用串行方式逐笔处理交易，这使得交易速度受到很大限制，尤其在交易密集的网络中会引发拥堵。然而，通过并行执行，多个交易可以同时处理，从而大幅提高执行效率并减轻链上压力。
为了更好地了解什么是并行，我们将先从执行开始介绍，并以 Merge 后 PBS 模式下的以太坊为例，来解释一下什么是执行，同时展示执行在整个交易生命周期中所处的位置。
交易执行的具体环节
交易进入内存池并被筛选和排序：这是交易被提交后的预处理阶段，包含了 Mempool、Searcher 和 Builder 的交互，完成对交易的筛选和排序。
Builder 构建区块（但不执行）：Builder 将有利可图的交易排列成一个区块，以完成对交易的打包和排序。
Proposer 验证并提交区块：区块构建完成后，Builder 会将区块的提案发送给 Proposer。Proposer 对区块的结构和交易内容进行验证，然后正式将区块提交到网络上，以开始执行。
执行交易：区块提交后，节点逐笔执行区块内的交易。这是状态更新的关键阶段，每笔交易都会触发智能合约调用、账户余额变化或状态变更。
见证者见证：验证者对区块的执行结果和状态根进行见证，并将其作为最终确认。这确保了区块在执行层的真实性和有效性，并防止不一致性。
状态同步：每个节点会将区块的执行结果（如账户余额、合约状态更新等）同步到自己的本地状态，执行每笔交易后，节点计算并存储一个新的状态根，用以在下一个区块中作为初始状态。
当然，这只是以区块为单位的交易的状态同步，为了保持最新的链上状态，通常情况下，节点会逐个区块同步数据，并持续验证区块和状态。但如果要达到 POS 机制下的最终性，还需要聚合者将每个 Slot 中的见证者签名聚合成一个完整的签名，并将其传递到下一个 Slot 的提议者处，并且验证者需要在经过一个 Epoch 后，基于投票数量确认该 Epoch 内的所有区块的状态，形成临时的共识状态检查点。当连续两个 Epoch 获得大多数验证者的见证支持后，区块和交易才会达成最终性。
从交易的整个生命周期来看，执行发生在 Proposer 对 Builder 发送来的区块的结构和交易内容进行验证后。实际执行过程需要对交易逐笔处理，并对相应的账户或合约状态进行更新。所有交易执行完毕后，Proposer 会计算出一个新的状态根（默克尔根），这是对当前区块所有交易的执行结果和最终全局状态的总结。通俗来说，完整的区块执行过程包括把以太坊从前一个状态变成下一个状态的过程中需要完成的一系列计算，从每个交易的执行到默克尔根的计算。
顺序执行
与并行相对的是顺序执行，也就是目前区块链较为通用的执行方式。通常，交易会按照顺序逐步执行。当一笔交易完成执行后，以太坊会将账户状态及相关信息（例如余额、合约存储数据）更新至账户状态树中，新的账户状态哈希被生成。所有账户状态树完成更新后，就会形成被称为状态默克尔根的状态树的根节点哈希。在完成状态默克尔根、交易默克尔根和收据默克尔根后，区块头就会进行哈希计算，生成该区块的区块哈希。
而在这其中，交易的执行顺序至关重要。由于默克尔树是哈希值的二叉树，不同顺序下形成的默克尔根值会不同。
并行执行
在并行执行的环境下，节点会尝试对区块中的交易进行并行处理。并不是按照顺序一笔一笔地执行交易，而是将交易分配到不同的「执行路径」上，使它们能同时执行。通过并行执行，系统能够更高效地处理区块中的交易，提高吞吐量。
所有交易执行完成后，节点会将执行结果（即交易影响的状态更新）汇总，形成一个新的区块状态。这个状态会被添加到区块链上，代表链上最新的全局状态。
状态冲突
由于并行会在不同路径同时处理交易，因此并行的一大难点就是状态冲突。即可能存在多个交易在同一时间段内对区块链上的同一部分数据（状态）进行读取或写入操作的情况。这种情况如果处理不当，会导致执行结果不确定。因为状态的更新顺序不同，最终的计算结果也会不同。举个例子，
假设有两个交易，交易 A 和交易 B，它们都试图对同一个账户的余额进行更新操作：
交易 A：增加账户余额 10。
交易 B：增加账户余额 20。
账户初始余额为 100。
如果我们串行执行，执行顺序的结果是确定的：
1. 先执行交易 A，再执行交易 B：
账户余额先增加 10，变为 110。
再增加 20，最终变为 130。
2. 先执行交易 B，再执行交易 A：
账户余额先增加 20，变为 120。
再增加 10，最终变为 130。
在这两种顺序中，最终余额都是 130，因为系统确保了交易执行的顺序一致性。
但在并行执行环境下，交易 A 和交易 B 可能同时读取初始余额 100 并进行各自的运算：
交易 A 读取到余额为 100，计算后更新余额为 110。
交易 B 也读取到余额为 100，计算后更新余额为 120。
在这种情况下，由于交易同时执行，导致最终余额只更新为 120，而不是 130，因为交易 A 和交易 B 的操作「覆盖」了对方的结果，产生了状态冲突。
这类状态冲突问题通常被叫做「数据覆盖」，即当交易试图同时修改相同的数据时，可能会相互覆盖对方的计算结果，导致最终状态不正确。另外一种状态冲突可能会导致的问题是无法保证执行顺序。由于多个交易在不同的时间段完成操作，会造成不同的执行顺序。顺序不同，可能会导致不同的计算结果，从而使结果不确定。
为了避免这种不确定性，区块链并行执行系统通常会引入一些冲突检测和回滚机制，或提前对交易进行依赖性分析，确保它们在不影响最终状态一致性的情况下并行执行。
乐观并行与确定性并行
有两种方法方式来对待可能存在的状态冲突问题：确定性并行和乐观并行。这两种模式在效率和设计复杂性上各有权衡。
确定性并行需要提前声明状态访问，验证者或 sequencer 会在交易排序时检查声明的状态访问。如果有多个交易试图写入同一状态，会将这些交易标记为冲突，避免同时执行。不同的链具体实现提前声明状态访问的形式不同，但一般包括以下几种方式：
通过合约规范约束：开发者在智能合约中直接规定状态访问范围。例如，ERC-20 代币转账需要访问发送方和接收方的余额字段。
通过交易结构化数据声明：交易中添加专门字段来标注状态访问。
通过编译器分析：高级语言的编译器可以静态分析合约代码，自动生成状态访问集合。
通过框架强制声明：某些框架要求开发者在调用函数时显式指定需要访问的状态
乐观并行则会乐观地先处理交易，等到冲突发生时，再将受影响的交易按顺序重新执行。为了尽可能避免冲突情况的发生，乐观并行设计的核心是通过历史数据、静态分析等对状态进行快速预判和假设。即系统在不完全验证的情况下，假设某些操作或状态更新是有效的，尽量避免等待所有验证过程，以此提高性能和吞吐量。
虽然乐观并行能通过一些对状态的快速预判和假设来尽可能避免冲突发生，但还是会有一些无法避免的挑战，特别是涉及合约执行或跨链交易，如果冲突频繁发生，重新执行可能显著拖慢系统性能，并增加计算资源消耗。
确定性并行则通过在交易前进行状态依赖性检查以避免乐观并行可能出现的冲突情况，但由于需要在交易提交前准确声明状态依赖，这对开发者提出更高要求，从而增加了实现的复杂性。
EVM 并行困境
对待状态冲突不仅有确定性和乐观之分，在实现并行的具体过程中，还需要从链数据库架构的角度进行考虑。并行中的状态冲突问题在默克尔树架构下的 EVM 中就尤为困难。默克尔树是一个分层哈希结构，在每次交易对某个状态数据进行修改后，默克尔树的根哈希值也需要更新。这种更新过程是递归的，从叶子节点向上逐层计算直至根节点。由于哈希是不可逆的，即只有当下层的数据变更完成后才能计算上层，这种特性导致它很难并行更新。
如果两个交易并行执行并访问同一个状态（如账户余额），就会造成默克尔树节点的冲突。而解决这种冲突通常需要额外的事务管理机制，确保在多个分支中都能得到一致的根哈希值。这对 EVM 来说并不容易实现，因为它需要在并行化与状态一致性间做取舍。
非 EVM 并行解决方案
Solana
不同于以太坊的全局状态树，Solana 采用了账户模型。每个账户是独立的存储空间，存储在账本中，因此避免了路径冲突问题。
Solana 是确定性并行。在 Solana 中，每笔交易需要在提交时明确声明将访问的账户和所需的访问权限（只读或读写）。这种设计让区块链节点可以在交易执行之前，提前分析每笔交易需要访问的资源。因为交易在开始执行前已明确所有的账户依赖关系，节点可以判断哪些交易会访问相同的账户，哪些交易可以安全地并行执行，从而实现智能调度，避免冲突，从而实现并行调度的基础。
由于每笔交易在执行前就已声明了需要访问的账户和权限，Solana 可以检查交易之间是否存在账户依赖关系（Sealevel 模型）。交易之间如果没有共享的读写账户，系统就可以把它们分配到不同的处理器上并行执行。
Aptos
Aptos 的并行执行设计与以太坊有很大的不同，它在架构和机制上做出了一些关键创新，主要体现在账户模型和状态存储。
以太坊在执行交易时需要频繁更新全局状态树（MPT）。所有账户、合约的状态都存储在一个共享的状态树中，任何交易都需要访问和更新这棵状态树的一部分。而 Aptos 则通过将账户划分为独立的状态单元，每个对象是一个独立的键值对，对象之间可以独立存在，彼此互不影响，只有明确引用关系时才会关联。对象之间没有公共的树路径，不会出现锁竞争，可以完全并行。
Aptos 的底层数据结构为 Jellyfish Merkle Tree。每个对象的状态最终存储在 JMT 中，作为独立的键值对。不同于以太坊的 MPT，Jellyfish Merkle Tree 以一种完全二叉树结构的形式，这种形式使得节点的存储路径和查询路径被简化，大幅降低了验证时间。并且，每个账户在树中的位置是固定的，且树中的节点是独立存储的，允许多个账户的更新和查找并行进行。
Aptos 是乐观并行，它不需要预先提供声明的所有账户的依赖关系。为此，Aptos 使用 Block-STM，Block-STM 会利用预设的交易顺序来估计依赖性，从而减少中止次数。
并行 EVM
与非 EVM 并行相比，并行 EVM 在处理状态依赖性、冲突检测、Gas 管理和回滚机制等问题时，面临的技术难度较大。为了更好地理解这一点，我们可以参考一些并行 EVM 项目（如 Sui、Monad、Canto）如何解决这些问题。
Sui
Sui 和 Aptos 一样，也是使用对象模型来处理状态，采用每个对象（例如账户、智能合约状态）作为独立的资源，这些对象通过对象唯一标识符来区分。当交易涉及不同的对象时，这些交易可以并行处理，因为它们对不同的状态进行操作，不会产生直接的冲突。
虽然 Sui 使用对象模型来管理状态，然而，为了兼容 EVM，Sui 的架构通过额外的适配层或抽象机制，来桥接对象模型和 EVM 的账户模型。
在 Sui 中，事务的调度使用乐观并行策略，假设事务之间没有冲突。如果冲突发生，系统会使用回滚机制来恢复状态。
Sui 使用了对象模型和状态隔离技术，能有效避免状态依赖性问题。每个对象作为独立的资源，不同的交易可以并行执行，从而提高了吞吐量和效率。但这种方法的 trade-off 是对象模型的复杂性和回滚机制的开销。如果交易之间发生冲突，需要对部分状态进行回滚，这会增加系统的负担，并且可能影响并行处理的效率。相较于非 EVM 并行系统（如 Solana），Sui 需要更多的计算和存储资源来维持高效的并行性。
Monad
与 Sui 一样，Monad 采用的也是乐观并行。但 Monad 的乐观并行在具体交易执行前还是会对一些具有依赖关系的交易进行预测，预测主要通过 Monad 的静态代码分析器来完成。预测需要对状态进行访问，而以太坊数据库中存储状态的方式使得访问状态非常困难，为了使得并行在状态读取的过程更具效率，Monad 还重构了数据库。
Monad 状态树按分区进行划分，每个分区维护自己的状态子树。更新时只需修改相关分片，无需重建整个状态树。通过状态索引表快速定位分区中的状态，减少分区间的交互。
小结
并行的核心是以多路径执行的方式提高执行层执行效率，而为了实现多路径执行，链则需要进行一系列如冲突检测和回滚机制以确保它们在不影响最终状态一致性的情况下并行执行，并对数据库进行一定程度的改良。
当然，执行层效率的提高不局限于并行这一种方式，执行环节的优化还可以通过降低一笔交易对数据库需要的读写操作来完成。而整个链速度提升涉及的范围则更为广泛，还包括了共识层效率的提升。
每个技术背后都有属于其特定的限制条件。并行仅是提升效率的方式之一，最终决定是否使用该技术还需要考虑对于开发者是否友好，是否能够以不牺牲去中心化的方式完成等等。技术的堆叠并非越多越好，至少，对于以太坊而言，并行并没有那么那么具有吸引力，如果单从提升效率的角度出发，加入并行对于以太坊而言并非是最优解，无论是从简洁性考虑还是以以太坊目前 Rollup 为中心的路线图来考虑。