The LRU-K Page Replacement Algorithm For Database Disk Buffering

LRU

LRU 算法利用最近的访问时间来淘汰缓存，但是有个问题：它根据太少的信息来决定从缓冲区中删除哪个页面，将自己限制在最后引用的时间。具体来说，LRU 无法区分被引用频率相对较高的页面和被引用频率很低的页面，会导致系统浪费了大量的资源，将不经常引用的页面在缓冲区中保存了很长一段时间。

例子1

常用的页面，比如索引（如B树上的索引节点）容易被大量的叶子节点访问淘汰。

例子2

比如有页面[1, 1000]，其中1-10页面会反复访问。LRU管理的缓存大小有10个页面。执行以下访问顺序：

1. 按序访问1-10，miss；
2. 按序访问11-20，miss，加载到内存中并淘汰1-10；
3. 按序访问1-10，miss，加载到内存中并淘汰其他；
4. 按序访问21-30，miss，加载到内存中并淘汰1-10；
5. …

可以看到，重复访问的页面没有与仅访问一次的页面区分开，每次都需要重新载入缓存。很多数据库应用中也包括需要顺序扫描页面而导致常驻在缓存中的页面淘汰的情况。

LRU无法区分那些具有相对频繁引用的页面和那些引用极少的页面。文献中已提出了一些解决这个问题的方案。前述的解决方法可以归入以下两大类:

1. 划分不同的缓存池；
2. 查询优化器显式指定缓存的重用。

而在这两种类型之外，LRU-K提供了内部的，自适应的缓存淘汰算法。

LRU-K

LRU-K 效率的论证主要基于统计学，在概率上对于缓存的命中率上，LRU-K要高于LRU算法。k一般取值为2，太大会导致缓存难以被淘汰。