数据库管理系统（DBMS）在处理并发操作时，需要一套并发控制协议来确保共享对象的“正确”结果。这种“正确性”可以从两个方面来理解：

• 逻辑正确性 (Logical Correctness) ：指线程能够看到它应该看到的数据。例如，如果一个B+树索引插入了一个键值，该线程立即读取该键值时，它应该能看到它，而不会得到一个假阴性（false negative）结果。
• 物理正确性 (Physical Correctness) ：指数据结构的内部表示是健全的。这意味着在多线程读写数据时，数据结构的完整性（例如指针和引用）必须得到维护，以避免指向无效内存位置，从而导致程序崩溃（seg fault）等问题。本次讨论主要关注的是物理正确性。

锁 (Locks) 与锁存 (Latches) 的区别

在数据库领域，"锁" 和 "锁存" 是两个不同的概念，用于保护不同层面的数据。

锁 (Locks)

• 保护对象 ：保护数据库的 逻辑内容 ，如元组（tuples）、一组元组或整个表、数据库，使其免受其他事务的并发访问和修改。
• 持有时间 ：通常在 整个事务期间 持有。这意味着如果一个事务正在修改某个数据，它会持有锁直到事务完成。
• 回滚需求 ：需要支持 回滚 机制。如果事务在修改过程中崩溃，DBMS必须能够撤销已做的更改。
• 模式类型 ：有多种锁模式，如共享 (Shared)、排他 (Exclusive)、更新 (Update)、意向 (Intention) 等。
• 死锁处理 ：依赖于外部的 锁管理器 (Lock Manager) 或事务管理器 (Transaction Manager) 来检测和解决死锁，例如通过等待-超时 (Waits-for, Timeout) 或事务中止 (Aborts)。

锁存 (Latches)

• 保护对象 ：保护DBMS内部数据结构（如索引、缓冲区池中的页面表等）的 关键代码段 (critical sections) 及其 物理完整性 ，使其免受其他线程的并发访问和修改。
• 持有时间 ：只在 操作的持续期间 持有，通常是极短的时间。例如，当线程需要更新一个页面时，它会获取该页面的锁存，进行更改，然后立即释放锁存。
• 回滚需求 ： 不需要支持回滚 。因为锁存保护的操作通常是原子性的，如果无法获取锁存，操作就不会执行，因此没有需要回滚的更改。
• 模式类型 ：主要有两种模式—— 读模式 (Read Mode) 和 写模式 (Write Mode) 。

读模式 (Read Mode) ：允许多个线程同时共享读锁存，因为读操作不会修改数据结构。

写模式 (Write Mode) ：是排他性锁存，只允许一个线程持有。当一个线程持有写锁存时，其他线程不能读取或修改该对象。

• 死锁处理 ： 不提供死锁检测或解决机制 。死锁的避免完全取决于 编程纪律 (Coding Discipline) ，即通过良好的设计和实现来确保死锁不会发生。

锁存的实现方式

锁存的实现通常基于现代CPU提供的原子比较-交换 (compare-and-swap, CAS) 指令。主要有以下几种方法：

阻塞式操作系统互斥锁 (Blocking OS Mutex)

• 实现方式 ：这是最简单的方式，直接使用操作系统提供的互斥锁（如C++标准库中的 std::mutex）。在Linux中，futex（fast user-space mutex）是一种常见的实现，它首先尝试在用户空间通过自旋锁获取，如果失败，则下沉到内核空间获取更昂贵的互斥锁，并可能导致线程被调度器挂起。
• 优点 ：使用简单，无需额外的编码。
• 缺点 ： 非可伸缩性 ，每次加锁/解锁操作可能需要约25纳秒，因为涉及操作系统的调度开销，对于高竞争系统来说，性能会成为问题。

测试-设置自旋锁 (Test-and-Set Spin Latch / TAS)

• 实现方式 ：由DBMS自己实现，通常使用CPU的单指令原子比较-交换操作。线程会反复尝试设置一个内存位置（例如，将一个布尔值设置为 true），直到成功获取。如果无法获取，线程会在一个 while 循环中“自旋”重试。
• 优点 ： 效率极高 ，加锁/解锁操作通常是单个CPU指令。
• 缺点 ： 非可伸缩性且不缓存友好 。在高竞争环境下，线程会不断自旋，消耗CPU周期但未做有效工作，导致CPU利用率飙升。同时，这可能引起缓存一致性问题，因为多个线程在不同CPU上轮询同一个缓存行。
• 优化 ：开发者可以根据工作负载决定是否在自旋失败后短暂地让出CPU（yield），或在尝试一定次数后中止操作。由于DBMS对数据结构的使用场景有更深入的了解，因此可以比操作系统做得更好。

