B树中的乐观锁：Optimistic Locking in B-Trees

Optimistic Locking in B-Trees

Source | HN Comments

文章探讨了B树在现代硬件上的高效性。B树具有出色的缓存效率，能充分利用大型缓存，并支持高效的线程同步。文章重点介绍了乐观锁耦合技术，通过序列号检测并发修改，避免了锁竞争，提高了B树的并发性能。这种技术使得B树在读写操作上都表现出色，即使在多核环境下也能高效运行，证明了B树作为数据结构的持久价值。

2025年3月6日

B树之路：基于乐观锁耦合的 B-Trees

B-Trees 经受住了时间的考验。在本文中，我们将探讨为什么我们仍然使用这种有 55 年历史的数据结构：当我们使用无竞争的乐观锁耦合时，它在现代硬件上仍然非常高效！

Philipp Fent

To B or not to B: B-Trees with Optimistic Lock Coupling

B树之路：基于乐观锁耦合的 B-Trees

B-Trees 是少数真正经受住时间考验的专用数据结构之一，至今已有超过 50 年的历史。它们诞生于 unix time 的元年，运行在一个拥有惊人的 7.25MB 磁盘存储的系统上——注意，不是 DRAM！它们只比关系数据库概念本身晚一个月，并且见证了多核架构、复杂的缓存层次结构、快速网络附加存储等等突破性变革的诞生。然而，尽管大多数技术都会显示出它们的年龄，并且可以舒适地退休，但 B-Trees 仍然是数据存储中无处不在的工具。

经典永不过时

许多经过实践检验的文件和数据库系统都使用 B-Trees，并且新的系统也对它们进行研究。在这篇博文中，我们将探讨为什么我认为 B-Trees 是最实用的数据结构，以及为什么它们是现代硬件的出色数据结构，尽管它们比现代硬件早了几十年。

CedarDB 使用 B-Trees 作为其主要数据存储，原因在于它具有两个特别适合现代系统的特性：

它们具有令人难以置信的缓存效率，并且可以充分利用大型缓存。
B-Trees 可以在数百个线程之间有效地同步。

这些属性对于以低延迟有效地存储和检索数据非常重要。纯粹的数据仓库系统通常会放弃索引结构，因为它们通常顺序扫描大部分数据。但是，对于其他系统，索引对于低延迟的点查找、小型连接以及强制执行外键约束至关重要。在 CedarDB 中，我们将数据仓库功能与短时运行的事务相结合。对于数据仓库风格的分析，我们通常还依赖于具有块式最小-最大边界剪枝的全表扫描。这通常适用于隐式聚集的属性（如创建日期），但对于上次访问日期则会失效，因为数据并非总是整齐地聚集在一起。特别是对于大型数据集，CREATE INDEX 语句可以使查询运行时间从几分钟缩短到几毫秒。

因此，我们不能走简单地跳过索引结构的路子。相反，我们重新审视了古老的 B-Trees，并对其进行了调整，使其能够在现代高度并行的硬件上高效工作。

缓存效率

B-Trees 的一个优点是它们出色的数据局部性。在我看来，B-Trees 在实践中非常接近 cache oblivious，因此它们可以从硬件开发中不断增长的更快内存中获益，而无需更改代码。要在 B-Tree 中找到一个值，我们只需在树中的节点之间进行少量的真正随机访问。

为了量化随机访问的确切数量，让我们看看实际的 B-Tree 中有多少层。真实的 ClickBench 数据集大约有 1 亿行和 70GB 原始数据。其 schema 定义了一个跨越 5 列的主键索引，从而产生了一个 4GB 的 B-Tree 索引。

CedarDB 使用 64KB 的页面，因此具有 32 字节键的 B-Tree 的扇出为 1361。因此，对于 B-Tree 中的每一层（即随机访问），我们将数据集中的搜索范围缩小了三个数量级。根据经验，一千行需要一层，一百万行需要两层，十亿行需要三层，依此类推。因此，ClickBench 的 1 亿行可以舒适地容纳在三层中。事实上，我们的 B-Tree 的根节点有 49 个子节点，总高度仅为三。下图显示了这种巨大扇出的可视化效果。

