526互联

Lecture #09: Index Concurrency Control

发布时间 2023-04-12 18:00:36作者: Angelia-Wang

review：

上几节讲了 hash table、B+Tree、Radix Tree 及其他树形结构。我们假设这些数据结构只能被一个线程访问，且在同一时间只有一个线程能对该数据结构进行读写数据。

然而大部分DBMS在实际场景中需要允许多线程安全地访问数据结构，以充分利用CPU多核以及隐藏磁盘I/O延时。（有DBMS只支持单线程，如Redis）。

1 Index Concurrency Control

并发控制协议，是DBMS使用以保证并发操作正确性的方法。

并发控制协议正确性标准有：

  • Logical Correctness，线程可以读它期望读到的值，如在一个 transaction 中，一个线程在写完一个值之后，再读它，应该是它之前写的值。
  • Physical Correctness，共享对象的内部表示是安全的，如共享对象内部指针不能指向非法物理位置。

本讲着重于Physical Correctness，Logical Correctness后面会讲。

2 Locks vs. Latches

1️⃣ Locks：

Locks 不同于 OS 中的锁，数据库中的 lock是一个 higher-level 的，概念上的。DBMS 使用 lock 避免不同 transactions 的竞争，如对 tuples、tables、databases 的 lock。Transactions 会在它整个生命周期持有 lock。lock 可以回滚。

2️⃣ Latches：

Latches是一个 low-level 的保护原语，DBMS 将 latch 用于其内部数据结构中的临界区，如 hash table 等。Latch 只在操作执行的时候被持有。latch 不支持回滚。

lock 专指的是事务语义层面的锁，例如两阶段提交锁。

latch 指的是程序层面对代码的锁保护，主要为了线程安全，例如常见的 mutex 等。

image-20230412163444885

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

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

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

3 Latch Implementations

用来实现latch的基本原理是通过现代 CPU 提供的 atomic compare-and-swap (CAS) 指令。借此，一个线程可以检查一个内存位置的内容，看它是否用某个值。如果有，则CPU将用一个新的值来交换旧的值，否则，该内存位置将保持不被修改。

在DBMS 实现 latch 用几种方法：每种都有不同的权衡。工程复杂性和运行时性能都有不同权衡。这些 test-and-set 是以原子方式进行的。

Blocking OS Mutex

  • Latch 的一个可能的实现是 OS 的内置互斥机制。Linux 提供了 Futex（快速用户控件互斥）。由 (1) 用户空间的自旋latch 和 (2) OS 级互斥组成。如果 DBMS 能够获得用户空间的 latch，那么 latch 就会被设置。在 DBMS 看来，它是一个单一的 latch，尽管内部其实有 2 个。如果 DBMS 不能获取用户空间的 latch，则会进入内核并试图获取更加昂贵的mutex。如果又不能获得，则线程会通知 OS 它在 mutex 被阻塞，然后取消调度。
  • OS mutex 在 DBMS 中，一般是不好的决定。因为它有 OS 控制，而且开销大。
    • 例子：std::mutex
    • 优点：使用简单
    • 缺点：消耗大。不可扩展。因为OS的调度。

Test-and-Set Spin Latch (TAS)

  • 自旋锁比 OS mutex 更有效。因为它被 DBMS 控制。自旋锁基本上是线程试图更新的内存位置（比如将一个 bool 设为 true）。一个线程执行 CAS 来尝试更新内存位置。DBMS 可以控制如果不能获得 latch 会发生什么。比如可以选择尝试再次尝试（while 循环）或允许操作系统取消调度。所以这种方式给了 DBMS 更多控制权。
    • 例子：std::atomic<T>
    • 优点：上锁解锁更高效。单一指令即可。
    • 缺点：不具有扩展性，也不适合缓存。因为在多线程中，CAS 指令将在不同指令多次执行。浪费的指令会在高竞争环境中堆积起来。比较浪费 CPU。（一直停在 while 循环上）

Reader-Writer Latches

  • Mutex 和自旋锁不区分读写。DBMS 需要一种允许并发读取的方法，所以如果用程序大量读取，就会有更好的性能。因为读可以共享，而不是等待。
  • 读写锁允许 latch 以读或者写的模式保持。可以跟踪有多少线程持有该 latch，并在每种模式下等待获取 latch。读写锁使用前两种 latch 现的一种作为基础，并用额外的逻辑来处理读写队列。不同的 DBMS 可以有不同的策略来处理。
    • 例子：std::shared_mutex
    • 优点：并发读取
    • 缺点：必须维护读写队列。以防饥饿。所以内存开销更大。