读写锁存 (Reader-Writer Latch)

• 实现方式 ：通常在自旋锁的基础上实现。它通过管理读/写队列和计数器来区分读写请求。
• 优点 ： 允许并发读取 ，这对于读密集型工作负载能显著提高性能，因为多个读取线程可以共享资源而无需等待。
• 缺点 ： 增加了复杂性 。DBMS需要管理读写队列以避免写线程饥饿 (starvation)，同时相比简单的自旋锁，它需要更多的元数据和存储开销。

哈希表 (Hash Table) 的锁存

哈希表相对容易支持并发访问，因为线程访问数据结构的方式有限。

• 单向访问 ：所有线程在从一个槽位移动到下一个槽位时都沿同一个方向（自上而下），且一次只访问一个页面或槽位。这使得 死锁不可能发生 。
• 重整大小 ：在调整哈希表大小时，通常会获取整个表的 全局锁存 （例如在头部页面上），以防止其他线程在此期间读写表。

哈希表的锁存策略主要有两种。

页面锁存 (Page Latches)

• 特点 ：每个页面有自己的读写锁存，保护整个页面内容。
• 权衡 ：需要存储的锁存数量较少（每个页面一个），但 可能会降低并行性 ，因为即使两个线程操作不同槽位，如果它们在同一页面内，也可能无法同时运行。

槽锁存 (Slot Latches)

• 特点 ：每个槽位都有自己的锁存。
• 权衡 ： 允许更高的并行性 ，因为锁存粒度更细。但 增加了存储和计算开销 ，因为线程在扫描时需要为每个访问的槽位获取锁存。

B+树 (B+Tree) 的锁存

B+树的并发控制更为复杂，因为它不仅涉及节点内容的修改，还涉及树结构的动态变化（如分裂和合并）。

B+树并发控制主要需要解决两个问题：

1. 多个线程同时修改同一个节点的内容。
2. 一个线程遍历树时，另一个线程可能正在分裂或合并节点，导致页面位置改变或指针失效。

解决这些问题的一种经典技术称为 锁存爬行 (Latch Crabbing) 或 锁存耦合 (Latch Coupling) 。

锁存爬行 (Latch Crabbing) 的基本思想

锁存爬行的基本思想是：

1. 获取父节点的锁存。
2. 获取子节点的锁存。
3. 如果确定子节点是“安全”的，则释放父节点的锁存。

“安全”节点定义 ：一个节点被认为是安全的，当对其进行更新操作时，它不会导致分裂 (split) 或合并 (merge)。

• 对于 插入 操作，如果节点未满（不会分裂），则认为是安全的。
• 对于 删除 操作，如果节点内的键值数量多于一半（不会合并），则认为是安全的。

查找 (Find) 操作

• 查找操作只涉及读取，因此可以全程使用 读锁存 。
• 从根节点开始，获取子节点的读锁存后，可以立即释放父节点的读锁存，因为读操作不会改变树的结构。

插入 (Insert) / 删除 (Delete) 操作

• 从根节点开始，获取 写锁存 。
• 在获取子节点锁存后， 检查该子节点是否安全 。如果安全，则可以释放所有祖先节点上持有的写锁存。
• 如果不安全，则需要继续持有祖先节点的锁存，直到找到安全的子节点或到达叶节点。
• 释放锁存的顺序 ：从性能角度考虑，应尽快释放更高层级（更接近根）的锁存，因为它覆盖的节点范围更广，能提高并行性。

根节点争用 (Root Contention) 问题

锁存爬行的一个问题是，每次插入或删除操作都必须在根节点上获取 写锁存 。由于写锁存是排他性的，这意味着在任何给定时间，只有一个线程可以持有根节点的写锁存，从而形成了一个 单点瓶颈 (single point of contention) ，严重限制了高并发系统的并行性。

乐观锁存 (Optimistic Latching)

为了解决根节点争用问题，出现了一种更优化的锁存算法，通常称为 乐观锁存 (Optimistic Latching) 或 Baron-Schlock-Nick 算法。

核心思想 ： 乐观假设 在实际数据库系统中，B+树节点通常很大（如8KB或16KB），因此大部分插入或删除操作不会导致节点分裂或合并。基于这个假设，算法会 乐观地假定 目标叶节点是安全的。

