简介这份资源是CMU 15-445数据库系统课程的实验代码与学习笔记合集面向希望深入理解数据库内核实现的高校学生与后端开发者。内容围绕缓冲池管理器、B树索引、并发控制与记录恢复机制展开并配有C11编程实践、课程视频总结与实验指导建议适合在完成课程作业或自研存储引擎时对照参考。压缩包共121个文件以55个C头文件与46个cpp源文件为主体另有6个md笔记、5个txt说明及少量C、cc、png与docx文档整体约2.64MB目录结构便于按实验模块检索。目前已有66人学习。读者可从中获取B树页面与锁管理器的实现思路、测试用例组织方式以及故障恢复的日志设计要点为构建高性能、高可靠的数据库系统打下基础。1. CMU 15-445 实验到底在练什么从缓冲池到恢复的完整数据库内核链路如果你写过 CRUD 业务代码却说不清一条SELECT从磁盘页到结果集之间到底经过了几层内存结构那 CMU 15-445 的实验就是冲着你来的。它不教你写 SQL而是让你亲手实现一个能跑起来的存储引擎缓冲池管理器负责把磁盘页换进换出B 树索引决定查询走哪条路径并发控制保证多事务同时读写不互相踩踏记录恢复机制让系统崩溃后还能把数据捞回来。这四个模块串起来就是数据库系统概论里那些抽象概念的真实落地。这套实验代码通常用 C11 编写配合课程视频和实验指导建议食用效果最好。适合谁适合已经会写业务代码、但想搞清楚数据库系统原理底层怎么运转的开发者也适合正在准备数据库系统实验一这类课程作业的学生。下面我按实际动手顺序把每个模块的关键实现和踩坑点拆开讲。2. 缓冲池管理器LRU-K 替换策略与页锁的工程实现缓冲池管理器是整个存储引擎的内存入口。所有对磁盘页的读写都要先经过它它决定哪些页留在内存、哪些页被换出。CMU 15-445 的实验通常要求实现 LRU-K 替换策略而不是简单的 LRU。原因很直接LRU 在顺序扫描场景下会把热点页全部挤出去而 LRU-K 通过记录每个页最近 K 次访问时间能识别出真正的热数据。2.1 为什么选 LRU-K 而不是 LRU一个反直觉的替换场景假设缓冲池有 3 个页框访问序列是 A、B、C、A、D、E、A。纯 LRU 在访问 D 时会把 B 换出访问 E 时把 C 换出等再次访问 A 时 A 还在看起来没问题。但如果序列变成 A、B、C、D、E、A纯 LRU 在访问 E 时会把 A 换出再次访问 A 就触发磁盘 IO。LRU-K 因为记录了 A 的两次历史访问会优先保留 A 而换出只访问过一次的 D 或 E。这个差异在顺序扫描大表时特别明显。全表扫描会把所有页都读一遍纯 LRU 会把之前的热点页全部淘汰导致后续查询命中率暴跌。LRU-K 通过 K 次访问历史过滤掉这种一次性访问保护真正的热数据。2.2 实现 LRU-K 的核心数据结构与代码骨架实现 LRU-K 需要两个关键结构一个记录每个页帧当前访问历史的队列另一个记录页帧是否可被替换的标记。常见做法是用一个std::unordered_mappage_id_t, std::dequesize_t存每个页的最近 K 次访问时间戳再用一个可替换页帧列表按最早的第 K 次访问时间排序。// 简化版 LRU-K 替换器核心逻辑 class LRUKReplacer { public: explicit LRUKReplacer(size_t num_frames, size_t k) : k_(k) { // 初始化每个帧的访问历史队列 for (size_t i 0; i num_frames; i) { access_history_[i] std::dequesize_t(); } } // 记录一次访问时间戳由外部递增传入 void RecordAccess(frame_id_t fid, size_t timestamp) { auto history access_history_[fid]; history.push_back(timestamp); // 只保留最近 K 次 if (history.size() k_) { history.pop_front(); } // 如果达到 K 次访问标记为可替换候选 if (history.size() k_) { evictable_[fid] true; } } // 淘汰一个页帧优先选第 K 次访问时间最早的 bool Evict(frame_id_t *frame_id) { size_t earliest SIZE_MAX; bool found false; for (auto [fid, history] : access_history_) { if (!evictable_[fid] || history.size() k_) continue; // 比较第 K 次访问时间即队列最前面的时间戳 if (history.front() earliest) { earliest history.front(); *frame_id fid; found true; } } if (found) { access_history_.erase(*frame_id); evictable_.erase(*frame_id); } return found; } private: size_t k_; std::unordered_mapframe_id_t, std::dequesize_t access_history_; std::unordered_mapframe_id_t, bool evictable_; };这段代码的关键参数是k_通常取 2。K 越大对历史访问的过滤越严格但冷启动阶段访问次数不足 K 次的页无法被淘汰可能导致缓冲池暂时无法换入新页。实际实现时还需要配合页锁读页时加读锁写页时加写锁淘汰前必须确认页的引用计数为 0。2.3 页锁与引用计数避免并发访问时的悬空指针缓冲池管理器必须处理多线程并发访问。一个线程正在读某页时另一个线程不能把它淘汰掉。常见做法是给每个页帧维护一个pin_count_读页时加一用完减一只有pin_count_ 0的页才能被淘汰。同时用std::shared_mutex保护页帧元数据读操作加共享锁写操作加独占锁。// 获取页时的加锁与引用计数逻辑 Page *FetchPage(page_id_t page_id) { std::unique_lockstd::shared_mutex lock(latch_); // 先查页表 auto it page_table_.find(page_id); if (it ! page_table_.end()) { frame_id_t fid it-second; // 命中增加引用计数记录访问 pin_count_[fid]; replacer_-RecordAccess(fid, timestamp_); return pages_[fid]; } // 未命中需要从磁盘读入 frame_id_t fid; if (!replacer_-Evict(fid)) { return nullptr; // 缓冲池满且无可淘汰页 } // 如果被淘汰的页是脏页先写回磁盘 if (is_dirty_[fid]) { disk_manager_-WritePage(pages_[fid].GetPageId(), pages_[fid].GetData()); } // 读入新页 disk_manager_-ReadPage(page_id, pages_[fid].GetData()); page_table_[page_id] fid; pin_count_[fid] 1; is_dirty_[fid] false; replacer_-RecordAccess(fid, timestamp_); return pages_[fid]; }这里有个容易翻车的点淘汰脏页时写回磁盘的操作必须在持有锁的情况下完成否则可能两个线程同时淘汰同一页导致数据错乱。但写磁盘是慢操作长时间持锁会严重拖累并发性能。常见优化是先把脏页标记为“正在写回”释放锁后再实际写磁盘写完再重新加锁更新状态。这个细节在实验指导建议里通常不会明说但实际跑并发测试时就会暴露。3. B 树索引从页分裂到并发安全的完整实现路径B 树索引是查询加速的核心。CMU 15-445 的实验要求实现一个支持插入、删除、点查和范围扫描的 B 树而且必须保证并发安全。很多人在这一步卡住不是因为不懂 B 树原理而是因为并发场景下的页分裂和合并太容易出 bug。3.1 B 树的节点布局与插入分裂逻辑B 树的每个节点对应一个磁盘页。内部节点存 key 和子页指针叶子节点存 key 和记录 ID。插入时从根往下找到目标叶子如果叶子满了就分裂把中间 key 推到父节点。父节点如果也满了就继续往上分裂直到根节点。// B 树叶子节点插入与分裂的核心逻辑 bool InsertIntoLeaf(LeafPage *leaf, const KeyType key, const ValueType value) { // 找到插入位置 auto pos std::lower_bound(leaf-keys_.begin(), leaf-keys_.end(), key); leaf-keys_.insert(pos, key); leaf-values_.insert(leaf-values_.begin() (pos - leaf-keys_.begin()), value); // 如果没满直接返回 if (leaf-keys_.size() leaf-max_size_) { return true; } // 叶子满了需要分裂 LeafPage *new_leaf AllocateNewLeaf(); size_t mid leaf-keys_.size() / 2; // 把后半部分移到新叶子 new_leaf-keys_.assign(leaf-keys_.begin() mid, leaf-keys_.end()); new_leaf-values_.assign(leaf-values_.begin() mid, leaf-values_.end()); leaf-keys_.resize(mid); leaf-values_.resize(mid); // 维护叶子链表指针 new_leaf-next_ leaf-next_; leaf-next_ new_leaf; // 把新叶子的第一个 key 插入父节点 InsertIntoParent(leaf, new_leaf-keys_[0], new_leaf); return true; }关键参数是max_size_通常由页大小和 key/value 大小决定。比如 4KB 页key 是 8 字节整数value 是 8 字节记录 ID那么叶子节点最多存约 250 个键值对。分裂时取mid size / 2是一种常见做法但有些实现会偏向一边以减少后续分裂频率具体取决于工作负载。3.2 并发 B 树的 latch crabbing 协议并发 B 树最经典的方案是 latch crabbing从根节点开始先锁住子节点再释放父节点。读操作加读锁写操作加写锁。如果子节点是安全的不会因为这次操作分裂或合并就可以释放父节点的锁。// latch crabbing 的读路径示例 Page *FindLeafRead(const KeyType key) { Page *curr root_page_; curr-RLatch(); while (!curr-IsLeaf()) { InternalPage *internal static_castInternalPage *(curr); Page *child internal-LookupChild(key); child-RLatch(); curr-RUnlatch(); // 释放父节点读锁 curr child; } return curr; // 返回时持有叶子节点读锁 }写路径更复杂如果子节点可能分裂就不能提前释放父节点锁因为分裂需要修改父节点。常见做法是判断子节点是否“安全”——插入时如果子节点未满就是安全的删除时如果子节点超过半满就是安全的。只有安全时才释放父节点锁。这里有个血泪经验很多人在实现删除时忘了处理根节点收缩。当根节点变成只有一个子节点的内部节点时必须把那个子节点提升为新根否则树的高度会无意义地增加查询性能逐渐退化。这个 bug 在功能测试时不会暴露只有跑大规模随机插入删除才会显现。4. 并发控制MVCC 多版本并发控制与两阶段锁的取舍并发控制是数据库系统原理里最抽象的部分也是实验中最容易写出“看起来对但并发跑就错”的模块。CMU 15-445 通常要求实现基于时间戳的 MVCC 或两阶段锁2PL两者各有适用场景。4.1 MVCC 的版本链与可见性判断MVCC 的核心思想是写操作不覆盖旧数据而是生成新版本读操作根据事务开始时间戳读取可见版本。每个元组维护一个版本链链上每个版本记录创建时间戳和删除时间戳。// MVCC 可见性判断逻辑 bool IsVisible(const TupleVersion *version, txn_id_t txn_id, timestamp_t read_ts) { // 版本创建时间戳必须小于等于读时间戳 if (version-created_ts_ read_ts) return false; // 版本删除时间戳必须大于读时间戳或者未删除 if (version-deleted_ts_ ! INVALID_TS version-deleted_ts_ read_ts) { return false; } // 如果版本是自己创建的可见 if (version-creator_txn_ txn_id) return true; // 如果版本是已提交事务创建的可见 return IsCommitted(version-creator_txn_); }关键参数是read_ts通常取事务开始时的全局时间戳。写操作会创建一个新版本把旧版本的deleted_ts_设为当前事务 ID。提交时更新全局时间戳未提交事务的版本对其他事务不可见。MVCC 的优点是读不阻塞写、写不阻塞读适合读多写少的场景。缺点是版本链会越来越长需要垃圾回收机制清理不再可见的旧版本。实验里通常不要求实现完整的 GC但至少要能正确处理版本链的遍历。4.2 两阶段锁的加锁顺序与死锁检测如果实验要求实现 2PL核心是维护一个锁表记录每个事务持有哪些锁、等待哪些锁。加锁时如果冲突就等待等待图出现环就说明死锁需要选择一个事务回滚。// 两阶段锁的加锁逻辑简化版 bool AcquireLock(txn_id_t txn_id, resource_id_t rid, LockMode mode) { std::unique_lockstd::mutex lock(latch_); auto lock_request lock_table_[rid]; // 检查是否与已有锁冲突 for (auto [holder, held_mode] : lock_request.holders_) { if (holder txn_id) continue; if (IsConflict(held_mode, mode)) { // 冲突加入等待队列 lock_request.waiters_.push_back({txn_id, mode}); // 检测死锁 if (HasCycle(txn_id)) { lock_request.waiters_.pop_back(); return false; // 触发回滚 } // 等待锁释放 lock_request.cv_.wait(lock, []() { return CanGrant(lock_request, txn_id, mode); }); } } lock_request.holders_[txn_id] mode; return true; }死锁检测用等待图每个事务是节点等待关系是边用 DFS 找环。发现环后选择代价最小的事务回滚通常是修改数据最少或优先级最低的那个。2PL 的优点是实现相对直接缺点是并发度低读写互相阻塞。MVCC 并发度高但实现复杂尤其是版本链管理和 GC。实验里如果时间有限建议先实现 2PL 跑通功能再考虑升级到 MVCC。5. 记录恢复机制WAL 日志与崩溃恢复的避坑指南记录恢复机制保证系统崩溃后数据不丢。核心是 WALWrite-Ahead Logging任何数据页的修改必须先写日志再写数据页。崩溃后根据日志重做已提交事务、撤销未提交事务。5.1 WAL 日志格式与 LSN 分配每条日志记录包含 LSN日志序列号、事务 ID、操作类型、修改前后的值。LSN 全局递增数据页头部记录最后一次修改它的 LSN用于恢复时判断是否需要重做。// WAL 日志记录结构 struct LogRecord { lsn_t lsn_; // 日志序列号 txn_id_t txn_id_; // 事务 ID LogType type_; // INSERT / DELETE / UPDATE / COMMIT / ABORT page_id_t page_id_; // 修改的页 uint32_t offset_; // 页内偏移 std::vectorchar before_; // 修改前数据 std::vectorchar after_; // 修改后数据 }; // 写日志并获取 LSN lsn_t AppendLog(LogRecord *record) { std::lock_guardstd::mutex lock(log_latch_); record-lsn_ global_lsn_; log_buffer_.push_back(*record); // 根据策略决定是否刷盘 if (flush_on_commit_ || record-type_ LogType::COMMIT) { FlushLogToDisk(); } return record-lsn_; }关键参数是刷盘策略。flush_on_commit_为 true 时每次提交都刷盘保证已提交事务不丢但性能差。为 false 时批量刷盘性能好但崩溃可能丢最近几个事务。实验里通常要求实现前者。5.2 崩溃恢复的三个阶段分析、重做、撤销恢复分三步分析阶段从最后一个检查点开始扫描日志确定哪些事务已提交、哪些未提交重做阶段把所有已提交事务的修改重新应用到数据页撤销阶段把未提交事务的修改回滚。// 恢复流程骨架 void Recover() { // 1. 分析阶段 std::unordered_settxn_id_t committed, active; for (auto record : ReadLogFromLastCheckpoint()) { if (record.type_ LogType::COMMIT) { committed.insert(record.txn_id_); active.erase(record.txn_id_); } else if (record.type_ LogType::ABORT) { active.erase(record.txn_id_); } else { active.insert(record.txn_id_); } } // 2. 重做阶段重放所有已提交事务的修改 for (auto record : ReadLogFromLastCheckpoint()) { if (committed.count(record.txn_id_)) { ApplyRedo(record); } } // 3. 撤销阶段回滚未提交事务 for (auto it active.rbegin(); it ! active.rend(); it) { UndoTransaction(*it); } }这里有个常见翻车点重做阶段必须从检查点开始按 LSN 顺序重放不能跳过任何记录。有些人为了优化性能只重放数据页 LSN 之后的记录但如果数据页刷盘顺序和日志不一致就会漏掉修改。正确做法是严格按 LSN 顺序重放数据页 LSN 只用于判断是否需要重做不能用于跳过日志。6. 避坑与排查实验代码跑不通时先查这五个地方6.1 缓冲池淘汰时页引用计数未归零导致死锁现象并发测试跑几分钟后线程全部卡住CPU 占用为零。原因某个线程获取页后忘记UnpinPage引用计数永远大于零淘汰器找不到可淘汰页后续FetchPage全部阻塞。解决在FetchPage和UnpinPage成对出现的地方加断言确保每次获取都有对应释放。常见做法是在页对象析构时自动减引用计数但实验里通常要求手动管理所以必须仔细检查每条返回路径。6.2 B 树删除后节点合并顺序错误导致索引断裂现象插入一批数据再删除一部分后点查某些 key 返回不存在但全表扫描能找到。原因删除时先合并了子节点再更新父节点中间状态被其他线程看到。解决合并操作必须持有父节点和子节点的写锁按“先锁父再锁子”的顺序合并完成后统一释放。另一个常见错误是叶子节点合并后忘记更新前驱节点的next_指针导致范围扫描漏数据。6.3 MVCC 版本链遍历时未处理已中止事务的版本现象并发事务回滚后其他事务读到回滚前的脏数据。原因版本链上存在未提交或已中止事务创建的版本可见性判断只检查了创建时间戳没检查事务状态。解决在IsVisible里增加事务状态判断未提交或已中止事务的版本一律不可见。同时撤销阶段要把这些版本从链上摘除否则版本链会无限增长。6.4 WAL 日志刷盘顺序与数据页刷盘顺序颠倒现象系统崩溃后恢复部分已提交事务的数据丢失。原因数据页在日志刷盘之前就写回了磁盘崩溃后日志里没有对应记录恢复时无法重做。解决严格保证 WAL 顺序——日志记录必须先于数据页刷盘。实现时可以在数据页刷盘前检查其 LSN 是否已持久化未持久化则先刷日志。这个检查会增加开销但正确性优先。6.5 并发测试通过但单线程测试失败锁粒度太粗现象单线程跑插入删除测试时结果正确但性能极差几千次操作要跑几十秒。原因全局锁保护了整个 B 树或整个缓冲池所有操作串行化。解决把锁粒度降到页级读操作加读锁写操作加写锁只有修改根节点或全局元数据时才用全局锁。latch crabbing 协议就是为此设计的。注意锁粒度降低后并发 bug 更难复现建议先用单线程验证逻辑正确性再逐步增加并发度。7. 进阶技巧用 Google Test 写可复现的并发测试用例实验代码最怕的是“看起来对”。功能测试通过不代表并发安全并发测试通过不代表恢复正确。我一般会分三层写测试第一层单线程功能测试验证 B 树插入删除点查范围扫描的基本正确性第二层多线程压力测试用多个线程随机插入删除最后校验数据一致性第三层崩溃恢复测试在随机时刻模拟崩溃重启后校验已提交事务的数据完整。Google Test 的TEST_F配合std::thread可以写出可复现的并发用例。关键是要控制随机种子让失败用例可以稳定复现。// 并发插入删除压力测试示例 TEST_F(BPlusTreeTest, ConcurrentInsertDelete) { const int kThreads 8; const int kOpsPerThread 10000; std::vectorstd::thread threads; std::atomicint success{0}; for (int t 0; t kThreads; t) { threads.emplace_back([, t]() { std::mt19937 rng(t); // 固定种子保证可复现 std::uniform_int_distributionint key_dist(0, 100000); for (int i 0; i kOpsPerThread; i) { int key key_dist(rng); if (i % 2 0) { tree_-Insert(key, key); } else { tree_-Remove(key); } success; } }); } for (auto t : threads) t.join(); // 校验全量扫描确认没有断裂或重复 auto iter tree_-Begin(); int prev -1; while (iter ! tree_-End()) { int curr iter-first; ASSERT_GT(curr, prev) Key order violated; prev curr; iter; } ASSERT_EQ(success.load(), kThreads * kOpsPerThread); }这个测试的价值在于固定种子让失败可复现多线程随机操作覆盖 latch crabbing 的各种边界最后全量扫描校验索引结构完整性。如果这个测试跑一万次不挂基本可以认为并发实现是可靠的。另一个实用技巧是给关键路径加统计计数器比如缓冲池命中率、B 树分裂次数、WAL 刷盘次数。这些数字在调优时比日志更直观。我习惯在FetchPage里记录命中/未命中跑完测试打印命中率如果低于 80% 就说明替换策略或缓冲池大小有问题。最后说一个我踩过的坑不要等到所有模块写完再联调。缓冲池、B 树、并发控制、恢复机制是层层依赖的缓冲池的 bug 会在 B 树测试里暴露B 树的并发 bug 会在恢复测试里放大。每写完一个模块就跑对应测试通过后再往上叠。这个习惯让我少熬了很多个通宵。希望帮到你。本文还有配套的精品资源点击获取
CMU 15-445数据库内核实验：缓冲池、B+树、并发控制与恢复机制实现
简介这份资源是CMU 15-445数据库系统课程的实验代码与学习笔记合集面向希望深入理解数据库内核实现的高校学生与后端开发者。内容围绕缓冲池管理器、B树索引、并发控制与记录恢复机制展开并配有C11编程实践、课程视频总结与实验指导建议适合在完成课程作业或自研存储引擎时对照参考。压缩包共121个文件以55个C头文件与46个cpp源文件为主体另有6个md笔记、5个txt说明及少量C、cc、png与docx文档整体约2.64MB目录结构便于按实验模块检索。目前已有66人学习。读者可从中获取B树页面与锁管理器的实现思路、测试用例组织方式以及故障恢复的日志设计要点为构建高性能、高可靠的数据库系统打下基础。1. CMU 15-445 实验到底在练什么从缓冲池到恢复的完整数据库内核链路如果你写过 CRUD 业务代码却说不清一条SELECT从磁盘页到结果集之间到底经过了几层内存结构那 CMU 15-445 的实验就是冲着你来的。它不教你写 SQL而是让你亲手实现一个能跑起来的存储引擎缓冲池管理器负责把磁盘页换进换出B 树索引决定查询走哪条路径并发控制保证多事务同时读写不互相踩踏记录恢复机制让系统崩溃后还能把数据捞回来。这四个模块串起来就是数据库系统概论里那些抽象概念的真实落地。这套实验代码通常用 C11 编写配合课程视频和实验指导建议食用效果最好。适合谁适合已经会写业务代码、但想搞清楚数据库系统原理底层怎么运转的开发者也适合正在准备数据库系统实验一这类课程作业的学生。下面我按实际动手顺序把每个模块的关键实现和踩坑点拆开讲。2. 缓冲池管理器LRU-K 替换策略与页锁的工程实现缓冲池管理器是整个存储引擎的内存入口。所有对磁盘页的读写都要先经过它它决定哪些页留在内存、哪些页被换出。CMU 15-445 的实验通常要求实现 LRU-K 替换策略而不是简单的 LRU。原因很直接LRU 在顺序扫描场景下会把热点页全部挤出去而 LRU-K 通过记录每个页最近 K 次访问时间能识别出真正的热数据。2.1 为什么选 LRU-K 而不是 LRU一个反直觉的替换场景假设缓冲池有 3 个页框访问序列是 A、B、C、A、D、E、A。纯 LRU 在访问 D 时会把 B 换出访问 E 时把 C 换出等再次访问 A 时 A 还在看起来没问题。但如果序列变成 A、B、C、D、E、A纯 LRU 在访问 E 时会把 A 换出再次访问 A 就触发磁盘 IO。LRU-K 因为记录了 A 的两次历史访问会优先保留 A 而换出只访问过一次的 D 或 E。这个差异在顺序扫描大表时特别明显。全表扫描会把所有页都读一遍纯 LRU 会把之前的热点页全部淘汰导致后续查询命中率暴跌。LRU-K 通过 K 次访问历史过滤掉这种一次性访问保护真正的热数据。2.2 实现 LRU-K 的核心数据结构与代码骨架实现 LRU-K 需要两个关键结构一个记录每个页帧当前访问历史的队列另一个记录页帧是否可被替换的标记。常见做法是用一个std::unordered_mappage_id_t, std::dequesize_t存每个页的最近 K 次访问时间戳再用一个可替换页帧列表按最早的第 K 次访问时间排序。// 简化版 LRU-K 替换器核心逻辑 class LRUKReplacer { public: explicit LRUKReplacer(size_t num_frames, size_t k) : k_(k) { // 初始化每个帧的访问历史队列 for (size_t i 0; i num_frames; i) { access_history_[i] std::dequesize_t(); } } // 记录一次访问时间戳由外部递增传入 void RecordAccess(frame_id_t fid, size_t timestamp) { auto history access_history_[fid]; history.push_back(timestamp); // 只保留最近 K 次 if (history.size() k_) { history.pop_front(); } // 如果达到 K 次访问标记为可替换候选 if (history.size() k_) { evictable_[fid] true; } } // 淘汰一个页帧优先选第 K 次访问时间最早的 bool Evict(frame_id_t *frame_id) { size_t earliest SIZE_MAX; bool found false; for (auto [fid, history] : access_history_) { if (!evictable_[fid] || history.size() k_) continue; // 比较第 K 次访问时间即队列最前面的时间戳 if (history.front() earliest) { earliest history.front(); *frame_id fid; found true; } } if (found) { access_history_.erase(*frame_id); evictable_.erase(*frame_id); } return found; } private: size_t k_; std::unordered_mapframe_id_t, std::dequesize_t access_history_; std::unordered_mapframe_id_t, bool evictable_; };这段代码的关键参数是k_通常取 2。K 越大对历史访问的过滤越严格但冷启动阶段访问次数不足 K 次的页无法被淘汰可能导致缓冲池暂时无法换入新页。实际实现时还需要配合页锁读页时加读锁写页时加写锁淘汰前必须确认页的引用计数为 0。2.3 页锁与引用计数避免并发访问时的悬空指针缓冲池管理器必须处理多线程并发访问。一个线程正在读某页时另一个线程不能把它淘汰掉。常见做法是给每个页帧维护一个pin_count_读页时加一用完减一只有pin_count_ 0的页才能被淘汰。同时用std::shared_mutex保护页帧元数据读操作加共享锁写操作加独占锁。// 获取页时的加锁与引用计数逻辑 Page *FetchPage(page_id_t page_id) { std::unique_lockstd::shared_mutex lock(latch_); // 先查页表 auto it page_table_.find(page_id); if (it ! page_table_.end()) { frame_id_t fid it-second; // 命中增加引用计数记录访问 pin_count_[fid]; replacer_-RecordAccess(fid, timestamp_); return pages_[fid]; } // 未命中需要从磁盘读入 frame_id_t fid; if (!replacer_-Evict(fid)) { return nullptr; // 缓冲池满且无可淘汰页 } // 如果被淘汰的页是脏页先写回磁盘 if (is_dirty_[fid]) { disk_manager_-WritePage(pages_[fid].GetPageId(), pages_[fid].GetData()); } // 读入新页 disk_manager_-ReadPage(page_id, pages_[fid].GetData()); page_table_[page_id] fid; pin_count_[fid] 1; is_dirty_[fid] false; replacer_-RecordAccess(fid, timestamp_); return pages_[fid]; }这里有个容易翻车的点淘汰脏页时写回磁盘的操作必须在持有锁的情况下完成否则可能两个线程同时淘汰同一页导致数据错乱。但写磁盘是慢操作长时间持锁会严重拖累并发性能。常见优化是先把脏页标记为“正在写回”释放锁后再实际写磁盘写完再重新加锁更新状态。这个细节在实验指导建议里通常不会明说但实际跑并发测试时就会暴露。3. B 树索引从页分裂到并发安全的完整实现路径B 树索引是查询加速的核心。CMU 15-445 的实验要求实现一个支持插入、删除、点查和范围扫描的 B 树而且必须保证并发安全。很多人在这一步卡住不是因为不懂 B 树原理而是因为并发场景下的页分裂和合并太容易出 bug。3.1 B 树的节点布局与插入分裂逻辑B 树的每个节点对应一个磁盘页。内部节点存 key 和子页指针叶子节点存 key 和记录 ID。插入时从根往下找到目标叶子如果叶子满了就分裂把中间 key 推到父节点。父节点如果也满了就继续往上分裂直到根节点。// B 树叶子节点插入与分裂的核心逻辑 bool InsertIntoLeaf(LeafPage *leaf, const KeyType key, const ValueType value) { // 找到插入位置 auto pos std::lower_bound(leaf-keys_.begin(), leaf-keys_.end(), key); leaf-keys_.insert(pos, key); leaf-values_.insert(leaf-values_.begin() (pos - leaf-keys_.begin()), value); // 如果没满直接返回 if (leaf-keys_.size() leaf-max_size_) { return true; } // 叶子满了需要分裂 LeafPage *new_leaf AllocateNewLeaf(); size_t mid leaf-keys_.size() / 2; // 把后半部分移到新叶子 new_leaf-keys_.assign(leaf-keys_.begin() mid, leaf-keys_.end()); new_leaf-values_.assign(leaf-values_.begin() mid, leaf-values_.end()); leaf-keys_.resize(mid); leaf-values_.resize(mid); // 维护叶子链表指针 new_leaf-next_ leaf-next_; leaf-next_ new_leaf; // 把新叶子的第一个 key 插入父节点 InsertIntoParent(leaf, new_leaf-keys_[0], new_leaf); return true; }关键参数是max_size_通常由页大小和 key/value 大小决定。比如 4KB 页key 是 8 字节整数value 是 8 字节记录 ID那么叶子节点最多存约 250 个键值对。分裂时取mid size / 2是一种常见做法但有些实现会偏向一边以减少后续分裂频率具体取决于工作负载。3.2 并发 B 树的 latch crabbing 协议并发 B 树最经典的方案是 latch crabbing从根节点开始先锁住子节点再释放父节点。读操作加读锁写操作加写锁。如果子节点是安全的不会因为这次操作分裂或合并就可以释放父节点的锁。// latch crabbing 的读路径示例 Page *FindLeafRead(const KeyType key) { Page *curr root_page_; curr-RLatch(); while (!curr-IsLeaf()) { InternalPage *internal static_castInternalPage *(curr); Page *child internal-LookupChild(key); child-RLatch(); curr-RUnlatch(); // 释放父节点读锁 curr child; } return curr; // 返回时持有叶子节点读锁 }写路径更复杂如果子节点可能分裂就不能提前释放父节点锁因为分裂需要修改父节点。常见做法是判断子节点是否“安全”——插入时如果子节点未满就是安全的删除时如果子节点超过半满就是安全的。只有安全时才释放父节点锁。这里有个血泪经验很多人在实现删除时忘了处理根节点收缩。当根节点变成只有一个子节点的内部节点时必须把那个子节点提升为新根否则树的高度会无意义地增加查询性能逐渐退化。这个 bug 在功能测试时不会暴露只有跑大规模随机插入删除才会显现。4. 并发控制MVCC 多版本并发控制与两阶段锁的取舍并发控制是数据库系统原理里最抽象的部分也是实验中最容易写出“看起来对但并发跑就错”的模块。CMU 15-445 通常要求实现基于时间戳的 MVCC 或两阶段锁2PL两者各有适用场景。4.1 MVCC 的版本链与可见性判断MVCC 的核心思想是写操作不覆盖旧数据而是生成新版本读操作根据事务开始时间戳读取可见版本。每个元组维护一个版本链链上每个版本记录创建时间戳和删除时间戳。// MVCC 可见性判断逻辑 bool IsVisible(const TupleVersion *version, txn_id_t txn_id, timestamp_t read_ts) { // 版本创建时间戳必须小于等于读时间戳 if (version-created_ts_ read_ts) return false; // 版本删除时间戳必须大于读时间戳或者未删除 if (version-deleted_ts_ ! INVALID_TS version-deleted_ts_ read_ts) { return false; } // 如果版本是自己创建的可见 if (version-creator_txn_ txn_id) return true; // 如果版本是已提交事务创建的可见 return IsCommitted(version-creator_txn_); }关键参数是read_ts通常取事务开始时的全局时间戳。写操作会创建一个新版本把旧版本的deleted_ts_设为当前事务 ID。提交时更新全局时间戳未提交事务的版本对其他事务不可见。MVCC 的优点是读不阻塞写、写不阻塞读适合读多写少的场景。缺点是版本链会越来越长需要垃圾回收机制清理不再可见的旧版本。实验里通常不要求实现完整的 GC但至少要能正确处理版本链的遍历。4.2 两阶段锁的加锁顺序与死锁检测如果实验要求实现 2PL核心是维护一个锁表记录每个事务持有哪些锁、等待哪些锁。加锁时如果冲突就等待等待图出现环就说明死锁需要选择一个事务回滚。// 两阶段锁的加锁逻辑简化版 bool AcquireLock(txn_id_t txn_id, resource_id_t rid, LockMode mode) { std::unique_lockstd::mutex lock(latch_); auto lock_request lock_table_[rid]; // 检查是否与已有锁冲突 for (auto [holder, held_mode] : lock_request.holders_) { if (holder txn_id) continue; if (IsConflict(held_mode, mode)) { // 冲突加入等待队列 lock_request.waiters_.push_back({txn_id, mode}); // 检测死锁 if (HasCycle(txn_id)) { lock_request.waiters_.pop_back(); return false; // 触发回滚 } // 等待锁释放 lock_request.cv_.wait(lock, []() { return CanGrant(lock_request, txn_id, mode); }); } } lock_request.holders_[txn_id] mode; return true; }死锁检测用等待图每个事务是节点等待关系是边用 DFS 找环。发现环后选择代价最小的事务回滚通常是修改数据最少或优先级最低的那个。2PL 的优点是实现相对直接缺点是并发度低读写互相阻塞。MVCC 并发度高但实现复杂尤其是版本链管理和 GC。实验里如果时间有限建议先实现 2PL 跑通功能再考虑升级到 MVCC。5. 记录恢复机制WAL 日志与崩溃恢复的避坑指南记录恢复机制保证系统崩溃后数据不丢。核心是 WALWrite-Ahead Logging任何数据页的修改必须先写日志再写数据页。崩溃后根据日志重做已提交事务、撤销未提交事务。5.1 WAL 日志格式与 LSN 分配每条日志记录包含 LSN日志序列号、事务 ID、操作类型、修改前后的值。LSN 全局递增数据页头部记录最后一次修改它的 LSN用于恢复时判断是否需要重做。// WAL 日志记录结构 struct LogRecord { lsn_t lsn_; // 日志序列号 txn_id_t txn_id_; // 事务 ID LogType type_; // INSERT / DELETE / UPDATE / COMMIT / ABORT page_id_t page_id_; // 修改的页 uint32_t offset_; // 页内偏移 std::vectorchar before_; // 修改前数据 std::vectorchar after_; // 修改后数据 }; // 写日志并获取 LSN lsn_t AppendLog(LogRecord *record) { std::lock_guardstd::mutex lock(log_latch_); record-lsn_ global_lsn_; log_buffer_.push_back(*record); // 根据策略决定是否刷盘 if (flush_on_commit_ || record-type_ LogType::COMMIT) { FlushLogToDisk(); } return record-lsn_; }关键参数是刷盘策略。flush_on_commit_为 true 时每次提交都刷盘保证已提交事务不丢但性能差。为 false 时批量刷盘性能好但崩溃可能丢最近几个事务。实验里通常要求实现前者。5.2 崩溃恢复的三个阶段分析、重做、撤销恢复分三步分析阶段从最后一个检查点开始扫描日志确定哪些事务已提交、哪些未提交重做阶段把所有已提交事务的修改重新应用到数据页撤销阶段把未提交事务的修改回滚。// 恢复流程骨架 void Recover() { // 1. 分析阶段 std::unordered_settxn_id_t committed, active; for (auto record : ReadLogFromLastCheckpoint()) { if (record.type_ LogType::COMMIT) { committed.insert(record.txn_id_); active.erase(record.txn_id_); } else if (record.type_ LogType::ABORT) { active.erase(record.txn_id_); } else { active.insert(record.txn_id_); } } // 2. 重做阶段重放所有已提交事务的修改 for (auto record : ReadLogFromLastCheckpoint()) { if (committed.count(record.txn_id_)) { ApplyRedo(record); } } // 3. 撤销阶段回滚未提交事务 for (auto it active.rbegin(); it ! active.rend(); it) { UndoTransaction(*it); } }这里有个常见翻车点重做阶段必须从检查点开始按 LSN 顺序重放不能跳过任何记录。有些人为了优化性能只重放数据页 LSN 之后的记录但如果数据页刷盘顺序和日志不一致就会漏掉修改。正确做法是严格按 LSN 顺序重放数据页 LSN 只用于判断是否需要重做不能用于跳过日志。6. 避坑与排查实验代码跑不通时先查这五个地方6.1 缓冲池淘汰时页引用计数未归零导致死锁现象并发测试跑几分钟后线程全部卡住CPU 占用为零。原因某个线程获取页后忘记UnpinPage引用计数永远大于零淘汰器找不到可淘汰页后续FetchPage全部阻塞。解决在FetchPage和UnpinPage成对出现的地方加断言确保每次获取都有对应释放。常见做法是在页对象析构时自动减引用计数但实验里通常要求手动管理所以必须仔细检查每条返回路径。6.2 B 树删除后节点合并顺序错误导致索引断裂现象插入一批数据再删除一部分后点查某些 key 返回不存在但全表扫描能找到。原因删除时先合并了子节点再更新父节点中间状态被其他线程看到。解决合并操作必须持有父节点和子节点的写锁按“先锁父再锁子”的顺序合并完成后统一释放。另一个常见错误是叶子节点合并后忘记更新前驱节点的next_指针导致范围扫描漏数据。6.3 MVCC 版本链遍历时未处理已中止事务的版本现象并发事务回滚后其他事务读到回滚前的脏数据。原因版本链上存在未提交或已中止事务创建的版本可见性判断只检查了创建时间戳没检查事务状态。解决在IsVisible里增加事务状态判断未提交或已中止事务的版本一律不可见。同时撤销阶段要把这些版本从链上摘除否则版本链会无限增长。6.4 WAL 日志刷盘顺序与数据页刷盘顺序颠倒现象系统崩溃后恢复部分已提交事务的数据丢失。原因数据页在日志刷盘之前就写回了磁盘崩溃后日志里没有对应记录恢复时无法重做。解决严格保证 WAL 顺序——日志记录必须先于数据页刷盘。实现时可以在数据页刷盘前检查其 LSN 是否已持久化未持久化则先刷日志。这个检查会增加开销但正确性优先。6.5 并发测试通过但单线程测试失败锁粒度太粗现象单线程跑插入删除测试时结果正确但性能极差几千次操作要跑几十秒。原因全局锁保护了整个 B 树或整个缓冲池所有操作串行化。解决把锁粒度降到页级读操作加读锁写操作加写锁只有修改根节点或全局元数据时才用全局锁。latch crabbing 协议就是为此设计的。注意锁粒度降低后并发 bug 更难复现建议先用单线程验证逻辑正确性再逐步增加并发度。7. 进阶技巧用 Google Test 写可复现的并发测试用例实验代码最怕的是“看起来对”。功能测试通过不代表并发安全并发测试通过不代表恢复正确。我一般会分三层写测试第一层单线程功能测试验证 B 树插入删除点查范围扫描的基本正确性第二层多线程压力测试用多个线程随机插入删除最后校验数据一致性第三层崩溃恢复测试在随机时刻模拟崩溃重启后校验已提交事务的数据完整。Google Test 的TEST_F配合std::thread可以写出可复现的并发用例。关键是要控制随机种子让失败用例可以稳定复现。// 并发插入删除压力测试示例 TEST_F(BPlusTreeTest, ConcurrentInsertDelete) { const int kThreads 8; const int kOpsPerThread 10000; std::vectorstd::thread threads; std::atomicint success{0}; for (int t 0; t kThreads; t) { threads.emplace_back([, t]() { std::mt19937 rng(t); // 固定种子保证可复现 std::uniform_int_distributionint key_dist(0, 100000); for (int i 0; i kOpsPerThread; i) { int key key_dist(rng); if (i % 2 0) { tree_-Insert(key, key); } else { tree_-Remove(key); } success; } }); } for (auto t : threads) t.join(); // 校验全量扫描确认没有断裂或重复 auto iter tree_-Begin(); int prev -1; while (iter ! tree_-End()) { int curr iter-first; ASSERT_GT(curr, prev) Key order violated; prev curr; iter; } ASSERT_EQ(success.load(), kThreads * kOpsPerThread); }这个测试的价值在于固定种子让失败可复现多线程随机操作覆盖 latch crabbing 的各种边界最后全量扫描校验索引结构完整性。如果这个测试跑一万次不挂基本可以认为并发实现是可靠的。另一个实用技巧是给关键路径加统计计数器比如缓冲池命中率、B 树分裂次数、WAL 刷盘次数。这些数字在调优时比日志更直观。我习惯在FetchPage里记录命中/未命中跑完测试打印命中率如果低于 80% 就说明替换策略或缓冲池大小有问题。最后说一个我踩过的坑不要等到所有模块写完再联调。缓冲池、B 树、并发控制、恢复机制是层层依赖的缓冲池的 bug 会在 B 树测试里暴露B 树的并发 bug 会在恢复测试里放大。每写完一个模块就跑对应测试通过后再往上叠。这个习惯让我少熬了很多个通宵。希望帮到你。本文还有配套的精品资源点击获取
