简介这份资源是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而是让你用 C11 从零实现一个能跑并发事务的存储引擎缓冲池管理器负责把页在磁盘和内存之间倒腾B 树索引负责让点查和范围查都落在 O(log n)并发控制负责让多个事务同时跑还不互相踩记录恢复机制负责在系统崩溃后把数据捞回来。这四个模块串起来就是数据库系统概论里那些 ER 图例题和 MVCC 多版本并发控制概念真正落地的地方。适合已经会 C、想深入数据库系统原理的人也适合正在做数据库系统实验一却卡在 LRU-K 替换策略上的同学。下面按我实际复现的顺序把每一步的命令、参数和翻车点讲清楚。2. 缓冲池管理器LRU-K 替换策略与页锁的落地实现缓冲池管理器是整个存储引擎的内存门面。磁盘上的页要读进内存才能被上层访问但内存有限必须有一套替换策略决定谁被踢出去。15-445 要求实现 LRU-K而不是简单的 LRU。原因很直接LRU 只看最近一次访问一次全表扫描就能把热页全部冲掉LRU-K 看最近 K 次访问的时间间隔把「偶尔被扫到一次」的页和「反复被点查」的页区分开。K 一般取 2也就是 LRU-2这是工业界和课程都常用的默认值。2.1 为什么是 LRU-K 而不是 LRU替换策略的选型理由假设一个页被访问了两次第一次在 t1第二次在 t100另一个页在 t99 和 t101 各被访问一次。LRU 会认为第二个页更热因为它最近被访问过。但 LRU-K 计算的是第 K 次访问与第 K-1 次访问之间的间隔第一个页间隔 99第二个页间隔 2。间隔越小说明访问越密集越应该留在内存。LRU-2 的淘汰优先级是先淘汰访问次数不足 K 次的页再淘汰 K 次访问间隔最大的页。这个策略能有效抵抗顺序扫描污染代价是需要为每个页维护一个访问历史队列。实现上每个 frame 需要记录一个std::dequesize_t或者固定大小的环形缓冲区来存最近 K 次访问的时间戳。当访问次数不足 K 时页处于「冷区」按 FIFO 淘汰当访问次数达到 K 后页进入「热区」按第 K 次访问的时间戳排序淘汰。这里有个容易忽略的点时间戳不需要真实时钟用一个全局递增的计数器就行每次访问加一避免系统调用开销。2.2 用 C11 实现 LRU-K 替换器的核心代码下面是我在buffer_pool_manager.cpp里实现的LRUKReplacer核心逻辑省略了头文件声明只保留关键路径。// 每个 frame 的访问记录 struct FrameInfo { std::dequesize_t access_history; // 最近 K 次访问时间戳 bool is_evictable{false}; // 是否可被淘汰 }; class LRUKReplacer { public: explicit LRUKReplacer(size_t num_frames, size_t k) : k_(k) { frames_.resize(num_frames); } // 记录一次访问返回被淘汰的 frame_id如果有 void RecordAccess(frame_id_t fid) { auto info frames_[fid]; info.access_history.push_back(global_ts_); if (info.access_history.size() k_) { info.access_history.pop_front(); // 只保留最近 K 次 } // 更新淘汰候选集访问次数达到 K 的进入热区 if (info.access_history.size() k_) { hot_set_.insert(fid); } } // 淘汰一个页优先淘汰冷区再淘汰热区间隔最大的 bool Evict(frame_id_t *frame_id) { // 先找冷区中 is_evictable 的页FIFO 顺序 for (auto it cold_list_.begin(); it ! cold_list_.end(); it) { if (frames_[*it].is_evictable) { *frame_id *it; cold_list_.erase(it); frames_[*it].access_history.clear(); return true; } } // 冷区没有从热区找间隔最大的 size_t max_gap 0; frame_id_t victim INVALID_FRAME; for (auto fid : hot_set_) { if (!frames_[fid].is_evictable) continue; auto h frames_[fid].access_history; size_t gap h.back() - h.front(); // 第 K 次与第 1 次的间隔 if (gap max_gap) { max_gap gap; victim fid; } } if (victim ! INVALID_FRAME) { *frame_id victim; hot_set_.erase(victim); frames_[victim].access_history.clear(); return true; } return false; } private: size_t k_; size_t global_ts_{0}; std::vectorFrameInfo frames_; std::listframe_id_t cold_list_; // 访问次数不足 K 的页 std::setframe_id_t hot_set_; // 访问次数达到 K 的页 };这段代码的关键参数是k_构造时传入课程默认用 2。global_ts_是单调递增计数器保证时间戳不重复。cold_list_用std::list是为了 O(1) 删除hot_set_用std::set是为了遍历时稳定。淘汰逻辑先扫冷区再扫热区冷区按插入顺序淘汰热区按间隔最大淘汰。注意is_evictable标志被上层 pin 住的页不能淘汰Unpin时才置为 true。2.3 页锁与并发安全什么时候加 latch什么时候加 lock缓冲池管理器本身要被多个线程并发访问所以每个 frame 需要一个std::mutex或者std::shared_mutex。读页时加共享锁修改页时加排他锁。但这里有个血泪经验不要在持有 frame latch 的时候去调用磁盘 IO否则整个缓冲池会被一个慢磁盘拖死。常见做法是先把页读进一个临时缓冲区释放 latch再拷贝到 frame 里。另外Page对象里的pin_count_和is_dirty_必须用原子变量或者受同一个 latch 保护否则并发Unpin会导致计数错乱。我一般会在FetchPage里先查页表命中就RecordAccess并pin_count_未命中就选一个 victim如果 victim 是脏页先写回磁盘再读新页。整个过程用std::scoped_lock锁住页表但磁盘 IO 放在锁外。3. B 树索引从页分裂到并发 Crabbing 的完整路径B 树是数据库索引的默认答案15-445 要求实现支持点查、范围查和迭代器的 B 树并且要能并发访问。课程里 B 树的每个节点就是一个页内部节点存 key 和子页指针叶子节点存 key 和记录 IDRID。和教科书不同的是这里的 B 树要处理页分裂、页合并还要用 crabbing 协议保证并发安全。3.1 B 树节点布局与插入分裂的边界条件一个 B 树节点页的大小是固定的比如 4KB。内部节点的结构是[header][key0][page_id0][key1][page_id1]...叶子节点是[header][key0][rid0][key1][rid1]...。插入时先找到目标叶子节点如果叶子没满就直接插入如果满了就分裂成两个节点把中间 key 推到父节点。这里最容易翻车的是分裂时的 key 分配假设叶子节点有 n 个 key分裂后左节点保留前 n/2 个右节点保留剩下的中间那个 key 是复制到父节点还是移动对于叶子节点父节点里的 key 是右节点的最小 key所以是复制对于内部节点父节点里的 key 是移动原节点不再保留。这个区别如果搞反范围查会丢数据。另一个边界是根节点分裂。根节点分裂后要创建一个新的根树高加一。很多同学在实现时忘了更新root_page_id_导致后续查找从旧根开始直接段错误。我一般会在Insert返回后检查root_page_id_是否变化如果变了就更新 header page 里的元数据。3.2 并发 Crabbing 协议 latch 的获取与释放顺序Crabbing 协议的核心是查找时先锁住根节点再锁住子节点然后释放父节点的锁。这样任意时刻最多持有两个节点的 latch避免死锁。插入时稍微复杂如果子节点不会分裂就释放父节点锁如果可能分裂就一路持有父节点锁直到完成分裂。判断「是否可能分裂」的方法是看子节点当前 key 数量是否等于 max_size - 1。这个预判可以减少锁持有时间。// 查找路径上的 crabbing先锁子再放父 Page *FindLeaf(page_id_t root_id, const Key key) { page_id_t cur root_id; Page *parent buffer_pool_-FetchPage(cur); parent-RLatch(); // 根节点加读锁 while (!parent-IsLeaf()) { page_id_t child_id parent-InternalLookup(key); Page *child buffer_pool_-FetchPage(child_id); child-RLatch(); parent-RUnlatch(); // 释放父节点读锁 buffer_pool_-UnpinPage(parent-GetPageId(), false); parent child; } return parent; // 返回叶子节点仍持有读锁 }这段代码里RLatch和RUnlatch是页级读写锁。查找时全部用读锁因为不修改结构。插入时从根开始加写锁向下走时如果子节点安全不会分裂就释放祖先的写锁。注意UnpinPage的第二个参数是is_dirty查找路径上不修改页所以传 false。如果传 true缓冲池会把这个页标记为脏导致不必要的写回。3.3 迭代器的实现与范围查的坑B 树的迭代器要支持Begin()、Begin(key)、Next()。Begin(key)找到第一个大于等于 key 的叶子位置然后Next()在当前叶子内移动如果到叶子末尾就通过next_page_id_跳到下一个叶子。这里有个坑叶子节点之间的链表指针必须在分裂时正确维护。分裂时新右节点的next_page_id_指向原节点的下一个原节点的next_page_id_指向新右节点。如果顺序搞反范围查会死循环或者漏数据。另外迭代器持有叶子节点的读锁Next()跳到下一个叶子时要先锁新叶子再放旧叶子否则中间窗口可能有其他线程修改结构。4. 并发控制 MVCC 多版本并发控制与两阶段锁的取舍并发控制是 15-445 最抽象的部分。课程要求实现基于两阶段锁2PL或者 MVCC 的事务管理器。MVCC 多版本并发控制是当前热搜里经常出现的词它的核心思想是读操作不阻塞写操作写操作不阻塞读操作每个事务看到自己开始时的快照。实现上每个元组维护多个版本每个版本有begin_ts和end_ts读的时候找begin_ts read_ts end_ts的版本。4.1 事务 ID 分配与可见性判断规则事务开始时分配一个read_ts提交时分配commit_ts。可见性规则是对于读事务 T元组版本 V 可见当且仅当V.begin_ts T.read_ts且V.end_ts INF或V.end_ts T.read_ts。写操作会创建一个新版本新版本的begin_ts是当前事务的commit_ts提交时才确定旧版本的end_ts也设为这个值。这里有个关键点未提交事务的写版本对其他事务不可见所以begin_ts在提交前是无效的通常用一个事务状态表来辅助判断。// 可见性判断读事务 read_ts 能否看到版本 v bool IsVisible(const Version v, timestamp_t read_ts) { if (v.begin_ts read_ts) return false; // 版本太新 if (v.end_ts ! INVALID_TS v.end_ts read_ts) return false; // 版本已过期 // 如果 begin_ts 对应的事务还未提交也不可见 if (!txn_mgr_-IsCommitted(v.begin_ts)) return false; return true; }INVALID_TS是一个极大值表示版本仍然有效。txn_mgr_-IsCommitted查事务状态表只有提交了的事务产生的版本才可见。这个判断在每次读元组时都要做所以事务状态表要用并发安全的结构比如std::unordered_map加读写锁。4.2 写冲突处理先写后读还是先读后写MVCC 下写冲突有两种处理策略第一种是「先写后读」写操作直接创建新版本如果发现另一个未提交事务已经写了同一个 key就等待或者回滚第二种是「先读后写」先检查可见版本再基于可见版本创建新版本如果版本在检查后被修改就重试。15-445 的 Project 4 通常要求实现第一种配合一个锁管理器来检测写写冲突。我一般会在Update时先获取元组的写锁然后检查是否有其他未提交事务持有该元组的写锁如果有就阻塞。这个写锁可以用一个std::mutex加条件变量实现也可以用更细粒度的锁表。4.3 死锁检测与回滚等待图与超时机制并发控制绕不开死锁。两个事务互相等待对方持有的锁就会永久阻塞。常见做法是维护一个等待图事务 A 等待事务 B 就加一条 A-B 的边如果图中出现环就回滚其中一个事务。等待图可以用std::unordered_maptxn_id_t, std::settxn_id_t表示每次加边时做一次 DFS 检测环。另一个简单做法是超时如果一个事务等待超过一定时间比如 50ms就回滚它。超时机制实现简单但可能误杀等待图更精确但开销大。我一般会先用超时兜底再在锁管理器里加等待图检测两者结合。5. 记录恢复机制 WAL 日志与 ARIES 算法的简化实现恢复机制保证数据库在崩溃后能回到一致状态。15-445 要求实现基于 WALWrite-Ahead Logging的恢复任何页的修改必须先写日志再写数据页日志按顺序落盘。恢复时重放日志把已提交事务的修改重新应用把未提交事务的修改撤销。ARIES 算法是工业界标准课程里通常简化成三个步骤分析、重做、撤销。5.1 日志记录格式与 LSN 的分配每条日志记录包含LSN日志序列号、txn_id、typeBEGIN/UPDATE/COMMIT/ABORT、page_id、offset、before_image、after_image。LSN 全局递增由日志管理器分配。写日志时先写进内存缓冲区再批量刷盘。刷盘策略有两种强制刷盘每次提交都刷和组提交攒一批再刷。课程实验一般要求强制刷盘保证提交的事务一定持久化。// 日志记录结构 struct LogRecord { lsn_t lsn; txn_id_t txn_id; LogType type; page_id_t page_id; uint32_t offset; std::vectorchar before_img; std::vectorchar after_img; }; // 写日志先分配 LSN再写缓冲区提交时刷盘 lsn_t LogManager::AppendLog(LogRecord rec) { std::scoped_lock lock(latch_); rec.lsn next_lsn_; buffer_.push_back(rec); if (rec.type LogType::COMMIT) { Flush(); // 提交时强制刷盘 } return rec.lsn; }next_lsn_是原子递增的buffer_是内存日志缓冲区。Flush把缓冲区写到磁盘文件并更新persist_lsn_。注意before_img和after_img的大小要和页内记录大小一致否则重做时会越界。5.2 重做与撤销从检查点恢复的完整流程恢复时先从检查点开始。检查点记录了当前活跃事务列表和persist_lsn_。分析阶段扫描日志重建活跃事务表和脏页表。重做阶段从检查点的persist_lsn_开始对每条 UPDATE 日志如果页的page_lsn小于日志的 LSN就应用after_img。撤销阶段从日志末尾反向扫描对未提交事务的 UPDATE 应用before_img并写一条 CLR补偿日志记录。CLR 的作用是防止恢复过程中再次崩溃导致重复撤销。这里有个容易忽略的坑重做时必须比较页的page_lsn和日志的 LSN如果page_lsn log.lsn说明这个修改已经落盘了跳过。否则重复应用会导致数据错乱。page_lsn存在每个页的头部每次修改页时更新为当前日志的 LSN。6. 避坑与排查四个模块联调时最容易翻车的地方6.1 缓冲池淘汰了还被引用的页现象程序随机崩溃报段错误或者数据错乱。原因UnpinPage时pin_count_减到 0页被标记为可淘汰但上层还持有Page*指针另一个线程触发淘汰后这个指针就悬空了。解决上层使用Page*期间必须保证pin_count_ 0用完立即Unpin。我一般会在FetchPage返回的页上强制要求调用方在同一个作用域内Unpin用 RAII 封装一个PageGuard。6.2 B 树分裂后父节点 key 没更新现象点查能找到数据但范围查漏掉一部分。原因叶子分裂后父节点里的分隔 key 还是旧值导致查找时路由到错误的叶子。解决分裂后必须把右节点的最小 key 插入父节点如果父节点也满了就继续向上分裂。检查方法是写一个单元测试插入 1000 个随机 key然后范围查验证返回数量。6.3 MVCC 读到了未提交的版本现象事务 A 未提交事务 B 却读到了 A 的修改。原因可见性判断里漏了事务状态检查只比较了begin_ts和read_ts。解决在IsVisible里加txn_mgr_-IsCommitted(v.begin_ts)判断并且事务状态表要在提交时原子更新。测试时可以用两个线程一个写一个读读线程 sleep 一段时间再读验证读不到未提交数据。6.4 WAL 日志刷盘顺序错误现象系统崩溃后恢复已提交的事务丢失。原因数据页先于日志落盘崩溃时日志还没写恢复时找不到对应记录。解决严格保证Flush日志在写数据页之前。可以在BufferPoolManager::FlushPage里先调用log_mgr_-Flush()再写磁盘。另一个检查点是commit时必须强制刷日志不能只写缓冲区。6.5 并发插入导致 B 树结构损坏现象多线程同时插入时树结构出现环或者节点丢失。原因crabbing 协议里释放父节点锁的时机不对两个线程同时分裂同一个节点。解决插入时对可能分裂的节点持有写锁直到分裂完成并且用std::mutex保护根节点 ID 的更新。测试时开 8 个线程各插入 1000 个 key最后中序遍历验证有序性。7. 用 Google Test 做模块级验证从单元测试到压力测试15-445 的代码量很大四个模块联调时靠打印日志排查效率极低。我习惯用 Google Test 给每个模块写独立的单元测试再写一个集成测试跑并发压力。下面是我常用的测试骨架。// 缓冲池 LRU-K 淘汰顺序测试 TEST(LRUKReplacerTest, EvictOrder) { LRUKReplacer replacer(3, 2); replacer.RecordAccess(1); replacer.RecordAccess(2); replacer.RecordAccess(1); // frame 1 达到 K2进入热区 replacer.RecordAccess(3); replacer.SetEvictable(1, true); replacer.SetEvictable(2, true); replacer.SetEvictable(3, true); frame_id_t victim; // 冷区先淘汰frame 2 和 3 访问次数不足 2 ASSERT_TRUE(replacer.Evict(victim)); ASSERT_EQ(victim, 2); // FIFO 顺序2 先于 3 ASSERT_TRUE(replacer.Evict(victim)); ASSERT_EQ(victim, 3); ASSERT_TRUE(replacer.Evict(victim)); ASSERT_EQ(victim, 1); // 最后才是热区 }这个测试验证了淘汰优先级冷区按 FIFO热区最后淘汰。参数k2是构造时传入的SetEvictable模拟上层Unpin。跑通这个测试缓冲池的替换逻辑基本就稳了。对于 B 树我会写一个随机插入和删除的测试插入 10000 个随机 key然后逐个点查验证存在再范围查验证数量。对于 MVCC写两个线程一个不断更新同一个 key另一个不断读验证读到的版本号单调不减。对于恢复模拟崩溃写一批日志不刷数据页然后调用恢复流程验证已提交事务的数据都在。压力测试用std::thread开 8 个线程每个线程跑 1000 次随机操作最后检查数据一致性。如果出现死锁用gdbattach 上去看各个线程的调用栈重点看锁的持有顺序。我一般会在锁管理器里加一个DLOG记录每次加锁和解锁崩溃后看日志就能定位到哪个事务没释放锁。最后说一个我踩过的坑Google Test 默认不检测内存泄漏缓冲池的Page对象如果忘记delete跑久了内存会爆。我习惯在测试里加--gtest_also_run_disabled_tests和 AddressSanitizer编译时加-fsanitizeaddress这样悬空指针和泄漏都能在测试阶段暴露。这套流程跑下来四个模块的联调时间能从几天压缩到几个小时。希望帮到你。本文还有配套的精品资源点击获取