简介这是一份基于CMU-15445课程Bustub数据库系统的个人实现源码包面向数据库方向学生、系统开发者及准备相关项目面试的求职者可用于深入理解存储管理、查询优化、事务处理等DBMS核心机制。包内共1195个文件压缩后约33.89MB以260个h头文件、209个cpp及149个cc源文件为主辅以Python脚本、Shell工具、HTML/CSS前端资源及Bazel、CMake等构建配置覆盖从核心代码到环境部署、测试脚本的完整工程链路。已有162人学习下载。代码遵循学术规范未公开托管适合放入个人简历展示阅读时可结合项目结构梳理Bustub各模块实现思路参考C内存管理与并发控制写法利用Dockerfile与测试文件辅助本地编译验证快速建立从理论到工程实现的整体认知。1. CMU-15445 与 Bustub一门课和一个能写进简历的内核项目做后端的人迟早会撞上这样一个问题天天用 MySQL、PostgreSQL可真要说出一条 SQL 从客户端到磁盘的完整路径大多数人是懵的。CMU-15445 这门课就是来解决这个问题的而 Bustub 是这门课的配套项目——一个麻雀虽小、五脏俱全的关系型数据库内核从缓冲池、BTree 索引、查询执行器到并发控制全部要求你亲手写一遍。我身边不少人最初只是冲着“课程名气大”去的结果写着写着发现这几乎是目前能接触到的最好的数据库内核入门源码实践。它不像读 PostgreSQL 源码那样动辄百万行也不像做某个 CRUD 项目那样毫无技术含量。Bustub 让你在一个学期内把数据库最核心的几十个文件啃完每一行代码都踩在真实工程问题上。这篇文章就围绕“个人实现”这条主线讲清楚这个项目怎么搭、怎么写、怎么避坑以及最终怎么能变成一份拿得出手的设计源码。2. 把 Bustub 跑起来环境、构建与三级测试目标2.1 构建环境选型为什么绕不开 Linux 和 Clang先说结论不要用 Windows 原生环境做这个项目。Bustub 的构建脚本、测试框架和内存检测工具全部围绕 Linux 设计Windows 下即使勉强跑通也会在教学环境依赖、内存调试和性能验证上浪费大量时间。我见过有人在 WSL 里折腾三天最后发现是文件权限和路径长度问题导致编译失败。一个干净的 Ubuntu 20.04/22.04 虚拟机或者云主机是最稳妥的选择。依赖项并不复杂Clang、CMake、Flex、Bison 以及一个较新版本的 C 标准库。有个容易被忽略的点Bustub 官方推荐 Clang 而不是 GCC因为它的测试框架里有不少依赖 LLVM 工具链的编译期行为。如果你用 GCC 编译某些模板特化和内存对齐相关的代码可能会产生诡异的行为这不是“玄学”是工具链差异。# 安装必要依赖Ubuntu 22.04 为例 sudo apt update sudo apt install -y clang cmake flex bison libreadline-dev zlib1g-dev # 克隆并编译 git clone https://github.com/cmu-db/bustub.git cd bustub mkdir build cd build cmake -DCMAKE_BUILD_TYPEDebug .. make -j$(nproc)我一般会把-DCMAKE_BUILD_TYPEDebug作为默认选项因为本项目大量依赖断言和调试符号来定位问题。Release 模式虽然在跑步测试时更快但一旦遇到段错误你面对的就是一堆没有行号信息的黑匣子。等代码完全稳定了再切 Release 做性能验证不迟。2.2 代码结构速览先认清哪些文件是你该写的Bustub 的源码树并不复杂但第一次打开时容易迷失。核心目录就是src/和src/include/头文件和实现文件一一对应。你需要重点关注的并不是全部代码而是标有TODO(P0)、TODO(P1)这类标记的文件——这些才是你要实现的“个人设计”部分。# 查看所有待实现的 TODO 标记 grep -rn TODO(P src/ src/include/ | wc -l # 按优先级查看分布 grep -rn TODO(P0) src/ src/include/ | head -20完成这个命令后你会看到大约 30 个左右的 TODO 点分布在缓冲池、BTree、执行器和并发控制模块中。这是个很关键的“范围认知”阶段很多人在 P0 的 LRU-K 替换策略上较劲太久却不知道 P1 的 BTree 才是真正的重头戏。2.3 三级测试目标本地测试、Grace Grade 与性能基准这个项目的测试体系分成三层。第一层是 Google Test 单元测试覆盖每个模块的基本功能第二层是课程官方的 Grace Grade 评分系统跑的是更全面的测试集第三层是性能基准比如 Leaderboard 测试要求你的 BTree 在特定并发场景下达到一定的吞吐量。我的建议是不要把精力全部放在“通过所有本地测试”上。本地测试只是保底Grace Grade 会做很多边界情况和并发压力测试这些才是拉开分数差距的地方。一个务实的目标顺序是先保证单线程功能全部通过再优化并发控制的正确性最后才是性能调优。# 只跑当前模块的测试而不是全量测试 cd build ./bustub-test --gtest_filterBufferPoolManager* # 查看测试用例列表 ./bustub-test --gtest_list_tests | head -50这一步的意义在于让你建立“增量式开发”的节奏。Bustub 的模块依赖关系很强比如 P3 的查询执行器依赖 P1 的缓冲池如果你不从最小可运行版本开始积累很容易陷入“写了三百行代码一编译全是错根本不知道从哪改起”的困局。3. 逐模块拆解从 LRU-K 到事务管理器四个必写的核心组件3.1 缓冲池管理LRU-K 替换策略为什么比 LRU 更适合数据库缓冲池是数据库的内存缓存层Bustub 在 P0 阶段就要求实现 LRU-K 替换策略。和传统的 LRU 不同LRU-K 关注的是“访问历史次数和最近访问时间”的二元组合它的核心思想是如果一个页在最近 K 次访问中表现出高频率它就应该被保留而不是仅因为“刚刚被访问过”就享受高优先级。这个设计的合理性在数据库场景中非常明显。全表扫描会让大量页变成“一次性访问”的状态如果只使用 LRU这些刚被扫过的页会占据缓冲池导致真正被频繁访问的索引页被挤出去。LRU-K 通过记录访问历史能够更准确地识别哪些页是“长期热点”。// src/include/buffer/lru_k_replacer.h 中的核心接口 class LRUKReplacer { public: // 记录一次访问历史frame_id 是缓冲池帧编号 void RecordAccess(frame_id_t frame_id) { // 维护访问历史队列和 eviction 候选集 // 具体实现要点使用 std::list 存储 frame 的访问记录 auto history access_history_[frame_id]; history.push_back(current_timestamp_); if (history.size() k_) { history.pop_front(); // 只保留最近 K 次访问 } } };我当时实现时踩了一个隐蔽的坑RecordAccess和Evict之间的同步问题。LRU-K 要求只淘汰“不可固定的帧”未被 pin 住的页而判断一个帧是否可淘汰的时机点非常微妙。正确做法是每次Evict时先遍历所有帧的访问历史找出最早一次访问时间最小的那个并且跳过所有 pin 计数大于零的帧。这块逻辑如果不加锁在并发测试下会出数据竞争而 GTest 的 TSan 配置会自动检测到这种问题。3.2 BTree 索引插入分裂与删除合并的边界条件BTree 是 Bustub 课程里最难啃的骨头也是工程价值最高的一块。与教科书里简单的二叉树不同BTree 的插入和删除需要处理节点分裂、节点合并、根节点变化、叶子节点链表维护等一堆边界条件。课程给了一个可视化调试工具b_plus_tree_printer但实际开发时的核心工具是 logging 和 gdb。插入操作的关键路径是从根节点向下搜索找到目标叶子节点插入键值对如果溢出则分裂。这里的难点在于分裂时需要把中间键上提到父节点并且正确连接新的兄弟节点。如果父节点也满了需要递归分裂直到根节点。// 插入分裂的核心逻辑简化版 void BPlusTree::InsertIntoLeaf(LeafNode *leaf, const KeyType key, const ValueType value) { if (leaf-IsFull()) { // 1. 创建新的叶子节点 auto *new_leaf NewLeafNode(); // 2. 将后半部分键值对移动到新节点 leaf-MoveHalfTo(new_leaf); // 3. 在父节点中插入新的分隔键 InsertIntoParent(leaf, new_leaf-GetFirstKey(), new_leaf); } else { leaf-Insert(key, value); } }删除操作比插入更繁琐。删除后的下溢小于最小填充数需要优先尝试向兄弟节点借键rotation不行才做合并merge。Bustub 的测试用例设计得很刁钻专门设计了连续删除后索引结构仍然保持正确的场景。我花了整整一个周末的时间重写了三版删除逻辑才全部通过最后发现原来借键时不仅要更新父节点的分隔键还要同步更新叶子链表的 prev/next 指针这是一个每周都有几十人在讨论区问的经典坑点。3.3 查询执行器火山模型与表达式求值的拆解P3 的查询执行器是 Bustub 里最有“数据库感觉”的部分。这一阶段要求实现一系列执行器节点SeqScan、Insert、Delete、IndexScan、Aggregation、Limit、NestedLoopJoin 等。整个架构使用的是标准的火山模型——每个执行器都实现Next()接口每次调用返回一条元组。对这部分的个人实现我的经验是不要从 NestedLoopJoin 开始写而应先完成 SeqScan 和 Insert/Delete 这三个最基础的节点。因为它们构成了表读写的基础路径后面的 IndexScan 和 Join 都依赖于对 Tuple 和 TableHeap 的理解。// SeqScan 执行器的核心实现 bool SeqScanExecutor::Next(Tuple *tuple, RID *rid) { // 从头开始扫描表堆每次调用返回下一个满足条件的元组 while (table_iterator_ ! table_info_-table_-End()) { auto [cur_tuple, cur_rid] *table_iterator_; table_iterator_; // 执行谓词过滤如果存在 WHERE 条件 if (predicate_ nullptr || predicate_-Evaluate(cur_tuple, schema_).GetAsbool()) { *tuple cur_tuple; *rid cur_rid; return true; } } return false; }这里有一个非常容易翻车的细节predicate_-Evaluate的调用时机。很多人会写成先取下一个元组再判断谓词导致最后一条有效元组被跳过。这个 bug 的诡异之处在于它只在特定数据分布下才会出现单测里很难发现。我在跑 TPC-H 风格的测试时才暴露出来。3.4 并发控制锁管理器与死锁检测的工程化实现P4 的锁管理器是课程里最后一个大模块。Bustub 要求实现共享锁、排他锁、意向锁以及死锁检测。这里的难点不是锁的语义——那部分教科书讲得很清楚——而是“锁的升级”“锁的等待队列”和“死锁检测”三者之间的交互。死锁检测的实现思路并不复杂构建一个等待者-持有者的有向图定期检测环发现环后选择一个 victim 事务回滚。但真正的工程难点在于“什么时候检测”“怎么选择 victim”“回滚后其他事务应该做什么反应”。// 死锁检测的核心数据结构 class LockManager { // 等待者 - 持有者 的映射边 std::unordered_maptxn_id_t, std::unordered_settxn_id_t waits_for_; // 定期执行的检测线程 void RunDeadlockDetection() { while (!stop_) { std::this_thread::sleep_for(std::chrono::milliseconds(1000)); std::lock_guardstd::mutex lock(lock_table_latch_); auto cycle FindCycle(waits_for_); if (cycle.has_value()) { auto victim ChooseVictim(cycle.value()); AbortTransaction(victim); } } } };选择 victim 的规则在课程里有明确要求优先选择事务 ID 较大较年轻的事务同时兼顾已经持有的锁数量。但实际跑测试时发现了一个微妙问题如果单纯按事务 ID 选可能会反复选中某个正在做长查询的事务导致它永远无法完成。更合理的做法是结合“事务年龄 持有的锁数量”做加权让老事务有更高的存活概率。4. 测试驱动开发用 GTest 和自定义工具验证每个阶段的正确性4.1 学会读测试源码比读源码更重要的事情Bustub 课程的测试文件里藏着一座金矿——每个测试用例的命名和注释都在告诉你这个模块的边界条件在哪。很多学生等着官方的 Grace Grade 评分却不知道test/目录下的 GTest 文件其实就是“开卷考试”的范围。// test/buffer/buffer_pool_manager_test.cpp 中的典型用例 TEST(BufferPoolManagerTest, UnpinAndReusePageTest) { // 核心意图验证 unpin 后页面可以被重新分配 // 场景创建一个容量为 1 的缓冲池连续分配两个页面 auto bpm std::make_uniqueBufferPoolManager(1); // 容量为 1 page_id_t page_a bpm-NewPage(); bpm-UnpinPage(page_a, true); page_id_t page_b bpm-NewPage(); ASSERT_NE(page_a, page_b); // 关键断言 }读测试源码的一个直接收益是你能精确知道某个函数在什么输入下会被调用以及期望的输出边界。比如上面的测试如果失败常见的原因是你的NewPage在缓冲池满了之后没有正确选择一个 victim 页或者UnpinPage没有正确维护 pin 计数。4.2 用自定义 SQL 语句做集成验证从底层到上层的完整链路Bustub 自带了一个命令行 shell你可以像使用 MySQL 一样输入 SQL 语句。这个工具在 P3 之后价值极大因为它能验证从解析、计划到执行的完整链路是否走得通。我习惯在完成每个执行器后就手工构造几条针对性 SQL 来测试。-- 创建一个测试表并插入数据 CREATE TABLE test_table (id INT, name VARCHAR(32)); INSERT INTO test_table VALUES (1, Alice); INSERT INTO test_table VALUES (2, Bob); -- 验证顺序扫描和投影 SELECT name FROM test_table WHERE id 1; -- 验证聚合函数 SELECT COUNT(*) FROM test_table;这里的执行计划会输出到终端你可以看到每个操作符的名字、涉及的表达式和预估行数。一个非常有用的技巧是在 shell 里执行EXPLAIN SELECT ...它会打印出执行计划树。如果你发现某条 SQL 走了 SeqScan 而不是 IndexScan先不要急着怀疑优化器先检查你的IndexScanExecutor是否正确处理了索引键的范围条件。4.3 性能验证Leaderboard 测试与热点分析当你功能全部通过后如果想要冲刺更高的分数就需要关注 Leaderboard 测试。这个测试集的关注点是在并发场景下你的 BTree 是否能够承受高吞吐的查询。这时候 Debug 版本的代码就能明显感到性能不足——大量断言检查和日志打印会拖慢速度。# 编译 Release 版本 cmake -DCMAKE_BUILD_TYPERelease .. make -j$(nproc) # 运行 Leaderboard 测试 cd build ./bustub-leaderboard-test --gtest_filterLeaderboardTest.*性能优化的常见切入点是锁粒度。Bustub 的 BTree 在 P2 阶段要求支持并发读写最朴素的做法是对整棵树加一把大锁这能保证正确性但性能极差。逐步细化为 latch crabbing 协议后吞吐量会有质的飞跃。我在优化时发现叶子节点的 latch 竞争是最大的瓶颈因为所有读操作最终都要锁叶子节点。通过把叶子节点上的读写锁改成 try-lock 加自旋重试的模式性能提升了大约 40%。5. 避坑指南个人实现中遇到的五个高频问题现象 → 原因 → 解决5.1 编译警告被当成错误Clang 的 -Werror 陷阱现象代码明明看起来没问题编译却报出几十个error: unused variable或error: implicit conversion。原因Bustub 的 CMake 配置开启了-Werror任何警告都会被升级为编译错误。这其实是课程有意为之逼迫你写出干净的代码但在开发初期非常折磨人。解决在CMakeLists.txt里找到target_compile_options注释掉-Werror但仅限本地方便开发用。提交代码前务必恢复否则会导致 Grace Grade 评分时直接编译失败。5.2 BTree 删除后索引结构不完整叶子节点链表断开现象删除大量键值后SELECT查询返回的行数变少甚至出现std::bad_alloc。原因合并叶子节点时只更新了父节点的指针没有同步维护叶子节点之间的prev_和next_双向链表。这个 bug 平时很难发现因为单线程的GetValue只走根到叶的路径不会用到叶子链表的横向遍历只有做全表扫描如SELECT *时才会触发。解决在合并逻辑中专门加一个步骤合并前先从叶子链表的结构开始检查。写一段校验函数遍历所有叶子节点检查prev_-next_ this是否成立不成立说明链表指针出了问题。5.3 事务回滚后没有释放锁死锁检测失效现象并发测试跑到一半突然卡死所有线程都阻塞在LockTable上。原因事务在死锁检测中被选为 victim 后只做了事务状态回滚但LockManager里该事务持有的锁没有释放。后续事务在等待这个永远不会释放的锁系统进入“活锁”状态。解决在AbortTransaction的实现中除了清除事务的WriteSet和还原数据外必须遍历LockManager的锁表释放当前事务持有的所有锁并唤醒对应的等待队列。5.4 缓冲区页面没有标记 dirty数据丢失无异常现象UPDATE语句执行成功但重启数据库后数据丢失。原因在BufferPoolManager::UnpinPage时is_dirty参数传入了false。查询执行器在修改页面数据后没有正确传递脏页标记导致页面被淘汰时没有写回磁盘。解决在TableHeap::UpdateTuple和DeleteTuple中调用UnpinPage时强制传入true。更稳妥的做法是让页面在被修改的时刻就标记为脏而不是依赖调用者传递参数。5.5 执行器在并发场景下的数据竞争Tuple 生命周期管理不当现象用 TSan 编译跑并发测试报data race on std::shared_ptrTableInfo或者偶发返回错误数据。原因多个执行器节点共享同一个TableInfo和Schema指针这些对象的所有权在查询计划销毁时统一释放。如果一个执行器还在迭代中另一个线程销毁了计划就会产生悬挂指针。解决在执行器构造函数中拷贝Schema对象而不是持有引用对TableInfo使用std::shared_ptr管理确保在所有执行器生命周期结束后才释放底层资源。6. 让源码成为“作品”代码组织、注释规范与进阶方向当你的 Bustub 全部测试都通过后面前还有一件更重要的事如何让这套代码看起来像一个“设计源码”而不是“作业草稿”。我的做法是花三个晚上做代码整理重点改三件事。第一头文件里的 TODO 注释全部删除改成自己的实现说明。写清楚“这个函数干了什么”“输入输出约束是什么”“边界情况如何处理”。这不仅是给别人看的更是给一个月后的自己看的。Bustub 的代码量大如果不留说明回头改 bug 时你会遗忘当时的思路。第二将分散在多处的条件编译开关统一整理。比如 Hw 版本标记#ifdef ENABLE_LOCK_MANAGER这类宏按课程阶段分组注释避免后续阅读时不知道哪些代码是“课程要求添加的”哪些是“个人扩展的”。第三补充一份项目级别的README.md内容包括编译步骤、测试命令、模块设计框图、踩坑记录、性能优化前后对比。很多面试官看项目时先打开 README如果这里写得清晰会留下“这个工程师有工程素养”的第一印象。做完这些整理后才算真正把 Bustub 从“课程项目”变成了“个人作品”。这几周写下的不仅仅是一个数据库内核的代码更是一套对存储引擎、索引结构、并发控制的直觉理解。以后再去读 MySQL 或 TiDB 的源码你会发现那些组件的命名和架构设计是那么熟悉。最后说个我自己的习惯每次提交一段新代码前强制自己回答三个问题——这个函数在什么输入下会失败这个锁的等待条件是什么如果事务在中间崩溃数据会变成什么状态答不上来就回去改代码。经过 Bustub 的洗礼这套思考方式现在已经成了我读任何后端源码的本能反应。希望帮到你。本文还有配套的精品资源点击获取