1
简述中规中矩的LRU链表
LRU：Least Recently Used
相信大家对LRU链表是不陌生的，它算是一种基础的数据结构吧，而且想必面试时也被问到过什么是LRU链表，甚至是让你手写一个LRU链表。
如果你读了上一篇：你有没有搞混查询缓存和BufferPool？谈谈看！
想必你已经知道了MySQL的Buffer Pool机制以及MySQL组织数据的最小单位是数据页。并且你也知道了 数据页在Buffer Pool中是以LRU链表的数据结构组织在一起的。
其实所谓的LRU链表本质上就是一个双向循环链表，如下图：
下面我们结合LRU链表和数据页机制描述一下MySQL加载数据的机制：
我们将从磁盘中读取的数据页称为young page，young page会被直接放在链表的头部。已经存在于LRU链表中数据页如果被使用到了，那么该数据页也被认为是young page而被移动到链表头部。这样链表尾部的数据就是最近最少使用的数据了，当Buffer Pool容量不足，或者后台线程主动刷新数据页时，就会优先刷新链表尾部的数据页。
2传统LRU链表的不足
相信你之前肯定听说过操作系统级别的空间局部性原理：
spatial locality（空间局部性）：也就是说读取一个数据，在它周围内存地址存储的数据也很有可能被读取到，于是操作系统会帮你预读一部分数据。
MySQL也是存在预读机制的！
当Buffer Pool中存储着一个区中13个连续的数据页时，你再去这个区里面读取，MySQL就会将这个区里面所有的数据页都加载进Buffer Pool中的LRU链表中。（然后可能你根本不会使用这些被预读的数据页）
当你顺序的访问了一个区中大于 <code>innndb_read_ahead_threshold=56</code>个数据页时，MySQL会自动帮你将下一个相邻区中的数据页读入LRU链表中。（这个机制默认是被关闭的）
当你执行<code>select * from xxx;</code>时，如果表中的数据页非常多，那这些数据页就会一一将Buffer Pool中的经常使用的缓存页挤下去，可能导致留在LRU链表中的全部是你不经常使用的数据。
当然你可能对什么是数据区并不了解，别急～ 关注我，白日梦将在第13篇文章中同你分享什么是数据区。
综上：你可以发现，所谓的预读机制的优势，在一定程度上违背了LRU去实现将最近最少使用的数据页刷入磁盘的设计初衷。
3MySQL的LRU链表
当业务进行大量的CRUD时，需要不断的将数据页读取到buffer pool中的LRU链表中，接下来我们看下MySQL的Buffer Pool是如何定制LRU链表的，以及LRU帮InnoDB解决了什么问题。
MySQL的LRU链表长下面这样：
LRU链表被MidPoint分成了New Sublist和Old Sublist两部分。
其中New Sublist大概占比5/8，Old Sublist占比3/8。
New Sublist存储着young page，而Old Sublist存储着Old Page。
我们可以通过如下的方式查看MidPoint的默认值。
用户可以根据自己的业务动态的调整这个参数！
这其实是一种冷热数据分离设计思想。他相对于传统的LRU链表有很大的优势
4MySQL定制的LRU链表的优势
而对于MySQL的LRU链表来说，通过MidPoint将链表分成两部分。
从磁盘中新读出的数据会放在Old Sublist的头部。
这样即使你真的使用<code>select * from t;</code>也不会导致New Sublist中的经常被访问的数据页被刷入磁盘中。
正常情况下，访问Old Sublist中的缓存页，那么该缓存页会被提升到New Sublist中成为热数据。
但是当你通过 <code>select * from t</code>将一大批数据加载到Old Sublist时，然后在不到1s内你又访问了它，那在这段时间内被访问的缓存页并不会被提升为热数据。这个1s由参数<code>innodb_old_blocks_time</code>控制。
另外：New SubList也是经过优化的，如果你访问的是New SubList的前1/4的数据，它是不会被移动到LRU链表头部去的。