前言

CMU 15-445 (Database Systems) 是数据库领域的经典课程，其核心项目 BusTub 旨在通过构建一个面向磁盘的嵌入式关系型数据库，探索数据库内核从存储层到执行层的全链路实现。

本文旨在复盘该数据库内核的关键架构决策，聚焦于核心算法的理论依据、系统设计的权衡 (Trade-off) 以及与工业级数据库 (如 MySQL/InnoDB) 的架构异同。通过对缓冲池、索引、执行引擎及并发控制四个维度的深度剖析，探讨如何构建一个高性能、线程安全的数据库系统。

缓冲池管理 (Buffer Pool Manager)

在面向磁盘的数据库管理系统中，数据主要存储在非易失性存储设备 (HDD/SSD) 上，但所有的计算和操作必须在易失性内存中进行。缓冲池管理器 (Buffer Pool Manager, BPM) 是连接磁盘与内存的中间层，其核心职责是在有限的内存空间 (Frames) 与巨大的磁盘空间 (Pages) 之间建立映射与调度机制。BPM 的设计目标极为明确：最大化缓存命中率，最小化磁盘 I/O 开销，并保证多线程环境下的数据一致性。

页表映射：可扩展哈希 (Extendible Hashing)

为了管理 Page_id(磁盘逻辑页号) 到 Frame_id(内存物理帧号) 的映射关系，系统并未采用传统的链式哈希或线性探测哈希，而是选择了可扩展哈希 (Extendible Hashing)。

传统哈希的局限性

  • 静态哈希 (Static Hashing)：在哈希冲突严重时，链表长度增加导致查找退化为 O(N)。且扩容 (Rehash) 操作需要锁住整个哈希表并重新计算所有键值，导致严重的性能停顿 (Stop-the-world)，不适合高并发场景。
  • 线性哈希 (Linear Hashing)：虽然支持平滑扩容，但其分裂策略通常基于负载因子，可能导致"由于热点数据集中在某个桶而该桶却迟迟不分裂"的情况，且实现逻辑相对复杂。

可扩展哈希的架构优势

可扩展哈希通过维护一个 目录 (Directory) 和多个 桶 (Bucket) 来实现动态扩容。其核心机制依赖于 全局深度 (Global Depth) 和 局部深度 (Local Depth)。

  • 目录倍增而非全量重哈希：当某个桶溢出且 Local Depth == Global Depth 时，只需将目录大小翻倍。目录中新增的指针大多指向原有的桶，只有溢出的那个桶需要分裂。这种操作主要涉及指针复制，内存开销极低且速度极快。
  • 局部性分裂：当 Local Depth < Global Depth 时，桶的分裂甚至不需要触动目录的扩容，仅需调整目录中对应的指针指向新分裂的桶。
  • 位运算寻址：利用 Page ID 的低位 (或高位) 二进制作为索引，硬件指令支持友好，寻址效率极高。

在 Buffer Pool 的场景下，可扩展哈希保证了在数据量剧烈波动时，映射表的维护开销是平滑且可控的，避免了系统吞吐量的剧烈抖动。

缓存置换策略：LRU-K

当缓冲池已满且需要加载新页面时，必须选择一个页面进行驱逐 (Evict)。传统的 LRU(Least Recently Used) 算法在数据库场景下存在著名的 “缓存污染”(Buffer Pool Pollution) 问题。

传统 LRU 的痛点

在执行 全表扫描 (Sequential Scan) 或大索引查找时，大量仅被访问一次的数据页会瞬间涌入缓冲池。在传统 LRU 策略下，这些偶发数据会排在队列头部，从而将那些被频繁访问的真正热点数据 (如 B+ 树根节点、常驻字典表) 挤出缓存。这会导致后续查询的缓存命中率呈断崖式下跌。

LRU-K 核心机制

LRU-K 算法的核心思想是：将"最近访问时间"与"访问历史频率"解耦。该算法认为，只有数据被访问至少 K 次，才能确立其"热点"地位。在 BusTub 实现中，通常取 K=2。

