如何避免预读失效和缓存污染
传统的 LRU 算法存在两个问题：
- 预读失效：导致缓存命中率下降
- 缓存污染：导致缓存命中率下降
Linux 系统通过改进 LRU 算法来避免预读失效和缓存污染。
Linux 操作系统的缓存
应用程序读取文件的数据时，会缓存在 Page Cache（页缓存）中。
传统 LRU 算法中的预读失效和缓存污染问题
预读机制
Linux 操作系统为基于 Page Cache 的读缓存机制提供预读机制，一个例子是：
- 应用程序只想读取磁盘上文件 A 的 offset 为 0-3kb 范围的数据，而磁盘的基本读写单位为 block(4kb)，所以操作系统至少会读取 0-4kb 的内容
- 但是操作系统出于空间局部性原理（靠近当前被访问数据的数据，在未来很大概率会被访问到），会选择将磁盘块中的 [4kb, 8kb), [8kb, 12kb), [12kb, 16kb) 都加载到内存，于是相当于额外申请了 3 个 page
但如果这些预先读取进来的页，并没有被访问，就会产生预读失效。如果这些预读数据一直不会被访问，使用传统的 LRU 算法就会产生一个问题：不会被访问的预读数据占用了 LRU 链表前排的位置，而在末尾却淘汰了热点数据，大大降低了缓存命中率。
为解决该问题，Linux 中实现了两个 LRU 链表：活跃 LRU 链表和非活跃 LRU 链表。
- 活跃 LRU 链表保存最近被访问的内存数据
- 非活跃 LRU 链表保存很少被访问的内存数据
这样，预读页不会直接加入到活跃 LRU 链表中，而是先加入到非活跃 LRU 链表中，被访问时，才加入到活跃 LRU 链表头部。
缓存污染
批量读取数据时，由于数据被访问，那么大量数据都会被加入到活跃 LRU 链表中，之前缓存的数据就全部被淘汰了，如果这些大量的数据在很长一段时间都不会被访问的话，那么整个活跃 LRU 链表就被污染了。
Linux 通过提高进入活跃 LRU 链表的门槛来解决缓存污染的问题，比如在内存页被访问第二次的时候，才将页从 inactive list 升级到 active list 中。