Block-STM：我们如何在Aptos区块链上每秒执行超过16万笔交易

Block-STM： 我们如何在 Aptos 区块链上每秒执行超过 16 万笔交易

Aptos 将世界一流的工程技术与尖端研究相结合。有关更多详细信息，请参阅 Block-STM 论文 和 Aptos 代码库。

作者： Alexander Spiegelman 和 Rati Gelashvili

要点：我们设计并实现了一个高效的、多线程的、内存中的并行执行引擎，通过利用预设的交易顺序并将软件事务内存技术与一种新颖的协作调度相结合，该引擎每秒可以执行超过 16 万笔非平凡的 Move 交易。

挑战

智能合约执行是区块链吞吐量的一个主要瓶颈。在提议区块并就其顺序达成一致后，验证者必须执行已排序区块中的交易。至关重要的是，验证者必须得出相同的最终状态，该状态必须对应于交易的某种顺序执行。由于缺乏基础解决方案，当前的区块链要么顺序执行，要么需要令人尴尬的并行工作负载（即没有内部冲突）以提高性能。顺序执行的可伸缩性不好，并且假设所有交易都是可交换的在考虑范围广泛的智能合约时是不现实的。事实上，由于潜在的性能攻击，访问流行的合约（例如，由于拍卖和套利等经济机会），区块链中的交易可能存在大量的访问冲突。

目标

设计一种并行执行引擎，在给定工作负载中的实际访问冲突的情况下，提取尽可能大的固有加速。为了获得最佳的编程和用户体验，该算法对用户应该是透明的。一些区块链并行执行引擎采取的另一种方法是强制用户预先声明依赖关系，这严重限制了交易可以执行的操作，并且可能需要拆分或重试交易。相反，为了避免产生此类成本和编程麻烦，我们的并行执行引擎的系统设计目标是在内部管理所有冲突并自动适应工作负载。

STM 方法

软件事务内存 (STM) 库开创的一种学术方法是对内存访问进行检测和管理冲突。具有 乐观并发控制 的 STM 库会在执行期间记录内存访问，在执行后验证每笔交易，并在验证发现冲突时中止并重新执行交易。然而，由于所需的冲突簿记和中止，与定制解决方案相比，STM 库通常存在性能限制，因此很少在生产中部署。

区块链用例

过去的研究表明，当 STM 应用于特定用例时，其性能可以显着提高。事实上，适用于区块链用例的三个重要观察结果指导了 Block-STM 的设计。

• 无需单独提交交易： 与通用 STM（其中每个线程都有无限的交易流，可以根据任意时间到达的查询进行提交）相比，在区块链中，状态通常按区块更新。这使得 Block-STM 可以避免单独提交交易的同步成本。相反，Block-STM 通过轻量级同步惰性地提交一个区块中的所有交易。此外，垃圾回收非常简单，因为可以在区块之间清理内存。
• VM 为乐观内存访问提供安全性： 交易在智能合约语言中指定，例如 Move 和 Solidity，并在虚拟机中运行，该虚拟机封装了它们的执行并确保安全行为。这很好地分离了抽象，并允许 Block-STM 避免处理并行推测执行期间不一致状态的后果（一种称为不透明性的属性）。
• 预定义的顺序减少了同步： 一般来说，STM 库针对不确定性，并将确定性视为系统中的限制，从而阻碍了性能。这使得它们不适合区块链用例，因为执行相同区块的验证者可能会导致不同的最终状态。然而，在 Block-STM 中，确定性被认为是性能上的恩赐。事实上，最终结果保证与固定、预设顺序的交易的顺序执行相匹配，并且此约束用于系统的优势。正如 Bohm 论文在数据库上下文中先前指出的那样，这是可能的，因为就特定序列化达成一致可以减少执行期间所需的同步量。例如，如果交易 tx5 和交易 tx9 之间存在冲突，那么 tx9 将等待 tx5——否则，如果没有顺序，执行这些交易的线程将需要打破僵局。因此，在直观的层面上，通用 STM 将解决一个更难的问题（即，一种共识形式），而 Block-STM 针对一个更简单的问题（即，它只需要执行交易）。

核心技术

Block-STM 将已知技术与新颖的想法相结合：

• 乐观并发控制： 交易以乐观的方式并行执行，并在执行后进行验证。不成功的验证会导致重新执行。由于预设的顺序，验证不是彼此独立的，并且必须在逻辑上按顺序发生。与之前的工作不同，成功的验证并不意味着可以提交交易。相反，交易验证失败意味着只有在之后成功验证所有更高的交易才能提交。
• 多版本数据结构： Block-STM 使用多版本数据结构来避免写-写冲突。对同一位置的所有写入都与其版本一起存储，版本包含其交易 ID 和写入交易乐观地重新执行的次数。当交易 tx 读取一个内存位置时，它从多版本数据结构中获得该位置的值，该值由预设顺序中出现在 tx 之前的最高交易写入，以及关联的版本。
• 验证： 在执行期间，交易记录一个 读取集 和一个 写入集。在验证期间，读取读取集中的所有内存位置，并将返回的版本与读取集中存储的相应版本进行比较。
• 协同调度： Block-STM 引入了一个协同调度程序来协调线程之间的验证和执行任务。由于预设的顺序决定了必须按顺序提交交易，因此成功验证交易执行并不能保证可以提交。这是因为区块中较早交易的中止和重新执行可能会使读取集无效并需要重新执行。因此，交易和执行线程之间的静态映射不起作用。相反，协同调度程序优先处理较低交易的执行和验证任务。然而，有序集和优先级队列在多核环境中扩展是出了名的具有挑战性。Block-STM 通过使用基于计数的方法来规避这个问题，这种方法通过预设的顺序和交易的紧凑索引成为可能。
• 动态依赖性估计： Block-STM 利用预设的顺序来显着避免中止，对于 STM 系统而言，中止是性能的关键，因为中止会级联并导致大量浪费的工作。当验证失败时，交易上次执行的写入集用于通过将多版本数据结构中的所有写入标记为 ESTIMATION 来估计依赖关系。当另一个交易从多值数据结构中读取 ESTIMATION 值时，它可以等待依赖关系得到解决——如果没有估计，它会继续执行，但很可能（如果写入 ESTIMATION 的交易确实在下一次重新执行时写入到相同的位置）稍后验证失败并被中止。与通过从 pre-block 状态以令人尴尬的方式并行预先执行所有交易来生成写入估计的教科书方法相比，我们的方法有两个好处：（a）仅在需要时才生成估计（而不是针对每个交易），并且 (b) 估计通常基于比区块开始时更新鲜的状态。

