数据库内核实践：实现LRU缓冲池与并发控制全复盘

某高校软件学院数据库系统实验四，终于在我把一个周末加两晚搭进去之后提交了。这轮实验和前面三次完全不是一个画风：前几轮还在调SQL、画ER图、写存储过程，到了第四次，需求文档里明明白白写着「实现一个支持LRU置换与并发访问的缓冲池管理器」。折腾完我才觉得，数据库系统这门课真正“扎进内核”的感觉就是从这次开始的。这篇帖子想把实验从需求拆解、底层存储格式设计、核心模块实现到压测翻车的完整链路复盘一遍，给正在做类似实验的同学一份可以抄作业的参考，也顺便聊聊那些课本里不会写、但实际写代码时一定会遇到的坑。

1. 需求拆解：从“实现一个缓冲池管理器”到“页、帧、置换策略”

1.1 前三次实验做了什么，第四次为什么画风突变

我们学院的数据库系统课程实验是递进的：实验一让所有人熟悉SQL，包括多表连接、子查询、视图和触发器；实验二是数据库设计，做一个完整的ER模型再加范式验证；实验三开始写应用，用某种语言接数据库做一个简单的信息管理系统。到实验四，需求文档直接给了几个接口签名和一段英文思路描述，要求我们自己动手模拟数据库内核中最核心的存储管理模块。

这个跳跃一开始让人很不适应。前三次实验的思考单位是“表”“记录”“查询”，而第四次实验的思考单位变成了“页”“帧”“磁盘I/O”。我刚开始看需求文档的时候甚至有点懵：为什么不让继续写SQL？数据库课不是已经快结束了吗？后来才明白，前三轮是教你怎么用数据库，第四轮是逼你回答一个更底层的问题——数据库凭什么能把数据稳定高效地读出来。

1.2 需求文档里到底要求了什么

这次所谓“缓冲池管理器”需求可以拆成四块：

• 底层存储：把数据组织成固定大小的页（Page），页在磁盘文件中连续存放，页号就是文件中的偏移量。
• 缓冲池核心：用一块有限的内存（若干帧）缓存磁盘页，对外提供FetchPage和UnpinPage两个主接口。
• 置换策略：当缓冲池满了需要淘汰某个页时，用LRU策略选择被踢出的页；如果该页被修改过，要先写回磁盘再淘汰。
• 并发安全：允许多个线程同时访问数据库，要求缓冲池内部元数据、页访问都要加合适的锁，不能出现数据竞争和死锁。

需求文档没有要求实现B+树或者SQL解析，只要能把“读页、改页、淘汰页、刷脏页”这一条主链路跑通即可。但恰恰是这条主链路，决定了后面加索引、加事务恢复时整个存储引擎的行为习惯。

1.3 为什么选C++而不是Python

实验要求提交的代码可以自选语言，但我们最后统一用了C++17。原因很现实：模拟页和帧需要直接操作固定大小的字节数组，需要在内存中伪造一个“磁盘文件”，还要精细控制指针引用和生命周期，这些在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::list<int> lru_list_; std::unordered_map<int, std::list<int>::iterator> lru_map_;

每次FetchPage命中时，先从哈希表找到链表迭代器，把对应节点splice到链表尾部。每次淘汰时，直接从链表头部取节点，如果该页脏了就先写回磁盘，再删除哈希表项、清空对应的帧。

这里有个初学者特别容易踩的坑：splice之后，原来的迭代器可能仍然指向同一个节点，但如果直接删除节点再重建，就会造成迭代器失效。正确做法是只用lru_map_保存的迭代器，不另外缓存迭代器副本。我在第一次实现时图省事，用一个auto it = lru_map_[page_id]，结果后续代码又把it存在另一个结构体里，等到淘汰时发现迭代器已经失效，整个LRU链表乱成一锅粥。

3.3 Pin计数：不是所有帧都能被淘汰

如果LRU只看链表头部就决定淘汰哪个页，那么在高并发场景下会出大问题：一个页可能正被某个线程读取，它的指针还在外面飘着，缓冲池却把它从帧里踢出去，帧内存被另一个页覆盖。这会导致正在使用的线程突然读到完全不同的数据。

因此每个帧必须维护一个pin_count。FetchPage返回时pin_count++，UnpinPage时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_count=1，线程B也FetchPage(页1)使pin_count=2；线程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_set<int> pages_held_。FetchPage成功后加入集合，UnpinPage时从集合中移除，只有集合中确实有这个页时才允许减少全局pin_count。这样即使两个线程同时UnpinPage，每个线程也只能触发一次减一，不会把别人的引用减掉。

修复之后，同一份并发压测跑了20轮，结果全部稳定一致。我又用AddressSanitizer跑了一遍，确认没有内存越界和哈希表迭代器失效。最终我们记录了一个对比结果：

这个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时比任何调试器都管用。

数据库系统这门课的实验四，是我第一次意识到“读代码”和“写代码”之间隔着一条巨大的鸿沟。单单是缓存一页数据看似简单，背后却藏着置换策略、引用计数、并发控制、脏页管理这么多个维度的工程决策。做完之后再去用数据库，感觉完全不一样了——这种体感，大概只有自己动手模拟一遍内核模块才能获得。