三藏签名
< Back to projectsCMU 15445: 数据库开发

CMU 15445: 数据库开发

C++

用C++实现数据库的关键模块

前言

CMU 15-445/645 是卡内基梅隆大学数据库组的经典课程，由 Andy Pavlo 教授主讲。Fall 2023 学期的五个编程 Project 围绕 BusTub 教学数据库系统展开，从 C++ 热身一路深入到 MVCC 并发控制，覆盖了数据库内核的核心模块。

本文以代码仓库的实际实现为基础，按 Project 顺序完整复盘每个项目的关键设计与技术要点。

Project #0: C++ Primer — COW Trie & 并发的 KV Store

目标：C++ 热身，熟悉 BusTub 代码风格。

任务

内容

Task 1

实现 Copy-on-Write Trie。所有修改操作不原地改节点，而是克隆路径上所有节点并返回新 root。插入 ("ad", 2) 时，复用原树中未修改的子节点，仅新建被修改路径上的节点

Task 2

实现线程安全的 TrieStore。用读写锁保护 root 指针，Put/Remove 操作持有写锁，Get 持有读锁，保证多线程并发安全

Task 3

调试练习

Task 4

实现 upper() / lower() SQL 字符串函数并注册到 BusTub SQL 框架

核心收获：COW 数据结构在不破坏旧版本的前提下实现"写时复制"，天然适合快照隔离；读写锁在并发 KV 场景下的粒度和性能权衡。

Project #1: Buffer Pool Manager — 磁盘页的缓存层

目标：实现数据库的缓冲池，在内存和磁盘之间透明地管理数据页。

Task 1: LRU-K Replacement Policy

E = FIFO-ordered entries (accesses < K)
R = LRU-ordered entries (accesses >= K)

evict candidate = max(backward k-distance) 
                  tie-break: earliest overall timestamp in E

LRU-K 不是简单的"最久未使用"，而是计算每个页的第 K 次历史访问距现在的时间差。访问不足 K 次的页给予 +∞ 距离优先淘汰。这解决了传统 LRU 被"一次性扫描"污染的问题。

核心数据结构：每个 frame 维护一个访问历史队列 (std::deque<timestamp_t>)，外层按 (is_evictable, k_distance) 排序决定淘汰顺序。

Task 2: Disk Scheduler

后台 worker 线程 + 共享请求队列（Channel），将磁盘 I/O 从调用线程中解耦：

调用线程                          DiskScheduler 后台线程
  │                                  │
  ├─ Schedule(request)               │
  │  promise → channel               │
  │                                  ├─ channel.pop()
  │                                  ├─ DiskManager.Read/Write()
  │                                  ├─ promise.set_value()
  │  future.get() ←───────────────── │
  ▼                                  ▼

用 std::promise/future 做回调同步，保证调用线程能感知 I/O 完成。

Task 3: Buffer Pool Manager

BufferPoolManager
  ├─ page_table_: map<page_id → frame_id>   ← 逻辑页到物理帧映射
  ├─ pages_: Page[pool_size]                ← 物理帧数组
  ├─ free_list_: deque<frame_id>            ← 空闲帧队列
  ├─ replacer_: LRUKReplacer                ← 淘汰策略
  └─ disk_scheduler_: DiskScheduler         ← 磁盘调度

核心接口：

  • FetchPage(page_id)：先从 page_table_ 找，命中则 pin 并记录访问；miss 则分配新帧（优先 free_list，其次 Replacer 淘汰），调度磁盘读取

  • UnpinPage(page_id, is_dirty)：解除 pin，标记 dirty，更新 Replacer 的 evictable 状态

  • NewPage：分配新 page_id，返回可写入的帧

  • FlushPage / FlushAllPages：强制写回磁盘

关键并发设计：page_table_ 用大锁保护，每个 Page 有独立的 rwlatch_（读写锁）。FetchPage 时会自动获取读锁，后续手动 RLatch/WLatch 升级保护页内容。

Project #2: Extendible Hash Index — 磁盘哈希索引

目标：基于 P1 的 Buffer Pool，构建支持并发读写的磁盘可扩展哈希索引。

Task 1: Read/Write Page Guards — RAII 页面保护

P1 中需要手动 UnpinPage 和 Unlatch，极易泄漏。Page Guard 用 RAII 惯用法自动管理：

// BasicPageGuard: 析构时自动 UnpinPage
// ReadPageGuard: 析构时自动 RUnlatch + UnpinPage
// WritePageGuard: 析构时自动 WUnlatch + UnpinPage (标记 dirty)

auto guard = bpm->FetchPageBasic(page_id);
auto read_guard = guard.UpgradeRead();   // 获取读锁
auto write_guard = read_guard.UpgradeWrite(); // 锁升级：R→W

