CMU15445-lecture9
第九课：索引并发控制
1 索引并发控制
到目前为止，我们假设我们讨论的数据结构是单线程的。然而，大多数 DBMS 需要允许多个线程安全地访问数据结构，以利用额外的 CPU 核心并隐藏磁盘 I/O 停顿。
有些系统使用单线程模型。将单线程数据结构转换为多线程数据结构的一种简单方法是使用读写锁，但效率不高。
并发控制协议是 DBMS 用于确保共享对象上的并发操作得到“正确”结果的方法。
协议的正确性标准可能会有所不同：
- 逻辑正确：这意味着线程能够读取它应该读取的值，例如线程应该读回它之前写入的值。
- 物理正确：这意味着对象的内部表示是健全的，例如数据结构中不存在会导致线程读取无效内存位置的指针
出于本讲座的目的，我们只关心强制执行物理正确性。我们将在后面的课中重新审视逻辑正确性。
2 Locks vs. Latches
在讨论 DBMS 如何保护其内部元素时，锁和闩锁之间存在重要区别。
Locks
锁时一种更高层次的逻辑原语，用于保护数据库中的内容（例如元组，表或者整个数据库），防止其他事务的干扰。一个事务在其整个执行期间都会持有锁。数据库系统可以向用户公开运行查询时持有的锁。应该有一些更高级别的机制来检测死锁和回滚更改。
Latches
锁存器是低级保护原语，用于来自其他线程的 DBMS 内部数据结构（例如数据结构、内存区域）的关键部分。锁存器会在数据库系统中短暂保留一个简单的操作（即页锁存器）。锁存器有两种模式：
- 读：允许多个线程同时读取同一个项目。即使另一个线程已经在读模式下获取了锁存器，线程也可以在读模式下获取该锁存器。
- 写：只允许一个线程访问该项目。如果另一个线程在任何模式下持有锁存器，则线程无法获取写锁存器。持有写锁存器的线程还会阻止其他线程获取读锁存器。
3 Latch实现
Latch实现应该具有较小的内存占用，并且在没有争用时可以有一条快速路径来获取锁存器。
用于实现锁存器的底层原语是通过现代 CPU 提供的原子指令。这样，线程可以检查内存位置的内容以查看它是否具有特定值。
有多种方法可以在 DBMS 中实现锁存器。每种方法在工程复杂性和运行时性能方面都有不同的权衡。这些测试和设置步骤以原子方式执行（即，没有其他线程可以更新测试和设置步骤之间的值。
Test-and-Set Spin Latch (TAS) （自旋锁）
自旋锁存器是操作系统互斥体的更有效替代方案，因为它由 DBMS 控制。自旋锁存器本质上是线程尝试更新的内存位置（例如，将布尔值设置为 true）。线程执行 CAS 来尝试更新内存位置。DBMS 可以控制如果无法获得锁存器会发生什么情况。它可以选择重试（例如，使用 while 循环）或允许操作系统取消调度它。因此，此方法为 DBMS 提供了比操作系统互斥体更多的控制权，在操作系统互斥体中，如果无法获取锁存器，则将控制权交给操作系统。
- 举例：std::atomic
- 优点:锁存/解锁操作非常高效（在 x86 上使用单指令锁定/解锁）。
- 缺点:不可扩展，也不适合缓存，因为使用多个线程，CAS 指令将在不同的线程中执行多次。这些浪费的指令会在高竞争环境中堆积起来；尽管线程没有做有用的工作，但对操作系统来说它们看起来很忙。这会导致缓存一致性问题，因为线程正在轮询其他 CPU 上的缓存线。
阻塞操作系统Mutex
锁存器的一种可能实现是操作系统内置的互斥基础设施。 Linux 提供了 futex（快速用户空间互斥体），它由 (1) 用户空间中的自旋锁存器和 (2) 操作系统级互斥体组成。如果 DBMS 可以获取用户空间锁存器，则锁存器被设置。尽管它包含两个内部锁存器，但它对于 DBMS 来说却显示为单个锁存器。如果 DBMS 无法获取用户空间锁存器，那么它会进入内核并尝试获取更昂贵的互斥锁。DBMS 无法获取第二个互斥体，然后线程通知操作系统它在互斥体上被阻塞，然后它被取消调度。
操作系统互斥在 DBMS 内部通常是一个坏主意，因为它由操作系统管理并且开销很大
- 举例：std::mutex
- 优点：使用简单并且在DBMS中不需要额外coding
- 缺点：由于操作系统调度，成本昂贵且不可扩展（每次锁定/解锁调用大约 25 ns）。
读写Latches
互斥锁和自旋锁存器不区分读/写（即，它们不支持不同的模式）。DBMS 需要一种允许并发读取的方法，因此如果应用程序有大量读取，它将具有更好的性能，因为读取者可以共享资源而不是等待。
读写器锁存器允许锁存器保持在读或写模式。它追踪有多少个线程持有锁存器并等待在每种模式下获取锁存器。读写器锁存器使用前两个锁存器实现之一作为原语，并具有额外的逻辑来处理读写器队列，这些队列是每种模式下对锁存器的请求的队列。不同的 DBMS 对于如何处理队列可以有不同的策略。
需要注意的一件事是，不同的读写锁实现具有不同的等待策略。有读者优先锁、作者优先锁和公平读写锁。不同操作系统和 pthread 实现中的行为有所不同。
- 举例：std::shared_mutex
- 优点：允许并发读
- 缺点：DBMS 必须管理读/写队列以避免饥饿。由于额外的元数据，存储开销比自旋锁存器更大。
4 哈希表Latch
由于线程访问数据结构的方式有限，因此很容易支持静态哈希表中的并发访问。例如，当从槽移动到下一个槽时（即自上而下），所有线程都沿相同方向移动。线程一次也只能访问一个页面/槽。因此，在这种情况下不可能出现死锁，因为没有两个线程可以竞争对方持有的锁存器。当我们需要调整表的大小时，我们只需对整个表进行全局锁存即可执行操作。
动态哈希方案（例如，可扩展）中的锁存是一种更复杂的方案，因为有更多的共享状态需要更新，但一般方法是相同的。
有两种方法支持哈希表中的锁存，它们的锁存粒度不同:
- 页级锁存器：每个页面都有自己的读写器锁存器来保护其全部内容。线程在访问页面之前获取读或写锁存器。这会降低并行性，因为一次可能只有一个线程可以访问一页，但是对于单个线程来说，访问一页中的多个槽会很快，因为它只需要获取一个锁存器。
- 槽级锁存器：每个插槽都有自己的闩锁。这增加了并行性，因为两个线程可以访问同一页面上的不同插槽。但它增加了访问表的存储和计算开销，因为线程必须为其访问的每个槽获取锁存器，并且每个槽必须为锁存器存储数据。DBMS 可以使用单模式锁存器（即自旋锁存器）来减少元数据和计算开销，但代价是一些并行性。
还可以直接使用比较和交换 (CAS) 指令创建无锁存线性探测哈希表。通过尝试将特殊的“空”值与我们希望插入的元组进行比较和交换，可以实现在槽处的插入。如果失败，我们可以探测下一个槽，继续直到成功。
5 B+树Latch
B+Tree 锁存的挑战是防止以下两个问题：
- 多个线程同时尝试修改节点的内容。
- 一个线程遍历树，而另一个线程拆分/合并节点。
“Latch crabbing/coupling” 是一种协议，它允许多个线程同时访问或修改B+树。基本思路如下：
- 获得父节点的锁
- 获得子节点的锁
- 如果子节点被认为“安全”，则释放父节点的锁。 “安全”节点是指更新时不会分裂、合并或重新分配的节点。换句话说，一个节点是“安全的”如果
- 插入：它不是满的
- 删除：它至少半满
请注意，读锁存器不需要担心“安全”条件。
基本锁抓取协议：
- 搜索：从根开始向下，重复获取子级的闩锁，然后解锁父级。
- 插入/删除：从根开始向下，根据需要获取 X 个锁存器。一旦孩子被锁住，检查是否安全。如果孩子安全，则释放其所有祖先的锁
从正确性的角度来看，锁存器释放的顺序并不重要。然而，从性能的角度来看，最好释放树中较高位置的锁存器，因为它们会阻止对大部分叶节点的访问。
改进的锁抓取协议：基本锁抓取算法的问题在于，事务总是在每次插入/删除操作的根上获取独占锁.这限制了并行性。相反，我们可以假设必须调整大小（即拆分/合并节点）的情况很少见，因此事务可以获取直至叶节点的共享锁存器。每个事务都会假设到目标叶节点的路径是安全的，并使用 READ 锁存器和螃蟹来到达它并进行验证。如果叶节点不安全，那么我们将中止并执行之前的算法，获取 WRITE 锁存器。
- 搜索：与以前相同的算法。
- 插入/删除：设置读锁就像搜索一样，转到叶子，然后在叶子上设置写锁。如果叶子不安全，则释放所有先前的锁存器，并使用先前的插入/删除协议重新启动事务。
叶子结点扫描
这些协议中的线程以“自上而下”的方式获取锁存器。这意味着线程只能从低于其当前节点的节点获取锁存器。如果所需的锁不可用，则线程必须等待直到它变得可用。鉴于此，永远不会出现僵局。
然而，叶节点扫描很容易出现死锁，因为现在我们有线程尝试同时在两个不同方向获取排它锁（例如，线程 1 尝试删除，线程 2 执行叶节点扫描）。索引锁存器不支持死锁检测或避免。
因此，程序员处理这个问题的唯一方法是通过编码规则。叶节点同级锁存器获取协议必须支持“无等待”模式。也就是说，B+树代码必须处理失败的锁存获取。由于锁旨在（相对）短暂地保持，因此如果线程尝试获取叶节点上的锁但该锁不可用，则它应该快速中止其操作（释放其持有的任何闩锁）并重新启动操作。