面试官：你懂LRU?那你知道InnoDB里的LRU怎么做的吗？
作者：孤独烟
引言
某日，烟哥前去面试(纯属瞎编)，有了如下对话
面试官:"懂mysql吧，知道CPU在读硬盘上数据的时候，是怎么解决CPU和硬盘速度不一致问题么?" 烟哥:"懂啊，mysql先把数据页加载到内存里，然后读内存中的数据啊！" 面试官:"你们用的是哪个存储引擎?" 烟哥:"嗯，innodb，因为需要用事务功能！" 面试官:"嗯，好。那既然需要把数据页加载到内存里，这里必然涉及到LRU算法，当这块区域满了后，将一些不常用的数据页淘汰掉，innodb具体怎么做的？" 烟哥尴尬的笑了笑，回答道:"我只知道redis中LRU怎么做的..balabala" 面试官:"停，我只想知道innodb怎么做的？" 烟哥:"我还是回去等通知吧~"
接下来烟哥回去
于是就有了本文诞生
正文
什么是BufferPool
Innodb为了解决磁盘上磁盘速度和CPU速度不一致的问题，在操作磁盘上的数据时，先将数据加载至内存中，在内存中对数据页进行操作。
Mysql在启动的时候，会向内存申请一块连续的空间，这块空间名为Bufffer Pool，也就是缓冲池，默认情况下Buffer Pool只有128M。
那缓冲池长什么样的呢，如下图所示
图片出自《Mysql运维内参》
如图所示，有三部分组成:
- ctl: 俗称控制体，里头有一个指针指向缓存页，还有一个成员变量存储着所谓的一些所谓的控制信息，例如该页所属的表空间编号、页号
- page:缓存页，就是磁盘上的页加载进Bufffer Pool后的结构体
- 碎片：每个控制体都有一个缓存页。最后内存中会有一点点的空间不足以容纳一对控制体和缓存页，于是碎片就诞生的！
这个控制体ctl在mysql源码中长这样的
struct buf_block_t{
//省略
buf_page_t page;
byte* frame;
//省略
}嗯，懂C语言的自然知道，frame是一个指针啦，指向缓存页。 而page存储的就是该页所属的表空间编号、页号等。
在BufferPool中有三大链表，需要重点关注，它们存储的元素都是buf_page_t。
比如，我总要知道那些页是可以用，是空闲的吧。
OK,这些信息在free链表中维护。
再比如，CPU肯定是不会去修改磁盘上的数据。那么，CPU修改了BufferPool中的数据后，Innodb总要知道要把哪一块信息刷到磁盘上吧。
OK，这些信息在flush链表中维护。
最后，当free链表里没多余的空闲页啦，innodb要淘汰一些缓存页啦。怎么淘汰？
这还用问，一定是淘汰最近最少使用的缓存页啊。
怎么知道这些页是最近最少使用的呢？
嗯，那就是要借助传说中的LRU链表啦。
简单的LRU
我们先来说一个简单的LRU算法。LRU嘛，全称吧啦吧啦…英文名忘了。反正就是一个淘汰最近最少使用的算法。 然后，烟哥去百度了一下，我发现百度是这么说的 最常见的实现是使用一个链表保存缓存数据，详细算法实现如下：
- 1. 新数据插入到链表头部；
- 2. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
- 3. 当链表满的时候，将链表尾部的数据丢弃。
嗯，完美！很完美！反正innodb中不可能这样设计～
那么为什么不能这么设计呢？
原因一
假设有一张表叫yan_ge_hao_shuai,(请将表名多看几遍)，回到正题，这张表什么索引都木有，有着几千万数据，反正就是很多很多数据页。然后，执行下面的语句
select * from yan_ge_hao_shuai因为没有任何索引嘛，那就进行全表扫描了。那么按照上面说的算法，这些数据页也会被全部塞入LRU链表，并且通通加载到BufferPool中，从而迅速清空其他查询语句留下来的高频的数据页。那么此时，你的BufferPool里全是低频的数据页，就会发现缓存命中率大大滴降低了。
于是你就会觉得:"我勒个去，设计这个Innodb的人，怕不是脑袋有问题…(以下省略一万字)"
原因二 这里先说以下innodb的预读机制，是这样子滴！这个预读细说起来可以分为线性预读和随机预读。借一张姜承尧大大的图，innodb的表逻辑结构如下图所示
从 InnoDB存储引擎的逻辑存储结构看,所有数据都被逻辑地存放在一个空间中,称之为表空间( tablespace)。表空间又由段(segment)、区( extent)、页(page)组成。页在一些文档中有时也称为块( block), InnoDB存储引擎的逻辑存储结构大致如图所示。
其实借这张图，我只想说一件事。数据页(page)是放在区(extent)里的。 那么
- 线性预读:当一个区中有连续56个页面(56为默认值)被加载到BufferPool中，会将这个区中的所有页面都加载到BufferPool中。其实挺合理的，毕竟一个区最多才64个页。
- 随机预读:当一个区中随机13个页面(13为默认值)被加载到BufferPool中，会将这个区中所有页面都加载到BufferPool中。随机预读默认是关闭，由变量
innodb_random_read_ahead控制。
好了，上面那一堆其实看不懂也没事。我只想说一件事，预读机制会预读一些额外的页到到BufferPool中。
那么，如果这些预读页并不是高频的页呢？
OK，如果这些页并不是高频的页，按照上面的算法，也会被加入LRU 链表，就会将链表末端一些高频的数据页给淘汰掉，从而导致命中率下降。
于是你会觉得:"唉，自己写一个都比他强…(此处略过一万字)"
Innodb的LRU
OK，为了解决上面的两个缺点。Innodb将这个链表分为两个部分，也就是所谓的old区和young区。
天啦噜，这两个区干嘛用的？
ok，young区在链表的头部，存放经常被访问的数据页，可以理解为热数据！
ok，old区在链表的尾部，存放不经常被访问的数据页，可以理解为冷数据！
这两个部分的交汇处称为midpoint，往下看！
怎么知道两个区的比例？
执行下面的命令
mysql> SHOW VARIABLES LIKE 'innodb_old_blocks_pct';
+-----------------------+-------+
| Variable_name | Value |
+-----------------------+-------+
| innodb_old_blocks_pct | 37 |
+-----------------------+-------+
1 row in set (0.01 sec)这说明了old区的比例为37%，也就是冷数据大概占LRU链表的3/8。剩下的就是young区的热数据。
于是可以得到一张大概的LRU链表图，如下所示(图片出自网络)
ps：一般生产的机器，内存比较大。我们会把innodb_old_blocks_pct值调低，防止热数据被刷出内存。
数据何时在old区，何时进入young区？
好，数据页第一次被加载进BufferPool时在old区头部。
当这个数据页在old区，再次被访问到，会做如下判断
- 如果这个数据页在LRU链表中
old区存在的时间超过了1秒，就把它移动到young区 - 这个存在时间由
innodb_old_blocks_time控制
我们来看看innodb_old_blocks_time的值，如下所示
mysql> SHOW VARIABLES LIKE 'innodb_old_blocks_time';
+------------------------+-------+
| Variable_name | Value |
+------------------------+-------+
| innodb_old_blocks_time | 1000 |
+------------------------+-------+
1 row in set (0.01 sec)那怎么解决这些缺点的？
针对原因一
也就是所谓的全表扫描导致Bufferpool中的高频数据页快速被淘汰的问题。
Innodb这么做的:
(1)扫描过程中，需要新插入的数据页，都被放到old区
(2)一个数据页会有多条记录，因此一个数据页会被访问多次
(3)由于是顺序扫描,数据页的第一次被访问和最后一次被访问的时间间隔不会超过1S，因此还是会留在old区
(4)继续扫描，之前的数据页再也不会被访问到，因此也不会被移到young区，最终很快被淘汰
针对原因二
也就是预读到的页，可能不是高频次的页。
你看，你预读到的页，是存在old区的。如果这个页后续不会被继续访问到，是会在old区逐步被淘汰的。因此不会影响young区的热数据。
监控冷热数据
执行下面命令即可
mysql> show engine innnodb status\G
……
Pages made young 0, not young 0
0.00 youngs/s, 0.00 non-youngs/s1、数据页从冷到热，称为young；not young就是数据在没有成为热数据情况下就被刷走的量(累计值)。
2、non-youngs/s，这个数值如果很高，一般情况下就是系统存在严重的全表扫描，自然意味着很高的物理读。(上面分析过)
3、youngs/s，如果这个值相对较高，最好增加一个innodb_old_blocks_time，降低innodb_old_blocks_pct，保护热数据。
总结
本文总结了Innodb中的LRU是如何做的，希望大家有所收获。 另外，唉，最近有一番新的感慨。
- 代码写的好，bug少，看起来像是一个闲人
- 注释多，代码清晰，任何人可以接手，看起来就是谁都可以替代
- 代码写的烂，每天惊动各大领导提流程改生产代码，解决生产问题，就是公司亮眼人才
- 代码写的烂，只有自己看得懂，就是公司不可替代的重要人才
心累，社会呀～
你可能会喜欢