CMU-15-445数据库内核实验：可调试的B+树与缓冲池实战指南

简介本资源是CMU-15-445数据库系统课程的完整实践学习包面向数据库内核开发者、系统软件工程师及高校高年级本科生/研究生聚焦数据库底层核心机制的理论理解与C11工程实现。内容覆盖缓冲池管理器、B树索引、并发控制锁管理器、WAL日志与崩溃恢复等关键模块配套实验代码、测试用例、课程视频要点总结及实操指导建议助力从原理到代码的深度贯通。压缩包共121个文件含46个cpp与55个h头文件构成完整C项目骨架6个md文档提供结构化说明5个txt含环境配置与运行指引另有png图示与docx补充资料整体2.64MB轻量但高度聚焦。已有66人下载学习资源结构清晰——如b_plus_tree.cpp/b_plus_tree_test.cpp等文件直指索引实现与验证lock_manager_test.cpp体现并发控制设计table_page.cpp与virtual_table.cpp反映存储层抽象适合动手复现、调试分析与源码级数据库原理研习。1. CMU-15-445 实验代码包不是“课程录像合集”而是可编译、可调试、可单步跟踪的数据库内核手术台你下载的这个.zip文件本质是一套带完整构建链路的工业级教学级数据库内核实验套件——它不依赖任何云服务、不封装成黑匣子 Docker 镜像、不预编译二进制而是从CMakeLists.txt开始到b_plus_tree.cpp里每一行Insert()的递归调用栈全部裸露在你 IDE 的断点之下。我去年带三个实习生复现 BufferPoolManager 时他们第一反应是“这怎么跑起来”第二反应是“原来PinPage()和UnpinPage()的 ref_count 变化居然能被 gdb 实时 watch 到”。这不是教科书里的伪代码这是卡内基梅隆大学数据库系统课CMU-15-445真实交付给学生的、用于期末项目答辩的底层代码基线。它覆盖缓冲池管理器LRU-K 替换策略、B 树索引支持重复键与范围查询、两阶段锁协议2PL下的并发控制、WAL 日志驱动的 ARIES 风格恢复机制全部用 C11 标准实现无第三方框架依赖。适合三类人想搞清 SQLite 底层页缓存逻辑的 DBA准备数据库岗面试、需要手写 B 树插入分裂逻辑的应届生以及正在开发嵌入式数据库、需要参考工业级内存管理设计的嵌入式工程师。别把它当学习资料——它是一把解剖刀插进数据库心脏前得先学会怎么握稳。2. 编译与运行从零构建可调试的 MiniDB 内核环境2.1 环境准备C11 工具链与最小依赖闭环CMU-15-445 实验代码对编译器版本敏感。官方要求 GCC ≥ 7.5 或 Clang ≥ 6.0但实测 GCC 9.4 是最稳定的组合GCC 10 在std::shared_ptr的weak_ptr锁竞争模拟中会触发未定义行为。Ubuntu 20.04/22.04、CentOS 8 Stream、macOS MontereyXcode 13.3均可直接构建Windows 用户必须使用 WSL2非 Git Bash 或 MinGW否则mmap()和pthread_rwlock_t行为不一致会导致 BufferPoolManager 测试随机挂起。# Ubuntu 22.04 示例安装核心工具链 sudo apt update sudo apt install -y \ build-essential \ cmake \ libgtest-dev \ libgmock-dev \ libboost-all-dev \ gdb \ valgrind # 手动编译 gtest/gmock避免 Ubuntu 自带版本 ABI 不兼容 sudo apt remove libgtest-dev libgmock-dev cd /tmp git clone https://github.com/google/googletest.git -b v1.11.0 cd googletest mkdir build cd build cmake .. sudo make install提示gmock-gtest-all.cc和gmock_main.cc是课程定制版 GoogleTest 链接桩不要替换为系统自带 gtest。课程测试框架强制要求TEST_F(BPlusTreeTest, InsertTest)这类 fixture 模式且日志输出格式与b_plus_tree_test.cpp中的EXPECT_EQ()断言强耦合。2.2 构建流程CMake 配置关键参数与 Debug 符号注入解压后进入CMU-15-445-master目录执行以下构建命令。注意CMAKE_BUILD_TYPEDebug不仅开启-g还启用课程自定义的ENABLE_LOGGING宏使LOG_INFO(Page %d pinned)输出到stderrmkdir build cd build cmake -DCMAKE_BUILD_TYPEDebug \ -DENABLE_LOGGINGON \ -DENABLE_TESTSON \ -DCMAKE_CXX_STANDARD11 \ .. make -j$(nproc)构建成功后你会看到bin/bustub_server轻量级交互式 SQL shell基于sqlite3.c改写支持CREATE TABLE,INSERT,SELECTbin/bustub_test所有单元测试可执行文件含buffer_pool_manager_test,b_plus_tree_test,lock_manager_testlib/libbustub.a静态库供后续扩展模块链接验证是否构建成功./bin/bustub_test --gtest_filterBufferPoolManagerTest.* | head -20 # 应看到类似输出 # [] Running 7 tests from 1 test suite. # [----------] Global test environment set-up. # [----------] 7 tests from BufferPoolManagerTest # [ RUN ] BufferPoolManagerTest.Pintwice # [ OK ] BufferPoolManagerTest.Pintwice (0 ms)2.3 运行第一个测试用 GDB 跟踪 BufferPoolManager 的 Page Pin 流程以BufferPoolManagerTest.Pintwice为例该测试验证同一页面被PinPage()两次后ref_count是否正确累加# 启动 GDB 并设置断点 gdb ./bin/bustub_test (gdb) b buffer_pool_manager.cpp:127 # PinPage() 函数入口 (gdb) r --gtest_filterBufferPoolManagerTest.Pintwice当程序停在断点时执行(gdb) p *page # 查看 page 结构体内容 (gdb) p page-GetPinCount() # 输出 1第一次 Pin (gdb) n # 单步执行 (gdb) p page-GetPinCount() # 输出 2第二次 Pin 后参数说明--gtest_filter是 GoogleTest 的测试筛选语法BufferPoolManagerTest.Pintwice对应buffer_pool_manager_test.cpp中TEST_F(BufferPoolManagerTest, Pintwice)的测试名。课程所有测试均采用TEST_Ffixture test确保每个测试前自动调用SetUp()初始化BufferPoolManager实例。2.4 启动交互式 Shell验证 B 树索引的实时插入与范围扫描bustub_server是课程定制的 CLI支持基础 DML但不解析 SQL 语法树而是将INSERT INTO t1 VALUES (1, a)直接映射为TableHeap::InsertTuple()调用./bin/bustub_server bustub CREATE TABLE t1(id int, name varchar); bustub INSERT INTO t1 VALUES (1, Alice); bustub INSERT INTO t1 VALUES (2, Bob); bustub SELECT * FROM t1 WHERE id 0; # 输出 # 1|Alice # 2|Bob此时b_plus_tree.cpp中的Insert()方法已被触发。若想观察 B 树分裂过程需在BPlusTree::Insert()开头加断点并用p *root_page_查看节点结构。注意课程 B 树实现默认 key 类型为int64_tvarchar字段实际存储为char[64]比较函数使用memcmp()非strcmp()。3. 缓冲池管理器LRU-K 替换策略与 Pin/Unpin 的引用计数陷阱3.1 设计原理为什么不用 LRU而用 LRU-KCMU-15-445 的BufferPoolManager实现的是LRU-KK2算法而非经典 LRU。核心动机是解决“一次性扫描污染缓存”问题当执行全表扫描如SELECT * FROM huge_table时传统 LRU 会把所有刚读入的页面推到队尾导致热点页面被挤出。LRU-K 记录每个页面最近 K 次访问的时间戳仅当 K 次访问间隔均大于阈值才判定为冷数据。课程实现中K 固定为 2replacer_成员维护一个std::listframe_id_t但每个frame_id_t关联一个std::vectortimestamp_t存储最近两次访问时间。// buffer_pool_manager.cpp 关键逻辑 bool BufferPoolManager::FindVictimFrame(frame_id_t *frame_id) { for (const auto fid : replacer_-GetCandidateList()) { // 获取该 frame 最近两次访问时间 auto times page_table_[fid]-GetAccessHistory(); // 返回 vectortimestamp_t if (times.size() 2 (times.back() - times[times.size()-2]) kLRUKThreshold) { *frame_id fid; return true; } } return false; }注意kLRUKThreshold默认为10000001 秒单位为微秒。该值在buffer_pool_manager.h中定义不可在运行时修改需重新编译。3.2 Pin/Unpin 语义ref_count 不是“引用计数”而是“持有者计数”PinPage()并非增加智能指针引用而是向page_table_中对应Page*的pin_count_字段 1UnpinPage()则 -1。关键约束是只有pin_count_ 0且is_dirty_ false的页面才可被FindVictimFrame()选为淘汰目标。这意味着事务在修改页面前必须PinPage()否则DirtyPage()调用会失败UnpinPage()后页面仍驻留内存只是解除“禁止淘汰”锁FlushPage()强制写盘并重置is_dirty_但pin_count_不变。// table_page.cpp 中 TablePage::InsertTuple() 的典型用法 bool TablePage::InsertTuple(const Tuple tuple, RID *rid, Transaction *txn) { // 1. 确保页面已 Pin由上层 BufferPoolManager 调用保证 assert(pin_count_ 0); // 2. 插入后标记 dirty is_dirty_ true; // 3. 事务提交时BufferPoolManager::UnpinPage() 会检查是否可刷盘 }3.3 常见问题排查Pin/Unpin 失配导致的段错误与死锁现象 1Segmentation fault在BufferPoolManager::UnpinPage()中访问空指针原因UnpinPage()被调用时传入的page_id在page_table_中不存在即页面已被FlushPage()后DeletePage()但上层代码仍持有旧Page*指针。解决在UnpinPage()开头添加防御性检查if (page_table_.find(page_id) page_table_.end()) { LOG_WARN(UnpinPage called on non-existent page %d, page_id); return false; }现象 2bustub_test卡死在BufferPoolManagerTest.FlushAllPages原因FlushAllPages()遍历page_table_时某页面pin_count_ 0且is_dirty_ true导致FlushPage()返回false循环永不退出。解决课程测试用例假设所有测试页在FlushAllPages()前已Unpin。检查你的测试是否遗漏UnpinPage()或在SetUp()中未正确初始化BufferPoolManager。现象 3valgrind --toolmemcheck报告Invalid read of size 8在replacer_.Remove()原因LRUKReplacer::Remove()被调用时对应frame_id的页面已被DeletePage()但replacer_的candidate_list_仍持有该frame_id。解决在DeletePage()中同步调用replacer_-Erase(frame_id)课程原始代码缺失此步需手动补丁。4. B 树索引从叶子分裂到内部节点合并的完整状态机4.1 节点类型与内存布局InternalPage 与 LeafPage 的二进制差异课程 B 树严格区分InternalPage和LeafPage二者共用Page基类但内存布局完全不同LeafPage[size][key0][value0][key1][value1]...[key_n][value_n]value是RID8 字节InternalPage[size][key0][page_id0][key1][page_id1]...[key_n][page_id_n]page_id是page_id_t4 字节// b_plus_tree_internal_page.cpp 关键字段 class BPlusTreeInternalPage { private: // 第一个 key 为空哨兵实际 keys 从 offset 1 开始 index_key_type GetKeyAt(int index) const { return array_[index].first; } page_id_t GetValueAt(int index) const { return array_[index].second; } // array_ 是 std::vectorstd::pairindex_key_type, page_id_t };注意index_key_type默认为int64_t若需支持字符串 key需修改BPlusTree::KeyComparator模板参数并重写Compare()函数。课程未提供字符串 key 的完整实现仅预留接口。4.2 插入分裂流程递归向上修正父节点的 key 与 page_idBPlusTree::Insert()的核心是InsertIntoParent()—— 当叶子节点满时分裂为left_page和right_page然后调用InsertIntoParent()将right_page的最小 key 和page_id插入父节点。若父节点也满则继续向上分裂直至根节点。课程实现中根节点分裂会创建新根高度 1// b_plus_tree.cpp 关键路径 void BPlusTree::Insert(const K key, const V value) { LeafPage *leaf FindLeafPage(key); if (leaf-GetSize() leaf-GetMaxSize()) { leaf-Insert(key, value); } else { LeafPage *new_leaf Split(leaf); // 分裂出 new_leaf InsertIntoParent(leaf, new_leaf-KeyAt(0), new_leaf-GetPageId()); } } void BPlusTree::InsertIntoParent(BPlusTreePage *old_page, const K key, page_id_t new_page_id) { if (old_page root_page_) { // 创建新根 InternalPage *new_root reinterpret_castInternalPage*(AllocatePage()); new_root-SetKeyAt(0, key); new_root-SetValueAt(0, old_page-GetPageId()); new_root-SetValueAt(1, new_page_id); root_page_id_ new_root-GetPageId(); } else { // 在父节点中插入 InternalPage *parent FetchPage(old_page-GetParentPageId()); parent-Insert(key, new_page_id); } }4.3 范围查询优化ScanKey与ScanKeyRange的游标复用BPlusTree::ScanKeyRange()是课程重点优化点它不逐个FetchPage()而是利用LeafPage的next_page_id_链表顺序遍历。关键技巧是复用LeafPage实例避免频繁new/delete// b_plus_tree.cpp template typename K, typename V, typename KC void BPlusTreeK, V, KC::ScanKeyRange(const K lower_key, const K upper_key, std::vectorstd::pairK, V *result) { LeafPage *leaf FindLeafPage(lower_key); while (leaf ! nullptr) { for (int i 0; i leaf-GetSize(); i) { K key leaf-KeyAt(i); if (key lower_key key upper_key) { result-emplace_back(key, leaf-ValueAt(i)); } else if (key upper_key) { goto done; // 提前退出 } } page_id_t next_id leaf-GetNextPageId(); if (next_id INVALID_PAGE_ID) break; leaf reinterpret_castLeafPage*(FetchPage(next_id)); } done: return; }参数说明INVALID_PAGE_ID定义为0next_page_id_在LeafPage构造时初始化为0Insert()末尾更新。课程未实现prev_page_id_故不支持反向范围扫描。4.4 常见问题排查B 树测试失败的四大根源现象 1BPlusTreeTest.InsertTest中EXPECT_EQ(result.size(), 100)失败实际为 99原因Insert()未处理 key 重复场景。课程 B 树允许重复 key但LeafPage::Insert()默认覆盖同 key 的 value。需修改LeafPage::Insert()逻辑当key KeyAt(i)时执行InsertAt(i1, key, value)而非UpdateAt(i, value)。现象 2BPlusTreeTest.ConcurrentInsertTest死锁在latch_.Lock()原因BPlusTree::Insert()在FindLeafPage()后未释放root_latch_导致并发插入时多个线程在根节点等待。课程原始实现要求在FindLeafPage()返回后立即root_latch_.Unlock()再对叶子节点加 latch。现象 3valgrind报告Conditional jump or move depends on uninitialised value(s)在InternalPage::Insert()原因array_vector 的resize()未初始化新元素。InternalPage::Insert()中array_.resize(size_ 1)后array_[size_]的firstkey和secondpage_id为未定义值。需显式赋值array_[size_].first key; array_[size_].second value_id;现象 4ScanKeyRange()返回结果乱序原因next_page_id_链表断裂。Split()函数中right_page-SetNextPageId(left_page-GetNextPageId())和left_page-SetNextPageId(right_page-GetPageId())顺序颠倒。正确顺序是先设right_page-next left_page-next再设left_page-next right_page-page_id。5. 并发控制与恢复机制两阶段锁与 WAL 日志的协同验证5.1 两阶段锁协议2PLLockManager 的粒度与超时设计课程LockManager实现行级锁Row-Level Lock锁对象为RIDRecord ID而非页面或表。LockRequestQueue使用std::listLockRequest维护等待队列GrantLock()按 FIFO 顺序尝试授予锁。关键设计是超时机制每个LockRequest包含timeout_ts_LockManager::LockShared()在等待时检查std::chrono::steady_clock::now() timeout_ts_超时则返回false。// lock_manager.cpp bool LockManager::LockShared(Transaction *txn, const RID rid) { std::unique_lockstd::mutex lck(latch_); auto queue lock_table_[rid]; LockRequest req{txn, LockMode::SHARED, std::chrono::steady_clock::now() 3s}; queue.request_queue_.push_back(req); // ... 等待逻辑 if (std::chrono::steady_clock::now() req.timeout_ts_) { queue.request_queue_.erase(std::find(queue.request_queue_.begin(), queue.request_queue_.end(), req)); return false; } }注意3s是硬编码超时值定义在lock_manager.h中。若需调整修改LOCK_TIMEOUT宏并重新编译。5.2 WAL 日志结构LogRecord 的物理格式与 Checkpoint 触发条件WAL 日志写入log_manager.cpp中的WriteLog()每条LogRecord固定 32 字节[4]byte type | [4]byte txn_id | [8]byte lsn | [8]byte prev_lsn | [8]byte page_id其中type为BEGIN,COMMIT,ABORT,UPDATE,INSERT等lsnLog Sequence Number是单调递增的 8 字节整数prev_lsn指向前一条日志的 lsn。Checkpoint 触发条件是当log_buffer_满默认 64KB或txn-GetState() COMMITTED时强制刷盘。// log_manager.cpp void LogManager::WriteLog(const LogRecord record) { // 1. 写入 log_buffer_ memcpy(log_buffer_ buffer_offset_, record, sizeof(LogRecord)); buffer_offset_ sizeof(LogRecord); // 2. 检查 buffer 是否满 if (buffer_offset_ LOG_BUFFER_SIZE) { FlushLog(); // write() 到 disk_log_ } // 3. 若事务提交立即刷盘 if (record.GetTxnID() ! INVALID_TXN_ID record.GetLogType() LogType::COMMIT) { FlushLog(); } }5.3 恢复流程Analysis → Redo → Undo 的三阶段执行RecoveryManager::Recover()按 ARIES 风格执行Analysis扫描 WAL 日志重建dirty_page_table_哪些页面被修改但未刷盘和transaction_table_哪些事务未提交Redo重放所有UPDATE/INSERT日志恢复dirty_page_table_中页面的最新状态Undo对transaction_table_中ABORTED或未COMMIT的事务反向执行其日志如UPDATE的Undo()将页面改回旧值。// recovery_manager.cpp void RecoveryManager::Recover() { AnalysisPhase(); RedoPhase(); UndoPhase(); } void RecoveryManager::RedoPhase() { for (auto page_id : dirty_page_table_) { Page *page bpm_-FetchPage(page_id); // 重放该 page_id 对应的所有 UPDATE 日志 for (auto log : logs_for_page_[page_id]) { if (log.GetLogType() LogType::UPDATE) { page-Redo(log); // Page::Redo() 解析 log 并修改内存 } } } }注意RedoPhase()必须在UndoPhase()之前否则未提交事务的修改可能被Undo覆盖导致数据丢失。5.4 常见问题排查并发与恢复的复合故障现象 1LockManagerTest.DeadlockTest永远不返回原因死锁检测算法未实现。课程LockManager::CheckDeadlock()是空桩需自行实现基于等待图Wait-for Graph的环检测。当前测试用例依赖LockManager::LockExclusive()的超时返回false模拟死锁若超时值过大测试会卡住。现象 2RecoveryManagerTest.CrashTest中EXPECT_EQ(table_heap_-GetTupleCount(), 100)失败原因CrashTest模拟进程崩溃后重启但RecoveryManager::Recover()未正确处理INSERT日志的 redo。INSERT日志的Redo()需调用TableHeap::InsertTuple()而课程Page::Redo()未覆盖INSERT类型。需在Page::Redo()中添加case INSERT:分支。现象 3valgrind报告Use of uninitialised value of size 8在LogManager::WriteLog()原因LogRecord构造时未初始化prev_lsn_。LogRecord的构造函数中prev_lsn_应设为INVALID_LSN定义为0但原始代码遗漏。现象 4并发插入后SELECT COUNT(*)返回值小于预期原因LockManager::LockShared()未阻塞INSERT操作。INSERT需要EXCLUSIVE锁但测试用例中LockShared()被错误地用于插入场景。应使用LockExclusive()并在TableHeap::InsertTuple()开头获取锁。6. 实战技巧用 GDB Valgrind 定位 BufferPoolManager 的隐式内存泄漏6.1 内存泄漏定位从valgrind --leak-checkfull到精准定位课程BufferPoolManager最隐蔽的泄漏点在于Page对象的生命周期管理。AllocatePage()返回的Page*由BufferPoolManager统一管理但DeallocatePage()仅在DeletePage()中调用而DeletePage()又依赖UnpinPage()后pin_count_ 0。若某页面被Pin后未Unpin它将永远驻留内存。用valgrind检测valgrind --leak-checkfull --show-leak-kindsall \ --track-originsyes \ ./bin/bustub_test --gtest_filterBufferPoolManagerTest.*关键输出示例12345 8 bytes in 1 blocks are definitely lost in loss record 1 of 10 12345 at 0x4C30F2F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 12345 by 0x404A5F: BufferPoolManager::AllocatePage() (buffer_pool_manager.cpp:89) 12345 by 0x403E21: BufferPoolManagerTest::SetUp() (buffer_pool_manager_test.cpp:45)这表明SetUp()中AllocatePage()分配的内存未被释放。追踪buffer_pool_manager_test.cpp第 45 行// buffer_pool_manager_test.cpp void BufferPoolManagerTest::SetUp() { bpm_ new BufferPoolManagerInstance(5, disk_manager_.get(), 0); page_ bpm_-NewPage(page_id_); // AllocatePage() 被调用 // 缺少bpm_-UnpinPage(page_id_, true); // true 表示 dirty触发 Flush }6.2 GDB 动态监控watchpage-pin_count_的每一次变化在BufferPoolManager::PinPage()和UnpinPage()中设置硬件观察点捕获pin_count_的所有修改gdb ./bin/bustub_test (gdb) b buffer_pool_manager.cpp:127 # PinPage() 入口 (gdb) r --gtest_filterBufferPoolManagerTest.Pintwice (gdb) # 程序停住后找到 page 指针地址 (gdb) p page $1 (Page *) 0x7ffff7f01000 (gdb) watch *(int*)((char*)$1 16) # pin_count_ 在 Page 结构体偏移 16 字节 Hardware watchpoint 1: *(int*)((char*)$1 16) (gdb) c # 程序会在 pin_count_ 修改时中断显示修改位置技巧Page结构体定义在page.hpin_count_是第二个成员page_id_t page_id_占 4 字节int pin_count_占 4 字节故偏移为 8错Page有虚函数表指针vptr64 位系统占 8 字节故pin_count_偏移为8 4 12再错Page继承自SlottedPageSlottedPage有int slot_num_4 字节和int free_space_pointer_4 字节故pin_count_偏移为8(vptr) 4 4 16。用p sizeof(Page)和p ((Page*)0)-pin_count_验证。6.3 故障注入测试强制FlushPage()失败验证恢复逻辑课程未提供FlushPage()失败的测试用例但生产环境必须处理磁盘满、I/O 错误。我们手动注入故障// 修改 disk_manager.cpp 的 WritePage() bool DiskManager::WritePage(page_id_t page_id, const char *page_data) { // 注入 10% 概率写失败 static std::random_device rd; static std::mt19937 gen(rd()); static std::bernoulli_distribution d(0.1); if (d(gen)) { LOG_ERROR(Simulated disk write failure for page %d, page_id); return false; // 模拟 write() 返回 -1 } // 原始 write() 逻辑... }然后运行RecoveryManagerTest.CrashTest观察Recover()是否能从部分写入的日志中恢复一致状态。若RedoPhase()失败说明日志lsn与页面page_lsn_的校验逻辑有缺陷。从那以后我每次调试 BufferPoolManager都强制走一遍valgrind --leak-checkfullgdb watch pin_count_的组合流程——不是为了证明代码没 bug而是为了在git commit前亲手确认那块内存确实被UnpinPage()归还了。数据库内核的稳定从来不是靠测试覆盖率数字堆出来的而是靠你盯着pin_count_从 2 变成 1、再变成 0 的那一秒。希望帮到你。本文还有配套的精品资源点击获取