The ClickBench primary key B-Tree.

ClickBench 主键 B-Tree 的可视化。中间的根节点通过 49 个内部节点连接到总共 66,689 个叶节点。

该图像说明了 B-Tree 的扇出是如何迅速增加的。这里，我们使用径向节点布局，因为超过 6 万个叶节点对于传统的树可视化来说太多了。虽然根节点和内部节点在这里仍然非常清晰，但这主要是因为根节点严重未满。

B-Tree 的扇出也很好地对应于现代 CPU 的缓存层次结构。虽然每个级别的缓存没有大幅度变大，但它们遵循相同的趋势。我们 B-Tree 的 64KB 根节点可以很好地容纳在现代 CPU 的 L1/L2 缓存中，下一级的内部节点可以容纳在 L3 中，而叶节点可以容纳在主内存中。

Visualization of the cache topology of an AMD EPYC CCD using hwloc.

现代 CPU 的缓存拓扑，它遵循与 B-Tree 节点类似的层次结构增长。

热数据会自动缓存在现代 CPU 的巨大缓存中，因为它被频繁访问。虽然 B-Trees 最初是为具有小主内存的系统设计的，但它们的缓存局部性如今极大地受益于缓存层次结构，并且仍然可以轻松地扩展到超出缓存或主内存。内存中的数据结构（如哈希表或基数树）可能更快，但它们在扩展到大于内存的数据大小和并行访问方面存在其自身的一系列挑战。

基于锁耦合的同步

高效地共享索引结构的状态是一个巨大的话题。许多系统可以通过分配或划分它们的工作来避免线程之间的同步。然而，数据库系统都是关于管理共享状态的。因此，它们需要有效地同步其数据结构。

全局读/写锁的简单解决方案似乎足够简单，但服务器现在有 100 多个内核，并且采用全局锁的代价非常高昂。虽然无锁数据结构是理想的，但这些数据结构通常是写时复制的，这对于大型数据大小来说并不能真正扩展。然而，最终目标是避免竞争，以便所有并行内核都可以完成有用的工作。B-Trees 通过层级节点的锁耦合来解决这个问题，这使得锁定快速地具有细粒度。我们从根节点上的锁开始，这实际上锁定了所有内容，但我们很快将其缩小到实际访问的数据范围。

Lock coupling in the ClickBench primary key B-Tree.

B-Tree 中锁耦合的动画。我们首先在根节点上获取红色锁，然后在内部节点上锁定黄色锁，最后到达绿色的细粒度叶锁。

虽然这种朴素的实现仍然存在一些竞争，但我们首先来看一下基本知识，然后再来看一下乐观锁耦合，乐观锁耦合可以使大多数操作无锁。

锁耦合背后的基本思想是，我们始终持有对我们感兴趣的数据的锁，首先是非常粗略的锁，然后是细粒度的锁。因此，要访问 B-Tree 中的一行，我们首先锁定根节点，然后向下移动到我们想要访问的范围。然后我们锁定内部节点，并且可以解锁根节点，始终持有一个或两个锁。

虽然锁耦合极大地受益于 B-Trees 的高扇出，但这也突出了所有访问都开始的共享根节点的瓶颈。虽然我们通常可以共享锁定根节点，但此共享锁仍需要更新引用计数的锁定状态。虽然修改引用计数本身通过原子操作是无锁的，但由于 CPU 使用 MESI 协议实现此操作的方式，写入共享状态仍然会导致竞争。

考虑以下示例，其中两个并发线程正在读取并共享锁定 B-Tree 的根节点。请注意，此示例显式写出缓存一致性状态转换以说明竞争。

