数据库缓冲池替换：LRU-K、2Q 与生产级扫描保护
内容提要
数据库缓冲池淘汰需兼顾pin、WAL顺序与访问语义。文章梳理LRU-K、2Q、CLOCK-Pro等抗扫描策略，并对比PostgreSQL 16的clock sweep加访问策略ring与InnoDB 8.0的midpoint insertion及old blocks time。实验表明，LRU在扫描后热点命中率降至58.65%，2Q与LRU-2可维持约80%，但需权衡命中路径开销与参数自适应。
延伸解读
数据库缓冲池替换的独特约束
数据库缓冲池替换并非简单的页面置换算法应用。文章指出，数据库页具有pin/unpin语义，脏页必须服从WAL顺序，访问还带有执行器语义（如点查、扫描）。这些约束使得替换器只能选择未pin的帧，且不能仅凭“冷热”决定淘汰。此外，命中路径的共享写入可能成为性能瓶颈。因此，缓冲池替换是一个带约束的在线缓存问题，需在命中率与并发开销间权衡。
抗扫描策略的核心思想
全表扫描会污染缓冲池，因为LRU赋予首次访问与热点页同等的晋升权。抗扫描策略如LRU-K、2Q、CLOCK-Pro的核心是区分“试用”与“保护”：第一次访问仅进入试用区，只有第二次访问或ghost命中才进入受保护区。例如，2Q使用A1in、A1out和Am三个队列，LRU-2记录最近K次访问时间。这些策略有效防止一次性扫描页挤走热点页，但需权衡元数据开销和参数自适应。
生产系统的实现差异与取舍
PostgreSQL 16采用clock sweep加访问策略ring，顺序扫描走小ring（如256 KiB），避免提升usage_count；InnoDB 8.0使用midpoint insertion，新页插入LRU的3/8位置，并设置old blocks time（默认1000ms）防止扫描页快速晋升。两者都体现了“试用区”思想，但实现不同：PG依赖执行器传入策略，InnoDB用单链表加时间窗口。这些设计在抗扫描和并发开销间取得平衡，但参数需根据负载调整。
实验揭示的命中率与开销权衡
在混合trace实验中，LRU和CLOCK在扫描后热点命中率降至58.65%，而LRU-2和2Q保持约80%。InnoDB midpoint总命中率略高但扫描后恢复低于2Q；PG clock-sweep介于两者之间。元数据操作数显示，LRU-2每次淘汰扫描缓冲池，开销远高；2Q、clock sweep和midpoint则保持较低开销。这表明高命中率可能伴随高维护成本，工程中需根据并发场景选择，不能仅看命中率。
Q&A
数据库缓冲池替换和操作系统的页面置换有什么本质区别？
数据库缓冲池替换需考虑四个额外约束：页面可被 pin，被 pin 的页不能淘汰；脏页必须服从 WAL 顺序，日志持久化后才能写回；访问有语义，顺序扫描、VACUUM、批量写入和 OLTP 点查可走不同策略；命中路径很热，每次命中都改全局 LRU 链表可能在高并发下造成锁热点。
LRU-K 算法如何避免全表扫描污染缓冲池？
LRU-K 记录每个页面最近 K 次独立访问的时间戳，用向后 K 距离（当前时间减去倒数第 K 次访问时间）作为淘汰依据。访问次数少于 K 的页面其距离视为无穷大，优先淘汰。这样只访问一次的全表扫描页不会挤掉已被多次访问的热点页。LRU-2 是常用特例，要求页面至少被独立访问两次才受保护。
2Q 算法是如何用三个队列近似 LRU-2 的？
2Q 使用三个队列：A1in 是驻留页的 FIFO 试用区，新页先进入；A1out 存放从 A1in 淘汰页面的 ghost 标识（仅 page id）；Am 是第二次访问后进入的 LRU 保护区。页面首次缺页进入 A1in，淘汰时只保留 id 到 A1out；若后续命中 A1out，则加载到 Am。这样用常数时间操作近似了 LRU-2 的“第二次访问才算热”原则。
PostgreSQL 16 的缓冲池替换是如何实现抗扫描的？
PostgreSQL 16 使用 clock sweep 算法，并配合访问策略 ring。clock sweep 扫描缓冲帧，淘汰 usage_count 为 0 的未 pin 页，否则减一。默认访问策略将 usage_count 上限设为 5，非默认策略只保证计数不为 0。对于大扫描，执行器传入 BufferAccessStrategy，使用小 ring（如 BAS_BULKREAD 为 256 KiB）反复复用少量缓冲帧，避免污染整个缓冲池。
InnoDB 8.0 的 midpoint insertion 策略是如何工作的？
InnoDB 8.0 将新读入的页面插入 LRU 链表离尾部 3/8 的位置（midpoint），下游 old 区域是优先淘汰区。参数 innodb_old_blocks_pct 控制 old 区域比例（默认 37%），innodb_old_blocks_time 设置时间窗口（默认 1000 毫秒），首次访问后在该时间内再次访问不会将页移到 new 端。只有超过时间窗口的再次访问才可能晋升到 new 区域。
在混合负载 trace 上，LRU、2Q 和 LRU-2 的扫描后热点命中率表现如何？
实验显示，LRU 在扫描后热点命中率降至 58.65%，而 2Q 和 LRU-2 分别保持在 79.15% 和 80.28%。LRU-2 总命中率最高（68.15%），但元数据操作数远高于其他策略（249.87 次/访问），2Q 仅 3.21 次/访问。PostgreSQL clock-sweep 和 InnoDB midpoint 的扫描后热点命中率分别为 76.95% 和 77.53%，介于朴素 CLOCK 与 2Q 之间。
选择缓冲池替换策略时，除了命中率还需要考虑哪些工程因素？
需考虑三点：命中路径的共享写入，精确 LRU、ARC、LRU-K 的维护可能落在每次命中上，高并发下锁争用影响吞吐；扫描是否可识别，如 PostgreSQL 的 ring 依赖执行器传入策略，否则只能靠替换器猜测；参数与自适应没有免费午餐，2Q 的 Kin/Kout、InnoDB 的 old 区比例与时间窗口等依赖负载，论文结论不能直接推广。
