简介本资源是2024年全国大学生计算机系统能力大赛数据库管理系统赛道一等奖作品“RMDB-2024”的完整工程源码包面向高校计算机专业本科生、系统软件学习者及数据库底层开发者聚焦关系型数据库核心功能实现与系统级性能优化实践。压缩包共377个文件涵盖110个C/C头文件.h、102个C实现文件.cc、25个.cpp源码、30个Python脚本用于测试/构建/工具、30个Markdown文档含设计说明与使用指南以及Bazel构建配置BUILD.bazel、词法/语法分析生成代码yacc.tab.c、lex.yy.c、Google Test/GMock单元测试用例等整体大小仅2.21MB结构紧凑、模块清晰。已有455人下载学习可直接复现高分赛题方案深入理解事务管理、查询解析、存储引擎与执行优化等关键模块的工程落地细节并参考其工业级构建体系与测试框架设计思路。1. 项目概述从零到一构建一个教学级关系型数据库内核去年带队参加全国大学生计算机系统能力大赛数据库管理系统赛道最终拿下一等奖的经历现在回想起来依然觉得收获巨大。我们团队的作品“RMDB-2024”是一个从Parser解析器到Storage存储引擎完全自研的、功能完备的关系型数据库管理系统。对于计算机专业尤其是系统软件方向的同学来说没有什么比亲手实现一个数据库内核更能深刻理解“数据是如何被组织、管理和操作的”这件事了。这个项目不仅是一场比赛作品更是一个绝佳的学习路径和工程实践范本。如果你正对数据库底层原理感到好奇或者想挑战一个综合性极强的系统编程项目亦或是为未来的系统能力大赛做准备那么跟随我们重构RMDB-2024的历程或许能给你带来不少启发。本文将抛开比赛的光环深入拆解我们是如何一步步设计并实现这个数据库的涵盖核心架构选型、关键模块的实现细节、过程中踩过的坑以及那些教科书上不会写的调试技巧。我们的目标是让你不仅能看懂更能基于这个思路动手搭建出自己的第一个数据库原型。2. 整体架构设计与核心思路拆解2.1 为什么选择“麻雀虽小五脏俱全”的架构在项目启动之初我们面临的首要抉择是做得多“深”做得多“广”。市面上有像SQLite这样轻量但功能完整的嵌入式数据库也有像MySQL、PostgreSQL这样庞大的通用数据库。作为教学和参赛项目我们决定采用一种折中但清晰的架构实现一个单机、磁盘持久化的关系型数据库支持标准的SQL DML数据操作语言和DDL数据定义语言核心子集并具备事务的ACID基本特性。这个选择基于几个核心考量教学与参赛的平衡大赛考察的是对数据库系统核心原理的理解与工程实现能力而非商业级的完备性。一个功能聚焦但深度足够的系统更能体现团队的技术把控力。技术栈的完整性从SQL解析、查询优化、执行引擎到存储管理、缓冲区管理、事务并发控制我们希望覆盖数据库课程中的主要知识点形成一个闭环的学习体验。可控的复杂度避免过早陷入分布式、高可用等高级主题的泥潭确保在有限时间内能交付一个稳定运行、逻辑正确的内核。我们的RMDB-2024最终确立了分层架构自上而下分为SQL前端层包括词法分析器Lexer、语法分析器Parser、语义分析器Semantic Analyzer和查询优化器Optimizer。负责将用户输入的SQL字符串转化为可执行的物理计划。查询执行层即执行引擎Execution Engine负责解释并执行物理计划调用下层接口进行数据的读写。我们实现了火山模型Volcano Model的迭代器接口这是理解查询流水线的关键。存储管理层这是数据库的“仓库”包括记录管理Record Manager、索引管理Index Manager我们实现了B树、缓冲区管理Buffer Pool Manager和磁盘管理Disk Manager。它向上提供以页Page为单位的抽象向下与操作系统文件交互。事务管理层负责保障ACID特性我们实现了基于锁的并发控制Lock Manager和Write-Ahead LoggingWAL的恢复机制。注意在架构设计初期切忌贪大求全。明确核心边界例如我们暂不支持存储过程、触发器、视图等高级功能而是确保SELECT、INSERT、UPDATE、DELETE、CREATE TABLE等基本操作的正确性和高效性。2.2 技术选型C作为系统编程语言的必然性实现数据库内核语言选型几乎是没有悬念的——C。原因如下零成本抽象数据库系统对性能极其敏感特别是存储引擎和查询执行路径。C允许我们在需要时进行底层内存操作和优化同时也能利用RAII等特性安全地管理资源如文件句柄、锁、内存缓冲区。对硬件和操作系统的直接控制我们需要直接调用系统API进行文件I/O如pread/pwrite管理内存映射控制数据对齐这些在C中都非常自然。丰富的生态系统虽然核心逻辑完全自研但一些辅助工具如语法分析器生成工具Flex/Bison与C集成良好。同时C的标准模板库STL为我们在管理内部数据结构如哈希表、向量时提供了可靠的基础。我们团队当时也讨论过Rust其所有权模型在避免内存错误方面有先天优势。但考虑到大赛的学习资源、队员的熟悉度以及调试工具的成熟度最终选择了更经典的C17标准。一个重要的心得是在系统编程中对语言特性的克制使用有时比炫技更重要。我们明确禁止在核心路径上使用异常采用错误码返回谨慎使用运行时类型信息RTTI并制定了严格的内存管理规范。3. 核心模块实现深度解析3.1 存储引擎一切从“页”开始数据库的所有数据最终都躺在磁盘上。如何高效地组织这些数据是存储引擎的首要任务。我们采用了业界通行的页式存储Page-Oriented Storage模型。3.1.1 磁盘管理器与页的设计DiskManager是唯一直接与磁盘文件打交道的模块。它的接口非常简单ReadPage(page_id_t page_id, char* page_data)和WritePage(page_id_t page_id, const char* page_data)。每个页有一个唯一的ID通常对应文件中的偏移量例如page_id * PAGE_SIZE。页Page是我们内存和磁盘之间交换数据的基本单位。我们将其大小定为4KB或8KB与大多数操作系统文件系统块大小对齐以减少I/O开销。一个Page对象在内存中不仅包含数据char data[PAGE_SIZE]还包含元信息class Page { page_id_t page_id_; // 该页的全局唯一标识 bool is_dirty_; // 自上次读入后是否被修改 int pin_count_; // 被引用计数为0时方可被换出 char data_[PAGE_SIZE]; // 实际数据 // ... 锁等其它元数据 };3.1.2 缓冲区池内存中的“缓存区”如果每次读写数据都直接访问磁盘性能将是灾难性的。BufferPoolManager(BPM) 负责管理一块固定的内存区域如16MB作为磁盘页的缓存。它维护一个页帧Frame数组和一个页表从page_id到frame_id的映射。当执行引擎请求一个页时BPM的工作流程如下检查页表若该页已在缓冲池中缓存命中则增加其pin_count返回该页指针。若未命中则需要找到一个空闲帧pin_count为0的帧。如果没有则必须使用替换策略我们实现了LRU-K淘汰一个脏页若为脏页则需先写回磁盘然后清空该帧。调用DiskManager::ReadPage将磁盘数据读入该帧更新页表设置pin_count1返回指针。实操心得缓冲区池的并发控制是调试难点。多个线程可能同时请求同一页或请求不同页但触发同一帧的替换。我们为每个Frame配备了细粒度的锁并在BPM内部使用锁表来避免死锁。一个常见的坑是忘记在UnpinPage时减少pin_count导致页永远无法被换出最终内存泄漏。3.1.3 记录管理页内的数据组织一个页内可能存放多条记录元组。RecordManager负责管理页内的空间。我们采用槽位目录Slot Directory的方式页的末尾维护一个槽位数组每个槽位存储对应记录在页内的起始偏移量和长度。删除记录时只需将对应槽位标记为“已删除”如偏移量设为-1并可能将该空间加入空闲链表供后续插入复用。这种设计支持变长记录并且通过槽位号RID: Record ID通常由page_id slot_num组成可以快速定位记录。3.2 索引管理B树的实现艺术为了加速基于键的查询如WHERE id 5我们实现了最经典的B树索引。B树的所有数据都存储在叶子节点且叶子节点通过指针串联非常适合范围查询。3.2.1 节点结构与操作我们将B树节点也存储为“页”这样可以利用已有的缓冲区池。一个节点页的内容包括节点类型内部节点/叶子节点当前键值对数量键的数组对于内部节点键是分割值对于叶子节点键是索引键值的数组对于内部节点值是子节点的页ID对于叶子节点值是记录RID的列表兄弟节点指针仅叶子节点有实现Insert和Delete操作时必须严格遵循B树的算法处理节点的分裂与合并。这是整个项目中最需要细心和严谨的部分。3.2.2 并发控制与锁耦合Lock CouplingB树索引本身会被多个事务并发访问。简单的做法是在整棵树上加一把大锁但这会严重限制并发性。我们实现了更精细的锁耦合协议从根节点开始搜索时对当前节点加读锁或写锁如果是插入/删除。在确定要进入某个子节点前对该子节点加锁。在安全地获得子节点锁之后才释放父节点的锁。这种“手递手”的方式保证了遍历路径的一致性同时允许其他线程访问不相关的子树。调试B树的并发操作极具挑战性。我们使用了大量的断言assert和一套完整的单元测试模拟各种并发插入、删除、搜索的场景才逐步稳定下来。3.3 查询执行火山模型的迭代器查询执行引擎负责将优化器生成的物理计划树“执行”出来。我们采用了经典的火山模型又称迭代器模型。在这个模型中每个物理算子如SeqScan,IndexScan,NestedLoopJoin,HashJoin,Filter,Projection都实现一个统一的迭代器接口class Executor { public: virtual void Init() 0; // 初始化算子状态 virtual bool Next(Tuple *tuple) 0; // 获取下一条结果返回false表示结束 virtual const Schema *GetOutputSchema() const 0; };3.3.1 执行流程示例对于查询SELECT name FROM student WHERE age 18;优化器可能生成如下计划树Projection(name) | Filter(age 18) | SeqScan(student)执行过程是自底向上、惰性拉取的执行引擎从根节点Projection调用Next()。Projection调用其子节点Filter的Next()。Filter调用其子节点SeqScan的Next()。SeqScan从student表的堆文件中读取一条元组返回给Filter。Filter检查age 18条件如果满足则将元组返回给Projection如果不满足则回到第3步向SeqScan要下一条元组。Projection从收到的元组中提取name字段构造成新的元组返回给执行引擎。这种模型的优点是内存占用小一次处理一条元组算子之间解耦清晰。缺点是函数调用开销大现代数据库更多采用向量化或编译执行来优化。3.3.2 连接操作的实现我们实现了两种基础的连接算法嵌套循环连接Nested Loop Join实现简单适用于任何连接条件但当内表很大时性能极差。我们对其进行了优化如果内表在连接键上有索引则转化为索引嵌套循环连接性能大幅提升。哈希连接Hash Join适用于等值连接。分为构建Build阶段和探测Probe阶段。构建阶段扫描内表根据连接键构建内存哈希表探测阶段扫描外表用连接键去哈希表中查找匹配的内表元组。这里的关键是哈希表的设计和当哈希表太大无法放入内存时的处理我们实现了Grace Hash Join的基本思想进行分区落盘。3.4 事务与并发控制保证正确性的基石事务管理器是数据库的“交警”确保并发操作下数据的一致性。我们实现了基于两阶段锁2PL的并发控制和WAL的恢复机制。3.4.1 锁管理器LockManager维护一个全局的锁表。锁的粒度我们支持到元组级这比页级锁并发度更高比表级锁更精细。锁的基本类型有共享锁S-Lock用于读和排他锁X-Lock用于写。我们遵循标准的锁兼容性矩阵。当一个事务请求锁时如果请求的锁与当前该元组上已持有的所有锁兼容则立即授予。如果不兼容则该事务进入该元组的等待队列。锁管理器需要检测并处理死锁。我们实现了等待图Wait-for Graph检测算法定期或当等待超时时运行如果发现环则选择一个“代价最小”的事务如修改数据最少的事务进行回滚Abort以打破死锁。3.4.2 日志管理与恢复WAL为了保证持久性Durability和原子性Atomicity我们实现了预写式日志。任何对数据页的修改都必须先写入日志再写入数据页本身。日志记录Log Record包含唯一递增的日志序列号LSN事务ID日志类型BEGIN, COMMIT, ABORT, UPDATE等修改前的数据镜像UNDO修改后的数据镜像REDO恢复过程分为两个阶段分析阶段Analysis重放日志确定故障发生时哪些事务是活跃的未提交或未完成回滚。重做阶段Redo从最早的脏页更新对应的日志开始重做所有已提交或未提交事务的REDO操作确保所有已提交的修改都持久化到磁盘。撤销阶段Undo反向扫描日志对故障时仍活跃的事务执行UNDO操作回滚其所有修改。重要提示WAL的实现必须保证日志写入的原子性。我们采用了“日志缓冲区强制刷盘”的策略。当日志缓冲区满或事务提交时必须调用fsync确保日志落盘之后才能向客户端返回提交成功。这是保证“提交即持久”的关键。4. 开发、测试与调试实战记录4.1 构建系统与单元测试框架我们使用CMake管理项目构建。代码结构清晰模块间通过抽象的接口依赖便于独立编译和测试。对于测试我们搭建了一个混合框架Google Test用于单元测试和模块集成测试。例如为BufferPoolManager编写测试用例模拟各种页面置换场景为B树测试插入、删除、搜索的正确性。自定义SQL测试脚本我们编写了一个简单的测试运行器可以读取包含SQL语句和预期输出的.test文件自动执行并比对结果。这是进行端到端功能测试的主要方式。4.2 调试技巧与性能剖析数据库系统的调试往往非常棘手问题可能出现在并发、磁盘I/O、内存管理等任何层面。4.2.1 核心调试手段日志输出我们在关键路径如加锁/解锁、页的pin/unpin、事务开始/提交添加了详细的日志并支持动态调整日志级别。当出现死锁或数据错误时日志文件是第一手资料。断言Assert在代码中大量使用断言检查不变量Invariant。例如在B树操作后断言节点键值有序、子指针有效在缓冲区池操作中断言pin_count非负。这能在第一时间捕获逻辑错误。Valgrind与AddressSanitizer定期使用内存检查工具运行测试套件排查内存泄漏、越界访问、使用未初始化内存等问题。系统编程中内存安全是头等大事。GDB与核心转储对于难以复现的并发bug我们会在代码中插入条件断点或者让程序在检测到特定状态如断言失败时自动生成核心转储文件然后用GDB进行事后分析。4.2.2 性能瓶颈定位在功能稳定后我们使用perf和火焰图FlameGraph进行性能剖析。一个典型的发现是在初期版本中字符串比较用于WHERE条件判断和连接是热点。我们通过将字符串字段哈希为整数进行快速比较并在内存中缓存常用字符串的哈希值获得了显著的性能提升。4.3 我们遇到的那些“坑”与解决方案坑缓冲区池的“幽灵页”现象偶尔在读取某个page_id的数据时内容错乱像是其他页的数据。排查经过大量日志分析发现是在BufferPoolManager::FetchPage中当需要淘汰一个脏页时我们写回了磁盘但没有重置该帧对应的page_id_映射。导致该帧被分配给新页后残留的旧映射关系使得其他线程误以为它还是旧页。解决在淘汰帧并重新使用前严格清理帧的所有元数据包括将其从页表中移除或覆盖。坑B树删除导致的下溢合并顺序错误现象进行一系列插入和删除后B树查询返回错误结果或崩溃。排查教科书上的删除算法描述得很清晰但实现时在兄弟节点间重新分配键或合并节点后忘记更新父节点中对应的关键字。这导致父节点的分割键失效后续搜索走入错误的分支。解决为B树的删除操作编写了独立的、详尽的测试用例模拟所有可能的情况删除后节点仍半满、需从左兄弟借、需从右兄弟借、需与左兄弟合并、需与右兄弟合并。并通过图形化工具将树的结构打印出来进行肉眼比对。坑事务提交后的“脏读”现象事务A提交后事务B有时仍然读不到A的修改。排查我们的事务隔离级别设计为可重复读Repeatable Read通过多版本并发控制MVCC的快照来实现。问题出在事务ID分配和快照生成的时机上。事务B在开始时就获取了“活跃事务列表”作为快照但事务A提交时其事务ID并未及时从全局活跃列表中移除移除操作发生在提交日志写盘之后但可能在返回客户端之前。解决将“从事务管理器获取快照”和“分配新事务ID”这两个操作置于同一个互斥锁的保护下确保事务状态的全局视图是一致的。5. 项目总结与延伸思考实现RMDB-2024的过程是一次对计算机系统知识的深度整合与实战。它强迫你去思考数据在磁盘和内存中的布局去设计多线程访问共享资源时的同步协议去权衡不同算法在时间与空间上的取舍。比赛获奖固然欣喜但更大的收获在于这个过程本身我们真正理解了CREATE TABLE背后发生了什么SELECT ... WHERE ...是如何被一步步优化和执行的以及数据库是如何保证在断电后数据不丢的。如果你也想尝试类似的挑战我的建议是分而治之逐个击破不要试图一下子看懂所有模块。从磁盘管理器和缓冲区池开始实现一个能存、能取、能缓存的简单键值存储。然后加上记录管理支持变长数据。接着实现B树索引。再往上构建SQL解析和执行引擎。最后攻克事务和并发。每一步都确保充分测试。测试驱动回归验证为每个模块编写全面的单元测试。特别是对于并发模块要编写压力测试模拟高并发场景。任何修改后都要运行完整的测试套件防止回归。善用工具深入底层学会使用调试器、内存检查器、性能剖析器。不要害怕阅读汇编代码当优化到极致时很有用。理解fsync和fdatasync的区别理解内存对齐和缓存行。阅读经典参考开源除了教材多阅读经典的论文如Google的LevelDB、RocksDB相关论文以及数据库系统实现方面的经典文献。也可以有选择地阅读SQLite、PostgreSQL等开源项目的部分代码但要以理解思路为主切忌直接拷贝。数据库的世界博大精深RMDB-2024只是掀开了帷幕的一角。但它足以为你打下坚实的系统基础让你在面对更复杂的分布式数据库、NewSQL、OLAP引擎时能够从容地理解其核心思想。编程的乐趣莫过于此——用代码构建一个有序而高效的世界并亲眼见证它稳定运行。本文还有配套的精品资源点击获取
