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

简介：本资源是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++给了我们这样的控制力，虽然开发难度大，但能让我们真正触及系统编程的细节。我们使用了C++17标准，利用智能指针管理部分内存生命周期，减少低级错误。

为什么是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次被访问的历史，能更好地区分偶然访问和频繁访问。我们实现了K=2，效果比朴素LRU在测试中提升了约15%。
脏页回写：被修改过的页称为“脏页”。我们不能等到缓冲区满了才写回磁盘，那样会阻塞后续操作。我们实现了一个后台刷新线程，定期扫描缓冲区，将“脏”且“非活跃”的页异步写回磁盘。这里的关键是协调好后台刷脏和前台线程的页面访问，避免数据不一致。
固定页（Pinning）：当一个线程正在读取或修改某个页面时，这个页面绝不能被置换出去。我们为每个页帧引入了一个“pin计数”。线程访问前pin++，访问后unpin--。只有pin count == 0的页才能成为置换候选。忘记unpin会导致内存泄漏（页面常驻），而unpin过早则可能引发访问非法内存。这是我们调试最久的问题之一。

// 简化的缓冲区获取页面接口示例 Frame* BufferPool::FetchPage(page_id_t page_id) { std::lock_guard<std::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 基于锁的并发控制实现

我们的事务管理器为每个事务分配一个唯一递增的ID（txn_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的过程，就像亲手搭建了一座微型的数字城市。你既是规划师（架构设计），也是建筑工人（编码实现），还是质检员（测试调试）。当你看到自己写的系统最终能流畅地处理复杂的查询和事务时，那种成就感是无与伦比的。这个项目带给我们的，远比一门课程、一次考试要多得多——它是一种构建复杂系统的思维方式和工程能力。如果你也有兴趣挑战自己，不妨就从设计一个简单的存储引擎开始吧。

本文还有配套的精品资源，点击获取