【CMU 15-445】09 索引并发控制

Slides
Notes

1. 索引并发控制

并发控制协议是DBM用来确保对共享对象进行并发操作的“正确”结果的方法。协议的正确性标准可以有所不同：

• 逻辑正确性：我可以看到我应该看到的数据吗？这意味着线程能够读取它应该被允许读取的值。
• 物理正确性：物体的内部表示是否正确？这意味着我们的数据结构中没有会导致线程读取无效内存位置的指针。

索引的逻辑内容是我们在这堂课中唯一关心的事情。它们与其他数据库元素不太一样，因此我们可以区别对待它们。

2. Locks vs. Latches

Locks ：

• 保护索引的逻辑内容不受其他事务的影响。
• 在交易的整个持续时间内(主要)持有。
• DBMS需要能够回滚更改。

Latches：

• 保护索引内部数据结构的临界区不受其他线程的影响。
• 持有操作持续时间。
• DBMS不需要能够回滚更改。

两种模式：

• READ：允许多个线程同时读同一项目。如果另一个线程处于读取模式，则线程可以获取读取latch
• WRITE：只允许访问一个线程。如果另一个线程以任何模式保持latch，线程就无法获得写latch。

3. Latch 实现

我们可以用来实现latch的底层原语是通过现代CPU提供的原子比较和交换(CAS)指令。这样，线程就可以检查内存位置的内容，以确定它是否具有某个值。如果是，则CPU将用新值交换旧值。否则，内存位置保持不变。

在DBMS中实现latch有几种方法。每种方法在工程复杂性和运行时性能方面都有不同的权衡。这些测试和设置( test-and-set，TAS)步骤是自动执行的(即，在一个线程检查它之后，但在它更新它之前，没有其他线程可以更新值)。

Blocking OS Mutex

使用操作系统内置的互斥基础设施作为 latch。Futex(快速用户空间互斥锁)由(1)用户空间中的自旋锁和(2)操作系统级互斥锁组成。如果DBMS可以获取用户空间锁，则设置锁。它显示为DBMS的单个latch，即使它包含两个内部 latch。如果DBMS无法获取用户空间latch，则它会进入内核并尝试获取更昂贵的 Mutex 。如果DBMS无法获取第二个Mutex，则线程通知OS它在锁上被阻止，然后取消调度。

在DBMS中，OS Mutex 通常不是一个好主意，因为它由操作系统管理，并且开销很大。

• Example：std::mutex
• 优点：使用简单，不需要在DBMS中额外编码。
• 缺点：由于操作系统调度，价格昂贵且不可伸缩(每次锁定/解锁调用约25 ns)。

测试和设置自旋锁存器(TAS)

自旋锁是操作系统互斥锁的更有效的替代方案，因为它由DBMS控制。自旋锁实质上是线程试图更新的内存中的位置(例如，将布尔值设置为真)。线程执行CAS以尝试更新内存位置。如果它不能，那么它会不停地在 while 循环中旋转，试图更新它。

• Example：std::atomic
• 优点：锁/解锁操作高效(单条指令锁定/解锁)。
• 缺点：伸缩性差，缓存也不友好，因为有多个线程，CAS指令会在不同的线程中多次执行。这些浪费的指令将堆积在竞争激烈的环境中；这些线程在操作系统看来很忙，即使它们没有做有用的工作。这会导致缓存一致性问题，因为线程正在轮询其他CPU上的缓存线。

读-写 锁

Mutex和自旋锁存不区分读/写(即，它们不支持不同的模式)。我们需要一种允许并发读取的方法，因此如果应用程序具有繁重的读取，它将具有更好的性能，因为读取器可以共享资源而不是等待。

读-写 锁允许在读或写模式下保持锁。它跟踪在每种模式下有多少线程持有锁并等待获取锁。

示例：这是在自旋锁上实现的。
优点：支持并发读取器。
缺点：DBMS必须管理读/写队列以避免饥饿。由于额外的元数据，存储开销比自旋锁更大。

4. 哈希表 latching

由于线程访问数据结构的方式有限，因此很容易在静态哈希表中支持并发访问。例如，当从一个槽移动到下一个槽(即，自上而下)时，所有线程都以相同的方向移动。线程一次也只能访问一个页面/槽。因此，死锁在这种情况下是不可能的，因为没有两个线程可以竞争对方持有的锁。要调整表的大小，需要对整个表(即header 页中的表)进行全局锁。

动态哈希方案(例如，可扩展的)中的锁稍微复杂一些，因为有更多的共享状态要更新，但一般方法是相同的。

• Page Latches：每个页面都有自己的读写器 latches，以保护其整个内容。线程在访问页面之前获取读取latch或写入latch。这降低了并行度，因为一次可能只有一个线程可以访问一个页面，但访问页面中的多个槽将会很快，因为一个线程只需要获取一个latch。
• Slot Latches：每个插槽都有自己的latches。这提高了并行度，因为两个线程可以访问同一页中的不同槽。但是它增加了访问表的存储和计算开销，因为线程必须为它们访问的每个槽获取一个latch。DBMS可以使用单latch(即，自旋锁)来减少元数据和计算开销。

5. B+ Tree latching

Lock crabbing / coupling 是一种允许多个线程同时访问/修改B+树的协议：

Get latch for parent.
Get latch for child.
Release latch for parent if it is deemed safe. A safe node is one that will not split or merge when updated (not full on insertion or more than half full on deletion).

基本的Latch Crabbing 协议:

查找：从根目录开始向下搜索，反复获取子级上的锁，然后解锁父级。
插入/删除：从根开始向下，根据需要获取 X 锁（write 锁）。一旦孩子锁上，检查它是否安全。如果孩子是安全的，就解开所有祖先上的锁。

改进的 Lock Crabbing 协议：

基本锁抓取算法的问题在于，对于每个插入/删除操作，事务始终获取根上的独占锁。这限制了并发性。

相反，我们可以假设很少需要调整大小(即拆分/合并节点)，因此事务可以获取向下到叶节点的共享锁。每个事务将假定到目标叶节点的路径是安全的，并使用读锁和爬行来到达它，并进行验证。如果路径中的任何节点不安全，则执行先前的算法(即获取写锁)。

• 查找：与之前的算法相同。
• 插入/删除：设置读锁，就像查找一样，转到叶节点，在叶节点上设置写锁。如果叶节点不安全，则释放所有先前的锁，并使用先前的插入/删除协议重新启动事务。

6. 叶子结点扫描

这些协议中的线程以“自上而下”的方式获取锁。这意味着线程只能从低于其当前节点的节点获取锁。如果所需的锁不可用，则线程必须等待，直到它变为可用。有鉴于此，不可能出现死锁。

叶节点扫描容易发生死锁，因为现在我们有多个线程试图同时获取两个不同方向的锁(即从左到右和从右到左)。索引锁不支持死锁检测或避免。

因此，我们处理这个问题的唯一方法是通过编码规程（coding discipline）。叶节点同级锁获取协议必须支持“无等待”模式。也就是说，B+树码必须处理失败的锁获取。这意味着，如果线程试图获取叶节点上的锁，但该锁不可用，则它将立即中止其操作(释放它持有的所有锁)，然后重新启动该操作。