总结 latch 的实现方式：

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

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

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

4 Hash Table Latching

了解过 latch 的概念，再来看看在哈希表中如何保证线程安全的。

静态哈希表比较好加锁，如开放地址哈希，进行查找的线程都是从上到下查找，从上到下地获取 slot 的锁，不会出现死锁的情况。如果要调整哈希表的大小，则对整个哈希表上把大锁就行。

动态哈希方法(如可扩展哈希)加锁更复杂，因为有更多的共享状态，更难进行并发控制。一般有两种加锁方式：

  • Page Latches：对每个 page 上读写锁，线程访问页之前上锁，但会降低一些并行性。
  • Slot Latches：对每个 slot 上读写锁，增加了并行性，但是也增加了内存和计算开销 (因为线程要为访问的每个 slot 都获取锁)。可以使用单模式锁（即自旋锁）来减少内存和计算开销，代价是降低了并行性。

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

image-20230412171913774

对 slot 加锁，减小了锁的粒度。多个线程可以同时访问一个 page，但是在访问具体的 slot 时仍然需要加锁。

image-20230412171946534

5 B+Tree Latching

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

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

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

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

image-20230412172236221

如果此时删除了 44 之后，触发了叶子节点的 borrow，并且此时有另一个线程 T2 需要读取节点 41。在没有任何并发安全的保证下，尽管节点 41 是存在的，但是 T2 有可能根本拿不到数据，因为此时 T1 有可能因为 borrow，而将节点 41 移动开了。这样就造成了数据的不一致，需要并发安全来保证。

image-20230412172423783

Latch Crabbing & Coupling

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

Latch Crabing 的基本思想：线程在遍历时，先获取 parent 的 latch，再获取 child 的 latch，若 child "safe"，则释放 parent 的 latch。

这里 safe 的定义是：节点在进行操作后，不会触发 split 或 merge，从而影响父节点。

  • 插入元素时，结点未满；
  • 删除元素时，结点超过半满；
  • 搜索元素时，所有节点都为 safe node。

Basic Latch Crabbing Protocol:

  • Search：从根开始往下，重复获取 child 结点的读锁，并释放父结点的读锁。

  • Insert/Delete：从根开始往下，对 child 结点加写锁，进一步判断 child 是否安全，若安全则释放所有祖先结点的写锁。

Improved Lock Crabbing Protocol:

基本的Latch Crabbing算法的问题是：事务在每次插入/删除操作的时候总是获得根上的写锁，这限制了并行性。
这其实是一种悲观锁的策略，对根节点加写锁，是因为每次都假设我们的操作会涉及到 split/merge，但实际上，大多数情况下都不会有 split/merge 操作。所以我们可以用乐观锁的策略来优化整个加锁流程。

  • Search：仍然会加读锁，这和前面的方案没有变化。
  • Insert/Delete：搜索 root 到leaf 的过程中加读锁，最后对 leaf 加写锁。然后判断叶结点是否安全。若安全则操作成功；若不安全则释放写锁，以悲观锁的方案重试这个操作，即对所有的节点加写锁。

6 Leaf Node Scans

之前两个算法都是从上到下的。这意味着线程只能从低于当前结点中获取锁存器。如果想要的锁存器不能用，则线程必须等待，直到它变得可用。鉴于此，永远不可能出现死锁

然而，叶子结点扫描很容易出现死锁，因为可能我们有线程从两个方向同时获得独占锁(写锁)。Index latch 不支持死锁检测和预防。

? T1 需要删除 4，T2 需要扫描数据，此时他们都在各自的叶子节点上加上了锁，T1 是写锁，T2 是读锁。

image-20230412174029019

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

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

经常采用的方法是第一种，即叶结点的兄弟结点的锁采用 “无等待模式”，若线程试图获取叶结点的兄弟结点的锁，但锁不可用，则迅速中止操作 (释放它所持有的所有锁)，并重新启动操作。

7 Delayed Parent Updates

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

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

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

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

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

在实践中使用更多的 Blink Tree 是对并发支持更好的 B+ 树结构，其专门对并发访问做了优化，

参考链接

官方 PPT 及讲义：

https://15445.courses.cs.cmu.edu/fall2019/schedule.html

参考笔记：

CMU 15445 学习笔记—8 Index Concurrency Control

CMU15445-Lec09 Index Concurrency Control

Index Concurrency Control