# 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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zhenghe.gitbook.io/open-courses/cmu-15-445-645-database-systems/index-concurrency-control.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.