具体操作

1. 初始遍历 ：线程从根节点开始， 全程使用读锁存 进行锁存爬行，直到到达目标叶节点。
2. 获取叶节点写锁存 ：到达叶节点后，线程尝试获取该叶节点的 写锁存 。
3. 检查安全并执行 ：如果此时发现叶节点是安全的（例如，有足够的空间进行插入而无需分裂，或删除后仍超过半满而无需合并），则线程可以直接在该叶节点上进行修改，然后释放锁存。
4. 失败重启 ：如果发现叶节点不安全（例如，需要分裂或合并），则说明乐观假设失败。此时，线程会 释放所有已获得的锁存，并中止当前操作 。然后，它会 从头开始，并使用悲观策略 ，即采用传统的锁存爬行方法，从根节点开始全程获取 写锁存 。

• 优点 ：显著减少了根节点和中间节点的写锁存持有时间， 提高了并发性 。
• 缺点 ：如果乐观假设经常失败（例如在节点频繁分裂或合并的负载下），那么每次重新启动并重新遍历树都会导致 浪费工作 (wasted work) ，反而可能比悲观策略慢。但在大多数实际场景中，这种乐观策略表现良好。

叶节点遍历 (Leaf Node Scans) 与死锁

在B+树中，如果只进行自上而下的遍历，死锁是不可能发生的，因为所有线程都沿一个方向前进。然而，当引入 叶节点扫描 (Leaf Node Scans) 时（即在叶节点层级从左到右或从右到左遍历），情况会变得复杂，因为此时线程可能需要获取不同方向的锁存，从而导致 潜在的死锁 。

例如，一个线程可能正在从左向右扫描并持有右侧节点的读锁存，而另一个线程从右向左扫描并持有左侧节点的读锁存，它们可能会同时尝试获取对方持有的锁存，从而发生死锁。

如何确保不会死锁 ：

• 锁存不提供死锁检测或避免功能 。
• 依赖编程纪律 ：解决这个问题的唯一方法是依靠 编程纪律 (Coding Discipline) 。
• “无等待”模式 (No-Wait Mode) ：当一个线程尝试获取叶节点上的锁存但该锁存不可用时，它会 立即中止操作 （释放所有已持有的锁存），然后 重新开始操作 。
• 原因 ：由于锁存是低级别的机制，它没有关于其他线程正在做什么的全局信息。因此，与其尝试推断或等待，最简单有效的方法就是立即中止并重试。虽然这可能导致在极端情况下线程“饥饿”或浪费周期，但在实践中，这通常是最佳策略。

延迟父节点更新 (Delayed Parent Updates) / Blink-Tree 优化

正常的B+树节点溢出时，需要更新三个节点：被分裂的叶节点、新创建的叶节点以及它们的父节点（用于添加新的分隔键）。这种多节点的更新需要复杂的锁存管理，可能导致更多的锁争用和重启。

Blink-Tree 优化 引入了一种技术，当叶节点溢出时， 延迟更新其父节点 。

实现方式 ：

1. 当叶节点分裂时，线程只更新叶节点本身，并创建一个新的相邻节点。
2. 它不会立即更新父节点。相反，它会在树的 全局信息表 中记录一个待处理的更新，表明父节点需要添加一个新的分隔键。
3. 下一次有线程以写模式获取该父节点的锁存时，它会首先检查并应用这个延迟的更新，从而使树结构变得一致。

• 优点 ：这避免了在分裂时重新启动乐观锁存操作，因为它不需要立即获取并持有父节点的写锁存。
• 正确性 ：这种方法仍然能保证正确性，因为即使父节点尚未更新，查找操作也可以通过遍历当前的指针（包括可能的兄弟节点指针，如果存在）来找到正确的数据。

总结

总而言之，使数据结构具有线程安全性在实践中是出了名的困难。我们讨论了哈希表和B+树的并发控制，但其核心思想是通用的：

• 强制单向操作 （如哈希表的自顶向下扫描，避免死锁）。
• 在遇到死锁潜力时立即中止并重试操作 （如B+树的叶节点扫描）。
• 乐观地假设快速路径 （如乐观锁存，大部分操作只需读锁存）。

这些并发控制技术在整个计算机科学和系统领域都有广泛应用。商业数据库系统通常会自己实现这些核心数据结构，以便根据其特定的目标操作环境进行优化。