算法维护两个优先级队列：

  1. 历史队列 (History Queue / Access List)：
    • 准入规则：页面初次被访问，或访问次数不足 K 次时，驻留在此队列。
    • 淘汰策略：采用 FIFO(先进先出)。用于过滤那些"一次性"的扫描数据。如果数据在移出历史队列前未被再次访问，说明它不是热点，直接淘汰。
  2. 缓存队列 (Cache Queue / Hot List)：
    • 准入规则：当历史队列中的页面访问次数达到 K 次时，晋升 (Promote) 至此队列。
    • 淘汰策略：采用标准 LRU。这里存放的是经过验证的真正热点数据。

值的权衡

  • K=1：退化为普通 LRU，抗扫描污染能力为零。
  • K 值过大：导致"缓存僵化"。新产生的热点数据 (如突发流量) 需要很长时间积累访问次数才能进入缓存队列，系统预热慢，且维护大量历史访问记录会消耗额外内存 (Memory Overhead)。
  • K=2：在实现复杂度、元数据内存开销以及抗污染能力之间取得了最佳平衡，是工业界的通用选择。

并发控制与 Pin/Unpin 机制

BPM 必须是线程安全的。在实现中，需要严格区分逻辑引用计数 (Pin Count) 与物理锁 (Latch) 的概念。

Pin Count (引用计数)

  • 作用：防止正在被使用的页面被 Replacer 驱逐。
  • 机制：当执行引擎 (Executor) 请求页面时，Pin Count++；使用完毕后，显式调用 Unpin，Pin Count--。
  • 约束：只有 Pin Count == 0 的页面才被视为 Evictable(可驱逐)，Replacer 只能选择这些页面进行淘汰。这从逻辑层面保证了数据的安全性。

Latch (物理锁)

  • BPM 粒度锁：保护哈希表、Free List 和 Replacer 的内部状态。这是一个短暂持有的互斥锁，操作完成后立即释放。
  • Page 粒度锁：保护页面内容 (data_)。这是读写锁 (Reader-Writer Latch)，允许多个线程同时读取页面内容，但写操作互斥。

脏页管理

为了保证数据的一致性与持久性，BPM 维护了页面的脏位 (Dirty Flag)。

  • 当执行引擎修改了页面内容 (如 Insert/Update)，在 Unpin 时会将该页标记为 Dirty。
  • 在 Replacer 决定驱逐一个脏页之前，BPM 必须强制调用磁盘管理器 (Disk Manager) 将该页数据写回磁盘，否则会导致数据丢失。这一过程通常配合预写日志 (WAL) 协议，以确保事务的原子性 (虽然 WAL 通常在更高层级处理，但 BPM 提供了落盘的基础能力)。

索引引擎 (B+ Tree Index)

在关系型数据库中，索引是提升数据检索效率的关键组件。本项目采用了 B+ 树 (B+ Tree) 作为核心索引结构。与二叉搜索树 (BST) 或红黑树相比，B+ 树是一种专为磁盘存储设计的多路平衡查找树，其核心优势在于极高的扇出率 (Fan-out) 和低高度 (Height)，能够显著减少检索过程中的磁盘 I/O 次数。

B+ 树数据结构

B+ 树将节点分为内部节点 (Internal Page) 和叶子节点 (Leaf Page)，两者在物理存储和逻辑功能上存在严格区分：

  • 内部节点：仅作为导航使用，不存储实际数据。节点内存储 (Key, Page_id) 对。由于不存数据，单个磁盘页 (Page) 能容纳大量的键值引导指针，从而支撑起巨大的树扇出。
  • 叶子节点：存储实际的索引键值和记录指针 (Key, Record_id)。所有叶子节点在逻辑上处于同一层，并通过 Next_Page_id 指针串联成一个双向链表。这种设计使得 B+ 树不仅支持高效的单点查找 (Point Query)，也能极其高效地支持范围扫描 (Range Scan)。

在节点内部，键值对保持有序排列。对于单个节点内的查找，不再采用线性扫描，而是利用二分查找 (Binary Search) 将时间复杂度控制在 O(log N)。

[!NOTE] LSM Tree vs. B+Tree

特性B+ TreeLSM Tree
数据更新方式原地更新 (In-place Update)：直接修改磁盘上的数据页。追加更新 (Append-only)：新数据写入内存，定期刷新并合并到磁盘。
写入性能较慢。涉及随机 I/O 和页分裂。极快。顺序 I/O 写入，利用内存缓冲。
读取性能极快且稳定。通常 3~4 次磁盘寻道即可找到。较慢。可能需要检索多个文件 (SSTable)。
空间利用率较低。存在页碎片 (Page Fragmentation)。较高。数据紧凑存储，且更易于压缩。
一致性/可靠性强。崩溃恢复逻辑相对成熟。依赖 WAL(预写日志) 来保证内存数据不丢失。
典型代表MySQL (InnoDB), PostgreSQL, SQLiteRocksDB, Cassandra, HBase, ClickHouse

