> For the complete documentation index, see [llms.txt](https://zhenghe.gitbook.io/open-courses/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zhenghe.gitbook.io/open-courses/cmu-15-445-645-database-systems/index-concurrency-control.md).

# Index Concurrency Control

在前两节中讨论的数据结构中，我们都只考虑单线程访问的情况。实践中，绝大多数情况下，我们需要在并发访问情况下保证我们的数据结构还能够正常工作。除了 VoltDB，它用一个线程处理所有请求，彻底排除了并发的需要。

## Concurrency Control

通常我们会从两个层面上来理解并发控制的正确性：

* Logical Correctness：（17 节）我是否能看到我应该要看到的数据？
* Physical Correctness：（本节）数据的内部表示是否安好？

### 本节大纲：

* Latch Modes
* Index Crabbing/Coupling
* Leaf Scans
* Delayed Parent Updates

## Latch Modes

#### Read Mode

* 多个线程可以同时读取相同的数据
* 针对相同的数据，当别的线程已经获得处于 read mode 的 latch，新的线程也可以继续获取 read mode 的 latch

#### Write Mode

* 同一时间只有单个线程可以访问
* 针对相同的数据，如果获取前已经有别的线程获得任何 mode 的 latch，新的线程就无法获取 write mode  的 latch

## B+ Tree Concurrency Control

我们希望在最大程度上允许多个线程同时读取、更新同一个 B+ Tree index，主要需要考虑两种情况：

* 多个线程同时修改同一个 node
* 一个线程正在遍历 B+ Tree 的同时，另一个线程正在 splits/merges nodes

举例如下：

![](/files/-L_DV_tT526tMb37s8Yx)

T1 想要删除 44，T2 想要查询 41。删除 44 时，DBMS 需要 rebalance D 节点，将 H 节点拆分成两个节点。若在拆分前，T2 读取到 D 节点，发现 41 在 H 节点，此时时间片轮转到了 T1，T1 把 D 节点拆分成 H、I 两个节点，同时把 41 转移到 I 节点，之后 CPU 交还给 T2，T2 到 H 节点就找不到 41，如下图所示：

![](/files/-L_DVF0MYiTsWD9iqtiV)

如何解决该问题？由于 B+ Tree 是树状结构，有明确的访问顺序，因此很容易想到沿着访问路径加锁的方法，即 Latch Crabbing/Coupling

### Latch Crabbing/Coupling

Latch Crabbing 的基本思想如下：

* 获取 parent 的 latch
* 获取 child 的 latch
* 如果***安全***，则可以释放 parent 的 latch

这里的“安全”指的是，当发生更新操作时，该节点不会发生 split 或 merge 的操作，即：

* 在插入元素时，节点未满
* 在删除元素时，节点超过半满

#### Search

从 root 往下，不断地：

* 获取 child 的 read latch
* 释放 parent 的 read latch

举例如下：Search 38

![](/files/-L_DYoD433UgUgaQbHwe)

![](/files/-L_DYsvqHdQzoya7pjj1)

![](/files/-L_DYxTzgPQOGenqWcFR)

![](/files/-L_DZ13egH9rrJkRhgGu)

![](/files/-L_DZ73JZvGSVmq2NryE)

#### Insert/Delete

从 root 往下，按照需要获取 write latch，一旦获取了 child 的 write latch，检查它是否安全，如果安全，则释放之前获取的所有 write latch。

例 1 如下：Delete 38

![](/files/-L_DZPQao5pTG0V-rkal)

![](/files/-L_DZUFCC557WpQ0xiOs)

![](/files/-L_DZaTDO794EM7WX-sx)

![](/files/-L_DZiCVUCje9HjTO-fP)

![](/files/-L_DZoWD0V2eGPVpBQCR)

![](/files/-L_D_IsLUJovGgB_28fo)

例 2 如下：Insert 45

![](/files/-L_D_cGh7PFgdsPWVEKy)

![](/files/-L_D_kHAAdtorfsq4gNM)

![](/files/-L_D_oWAJbDbHHA36cm0)

![](/files/-L_D_uzqhJMGdNgJXC4k)

![](/files/-L_D_zcsb1G_n-lL0UWF)

例 3：Insert 25

![](/files/-L_DaA7Ey04vDM9NceNx)

![](/files/-L_DaEwuxQ3apU-rSJXS)

![](/files/-L_DaJZBHE-13w2RvuyS)

![](/files/-L_DaNg_9tRVu7tENaU_)

![](/files/-L_DaSsennVpIB5Mm5s0)

![](/files/-L_DaZ8reSqVj3Do_R7h)

![](/files/-L_Dacx04-MRg935Naf2)

### Better Latching Algorithm

在实际应用中：

* 更新操作每次都需要在路径上获取 write latch 容易成为系统并发瓶颈
* 通常 Node 的大小为一个 page，可以存储很多 keys，因此更新操作的出现频率不算高

我们能否在 Latch Crabbing 的基础上做得更好？

可以采用类似乐观锁的思想，假设 leaf node 是安全（更新操作仅会引起 leaf node 的变化）的，在查询路径上一路获取、释放 read latch，到达 leaf node 时，若操作不会引起 split/merge 发生，则只需要在 leaf node 上获取 write latch 然后更新数据，释放 write latch 即可；若操作会引起 split/merge 发生，则重新执行一遍，此时在查询路径上一路获取、释放 write latch，即 Latch Crabbing 原始方案。

举例：Delete 38

![](/files/-L_GGE6wjo3z5rM-T7_4)

![](/files/-L_GGIDQ9aPavzNUSBhh)

![](/files/-L_GGMcQDKDZ-az_Alci)

![](/files/-L_GGQY0sv9c7JaZt0pr)

![](/files/-L_GGV2EJzM8dLCC9um6)

![](/files/-L_GGaH98oZ83IAgp3Dz)

![](/files/-L_GGfpxVWwbR7UUOufR)

#### Better Latching Algorithm 小结

* Search：与 Latch Crabbing 相同
* Insert/Delete:
  * 使用与 Search 相同的方式在查询路径上获取、释放 latch，在 leaf node 上获取 write latch
  * 如果 leaf node 不安全，可能会引起其它节点的变动，则使用 Latch Crabbing 的策略再执行一遍

该方法乐观地假设整个操作只会引起 leaf node 的变化，若假设错误，则使用 Latch Crabbing 的原始方案。

### Horizontal Scan

之前的分析中我们仅仅关注了从上到下的访问模式，而没有考虑到左右方向的访问模式，在 range query 中，常常需要横向访问相邻的 nodes。

例1：T1: Find Keys < 4

![](/files/-L_GIK6BxfxYVy1jWIfS)

![](/files/-L_GINosGE2fwYVU3QsL)

![](/files/-L_GIS46FdXYaOULCDAa)

![](/files/-L_GIXAbBqVKR6-yd52X)

![](/files/-L_GI_qIgogjtJBIC-EX)

如果此时刚好有另一个线程作相反方向的访问：T2: Find Keys > 1：

![](/files/-L_GJ0xlbj6jjhobhDKx)

![](/files/-L_GJ4_GP48w_PRh9G0L)

![](/files/-L_GJBlzSLrXOOYpiiF9)

![](/files/-L_GJFjSEnpVJe8EgtGu)

由于 read latch 允许被多次获取，因此并发读的情况不会产生负面影响。

例 2：T1: Delete 4，T2: Find Keys > 1

![](/files/-L_GJ_Q66CTHqFc4eG5K)

![](/files/-L_GJeEmwL75d9UwCVyU)

![](/files/-L_GJhn4apCKL3f4uFu9)

![](/files/-L_GJmfevcs4JFNYJ_8i)

当遇到横向扫描无法获取下一个节点的 latch 时，该线程将释放 latch 后自杀。这种策略逻辑简单，尽管有理论上的优化空间，但在实践中是常见的避免死锁的方式。

### Delayed Parent Updates

从上文中，我们可以观察到：每当 leaf node 溢出时，我们都需要更新至少 3 个节点：

* 即将被拆分的 leaf node
* 新的 leaf node
* parent node

修改的成本较高，因此 B-link Tree 提出了一种优化策略：每当 leaf node 溢出时，只是标记一下而暂时不更新 parent node，等下一次有别的线程获取 parnet node 的 write latch 时，一并修改。

举例如下：Insert 25

![](/files/-L_GLhe5dLXhoZDVLrbG)

![](/files/-L_GLlSaNU9iAtS-vXYc)

![](/files/-L_GLpJnUC_UAaIpc4XF)

![](/files/-L_GLtMpUl7HSTTCPcys)

![](/files/-L_GLxXjX0uv5enS6YVJ)

![](/files/-L_GM0YkZQzKWPpIhEjQ)

![](/files/-L_GM586KEYFngym07la)

Delayed Parent Updates 仅用在 insert 操作中。

## Conclusion

让一个数据结构具备并发安全的特点知难行易，尽管本节只是介绍 B+ Tree 上的相关技术，但这些技术同样适用于其他数据结构。

## 参考

[slides](https://15445.courses.cs.cmu.edu/fall2018/slides/09-indexconcurrency.pdf)