尧图网页设计 
简介本资源是全国大学生计算机系统能力大赛数据库管理系统赛道的完整参赛项目面向系统能力培养导向的高校本科生与研究生聚焦关系型数据库内核开发实践。项目基于RMDB框架实现了一套支持TPC-C基准测试的轻量级RDBMS覆盖存储引擎、查询优化器、事务管理等核心模块可作为数据库原理课程设计、系统级编程实训及竞赛备赛的高质量参考方案。压缩包共442个文件2.43MB含121个C/C头文件h/hpp与146个源码文件cc/cpp/c、47个Python脚本用于测试与工具链、30个Markdown文档含设计说明与接口规范、11个CMake/Bazel构建配置文件以及PDF技术报告和CSV测试数据等目录结构体现典型DBMS分层架构。已有70人学习下载读者可直接复现编译环境、剖析关键算法实现如B树索引、基于代价的连接优化、运行TPC-C负载验证性能并参考配套文档理解从SQL解析到物理执行的全链路设计逻辑。1. 项目概述从零构建一个“能跑”的关系型数据库如果你是一名计算机专业的学生或者对数据库底层技术充满好奇那么“自己动手写一个数据库”这个想法大概率在你脑海里闪现过。它听起来既酷炫又遥不可及仿佛是系统软件领域的皇冠。全国大学生计算机系统能力大赛数据库管理系统赛道就是为有这样想法的同学准备的顶级舞台。这个项目正是我们团队为参赛而开发的一个完整的关系型数据库管理系统RDBMS。它不是玩具而是一个从存储引擎、查询优化器到事务管理内核功能齐全并且能通过标准工业级基准测试TPC-C验证的系统。简单来说我们的目标不是重复造一个MySQL或PostgreSQL而是在有限的时间和资源下深入理解一个现代数据库内核的骨架与灵魂。我们选择了基于RMDB这个教学/研究型框架进行深度开发。RMDB提供了一个不错的起点它定义了模块接口和基础架构但真正的“血肉”——如何高效地组织数据、如何聪明地执行查询、如何保证数据在并发下的正确性——都需要我们亲手填充。最终我们实现了一个支持标准SQL子集、具备ACID事务特性、并能承受TPC-C这种复杂OLTP负载考验的数据库系统。这个过程就像是在导师提供的汽车底盘上自己设计发动机、变速箱和控制系统最后让它真正跑起来甚至去赛道上测个速。接下来我将详细拆解我们是如何一步步完成这个挑战的。2. 核心架构设计与技术选型思路当我们决定基于RMDB框架开发时首先需要吃透它的架构并在此基础上做出我们的技术决策。RMDB采用了经典的分层架构这为我们清晰地划分了工作模块。2.1 为什么选择RMDB框架市面上教学用的数据库框架不止一个比如CMU的BusTub、Stanford的SimpleDB。我们选择RMDB主要基于几点考量。首先它的代码结构清晰模块耦合度相对较低每个核心组件如StorageManagerExecutorPlanner的接口定义明确这非常有利于团队分工。其次RMDB使用C编写这让我们能更贴近工业级数据库如MySQL、SQLite的实现语言对内存管理、性能优化有更直接的掌控感同时也避免了Java等语言GC带来的不确定性对性能测试的影响。最后RMDB的社区和配套资料在国内相对丰富遇到深层次问题时有更多可参考的解决方案。但RMDB只是一个骨架。它提供了磁盘I/O的抽象、缓冲池的基本管理、记录格式的定义以及查询执行的大致流程。而真正的难点在于缓冲池替换策略用什么算法数据在磁盘上用什么结构组织堆文件、B树查询优化器基于什么规则进行等价变换和代价估算事务管理器如何实现锁或多版本并发控制MVCC这些都需要我们做出独立的设计和实现。2.2 整体系统架构拆解我们的系统最终呈现为以下核心模块的协同工作存储管理层这是系统的基石。负责管理数据在磁盘上的持久化存储。我们实现了基于缓冲池Buffer Pool的磁盘数据缓存机制并在此基础上构建了两种主要的存储引擎结构用于顺序存储的堆文件Heap File和用于高效索引的B树。这一层直接决定了数据存取的效率。查询处理层这是系统的“大脑”。它接收SQL语句经过解析器Parser生成抽象语法树AST然后由查询优化器Optimizer进行重写、选择执行路径生成最优的物理执行计划最后由执行器Executor调用存储层的接口逐行处理数据。优化器是我们投入精力最多的模块之一。事务管理层这是系统的“安全卫士”。它确保数据库的ACID特性。我们实现了基于锁的并发控制协议两阶段锁2PL和Write-Ahead LoggingWAL日志机制来保证事务的原子性、一致性和隔离性。恢复管理器则基于WAL日志在系统崩溃后恢复数据一致性。TPC-C驱动与测试层这不是数据库内核的一部分但却是项目的“验收官”。我们实现了TPC-C基准测试的标准驱动程序模拟一个批发公司的业务负载新建订单、支付、订单状态查询等持续对数据库施加压力并最终收集衡量性能的指标tpmC每分钟完成的事务数。这个架构决定了我们的开发路线图先让存储引擎稳定读写再让执行器能跑通简单查询接着优化器提升复杂查询效率然后事务管理器保证并发正确性最后用TPC-C验证整体性能和稳定性。每一步都环环相扣。3. 存储引擎数据如何被高效地放置与查找存储引擎是数据库的“仓库管理员”它的设计直接决定了数据存取的性能。我们的核心工作是实现了缓冲池管理、堆文件组织和B树索引。3.1 缓冲池在内存与磁盘之间架起高速桥梁数据库的数据远大于内存容量因此需要一个智能的缓存系统。缓冲池就是一块固定的内存区域用于缓存从磁盘读出的数据页Page。我们的实现关键点在于页面置换算法当缓冲池满时需要淘汰一个旧页面。我们对比了LRU最近最少使用和Clock算法。LRU实现简单但对顺序扫描全表扫描不友好会污染缓存。我们最终实现了改进版的LRU-K算法它不只记录最近一次访问而是记录最近K次访问的历史能更好地区分“热点数据”和“一次性扫描数据”在TPC-C的混合负载下表现更稳定。钉住Pin与脏页Dirty Page执行器在读取或修改一个页面时必须“钉住”它防止被置换出去。修改后的页面标记为“脏”由后台线程或检查点机制定期刷回磁盘。这里的一个关键细节是我们严格管理了pin_count和dirty标志确保线程安全避免一个正在被事务修改的页面被意外淘汰。预取Prefetching对于顺序扫描操作我们实现了简单的顺序预取。当执行器请求第N页时缓冲池管理器会异步地将第N1, N2页也加载到缓冲池中有效减少了I/O等待。实操心得缓冲池的调试陷阱。初期我们曾遇到一个诡异的“数据消失”问题事务提交后再次查询数据有时会丢失。排查了很久最终发现是在某个错误处理分支中页面被修改后没有正确标记为dirty导致刷盘时漏掉了这个页面。教训是所有修改页面的操作必须在同一原子操作中递增pin_count和设置dirty标志并且要有完善的单元测试覆盖所有异常路径。3.2 堆文件与B树两种核心数据组织方式堆文件Heap File这是最简单的存储方式数据记录按插入顺序依次存放。我们使用一个“空闲空间映射”来快速找到有空间插入新记录的页面。堆文件的优势是插入极快O(1)但根据条件查找特定记录需要全表扫描O(n)。它适合数据仓库中追加式的批量加载或者作为没有索引的表的底层存储。B树索引这是数据库索引的绝对核心。我们实现了典型的B树结构支持等值查找、范围查找和有序遍历。叶子节点存储键值Key和记录IDRID内部节点存储导航键。实现难点包括分裂与合并当节点满时需分裂当节点元素过少时需与兄弟节点合并或重新分配。这些操作必须保证树的平衡并且是原子性的我们通过精心设计页面操作顺序和WAL日志来保证。并发控制B树的并发访问非常频繁。我们实现了Crabbing Protocol蟹行协议的变种。搜索时从根到叶子一路共享锁S锁仅在需要修改的叶子节点才升级为排他锁X锁插入/删除时从根向下在可能发生分裂/合并的路径节点上使用排他锁但范围控制得尽可能小以减少锁冲突。这比直接锁整棵树效率高得多。为什么选择B树而不是B树或哈希B树所有数据都在叶子节点且叶子节点链表连接这使得范围查询和全键值顺序遍历的效率极高非常适合数据库最常见的“WHERE ... BETWEEN ...”和“ORDER BY”场景。哈希索引虽然等值查询是O(1)但无法支持范围查询。B树的数据可能在任何节点遍历不如B树高效。因此B树在关系型数据库中成为了索引的默认选择。4. 查询优化器让SQL执行从“蛮干”到“巧干”如果没有优化器执行器可能会用最笨的方式执行查询。例如SELECT * FROM A, B WHERE A.id B.a_id AND A.name ‘foo‘可能会先对A做全表扫描找出所有name‘foo‘的记录然后对每一条记录再去B表做全表扫描找匹配的a_id。如果表很大这就是灾难。优化器的任务就是把这种“蛮干”计划变成“巧干”计划。4.1 优化器的核心工作流程我们的优化器遵循经典的Volcano/Cascades风格模型分为几个阶段语法分析与生成初始逻辑计划解析器将SQL变成语法树然后转换成初始的关系代数表达式树如Select, Project, Join, Scan。逻辑优化基于关系代数等价规则对表达式树进行重写目标是减少中间结果集的大小。我们实现了以下常见规则谓词下推尽早执行选择Select操作把过滤条件A.name ‘foo‘推到连接Join之前减少参与连接的数据量。投影下推尽早执行投影Project操作只取出后续计算需要的列减少数据在内存中的体积。连接重排序对于多表连接A JOIN B JOIN C连接顺序不同产生的中间结果大小天差地别。我们实现了基于动态规划的连接顺序优化算法估算每种连接顺序的代价选择代价最小的。物理优化与代价估算为逻辑计划中的每个操作符选择具体的物理实现算法并估算其代价。这是最核心也最困难的部分。代价模型我们建立了一个简单的代价模型Cost CPU_Cost I/O_Cost。I/O成本占主导我们主要计算需要读写的页面数。为此系统需要维护表的统计信息包括总行数、每列的不同值数量基数、最大值、最小值等。这些信息通过ANALYZE命令定期收集。选择率估算对于WHERE col value这样的条件优化器需要估算满足条件的行数占总行数的比例。我们假设数据均匀分布利用列基数来估算选择率 ≈ 1 / NDV(col)。对于范围查询则利用最大值最小值来估算。连接算法选择对于Join操作我们实现了三种物理算法优化器根据情况选择嵌套循环连接适用于小表驱动大表或者有索引可用的情况。哈希连接适用于内存能装下其中一张表或分区的情况它是等值连接效率最高的算法之一。我们实现了Grace Hash Join当表太大时进行分区落盘。排序合并连接当输入数据已经有序或者需要输出有序结果时很有优势。生成最终执行计划经过以上步骤得到一棵附带了具体算法和代价估算的物理执行计划树交给执行器去执行。4.2 一个优化实例分析假设查询SELECT * FROM orders, customer WHERE orders.c_id customer.id AND customer.credit ‘good‘。糟糕的计划全表扫描customer对每一行credit‘good‘的记录全表扫描orders找匹配的c_id。代价是|customer| |good_customer| * |orders|次页面I/O。优化后的计划谓词下推先对customer表执行credit‘good‘的选择操作得到一个小的结果集good_cust。连接重排序与算法选择现在连接good_cust和orders。因为good_cust很小优化器可能选择以它为构建表orders为探测表进行哈希连接。如果orders在c_id上有B树索引也可能选择索引嵌套循环连接即遍历good_cust每次用c_id去索引中快速查找orders记录。最终代价可能降低为扫描customer表的代价 构建good_cust哈希表的代价 扫描orders表一次的代价哈希连接或|good_cust|次索引查找的代价。注意事项统计信息的重要性与局限性。优化器的好坏极度依赖统计信息的准确性。如果统计信息过时例如customer表刚插入大量credit‘bad‘的记录但统计信息显示credit分布均匀优化器可能会严重误判选择率选出糟糕的计划。因此在TPC-C测试前我们必须对测试表执行ANALYZE。此外我们的简单代价模型无法考虑CPU缓存命中率、顺序I/O与随机I/O的差异等更复杂的硬件因素这是一个可以继续深化的方向。5. 事务管理与恢复保障数据的“金科玉律”数据库事务必须满足ACID特性我们通过锁管理器Lock Manager和预写日志WAL两大组件来实现。5.1 基于锁的并发控制我们实现了严格的**两阶段锁2PL**协议事务在释放任何一个锁之后就不能再申请任何新的锁。这保证了可串行化隔离级别。锁管理器维护一个全局的锁表记录每个资源我们以RID即记录ID为粒度上的锁信息。锁的升级与等待事务T1持有R1的共享锁(S锁)事务T2也想获得R1的排他锁(X锁)进行修改T2必须等待。锁管理器处理这种等待队列防止饿死。当T1释放锁后唤醒等待队列中的T2。死锁检测与处理我们采用周期性的死锁检测而非预防。维护一个“等待图”Wait-for Graph节点是事务边表示T1正在等待T2占用的资源。定期运行一个后台线程检测图中是否有环。一旦发现死锁选择一个“代价最小”的事务如修改数据最少的事务进行回滚Abort释放其所有锁从而打破死锁。锁粒度我们主要实现了记录级锁这对OLTP的TPC-C负载比较合适。也在表级提供了意向锁IS, IX用于在B树遍历时快速判断子树是否可能被上锁提高效率。5.2 预写日志与恢复为了保证原子性和持久性我们实现了Write-Ahead Logging。其核心原则是任何数据页面的修改必须在页面本身被写回磁盘之前先将其对应的日志记录持久化到磁盘上的日志文件中。日志格式每条日志记录包含唯一LSN日志序列号、事务ID、日志类型Update, Commit, Abort等、修改的前像Before-Image和后像After-Image。提交协议事务提交时并不立即将所有修改的脏页刷盘这很慢而是只需强制写入一条COMMIT日志记录到磁盘。只要这条日志落盘事务就算持久化提交了。脏页由后台的检查点Checkpoint线程异步刷回。恢复过程系统崩溃重启后恢复管理器启动扫描日志文件重做阶段Redo从最后一个检查点开始正向扫描日志对所有日志包括已提交和未提交事务根据后像重新执行一遍操作。这保证了已提交事务的修改不会丢失即使脏页没刷盘。撤销阶段Undo反向扫描日志对所有在崩溃时未提交的事务根据前像执行反向操作回滚所有修改。这保证了未提交事务的修改不会残留。我们实现了ARIES恢复算法的简化版支持逻辑Undo和检查点使得恢复过程更快、更健壮。踩坑实录日志序列号与页面LSN的同步。在实现WAL时我们曾遇到一个棘手的Bug系统恢复后某些已提交事务的修改丢失了。经过逐条日志分析发现是在写日志记录和更新数据页面pageLSN页面最后修改的日志号时顺序出了问题。正确的顺序必须是1) 在内存中组装好日志记录2) 将日志记录写入日志缓冲区3)更新内存中页面的pageLSN4) 修改页面内容。如果步骤3和4颠倒可能在页面修改后、pageLSN更新前发生崩溃导致恢复时误认为这个页面的修改已经持久化因为其pageLSN小于日志中的LSN从而跳过重做造成数据丢失。这个细节对保证恢复的正确性至关重要。6. TPC-C基准测试工业级的压力检验实现所有内核功能后我们需要一个公正的“考官”来检验系统的成色。TPC-C是事务处理性能委员会制定的经典OLTP基准测试模拟了一个批发公司的业务包含5种事务类型和9张表非常复杂且贴近真实场景。6.1 TPC-C负载特性与我们的适配TPC-C的核心指标是tpmCTransactions per Minute, C即系统每分钟能完成多少个“新订单”事务。它强调系统的整体吞吐量和响应时间。其负载特点包括混合读写包含插入新订单、更新支付、删除交付和复杂查询订单状态、库存水平。高并发模拟多个终端同时操作。数据争用热点数据如最后一个仓库的库存访问频繁对并发控制机制是严峻考验。我们的测试驱动程序严格按照TPC-C规范实现建表与数据加载生成符合规模要求的初始数据例如配置了10个仓库的数据。事务混合以特定比例随机执行5种事务新订单约45%支付约43%等。键值生成遵循规范要求的非均匀分布如大部分订单访问本地仓库。度量与报告持续运行一段时间如2小时收集吞吐量tpmC和平均/百分位响应时间。6.2 性能调优实战在初始测试中我们的tpmC值很低。通过性能剖析Profiling我们发现了瓶颈并逐一优化瓶颈一锁竞争激烈。在“支付”事务中需要更新仓库和地区的销售总额YTD这两条记录是全局热点。我们最初使用记录锁导致大量事务串行等待。优化对于这种“读-修改-写”的计数器更新模式我们引入了增量更新和延迟合并。事务只在日志中记录增量如10而不直接更新主数据页。后台线程定期合并增量。这大大减少了热点记录上的排他锁持有时间。当然这增加了读操作的复杂度需要读主数据并累加所有未合并的增量但在TPC-C以更新为主的负载下收益显著。瓶颈二日志刷盘成为瓶颈。每个事务提交都要强制刷日志I/O等待高。优化实现了组提交。将短时间内多个事务的提交日志在一次性I/O中刷入磁盘摊薄了每次刷盘的开销。瓶颈三B树索引分裂频繁。在大量插入下主键索引分裂导致页面锁升级和额外I/O。优化采用了B树的分裂预分配策略。在新建索引或插入非常频繁时提前分配好一批空的叶子页面形成一个“缓冲带”减少分裂的即时开销。经过多轮调优我们的系统tpmC得到了数倍的提升。这个过程让我们深刻体会到数据库性能是设计、算法和工程细节共同作用的结果。7. 开发历程中的典型问题与排查心法在长达数月的开发中我们遇到了无数问题。这里分享几个最具代表性的案例和排查思路。7.1 问题一查询结果偶尔不正确但非必现现象一个简单的等值查询在并发测试时偶尔会多返回或少返回一行数据。排查隔离怀疑对象首先在单线程下测试问题不复现初步判断是并发控制问题。日志分析增加了事务操作和加锁的详细日志。发现异常出现时两个事务对同一范围的数据加锁顺序出现了交叉。根因定位我们的范围查询如WHERE id BETWEEN 10 AND 20最初实现是先找到id10的记录上锁然后沿着叶子节点链表扫描并逐条上锁直到id20。问题在于在扫描过程中如果另一个事务在已扫描过的位置插入了一条新记录例如id15而这条记录恰好也满足范围条件它就会被漏掉。这就是幻读现象。解决为了在可串行化隔离级别下防止幻读仅靠记录锁不够。我们引入了间隙锁。在BETWEEN 10 AND 20时不仅锁住范围内所有存在的记录还要锁住记录之间的“间隙”以及两端的“上界”和“下界”间隙阻止其他事务在范围内插入新记录。这彻底解决了幻读问题。7.2 问题二系统在长时间TPC-C测试后吞吐量逐渐下降现象测试开始时tpmC正常运行几小时后吞吐量缓慢下降响应时间变长。排查监控资源使用top、iostat监控发现内存使用稳定但磁盘I/O等待时间在后期明显增高。检查缓冲池发现缓冲池的命中率在后期显著下降。分析缓冲池内容充满了大量几乎不再被访问的“冷数据”页面。根因定位我们的LRU-K算法中K值设置得较小为2且对历史访问记录的衰减策略不够积极。在TPC-C的混合负载下一些大规模的分析型查询如库存水平查询会顺序扫描大表将大量“一次性”页面刷进缓冲池污染了缓存挤出了真正热点的数据如仓库、地区表。解决我们改进了置换算法引入了“访问频率”和“最近性”的加权评估并对顺序扫描的页面进行了特殊标记让它们在缓冲池中的“生存优先级”更低。同时增加了后台线程定期清理过于陈旧的访问历史。调整后缓冲池命中率在长期运行中保持稳定。7.3 问题速查表问题现象可能原因排查方向解决思路查询返回结果集为空但数据存在1. 索引损坏2. 查询条件错误类型不匹配3. 事务隔离级别导致不可见1. 检查索引结构完整性B树遍历2. 打印优化后的查询计划检查条件表达式3. 检查事务快照或锁状态1. 重建索引2. 修正查询或数据类型3. 调整隔离级别或检查MVCC可见性判断单个事务执行很慢1. 锁等待2. 执行计划差全表扫描3. 日志同步等待1. 查看锁管理器状态是否存在阻塞链2. 使用EXPLAIN分析查询计划3. 检查WAL日志写入延迟1. 优化事务逻辑缩短锁持有时间2. 创建合适索引或更新统计信息3. 调整组提交参数或使用更快的存储系统崩溃后无法恢复1. 日志记录不完整2. 检查点信息错误3. 页面LSN与日志LSN不一致1. 检查日志文件末尾是否完整2. 检查检查点记录的有效性3. 比对崩溃前最后操作的页面和日志1. 确保日志写入是原子的如页大小对齐2. 增强检查点日志的校验和3. 严格保证WAL协议顺序8. 参赛总结与对数据库内核学习的建议回顾整个项目从阅读RMDB框架代码时的懵懂到调试第一个B树分裂成功时的兴奋再到看到TPC-C测试通过时的如释重负这是一段极其扎实和宝贵的系统编程训练。它强迫你去思考数据在磁盘和内存中的每一比特是如何组织的去设计算法在效率和正确性之间权衡去处理并发环境下各种诡异的边界条件。对于也想深入数据库内核的同学我的建议是不要一开始就试图读懂MySQL或PostgreSQL那样庞大的代码库。那会让你望而生畏。最好的路径就是像这个赛道一样从一个清晰的小框架如RMDB、BusTub开始亲手实现每一个核心模块。实现一遍B树你会对索引的理解远超任何书本实现一遍优化器你会真正明白为什么查询会慢实现一遍事务恢复你会对“持久化”有刻骨铭心的认识。在实现过程中一定要写测试。为每个模块编写单元测试例如测试B树的插入、删除、范围查询为整个系统编写集成测试例如测试多语句事务的原子性。TPC-C就是一个终极的集成测试。调试并发和恢复问题非常困难良好的日志系统是你的“眼睛”要设计不同级别的日志输出在出问题时能快速定位。最后数据库是一个博大精深的领域我们这个项目只是叩开了大门。现代数据库还有太多值得探索的方向向量化执行引擎、基于代价的优化器中的深度学习、存算分离架构、云原生分布式事务……但通过这个从零到一的过程你获得的是解决复杂系统问题的底层能力和信心这是无论未来研究哪个方向都无比珍贵的财富。本文还有配套的精品资源点击获取 从零实现关系型数据库内核：存储引擎、查询优化与事务管理的工程实践
简介本资源是全国大学生计算机系统能力大赛数据库管理系统赛道的完整参赛项目面向系统能力培养导向的高校本科生与研究生聚焦关系型数据库内核开发实践。项目基于RMDB框架实现了一套支持TPC-C基准测试的轻量级RDBMS覆盖存储引擎、查询优化器、事务管理等核心模块可作为数据库原理课程设计、系统级编程实训及竞赛备赛的高质量参考方案。压缩包共442个文件2.43MB含121个C/C头文件h/hpp与146个源码文件cc/cpp/c、47个Python脚本用于测试与工具链、30个Markdown文档含设计说明与接口规范、11个CMake/Bazel构建配置文件以及PDF技术报告和CSV测试数据等目录结构体现典型DBMS分层架构。已有70人学习下载读者可直接复现编译环境、剖析关键算法实现如B树索引、基于代价的连接优化、运行TPC-C负载验证性能并参考配套文档理解从SQL解析到物理执行的全链路设计逻辑。1. 项目概述从零构建一个“能跑”的关系型数据库如果你是一名计算机专业的学生或者对数据库底层技术充满好奇那么“自己动手写一个数据库”这个想法大概率在你脑海里闪现过。它听起来既酷炫又遥不可及仿佛是系统软件领域的皇冠。全国大学生计算机系统能力大赛数据库管理系统赛道就是为有这样想法的同学准备的顶级舞台。这个项目正是我们团队为参赛而开发的一个完整的关系型数据库管理系统RDBMS。它不是玩具而是一个从存储引擎、查询优化器到事务管理内核功能齐全并且能通过标准工业级基准测试TPC-C验证的系统。简单来说我们的目标不是重复造一个MySQL或PostgreSQL而是在有限的时间和资源下深入理解一个现代数据库内核的骨架与灵魂。我们选择了基于RMDB这个教学/研究型框架进行深度开发。RMDB提供了一个不错的起点它定义了模块接口和基础架构但真正的“血肉”——如何高效地组织数据、如何聪明地执行查询、如何保证数据在并发下的正确性——都需要我们亲手填充。最终我们实现了一个支持标准SQL子集、具备ACID事务特性、并能承受TPC-C这种复杂OLTP负载考验的数据库系统。这个过程就像是在导师提供的汽车底盘上自己设计发动机、变速箱和控制系统最后让它真正跑起来甚至去赛道上测个速。接下来我将详细拆解我们是如何一步步完成这个挑战的。2. 核心架构设计与技术选型思路当我们决定基于RMDB框架开发时首先需要吃透它的架构并在此基础上做出我们的技术决策。RMDB采用了经典的分层架构这为我们清晰地划分了工作模块。2.1 为什么选择RMDB框架市面上教学用的数据库框架不止一个比如CMU的BusTub、Stanford的SimpleDB。我们选择RMDB主要基于几点考量。首先它的代码结构清晰模块耦合度相对较低每个核心组件如StorageManagerExecutorPlanner的接口定义明确这非常有利于团队分工。其次RMDB使用C编写这让我们能更贴近工业级数据库如MySQL、SQLite的实现语言对内存管理、性能优化有更直接的掌控感同时也避免了Java等语言GC带来的不确定性对性能测试的影响。最后RMDB的社区和配套资料在国内相对丰富遇到深层次问题时有更多可参考的解决方案。但RMDB只是一个骨架。它提供了磁盘I/O的抽象、缓冲池的基本管理、记录格式的定义以及查询执行的大致流程。而真正的难点在于缓冲池替换策略用什么算法数据在磁盘上用什么结构组织堆文件、B树查询优化器基于什么规则进行等价变换和代价估算事务管理器如何实现锁或多版本并发控制MVCC这些都需要我们做出独立的设计和实现。2.2 整体系统架构拆解我们的系统最终呈现为以下核心模块的协同工作存储管理层这是系统的基石。负责管理数据在磁盘上的持久化存储。我们实现了基于缓冲池Buffer Pool的磁盘数据缓存机制并在此基础上构建了两种主要的存储引擎结构用于顺序存储的堆文件Heap File和用于高效索引的B树。这一层直接决定了数据存取的效率。查询处理层这是系统的“大脑”。它接收SQL语句经过解析器Parser生成抽象语法树AST然后由查询优化器Optimizer进行重写、选择执行路径生成最优的物理执行计划最后由执行器Executor调用存储层的接口逐行处理数据。优化器是我们投入精力最多的模块之一。事务管理层这是系统的“安全卫士”。它确保数据库的ACID特性。我们实现了基于锁的并发控制协议两阶段锁2PL和Write-Ahead LoggingWAL日志机制来保证事务的原子性、一致性和隔离性。恢复管理器则基于WAL日志在系统崩溃后恢复数据一致性。TPC-C驱动与测试层这不是数据库内核的一部分但却是项目的“验收官”。我们实现了TPC-C基准测试的标准驱动程序模拟一个批发公司的业务负载新建订单、支付、订单状态查询等持续对数据库施加压力并最终收集衡量性能的指标tpmC每分钟完成的事务数。这个架构决定了我们的开发路线图先让存储引擎稳定读写再让执行器能跑通简单查询接着优化器提升复杂查询效率然后事务管理器保证并发正确性最后用TPC-C验证整体性能和稳定性。每一步都环环相扣。3. 存储引擎数据如何被高效地放置与查找存储引擎是数据库的“仓库管理员”它的设计直接决定了数据存取的性能。我们的核心工作是实现了缓冲池管理、堆文件组织和B树索引。3.1 缓冲池在内存与磁盘之间架起高速桥梁数据库的数据远大于内存容量因此需要一个智能的缓存系统。缓冲池就是一块固定的内存区域用于缓存从磁盘读出的数据页Page。我们的实现关键点在于页面置换算法当缓冲池满时需要淘汰一个旧页面。我们对比了LRU最近最少使用和Clock算法。LRU实现简单但对顺序扫描全表扫描不友好会污染缓存。我们最终实现了改进版的LRU-K算法它不只记录最近一次访问而是记录最近K次访问的历史能更好地区分“热点数据”和“一次性扫描数据”在TPC-C的混合负载下表现更稳定。钉住Pin与脏页Dirty Page执行器在读取或修改一个页面时必须“钉住”它防止被置换出去。修改后的页面标记为“脏”由后台线程或检查点机制定期刷回磁盘。这里的一个关键细节是我们严格管理了pin_count和dirty标志确保线程安全避免一个正在被事务修改的页面被意外淘汰。预取Prefetching对于顺序扫描操作我们实现了简单的顺序预取。当执行器请求第N页时缓冲池管理器会异步地将第N1, N2页也加载到缓冲池中有效减少了I/O等待。实操心得缓冲池的调试陷阱。初期我们曾遇到一个诡异的“数据消失”问题事务提交后再次查询数据有时会丢失。排查了很久最终发现是在某个错误处理分支中页面被修改后没有正确标记为dirty导致刷盘时漏掉了这个页面。教训是所有修改页面的操作必须在同一原子操作中递增pin_count和设置dirty标志并且要有完善的单元测试覆盖所有异常路径。3.2 堆文件与B树两种核心数据组织方式堆文件Heap File这是最简单的存储方式数据记录按插入顺序依次存放。我们使用一个“空闲空间映射”来快速找到有空间插入新记录的页面。堆文件的优势是插入极快O(1)但根据条件查找特定记录需要全表扫描O(n)。它适合数据仓库中追加式的批量加载或者作为没有索引的表的底层存储。B树索引这是数据库索引的绝对核心。我们实现了典型的B树结构支持等值查找、范围查找和有序遍历。叶子节点存储键值Key和记录IDRID内部节点存储导航键。实现难点包括分裂与合并当节点满时需分裂当节点元素过少时需与兄弟节点合并或重新分配。这些操作必须保证树的平衡并且是原子性的我们通过精心设计页面操作顺序和WAL日志来保证。并发控制B树的并发访问非常频繁。我们实现了Crabbing Protocol蟹行协议的变种。搜索时从根到叶子一路共享锁S锁仅在需要修改的叶子节点才升级为排他锁X锁插入/删除时从根向下在可能发生分裂/合并的路径节点上使用排他锁但范围控制得尽可能小以减少锁冲突。这比直接锁整棵树效率高得多。为什么选择B树而不是B树或哈希B树所有数据都在叶子节点且叶子节点链表连接这使得范围查询和全键值顺序遍历的效率极高非常适合数据库最常见的“WHERE ... BETWEEN ...”和“ORDER BY”场景。哈希索引虽然等值查询是O(1)但无法支持范围查询。B树的数据可能在任何节点遍历不如B树高效。因此B树在关系型数据库中成为了索引的默认选择。4. 查询优化器让SQL执行从“蛮干”到“巧干”如果没有优化器执行器可能会用最笨的方式执行查询。例如SELECT * FROM A, B WHERE A.id B.a_id AND A.name ‘foo‘可能会先对A做全表扫描找出所有name‘foo‘的记录然后对每一条记录再去B表做全表扫描找匹配的a_id。如果表很大这就是灾难。优化器的任务就是把这种“蛮干”计划变成“巧干”计划。4.1 优化器的核心工作流程我们的优化器遵循经典的Volcano/Cascades风格模型分为几个阶段语法分析与生成初始逻辑计划解析器将SQL变成语法树然后转换成初始的关系代数表达式树如Select, Project, Join, Scan。逻辑优化基于关系代数等价规则对表达式树进行重写目标是减少中间结果集的大小。我们实现了以下常见规则谓词下推尽早执行选择Select操作把过滤条件A.name ‘foo‘推到连接Join之前减少参与连接的数据量。投影下推尽早执行投影Project操作只取出后续计算需要的列减少数据在内存中的体积。连接重排序对于多表连接A JOIN B JOIN C连接顺序不同产生的中间结果大小天差地别。我们实现了基于动态规划的连接顺序优化算法估算每种连接顺序的代价选择代价最小的。物理优化与代价估算为逻辑计划中的每个操作符选择具体的物理实现算法并估算其代价。这是最核心也最困难的部分。代价模型我们建立了一个简单的代价模型Cost CPU_Cost I/O_Cost。I/O成本占主导我们主要计算需要读写的页面数。为此系统需要维护表的统计信息包括总行数、每列的不同值数量基数、最大值、最小值等。这些信息通过ANALYZE命令定期收集。选择率估算对于WHERE col value这样的条件优化器需要估算满足条件的行数占总行数的比例。我们假设数据均匀分布利用列基数来估算选择率 ≈ 1 / NDV(col)。对于范围查询则利用最大值最小值来估算。连接算法选择对于Join操作我们实现了三种物理算法优化器根据情况选择嵌套循环连接适用于小表驱动大表或者有索引可用的情况。哈希连接适用于内存能装下其中一张表或分区的情况它是等值连接效率最高的算法之一。我们实现了Grace Hash Join当表太大时进行分区落盘。排序合并连接当输入数据已经有序或者需要输出有序结果时很有优势。生成最终执行计划经过以上步骤得到一棵附带了具体算法和代价估算的物理执行计划树交给执行器去执行。4.2 一个优化实例分析假设查询SELECT * FROM orders, customer WHERE orders.c_id customer.id AND customer.credit ‘good‘。糟糕的计划全表扫描customer对每一行credit‘good‘的记录全表扫描orders找匹配的c_id。代价是|customer| |good_customer| * |orders|次页面I/O。优化后的计划谓词下推先对customer表执行credit‘good‘的选择操作得到一个小的结果集good_cust。连接重排序与算法选择现在连接good_cust和orders。因为good_cust很小优化器可能选择以它为构建表orders为探测表进行哈希连接。如果orders在c_id上有B树索引也可能选择索引嵌套循环连接即遍历good_cust每次用c_id去索引中快速查找orders记录。最终代价可能降低为扫描customer表的代价 构建good_cust哈希表的代价 扫描orders表一次的代价哈希连接或|good_cust|次索引查找的代价。注意事项统计信息的重要性与局限性。优化器的好坏极度依赖统计信息的准确性。如果统计信息过时例如customer表刚插入大量credit‘bad‘的记录但统计信息显示credit分布均匀优化器可能会严重误判选择率选出糟糕的计划。因此在TPC-C测试前我们必须对测试表执行ANALYZE。此外我们的简单代价模型无法考虑CPU缓存命中率、顺序I/O与随机I/O的差异等更复杂的硬件因素这是一个可以继续深化的方向。5. 事务管理与恢复保障数据的“金科玉律”数据库事务必须满足ACID特性我们通过锁管理器Lock Manager和预写日志WAL两大组件来实现。5.1 基于锁的并发控制我们实现了严格的**两阶段锁2PL**协议事务在释放任何一个锁之后就不能再申请任何新的锁。这保证了可串行化隔离级别。锁管理器维护一个全局的锁表记录每个资源我们以RID即记录ID为粒度上的锁信息。锁的升级与等待事务T1持有R1的共享锁(S锁)事务T2也想获得R1的排他锁(X锁)进行修改T2必须等待。锁管理器处理这种等待队列防止饿死。当T1释放锁后唤醒等待队列中的T2。死锁检测与处理我们采用周期性的死锁检测而非预防。维护一个“等待图”Wait-for Graph节点是事务边表示T1正在等待T2占用的资源。定期运行一个后台线程检测图中是否有环。一旦发现死锁选择一个“代价最小”的事务如修改数据最少的事务进行回滚Abort释放其所有锁从而打破死锁。锁粒度我们主要实现了记录级锁这对OLTP的TPC-C负载比较合适。也在表级提供了意向锁IS, IX用于在B树遍历时快速判断子树是否可能被上锁提高效率。5.2 预写日志与恢复为了保证原子性和持久性我们实现了Write-Ahead Logging。其核心原则是任何数据页面的修改必须在页面本身被写回磁盘之前先将其对应的日志记录持久化到磁盘上的日志文件中。日志格式每条日志记录包含唯一LSN日志序列号、事务ID、日志类型Update, Commit, Abort等、修改的前像Before-Image和后像After-Image。提交协议事务提交时并不立即将所有修改的脏页刷盘这很慢而是只需强制写入一条COMMIT日志记录到磁盘。只要这条日志落盘事务就算持久化提交了。脏页由后台的检查点Checkpoint线程异步刷回。恢复过程系统崩溃重启后恢复管理器启动扫描日志文件重做阶段Redo从最后一个检查点开始正向扫描日志对所有日志包括已提交和未提交事务根据后像重新执行一遍操作。这保证了已提交事务的修改不会丢失即使脏页没刷盘。撤销阶段Undo反向扫描日志对所有在崩溃时未提交的事务根据前像执行反向操作回滚所有修改。这保证了未提交事务的修改不会残留。我们实现了ARIES恢复算法的简化版支持逻辑Undo和检查点使得恢复过程更快、更健壮。踩坑实录日志序列号与页面LSN的同步。在实现WAL时我们曾遇到一个棘手的Bug系统恢复后某些已提交事务的修改丢失了。经过逐条日志分析发现是在写日志记录和更新数据页面pageLSN页面最后修改的日志号时顺序出了问题。正确的顺序必须是1) 在内存中组装好日志记录2) 将日志记录写入日志缓冲区3)更新内存中页面的pageLSN4) 修改页面内容。如果步骤3和4颠倒可能在页面修改后、pageLSN更新前发生崩溃导致恢复时误认为这个页面的修改已经持久化因为其pageLSN小于日志中的LSN从而跳过重做造成数据丢失。这个细节对保证恢复的正确性至关重要。6. TPC-C基准测试工业级的压力检验实现所有内核功能后我们需要一个公正的“考官”来检验系统的成色。TPC-C是事务处理性能委员会制定的经典OLTP基准测试模拟了一个批发公司的业务包含5种事务类型和9张表非常复杂且贴近真实场景。6.1 TPC-C负载特性与我们的适配TPC-C的核心指标是tpmCTransactions per Minute, C即系统每分钟能完成多少个“新订单”事务。它强调系统的整体吞吐量和响应时间。其负载特点包括混合读写包含插入新订单、更新支付、删除交付和复杂查询订单状态、库存水平。高并发模拟多个终端同时操作。数据争用热点数据如最后一个仓库的库存访问频繁对并发控制机制是严峻考验。我们的测试驱动程序严格按照TPC-C规范实现建表与数据加载生成符合规模要求的初始数据例如配置了10个仓库的数据。事务混合以特定比例随机执行5种事务新订单约45%支付约43%等。键值生成遵循规范要求的非均匀分布如大部分订单访问本地仓库。度量与报告持续运行一段时间如2小时收集吞吐量tpmC和平均/百分位响应时间。6.2 性能调优实战在初始测试中我们的tpmC值很低。通过性能剖析Profiling我们发现了瓶颈并逐一优化瓶颈一锁竞争激烈。在“支付”事务中需要更新仓库和地区的销售总额YTD这两条记录是全局热点。我们最初使用记录锁导致大量事务串行等待。优化对于这种“读-修改-写”的计数器更新模式我们引入了增量更新和延迟合并。事务只在日志中记录增量如10而不直接更新主数据页。后台线程定期合并增量。这大大减少了热点记录上的排他锁持有时间。当然这增加了读操作的复杂度需要读主数据并累加所有未合并的增量但在TPC-C以更新为主的负载下收益显著。瓶颈二日志刷盘成为瓶颈。每个事务提交都要强制刷日志I/O等待高。优化实现了组提交。将短时间内多个事务的提交日志在一次性I/O中刷入磁盘摊薄了每次刷盘的开销。瓶颈三B树索引分裂频繁。在大量插入下主键索引分裂导致页面锁升级和额外I/O。优化采用了B树的分裂预分配策略。在新建索引或插入非常频繁时提前分配好一批空的叶子页面形成一个“缓冲带”减少分裂的即时开销。经过多轮调优我们的系统tpmC得到了数倍的提升。这个过程让我们深刻体会到数据库性能是设计、算法和工程细节共同作用的结果。7. 开发历程中的典型问题与排查心法在长达数月的开发中我们遇到了无数问题。这里分享几个最具代表性的案例和排查思路。7.1 问题一查询结果偶尔不正确但非必现现象一个简单的等值查询在并发测试时偶尔会多返回或少返回一行数据。排查隔离怀疑对象首先在单线程下测试问题不复现初步判断是并发控制问题。日志分析增加了事务操作和加锁的详细日志。发现异常出现时两个事务对同一范围的数据加锁顺序出现了交叉。根因定位我们的范围查询如WHERE id BETWEEN 10 AND 20最初实现是先找到id10的记录上锁然后沿着叶子节点链表扫描并逐条上锁直到id20。问题在于在扫描过程中如果另一个事务在已扫描过的位置插入了一条新记录例如id15而这条记录恰好也满足范围条件它就会被漏掉。这就是幻读现象。解决为了在可串行化隔离级别下防止幻读仅靠记录锁不够。我们引入了间隙锁。在BETWEEN 10 AND 20时不仅锁住范围内所有存在的记录还要锁住记录之间的“间隙”以及两端的“上界”和“下界”间隙阻止其他事务在范围内插入新记录。这彻底解决了幻读问题。7.2 问题二系统在长时间TPC-C测试后吞吐量逐渐下降现象测试开始时tpmC正常运行几小时后吞吐量缓慢下降响应时间变长。排查监控资源使用top、iostat监控发现内存使用稳定但磁盘I/O等待时间在后期明显增高。检查缓冲池发现缓冲池的命中率在后期显著下降。分析缓冲池内容充满了大量几乎不再被访问的“冷数据”页面。根因定位我们的LRU-K算法中K值设置得较小为2且对历史访问记录的衰减策略不够积极。在TPC-C的混合负载下一些大规模的分析型查询如库存水平查询会顺序扫描大表将大量“一次性”页面刷进缓冲池污染了缓存挤出了真正热点的数据如仓库、地区表。解决我们改进了置换算法引入了“访问频率”和“最近性”的加权评估并对顺序扫描的页面进行了特殊标记让它们在缓冲池中的“生存优先级”更低。同时增加了后台线程定期清理过于陈旧的访问历史。调整后缓冲池命中率在长期运行中保持稳定。7.3 问题速查表问题现象可能原因排查方向解决思路查询返回结果集为空但数据存在1. 索引损坏2. 查询条件错误类型不匹配3. 事务隔离级别导致不可见1. 检查索引结构完整性B树遍历2. 打印优化后的查询计划检查条件表达式3. 检查事务快照或锁状态1. 重建索引2. 修正查询或数据类型3. 调整隔离级别或检查MVCC可见性判断单个事务执行很慢1. 锁等待2. 执行计划差全表扫描3. 日志同步等待1. 查看锁管理器状态是否存在阻塞链2. 使用EXPLAIN分析查询计划3. 检查WAL日志写入延迟1. 优化事务逻辑缩短锁持有时间2. 创建合适索引或更新统计信息3. 调整组提交参数或使用更快的存储系统崩溃后无法恢复1. 日志记录不完整2. 检查点信息错误3. 页面LSN与日志LSN不一致1. 检查日志文件末尾是否完整2. 检查检查点记录的有效性3. 比对崩溃前最后操作的页面和日志1. 确保日志写入是原子的如页大小对齐2. 增强检查点日志的校验和3. 严格保证WAL协议顺序8. 参赛总结与对数据库内核学习的建议回顾整个项目从阅读RMDB框架代码时的懵懂到调试第一个B树分裂成功时的兴奋再到看到TPC-C测试通过时的如释重负这是一段极其扎实和宝贵的系统编程训练。它强迫你去思考数据在磁盘和内存中的每一比特是如何组织的去设计算法在效率和正确性之间权衡去处理并发环境下各种诡异的边界条件。对于也想深入数据库内核的同学我的建议是不要一开始就试图读懂MySQL或PostgreSQL那样庞大的代码库。那会让你望而生畏。最好的路径就是像这个赛道一样从一个清晰的小框架如RMDB、BusTub开始亲手实现每一个核心模块。实现一遍B树你会对索引的理解远超任何书本实现一遍优化器你会真正明白为什么查询会慢实现一遍事务恢复你会对“持久化”有刻骨铭心的认识。在实现过程中一定要写测试。为每个模块编写单元测试例如测试B树的插入、删除、范围查询为整个系统编写集成测试例如测试多语句事务的原子性。TPC-C就是一个终极的集成测试。调试并发和恢复问题非常困难良好的日志系统是你的“眼睛”要设计不同级别的日志输出在出问题时能快速定位。最后数据库是一个博大精深的领域我们这个项目只是叩开了大门。现代数据库还有太多值得探索的方向向量化执行引擎、基于代价的优化器中的深度学习、存算分离架构、云原生分布式事务……但通过这个从零到一的过程你获得的是解决复杂系统问题的底层能力和信心这是无论未来研究哪个方向都无比珍贵的财富。本文还有配套的精品资源点击获取