核心操作算法

B+ 树的维护核心在于如何在插入和删除操作中始终保持树的平衡性。

查找操作从根节点开始，利用二分查找确定目标 Key 所在的子节点指针，递归向下直到叶子节点。在叶子节点中再次进行二分查找，定位具体的 Record ID。

插入 (Insert) 与分裂机制

插入操作首先定位到目标叶子节点。若插入后节点未满，则直接完成；若节点已满 (Size > Max_Size)，则触发分裂 (Split)：

  1. 叶子节点分裂：将原有节点一分为二，创建一个新节点。将原节点的一半数据移动到新节点。关键点：将新节点的首个 Key 复制 (Copy Up) 到父节点中作为索引。
  2. 内部节点分裂：当父节点也满时，同样一分为二。关键点：与叶子节点不同，内部节点会将中间的 Key 上推 (Push Up) 到更上一层，而不是复制。
  3. 递归传播：分裂可能一直向上传播至根节点。当根节点分裂时，会创建一个新的根节点，这是 B+ 树高度增加 (Height + 1) 的唯一方式。

删除 (Delete) 与合并/重分配

删除操作定位并移除 Key 后，需检查节点利用率是否低于阈值 (Min_Size，通常为 Max_Size/2)。若低于阈值，触发调整：

  1. 重分配 (Redistribute/Borrow)：优先检查兄弟节点 (Sibling)。若兄弟节点富余，则从兄弟节点"借"一个键值对。这种方式只修改当前节点、兄弟节点和父节点，开销较小。
  2. 合并 (Merge/Coalesce)：若兄弟节点也刚好处于最低阈值，无法借出，则将当前节点与兄弟节点合并。合并后，父节点需要删除指向原节点的指针。
  3. 递归传播：合并会导致父节点元素减少，可能触发父节点的合并，直至根节点。若根节点只剩一个子节点，则将该子节点设为新根，树高度降低。

并发控制：螃蟹锁协议 (Latch Crabbing)

在多线程环境下，简单的互斥锁会严重限制吞吐量。为了支持高并发读写，系统实现了螃蟹锁协议 (Latch Crabbing / Coupling)。其核心思想是：线程在获取子节点锁的同时，判断是否可以释放父节点的锁，像螃蟹一样交替前进。

基本协议流程

  • 查询 (Search)：
    1. 获取父节点的 读锁 (Read Latch)。
    2. 获取子节点的读锁。
    3. 立即释放父节点的读锁。
    4. 重复直到叶子节点。
  • 修改 (Insert/Delete)：
    1. 获取父节点的 写锁 (Write Latch)。
    2. 获取子节点的写锁。
    3. 安全检查 (Safety Check)：判断子节点是否"安全"。
      • 对于插入：子节点未满 (不会触发分裂)。
      • 对于删除：子节点超过半满 (不会触发合并)。
    4. 锁释放：如果子节点安全，则该操作的影响范围被限制在子节点内部，此时可以提前释放父节点及所有祖先节点的写锁。否则，必须持有祖先锁，以防止分裂/合并波及上层。

优化策略：乐观锁 (Optimistic Coupling)

标准的螃蟹锁在修改操作时，必须从根节点开始加写锁。由于根节点是所有操作的必经之路，这会导致根节点成为严重的并发瓶颈。为此，系统引入了乐观锁优化：

  1. 乐观假设：假设绝大多数插入/删除操作不会触发分裂或合并 (即叶子节点是安全的)。
  2. 执行路径：
    • 线程首先以读锁 (Read Latch) 从根节点遍历至叶子节点。
    • 到达叶子节点后，获取叶子节点的写锁。
    • 检查叶子节点是否真的安全。
    • 分支一 (成功)：如果安全，直接进行修改，操作结束。整个过程根节点未加写锁，大幅提升并发度。
    • 分支二 (失败)：如果发现叶子节点已满 (需要分裂)，则乐观假设失败。线程释放所有持有的锁，重启 (Restart) 操作，这次回退到标准的悲观策略，从根节点开始加写锁。

