背景：不停的把磁盘上的数据页加载到空闲缓存页里去，free链表中不停的移除空闲缓存页，当free链表中已经没有空闲缓存页了，但还要加载数据页到空闲缓存页的时候，只能淘汰调一些缓存页。

淘汰缓存页：把缓存页里被修改的数据，刷到磁盘上的数据页去，然后这个缓存页就可以清空了，让他重新变成一个空闲缓存页。

那么，应该把哪个缓存页的数据给刷入磁盘呢？

一、LRU链表：判断不常用缓存页

LRU：Least Recently Used
MySQL的Buffer Pool机制以及MySQL组织数据的最小单位是数据页。并且数据页在Buffer Pool中是以LRU链表的数据结构组织在一起的。
其实所谓的LRU链表本质上就是一个双向循环链表，如下图：
image.png
简单描述一下MySQL加载数据的机制：

  1. 我们将从磁盘中读取的数据页称为Young Page，Young Page会被直接放在链表的头部。
  2. 已经存在于LRU链表中数据页如果被使用到了，那么该数据页也被认为是Young Page而被移动到链表头部。
  3. 这样链表尾部的数据就是最近最少使用的数据了，当Buffer Pool容量不足，或者后台线程主动刷新数据页时，就会优先刷新链表尾部的数据页。

二、LRU链表可能导致问题

2.1 隐患1：Mysql预读机制:

了解一下操作系统级别的空间局部性原理： spatial locality（空间局部性）：也就是说读取一个数据，在它周围内存地址存储的数据也很有可能被读取到，于是操作系统会帮你预读一部分数据。

MySQL也是存在预读机制的！

  1. 当你顺序的访问了一个区中大于 innndb_read_ahead_threshold=56 个数据页时，MySQL会自动帮你将下一个相邻区中的数据页读入LRU链表中。
  2. 当Buffer Pool中存储着一个数据区中13个连续的数据页时，你再去这个区里面读取，MySQL就会将这个区里面所有的数据页都加载进Buffer Pool中的LRU链表中（然后可能你根本不会使用这些被预读的数据页）。这个机制通过参数 innodb_random_read_ahead 控制，默认OFF。

    PS：什么是数据区？

综上：你可以发现，所谓的预读机制的优势，在一定程度上违背了LRU去实现将最近最少使用的数据页刷入磁盘的设计初衷。

2.2 隐患2：全表扫描

所谓全表扫描就是：SELECT * FROM xxx; 此时没有加任何where条件，会导致直接把这个表的所有数据页都从磁盘中加载到Buffer Pool里。如果表中的数据页非常多，那这些数据页就会一一将Buffer Pool中的经常使用的缓存页挤下去，可能导致留在LRU链表中的全部是你不经常使用的数据。

三、基于冷热数据分类优化LRU链表

为了解决以上问题，真正Mysql在设计LRU链表时，采取的实际是冷热数据分离的思想。LRU链表被MidPoint分成了New Sublist和Old Sublist两部分。New Sublist存储着Young Page（热数据），而Old Sublist存储着Old Page（冷数据）。这个冷热数据的比例由参数 innodb_old_blocks_pct 控制，默认37，即冷数据占37%。
实际的Mysql的LRU链表是下面的结构：
image.png

3.1 实际LRU链表工作机制及优势：

  1. 从磁盘中新读出的数据会放在Old Sublist的头部。这样即使预读大批数据或全表扫描也不会导致New Sublist中经常被访问的数据页被刷入磁盘中。
  2. 正常情况下，访问Old Sublist中的缓存页，该缓存页会被提升到New Sublist的头部成为热数据
    1. 但是有一批数据页刚被加载到Old Sublist头部，然后在不到 innodb_old_blocks_time=1 s内又被访问了，那么在这段时间内被访问的缓存页并不会被提升为热数据。
    2. 如果一个缓存页在Old Sublist的尾部，已经超过1秒了，这个缓存页被访问了一下，此时它会被移动到冷数据区域的链表头部。
  3. New SubList也是经过优化的，如果你访问的是New SubList的前1/4的数据，它是不会被移动到LRU链表头部去的。因为热数据区域的缓存页可能是经常被访问的，频繁的进行移动对性能不好。
  4. 假设缓存页不够需要淘汰一些缓存页，就直接Old Sublist尾部的缓存页。

四、LRU链表中缓存页刷盘

4.1 冷数据区缓存页刷盘时机

  1. 缓存页满时。
  2. 后台线程，定时任务：每隔一段时间把冷数据区域尾部的缓存页刷入磁盘，清空缓存页，从flush链表移除，并加入free链表。

4.2 flush链表中一些缓存页定时刷入磁盘

仅仅是把冷数据区域的缓存刷入磁盘是不够的，因为LRU链表的热区域里很多缓存页可能也会被频繁的修改，难道他们永远都不刷入磁盘中了？
后台线程同时也会在Mysql不怎么繁忙的时候，找个时间把flush链表中的缓存页都刷入磁盘中，这样被修改过的数据，迟早都会刷入磁盘。

PS：详情见FLush链表专栏

Flush链表：脏页刷到磁盘

整个动态过程是： 一边不停的加载数据到缓存页，不停的查询和修改缓存数据，然后free链表中的缓存页不停的在减少，flush链表中的缓存页不停的在增加，LRU链表中的缓存页不停的在增加和移动。 另一边后台线程不停的在把LRU链表的冷数据区域的缓存页以及flush链表的缓存页，刷入磁盘中来清空缓存页，然后flush链表和LRU链表中的缓存页在减少，free链表中的缓存页在增加。