简介数据库管理系统是集存储、查询、事务于一体的复杂软件系统其设计不仅考验算法能力更考验工程取舍与系统稳定性。从底层存储引擎的页管理与缓冲池优化到B树索引的并发控制再到SQL查询优化、事务隔离与崩溃恢复每一个环节都直接影响数据库的性能与可靠性。理解这些核心原理是构建高性能、高可用数据库内核的基础也广泛应用于金融交易、电商平台、大数据分析等真实业务场景。本文围绕一份全国一等奖的数据库管理系统设计作品剖析其在存储、查询、并发与恢复等关键模块上的工程决策为开发者提供可借鉴的系统设计思路与实战经验。 最近在整理2023年数据库管理系统设计赛的获奖材料翻到这份一等奖作品的源码包时我下意识多看了几遍。说真的这个题目每年都有大量队伍参加但真正能跑通完整SQL、保证事务不死锁、崩溃还能恢复的凤毛麟角。这份作品能拿全国一等奖不是靠运气而是靠一整套踏实的工程决策。这篇博客我就围绕这个作品讲讲数据库管理系统设计中那些决定成败的细节。1. 先搞清楚这比赛在考什么代码量不是重点1.1 为什么数据库管理系统是最能体现系统能力的赛题计算机系统能力大赛里的数据库管理系统设计赛和普通的算法竞赛、代码马拉松完全不一样。算法题考的是单点突破一句话就能描述清楚问题给你一个函数接口你把性能跑上去就行。数据库管理系统不是这样它是一个复杂的软件系统要求参赛队伍在一学期左右的时间里从零实现一个能稳定运行、支持SQL查询、具备事务能力的数据库内核。这考的不是“会不会某个算法”而是“能不能把一个复杂的软件系统拆清楚、做扎实让各个模块顺畅协作”。评审专家看重的不是谁写的代码行数多也不是谁用了某个冷门的新技术。真正拉开差距的是系统整体架构的完整性、可扩展性以及面对异常情况时的稳定性。很多队伍能做到单线程下跑通几个简单查询但一上并发、一断电或者一跑复杂join系统就崩。这恰恰是“比赛作品”和“课程作业”之间最关键的分水岭。1.2 一等奖作品的服务对象与功能边界这份获奖作品目标很明确实现一个功能完整的关系型数据库管理系统支持类MySQL的SQL语法覆盖表的创建与删除、索引管理、增删改查、多表连接、聚合分组、事务提交与回滚。它还额外支持了并发控制、检查点恢复和基本的多用户访问这些在比赛评分标准里属于高阶加分项也是很多队伍直接放弃的部分。这个作品最值得称赞的一点是它把“功能边界”定得很清晰。团队没有盲目去砸一堆花哨特性而是先把主链路做稳再往周边扩展。比如它先保证了B树索引在并发写入下不丢数据之后再考虑查询优化器对谓词下推的改进。这种“先让系统跑得稳再让它跑得快”的思路也正是工业级数据库开发的常态。2. 存储引擎数据在磁盘上的家决定了系统下限2.1 页面管理与缓冲池别小看读写效率数据库和普通文件系统最关键的区别在于数据库需要管理大量的、结构化的数据并且要在极短的时间内完成读取和写入。如果每个字段都直接调用操作系统的文件读写接口性能会惨不忍睹。正确的做法是采用“页”Page这一逻辑存储单位通常每页大小设为4KB或8KB对整个表空间或数据库文件按页进行管理。这份作品在页面管理上做得相当扎实。它的页面生命周期包括从磁盘加载到缓冲池、在缓冲池中被更改、被标记为脏页、最终异步刷回磁盘。这个过程中有一个很容易被忽略的点——缓冲池的大小和替换策略。作品里实现的是优化过的LRU-K算法而不是最基础的LRU。LRU-K和经典LRU的区别在于它跟踪页面在最近K次访问的历史可以避免全表扫描时偶发访问的页面把真正高频的索引页挤出去这在混合负载下性能优势非常明显。这里补充一句很多参赛队伍会把精力全放在索引和查询优化上认为缓冲池就是“缓存一下而已”。但实际上缓冲池命中率往往决定了数据库90%以上的读性能。一个设计良好的缓冲池应该把热数据稳稳放在内存里同时还要有预读机制避免顺序扫描时频繁卡在磁盘I/O上。这份作品预读做得也很讲究它不是简单地每次多读几个页而是根据查询计划里的访问模式点查还是范围扫描动态调整预读长度这是我复现源码时觉得非常惊艳的地方。2.2 索引结构选型B树 vs LSM-Tree索引是数据库加速查询的核心工具而索引结构的选择本质上是在读性能、写性能和空间占用之间做权衡。参赛作品里绝大部分队伍都会选择B树这份作品也不例外。原因很简单B树在点查询和范围查询上都能保持稳定的对数复杂度而且天然支持按序扫描非常适合比赛常见的TPC-H风格查询和点查压力测试。相比之下LSM-Tree写入性能更强但读放大和空间放大的问题更难控制。在比赛这种有限时间内把一个LSM-Tree的压缩策略调好难度远大于把B树调通。所以这个团队选择B树作为主索引结构是成熟且理性的工程决策。不过实现B树也有大量细节。最有意思的是它的叶子节点和内部节点都采用了“预分配空闲槽位”的方式并不等插入时再临时申请内存。这个设计可以减少节点分裂时的内存分配次数也方便实现并发控制。它的节点分裂策略也不是简单的“满一半就分裂”而是一种“延迟分裂”思想当节点快满但兄弟节点还有空间时优先向兄弟节点借位只有整组节点都满了才分裂。这个优化让B树的写放大减少了不少也让我想起Berkeley DB里的一些经典技巧。2.3 数据字典与系统表设计存储引擎之上还有一个容易被忽视的部分数据字典。数据字典负责管理系统中的元数据包括所有数据库、表、索引、列信息、约束、权限等。作品里把这些元数据同样用B树存储在系统表空间里而不是在内存里维护一份简单的结构体。这样做有一个天大的好处系统重启后不必再去解析一堆配置文件直接可以从系统表恢复出整个集群的元数据状态。数据字典的访问必须走统一的事务流程这样任何一条元数据的创建和修改都可以回滚。这一点在支持“CREATE TABLE ... 失败后自动清理”等场景时至关重要。我看到不少队伍在实现多表连接时因为数据字典里缺少列级统计信息导致优化器只能靠猜来设计连接顺序最终性能惨不忍睹。而这个作品从第一天起就把统计信息同步更新到数据字典中为后续的查询优化打好了底子。3. 查询处理链路让SQL从字符串变成高性能执行计划3.1 词法语法分析与语义检查SQL是数据库系统对外提供的唯一接口因此系统的第一站就是SQL解析器。这份作品用Lex与Yacc生成词法与语法分析器把SQL语句解析为抽象语法树AST然后通过语义分析检查表名、列名、函数是否存在数据类型是否匹配权限是否足够。这一步看似基础但涉及非常多的边界情况比如连续嵌套的子查询、带有复杂谓词的JOIN条件处理。很多队伍在语法分析阶段就崩溃因为SQL语法极其繁杂光是SELECT子句就能组合出无数种形式。但作品的做法很聪明在AST生成后立刻进行一次“规范化”把各种SQL等价写法统一成一个内部表示。比如把WHERE a 1 AND b 2转换成统一的 conjuctive normal form合取范式把复杂的子查询尝试转换为等价的JOIN。这样后续优化器和执行器的处理逻辑就变得非常简单不需要为一个SQL的特定写法单独写分支。3.2 优化器的关键决策连接顺序与索引选择得到语法树之后真正决定查询性能的核心组件是查询优化器。这个作品构建了一个基于代价的优化器并且采用了动态规划的方式来枚举多表连接的顺序。大赛测试集里常见的查询大多是3到6张表的连接如果直接枚举所有排列数量会爆炸式增长。作品通过“切割”策略把表集合分成左右两个子集递归考虑同时使用分支定界砍掉明显代价过高的子树。代价估算里最重要的是基数估计也就是每个算子会产生多少行数据。作品在系统表里保存了每个表的总行数、每列的不同值数量、最大值和最小值并且利用这些信息估算选择率。对于没有统计信息的列它会采用默认的选择率0.1并且通过运行时统计自动修正。这个“从默认值到自查优化”的过程让我想起PostgreSQL里analyze命令的思路只不过作品把它压缩到了一个更简化的模型里。至于索引选择作品会把可用的索引与查询谓词做匹配优先选择能缩小扫描范围的索引路径。它还实现了索引条件与过滤条件的分离例如WHERE age 20 AND name Tom如果age上有索引那么age 20作为索引范围条件name Tom则作为回表后的过滤条件。这是一件很细节但很见功力的事因为很多参赛队伍只会做全表扫描一旦遇到范围查询就只能硬扛。3.3 执行器算子设计与火山模型执行器是查询计划的执行者作品采用的是经典的“火山模型”Volcano Model每一个算子都实现next()接口通过迭代器的方式一层层向上返回数据。这种模型胜在代码结构清晰每个算子可以独立测试也方便增加新的算子类型。它支持了SeqScan、IndexScan、NestLoopJoin、HashJoin、Aggregation、Sort等多种算子。工程实现里HashJoin算子特别讲究。作品没有选择最基本的“把左边全部建成哈希表再探测右边”而是实现了“分块哈希连接”Grace HashJoin当哈希表内存不足时把左右两张表按哈希值分成多个桶分别写回临时文件再对每个分桶递归地做哈希连接。这让系统在处理大表连接时不会因内存溢出而崩掉同时它采用了“右侧建表左侧探测”的策略即把小表作为建表侧把哈希表的内存消耗压到最低。聚合算子的实现也值得一提。作品区分了无GROUP BY的聚合和带GROUP BY的聚合。对于后者它在聚合时利用了哈希表分组键作为哈希键同时维护一个“内存滑窗”用于在GROUP BY字段有顺序时优化排序导致的开销。这种实现让我看到团队对执行细节的较真程度。4. 并发控制与恢复机制正确性比性能更敏感4.1 基于锁的并发控制死锁检测到怎么处理任何数据库管理系统只要宣称支持多用户访问就必须处理并发冲突。作品采用的是两阶段锁协议即事务在访问数据前必须获得相应粒度的锁并且一旦事务释放一个锁就不再请求新的锁。锁粒度覆盖了表级锁和行级锁对于单点操作如主键查询会自动升级为行级锁而对于全表扫描则使用表级锁避免需要同时持有太多行锁造成锁表空间膨胀。死锁是并发控制的经典难题。作品用了超时检测加等待图检测的双重办法先看一个事务等待锁的时间是否超过阈值如果超时就判定为疑似死锁如果同一时刻多个事务互相等待则在等待图中做环检测一旦检测到环就选择代价最小的那个事务中止回滚。这里面“代价最小”的定义很实际综合了事务已执行时间、持有的锁数量以及被其他事务等待的数量。这个设计在比赛演示环节里表现得很亮眼即使评审故意制造了多个高并发事务交叉更新同一批数据系统也能在几十毫秒内自动解除死锁而不是直接卡死。4.2 日志机制与崩溃恢复WAL的核心思路崩溃恢复是数据库系统稳定性的最后一道防线。作品的恢复机制严格遵循Write-Ahead LoggingWAL原则任何数据页的修改都必须先写入日志再更新缓冲池里的页面。日志记录采用物理日志和逻辑日志混合的方式物理日志记录操作的是哪个页面和页面内的具体偏移量变化逻辑日志则记录的是“更新前值”和“更新后值”用于回滚时做UNDO。恢复流程分为三个阶段分析阶段、重做阶段和回滚阶段。启动时系统先扫描日志从最后一个检查点开始分析出哪些事务在崩溃时已经提交、哪些还在活跃中。然后重做所有已提交事务的日志记录把数据页恢复到崩溃前的状态对于未提交事务则利用UNDO日志逐条回滚撤销已经写到磁盘上的影响。这个流程虽然说起来简单但实现时会有大量细节比如日志的LSN号如何递增、如何与页面的LSN对比来判断是否需要重做这些作品都处理得相当严谨。4.3 MVCC作为加分项在锁并发之外作品还实现了基于多版本并发控制MVCC的快照隔离。它给每个事务分配了一个递增的事务ID并且在每一行数据上保存创建该行版本的事务ID和删除该行版本的事务ID。读操作根据当前事务的快照条件判断哪些版本可见写操作则生成新版本而不是原地覆盖。有了MVCC系统可以把“读写阻塞”降到最低。一个事务在读的时候另一个事务写同一行不会发生冲突因为读事务看到的是快照版本。这个设计在比赛的高级功能评测里是很大的加分点而且在演示活跃的Web应用场景时系统的并发吞吐量明显高于那些只靠锁的系统。实现MVCC最麻烦的是垃圾回收。如果一直保留旧版本存储空间会无限制增长。作品实现了一种类似PostgreSQL的Vacuum机制在后台线程中定期扫描没有活跃事务引用的旧版本并物理回收。它还特别处理了一个边界条件当某个事务长时间不提交时比该事务ID更大的所有新版数据都不能被回收所以它会把这种“长事务”的ID记录到系统表中避免后台清理线程误删。这一点很多工程经验不足的队伍完全想不到。5. 从比赛源码里提炼的工程经验想拿高分得这么干5.1 性能测试里的“不公平优势”如何在白盒测试里稳压对手比赛现场性能测试有一个和真实场景不同的地方评测环境通常是可控的数据集是预先准备好的查询负载也是固定的。这意味着可以针对评测特征做出一些“看似取巧但其实合理”的优化而这些优化在通用场景下未必适用但在这里能带来巨大收益。这份作品性能最亮眼的几个优化都围绕“索引选择”和“执行计划缓存”展开。它把同一查询文本的执行计划缓存起来第二次执行时直接复用省去了解析和优化的时间。同时它根据评测表的统计信息为每个表预建了多个复合索引当查询里的WHERE条件命中多个索引时优化器会尝试Bitmap Index Scan的方式将多个索引的结果集做位图与或运算大幅降低回表次数。这些特性加起来让它在评测中的查询平均响应时间比第二名快了将近一倍。5.2 团队协作与模块拆分的智慧从源码的目录结构看这个团队的工程组织能力也相当强。整个项目分为catalog、storage、executor、optimizer、transaction、recovery六个核心模块模块之间通过清晰的头文件接口通信没有循环依赖。这意味着每个模块可以独立测试、独立调试后期集成的成本被压缩得很低。我尤其欣赏他们对“错误处理”的规范。几乎每个函数都会返回统一的自定义错误码所有错误码都在一个中心头文件里登记并附有说明文档。这使得在遇到崩溃时可以迅速定位到具体模块和错误原因而不是像很多比赛项目一样靠到处打印日志来猜问题。良好的模块边界和错误处理是6个人团队能在一学期里交出这么完整作品的重要前提。5.3 我踩过的坑与建议如果我是一个明年要参加这个比赛的选手我会从这份作品里吸取三个教训。第一不要从索引开始。很多队伍一上来就写B树而把文件管理和数据页结构抛在脑后这是本末倒置。没有可靠的页管理和缓冲池再牛的索引也无法稳定工作。先把单表无索引的增删改查跑通再考虑加索引。第二一定要从第一天就支持事务。即使最简单的单线程系统也要把日志和恢复机制考虑进去。因为一旦项目后期再加入事务模块你会发现所有存储操作的接口都需要重新设计那才是灾难。第三性能压测要趁早。不要等到所有功能做完了再开始优化。作品团队每周都会跑一次TPC-H的简化测试集记录各项查询的响应时间用性能变化曲线来追踪每次代码改动的收益。这样既能防止性能回退也能让大家看到进展保持动力。我在实际接触数据库内核开发后越来越感受到一个道理数据库管理系统设计赛真正奖励的不是那些会背概念的人而是能在有限时间内做出正确工程取舍的人。这份一等奖作品的源码包在我看来就是一本最好的教材它告诉后来者什么才叫“把系统做出来、做稳、做快”。本文还有配套的精品资源点击获取
从一等奖作品看数据库管理系统设计的关键工程决策
简介数据库管理系统是集存储、查询、事务于一体的复杂软件系统其设计不仅考验算法能力更考验工程取舍与系统稳定性。从底层存储引擎的页管理与缓冲池优化到B树索引的并发控制再到SQL查询优化、事务隔离与崩溃恢复每一个环节都直接影响数据库的性能与可靠性。理解这些核心原理是构建高性能、高可用数据库内核的基础也广泛应用于金融交易、电商平台、大数据分析等真实业务场景。本文围绕一份全国一等奖的数据库管理系统设计作品剖析其在存储、查询、并发与恢复等关键模块上的工程决策为开发者提供可借鉴的系统设计思路与实战经验。 最近在整理2023年数据库管理系统设计赛的获奖材料翻到这份一等奖作品的源码包时我下意识多看了几遍。说真的这个题目每年都有大量队伍参加但真正能跑通完整SQL、保证事务不死锁、崩溃还能恢复的凤毛麟角。这份作品能拿全国一等奖不是靠运气而是靠一整套踏实的工程决策。这篇博客我就围绕这个作品讲讲数据库管理系统设计中那些决定成败的细节。1. 先搞清楚这比赛在考什么代码量不是重点1.1 为什么数据库管理系统是最能体现系统能力的赛题计算机系统能力大赛里的数据库管理系统设计赛和普通的算法竞赛、代码马拉松完全不一样。算法题考的是单点突破一句话就能描述清楚问题给你一个函数接口你把性能跑上去就行。数据库管理系统不是这样它是一个复杂的软件系统要求参赛队伍在一学期左右的时间里从零实现一个能稳定运行、支持SQL查询、具备事务能力的数据库内核。这考的不是“会不会某个算法”而是“能不能把一个复杂的软件系统拆清楚、做扎实让各个模块顺畅协作”。评审专家看重的不是谁写的代码行数多也不是谁用了某个冷门的新技术。真正拉开差距的是系统整体架构的完整性、可扩展性以及面对异常情况时的稳定性。很多队伍能做到单线程下跑通几个简单查询但一上并发、一断电或者一跑复杂join系统就崩。这恰恰是“比赛作品”和“课程作业”之间最关键的分水岭。1.2 一等奖作品的服务对象与功能边界这份获奖作品目标很明确实现一个功能完整的关系型数据库管理系统支持类MySQL的SQL语法覆盖表的创建与删除、索引管理、增删改查、多表连接、聚合分组、事务提交与回滚。它还额外支持了并发控制、检查点恢复和基本的多用户访问这些在比赛评分标准里属于高阶加分项也是很多队伍直接放弃的部分。这个作品最值得称赞的一点是它把“功能边界”定得很清晰。团队没有盲目去砸一堆花哨特性而是先把主链路做稳再往周边扩展。比如它先保证了B树索引在并发写入下不丢数据之后再考虑查询优化器对谓词下推的改进。这种“先让系统跑得稳再让它跑得快”的思路也正是工业级数据库开发的常态。2. 存储引擎数据在磁盘上的家决定了系统下限2.1 页面管理与缓冲池别小看读写效率数据库和普通文件系统最关键的区别在于数据库需要管理大量的、结构化的数据并且要在极短的时间内完成读取和写入。如果每个字段都直接调用操作系统的文件读写接口性能会惨不忍睹。正确的做法是采用“页”Page这一逻辑存储单位通常每页大小设为4KB或8KB对整个表空间或数据库文件按页进行管理。这份作品在页面管理上做得相当扎实。它的页面生命周期包括从磁盘加载到缓冲池、在缓冲池中被更改、被标记为脏页、最终异步刷回磁盘。这个过程中有一个很容易被忽略的点——缓冲池的大小和替换策略。作品里实现的是优化过的LRU-K算法而不是最基础的LRU。LRU-K和经典LRU的区别在于它跟踪页面在最近K次访问的历史可以避免全表扫描时偶发访问的页面把真正高频的索引页挤出去这在混合负载下性能优势非常明显。这里补充一句很多参赛队伍会把精力全放在索引和查询优化上认为缓冲池就是“缓存一下而已”。但实际上缓冲池命中率往往决定了数据库90%以上的读性能。一个设计良好的缓冲池应该把热数据稳稳放在内存里同时还要有预读机制避免顺序扫描时频繁卡在磁盘I/O上。这份作品预读做得也很讲究它不是简单地每次多读几个页而是根据查询计划里的访问模式点查还是范围扫描动态调整预读长度这是我复现源码时觉得非常惊艳的地方。2.2 索引结构选型B树 vs LSM-Tree索引是数据库加速查询的核心工具而索引结构的选择本质上是在读性能、写性能和空间占用之间做权衡。参赛作品里绝大部分队伍都会选择B树这份作品也不例外。原因很简单B树在点查询和范围查询上都能保持稳定的对数复杂度而且天然支持按序扫描非常适合比赛常见的TPC-H风格查询和点查压力测试。相比之下LSM-Tree写入性能更强但读放大和空间放大的问题更难控制。在比赛这种有限时间内把一个LSM-Tree的压缩策略调好难度远大于把B树调通。所以这个团队选择B树作为主索引结构是成熟且理性的工程决策。不过实现B树也有大量细节。最有意思的是它的叶子节点和内部节点都采用了“预分配空闲槽位”的方式并不等插入时再临时申请内存。这个设计可以减少节点分裂时的内存分配次数也方便实现并发控制。它的节点分裂策略也不是简单的“满一半就分裂”而是一种“延迟分裂”思想当节点快满但兄弟节点还有空间时优先向兄弟节点借位只有整组节点都满了才分裂。这个优化让B树的写放大减少了不少也让我想起Berkeley DB里的一些经典技巧。2.3 数据字典与系统表设计存储引擎之上还有一个容易被忽视的部分数据字典。数据字典负责管理系统中的元数据包括所有数据库、表、索引、列信息、约束、权限等。作品里把这些元数据同样用B树存储在系统表空间里而不是在内存里维护一份简单的结构体。这样做有一个天大的好处系统重启后不必再去解析一堆配置文件直接可以从系统表恢复出整个集群的元数据状态。数据字典的访问必须走统一的事务流程这样任何一条元数据的创建和修改都可以回滚。这一点在支持“CREATE TABLE ... 失败后自动清理”等场景时至关重要。我看到不少队伍在实现多表连接时因为数据字典里缺少列级统计信息导致优化器只能靠猜来设计连接顺序最终性能惨不忍睹。而这个作品从第一天起就把统计信息同步更新到数据字典中为后续的查询优化打好了底子。3. 查询处理链路让SQL从字符串变成高性能执行计划3.1 词法语法分析与语义检查SQL是数据库系统对外提供的唯一接口因此系统的第一站就是SQL解析器。这份作品用Lex与Yacc生成词法与语法分析器把SQL语句解析为抽象语法树AST然后通过语义分析检查表名、列名、函数是否存在数据类型是否匹配权限是否足够。这一步看似基础但涉及非常多的边界情况比如连续嵌套的子查询、带有复杂谓词的JOIN条件处理。很多队伍在语法分析阶段就崩溃因为SQL语法极其繁杂光是SELECT子句就能组合出无数种形式。但作品的做法很聪明在AST生成后立刻进行一次“规范化”把各种SQL等价写法统一成一个内部表示。比如把WHERE a 1 AND b 2转换成统一的 conjuctive normal form合取范式把复杂的子查询尝试转换为等价的JOIN。这样后续优化器和执行器的处理逻辑就变得非常简单不需要为一个SQL的特定写法单独写分支。3.2 优化器的关键决策连接顺序与索引选择得到语法树之后真正决定查询性能的核心组件是查询优化器。这个作品构建了一个基于代价的优化器并且采用了动态规划的方式来枚举多表连接的顺序。大赛测试集里常见的查询大多是3到6张表的连接如果直接枚举所有排列数量会爆炸式增长。作品通过“切割”策略把表集合分成左右两个子集递归考虑同时使用分支定界砍掉明显代价过高的子树。代价估算里最重要的是基数估计也就是每个算子会产生多少行数据。作品在系统表里保存了每个表的总行数、每列的不同值数量、最大值和最小值并且利用这些信息估算选择率。对于没有统计信息的列它会采用默认的选择率0.1并且通过运行时统计自动修正。这个“从默认值到自查优化”的过程让我想起PostgreSQL里analyze命令的思路只不过作品把它压缩到了一个更简化的模型里。至于索引选择作品会把可用的索引与查询谓词做匹配优先选择能缩小扫描范围的索引路径。它还实现了索引条件与过滤条件的分离例如WHERE age 20 AND name Tom如果age上有索引那么age 20作为索引范围条件name Tom则作为回表后的过滤条件。这是一件很细节但很见功力的事因为很多参赛队伍只会做全表扫描一旦遇到范围查询就只能硬扛。3.3 执行器算子设计与火山模型执行器是查询计划的执行者作品采用的是经典的“火山模型”Volcano Model每一个算子都实现next()接口通过迭代器的方式一层层向上返回数据。这种模型胜在代码结构清晰每个算子可以独立测试也方便增加新的算子类型。它支持了SeqScan、IndexScan、NestLoopJoin、HashJoin、Aggregation、Sort等多种算子。工程实现里HashJoin算子特别讲究。作品没有选择最基本的“把左边全部建成哈希表再探测右边”而是实现了“分块哈希连接”Grace HashJoin当哈希表内存不足时把左右两张表按哈希值分成多个桶分别写回临时文件再对每个分桶递归地做哈希连接。这让系统在处理大表连接时不会因内存溢出而崩掉同时它采用了“右侧建表左侧探测”的策略即把小表作为建表侧把哈希表的内存消耗压到最低。聚合算子的实现也值得一提。作品区分了无GROUP BY的聚合和带GROUP BY的聚合。对于后者它在聚合时利用了哈希表分组键作为哈希键同时维护一个“内存滑窗”用于在GROUP BY字段有顺序时优化排序导致的开销。这种实现让我看到团队对执行细节的较真程度。4. 并发控制与恢复机制正确性比性能更敏感4.1 基于锁的并发控制死锁检测到怎么处理任何数据库管理系统只要宣称支持多用户访问就必须处理并发冲突。作品采用的是两阶段锁协议即事务在访问数据前必须获得相应粒度的锁并且一旦事务释放一个锁就不再请求新的锁。锁粒度覆盖了表级锁和行级锁对于单点操作如主键查询会自动升级为行级锁而对于全表扫描则使用表级锁避免需要同时持有太多行锁造成锁表空间膨胀。死锁是并发控制的经典难题。作品用了超时检测加等待图检测的双重办法先看一个事务等待锁的时间是否超过阈值如果超时就判定为疑似死锁如果同一时刻多个事务互相等待则在等待图中做环检测一旦检测到环就选择代价最小的那个事务中止回滚。这里面“代价最小”的定义很实际综合了事务已执行时间、持有的锁数量以及被其他事务等待的数量。这个设计在比赛演示环节里表现得很亮眼即使评审故意制造了多个高并发事务交叉更新同一批数据系统也能在几十毫秒内自动解除死锁而不是直接卡死。4.2 日志机制与崩溃恢复WAL的核心思路崩溃恢复是数据库系统稳定性的最后一道防线。作品的恢复机制严格遵循Write-Ahead LoggingWAL原则任何数据页的修改都必须先写入日志再更新缓冲池里的页面。日志记录采用物理日志和逻辑日志混合的方式物理日志记录操作的是哪个页面和页面内的具体偏移量变化逻辑日志则记录的是“更新前值”和“更新后值”用于回滚时做UNDO。恢复流程分为三个阶段分析阶段、重做阶段和回滚阶段。启动时系统先扫描日志从最后一个检查点开始分析出哪些事务在崩溃时已经提交、哪些还在活跃中。然后重做所有已提交事务的日志记录把数据页恢复到崩溃前的状态对于未提交事务则利用UNDO日志逐条回滚撤销已经写到磁盘上的影响。这个流程虽然说起来简单但实现时会有大量细节比如日志的LSN号如何递增、如何与页面的LSN对比来判断是否需要重做这些作品都处理得相当严谨。4.3 MVCC作为加分项在锁并发之外作品还实现了基于多版本并发控制MVCC的快照隔离。它给每个事务分配了一个递增的事务ID并且在每一行数据上保存创建该行版本的事务ID和删除该行版本的事务ID。读操作根据当前事务的快照条件判断哪些版本可见写操作则生成新版本而不是原地覆盖。有了MVCC系统可以把“读写阻塞”降到最低。一个事务在读的时候另一个事务写同一行不会发生冲突因为读事务看到的是快照版本。这个设计在比赛的高级功能评测里是很大的加分点而且在演示活跃的Web应用场景时系统的并发吞吐量明显高于那些只靠锁的系统。实现MVCC最麻烦的是垃圾回收。如果一直保留旧版本存储空间会无限制增长。作品实现了一种类似PostgreSQL的Vacuum机制在后台线程中定期扫描没有活跃事务引用的旧版本并物理回收。它还特别处理了一个边界条件当某个事务长时间不提交时比该事务ID更大的所有新版数据都不能被回收所以它会把这种“长事务”的ID记录到系统表中避免后台清理线程误删。这一点很多工程经验不足的队伍完全想不到。5. 从比赛源码里提炼的工程经验想拿高分得这么干5.1 性能测试里的“不公平优势”如何在白盒测试里稳压对手比赛现场性能测试有一个和真实场景不同的地方评测环境通常是可控的数据集是预先准备好的查询负载也是固定的。这意味着可以针对评测特征做出一些“看似取巧但其实合理”的优化而这些优化在通用场景下未必适用但在这里能带来巨大收益。这份作品性能最亮眼的几个优化都围绕“索引选择”和“执行计划缓存”展开。它把同一查询文本的执行计划缓存起来第二次执行时直接复用省去了解析和优化的时间。同时它根据评测表的统计信息为每个表预建了多个复合索引当查询里的WHERE条件命中多个索引时优化器会尝试Bitmap Index Scan的方式将多个索引的结果集做位图与或运算大幅降低回表次数。这些特性加起来让它在评测中的查询平均响应时间比第二名快了将近一倍。5.2 团队协作与模块拆分的智慧从源码的目录结构看这个团队的工程组织能力也相当强。整个项目分为catalog、storage、executor、optimizer、transaction、recovery六个核心模块模块之间通过清晰的头文件接口通信没有循环依赖。这意味着每个模块可以独立测试、独立调试后期集成的成本被压缩得很低。我尤其欣赏他们对“错误处理”的规范。几乎每个函数都会返回统一的自定义错误码所有错误码都在一个中心头文件里登记并附有说明文档。这使得在遇到崩溃时可以迅速定位到具体模块和错误原因而不是像很多比赛项目一样靠到处打印日志来猜问题。良好的模块边界和错误处理是6个人团队能在一学期里交出这么完整作品的重要前提。5.3 我踩过的坑与建议如果我是一个明年要参加这个比赛的选手我会从这份作品里吸取三个教训。第一不要从索引开始。很多队伍一上来就写B树而把文件管理和数据页结构抛在脑后这是本末倒置。没有可靠的页管理和缓冲池再牛的索引也无法稳定工作。先把单表无索引的增删改查跑通再考虑加索引。第二一定要从第一天就支持事务。即使最简单的单线程系统也要把日志和恢复机制考虑进去。因为一旦项目后期再加入事务模块你会发现所有存储操作的接口都需要重新设计那才是灾难。第三性能压测要趁早。不要等到所有功能做完了再开始优化。作品团队每周都会跑一次TPC-H的简化测试集记录各项查询的响应时间用性能变化曲线来追踪每次代码改动的收益。这样既能防止性能回退也能让大家看到进展保持动力。我在实际接触数据库内核开发后越来越感受到一个道理数据库管理系统设计赛真正奖励的不是那些会背概念的人而是能在有限时间内做出正确工程取舍的人。这份一等奖作品的源码包在我看来就是一本最好的教材它告诉后来者什么才叫“把系统做出来、做稳、做快”。本文还有配套的精品资源点击获取
![[光学原理与应用-521]：对光的错误理解与纠偏](http://pic.xiahunao.cn/yaotu/[光学原理与应用-521]：对光的错误理解与纠偏)
