某高校软件学院数据库系统实验四终于在我把一个周末加两晚搭进去之后提交了。这轮实验和前面三次完全不是一个画风前几轮还在调SQL、画ER图、写存储过程到了第四次需求文档里明明白白写着「实现一个支持LRU置换与并发访问的缓冲池管理器」。折腾完我才觉得数据库系统这门课真正“扎进内核”的感觉就是从这次开始的。这篇帖子想把实验从需求拆解、底层存储格式设计、核心模块实现到压测翻车的完整链路复盘一遍给正在做类似实验的同学一份可以抄作业的参考也顺便聊聊那些课本里不会写、但实际写代码时一定会遇到的坑。1. 需求拆解从“实现一个缓冲池管理器”到“页、帧、置换策略”1.1 前三次实验做了什么第四次为什么画风突变我们学院的数据库系统课程实验是递进的实验一让所有人熟悉SQL包括多表连接、子查询、视图和触发器实验二是数据库设计做一个完整的ER模型再加范式验证实验三开始写应用用某种语言接数据库做一个简单的信息管理系统。到实验四需求文档直接给了几个接口签名和一段英文思路描述要求我们自己动手模拟数据库内核中最核心的存储管理模块。这个跳跃一开始让人很不适应。前三次实验的思考单位是“表”“记录”“查询”而第四次实验的思考单位变成了“页”“帧”“磁盘I/O”。我刚开始看需求文档的时候甚至有点懵为什么不让继续写SQL数据库课不是已经快结束了吗后来才明白前三轮是教你怎么用数据库第四轮是逼你回答一个更底层的问题——数据库凭什么能把数据稳定高效地读出来。1.2 需求文档里到底要求了什么这次所谓“缓冲池管理器”需求可以拆成四块底层存储把数据组织成固定大小的页Page页在磁盘文件中连续存放页号就是文件中的偏移量。缓冲池核心用一块有限的内存若干帧缓存磁盘页对外提供FetchPage和UnpinPage两个主接口。置换策略当缓冲池满了需要淘汰某个页时用LRU策略选择被踢出的页如果该页被修改过要先写回磁盘再淘汰。并发安全允许多个线程同时访问数据库要求缓冲池内部元数据、页访问都要加合适的锁不能出现数据竞争和死锁。需求文档没有要求实现B树或者SQL解析只要能把“读页、改页、淘汰页、刷脏页”这一条主链路跑通即可。但恰恰是这条主链路决定了后面加索引、加事务恢复时整个存储引擎的行为习惯。1.3 为什么选C而不是Python实验要求提交的代码可以自选语言但我们最后统一用了C17。原因很现实模拟页和帧需要直接操作固定大小的字节数组需要在内存中伪造一个“磁盘文件”还要精细控制指针引用和生命周期这些在C里都是顺手的操作。Python虽然写起来快但模拟磁盘I/O时要么用很大的bytearray要么得反复做bytes转struct代码会变得极其别扭而且性能测试时GIL还会干扰并发结果。当然用C语言也行但标准库缺少容器LRU队列和哈希表都要自己撸开发效率会明显下降。C的std::list加std::unordered_map组合正好是教学版LRU最方便的实现方式。这里也有一个很重要的心态转变这个实验不是为了写一个高并发生产级数据库而是为了验证原理。所以目标是“结构清晰、正确性优先”而不是盲目炫技。2. 底层存储设计页、槽位和记录映射的那些细节2.1 为什么页要设计成8KB在动手写LRU之前先得把“页”这个东西定义清楚。我们最终把单页大小定为8KB也就是8192字节。这个数字不是随便拍的机械磁盘的传统扇区是512字节文件系统块通常是4KB数据库页设置成4KB或8KB都是常见选择。页太小一次磁盘I/O能带回来的数据有限扫描效率低页太大内存浪费和随机写放大又会变严重。8KB是教学实验里最不容易出错的取值既足够容纳多条记录又不会让测试文件体积失控。页在磁盘文件里的组织方式是最简单的一种第0页是元数据页第1页开始每8192字节算一页数据页号n对应的文件偏移就是n * 8192。这样只要知道页号就能用pread精确读到对应内容。实验里我们并没有真的操作机械硬盘而是先创建一个二进制文件作为“模拟磁盘”每次FetchPage未命中时从这个文件读8192字节进内存帧淘汰时如果帧是脏的再把这8192字节写回去。这个简化足够还原磁盘I/O的语义也能让命中率测试有实际意义。2.2 槽位数组定长记录也不是随便放接下来要设计页里的记录布局。我们模拟的表是一张很简单的成绩表学号、姓名、院系、课程名、成绩。为了让计算方便最终每条记录固定占64字节。名字字段我们强行扩到24字节并按UTF-8存中文为了防止溢出另外加了16字节的预留在末尾。这样一页8192字节减去页头占用的16字节剩下8176字节刚好可以放127条记录还有一部分剩余空间。如果只是顺序往页里塞记录删除操作就会很麻烦删掉中间的记录后后面的记录要不要往前挪挪了之后旧指针全部失效。所以我们在页头里维护了一个槽位数组。这个数组记录每个槽位对应记录在页内的字节偏移槽位本身也占用页空间。删除记录时只需要把槽位标记为空并加入空闲槽链插入新记录时优先复用空闲槽而不是追加到页尾。槽位数组的具体布局可以做成定长数组也可以做成链表。我们采用了一个非常简化的方案页头用一个16字节的结构体包含页号、已用槽位数、空闲槽链表头偏移。后面的8176字节按64字节一份划分成127个物理槽位再用一个等长的字节位数组标记每个槽是否占用。访问记录时先根据行号算出物理槽位读到位图检查占用再从对应偏移取64字节。这套设计虽然不像真实数据库那样紧凑但胜在逻辑清晰调试时也很容易用hexdump对照。2.3 元数据页表从哪里来一个缓冲池管理器不能只管一堆无意义的页它至少要知道“当前这个数据文件有哪些页哪些页属于哪张表”。我们利用第0页做元数据页里面记录了表名、行数、总页数和一个简单的页号分配位图。新建一页时从位图里找一个空闲页号分配出去删除页时把位图对应位置置0。这里没有做复杂的表空间和文件组概念因为实验重点在缓冲替换算法不在字典系统。这个设计直接导致了一个必须小心的点元数据页本身也要走缓冲池。几乎所有同学都会在测试时反复刷元数据页结果它被LRU淘汰掉然后新一轮试验找不到总页数。更常规的做法是把元数据页设置为“始终驻留”的页或者给它一个极高的访问频率让LRU永远不会把它踢出去。我们在实验里也做了这个特殊化处理把页0标记为不可淘汰帧这就避免了最蠢的启动失败问题。3. LRU置换与脏页写回缓冲池核心模块的关键决策3.1 接口设计先想清楚调用方怎么用缓冲池对外接口我们最终定义成下面几个函数class BufferPoolManager { public: Page* FetchPage(int page_id); Page* NewPage(int* page_id); bool UnpinPage(int page_id, bool is_dirty); bool FlushPage(int page_id); bool FlushAllPages(); private: Page* FindVictim(); };这里最关键的是UnpinPage。一开始我天真地以为FetchPage读完就完了直到写代码才发现缓冲池必须知道“这个页现在还有没有人用”。FetchPage返回的Page指针相当于一把钥匙调用方拿到后可以读也可以改用完必须告诉缓冲池“我不用了”否则缓冲池永远不能淘汰这个页。is_dirty参数则表示这次使用期间是否修改了数据只有修改过的页在淘汰时才需要写回磁盘。如果调用方忘记UnpinPage缓冲池很快就会被占满后续FetchPage全部失败如果调用方在未修改的情况下也传了true就会导致大量无意义的磁盘写回。这个接口设计虽然只有四五个函数但它直接把“用户”和“缓冲区管理”的职责边界划清楚了用户不用关心页在内存还是磁盘缓冲池也不用关心用户拿这个页去做了什么操作。3.2 LRU经典实现双向链表加哈希表LRU最经典的教学实现就是用std::list保存页的访问顺序链表头部是最久未使用尾部是最近使用再用std::unordered_map保存页号到链表节点的映射保证查找和移动到尾部都是O(1)复杂度。std::listint lru_list_; std::unordered_mapint, std::listint::iterator lru_map_;每次FetchPage命中时先从哈希表找到链表迭代器把对应节点splice到链表尾部。每次淘汰时直接从链表头部取节点如果该页脏了就先写回磁盘再删除哈希表项、清空对应的帧。这里有个初学者特别容易踩的坑splice之后原来的迭代器可能仍然指向同一个节点但如果直接删除节点再重建就会造成迭代器失效。正确做法是只用lru_map_保存的迭代器不另外缓存迭代器副本。我在第一次实现时图省事用一个auto it lru_map_[page_id]结果后续代码又把it存在另一个结构体里等到淘汰时发现迭代器已经失效整个LRU链表乱成一锅粥。3.3 Pin计数不是所有帧都能被淘汰如果LRU只看链表头部就决定淘汰哪个页那么在高并发场景下会出大问题一个页可能正被某个线程读取它的指针还在外面飘着缓冲池却把它从帧里踢出去帧内存被另一个页覆盖。这会导致正在使用的线程突然读到完全不同的数据。因此每个帧必须维护一个pin_count。FetchPage返回时pin_countUnpinPage时pin_count--。LRU淘汰时需要从链表头部向后找到一个pin_count 0的页而不是直接拿第一个。我们最终写的FindVictim逻辑大致是Page* BufferPoolManager::FindVictim() { for (auto it lru_list_.begin(); it ! lru_list_.end(); it) { Page* frame pages_[*it]; if (frame-GetPinCount() 0) { if (frame-IsDirty()) { DiskManager::WritePage(frame-GetPageId(), frame-GetData()); frame-SetDirty(false); } lru_list_.erase(it); lru_map_.erase(*it); return frame; } } return nullptr; }如果循环一圈都没有pin_count 0的帧说明当前所有缓冲帧都被占用这时候返回空指针让上层报错而不是随便挑一个帧强杀。真实数据库里遇到这种情况会等待或者扩大缓冲池但教学实验里直接报告“缓冲区不足”是更安全的行为。3.4 脏页写回什么时候刷什么时候不刷脏页写回是整个实验里最容易“性能翻车”的地方。一个页被修改后如果没有立刻写回磁盘那么掉电时数据会丢如果每次都立刻写回那么缓冲池的存在意义就减少了一半。实验要求我们实现的是no-steal no-force风格的简化策略只有在淘汰脏页或显式调用FlushPage时才写回平时允许脏页继续呆在内存里。这个策略模拟了数据库恢复中的基本权衡。注意在UnpinPage时is_dirty参数是按本次访问是否修改来传的。如果一个页被线程A修改写回磁盘后又被线程B读取并Unpin(false)它仍然是脏的因为内存和磁盘已经一致了不这里要小心如果写回后没有新修改其实应该把dirty标记清掉。我们在实现里把“是否写回”和“是否脏”分开每次淘汰写回后立刻清掉dirty标记后续Unpin(false)则不会重新置脏。但是有一种常见错误UnpinPage时无条件用is_dirty || old_dirty合并标记看起来更“安全”结果会让已经写回的页一直保持脏状态导致LRU每次淘汰它时都要重复写盘。这个bug我用两个线程压测时才暴露出来I/O次数比预期高了快一倍。4. 并发访问接入锁粒度、死锁检测与隔离级别取舍4.1 全局锁与页锁先分清锁保护的是什么需求文档要求支持并发访问但并发的粒度很讲究。最省事的实现是整个缓冲池一把大锁所有线程进入FetchPage后串行执行。这样正确性几乎不会有问题但压测时吞吐上不去因为命中Cached页后的读取操作也被锁挡住了。我们把锁分成两层一层是全局缓冲池元数据锁只保护哈希表、LRU链表、空闲帧链表这些结构另一层是页数据锁每个帧自带一个读写锁。FetchPage的流程变成加全局锁查缓冲池是否命中如果命中给对应页的pin_count加一然后释放全局锁如果未命中选择一个受害者帧可能写回脏页从磁盘读入目标页更新哈希表和LRU链表pin_count加一释放全局锁。页数据的读写锁则在调用方拿到Page指针之后、访问Page内数据之前加。这样两个线程可以同时读同一页写线程之间仍然互斥。缓冲池元数据的保护和页内容的保护被彻底分开并发度比一把大锁高出一个量级。4.2 锁表与死锁检测不检测也能跑但会死给你看多线程访问多页时很容易出现经典死锁事务T1持有页1的锁等待页2事务T2持有页2的锁等待页1。两个事务互相等待如果不干预整个程序就会卡死。实验要求里专门提到了死锁检测不能只用超时解决。我们实现了一个简化版锁表维护每个页当前持锁事务的位图以及每个事务等待的页集合。每次某个事务申请页锁失败时先把这条等待边加入等待图然后用DFS检测图中是否存在环。如果发现环就选择一个回滚代价最小的事务通常是已经在等待列表里待得最久的那个杀死它并释放它持有的所有锁。这个逻辑听上去复杂但代码量其实不大因为事务数量很少图搜索开销可以忽略不计。另一个更实用的规避策略是在事务启动时先收集本事务要访问的所有页号排序后按页号顺序加锁。这种全局顺序加锁能从源头消除绝大多数死锁。我们在提交前把两种方案都写进文档里死锁检测作为兜底策略顺序加锁作为默认策略最终压测时死锁次数是零。4.3 隔离级别实验里该做到哪一步才算达标真实数据库有读未提交、读已提交、可重复读、可串行化四个隔离级别。如果只是做一个缓冲池管理器严格来说不应该绑定事务的隔离级别但并发压测会逼你回答一个问题多个线程同时读同一个页、写同一个页能不能读到中间状态我们选择了“可重复读”这个折中方案读页时加共享锁写页时加排他锁事务结束后才释放所有锁而不是读完立即释放。这样保证一个事务内多次读取同一页结果一致。这其实是在没有真正实现undo日志的情况下能做到的最强隔离级别。如果要做到可串行化还需要对顺序扫描时的谓词加锁或做冲突序列化课时内基本做不完。压测时我们写了三类检查第一类所有线程对全表求和多次运行结果必须一致第二类两个线程同时对一个范围的页做累加累加结果要等于单线程基准结果第三类故意设一个低概率的交叉读写场景看是否出现两个线程读到矛盾的数据。第三类问题最终帮助我们暴露了下面要说的那个严重的pin_count bug。5. 压测翻车实录一次“数据被覆盖”从现象到根因的完整排查5.1 现象多线程压测时出现莫名的数据错乱一切模块写完、单线程测试通过之后我开始上压力测试。测试场景很简单用4个线程并发读取同一张含有2000页的数据表每个线程随机访问5000次最后把读到的记录累加多次运行对比结果。第一次跑就出问题了结果不稳定有时多几十有时少几百。更诡异的是我在代码里加了校验检查每次读取的记录是否属于预期页号范围结果有一轮竟然从页A读出了页B的内容。这个现象如果发生在真实数据库里就是典型的“数据串页”属于非常严重的存储一致性bug。因为哈希表、LRU链表、页数据整个链路都是自己刚写的第一反应是某个地方发生了越界写把帧内存改掉了。我甚至怀疑是Page里那8192字节的数组定义在栈上被上层应用踩爆了。但查了很久栈和堆都没有越界迹象。5.2 定位过程从睡眠日志到pin_count泄露排查第一步把每一个FetchPage和UnpinPage的关键动作都加上日志记录线程ID、页号、操作前后pin_count。日志打到文件后发现一个规律出错前总是有一个页的pin_count从2直接跳到0而中间另一个线程还在访问它。也就是说UnpinPage被某线程调用后把pin_count减到了0但页面上还挂着一个正在使用它的线程。问题出在我们对pin_count的语义理解太粗糙。我们用单一的整数计数表示“有多少个线程正在使用这个页”但当一个线程在释放页的时候它并不知道其他线程是否也在使用这个页。举一个具体场景线程AFetchPage(页1)拿到pin_count1线程B也FetchPage(页1)使pin_count2线程B先结束调用UnpinPage(false)把计数变成1线程A随后结束调用UnpinPage(false)把计数变成0。到这里看起来没问题。但坏就坏在线程B在UnpinPage(页1)之后又立刻发起了一个新的FetchPage(页1)——因为页还在缓冲池里FetchPage会直接把pin_count从1加到2。如果这个新的FetchPage发生在线程A的UnpinPage之前计数先变成2再被线程A减回1逻辑还勉强能维持可一旦顺序反了计数就会变成1而线程B认为自己已经拿到了页面引用但全局计数已经不允许它继续持有这个引用——此时如果LRU选到这个页发现pin_count为0就把它淘汰线程B手里拿到的Page指针瞬间指向了另一个页。理解这个根因之后我调整了设计不再让缓冲池替调用方管理pin_count而是让每个事务线程自己维护已获取页面的引用列表。UnpinPage只负责把当前事务的持有关系解除并把传入的is_dirty合并到页的全局脏标记中。页的全局可用状态由“当前持有该页的事务数量”决定而不是由一个受并发交错影响的整数决定。5.3 修复与回归验证具体修改是给每个事务增加一个std::unordered_setint pages_held_。FetchPage成功后加入集合UnpinPage时从集合中移除只有集合中确实有这个页时才允许减少全局pin_count。这样即使两个线程同时UnpinPage每个线程也只能触发一次减一不会把别人的引用减掉。修复之后同一份并发压测跑了20轮结果全部稳定一致。我又用AddressSanitizer跑了一遍确认没有内存越界和哈希表迭代器失效。最终我们记录了一个对比结果检查项修复前修复后求和一致性4线程x5000次失败结果偏差不定20轮全部一致并发串页现象偶发未复现死锁发生次数6次依赖检测恢复0次平均命中率随机访问无明显变化无明显变化这个bug给我最大的教训是数据库系统的并发bug不一定是锁加少了更可能是“资源引用计数”的语义没有在并发上下文中校准。锁只解决互斥解决不了生命周期管理二者必须合并设计。6. 做完整轮实验后我对缓存和事务的几个新认识6.1 缓冲池缓存才是数据库的“内存”真相以前我一直以为数据库的“内存”是指查询结果缓存做完这个实验才知道真正决定数据库能不能扛住高并发的是页面缓冲池。用户发的每一条SQL最终都会被翻译成访问某些页面的请求能不能在缓冲池命中直接决定了这条SQL是微妙级还是毫秒级。哪怕索引建得再好如果缓冲池太小、LRU频繁踢出热页磁盘I/O也会迅速拖垮整个系统。这让我彻底理解了为什么真实数据库的配置项里缓冲池大小永远排在第一位也理解了为什么DBA宁可减少并发连接数也要留足Buffer Pool内存。6.2 隔离级别不是配置项而是实现细节在实验里自己亲手实现了一次加锁和死锁检测之后我才意识到SET TRANSACTION ISOLATION LEVEL READ COMMITTED这种SQL语句背后有多少事要做。隔离级别不是数据库随意提供的开关而是加锁时机、锁释放时机、版本链保留策略三者共同作用的结果。真实数据库还要处理幻读、不可重复读、MVCC快照等远比我们的模拟复杂。但理解了Page锁和事务持有的关系再去读那些配置文件里的所谓“隔离级别”至少不会被参数吓住了。6.3 给后来者的一句话经验如果现在让我重新做一遍这个实验我会把顺序调整成先写单线程版本并跑通正确性测试再引入pin_count生命周期管理最后才上并发锁。不要一开始就追求“高并发实现”并发正确性是建立在单线程模型完全正确的前提上的。另外日志和断言要早写特别是每次UnpinPage前后打印pin_count的调试日志在排查并发bug时比任何调试器都管用。数据库系统这门课的实验四是我第一次意识到“读代码”和“写代码”之间隔着一条巨大的鸿沟。单单是缓存一页数据看似简单背后却藏着置换策略、引用计数、并发控制、脏页管理这么多个维度的工程决策。做完之后再去用数据库感觉完全不一样了——这种体感大概只有自己动手模拟一遍内核模块才能获得。