面试中的两个问题：

　　操作系统在读磁盘的时候会额外多读一些数据到内存中，最后也没有用到，如何改善？

　　批量读取数据的时候，可能会热点数据挤出去，如何改善?

　　Linux 和 MySQL 的缓存

　　Linux 操作系统的缓存

　　在应用程序读取文件的数据的时候，Linux 操作系统是会对读取的文件数据进行缓存的，会缓存在文件系统中的 Page Cache（如下图中的页缓存）。

　　Page Cache 属于内存空间里的数据，由于内存访问比磁盘访问快很多，在下一次访问相同的数据就不需要通过磁盘 I/O 了，命中缓存就直接返回数据即可。

　　因此，Page Cache 起到了加速访问数据的作用。

　　MySQL 的缓存

　　MySQL 的数据是存储在磁盘里的，为了提升数据库的读写性能，Innodb 存储引擎设计了一个缓冲池（Buffer Pool），Buffer Pool 属于内存空间里的数据。

　　有了缓冲池后：

　　当读取数据时，如果数据存在于 Buffer Pool 中，客户端就会直接读取 Buffer Pool 中的数据，否则再去磁盘中读取。

　　当修改数据时，首先是修改 Buffer Pool 中数据所在的页，然后将其页设置为脏页，最后由后台线程将脏页写入到磁盘。

　　传统 LRU 是如何管理内存数据的？

　　Linux 的 Page Cache 和 MySQL 的 Buffer Pool 的大小是有限的，并不能无限的缓存数据，对于一些频繁访问的数据我们希望可以一直留在内存中，而一些很少访问的数据希望可以在某些时机可以淘汰掉，从而保证内存不会因为满了而导致无法再缓存新的数据，同时还能保证常用数据留在内存中。

　　要实现这个，最容易想到的就是 LRU（Least recently used）算法。

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

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

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

　　当访问的页在内存里，就直接把该页对应的 LRU 链表节点移动到链表的头部。

　　当访问的页不在内存里，除了要把该页放入到 LRU 链表的头部，还要淘汰 LRU 链表末尾的页。

　　存在的问题：

　　如果一条数据仅仅是突然被访问（有可能后续将不再访问），在 LRU 算法下，此数据将被定义为热数据，最晚被淘汰。但实际生产环境下，我们很多时候需要计算的是一段时间下key的访问频率，淘汰此时间段内的冷数据。

　　预读失效，怎么办？

　　什么是预读机制？

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

　　应用程序只想读取磁盘上文件 A 的 offset 为 0-3KB 范围内的数据，由于磁盘的基本读写单位为 block（4KB），于是操作系统至少会读 0-4KB 的内容，这恰好可以在一个 page 中装下。

　　但是操作系统出于空间局部性原理（靠近当前被访问数据的数据，在未来很大概率会被访问到），会选择将磁盘块 offset [4KB,8KB)、[8KB,12KB) 以及 [12KB,16KB) 都加载到内存，于是额外在内存中申请了 3 个 page；

　　下图代表了操作系统的预读机制：

　　上图中，应用程序利用 read 系统调动读取 4KB 数据，实际上内核使用预读机制（ReadaHead） 机制完成了 16KB 数据的读取，也就是通过一次磁盘顺序读将多个 Page 数据装入 Page Cache。

　　这样下次读取 4KB 数据后面的数据的时候，就不用从磁盘读取了，直接在 Page Cache 即可命中数据。因此，预读机制带来的好处就是减少了 磁盘 I/O 次数，提高系统磁盘 I/O 吞吐量。

　　MySQL Innodb 存储引擎的 Buffer Pool 也有类似的预读机制，MySQL 从磁盘加载页时，会提前把它相邻的页一并加载进来，目的是为了减少磁盘 IO。

　　预读失效会带来什么问题？

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

　　如果把「预读页」放到了 LRU 链表头部，而当内存空间不够的时候，还需要把末尾的页淘汰掉。而末尾淘汰的页，可能是热点数据，这样就大大降低了缓存命中率 。

　　如何避免预读失效造成的影响？

　　我们不能因为害怕预读失效，而将预读机制去掉，大部分情况下，空间局部性原理还是成立的。要避免预读失效带来影响，可以从两个方面考虑

　　让预读页停留在内存里的时间要尽可能的短，

　　让真正被访问的页移动到 LRU 链表的头部，从而保证热数据留在内存里的时间尽可能长。

　　那到底怎么才能避免呢？

　　Linux 操作系统和 MySQL Innodb 通过改进传统 LRU 链表来避免预读失效带来的影响，具体的改进分别如下：

　　Linux 操作系统实现两个了 LRU 链表：活跃 LRU 链表（active_list）和非活跃 LRU 链表（inactive_list）；

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

　　这两个改进方式，设计思想都是类似的，都是将数据分为了冷数据和热数据，然后分别进行 LRU 算法。不再像传统的 LRU 算法那样，所有数据都只用一个 LRU 算法管理。

　　接下来，具体聊聊 Linux 和 MySQL 是如何避免预读失效带来的影响？

　　Linux 是如何避免预读失效带来的影响？

　　Linux 操作系统实现两个了 LRU 链表：活跃 LRU 链表（active_list）和非活跃 LRU 链表（inactive_list）。

　　active list 活跃内存页链表，这里存放的是最近被访问过（活跃）的内存页；

　　inactive list 不活跃内存页链表，这里存放的是很少被访问（非活跃）的内存页；

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

　　MySQL 是如何避免预读失效带来的影响？

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

　　young 区域在 LRU 链表的前半部分，old 区域则是在后半部分，这两个区域都有各自的头和尾节点，如下图：

　　young 区域与 old 区域在 LRU 链表中的占比关系并不是一比一的关系，而是 63:37（默认比例）的关系。划分这两个区域后，预读的页就只需要加入到 old 区域的头部，当页被真正访问的时候，才将页插入 young 区域的头部。如果预读的页一直没有被访问，就会从 old 区域移除，这样就不会影响 young 区域中的热点数据。

　　缓存污染，怎么办？

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

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

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

　　缓存污染带来的问题

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

　　怎么避免缓存污染造成的影响？

　　前面的 LRU 算法只要数据被访问一次，就将数据加入活跃 LRU 链表（或者 young 区域），这种 LRU 算法进入活跃 LRU 链表的门槛太低了！正式因为门槛太低，才导致在发生缓存污染的时候，很容就将原本在活跃 LRU 链表里的热点数据淘汰了。

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

　　Linux 操作系统和 MySQL Innodb 存储引擎分别是这样提高门槛的：

　　Linux 操作系统：在内存页被访问第二次的时候，才将页从 inactive list 升级到 active list 里。

　　MySQL Innodb：在内存页被访问第二次的时候，并不会马上将该页从 old 区域升级到 young 区域，因为还要进行停留在 old 区域的时间判断：

　　如果第二次的访问时间与第一次访问的时间在 1 秒内（默认值），那么该页就不会被从 old 区域升级到 young 区域；

　　如果第二次的访问时间与第一次访问的时间超过 1 秒，那么该页就会从 old 区域升级到 young 区域；