Lecture #09: Index Concurrency Control
本文是对CMU15-445课程第9节笔记的一个粗略总结和翻译。仅供个人(M1kanN)复习使用。
目录
1. Index Concurrency Control
-
目前讨论的数据结构都是单线程的，但大多数DBMS都需要允许多线程安全访问数据结构，去最大化了利用CPU核心或者隐藏I/O stall。
-
并行控制协议是DBMS用于确保对共享对象进行并发操作保持正确结果的方法。
-
一个协议的正确性标准可以有所不同：
- 逻辑正确性：
即线程能够读取它应该期望读取的值。
例如：一个线程应该读回它之前写的值。 - 物理正确性：
即对象的内部是健全的(sound)。
例如：在数据结构中没有会导致线程读取无效内存位置的指针。
- 逻辑正确性：
-
本次课程中，只关心物理正确性的问题。
2. Locks vs. Latches
- 讨论DBMS如何保护其内部元素的时候，lock和latch之间有重要区别。
Locks
- Lock是一个更高层次的逻辑基元(logical primitive)， 它用来保护数据库的内容（如tuples、tables、databases）不受其他事务（transactions）的影响。事务将在整个持续时间内持有一个lock。数据库系统可以在运行查询的过程中向用户暴露正在持有的lock。lock需要能够回滚（rollback changes）
Latches
- Latch是用于DBMSD内部数据结构（例如：数据结构、内存区域）的关键部分的低级保护基元，不受其他线程影响。Latch只在正在进行的操作的持续时间内保持。Latch不需要回滚变化（rollback change）。有两种模式的latch：
- READ：
多个线程可以允许读同一项。一个线程可以获取read latch，即使另一个线程已经持有。 - WRITE:
只有一个线程才能允许访问该项。如果另一个线程已经持有write latch，则另一个不能获得。
- READ：
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 - 优点：并发读取
- 缺点：必须维护读写队列。以防饥饿。所以内存开销更大。
- 例子：
4. Hash Table Latching
- 由于线程访问的数据结构优先，因此在静态哈希表中支持并发访问很简单。例如：所有线程从槽中移动到下一个槽的时候，都自上而下移动。线程每次也只访问一个页面/槽。这种情况下死锁是不可能的，因为没有两个线程可以争夺对方的latch。当需要调整表的大小的时候，我们可以直接对整个表进行全局锁存。
- 动态散列方案的锁存更复杂。因为有更多的共享状态需要更新，一般的方法是一样的。
- 哈希表的锁存有两种方法：在锁存的粒度上有所不同。
- Page Latches：
每个页有自己的读写锁来保护全部内容。线程在访问一个页面之前，获得一个读写锁。这降低了并行性。但访问一个页面中的多个槽对一个线程来说是非常快的。因为只需要获取一个锁存器。 - Slot Latches：
每个槽都有自己的锁存器。增加并行性，因为两个线程可以访问不同槽位。但也增加了存储和计算开销。因为线程必须为它们访问的每个槽获得一个锁存器，而每个槽都必须存储锁存器的数据。
DBMS可以使用单模式锁存器（自旋锁）来减少元数据和计算开销，但需要付出一些并行性的代价。
- Page Latches：
- 也可以直接使用CAS指令创建一个latch-free 的线性探测哈希表。通过尝试将一个“null”值与我们希望插入的tuple进行比较和交换，可以实现在一个槽中的插入。与我们想要插入的tuple进行CAS。如果失败可以探测下一个槽，直到成功。
5. B+Tree Latching
- B+树的锁存主要用于防止以下问题：
- 不同线程试图同时修改同一个结点的内容
- 当一个线程分裂/合并结点的时候，另一个线程在遍历树
- Latch Crabbing/Coupling(锁存耦合？)是一种协议：允许多个线程同时访问/修改 B+树。基本思想是：
- Get latch for the parent
- Get latch for the child
- 若子结点被认为是安全的，则释放父节点的latch。一个安全结点是在更新的时候不会分裂、合并或者重新分配的结点。
- 注意：安全的概念取决于操作是插入还是删除。一个完整的结点对于删除是安全的，因为不需要合并，但对于插入就不安全了，因为可能需要分割结点！注意：读锁存器不需要担心安全条件！
Basic Latch Crabbing Protocol
- Search：
从根开始往下，重复获取孩子结点的锁，并释放父结点的锁。 - Insert/Delete:
从根开始往下，按需获得X个latch。一旦孩子结点被锁住，检查是否安全。如果安全，则释放所有祖先结点的锁！
从正确性的角度来看，释放锁存器的顺序并不重要。然而从性能上来讲，最好是释放树中较高的锁存器，因为更高的结点锁存器阻止了较大部分叶结点的访问。
Improved Latch Crabbing Protocol
- 基本的Latch Crabbing算法的问题是：事务在每次插入/删除操作的时候总是获得根上的独占锁存器，这限制了并行性。
相反，我们可以假设必须调整大小（分割、合并结点）的情况很少，因此事务可以获得共享锁存器，直到叶结点。每个事务都会假设通往目标叶子结点的路径是安全的，并使用READ锁存器来抓取（Crabbing）来到达，并进行检验（是否安全）。如果不安全，则我们终止操作，并重新操作，这次用WRITE锁存器来进行。- Search:
与基本算法一样。 - Insert/Delete:
跟Search一样，不断获取和释放READ latch。最后在叶子结点上设置WRITE latch。如果叶子不安全，则重来，这次用基本算法的思路！
- Search:
Leaf Node Scans
- 之前两个算法都是从上到下的。这意味着线程只能从低于当前结点中获取锁存器。如果想要的锁存器不能用，则线程必须等待，直到它变得可用。鉴于此，永远不可能出现死锁
- 然而，叶子结点扫描很容易出现死锁，因为现在我们有线程从两个方向同时获得独占锁。Index latch不支持死锁检测和预防。
- 因此，程序员唯一处理这个问题的方法就是通过code discipline。叶子结点的兄弟结点的锁存器获取协议必须支持“无等待”模式。也就是说，B+树的代码必须应对锁存器获取失败的问题。由于锁存器旨在被（相对）短暂的持有，如果一个线程试图在叶子结点上获取锁存器，但该锁存器不可用，那么它应该迅速中止其操作（释放它所持有的任何锁存器），并重新启动操作。