迭代器与全表扫描

为了支持 SELECT * 或范围查询，B+ 树实现了索引迭代器 (Index Iterator)。 迭代器利用叶子节点的 Next_Page_i* 指针，使得执行引擎可以在不经过 B+ 树内部节点的情况下，直接在叶子节点层横向遍历。在实现中，迭代器需持有当前叶子节点的读锁 (或 Page Guard)，在移动到下一个叶子节点时，需遵循"先锁下一个，再释放当前"的顺序，以避免出现并发下的"游标失效"或幻读风险。

查询执行引擎 (Query Execution)

查询执行引擎是数据库内核的"大脑"与"手脚"。它负责将用户输入的 SQL 语句转化为可执行的物理计划，并调度底层存储引擎完成数据的检索与计算。本系统的架构遵循经典的数据库分层设计：Parser（解析器） -> Binder（绑定器） -> Optimizer（优化器） -> Executor（执行器）。

火山模型 (Volcano / Iterator Model)

在物理执行层面，系统采用了火山模型（亦称迭代器模型）。这是传统行存数据库（如 MySQL, PostgreSQL, Oracle）中最通用的执行模型。

火山模型将所有的代数操作（如 Scan, Filter, Project, Join）抽象为一组通用的算子（Operator）。每个算子都实现了统一的接口：

  • Init()：初始化算子状态（如分配内存、打开文件句柄）。
  • Next()：向下游算子请求并返回一个元组（Tuple）。当没有更多数据时返回 False。

执行流：拉取式管道 (Pull-based Pipelining)

执行过程是一个自顶向下的函数调用链。查询计划树的根节点（通常是 Result Printer）调用 Next()，该调用会递归地传递给子节点，直到叶子节点（通常是 Scan 算子）。

  • 数据流向：数据像火山岩浆一样，从底层的叶子节点被"拉（Pull）“到顶层。
  • 优势：
    • 低耦合与模块化：任意算子可以自由组合，极大地简化了复杂查询计划的构建。
    • 流水线执行 (Pipelining)：数据在算子间流动时无需落地存储。对于 Filter 或 Projection 等操作，一个 Tuple 处理完即可立即交给上层，无需等待所有数据处理完毕，显著降低了内存峰值。
  • 劣势与瓶颈：
    • 虚函数开销：每处理一个 Tuple 都需要经历多层虚函数调用（Virtual Function Call），导致 CPU 指令流水线中断和分支预测失败。
    • 缺乏局部性：一次只处理一行数据，无法有效利用 CPU 的 L1/L2 缓存，也难以利用 SIMD 指令进行向量化加速。这也是现代 OLAP 数据库转向向量化执行（Vectorized Execution） 的主要原因。

算子实现

扫描算子 (Scan Executors)

  • 顺序扫描 (SeqScan)：遍历表堆（Table Heap）。它持有 Buffer Pool 的页面锁，通过迭代器逐行读取 Tuple。为了避免长时间锁表，通常采用Crabbing（螃蟹锁） 机制，即读取完一个 Page 后立即释放锁，再获取下一个 Page 的锁。
  • 索引扫描 (IndexScan)：利用第二章实现的 B+ 树迭代器。通过索引快速定位 RID（Record ID），再回表查询完整 Tuple。这体现了索引引擎与执行引擎的交互。

修改算子 (Insert/Delete)

修改操作涉及两个层面的更新：表数据（Table Heap） 和索引数据（Index）。

  • 一致性维护：系统必须保证表数据与索引数据的一致性。通常先更新表堆获取新的 RID，再将 (Key, RID) 插入所有相关的索引中。
  • 写放大：一个简单的 INSERT 可能引发多次 B+ 树的插入操作（视索引数量而定），这是写密集型场景下的性能瓶颈所在。

连接算子 (Join)

Join 是关系型数据库中最耗时的操作之一。系统实现了多种 Join 策略以适应不同的数据规模。

嵌套循环连接 (Nested Loop Join, NLJ)

这是最基础的实现。对于左表（Outer Table）的每一行，遍历右表（Inner Table）的所有行进行匹配。

  • 写放大：$O(N \times M)$。
  • 复杂度：仅适用于极小的数据集。在没有索引的情况下，性能极差。

索引嵌套循环连接 (Index Nested Loop Join, INLJ)

