Skip to content

1. 预读失效和缓存污染⚓

传统的 LRU 算法存在这两个问题：

  • 预读失效导致缓存命中率下降
  • 缓存污染导致缓存命中率下降

Redis 的缓存淘汰算法是通过实现 LFU 算法来避免「缓存污染」而导致缓存命中率下降的问题（Redis 没有预读机制）。

MySQL 和 Linux 操作系统是通过改进 LRU 算法来避免「预读失效和缓存污染」而导致缓存命中率下降的问题。

1.1 传统 LRU⚓

LRU（Least recently used）算法：一般是用「链表」作为数据结构来实现的，链表头部的数据是最近使用的，而链表末尾的数据是最久没被使用的。那么，当空间不够了，就淘汰最久没被使用的节点，也就是链表末尾的数据，从而腾出内存空间。

因为 Linux 的 Page Cache 和 MySQL 的 Buffer Pool 缓存的基本数据单位都是页（Page）单位，所以后续以「页」名称代替「数据」。

传统的 LRU 算法的实现思路是这样的：

  • 当访问的页在内存里，就直接把该页对应的 LRU 链表节点移动到链表的头部。
  • 当访问的页不在内存里，除了要把该页放入到 LRU 链表的头部，还要淘汰 LRU 链表末尾的页。

存在的问题：

  • 预读失效导致缓存命中率下降；
  • 缓存污染导致缓存命中率下降；

1.2 预读失效⚓

1.2.1 预读机制⚓

预读机制就是在读取指定记录时，把后续的记录也一起读取出来。

Linux 操作系统为基于 Page Cache 的读缓存机制提供预读机制，一个例子是：

  • 应用程序只想读取磁盘上文件 A 的 offset 为 0-3KB 范围内的数据，由于磁盘的基本读写单位为 block（4KB），于是操作系统至少会读 0-4KB 的内容，这恰好可以在一个 page 中装下。
  • 但是操作系统出于空间局部性原理（靠近当前被访问数据的数据，在未来很大概率会被访问到），会选择将磁盘块 offset [4KB,8KB)、[8KB,12KB) 以及 [12KB,16KB) 都加载到内存，于是额外在内存中申请了 3 个 page；

这样下次读取 4KB 数据后面的数据的时候，就不用从磁盘读取了，直接在 Page Cache 即可命中数据。

因此，预读机制带来的好处就是减少了 磁盘 I/O 次数，提高系统磁盘 I/O 吞吐量。

MySQL Innodb 存储引擎的 Buffer Pool 同理。

1.2.2 预读失效⚓

如果这些被提前加载进来的页，并没有被访问，相当于这个预读工作是白做了，这个就是预读失效。

这样会导致不会被访问的预读页却占用了 LRU 链表前排的位置，而末尾淘汰的页，可能是热点数据，这样就大大降低了缓存命中率 。

1.2.3 如何避免⚓

不能因为害怕预读失效，而将预读机制去掉，大部分情况下，空间局部性原理还是成立的。

要避免预读失效带来影响，最好就是让预读页停留在内存里的时间要尽可能的短，让真正被访问的页才移动到 LRU 链表的头部，从而保证真正被读取的热数据留在内存里的时间尽可能长。

1.2.3.1 Linux 的改进方式⚓

Linux 操作系统实现两个了 LRU 链表：

  • active_list 活跃内存页链表，这里存放的是最近被访问过（活跃）的内存页；
  • inactive_list 不活跃内存页链表，这里存放的是很少被访问（非活跃）的内存页；

预读页就只需要加入到 inactive list 区域的头部，当页被真正访问的时候，才将页插入 active list 的头部。如果预读的页一直没有被访问，就会从 inactive list 移除，这样就不会影响 active list 中的热点数据。

即使编号为 20 的预读页一直不会被访问，它也没有占用到 active list 的位置，而且还会比 active list 中的页更早被淘汰出去。

如果 20 号页被预读后，立刻被访问了，那么就会将它插入到 active list 的头部， active list 末尾的页（5号），会被降级到 inactive list ，作为 inactive list 的头部，这个过程并不会有数据被淘汰。

1.2.3.2 MySQL 的改进方式⚓

MySQL 的 Innodb 存储引擎是在一个 LRU 链表上划分来 2 个区域，young 区域 和 old 区域。

参考 MySQL ->《Buffer Pool》->《MySQL 使用的 LRU 算法》 小节。

1.3 缓存污染⚓

缓存污染

1.3.1 缓存污染⚓

虽然 Linux（实现两个 LRU 链表）和 MySQL（划分两个区域）通过改进传统的 LRU 数据结构，避免了预读失效带来的影响。

但是如果还是使用只要数据被访问一次，就将数据加入到活跃 LRU 链表头部（或者 young 区域）这种方式的话，那么还存在缓存污染的问题。

当我们在批量读取数据的时候，由于数据被访问了一次，这些大量数据都会被加入到「活跃 LRU 链表」里，然后之前缓存在活跃 LRU 链表（或者 young 区域）里的热点数据全部都被淘汰了，如果这些大量的数据在很长一段时间都不会被访问的话，那么整个活跃 LRU 链表（或者 young 区域）就被污染了。

等这些热数据又被再次访问的时候，由于缓存未命中，就会产生大量的磁盘 I/O，系统性能就会急剧下降。

1.3.2 怎么避免⚓

只要提高进入到活跃 LRU 链表（或者 young 区域）的门槛，就能有效地保证活跃 LRU 链表（或者 young 区域）里的热点数据不会被轻易替换掉。

  • Linux 操作系统：在内存页被访问第二次的时候，才将页从 inactive list 升级到 active list 里。
  • MySQL Innodb：在内存页被访问第二次的时候，并不会马上将该页从 old 区域升级到 young 区域，因为还要进行停留在 old 区域的时间判断：
  • 如果第二次的访问时间与第一次访问的时间在 1 秒内（默认值），那么该页就不会被从 old 区域升级到 young 区域；
  • 如果第二次的访问时间与第一次访问的时间超过 1 秒，那么该页就会从 old 区域升级到 young 区域；