简介这是基于CMU-15445课程Bustub数据库系统的个人实现源码包面向数据库内核学习者、系统程序员及准备求职的在校学生用于理解DBMS底层机制并沉淀项目经验。压缩包共1195个文件、33.89MB以C/C源码h/cpp/cc为主辅以Python测试脚本、HTML/JS前端页面、CMake/Bazel构建配置、Dockerfile部署与Shell自动化文件覆盖从编译、运行、测试到容器化交付的完整开发链路。项目未在GitHub开源更适合作为简历中的个人项目展示目前已有162人学习浏览。包内还包含.gitignore、LICENSE、.clang-format/.clang-tidy等工程规范文件以及test.db、insert1.txt、test.log等测试调试样本与日志记录目录结构清晰可辅助复现实验场景。源码围绕存储管理、查询优化与事务处理等课程核心内容展开便于读者对照真实代码梳理模块划分与设计思路也适合系统设计、模块拆分、调试排错和简历表述时参考。1. Bustub 个人实现不只是抄完 15445 四个 Project 那么简单Bustub 是 CMU-15445 数据库系统课程的配套工程这门课要求学生从零手写一个 DBMS。拿到这份个人实现源码时我第一反应是看它到底做到哪一档缓冲池、B 树、查询执行、锁管理都齐了1208 个文件的规模放在个人项目里算相当完整。它不是课程答案的照搬而是把虚拟内存、磁盘 I/O、并发控制这些教科书理论全部落成了可编译、可运行的代码。适合三类人正在刷 15445 想找对照实现的同学、准备数据库内核方向面试的从业者以及想快速了解一个 DBMS 内部结构、又不想从头造轮子的工程师。2. Bustub 整体骨架Bazel 构建体系与缓冲池选型2.1 从 Bazel 构建文件读懂工程的编译规则拿到源码后我不急着读代码而是先跑构建。这份工程用 Bazel 管理根目录的 WORKSPACE.bazel 定义外部依赖BUILD.bazel 声明各个编译目标.bazelrc 和 .bazelversion 分别控制构建选项和 Bazel 版本。我拿到代码第一件事就是 cat .bazelversion否则本地 Bazel 版本不匹配构建时满屏的 unknown option 会让人误以为是代码语法问题。一个实用的习惯是先用 clang_format.bash 统一代码风格再用 Bazel 构建一个最小的库目标。Bustub 里每个子模块都有独立的 BUILD.bazel如果你的 IDE 跳转不到符号多半是 rules 里漏了 cc_library 的 deps而不是代码本身的问题。# 建议在工程根目录执行 # 先确认 Bazel 版本约束避免构建环境不一致 cat .bazelversion # 用 clang-format 统一代码风格建议提交代码前先跑一次 bash clang_format.bash # 构建核心的缓冲池管理模块验证编译链路是通的 bazel build //src:buffer_pool_manager第一行 cat 是为了确认构建环境第二行做代码格式化第三行是构建缓冲池模块。注意这里和用 CMake 的其他课程工程不一样Bustub 的 Bazel 目标名和目录结构严格对应src 目录下每个模块都有独立的 BUILD.bazeldeps 没补齐就编译不过。另外工程里带着 Dockerfile 和 .dockerignore本机环境乱掉的时候可以用容器起一个干净的构建环境省去系统性差异带来的排错时间。2.2 缓冲池管理器为什么 LRU-K 会打败 LRU缓冲池模块是整个工程的第一个硬骨头。它做的事很简单把磁盘页缓存到内存对外提供「按 page_id 拿页」的接口。难点在替换策略——经典 LRU 只记录最近一次访问遇到顺序扫描会把缓冲池冲垮实际操作里连续两次访问同一页的时间间隔比最近一次访问时间更能反映页的真实热度。这就是 Project 1 里 LRU-K 替换器存在的原因。LRU-K 的核心数据结构是访问历史记录加淘汰队列。我先给出一个最小实现框架// lru_k_replacer.h 的核心思路为每个 frame 维护访问历史 class LRUKReplacer { public: // 访问一次 frame刷新它的历史时间戳 void RecordAccess(frame_id_t frame_id) { // 注意第一次访问的 frame 先进入 history 阶段 // 只有访问次数达到 k 次才把帧放入可淘汰队列 } // 淘汰时优先选 history 里最早访问的帧 // 如果 history 为空则选可淘汰队列里倒数第 k 次访问最早的帧 bool Evict(frame_id_t *frame_id) { // 遍历两个队列返回最合适的 victim } private: size_t current_timestamp_{0}; // 逻辑时钟每次访问 1 size_t k_{2}; // 默认可配置2 表示 LRU-2 std::unordered_mapframe_id, size_t access_timestamps_; };这里的 k_ 是可以调的参数。Bustub 默认把替换器初始化为 LRUKReplacer(2)测试也以 k2 为准。实现时不要把历史时间戳和当前时间戳放在同一个容器里否则 Evict 时要区分「是否达到 k 次访问」会写得很别扭。我一开始图省事把时间戳全塞进一个 vector结果每次淘汰都要线性扫一遍跑到后续的并发测试直接超时。缓冲池管理器是在替换器之上叠加 pin 计数。每当执行器拿到一个页必须调用 Pin()用完调用 Unpin()只有 pin count 为 0 的页才有资格被替换。这段逻辑不复杂但极容易漏 Unpin——漏一次后面的淘汰顺序就乱了表现出来就是测试随机超时或断言失败。我在实现里习惯写一个 RAII 的 PageGuard 包装类让页在作用域结束时自动 Unpin能省掉一半的漏 pin 问题。2.3 可扩展哈希表索引从内存到磁盘的第一步Project 1 的另一个子模块是可扩展哈希表它服务于缓冲池内部的 page_id 到 frame_id 映射。可扩展哈希的核心是两个参数全局深度 global_depth_ 和局部深度 local_depth_。发生桶分裂时两者是否相等决定是翻倍整个目录还是只分裂单个桶。这个逻辑不画图很难写对我给出分裂部分的骨架// directory 分裂或 bucket 分裂的核心分支 void ExtendibleHash::Insert(const K key, const V value) { auto bucket_idx IndexOf(key); // 用 global_depth_ 截取哈希值 if (buckets_[bucket_idx]-IsFull()) { // 情况1局部深度 全局深度只需分裂当前桶 if (buckets_[bucket_idx]-GetLocalDepth() global_depth_) { SplitBucket(bucket_idx); } else { // 情况2局部深度 全局深度先翻倍目录再分裂 GlobalDepthIncrement(); SplitBucket(bucket_idx); } } buckets_[bucket_idx]-Insert(key, value); }IndexOf 使用 key 哈希的低 global_depth_ 位目录翻倍后旧桶的 entry 一分为二分到两个新桶。最常见的错误是 GlobalDepthIncrement 前手动复制旧目录的全部指针——其实用 vector.resize(1 global_depth_) 再逐个映射即可。可扩展哈希的摊还复杂度是 O(1)前提是分裂策略正确每个桶的 local depth 必须时刻记录否则后续合并时无法还原。写完这个模块我对哈希索引的认知从「用数组存」升级到了「用深度管理目录」算是第一个真正落地的基础组件。3. B 树索引从叶子分裂到 Latch Crabbing 并发3.1 为什么课程选 B 树而不是 LSM 或哈希索引15445 的 Project 2 是 B 树这几乎是所有数据库内核课程的标配。原因是它有三个同时成立的特性所有叶子在同一层、支持范围扫描、单点查找的 I/O 次数等于树的高度。Bustub 里的 B 树页分为内部节点页和叶子节点页两类页在磁盘上是定长的默认 4096 字节节点内能存多少 key 由 max_size_ 计算得出项目默认叶子页能容纳的键值对上限在 128 对左右。写实现之前要理解一个关键设计B 树的叶子节点存的是 key 和 value 对value 是 record id内部节点存的是 key 和 child_page_id。这两类页的布局完全不同实现时要分别建类不要试图用一个统一的页结构兼容。我见过有人图省事让内部节点也存 value功能测试能过一到并发或空间回收测试就露馅。另外工程里会出现 utf8proc_data.c 这种底层的 Unicode 数据文件原因很实际B 树的 key 可能是 varchar 类型排序和比较绕不开字符编码处理这种底层数据文件是给字符串比较算子用的。3.2 插入路径与分裂从叶子到根的一条龙插入操作是所有 B 树操作的难点。先写查找路径因为插入的第一步也是搜索// 在 B 树上查找 key 对应的叶子页 auto FindLeafPage(page_id_t root, const KeyType key) - page_id_t { auto page buffer_pool_-FetchPage(root); // 内部节点二分查找第一个 key 的子指针 while (!page-IsLeafPage()) { auto internal reinterpret_castInternalPage *(page-GetData()); auto child_id internal-Lookup(key); page buffer_pool_-FetchPage(child_id); } return page-GetPageId(); }Lookup 的实现要保证退化情况正确key 小于节点内第一个 key 时必须返回第一个 child不能越界。这里最容易翻车因为我一开始用 lower_bound 后没判断迭代器是否等于 end()结果范围查询时直接跳到不存在的页。插入一个键值对的完整路径是找到叶子判断是否满满则分裂把分裂产生的提升键插入父节点父节点满则递归向上分裂根节点分裂则新建根。课程测试里采用队列式分裂就够用即把一半 key 分给新页。真正的难点在于分裂后的提升键取右子节点第一个 key 作为父节点的分隔键这个 key 不会出现在父节点中但会被用于路由查找。3.3 并发控制Crabbing Protocol 的两种持有方式Project 2 到了并发版本难度直接上一个台阶。Bustub 要求实现 latch crabbing搜索时从根向下获取子节点 latch 后释放父节点 latch插入删除时则要一路持有可能导致分裂或合并的祖先节点的写 latch。核心判断是「当前节点是否安全」叶子节点分裂、合并和重分布都会影响父节点所以安全节点指插入时不分裂、删除时不合并的节点。实际操作里分两步。第一步判断安全的函数// 内部节点安全 插入后不溢出删除后不低于半满 bool IsSafeAfterInsert(InternalPage *node) { // 插入可能导致分裂size 1 max_size 才算安全 return node-GetSize() 1 node-GetMaxSize(); }第二步在插入时持有写锁直到遇到安全节点才释放祖先。这里的 latch 顺序必须严格从根到叶如果先锁了子节点再回头锁父节点两个线程一交叉就死锁。并发测试跑的线程数越多死锁越明显。我调试时把 std::lock_guard 和手动 unlock 混用结果作用域结束双重释放CPU 直接 100% 转圈改成每层操作都显式持有、显式释放才稳定下来。B 树这块我前前后后改了三版第一版功能对、并发死锁第二版死锁解决、性能差第三版才把 latch 的持有范围和释放时机理顺。4. 查询执行引擎火山模型与三种 Join 的取舍4.1 火山模型的 Next() 契约Project 3 把重点从存储层挪到执行引擎。火山模型的思路很直接一个查询计划树每个节点都是一个算子上层调用下层的 Next() 拿到一行算子内部维护自己的状态。Bustub 里所有执行器都实现 Init() 和 Next(Tuple *tuple, RID *rid)返回 false 表示没有更多数据。一个容易忽略的契约是Next() 返回的 Tuple 在下次调用时可能被覆盖如果上层算子保存了指针而不是拷贝数据就会读到被污染的值。我在写聚合算子时遇到过这个坑聚合算子需要把 Tuple 存入哈希表但如果直接存引用下一次 Next() 会篡改哈希表里的内容。解决方法是存 std::make_tuple 的副本代价是多一次拷贝换来的却是正确性。这个契约理解不到位后面所有算子都会出现随机性的数据错乱而且不好定位。4.2 Join 的三条路NLJ、Hash Join 与执行顺序Project 3 有多个 Join 实现最基础的是 NestedLoopJoin还有 HashJoin。NLJ 的逻辑不过三层循环外层遍历左表内层遍历右表对每行判断 join predicate。但它有致命的性能问题——每行都全表扫右表。实现里常见的优化是先把右表加载到内存至少减少页的重复 Fetch。Hash Join 的做法完全不同先用右表建哈希表再扫描左表用哈希探测。Bustub 的 HashJoin 实现中Build 阶段把 join key 的哈希值和对应的行存入一个 unordered_mapProbe 阶段逐行扫描左表。这里的坑在于哈希冲突时不同 key 可能落在同一个桶所以探测时不能只比较哈希值还要再比较一次实际 join key。我先只比较哈希值测试里用重复度低的数据全部通过一换到带大量重复 key 的用例就直接漏数据。// hash_join_executor.cpp 中 Build 阶段的简化实现 void HashJoinExecutor::BuildHashTable() { // 从右子节点拿到所有行按 join key 的哈希值分组 Tuple tuple{}; RID rid{}; while (right_child_executor_-Next(tuple, rid)) { // 1. 计算 join key 的哈希值注意表达式求值开销较大 auto key join_key_expr_.Evaluate(tuple, right_table_schema_); auto hash HashValue(key); // 2. 存入桶内这里存整行拷贝避免引用被后续覆盖 hash_table_[hash].push_back(tuple); } }用右表建哈希表是为了在探测阶段做一对一匹配。因为 Evaluate 每次都会重新计算表达式我在循环外面缓存了 schema 的索引引用能省下不少无谓的对象构造。如果 join key 是单列可以直接用列 index 替代整个表达式求值性能提升非常明显。4.3 物化与内存控制执行引擎另一个容易忽视的问题是物化。Limit 算子理论上可以不物化但排序和聚合必须物化。排序算子先把所有行收集到内存再调用 std::sort这一步在课程测试规模里没问题但如果右表行数到百万级内存和时间会失控。课程测试不会压到这个量级但我在实现排序器时仍然加了一个简单的 reserve 提示按子表大小预估行数避免 vector 反复扩容。内存控制的常见做法是需要跨多个算子共享中间结果时优先考虑重复执行子查询或临时文件不要把所有物化数据放在一个全局 list 里。Bustub 的课程范围不涉及外部排序但知道这个边界是好事——如果真到数据量大到内存装不下的场景就该考虑归并排序落盘而不是继续堆内存。5. 避坑清单五个让 15445 新手翻车的典型问题5.1 Bazel 版本不匹配构建直接翻车现象运行 bazel build //... 抛出一堆 unknown option 或 load 方法找不到的错误。原因工程用 .bazelversion 锁定了 Bazel 版本本机默认版本不同Bazel 会按本机默认版本来解释规则旧版本不认新版本的语法标记。解决先 cat .bazelversion再用 bazelisk 自动切到对应版本。如果项目里带 build.bat这是 Windows 下的包装脚本说明作者是用脚本统一环境的最好也看一眼里面有没有隐藏的编译参数。Dockerfile 也是同类作用容器构建能绕开本机环境的版本纠缠。5.2 缓冲池的「是否写回」幻觉现象跑磁盘测试时数据读出来是旧值或者频繁丢页调试时发现 FetchPage 返回的页内容不是上次写入的内容。原因BufferPool 有两个容易漏的地方。第一Unpin 时没有设置 is_dirty_页被淘汰时不写回磁盘第二NewPage 分配出来的页没有初始化数据读到的是上一个使用者留下的残留。解决在 Unpin 接口里强制要求调用方传入 dirty 标志并在页被淘汰前用 DiskManager::WritePage 写回。另外每次 NewPage 后调用一次 Memset(page-GetData(), 0, PAGE_SIZE)虽然多花一点时间但能杜绝大量诡异的脏数据问题。5.3 B 树并发时 latch 顺序颠倒直接死锁现象并发测试比如 4 线程同时插入运行到中间卡死CPU 占用掉到零。用 gdb 查看线程栈发现两个线程分别在等对方持有的 latch。原因经典死锁。线程 A 持有了父节点 latch 想要子节点的 latch线程 B 持有了子节点 latch 想要父节点的 latch锁顺序不一致交叉等待就必然发生。解决严格保证先父后子的顺序。搜索过程里一旦获得某个子节点的 latch就释放它的所有祖先节点。插入过程里如果决定要持锁到分裂完成那就要保证从根开始的路径上所有节点都按顺序获取。每层要么先持有上层再取下层要么在已知安全节点处统一释放。5.4 叶子节点指针不一致导致的范围扫描漏数据现象遍历叶子节点时跳过了一部分 key但单独查找每一个 key 都是正确的。原因B 树的叶子节点之间的 next 指针没在分裂时维护好。分裂发生时新节点右节点的 next 指针要指向原节点的旧 next原节点的 next 要指向新节点。如果写成两个节点互指链表末尾就会出现循环或断链。解决分裂函数里明确写成三条赋值OldNext Right-nextLeft-next RightRight-next OldNext。这三步缺一不可。我第一次实现就漏了最后一条导致尾部叶子死活遍历不完查了两天才定位到是分裂时的指针更新顺序问题。5.5 测试超时是玄学吗现象本地跑 grader 时有的用例稳定通过有的偶尔超时没有任何一致性规律。原因超时多半不是 CPU 算不过来而是死循环或死锁。把线程数从默认值调到 1如果超时消失基本可以确定是并发问题如果单线程也超时就要查 B 树的查找路径是不是出现了环形指针。解决把全部测试用 ASAN 跑一遍能暴露大部分内存错误但更直接的办法是写一个小的压力脚本连续执行 1000 次随机插入删除观察内存和耗时是否单调增长。这一步比看日志有用得多——很多内存泄漏只会让耗时缓慢上升而不是瞬间崩溃。源码里自带 test.db、insert1.txt 和 test.log 这类文件说明作者保留了一套原始测试环境。拿 insert1.txt 里的数据重新导入可以直接验证插入路径在真实文本上的行为这比我自己造的随机数据更接近课程评测的分布。6. 验证与调优本地跑通 Grader 测试的检查清单6.1 从编译到 Sanitizer 的验证顺序我拿到源码后习惯按四步走先编译再跑单测然后跑并发最后用 Sanitizer 压测。# 编译全部测试目标 bazel build //test:all # 跑单个模块的测试 bazel test //test:buffer_pool_manager_test # 开 ASAN 跑并发测试重点看内存越界和死锁 bazel test //test:b_plus_tree_contention_test --copt-fsanitizeaddress --linkopt-fsanitizeaddress这里 --copt 和 --linkopt 是手动开启 ASAN 的通用做法Bazel 里也常见封装好的 --configasan。ASAN 开启后运行速度会明显变慢但如果它能跑过后面的排查成本会低很多。并发测试类问题ASAN 不一定能直接抓到死锁但它能暴露掉内存越界导致的崩溃排除一个变量就少一条排查路径。6.2 容易漏掉的参数细节Bustub 的部分测试依赖全局配置比如 page_size 和缓冲池的 pool_size。测试里 BufferPoolManager 的 pool_size 默认设成较小值如果你的实现依赖「所有页都在内存」的假设一旦池子容量不够触发淘汰隐式的页失效问题就会爆发。我在验证时会写一个简单对比同一个用例分别在 pool_size10 和 pool_size100 下运行如果结果不一致说明缓冲区替换逻辑有隐患。# 简单的对比验证脚本思路根据实际情况调整参数 import subprocess for pool in [10, 100]: subprocess.run( [bazel, test, //test:buffer_pool_manager_test, --test_arg--pool_size str(pool)] )这段脚本的作用是强制替换器在不同容量下工作验证是否在任何池大小下都不会丢数据。它不能替代 grader但能提前发现「测试环境规模变大就翻车」的问题。另外.clang-format 和 .clang-tidy 不是摆设个人实现里代码风格不统一会让后期维护非常痛苦我在完成每个项目后都会跑一遍 clang_format.bash这个习惯帮我少掉了至少十次「编译不过但看不出为什么」的麻烦。6.3 用日志定位并发问题B 树并发调试是最难的一环。我最后的习惯是给每个 latch 操作打带线程号的日志。日志会很多但 grep 出特定页面 id 就能还原出一条完整的等待链。只要能看到「线程 2 持有 page 5等待 page 7线程 3 持有 page 7等待 page 5」这样两行死锁原因基本就明确了。从那以后我每次调并发问题都强制自己先把日志开关打开再动手改代码——这个顺序帮我避免了很多「先怀疑逻辑、其实是锁没释放」的无用功。这样一个项目完整跑下来你对数据库系统的理解会比只看教材深得多。希望这份实现和这些踩坑记录能帮到你——如果你也在刷 15445 或者想补数据库内核的实战经验这份源码值得仔细拆一遍。本文还有配套的精品资源点击获取