当右表的连接字段上有索引时，优化器会选择 INLJ。

  • 适用场景：对于左表的每一行，利用右表的索引进行查找，而非全表扫描。
  • 机制：$O(N \times \log M)$。这体现了索引下推（Index Pushdown） 的重要性，将计算压力下沉到了存储层。

哈希连接 (Hash Join)

虽然基础实验主要涉及 NLJ，但工业界处理大表等值连接（Equi-Join）的标准做法是 Hash Join。

  • 复杂度：遍历较小的表，建立内存哈希表。
  • Build Phase：遍历较大的表，在哈希表中探测匹配项。
  • Probe Phase：复杂度降为 $O(N + M)$，在内存充足时性能远超 NLJ。
  • 分治：内存不足时，可以利用分治来优化。

聚合 (Aggregation) 与流水线阻断

聚合操作（如 SUM, COUNT, MAX）是典型的优势。

  • 流水线阻断者 (Pipeline Breaker)：算子无法在处理完一个 Tuple 后立即输出结果（例如，计算平均值必须等到读取完所有数据）。因此，Next() 方法在第一次被调用时，通常会一次性消耗所有子节点的输入，构建哈希表计算结果，然后将结果缓存。后续的 Next() 调用则是从缓存中逐条返回结果。
  • 阻断原理：使用非持久化的内存哈希表（In-memory Hash Table）维护分组键（Group By Key）到聚合值（Aggregate Value）的映射。

查询优化器 (Query Optimizer)

优化器的作用是将逻辑计划（Logical Plan）转换为最高效的物理计划（Physical Plan）。本系统实现了一个基于规则（Rule-based）的优化器。

规则驱动优化

系统通过遍历查询树，匹配特定的模式（Pattern）并进行重写。

  • Top-N 优化 (Sort + Limit -> TopN)：
    • 原始计划：ORDER BY x LIMIT k。默认做法是先对全量数据进行排序（$O(N \log N)$），然后取前 k 个。
    • 优化规则：当优化器检测到 Limit 算子紧跟在 Sort 算子之后时，会将它们合并为一个 TopN 算子。
    • 物理实现：使用堆（Heap）/ 优先队列算法。维护一个大小为 k 的堆，只需一次遍历即可得到结果，时间复杂度降低为 $O(N \log k)$。这在 $k \ll N$ 的场景下有数量级的性能提升。

其他常见优化

  • 谓词下推 (Predicate Pushdown)：将 Filter 算子尽可能下推到 Scan 算子上方，尽早过滤数据，减少后续 Join 或 Aggregate 的数据量。
  • 列裁剪 (Column Pruning)：只读取上层算子真正需要的列，减少 I/O 和内存拷贝开销。

并发控制 (Concurrency Control)

在多线程环境下，如何保证多个事务并发执行时数据的正确性（ACID 中的 Isolation），是数据库内核最核心的挑战之一。本系统通过实现锁管理器（Lock Manager） 和两阶段锁协议（2PL） 来解决读写冲突与写写冲突。

核心理论：两阶段锁协议 (2PL)

为了保证并发调度是"可串行化"的（即并发执行的结果等价于某种串行执行的结果），事务对锁的使用必须遵循严格的纪律。

协议定义

两阶段锁将事务的生命周期划分为两个截然不同的阶段：

  1. 增长阶段 (Growing Phase)：事务可以申请获得任何类型的锁（读锁或写锁），但不能释放任何锁。
  2. 收缩阶段 (Shrinking Phase)：一旦事务释放了任何一把锁，它就进入了收缩阶段。在此阶段，事务只能释放锁，绝不能再申请新锁。

核心意义：2PL 从理论上保证了只要所有事务都遵守该协议，生成的调度历史就是可串行化的，从而保证了数据的一致性。

[!NOTE] 两阶段提交协议

两阶段提交协议（Two-Phase Commit, 2PC）是一种分布式事务一致性协议，用于确保跨多个节点的事务要么全部成功提交，要么全部回滚，从而维持 ACID 中的原子性（Atomicity）和一致性（Consistency）。

它分为两个阶段：

  • 准备阶段（Prepare Phase）：协调者（Coordinator）向所有参与者（Participants）发送 PREPARE 请求；各参与者执行事务操作并写入 undo/redo 日志，然后回复 YES（可提交）或 NO（中止）。
  • 提交阶段（Commit Phase）：若所有参与者都返回 YES，协调者发送 COMMIT；否则发送 ABORT。参与者据此持久化或回滚，并反馈完成状态。

