15445-10-IndexConcurrencyControl
发布于 • 作者: Ethan
Mindmap
一、索引并发控制
到目前为止，我们假设讨论的数据结构是单线程的。然而，大多数数据库管理系统（DBMS）需要允许多个线程安全地访问数据结构，以利用多核 CPU 并隐藏磁盘 I/O 停顿。
一些系统（如 Redis）采用单线程模型，因为它们认为不使用锁会更快。另一种将单线程数据结构转为多线程结构的简单方法是使用单一读写锁保护整个结构，但这效率较低。
并发控制协议（Concurrency Control Protocol） 是 DBMS 用于确保多个工作线程对共享对象进行并发操作时产生“正确”结果的方法。这里“工作线程”可泛指多个并发访问者：有的 DBMS 使用进程（如 Postgres），有的使用线程。
协议正确性标准
- 逻辑正确性（Logical Correctness）：工作线程应能读取其期望的值，例如一个线程应能读取自己写入的值。
- 物理正确性（Physical Correctness）：对象的内部表示应是有效的，例如数据结构中的指针不会导致读取非法内存。
本讲主要关注物理正确性，逻辑正确性将在后续讲授。
二、锁与闩（Locks vs. Latches）
在 DBMS 内部保护机制中，锁（Lock） 与 闩（Latch） 存在重要区别。
锁（Lock）
- 是高层逻辑原语，用于保护数据库内容（如元组、表、数据库）不被其他事务干扰。
- 事务通常在整个执行过程中持有锁。
- 数据库系统可以向用户显示当前持有的锁。
- 需要高层机制来检测死锁并进行回滚。
闩（Latch）
- 是底层保护原语，用于保护 DBMS 内部数据结构（如页、内存区域）的临界区。
- 闩的持有时间较短，仅用于关键操作（如页锁定）。
- 与锁不同，死锁检测与回滚需由工作线程自行负责。
闩的两种模式
- 读（READ）：允许多个线程同时读取同一项。
- 写（WRITE）：仅允许单个线程访问，且阻止其他线程获取读或写锁。
三、闩的实现（Latch Implementations）
实现目标
- 内存占用小（最好以字节计）
- 无争用时执行速度快
- 分布式管理
- 避免昂贵的系统调用
底层机制：原子指令（Atomic Instructions）
现代 CPU 提供的原子指令使得线程能检测并修改内存内容。 例如：
比较并交换（CAS）
- 比较内存位置
M与值V。 - 若相等，则将新值
V’写入M；否则操作失败。
（一）测试与设置自旋闩锁（Test-and-Set Spin Latch, TAS）
自旋闩锁是 DBMS 自控的轻量锁，比操作系统互斥锁更高效。线程通过反复 CAS 操作尝试获取锁。
- 示例：
std::atomic<T> - 优点：锁/解锁操作极快（x86 上为单条指令）
- 缺点：在多线程高竞争下不可扩展，不友好于缓存，线程浪费大量无效 CAS 操作。
（二）阻塞操作系统互斥锁（Blocking OS Mutex）
使用操作系统自带的互斥锁（如 Linux 的 futex），由用户态自旋锁 + 内核态互斥锁组成。
- 若用户态锁获取成功，则直接使用；否则进入内核等待。
- 缺点：由操作系统调度，开销大（锁/解锁约 25ns），不可扩展。
- 示例：
std::mutex
（三）读写闩锁（Reader-Writer Latch）
允许读写区分，使多个线程能同时读取。
- 示例：
std::shared_mutex - 优点：支持并发读，提高性能。
- 缺点：DBMS 需维护读写队列以防饥饿，元数据开销较大。
四、哈希表闩锁（Hash Table Latching）
静态哈希表中支持并发访问较简单： 线程访问方向一致，每次只访问一个槽位，不会发生死锁。 表扩容时，可全局加锁。
动态哈希表（如可扩展哈希）更复杂，但思路一致。
两种锁粒度
-
页锁（Page Latch）：每页一个读写锁。
- 并行度低，但单线程访问页内多个槽位快。
-
槽锁（Slot Latch）：每槽位一个锁。
- 并行度高，但锁存储与获取成本大。
- 可用单模式自旋锁降低开销。
还可直接用 CAS 实现 无锁线性探测哈希表。
五、B+ 树闩锁（B+Tree Latching）
挑战
- 多线程同时修改同一节点。
- 一线程遍历时另一线程分裂/合并节点。
锁抓取/耦合协议（Latch Crabbing / Coupling）
允许多线程并发访问 B+ 树。
基本思想：
- 获取父节点锁
- 获取子节点锁
- 若子节点“安全”，释放父节点锁
“安全”定义：
- 插入时：节点未满
- 删除时：节点超过半满
基本协议
- 查找：从根向下，依次锁定子节点并释放父节点锁。
- 插入/删除：自上而下获取写锁，若子节点安全则释放祖先锁。
性能优化建议：优先释放树上层锁。
乐观抓取协议（Optimistic Latch Crabbing）
基本算法的问题在于每次插入/删除都锁根节点，限制并行。 优化思路是假设分裂/合并很少：
- 事务先以读锁方式向下遍历；
- 到叶节点后尝试升级为写锁；
- 若叶节点不安全，释放锁并重启事务。
叶节点扫描（Leaf Node Scans）
线程自上而下获取锁，不会形成死锁。 但若叶节点扫描与删除等操作并发，可能出现死锁。
解决方式：
- 叶节点兄弟锁采用“无等待模式”（no-wait）。
- 若锁不可用，线程应快速放弃并重启操作。
- 可根据线程已完成的工作量调整重试等待时间。
对于高竞争索引结构，可通过高层系统线程调度器检测并协调线程调度，而非在数据结构中直接实现。
Notes