锁升级（Upgrade）：先确保自己是该页面唯一的读者，然后释放读锁并获取写锁。在升级前会再次从 buffer pool 获取该页，保证中途未被淘汰。如果读到不同的 Page 对象，说明发生了并发冲突，需要重试。

Task 2: Extendible Hash Table — 三级结构

Header Page (global depth ≤ 9)
    │
    ▼
Directory Pages (local depth ≤ 9, 每个最多 512 entries)
    │
    ▼
Bucket Pages (每个最多 511 个 KV pair)

核心算法：

操作

步骤

Insert

① 计算 hash，查找目录→桶 ② 桶满则 Split：目录扩容或重排，桶分裂重新分配 ③ 插入

GetValue

hash → 目录查找 → 桶内线性查找

Remove

hash → 目录查找 → 桶内删除。可能触发 Merge：两个兄弟桶可以合并时收缩结构

Split

桶满 + local_depth < global_depth → 在目录中创建新映射，两个桶各分一半

并发设计：使用 header page 的大锁根目录互斥锁保护全局目录修改。实际实现中，普通读写依赖 page guard 的 latch 机制保证正确性。

Project #3: Query Execution — 查询执行引擎

目标：实现 Volcano 迭代器模型的所有算子，构建完整的查询执行流水线。

执行模型

Volcano 模型（拉取模型）：

每个 executor 实现 Init() + Next(Tuple*, RID*):
  - Next() 返回 true 表示有数据，false 表示结束
  - 内部调用 child_executor_->Next() 逐行拉取

迭代器模式天然支持流水线（pipelining），不需要物化中间结果。

Task 1: Access Method Executors

算子

关键逻辑

SeqScan

遍历 table heap，对每个 tuple 检查 predicate，通过 RID 获取字段值

Insert

调用 TableHeap::InsertTuple，更新索引

Delete

从 child 拉取 RID，调用 TableHeap::MarkDelete，更新索引

Update

从 child 拉取 RID，生成新 tuple，UpdateTupleInPlace + 索引维护

IndexScan

从索引查找 key，获取 RID，定位 table heap 中的 tuple

SeqScan → IndexScan 优化规则

当 WHERE 条件匹配索引时，换用 IndexScan 减少扫描

Task 2: Aggregation & Join

  • Aggregation：Init() 中一次性拉取所有 child 数据，按 group-by 列哈希聚合（SimpleAggregationHashTable），Next() 逐个吐出

  • NestedLoopJoin：外层表驱动，每行和内表做交叉积，匹配 Join predicate 通过则输出。支持 LEFT/RIGHT/INNER

  • NestedIndexJoin：优化版——外层每行的 join key 直接 probe 内层索引，无需全遍历内表

Task 3: Hash Join

Build Phase (Init):
  构建哈希表: key = left join key → value = left tuple values

Probe Phase (Next):
  右表每行 probe 哈希表，命中则拼接输出
  需要维护 hash table iterator 以支持同 key 多 match

Task 4: Sort, Limit, Window, Top-N

算子

实现要点

Sort

Init() 收集全部数据，按 ORDER BY + 比较器排序，维护游标

Limit

包装 child，计数返回指定行

Top-N

Init() 收数据入优先队列，Next() pop。Sort + Limit 的等价优化

Window

Init() 按 PARTITION BY 分组，组内排序，计算 ROW_NUMBER()、RANK()、聚合窗口函数

Top-N-Per-Group

每组维护优先队列，Next() 按时序跨组输出——通过 leaf_child_ 获取新组数据

Project #4: Concurrency Control — MVCC 快照隔离

目标：在 BusTub 上实现完整的 MVCC 协议，支持 Snapshot Isolation。

这是五个 Project 中工作量最大、最考验理解深度的一个。

Task 1: Timestamps

每事务两个时间戳：

Begin():  read_ts = last_commit_ts_        // 事务开始时的最新提交 ts
Commit(): commit_ts = last_commit_ts_ + 1  // 提交时单调递增
         last_commit_ts_++

Watermark（最低活跃 read_ts）用 O(1) 哈希表 + 有序列表实现，用于 GC 时判断哪些 undo log 可以回收。

Task 2: Storage Format & Version Chain

三种数据存储位置：

┌──────────────────┐
│ Table Heap (磁盘) │ ← 永远存最新版 tuple
│ meta.ts_ = ts    │
└──────┬───────────┘
       │ VersionUndoLink.prev_ (内存映射)
       ▼
┌──────────────────────────┐
│ version_info_ (内存)      │ ← 每个 RID → 链头 VersionUndoLink
│ = map<page_id,            │
│    PageVersionInfo>       │
│   └─ map<slot, VerUL>    │
└──────┬───────────────────┘
       │ UndoLink(txn_id, log_idx)
       ▼
