从零构建数据库内核：学生团队实战解析存储引擎与并发控制

简介本资源是2024年全国大学生计算机系统能力大赛数据库管理系统赛道一等奖获奖作品“RMDB-2024”面向高校计算机专业本科生、数据库系统课程学习者及系统级开发初学者聚焦关系型数据库核心机制的工程化实现涵盖存储管理、查询解析、事务处理与优化器设计等关键问题。压缩包共377个文件主体为110个C/C头文件.h与102个C源文件.cc辅以30个Python脚本测试/构建辅助、30份Markdown文档含设计说明与使用指南、25个C测试用例如gmock/gtest相关及6个Bazel构建配置BUILD.bazel整体仅2.21MB轻量但结构完整体现工业级项目组织规范。已有455人学习下载读者可直接获取一套通过权威赛事验证的、具备ACID保障与SQL基础支持的轻量级RDBMS完整源码包含可编译运行的主干分支master、多层级测试框架、构建配置及技术文档是理解数据库内核原理与动手实践系统编程的优质参考样本。1. 从零到一一个学生团队如何构建自己的数据库内核去年这个时候我和几个同学还在为数据库原理课的课程设计发愁面对一堆复杂的理论总感觉纸上谈兵。直到我们决定参加全国大学生计算机系统能力大赛的数据库管理系统赛道并最终捧回了一等奖这段经历才让我真正理解了“系统能力”这四个字的分量。我们做的项目叫RMDB-2024一个从零开始实现的、具备基本功能的数据库管理系统。今天我想抛开那些华丽的获奖词以一个亲历者的身份复盘一下我们是如何从一行代码都没有到构建出一个能跑通SQL、管理事务、处理并发请求的数据库内核的。这个过程充满了挑战也踩了无数的坑但每一步都无比扎实。如果你也对数据库底层实现感兴趣或者正打算参与类似的系统类竞赛希望这篇复盘能给你一些实实在在的参考。很多人觉得数据库是个黑盒会用SQL就行了。但当你真正去实现它你会发现每一个简单的SELECT * FROM users背后都是一系列精妙设计的子系统在协同工作从接收SQL字符串的解析器到将操作转化为执行计划的优化器再到与磁盘打交道的存储引擎最后是保证数据一致性的事务管理器。RMDB-2024就是我们对这个黑盒的一次系统性拆解与重建。这不是一个玩具我们实现了多粒度锁协议MVCC的简化版来处理并发用B树作为索引的核心数据结构并设计了一个简单的基于WAL预写式日志的恢复机制。接下来我会分几个核心部分详细聊聊我们的设计思路、技术选型的理由以及那些在深夜调试中才恍然大悟的“坑点”。2. 架构蓝图我们为什么选择这样的分层设计做系统最怕一开始架构就歪了后面修修补补无比痛苦。在动手写第一行代码前我们花了将近两周时间反复讨论和画图确定了RMDB-2024的核心架构。我们的目标是清晰、可扩展、便于分工。最终我们采用了经典的四层架构但每一层我们都赋予了符合我们能力与竞赛要求的具体内涵。2.1 核心四层与数据流整个系统从上到下分为SQL接口层、查询处理层、存储引擎层和磁盘管理层。数据流和命令流是双向的。SQL接口层这是门面。它负责接收客户端我们实现了一个简单的命令行工具发来的SQL字符串也负责将最终的结果集格式化成表格输出。这一层很薄主要工作是字符串的初步处理和会话状态的管理。查询处理层这是大脑。它包含了解析器Parser、优化器Optimizer和执行器Executor。解析器将SQL字符串转换成一颗抽象语法树AST。优化器在我们的初版中比较简单主要是规则优化对这棵树进行重写选择最优的索引和连接顺序生成一个物理执行计划。执行器则像个工头按照执行计划调用下层存储引擎的接口一步步获取数据、进行计算如过滤、聚合、连接并向上层返回结果。存储引擎层这是心脏。这是最复杂、代码量最大的一层。它直接管理数据在内存和磁盘上的形态。核心模块包括记录管理器Record Manager负责单条记录的存储格式定长/变长、在页面内的摆放以及记录的增删改查。索引管理器Index Manager我们实现了B树索引用于加速基于等值查询和范围查询的数据定位。缓冲区管理器Buffer Pool Manager这是性能的关键。它管理着一块固定大小的内存区域缓冲区通过特定的页面置换算法我们实现了LRU的变种来缓存磁盘数据页最大限度减少昂贵的磁盘I/O。锁管理器Lock Manager与事务管理器Transaction Manager二者紧密配合实现并发控制。锁管理器负责分配和协调行级锁、表级锁事务管理器负责事务的开启、提交、回滚并管理事务ID和快照。磁盘管理层这是基石。它提供最基础的磁盘空间抽象将物理磁盘文件划分成固定大小的“页”Page我们设为4KB或8KB并提供“读取第N页到内存”和“将内存中的第N页写回磁盘”的原子操作。所有上层模块都基于“页”这个单位进行操作。提示在项目初期明确每一层的接口API至关重要。我们使用C为每一层定义了清晰的抽象类或头文件。例如存储引擎层给查询处理层提供GetRecord()、InsertRecord()等接口而不暴露底层是B树还是哈希索引。这保证了模块间的低耦合方便后期替换算法或进行单元测试。2.2 技术选型的权衡C、B树与两阶段锁为什么用C这是讨论最久的问题。Python/Go写起来快但我们对性能有极致要求尤其是缓冲区管理和索引操作需要精细的内存控制和指针操作。C给了我们这样的控制力虽然开发难度大但能让我们真正触及系统编程的细节。我们使用了C17标准利用智能指针管理部分内存生命周期减少低级错误。为什么是B树而不是哈希索引哈希索引对于等值查询是O(1)但它无法高效支持范围查询如WHERE age 20而这是数据库非常常见的操作。B树所有数据都存储在叶子节点且叶子节点通过指针相连范围查询效率极高。考虑到竞赛场景的查询多样性B树是更稳妥和通用的选择。实现一个工业强度的B树非常复杂我们做了简化如节点分裂/合并时采用简单的算法但核心的搜索、插入、删除流程都完整实现了。并发控制为什么用锁而不是MVCC完整的MVCC多版本并发控制实现复杂度极高涉及版本链、垃圾回收等。在有限时间内我们选择实现了基于锁的并发控制并扩展为两阶段锁协议2PL以保证可串行化。事务在读数据前加读锁写数据前加写锁并且所有锁的释放都等到事务结束提交或回滚。为了减少死锁我们实现了简单的超时检测和回滚机制。虽然性能上不如MVCC但保证了数据的正确性这对于竞赛评测是首要的。3. 存储引擎深潜缓冲区、B树与记录格式的魔鬼细节存储引擎是数据库的性能基石这里面的每一个设计决策都直接影响着系统的吞吐和稳定性。我们踩的坑80%集中在这一层。3.1 缓冲区管理不只是缓存那么简单缓冲区管理器Buffer Pool的目标很简单让热数据留在内存。但实现起来处处是细节。我们分配了一块连续的内存比如1GB将其划分为多个与磁盘页大小相同的“帧”Frame。每个帧对应一个磁盘页并通过一个“页表”来管理映射关系。核心挑战与解决方案页面置换算法我们实现了LRU-K算法而不是简单的LRU。传统的LRU最近最少使用容易被一次性的全表扫描“污染”把真正的热数据挤出去。LRU-K记录页面最近K次被访问的历史能更好地区分偶然访问和频繁访问。我们实现了K2效果比朴素LRU在测试中提升了约15%。脏页回写被修改过的页称为“脏页”。我们不能等到缓冲区满了才写回磁盘那样会阻塞后续操作。我们实现了一个后台刷新线程定期扫描缓冲区将“脏”且“非活跃”的页异步写回磁盘。这里的关键是协调好后台刷脏和前台线程的页面访问避免数据不一致。固定页Pinning当一个线程正在读取或修改某个页面时这个页面绝不能被置换出去。我们为每个页帧引入了一个“pin计数”。线程访问前pin访问后unpin--。只有pin count 0的页才能成为置换候选。忘记unpin会导致内存泄漏页面常驻而unpin过早则可能引发访问非法内存。这是我们调试最久的问题之一。// 简化的缓冲区获取页面接口示例 Frame* BufferPool::FetchPage(page_id_t page_id) { std::lock_guardstd::mutex guard(latch_); // 1. 检查是否已在缓冲池中 auto it page_table_.find(page_id); if (it ! page_table_.end()) { frame_id_t frame_id it-second; Frame* frame frames_[frame_id]; frame-pin_count_; // 固定住 UpdateLRUKHistory(frame_id); // 更新访问历史 return frame; } // 2. 不在缓冲池需要置换 frame_id_t victim_frame_id FindVictim(); // 使用LRU-K选择牺牲者 Frame* victim_frame frames_[victim_frame_id]; // 3. 如果牺牲者是脏页必须写回磁盘 if (victim_frame-is_dirty_) { disk_manager_-WritePage(victim_frame-page_id_, victim_frame-data_); } // 4. 从磁盘读取新页面到牺牲者帧 disk_manager_-ReadPage(page_id, victim_frame-data_); // 5. 更新页表重置帧元数据并固定 page_table_.erase(victim_frame-page_id_); victim_frame-page_id_ page_id; victim_frame-is_dirty_ false; victim_frame-pin_count_ 1; // 新页面pin计数为1 page_table_[page_id] victim_frame_id; return victim_frame; }3.2 B树实现平衡、分裂与并发访问实现B树是一次深刻的数据结构教育。我们参考了《数据库系统概念》中的伪代码但纸上得来终觉浅。节点结构设计我们设计了内部节点和叶子节点。内部节点存储键值和指向子节点的页ID。叶子节点存储键值对键和指向实际记录位置的RID以及指向下一个叶子节点的指针用于范围扫描。每个节点的大小恰好填满一个磁盘页如4KB这就决定了每个节点能存储多少对键值。这是一个关键的计算(PAGE_SIZE - 元数据大小) / (KEY_SIZE sizeof(page_id_t))。插入与分裂的坑插入一个新键值对时如果叶子节点已满需要分裂。分裂后中间键需要“提升”到父节点。这个过程可能递归向上直到根节点。最棘手的情况是根节点分裂这时树的高度会增加。我们一开始没有处理好根节点分裂后新根节点的创建和持久化导致后续查询时找不到数据。我们的教训是任何修改树结构的操作插入、删除都必须先想清楚所有可能的路径并在内存中完成完整的结构变更后再通过事务确保所有相关页面子节点、父节点、新根节点的修改原子性地持久化到磁盘。并发控制多个事务同时查询和修改B树怎么办我们采用了蟹行协议Crabbing Protocol的简化版。搜索时从上到下获取子节点的读锁但一旦确定路径就释放父节点的锁。插入/删除时则需要更保守的加锁策略有时甚至需要在整个路径上持有写锁以防止“幻读”在树结构变化时发生。实现正确的B树并发是高级话题我们做了大量简化例如在修改树结构时使用一个全局的树锁牺牲了一些并发度但保证了正确性。3.3 记录格式定长与变长的抉择如何把一条(id INT, name VARCHAR(255), salary FLOAT)这样的记录塞进页面里我们支持了定长和变长记录。定长记录最简单。每个字段长度固定如INT 4字节FLOAT 8字节。一条记录的总长度固定可以直接通过槽位号 * 记录大小计算出在页面内的偏移量。管理简单访问速度快但浪费空间VARCHAR(255)即使只存‘A’也占255字节。变长记录更实用但复杂。我们采用了“槽目录Slot Directory”的方案。在页面末尾维护一个槽数组每个槽存储对应记录的起始偏移量和长度。记录本身从页面头部开始向前生长。删除记录时只需将对应槽标记为空并可能触发页面内记录的重整以压缩空间。这里的一个关键优化是对于频繁更新的表可以定期进行页面碎片整理但重整操作需要谨慎加锁避免阻塞读写。4. 查询处理从SQL字符串到结果集这一层是将用户意图转化为机器指令的翻译官。我们并没有实现一个完整的优化器而是聚焦于让基础的查询能正确、高效地执行。4.1 解析与验证自己动手写Parser我们没有使用yacc/lex或ANTLR而是手写了一个递归下降的SQL解析器。这听起来很硬核但对于竞赛限定的一部分SQL子集SELECT, INSERT, UPDATE, DELETE, CREATE TABLE是完全可行的。解析器将SQL字符串转换成我们自定义的抽象语法树AST节点如SelectStatement、InsertStatement等。关键步骤词法分析Tokenizer将字符串拆分成一个个词元Token如关键字SELECT、标识符table_name、操作符、常量‘hello’。语法分析Parser根据预定义的语法规则将词元序列组合成AST。例如SELECT id, name FROM users WHERE age 18会被解析成一个SelectStatement节点其内部包含columns列表、from表名、where条件表达式子树。语义检查检查AST的合理性。表名是否存在列名是否属于该表WHERE条件中的数据类型是否匹配这部分需要访问系统目录我们称为Catalog它记录了所有表、列、索引的元数据。注意手写Parser的调试非常耗时。一个括号不匹配或者关键字优先级理解错误就会导致解析失败。我们花了大量时间编写测试用例覆盖各种边界情况比如嵌套的WHERE条件、带别名的多表连接等。使用现成的解析器生成工具会更高效但手写让我们对SQL语法有了肌肉记忆般的理解。4.2 执行计划生成与执行对于优化器我们只实现了最基本的规则优化选择下推尽早执行WHERE条件中的过滤减少后续操作如连接需要处理的数据量。投影下推只取出查询中需要的列减少中间结果的数据体积。简单连接顺序选择基于表的大小统计信息决定连接顺序小表驱动大表。执行器是真正的实干家。它接收一个物理执行计划树例如Projection (id, name) - Filter (age 18) - SeqScan (users)然后自底向上地执行。SeqScan算子会调用存储引擎的接口遍历users表的所有记录。Filter算子对每一条记录检查age 18的条件将符合条件的传递给上层的Projection算子。Projection算子最后只提取出id和name两列形成最终的结果集。算子的实现我们实现了最基础的几个算子顺序扫描SeqScan、索引扫描IndexScan利用B树、嵌套循环连接NestedLoopJoin、哈希聚合HashAgg等。每个算子都实现一个Next()方法每次调用返回下一条结果或一个批次的结果这是一种经典的火山模型Volcano Model实现。它的优点是接口统一、内存占用可控一次处理一条缺点是函数调用开销大。在性能瓶颈分析中我们发现大量时间花在了算子间的虚函数调用上后期我们尝试了对某些热点路径进行批处理优化。5. 事务与并发在正确性和性能之间走钢丝数据库的核心价值之一就是保证并发操作下的数据正确性。这是我们投入精力最多也最考验设计能力的部分。5.1 基于锁的并发控制实现我们的事务管理器为每个事务分配一个唯一递增的IDtxn_id。锁管理器维护着一个全局的锁表记录每个资源我们细粒度到行级用(table_id, RID)标识被哪些事务以何种模式共享锁S/排他锁X持有。两阶段锁2PL的严格执行这意味着事务分为两个阶段。第一阶段是“生长阶段”事务可以不断申请新锁但不能释放任何锁。第二阶段是“收缩阶段”事务开始释放锁且不能再申请新锁。我们通过锁管理器的接口严格保证了这一点。事务提交或回滚时才一次性释放其持有的所有锁这自然满足了2PL。死锁处理加锁顺序不当就会引发死锁。我们实现了两种策略超时检测每个锁请求设置一个等待超时时间如2秒。如果超时仍未获得锁事务自动回滚。实现简单但可能误杀长事务。等待图检测定期或当锁等待超时时构建一个“等待图”节点是事务边表示“事务A等待事务B释放锁”。如果图中存在环则说明发生死锁。我们实现了简单的DFS检测环并选择回滚环中txn_id最小最年轻的事务来打破死锁。这更公平但实现更复杂。5.2 日志与恢复应对系统崩溃如果系统在事务中途崩溃如何保证数据不丢失、不混乱我们实现了简单的预写式日志Write-Ahead Logging, WAL机制。核心原则任何对数据页的修改在持久化到磁盘之前必须先将其对应的日志记录持久化到日志文件中。日志记录内容每条日志记录包含日志序列号LSN、事务ID、日志类型如UPDATE、修改的前像旧值和后像新值以及上一日志的LSN用于将同一事务的日志串起来。恢复过程分析阶段扫描日志确定崩溃时哪些事务是活跃的已开始未提交以及哪些脏页可能尚未写回磁盘。重做阶段Redo从最近一次检查点开始正向扫描日志对所有日志记录包括已提交和未提交事务重做一遍操作。这确保了所有已提交事务的修改肯定被持久化。因为WAL保证了日志先写所以即使数据页丢失也能用日志重做出来。撤销阶段Undo反向扫描日志对所有崩溃时仍活跃的事务的日志记录撤销其操作用前像替换后像。这消除了未提交事务对数据库的影响。我们实现了一个检查点Checkpoint机制来加速恢复。定期地系统会停止接受新事务等待所有当前事务完成并将所有脏页和日志记录刷盘然后记录一个检查点日志。恢复时只需从这个检查点开始扫描日志而不用从头开始。提示日志管理是性能的另一个关键点。频繁同步日志到磁盘fsync会极大影响吞吐。我们采用了组提交Group Commit策略将一段时间内多个事务的日志缓存在内存中然后一次性刷盘显著提高了并发写事务的性能。6. 测试、调试与性能调优通往稳定的漫漫长路系统写完了能跑通简单SQL但这离“稳定可用”还差得远。我们建立了多层次的测试体系。单元测试使用Google Test框架对每一个底层模块进行测试。例如针对B树我们编写了测试随机插入10万条数据然后顺序读取、删除一半再插入等场景。针对缓冲区测试页面置换算法是否正确、脏页回写是否正常。集成测试模拟客户端发送SQL序列测试多个模块协同工作。我们编写了测试用例模拟转账业务多个UPDATE操作在一个事务内验证其原子性。压力测试与竞品对比我们使用了简单的TPC-C基准测试改编版模拟多个终端并发执行新订单、支付、查询等操作。我们用同样的测试脚本跑我们的RMDB和SQLite配置为禁用内存模式强制刷盘。结果当然比不过SQLite但在关键指标上如每秒处理事务数TPS的差距从最初的百倍缩小到了十倍以内这个优化过程让我们受益匪浅。性能调优实战瓶颈定位我们使用gperftools进行CPU Profiling发现大量时间花在了内存拷贝和锁竞争上。优化内存拷贝在记录管理器中对于定长记录我们改为直接操作内存指针避免不必要的memcpy。减少锁粒度将缓冲区管理器的全局大锁拆分为多个分区锁每个分区管理一部分页帧显著减少了并发访问的冲突。I/O优化将多个小的日志记录打包成一个大的物理块写入磁盘提高了磁盘吞吐量。调试最痛苦的一次是遇到一个偶现的数据损坏错误。最终发现是在B树分裂过程中一个指针在异常路径下没有被正确初始化导致后续查询时访问了非法内存。我们通过给所有内存分配器如new和磁盘读取的数据页填充特定的模式如0xDEADBEEF并在每次访问前进行校验才最终定位到这个幽灵般的Bug。7. 参赛心得与给后来者的建议回顾整个项目从最初的架构图到最终能稳定运行测试集的系统近半年的开发周期里我们最大的收获不是一等奖而是对“系统”二字的敬畏。数据库管理系统是一个极其复杂的系统工程它要求你在不同维度功能、性能、正确性、鲁棒性之间做出艰难的权衡。给有意参加此类系统竞赛同学的建议团队与分工明确分工但核心模块如存储引擎、事务的接口设计必须全员参与评审。一个糟糕的接口设计会让后续开发举步维艰。代码管理尽早使用Git并建立清晰的分支策略如main,develop,feature/xxx。每天进行代码评审Code Review这是保证代码质量、传播知识的最佳方式。测试驱动不要写完一大坨代码再测试。为每个模块编写单元测试边写边测。集成测试用例就是你的功能清单。文档与注释设计文档、关键算法流程图、复杂的函数头注释这些在后期调试和团队交接时是无价之宝。我们要求每个非自解释的代码块都必须有注释。性能分析不要凭感觉优化。一定要用Profiling工具如perf,gprof,Valgrind找到真正的热点否则可能白费功夫。心态调整一定会遇到无法理解的Bug一定会推翻重来某些设计。这是学习过程的一部分。保持耐心善于利用调试工具GDB是我们的好朋友和日志输出。实现RMDB-2024的过程就像亲手搭建了一座微型的数字城市。你既是规划师架构设计也是建筑工人编码实现还是质检员测试调试。当你看到自己写的系统最终能流畅地处理复杂的查询和事务时那种成就感是无与伦比的。这个项目带给我们的远比一门课程、一次考试要多得多——它是一种构建复杂系统的思维方式和工程能力。如果你也有兴趣挑战自己不妨就从设计一个简单的存储引擎开始吧。本文还有配套的精品资源点击获取