cmu15545笔记-索引并发控制（Concurrent Indexes）

Overview

Lock和Latch辨析

• Lock
  ：抽象的，逻辑的，整体统筹
• Latch
  ：具体的，原语性的，自我管理

本节主要探讨
Latch
。

设计目标

• 内存占用少，无竞态时执行迅速
• 等待时间过长时取消调度

大致分类

1. 自旋锁（Test-and-Set Spin Latch）
2. 阻塞互斥锁（Blocking OS Mutex）
3. 读写锁（Reader-Writer Latches）

C++中的mutex -> pthread -> Linux futex(fast user mutex)：先在用户空间用自旋锁，如果获取不到锁，陷入内核态调用阻塞锁进入阻塞队列。

Hash Table Latches

两种粒度：Page Latches和Slot Latches

Page Latches

• T1给page1上读锁，T2等待（如左上图）
• T1查看page2无读锁，给page2上读锁，释放page1读锁；T2访问page1，上写锁（如右上图）
• T2访问page2，但由于有T1读锁，等待（如左下图）
• T1释放page2读锁，T2结束等待，给page2上写锁，写入
  E|val
  （如右下图）

Slot Latches

整体过程和Page Latches类似，只不过粒度变了。

• T1给Slot A上读锁，T2给Slot C上写锁
• T1访问Slot C，但是由于有T2的写锁，释放Slot A写锁，在C等待（如左上图）
• T2访问Slot D，释放Slot C写锁，给Slot D上写锁；T1可以访问Slot C，上读锁（如右上图）
• 重复上述两个步骤（左下图和右下图）

B+Tree Latches

并发问题

相比于哈希表，B+树并发的难点在于树的结构会发生分裂或合并。

• T1找到了需要删除的值44（如左上图）
• 删除了值44，此时需要偷（steal）左兄弟的值41进行合并，保证叶子结点半满，但是T1被调度，进入休眠（如右上图）
• T2找到了需要删除的值41，准备读取值41，但是此时T2被调度，进入休眠（如左下图）
• T1唤醒，进行结点合并，41移动到了新的位置
• T2被唤醒，读取41，但是数据已经被移动（如右下图）

Latch Crabbing/Couping

具体步骤：

• 得到父结点的锁
• 得到子结点的锁
• 如果子结点是安全的，释放之前的锁，否则不释放
• 安全的定义：
  
  • 对于查询：不做要求
  • 对于插入：不满
  • 对于删除：多于半满

例：查询

例：删除

例：插入

Optimistic Coupling（乐观锁）

观察：在插入和删除操作中，都会给根结点上写锁，造成系统在根结点处是串行的，有性能瓶颈。

实际上一个页存储一个结点，页大小很大，大多数时候不需要结点分裂，删除时结点也可以延迟合并，说明B+树结构大多数时候不会变化，上写锁的代价太大。

基本思想：上读锁，发现冲突后重新上写锁。

步骤：

• 查询：不变
• 插入/删除：
  
  • 和查询一样，在路径上加读锁，到达叶子结点后加写锁
  • 如果叶子结点不安全，重做；否则直接执行相关操作

Leaf Node Scan

叶子结点扫描顺序：

• 垂直方向：自顶向底
• 水平方向：没有限制

扫描方向冲突：

1. 水平扫描方向不一致导致冲突
2. 水平扫描和垂直扫描冲突

水平扫描方向不一致：读锁没有冲突，互换读锁即可。

水平扫描方向不一致：带写锁时会有冲突，选择自我终结。

为什么选择自我终结：根本原因是latch是低级原语，不涉及全局信息，唯一知道的只有自己的信息，所以选择自我终结。

• 涉及到读写磁盘，等待时间不定
• 不知道其他进程进行到什么程度，也不知道其他进程是什么状况

为什么水平方向不能强制一个方向扫描：影响效率，在数据规模变大时更为明显。
比如where子句是
where id > 100000
，如果强制从左到右，得扫描100000条数据

水平扫描和垂直扫描方向不一致：

垂直到达叶子结点的操作，在遇到水平进行的操作时，同样会遇到上述问题，处理方式也相同。