┌──────────────────────────┐
│ Transaction.undo_logs_    │ ← 各事务私有缓冲区
│ = vector<UndoLog>        │
│   ├─ modified_fields_    │
│   ├─ tuple_ (部分列)      │
│   ├─ ts_                 │
│   └─ prev_version_       │
└──────────────────────────┘

Undo Log 只存被修改的列（partial update），节省空间。版本链通过 prev_version_ 单向串联，可跨事务。

Tuple Reconstruction（ReconstructTuple）：从 base tuple 开始，反向应用 undo log 链，恢复出指定时间点 tuple：

for undo_log in undo_logs (t_newest → t_oldest):
  for each column:
    if undo_log.modified_fields_[i]:
      tuple[i] = undo_log.tuple_[i]  // 用旧值覆盖
    else:
      keep tuple[i]                  // 未修改，保留

SeqScan 重建逻辑（GetTuple）：

base tuple ts:
  ├─ ts ≤ read_ts & not deleted → 直接返回
  ├─ ts == my txn_temp_ts       → 直接返回（自己写的）
  ├─ ts > read_ts               → 沿版本链回溯到 ≤ read_ts
  └─ ts 是其他未提交 txn        → 沿版本链回溯

Task 3: MVCC Executors

算子

要点

Insert

TupleMeta{txn_temp_ts, false}，创建空 VersionUndoLink 哨兵，加入 WriteSet

Commit

遍历 WriteSet，将 ts_ 从 txn_temp_ts 替换为 commit_ts；in_progress_=false

Update

先检测写-写冲突 → UpdateTupleDiffTxn（异事务）或 UpdateTupleSameTxn（同事务）

Delete

同 Update，但 new_tuple 长度为 0 → is_deleted=true

更新核心流程（UpdateTupleDiffTxn）：

1. CAS 锁 VersionLink（in_progress_: false→true）
      ↓ 抢到锁
2. 双重检查冲突（锁住后再 check ts）
      ↓ 无冲突
3. GenUndoLog(old→new 差异)     ← 只有变化列
4. undo_log.prev_version_ = 旧 VersionLink.prev_  ← 串联版本链
5. AppendUndoLog(undo_log)      ← 写事务私有缓冲区
6. UpdateVersionLink(rid, 新 UndoLink)             ← 更新链头
7. UpdateTupleInPlace(new_tuple)                   ← 写 table heap

Task 4: Primary Key Index

插入三步法（有并发竞争窗口）：

1. ScanKey → 检查主键是否存在
2. InsertTuple → 创建 table heap tuple
3. InsertEntry → 插入索引条目
   ↑ TOCTOU窗口：1和3之间可能被其他事务抢先

核心规则：索引条目一旦创建永不删除（即使数据被 delete），始终指向同一 RID。Insert 时如遇已删除 tuple，走 Update 覆盖而非新建 RID。

in_progress_ 并发控制：多事务同时修改同一 RID 的版本链时，通过 CAS（compare-and-swap）保证只有一个能成功：

  • 成功者：in_progress_=true，追加 undo log，更新链头

  • 失败者：自旋等待或 abort（TAINTED）

Garbage Collection：stop-the-world 模式下，计算 watermark（最低 read_ts），删除所有不包含 watermark 可见 undo log 的已提交事务。

技术全景图

                         Project 0          Project 1          Project 2
                         ─────────          ─────────          ─────────
                         COW Trie           Buffer Pool        Ext Hash Index
                         KV Store           管理磁盘页缓存        三级目录哈希表
                         C++ Primer         LRU-K 淘汰          Page Guard RAII
                                            Disk Scheduler     并发读写索引

                         Project 3          Project 4
                         ─────────          ─────────
                         Query Execution    Concurrency Control
                         Volcano Model      MVCC + SI
                         算子: Scan/Join     Version Chain
                         /Agg/Sort/Window   Undo Log + CAS
                         Top-N/Hash Join    Timestamps + GC
                         SeqScan→IndexScan  主键索引 + 并发竞争

核心收获

  1. C++ 工程能力：RAII、移动语义、智能指针、线程安全（mutex/shared_mutex/latch）、原子操作（atomic、CAS）

  2. 存储层：Buffer Pool 的 pin/unpin 引用计数、LRU-K 防扫描污染、异步磁盘调度

  3. 索引层：可扩展哈希的动态分裂/合并、目录结构、并发安全的桶操作

  4. 执行层：Volcano 流水线模型、算子组合 (Filter→Join→Agg→Sort→TopN)、优化器规则

  5. 事务层：MVCC 版本链、Snapshot Isolation、时间戳分配、写-写冲突检测、CAS 互斥、Stop-the-world GC

Comments

Discuss this project

Emoji supported. Comments appear immediately.

No comments yet.