线程 1：lock_shared(root)：获取根独占锁 → 递增引用计数 → 根被修改
线程 2：lock_shared(root)：获取根独占锁 → 使远程缓存失效 → 递增引用计数 → 根被修改
线程 1：unlock_shared(root)：获取根独占锁 → 使远程缓存失效 → 递减引用计数 → 根被修改
线程 2：unlock_shared(root)：获取根独占锁 → 使远程缓存失效 → 递减引用计数 → 根被修改

乐观锁耦合

所有这些争夺独占写访问会导致线程之间的元数据竞争。即使我们干净地共享数据结构而不进行修改，并且仅保持共享锁。一种避免引用计数竞争的简洁锁定替代方法是 sequence lock，如 linux kernel 中使用的那样。在这里，我们不会主动防止并发修改。相反，我们引入一个序列号来事后检测它们。

基本思想是在不持有任何（共享）锁的情况下读取节点，以消除竞争。但是，这会冒着与并发修改发生数据竞争的风险。因此，我们需要验证我们是否读取了正确的数据，否则重试读取。

检测并发修改的过程依赖于修改序列号，写入器需要为每次修改 B-Tree 节点递增该序列号。然后，读取器可以比较读取前后的序列号，以检测是否观察到任何修改。在只读情况下，这会增加一个额外的负载。但是，由于缓存行现在可以保持共享，因此这是一个快速的 L1 缓存读取，实际上是瞬间的。写入器需要更加小心，并确保他们始终递增版本而不是解锁。

我们将此称为乐观锁定，因为我们只是假设没有写入器，但有一个备用计划。这巧妙地利用了 B-Trees 很少更新根节点的事实。在我们的三级树的示例中，扇出为 1361，因此只有每 1361 * 1361 = 185 万次插入才会发生写入。当然，叶节点的修改仍然需要锁定它们，但叶节点无论如何都是细粒度的，因此我们几乎不会遇到竞争。

虽然这乍听起来很容易，但遍历 B-Tree 节点的代码仍然有些棘手。考虑以下节点遍历的伪代码。

traverse_node(page, version, key):
  retry:
  # 读取页面
  pageCopy = copy(page)
  if version != atomic_load(page.version):
    goto retry;
  # 转到下一页
  childPtr = binary_search(pageCopy, key)
  nextPage = load(childPtr)
  nextVersion = atomic_load(nextPage.version)
  # 验证没有写入器超过读取器
  if version != atomic_load(page.version):
    goto retry;
  # 安全地遍历到下一个节点
  page = nextPage

在这里，我们假设 copy() 是一个并发安全复制操作。在验证版本序列号之后，我们可以确定我们对数据有一个一致的视图，并且我们可以使用常规函数来搜索该节点。但是，复制 64KB 的整个节点效率很低。在 CedarDB 中，我们使用精心实现的 binary_search，它对于并发修改是安全的，特别是其排序数据的不变性可能会被违反。

TODO 乐观锁耦合的性能。B-Tree 的乐观锁定几乎与非同步读取一样好。

乐观锁增加了一点复杂性，但老实说，对于真正的 lock-free data structures，我见过更糟糕的情况。尽管如此，2019 年论文中报告的性能数字仍然令人印象深刻，并且它们显示出几乎没有非同步查找的开销。也许令人惊讶的是，写入操作也更快，即使写入锁更复杂。避免在主要读取根节点锁状态上的竞争也在这里有所帮助。

B-Trees 不会过时

虽然尤其是在计算机科学中，变化频繁，但 B-Trees 将长期存在，原因如下：它们的局部性从小型磁盘无缝地转换到我们现在在现代系统中拥有的缓存。这也使它们足够接近 cache-oblivious，并适应它们可用的任何资源。同步也是如此。凭借其高扇出和乐观锁耦合，它们在高度并行的环境中蓬勃发展。虽然它们在技术上不是无锁的，但实际上是无锁的就足够了。对于特殊应用，可能存在更快、更定制的数据结构，但对于通用性能而言，B-Trees 的工作效果非常好，以至于其他任何东西都具有严重的收益递减。

内容