工程实现：强严格两阶段锁 (SS2PL)

在实际工程（包括 BusTub）中，为了避免级联回滚（Cascading Aborts）——即一个事务的回滚导致读取了它脏数据的其他事务也被迫回滚——通常采用 Strong Strict 2PL。

  • 规则：所有的排他锁（写锁） 必须保留到事务结束（Commit 或 Abort）那一刻才能释放。
  • 收益：确保了如果事务 A 修改了数据，其他事务只有在 A 提交后才能读取该数据，彻底杜绝了脏读引发的连锁反应。

锁管理器与隔离级别 (Lock Manager & Isolation Levels)

锁管理器是并发控制的调度中心，它负责维护锁表（Lock Table），处理加锁请求，并根据隔离级别决定何时释放锁。

多粒度锁 (Multiple Granularity Locking)

为了平衡并发度与系统开销，系统引入了意向锁（Intention Lock） 机制，支持表级与行级锁共存。

  • 问题背景：如果没有意向锁，当事务想要锁住整张表（例如 LOCK TABLE 或全表扫描）时，它必须遍历每一行，检查是否有其他事务锁住了某一行。这效率极低。
  • 解决方案：
    • IS (意向共享)：表示事务打算读取表中的某些行。
    • IX (意向排他)：表示事务打算修改表中的某些行。
    • 协议：事务在锁行之前，必须先锁表。例如，要锁某一行（X 锁），必须先获得该表的 IX 锁。
  • 效果：系统在判断"能否锁表"时，只需检查表上是否有冲突的意向锁，无需检查具体的行锁，极大地提升了冲突检测效率。

隔离级别的实现策略

不同的隔离级别本质上是对读锁（S 锁）持有时间的权衡。写锁（X 锁）通常都持有到事务结束。

  1. 可重复读 (Repeatable Read, RR)
    • 实现：事务在读取数据时加 S 锁，并一直持有到事务结束。
    • 效果：保证在同一个事务内，多次读取同一行数据，内容始终一致（因为其他事务无法获取 X 锁来修改它）。
  2. 读已提交 (Read Committed, RC)
    • 实现：事务在读取数据时加 S 锁，但读取完成后立即释放，不等到事务结束。
    • 效果：允许其他事务在当前事务两次读取之间修改数据，从而导致不可重复读，但显著提升了读操作的并发度（锁持有时间短）。
  3. 读未提交 (Read Uncommitted, RU)
    • 实现：读操作通常不加锁（或仅加极短的锁）。
    • 效果：允许脏读，并发度最高，但安全性最低。

死锁处理：检测与恢复

在 2PL 协议下，死锁（Deadlock）是无法通过协议本身避免的（例如 T1 锁 A 等 B，T2 锁 B 等 A）。解决死锁通常有两种思路：死锁预防和死锁检测。本系统采用了死锁检测方案。

死锁检测 (Deadlock Detection)

这是 BusTub 的实现方式。Lock Manager 在后台维护一个独立的线程，周期性地执行以下步骤：

  1. 构建等待图 (Wait-for Graph)：遍历所有被阻塞的事务请求。如果事务 T1 正在等待事务 T2 持有的锁，则在图中添加一条 $T_1 \rightarrow T_2$ 的有向边。
  2. 环检测：使用深度优先搜索（DFS）算法检测图中是否存在环。如果存在环，说明发生了死锁。
  3. 受害者选择 (Victim Selection)：为了打破死锁，必须中止（Abort）环中的一个事务。通常选择 “最年轻” （事务 ID 最大）的事务作为受害者，因为它的回滚代价通常最小。
  4. 恢复：被选中的事务状态被置为 ABORTED，并唤醒其线程执行回滚操作，释放其持有的所有锁，从而让其他事务继续运行。

[!NOTE] 死锁预防 (Deadlock Avoidance)

  • Wait-Die 策略：基于时间戳。老事务等新事务（Wait），新事务遇老事务直接自杀（Die）。
  • Wound-Wait 策略：基于时间戳。老事务强行抢占新事务资源（Wound），新事务等老事务（Wait）。
  • 资源有序分配：强制所有事务按照全局固定的顺序（如 Primary Key 顺序）申请锁，从根本上破坏"循环等待"条件。

