Block-STM：我们如何在 Aptos 区块链上每秒执行超过 16 万笔交易
世界一流的工程与 Aptos 的前沿研究相得益彰。 有关详细信息，请参阅 Block-STM 论文和 Aptos 代码库。
作者：Alexander Spiegelman / Rati Gelashvili
TL;DR:
我们设计并实现了一个高效、多线程、内存中的并行执行引擎，通过利用预设的事务顺序并将软件事务内存技术与新颖 协作时间表。
挑战
智能合约执行是区块链的主要吞吐量瓶颈。 在提出区块并就其顺序达成一致后，验证者必须在有序区块中执行交易。 至关重要的是，验证者必须达到相同的最终状态，这必须对应于交易的某些顺序执行。 由于缺乏基础解决方案，当前的区块链要么按顺序执行，要么需要令人尴尬的并行工作负载（即没有内部冲突）以提高性能。 顺序执行不能很好地扩展，并且在考虑广泛的智能合约时假设所有交易都是可交换的是不现实的。 事实上，由于潜在的性能攻击、访问流行的合约（例如，由于拍卖和套利等经济机会），区块链中的交易可能会出现大量访问冲突。
目标
考虑到工作负载中的实际访问冲突，设计一个并行执行引擎，以提取可能的最大固有加速。 为了获得最佳编程和用户体验，算法应该对用户透明。 一些区块链并行执行引擎采用的另一种方法是强制用户预先声明依赖关系，这严重限制了事务可以做什么，并且可能需要分解或重试事务。 相反，为了避免产生此类成本和编程烦恼，我们的并行执行引擎的系统设计目标是在内部管理所有冲突并自动适应工作负载。
STM 方式
软件事务内存 (STM) 库开创的一种学术方法是检测内存访问以检测和管理冲突。 具有乐观并发控制的 STM 库记录执行期间的内存访问，在执行后验证每个事务，并在验证出现冲突时中止并重新执行事务。 然而，由于所需的冲突簿记和中止，与定制解决方案相比，STM 库经常受到性能限制，因此很少在生产中部署。
区块链用例
过去表明，当 STM 应用于特定用例时，它们的性能可以显着提高。事实上，区块链用例的三个重要观察指导了 Block-STM 的设计。
无需单独提交事务：与通用 STM（每个线程有无限的事务流基于可能在任意时间到达的查询提交）相比，在区块链中，状态通常更新每个块。这允许 Block-STM 避免单独提交事务的同步成本。相反，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 的事务确实写入相同下一次重新执行中的位置）以稍后验证失败并中止。与通过从预块状态并行地预先执行所有事务来生成写入估计的教科书方法相比，我们的方法有两个好处：（a）仅在需要时生成估计（不是针对每个事务），以及（b ) 估计通常基于比块开始时更新鲜的状态。
评估
我们在 Aptos 开源代码库中的安全 Rust 中实现了 Block-STM，依靠 Rayon、Dashmap 和 ArcSwap crates 实现并发。 我们使用非平凡的点对点移动事务（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 也自然地将线程分散到不同的索引，确保状态信息不会被大量竞争，这允许我们使用互斥锁并简化实现（无锁实现是可能的，但基准测试并没有显示出显着的改进）。
下图给出了交易的可能状态。下图中的参数 i 是事务被重新执行的次数。
我们还使用锁来同步依赖关系列表，但是，如果不小心，协作调度程序必须避免一些微妙的竞争仍然可能 - 精彩的细节在论文中。
惰性提交机制
Block-STM 提交整个区块以消除跟踪单个事务何时可以安全提交的同步成本。简而言之，当满足以下所有条件时，可以提交整个块：
执行和验证索引都达到块大小。
没有正在进行的验证和执行任务。
所有交易的状态都是 EXECUTED。
正如我们在 #way-too-rigorous-for-a-systems-result 证明中所证明的那样，Block-STM 算法中的前两个条件暗示了第三个条件。为了原子地验证 (1) 和 (2)，我们引入了两个额外的计数器。第一个计数器跟踪正在进行的任务的数量。在代码中的错误位置增加或减少这个计数器太容易了，而且从不观察 (2)。为避免此类错误，我们使用资源获取即初始化 (RAII) 模式将计数器与任务守卫相结合，确保在分派任务之前和完成之后分别增加和减少它。
为了以原子方式读取此计数器以及跟踪执行和验证索引的计数器，我们使用双重收集技术。这需要引入第四个原子计数器来跟踪执行和验证计数器减少的次数。然后，我们收集所有计数器的值两次（顺序很重要！）如果在两种情况下都满足条件（1）和（2），那么（正如我们所证明的），在两者之间的某个时间，条件（1）和(2) 确实同时满足。在这种情况下，整个块被安全提交，因为不再需要或将创建任何验证和执行任务。
如果您像我们一样热衷于设计算法、将它们付诸实践并对 Web3 的未来产生真正的影响，请联系我们——我们正在 招聘。
Last updated