评估

我们在 Aptos 开源代码库 中以安全 Rust 实现了 Block-STM，依赖于 Rayon、Dashmap 和 ArcSwap crates 进行并发。我们使用非平凡的点对点 Move 交易（8 次读取和 5 次写入）评估了系统。在下面的图表中，我们将 Block-STM 与区块的顺序执行进行了比较。每个区块包含 10k 交易，账户数量决定了冲突和争用的级别。在低争用下，Block STM 在 32 个线程上实现了比顺序执行快 16 倍的速度，而在高争用下，Block-STM 实现了超过 8 倍的加速。重要的是，当工作负载本质上是顺序的时，Block-STM 会产生很小的开销。总的来说，Block-STM 能够动态且透明地（没有来自用户的任何提示）从工作负载中提取固有的并行性。与相关工作的详细比较可以在 论文 中找到。

不同争用级别的 Block STM 性能

那么我们是如何获得这种性能的呢？

协同调度程序与多版本技术相结合，使 Block-STM 能够利用预设的交易顺序来估计依赖关系并显着减少浪费的工作量。协同调度程序是算法的关键部分，包含大多数性能关键逻辑。除其他外，它确保：

• 每个中止的交易都会被重新执行，但同一个交易永远不会被多个线程同时执行。
• 如果一个交易被重新执行，那么所有更高的交易都必须被重新验证。因此，不同的线程可能会同时验证同一个交易执行，但最多只能有一个线程中止它。
• 遇到依赖关系的交易在依赖关系解决后恢复。
• 所有交易最终都会被提交。

挑战在于尽可能减少同步开销来确保上述内容。跟踪执行和验证任务的一种天真但代价高昂的方法是有两个优先级队列（或有序集合以避免重复）。一旦依赖关系被解决或验证被中止，相应交易的执行任务就会被添加到执行队列中。类似地，一旦一个交易被执行，就会为预设顺序中所有更高的交易创建验证任务，并将其添加到验证队列中。

高效的并发有序集

相反，Block-STM 利用预设的交易顺序并使用两个原子计数器。

这些计数器跟踪任何需要执行或验证的交易的下限索引。结合一种了解每个交易状态的方法，这些索引可以有效地模拟天真方法中的有序集合语义。线程通过 fetch-and-increment 计数器（带有较低的索引）来重复尝试获取任务，并读取状态以检查相应的交易是否已准备好执行（或验证，具体取决于计数器）。Fetch-and-increment 还可以自然地将线程分散到不同的索引，确保状态信息不会被过度争用，这允许我们使用互斥锁并简化实现（可以实现无锁实现，但基准测试并未显示出显着改进）。

交易的可能状态在下图给出。下图中的参数 i 是交易被重新执行的次数。

我们还使用锁来同步依赖关系列表，但是，如果不小心，仍然可能存在一些细微的竞争，协同调度程序必须避免这些竞争——光荣的细节在论文中。

惰性提交机制

Block-STM 提交整个区块以消除跟踪单个交易何时可以安全提交的同步成本。简而言之，当满足以下所有条件时，可以提交整个区块：

1. 执行和验证索引都达到区块大小。
2. 没有正在进行的验证和执行任务。
3. 所有交易的状态均为 EXECUTED。

正如我们在我们过于严格的系统结果证明中所证明的那样，Block-STM 算法中的前两个条件意味着第三个条件。为了原子地验证 (1) 和 (2)，我们引入了两个附加计数器。第一个计数器跟踪正在进行的任务的数量。在代码中的错误位置增加或减少此计数器太容易，并且永远不会观察到 (2)。为了避免此类错误，我们使用了资源获取即初始化 (RAII) 模式将计数器与任务保护相关联，确保它分别在任务分派之前和完成之后增加和减少。

为了将此计数器与跟踪执行和验证索引的计数器一起原子地读取，我们使用了双重收集技术。这需要引入第四个原子计数器来跟踪执行和验证计数器减少的次数。然后，我们收集所有计数器的值两次（顺序很重要！），如果在两种情况下都满足条件 (1) 和 (2)，那么（正如我们证明的那样），在两者之间的某个时间，条件 (1) 和 (2) 确实同时满足。在这种情况下，整个区块可以安全地提交，因为不再需要或将创建更多的验证和执行任务。

如果你像我们一样，对设计算法、将其付诸实践并对 Web3 的未来产生真正影响充满热情，请联系我们——我们正在 Aptos 招聘。

• 原文链接： medium.com/aptoslabs/blo...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～