MySQL 事务

特性含义解释与示例
Atomicity
原子性		事务是一个不可分割的原子单位，所有操作要么全部成功，要么全部失败。这是事务最核心的特性。靠 Undo Log 实现。如果事务中途失败，数据库会利用 Undo Log 将已经执行的操作完全撤销，就像这个事务从来没执行过一样。
Consistency
一致性		事务执行前后，数据库都必须从一个一致性状态转变到另一个一致性状态。这是事务的最终目的。一致性包括预定义的数据规则、约束、触发器等等。例如，转账前后，两个账户的总金额必须保持不变。原子性、隔离性、持久性都是为了保障一致性而存在的手段。
Isolation
隔离性		并发事务之间的操作是相互隔离的，一个事务的执行不应影响其他事务。这是并发控制的核心。数据库通过锁机制和 MVCC 来实现隔离性。但完全隔离会影响性能，因此提供了不同的隔离级别供用户在高性能和高一致性之间做权衡。
Durability
持久性		一旦事务提交，它对数据库的修改就是永久性的，即使系统发生故障也不会丢失。靠 Redo Log 实现。提交事务时，数据变更可能还没真正写到磁盘的数据文件中，但一定会先写入 Redo Log。即使数据库宕机，重启后也能根据 Redo Log 重新恢复已提交的事务数据。
  1. 脏读：一个事务读到了另一个未提交事务修改的数据。
  2. 不可重复读：一个事务内，两次读取同一条数据，结果不一样（因为另一个已提交的事务在中间修改了该数据）。
  3. 幻读：一个事务内，两次执行相同的查询，返回的记录数不一样（因为另一个已提交的事务在中间插入或删除了数据）
隔离级别脏读不可重复读幻读实现方式简述
读未提交
(READ UNCOMMITTED)		❌ 可能发生❌ 可能发生❌ 可能发生几乎不加锁，性能最高，但问题最多，基本不用。
读已提交
(READ COMMITTED)		✅ 避免❌ 可能发生❌ 可能发生每个 SELECT 都会生成一个新的快照（ReadView），所以总能读到其他事务已提交的修改。解决了脏读。
可重复读
(REPEATABLE READ)		✅ 避免✅ 避免❌ 可能发生
（但 InnoDB 解决了）		MySQL InnoDB 默认级别。事务开始时生成一个快照，整个事务期间都使用这个快照，因此多次读取结果一致。
可串行化
(SERIALIZABLE)		✅ 避免✅ 避免✅ 避免通过强制事务串行执行（加锁）来实现最高隔离性。性能最低，一般只在极端场景下使用。

隔离级别：两读两可。

非常重要的补充：MySQL InnoDB 对幻读的解决

在 可重复读 隔离级别下，InnoDB 通过 Next-Key Lock（临键锁）机制很大程度上避免了幻读。Next-Key Lock 是行锁（锁定当前行）和间隙锁（锁定行之间的范围）的结合。

例子： 事务 A 执行 SELECT * FROM players WHERE level > 50 FOR UPDATE;（加锁的读）。 InnoDB 不仅会锁住所有 level > 50 的现有行，还会锁住 level > 50 的这个范围（间隙）。 这样，事务 B 试图插入一个 level=60 的新玩家时，就会被阻塞，直到事务 A 提交。这样就避免了幻读。

注意：FOR UPDATE 这类加锁读会触发 Next-Key Lock，而普通的快照读（不加锁）依靠 MVCC 来保证一致性，理论上在极端并发下仍可能遇到幻读，但概率极低。因此我们通常说 InnoDB 在 RR 级别下解决了幻读问题。

MVCC

MVCC 的全称是 Multi-Version Concurrency Control，中文是多版本并发控制。为了避免读写操作互相阻塞，数据库为每一行数据保留多个历史版本（快照）。当一个事务要读取数据时，它会看到在它开始之前就已经提交的数据版本，而不是当前可能正在被其他事务修改的最新版本。

主要依赖三个核心概念：隐藏的列、Undo log、Read View

隐藏的列

InnoDB 为每一行数据都自动添加了两个隐藏的字段（其实还有第三个，DB_ROW_ID，这里不讨论）：

  • DB_TRX_ID (6 字节)：最后修改此行数据的事务 ID。每当一个事务对某行数据进行插入（INSERT） 或更新（UPDATE） 操作时，就会将自己的事务 ID 填入这个字段。
  • DB_ROLL_PTR (7 字节)：回滚指针。这个指针指向该行数据在 Undo Log 中的上一个历史版本。

