索引数据结构并发控制。
Latches Overview
Latches Mode
闩锁（latch）有两种模式：简单来说就是读模式允许多个线程读，写模式允许唯一线程写。
- Read：
- 多个线程可以同时读取同一个对象
- 单个线程可以在其他线程都以read mode持有对象闩锁的情况下，获取闩锁
- Write：
- 同一时刻只有单一线程可以持有latch
- 若任何线程在某时刻持有该对象的任意模式闩锁，则当前线程无法以write mode获取对象闩锁
闩锁实现目标
- 占据较小内存
- 在没有竞争的情况下，临界区代码能够快速执行
- 去中心化的锁管理
- 避免代价高昂的系统调用
闩锁实现
Test-and-Set Spinlock
用法如图所示：
- 声明一个原子变量，例如布尔值，假设true表示占用，false表示空闲；
- 尝试获取闩锁时将设置该布尔值，期望值为false，目标值为true；
- 设置成功，则视为获取闩锁；
- 设置失败，证明正在被其他线程占用，自旋等待，这里while将会不断尝试。
Non-uniform Memory Access, NUMA：非统一内存访问，在多插槽CPU上，每个插槽拥有自己的本地DRAM，可以快速访问，也可以通过互连访问读取其他插槽的DRAM，但这将比直接访问本地DRAM速度慢上两倍。
在NUMA架构下，上述自旋锁就出现一个问题，获取latch时可能需要不断通过互连去读取另一个插槽的DRAM，速度较慢；此外大量自旋对CPU占用比较高。
Blocking OS Mutex
std::mutex -> pthread_mutex_t -> futex
futex：
- 首先通过CAS尝试获取用户态的锁：
- 成功则直接进入临界区
- 失败说明存在竞争，进入第二阶段
- 进入内核态，线程会调用futex syscall，内核将线程挂起，等待占用线程释放锁时被唤醒。
Reader-Writer Locks
std::shared_mutex -> pthread_rwlock_t -> pthread_mutex_t + pthread_cond_t
操作系统将为读锁和写锁都维护状态
- 记录当前持有锁的线程
- 记录正在等待该锁的线程
例如上图线程获取写锁失败（两个线程正在占用读锁），因此线程将被阻塞进入队列等待被唤醒。
Hash Table Latching
- 每个page / block持有自己的读写锁，保护当前page / block中的数据；
- 更细粒度的锁实现中，每个slot持有自己的latch
B+ Tree Latching
并发问题举例
在B+树的并发控制中需要考虑如下问题：
- 多线程尝试修改同一节点内容；
- 当一个线程正在读取B+树而另一个线程正在尝试分裂/合并节点。
例如：
Solution：Latch Crabbing/Coupling
闩锁耦合：给定一种方法指导线程在B+树中移动时，如何获取闩锁，即当前线程向下移动时，其下方不应该存在其他线程，使当前线程获取的信息可能失效。
- 首先获取父节点的闩锁；
- 获取子节点闩锁；
- 如果成功获取，则释放父节点闩锁。
对于读取操作，是要按照上述过程获取锁即可确保安全。
对于写入操作，从根节点开始向下，并持有所有的写锁，直到持有了子节点闩锁并确保安全，释放父节点及以上的祖先节点的锁。
当我们到达节点D，节点D当前包含两个索引条目，删除38至多导致一个索引条目被删除，节点D仍然持有半数的元素数量，因此节点D不会发生merge行为，因此此时可以判断释放父、祖先节点是安全的。
关于A和B的释放顺序：
- 先A后B和先B后A都是正确的，并不会导致死锁；
- 但从性能来看，先释放A受益较高，因为持有A的写锁，意味着其他线程无法在同时获取整棵树任意一个节点，相当于堵住了入口。
Better Latching Algorithm
上述方案中，任意写线程将首先从B+树根节点获取写锁，假设极端情况，所有工作线程都是写线程，那么整个工作流程将变成单线程的形式，并发性能较差。
有一种更好的方式是对写线程使用乐观并发控制：
- 假设合并/拆分操作发生的概率很低；
- 从根节点开始向下获取各个节点的读锁，在叶子节点处获取写锁；
- 如果写线程发现假设出错，则重新使用悲观算法自顶向下获取锁。
Leaf Node Scans
设T1正在执行写入操作，T2正在执行范围查询，此时T1持有节点C的写锁，T2持有节点B的读锁，并按照范围查询将继续读取节点C，由于C的写锁已经被T1占用，此时T2该如何选择？
T2应当选择直接自杀重来，因为在T2视角，T1正在做什么、需要多久结束是未知的。