CMU 15-445/645-笔记-09-多线程索引并发控制
## 课程目标
课程目标图
https://wx2.sinaimg.cn/large/dfe0c359gy1h6jba8gefxj20me0cctab.jpg
Observation 图
https://wx3.sinaimg.cn/large/dfe0c359gy1h6jba8xm70j20ow0g3n1l.jpg
主要是为了讨论如何用多线程去访问数据结构，并且保证线程安全
VoltDB 和 redis 是使用单线程来访问的，但他们依然可以获得良好的性能
VoltDB 虽然是一个多线程引擎，但它是以某种方式将数据库分割，每个 B+ Tree 只能由一条单线程来访问
因此它们也不会使用 latch 锁
但缺点是拓展到多核或者多台机器上时情况就会变得复杂
## 并发控制(Concurrency Control)
并发控制图
https://wx3.sinaimg.cn/large/dfe0c359gy1h6jba95ug4j20mc0de422.jpg
强制所有访问数据结构的线程都使用某种协议或者某种方式来解决并发访问的问题(主要是为了保护数据结构)
并发控制不仅仅用于某个数据结构，它同时也可以用在 tuple/index/page table/buffer pool 等场景
并发控制主要关注 2 种正确性类型(Correctness Type)
1. 逻辑正确性(Logical Correctness): 所见即所期望得到的
2. 物理正确性(Physical Correctness): 比如在多线程并发访问一个 B+ Tree 的时候，我们经常在遍历它的时候用到指针，如何保证在使用这个指针的时候，这个指针指向的那个数据没有被修改过呢(万一这个指针指向的是一个无效的位置那么就糟糕了)?
## Locks Vs. Latches
Locks Vs. Latches 图
https://wx3.sinaimg.cn/large/dfe0c359gy1h6jba9cqk3j20n60enq61.jpg
再谈 Locks 和 Latches 的区别
1. Locks 是一种更高层面的概念，它保护了数据库中的逻辑内容(一个 tuple、一个 tuple 的集合、一张表、一个数据库)，当同一时间有其他事务在运行时，我们会使用这些 Locks 来保护这些逻辑内容。我们会在整个事务的执行期间持有这些 Locks(虽然这种方式并不完全正确)，这个时候如果要将这些逻辑内容进行回滚，而在同一时间又有其他事务在运行，那么这些逻辑内容可能会遭到修改，所以需要用 Locks 来保护。
2. Latches 是一种低级层面的概念，对于 OS 来讲，它会把所谓的 Latches 看作 Locks/Mutex，Latches 负责保护的是数据库系统中的关键部分，即 Latches 可以保护内部数据结构免受其他线程对该数据结构或对象在同一时刻进行读写所带来的问题。我们只会在一小段时间内持有 Latches，并且只会在对关键部分执行所需要的操作时持有这些 Latches。执行这些操作时，不需要去回滚做任何的修改，因为 Latches 要保护的操作都是原子性的。
```
操作开始 操作结束
↓---> 获取 Latch ---> 修改数据 ---> 释放 Latch --->↑
```
如果没有这些 Latches，也没法进行上述的修改操作，那也没必要进行回滚了
一些其他的区别
https://wx2.sinaimg.cn/large/dfe0c359gy1h6jba9kaulj20sf0e8wiw.jpg
应对死锁问题时，我们会依赖某些外部协调器(Lock 管理器、事务管理器)来解决
Latches 只有 2 种模式: 读和写
## Latch 模式
1. 读模式: 允许多线程在同一时间读取同一个对象
2. 写模式: 一次只允许一条线程能持有这个 Latch
## Latch 实现
### 使用 Blocking OS Mutex
Blocking OS mutex 的原理是，它使用了 Futex 即 Fast Userspace Mutex，它是在 Userspace 中的，也就是某个进程的地址空间里面，它会占用一点内存，比如 1 bit 或者 1 byte 的大小，通过这个内存的这个位置来尝试进行一次 CAS 操作，用以获取这个 Latch。但如果你没能获取到它，那么它就会退一步使用速度更慢的的 Mutex(注意此时的 mutex 是在 Kernel space 中的)。为什么? 因为 OS 此时知道你没能拿到这个 Latch，它就会将你此刻的操作放入一个等待队列中，等待调度器调度。
> CAS 即 Compare And Swap
> Futex 是一个 spin latch，也就是自旋锁
所以要尽可能地避免使用 OS 层面的 mutex
### 使用 Test-and-Set Spin Latch
第二种方式就是使用一个 TAS(Test-And-Set) 的 spin latch
这种方式会很快，因为现代 CPU 中有一个指令，这个指令可以在一个内存地址上进行单次 CAS 操作，即检查这个内存地址上的值是否和期待的值相等，如果相等，那么就允许将它原来的值变为新的值(就不用自己写 if else 了，这条指令就帮你做了这件事)
上图中，如果想要获取到这个 latch，就必须使用 `while` 循环，如果 `latch.test_and_set(...)` 为 `true`，则证明拿到了这个 latch，需要跳出循环
如果没拿到则需要一直 spin 等待，一直执行 `latch.test_and_set(...)` 直到能拿到 latch
但缺点是 CPU 的使用率会上升
虽然效果跟 OS 中的 Mutex 差不多，但是 OS 中的 Mutex 并不是一直无限循环做 TAS
可以通过 TAS 的次数来判断要不要退出循环，这是调优的方式之一
主要是如果一个 spin latch 等待的时间过长了，要采取什么样的方式去让其他线程获得机会?(直接把当前线程 yeild 让其他线程先执行，或者是直接中断掉当前线程)
### 使用 Reader-Writer Latch
简而言之就是在基础的 latch 之上构建出 spin latch 或者 POSIX mutex 这种东西，然后通过管理不同的队列来跟踪不同类型的 latch，看看有哪些线程在等待获取它们
读写 latch 的工作原理如下
首先无论是 reader latch 还是 writer latch，它们内部都会使用到一些计数器
1. 一个计数器 1 表示持有该模式 latch 的线程数量(图中的芯片 icon)
2. 一个计数器 2 表示等待该模式 latch 的线程数量(图中的沙漏 icon)
如果此时有一个 read 线程，它想要获取 read latch
此时没有线程持有这个 read latch，也没有人正在等待获取它，所以此时可以把这个 read latch 分发给这个线程 ，然后更新下计数器 1，表示此时有一个线程持有这个 read latch
如果此时又来一个线程，这个线程也想去获取一个 read latch
因为 read latch 任何线程都可以共享，所以此时只需要更新计数器 1 即可
如果此时又来一个 write 线程
那么它必须停下来，等待获取 write latch，因为 read latch 已经被其他线程持有了。这里只需要更新下 write latch 的计数器 2，表示有一个线程正在等待获取这个 write latch
如果此时又来了一个 read 线程，并且它想获取 read latch，此时会发生什么呢?
这取决于使用的策略。此时的情况是什么呢?
read latch 已经被上面几个线程拿到了，并且其他线程也在等待获取它，如果此时要分发 read latch 给这个新来的 read 线程，那么就会导致 starvation(饥饿)，因为右边的 write 线程永远拿不到这个 write latch 了，所以此时只能将这个新来的 read 线程停下来，并将它添加到计数器的等待队列中去
最终，当之前的 2 个 read 线程释放了它们获取到的 read latch 之后，右边的 write 线程就会拿到它的 write latch
这里所说的策略是指什么呢?
如果有这么一种数据结构，它不会涉及到太多的写入操作。而由于这些写入操作非常重要，此时就会赋予 write 线程一个更高的优先级，也就是上面出现的那个情况
## Hash Table Latching
使用 Hash Table Latching 来支持并发访问是非常容易的，因为多个线程间通过使用 hash table 来进行交互的方式是有限的(有限，意味着有规则，有规则，意味着不会出现太多的意外情况)
1. 所有线程只会朝 hash table 的一个方向去做访问，并且在同一时间只会访问到一个 hash table 中的 page/slot
2. 不会发生死锁
例如，在一个静态的 hash table 中(暂且忽略掉动态 hash table，因为情况更加复杂)，当你要插入某个 key 时，你需要对他进行一次 hash，然后跳到这个 hash table 的某个 slot 处，这个时候线程可以按照顺序往下扫描 hash table，以此来找到它想要找到的东西。对于其他线程来说也是一样的，他们也会自上而下的对这个 hash table 进行扫描，扫描到底部如果找不到，那么他们会从这个 hash table 的起始位置开始继续扫描，循环反复(可以将这个 hash table 想象成一个环形的 buffer)
由于线程访问 hash table 的顺序一致，那么对于持有 latch 的线程来说，每个线程都不会碰到并且拥有来自反方向的线程的 latch，那么也就不会发生死锁问题
但是如果要重新对 hash table 的 size 进行调整的话，我们通常会在 header page 上加一个全局的 latch，这主要是为了避免在对 hash table 的 size 的调整结束之前，有其他线程对当前的 hash table 进行了读写操作(但如果一开始 hash table 的 size 很大，这种情况就会变得少见)
hash table 的 latching 有 2 种粒度
1. Page Latches(粒度较大)
2. Slot Latches(粒度较小)
如果使用 Page Latches，那么用的 latch 就会少些，毕竟一个 latch 对应一个 page，缺点是线程访问的并行性会降低(如果有 2 个线程操作的 slot 是在同一个 page 中，那它们俩也就没法在同一时间执行任务了)
如果使用的是 Slot Latches，那么用的 latch 就会多一些，毕竟一个 latch 对应一个 slot，并行性虽然提升了，但是在线程进行访问时，开销会变大(因为这么多的 latches 占的空间大，占的计算资源也多)
### Page Latches 原理
假设现在有 3 个简单的 page table，每个 page table 里面都有 2 个 slot
第一个线程要寻找 D，通过对 D 进行 hash 处理，它落到下图中 A 的位置
虽然不知道这个位置里面的东西是不是这个线程真的想要的，但是还是要在这个线程访问到里面的内容之前，先拿到这个 page 的 read latch
一旦拿到这个 latch，就开始利用游标查找
假设现在又来了一个线程，这个线程想要插入 E，通过对 E 进行 hash 处理，它落到下图中 C 的位置
此时这个线程还可以进行插入操作吗? 当然不行，在这之前这个线程需要拿到这个 page table 上的 write latch，因为它不知道 C 这个位置对应的内容是否是满的，它也需要去做扫描操作。然而此时它所拿到的 write latch 跟左边那个线程拿到的 read latch 并不匹配，所以右边这个线程需要停下来等待
所以此时左边的线程继续往下扫描
继续看下一个 page table
> 注意: 如果要知道要查看的 page 里面包含了什么，就从 hash table 的 header 中去获取查看信息，这个 header 会给你要查看的 page 有哪些。从逻辑上来讲，page table 是按照顺序排列的，比如下图中的 page 0、page 1、page 2，所以通过 header 就可以知道 hash table 中 page2 对应的位置
左边的线程为了能从 page 1 遍历到 page 2，就不需要持有 page 1 的 latch 了(假设此时的 hash table 是静态的，size 不会变，对应的 page 1 2 3 的地址都是一样的)
在跳到 page 2 之前，立即释放掉 page 1 的 latch，然后获取 page 2 的 latch
> 注意: 不能去对 latch 的模式进行升级，即将 read latch 升级成 write latch，只能是将当前持有的 latch 释放掉，然后去获取另一个不同模式的 latch
现在，右边的线程可以去拿 page 1 的 write latch 了
此时 C 的位置并不是右边线程所期望的，所以它继续往下找来到 page 2，并且拿到 write latch(此时左边线程的查找工作已经做完)
看到 D 的位置已满，就插入到 D 下面
### Slot Latches 原理
对于线程 T1，它将访问到 page 1 上的 A 位置，并获取到了 A 位置上的 read latch
此时对于线程 T2，它将访问到 page 1 上的 C 位置，并获取到了 C 位置上的 write latch
当 T1 再次执行任务时，它会试着去看 C 位置这里，此时它必须停下来，因为它没拿到 C 位置上的 latch
所以 T2 可以继续往下走，它释放了 C 位置的 latch，然后拿到了 page 2 上 D 位置的 latch
现在 T1 可以往下走了，它去拿 C 位置的 latch
接着，T1 又得停下来，因为它没法拿到 D 位置的 latch
直到 T2 完成插入操作，T1 才可以继续处理
### 小结
这里的特点还是不能有死锁，因为在上述例子中，所有的线程的执行操作的方向都是一致的，即从上往下，因为没有任何一个线程是反过来的，这样就能保证数据一致性
## B+ Tree 并发控制
如果有 2 条线程同时对同一个 B+ Tree 的某个节点进行读写操作，那么有可能其中一条线程经过一系列操作之后，这个节点被 merge/split 了，然后另一条线程在对当前的节点做操作时可能就会访问到一个无效的 地址/值
### B+ Tree 多线程访问会出现的问题
现在有一个 B+ Tree 的数据如下图
假设现在要有一个线程 T1 要删除叶子节点上的 44
第一个线程会先从根节点 A 开始深度向下遍历，直到遍历到 44 这个节点
此时将 44 节点删除
现在之前的 44 这个对应的节点是处于半满(half-full)的情况，所以此时就需要重新平衡这个 B+ Tree，但在这个例子中不需要做 split 操作，而是从兄弟节点中复制一个 key 到这个空的节点中去。但在执行重新平衡操作之前，OS 会将这个要删除的线程交换出去，所以这个线程就必须停下来等待
如果此时有另一个线程 T2 要查找 41，此时线程会遍历直到到 D 这个节点
此时，线程 T2 会在这里停下来，OS 会切换回线程 T1，然后 T1 会将 41 移动到之前的那个空节点上
然后当 T2 再次可以执行时，它到了 H 这个节点上，就会发现 41 已经不在这里了
那么如何解决这种情况呢?
### Latch Crabbing/Coupling
本质上还是使用 latches 来做一个数据访问保护的操作
它的基本工作原理是，我们在对某个节点做操作时，这个节点上必须挂有一个 读/写 latch，在访问这个节点的 child 节点之前，需要先拿到这个节点的 child 节点的上的 latch，以及下一个需要访问到的节点的 latch
而当真正访问到了这个节点的 child 节点时，就需要对它里面的内容进行判断: 我访问到的这个节点是否安全?如果安全，那么就将这个节点的上的 latch 释放掉
> 就像螃蟹走路，一条腿迈过另一条腿
那么如何定义一个节点是否安全?
就是当你需要修改这个节点时，这个节点没必要做一些 merge/split 操作
并且
1. 如果要做 insert 操作，那么该节点必须要有足够的空间去容纳要 insert 的 key(这样就不会发生 split)
2. 如果要做 delete 操作，那么该节点中元素的数量必须要超过该节点容量的一半(这样就不会发生 merge)
总之，基本原理如下图
> 注意在该例子中，所有的线程都是 从上往下 深度递归遍历的
### find 操作
比如要查找 38 这个 key ，每次向下遍历时要加一个 read latch，直到遍历到 B 这个节点
因为所做的都是只读操作，所以释放 A 节点处的 read latch 是安全的
继续往下扫描，到达 D 节点时释放掉 A 节点的 latch
最终到达 H 节点，释放掉 B 节点上的 latch
然后读 H 节点之前，释放掉 D 节点上的 latch
### delete 操作
比如要删除 38 这个 key ，每次向下遍历时要加一个 write latch，直到遍历到 B 这个节点
此时释放 A 节点的 latch 对于执行该删除操作的线程来说是安全的吗?
不是
因为在 B 节点处，只有一个 key 即 35，对于这个线程来说，它还不知道 B 节点下面的子节点的数据是一个什么情况，如果遍历到 D 节点执行删除操作，对于 B 节点它就必须进行 merge，那么这个 merge 的递归操作就会传播到 A 节点，A B 2 个节点都会有被修改的可能
所以这个时候得同时持有 A、B 节点的 write lacth
接着遍历到 D 节点，拿到 D 节点的 write latch，此时不管 D 节点下面的子节点发生了什么操作，删除了 key 38 并不会导致 C 节点和 D 节点的 merge。对于此时的 A B 节点来说修改可能不会存在
所以此时可以将 A B 节点的 write latch 释放掉
继续向下遍历到 H 节点，此时可以释放掉 D 节点的 write latch，因为 H 节点是全满(100% full)状态
执行删除操作，释放掉 latch，即完成整个过程
### insert 操作
比如要插入 45 这个 key ，每次向下遍历时要加一个 write latch，直到遍历到 B 这个节点
如果 D 节点要执行 split 操作，对于 B 节点来说它是有空间容纳的下一个 key 的，那么在递归 split 时 B 节点就不会发生 split，B 节点不会发生那么 A 节点也不会发生，所以此时释放掉 A 节点的 latch 是安全的
继续向下遍历，直到 D 节点
因为此时 D 节点是一个全满状态，此时如果在 D 节点下面做插入会不会导致 D 节点被 split ? 不清楚。D 节点如果被 split ，那么 B 节点也可能会被 split，所以此时需要持有 B 节点的 latch
继续向下遍历，直到 I 节点
因为 I 节点有足够空间支持插入一个 key，所以此时不需要对 I 节点进行 split 操作。在插入之前，可以释放掉 B D 节点处的 write latch，最后执行插入操作
### 小结
基本上就是用一个栈去存储这些 latch，当找到一个安全的节点时，用 stack 将它们一一 pop 出来
> 注意这里，不用在意 stack pop latch 的顺序。虽然将顺序对于最终的结果来说都一样，但从性能的角度，还是尽可能快的释放更上层节点的 latch 会比较好，因为更上层的节点的 latch 不再涉及更多的叶子节点(leaf node)，尽快释放更上层节点的 latch 主要是为了让下一个线程能更快的拿到这个 latch，从而减少阻塞访问的时间
### 性能问题
在 B+ Tree 中做插入和删除时，都需要做的第一件事就是使用独占模式的的 latch 或者是写模式的 latch 对根节点加锁
由于写模式下的 latch 具备独占性，为了访问这个 B+ Tree，每个线程都需要去获取这个 latch，但一次只能有一个线程能持有这个 latch，所以这对并行和并发的性能都会有影响
那么怎么做优化呢？那自然是在访问这个 B+ Tree 时，让这些线程都尽量能够持有这些个 latch
### 更好的 Latching 算法
> 1977 年的算法，由 2 个德国佬所写
首先，假设访问到的叶子节点是安全的，并且假设大部分的线程不需要对叶子节点进行 split/merge 操作
那么就有
1. 从根节点开始，在向下访问 B+ Tree 时，获取 read latch 而不是 write latch
2. 处理叶子节点时，获取 write latch
3. 如果此时该节点不需要 split/merge 操作，那么继续向下访问时只需要拿到 read latch 就行，此时也可以对该节点执行任意的修改
4. 如果此时该节点需要 split/merge 操作，并且此时如果操作犯错，那么操作在这里就直接 abort ，然后在根节点处重启该操作，在向下访问时获取 write latch
这就是乐观 latch 和 悲观 latch 算法
乐观的意思就是假设不会去做任何的 split/merge 操作，在这种情况下尽量用 read latch，那么性能就会很高
悲观的意思就是线程在访问时拿的全都是 write latch
在实际工作中，这种乐观的假设是非常安全的，因为很大概率上，在数据库系统中所作的大部分操作都是乐观锁这样的场景
### delete 操作
比如说要删除 38 这个 key
在根节点处不会去获取一个 write latch，在向下遍历时，拿到的始终是 read latch
直到遍历到 D 节点，此时获取到 H 节点的处的 write latch
删除掉 H 节点处的 38 这个 key，此时线程乐观的认为在 H 节点不需要做 split/merge 操作，那么只需要在执行删除这个操作时，再去获取 H 节点的 write latch
最后执行删除，释放 latch
### insert 操作
比如说要插入 25 这个 key
在根节点处不会去获取一个 write latch，在向下遍历时，拿到的始终是 read latch
直到遍历到 C 节点，此时获取到 F 节点处的 write latch
在 F 节点插入 25，就必须做一次 split 操作
所以就需要 abort 这次插入操作，回到根节点开始重新来一遍，当向下遍历时，拿的都是 write latch
### 小结
乐观锁的机制并不完美，没法保证所要做的遍历以及其他操作总是最小的。因为在大量插入的场景中，split/merge 的操作也是大量的，那么就需要不停的回到根节点处，向下遍历时一直拿 write latch
所以如果线程间的争抢率很高的话，乐观锁的假设就是错误的，那这样还不如一开始就用悲观锁呢
但还是那句话，看场景用哪种锁机制
### 如何遍历叶子节点
一个线程从 B+ Tree 中从上往下遍历，另一个线程在叶子节点中从左往右进行遍历，这 2 个线程还是有可能产生死锁的
那么如何解决呢?
### 单个线程遍历读叶子节点
比如通过线程 T1 来查找所有小于 4 的 key
首先在根节点处获取一个 read latch
然后向下遍历到 C 节点，获取到该节点处的 read latch，释放掉 A 节点处的 latch
然后从 C 节点开始，从右向左遍历这个叶子节点
为了能遍历到 B 节点，必须要拿到 B 节点的 read latch，然后释放掉 C 节点的 latch
### 多个线程遍历读叶子节点
此时有另一个线程 T2，它要查找所有大于 1 的 key
那么它们同时遍历，T1 到 C 节点，T2 到 B 节点
但到 T1 想要获取 B 节点上的 read latch，而 T2 想要获取 C 节点上的 read latch 时
它们都交替获得了对方的 read latch
最后完成遍历
最后再释放掉自己持有的 latch
这里不会产生死锁，因为 read latch 是共享的
### 多个线程遍历写叶子节点
如果线程 T1 想要删除 4 这个 key
在根节点处，T1 和 T2 拿到的始终是 read latch，只有在叶子节点时才会拿 write latch
继续遍历
T2 在叶子节点上继续遍历，它想要拿到 C 节点上的 read latch，但这是不可能拿到的，因为 t1 已经拿到了 C 节点处的 write latch
此时 T2 并不了解 T1 啥情况，为什么，因为在数据库系统的实现中，并不会使用一个全局的角度来告诉你另一个线程在做什么，线程间无权访问各自的信息
这里是可能会产生死锁的，因为 T1 也可以去尝试获取 B 节点处的 write latch，但由于 T2 不知道 T1 在干嘛，所以 T1 不可能释放掉 B 节点的 read latch，那么 T1 也就永远拿不到 B 节点的 write latch
那么怎么解决这个问题呢? 还是直接 abort 掉线程 T2 吧
然后让 T2 重新执行查询操作
### 小结
虽然通过 abort + 不停的重试能解决死锁问题，但这同样会导致 starvation 出现，或者浪费大量的 CPU 时钟周期来遍历叶子节点的数据
## 如何处理叶子节点数据 overflow
通常节点在发生 overflow 时会通过递归 split 的方式，将这个 overflow 的 key 插入到一个经过 B+ Tree 平衡操作之后的一个新的节点中去，但提出 B-link Tree 的人提出了一种优化方式，即
当某个子节点发生 overflow 情况时，延迟对父节点的更新操作，这样就不用再从根节点开始，并且拿着 write latch 一直往下遍历了，只需要更新这个 Tree 中的全局信息表中的一点点内容就可以了
当在某个时刻，有另一个线程在遍历这个 Tree 时，再去更新这个父节点即可
### insert 操作
比如线程 T1 要插入 25 这个 key，用乐观锁机制遍历
当遍历到 F 节点时，如果做插入操作，F 节点 overflow，需要 split
但是此时不需要再从根节点开始用获取 write latch 的方式进行遍历，而是进行插入操作
从 F 节点处弄一个 overflow 的节点出来放入 31，然后将 25 插入到 F 节点中
这样就不用为了更新 C 节点而再从根节点开始遍历了，这里就使用该 Tree 的一个小的全局表来处理这个 overflow 的信息
如果此时有个线程 T2 要查找 31 这个 key，它会按照遍历规则查到 F 指向的这个 overflow 节点
如果此时有个 T3 线程要插入 33，那么它会遍历到 C 节点处，拿到一个 write latch
然后完成 C 节点处内容的修改
最终拿到 overflow 节点的 write latch，并插入 33
这样就不需要重新遍历来进行操作了
## 总结
要确保所有线程始终沿着一个方向遍历数据结构，这样就可以避免死锁