每一行数据，通过 DB_ROLL_PTR 指针，就形成了一个单向链表，链表的每个节点就是该行数据的一个历史版本。

Undo Log

  • 是什么：撤销日志，用于事务回滚和 MVCC。
  • 作用：当一行数据被更新时，InnoDB 会先将这行数据的旧版本完整地拷贝到 Undo Log 中，然后再修改数据页中的这行数据，同时将新的 DB_TRX_ID 和 DB_ROLL_PTR 指向刚刚存入 Undo Log 的旧版本记录。
  • 版本链：通过 DB_ROLL_PTR，当前数据页中的最新数据可以找到它的上一个版本，上一个版本又可以找到上上个版本，这样就形成了一个数据版本链。链表的头部是最新的记录，尾部是最老的记录。

Read View（读视图）

  • 是什么：Read View 是事务在执行快照读（普通 SELECT）时产生的，它定义了当前事务能看到哪个版本的数据。
  • 关键组成部分：一个 Read View 主要包含以下几部分：
    • m_ids： 生成 Read View 时，系统中所有活跃（未提交）的事务 ID列表。
    • min_trx_id： m_ids 中最小的那个事务 ID。
    • max_trx_id： 生成 Read View 时，系统应该分配给下一个新事务的 ID。（注意：它并不是 m_ids 中的最大值，而是已创建的最大 ID+1）。
    • creator_trx_id： 创建这个 Read View 的当前事务自己的 ID。

如果当前版本不可见，就顺着回滚指针 DB_ROLL_PTR 找到上一个历史版本，重新执行上述判断规则，直到找到第一个对自己可见的版本为止。

机制针对的操作类型工作原理解决的幻读场景
MVCC快照读
(Snapshot Read)
例如：SELECT …		通过 Read View 和 Undo Log 版本链，为事务提供一个稳定的数据快照。在这个快照里，第一次查询后，看不到其他事务新插入并提交的数据。防止事务看到幻影行。例如：事务 A 两次 SELECT，由于复用同一个 Read View，即使事务 B 插入新行并提交，事务 A 也看不到，从读取视角避免了幻读。
临键锁
(Next-Key Lock)		当前读
(Current Read)
例如：SELECT … FOR UPDATE
UPDATE …
DELETE …		通过 记录锁（行锁） + 间隙锁（Gap Lock） 的组合，锁定一个范围。不仅锁住满足条件的现有记录，还锁住记录之间的"间隙”，防止在这个范围内插入新的数据。防止事务产生幻影行。例如：事务 A 执行 SELECT … FOR UPDATE，临键锁会锁定一个范围。事务 B 试图在这个范围内插入新行时会被阻塞，直到事务 A 提交。从写入视角避免了幻读。
  1. MVCC (解决"看见"的问题)：它的目标是保证读一致性。让读操作（SELECT）不受写操作（UPDATE, INSERT, DELETE）的影响，可以看到一个稳定的视图。它让读操作"看不见"幻影行，但并不阻止其他事务创建幻影行。
  2. 临键锁 (解决"产生"的问题)：它的目标是保证写操作的独占性和数据逻辑的正确性。当你的当前读操作（比如 SELECT … FOR UPDATE）意图基于当前查询结果进行后续更新时，必须确保在本次事务结束前，这个查询结果集不能被其他事务改变（不能插入新的行）。它通过物理上的加锁，直接阻止了幻影行的产生。

总结

通过 CMU 15-445 的四个 Project，从零实现了面向磁盘的嵌入式关系型数据库核心：

  1. 基于可扩展哈希 + LRU-K 缓冲池，实现高并发页管理与抗扫描污染；
  2. 构建线程安全的B+ 树索引，集成螃蟹锁（Latch Crabbing）与乐观分裂优化；
  3. 设计火山模型执行引擎，支持 SeqScan/IndexScan/Join/Aggregation 等算子及 Top-N 等规则优化；
  4. 实现基于两阶段锁（2PL）的锁管理器，支持多粒度锁、死锁检测与 RR/RC 隔离级别。

完整覆盖存储、索引、执行与并发控制四大内核层。