前面讲到的索引数据结构，例如哈希表、B+ 树，我们都假设它是在单线程环境下运行的。

但实际上数据库中的行为大多是并发执行的，我们需要利用现代多核 CPU 的优势，避免频繁查询磁盘导致系统响应延迟。所以保证在多线程环境下索引访问的正确性，就十分的重要了。

Lock & Latch

首先我们在数据库的上下文中来了解一下关于 lock 和 latch 的概念。

lock 专指的是事务语义层面的锁，例如两阶段提交锁，而 latch 指的是程序层面对代码的锁保护，主要为了线程安全，例如常见的 mutex 等。

这两者的大致区别如下图中所示：

本节主要专注于 latch 相关的概念，事务层面的 lock 会在后续进行介绍。

latch 的语义比较类似我们在编程语言中见到的各种锁，它有两种模式：读和写。

• 读模式
  • 多个线程可以同时访问一个对象而不阻塞
  • 如果一个线程占据了读锁，另一个线程还可以继续申请读锁
• 写模式
  • 同一时刻只能有一个线程访问对象
  • 如果一个线程已经有写锁了，则另一个线程不能申请读锁，也不能申请写锁

latch 的实现方式有多种：

一是可以使用互斥原语，例如大多数编程语言中都内置了的锁，C 语言中的 pthread_mutex，C++ 中的 std::mutex，Go 中的 Mutex。

二是使用 CAS 指令，这主要依赖于 CPU 的 cas 原子操作，这种方式基于硬件平台的汇编指令，效率很高。大多数语言中的 atomic 都依赖于 cas 实现。

三是利用上述的两种方式，将锁的粒度减小，可以分离为读锁和写锁，分别锁定不同的对象，减少获取锁的冲突。

Hash Table Latching

了解过 latch 的概念，再来看看在哈希表中如何保证线程安全的。假设哈希表是一个 Page table，当多个线程访问到其中某个 page 的时候，我们可以对这个 page 加锁，或者对 page 中的单个 solt 加锁。

首先是对 page 加锁，理解起来也比较简单，例如下面的例子，一个线程获取到锁，访问到 page 之后，如果另一个线程同时需要加写锁，那么就会阻塞。

然后是对 page 中的空闲空间 slot 加锁，这种方式将锁的粒度减小了。多个线程可以同时访问一个 page，但是在访问具体的 slot 时仍然需要加锁。

B+ Tree Latching

哈希表中的加锁操作相对简单容易理解，B+ 树中的线程安全保证就稍微麻烦点了，需要考虑类似下面这样的问题：

• 多个线程在同一时刻去修改 B+ Tree 中的同一个节点
• 一个线程在遍历 B+ 树，而另一个线程在执行 split/merge 操作

例如下面的例子，描述了在 B+ 树中读写线程安全的问题。

首先，一个线程 T1 要删除 B+ 树中的节点 44，它会从根节点开始查找，并从这个链路找到位于叶子节点的 44，然后将其删除。

如果此时删除了 44 之后，触发了叶子节点的分裂，并且此时有另一个线程 T2 需要读取节点 41。

在没有任何并发安全的保证下，尽管节点 41 是存在的，但是 T2 有可能根本拿不到数据，因为此时 T1 有可能因为分裂节点，而将节点 41 移动开了。

这样就造成了数据的不一致，需要并发安全来保证。

Latch Crabbing & Coupling

B+ 树中将保证线程安全的加锁方式统一叫做 latch crabbing/coupling。

其基本思路是对需要访问的节点及其父节点都加锁，同时为了减少锁定父节点带来的开销，在确定父节点是“安全”的之后，可以将父节点的锁释放掉。

这里的父节点的“安全”指的是，在本次操作中，确定不会发生节点的分裂或合并，也就是说父节点的状态不会发生变更。

当在 B+ 树上 read 时，从根节点开始向下搜寻，首先对扫描到的节点加读锁，向下一层时，将父节点的锁直接释放，这里能直接释放的原因是整个操作是只读的，不会变更 B+ 树节点的状态。

当需要对 B+ 树更新（write/delete）时，同样从根节点进行搜寻，并且在经过的节点上加写锁，并进一步判断，如果当前节点是“安全”的，那么释放所有父级节点的锁。

Better Latching Algorithm

上面提到的 latch crabbing 的方式简单直观，但是其问题也显而易见，那就是对 B+ 树更新的时候，每次都需要先对根节点加写锁，这对 B+ 树的并发性能造成了很大的影响。

这其实是一种悲观锁的策略，对根节点加写锁，是因为每次都假设我们的操作会涉及到 split/merge，但实际上，大多数情况下都不会有 split/merge 操作。

所以我们可以用乐观锁的策略来优化整个加锁流程。

首先读仍然会加读锁，这和前面的方案没有变化。

在更新 B+ 树的时候，搜索根节点到叶子节点的过程中加读锁，只是最后的叶子节点时再对其加写锁。并且判断，此操作会不会发生 split/merge 操作。

如果不会，那么操作成功完成，如果会的话，那么则会放弃这个操作，并且以悲观锁的方案重试这个操作，即对所有的节点加写锁。

Leaf Node Scan

前面提到的两种加锁方式都是从上到下进行节点扫描，然后在多个节点上加锁，这样多个线程实际上只能同时获取到一个节点上的锁，其他的线程只能等待。

如果我们进行叶子节点的扫描，这时候应该怎么加锁呢？

首先是 read-only 的操作，看下面的这个例子，有两个线程都去读取数据，并且在各自扫描的叶子节点都加了读锁。

此时 T1 需要扫描 Page B，T2 需要扫描 Page C，但由于他们都是加的读锁，可以共享，T1 能获取到 Page B 的读锁，T2 能获取到 Page C 的读锁，所以这里并不会造成死锁。

再看下 read-write 的操作，下图中 T1 需要删除 4，T2 需要扫描数据，此时他们都在各自的叶子节点上加上了锁，T1 是写锁，T2 是读锁。

此时两个线程都无法获取到另一个 page 的锁，T2 的办法有以下几种：

• T2 立刻主动释放锁，并且重头开始
• T2 让 T1 放弃锁，T2 获得了 Page C 的锁，让 T1 重新开始
• T2 等待一段时间，但是为了避免死锁，应该在 timeout 之后释放掉锁重头开始

Delayed Parent Updates

在 B+ 树中，当有叶子节点分裂的时候，涉及到这几个点：

• 叶子节点本身分裂
• 创建新的叶子节点
• 父节点更新

在 Blink Tree 当中，有一种针对此的优化，就是将更新父节点的操作延迟。

当对 B+ 树进行更新的时候，如果判断到叶子节点需要分裂，那么并不会从头加写锁，而是延迟对父节点的更新。

实际上，前面提到的这种 B+ 树并发控制的方案，只是一种很初级的实现，锁的粒度仍然很大。

在实践中使用更多的 Blink Tree 是对并发支持更好的 B+ 树结构，其专门对并发访问做了优化，后续有空的话，可以专门再聊聊 Blink Tree。

后续的文章，将会开始讲解执行器相关的内容。