面试官：你懂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/s

1、数据页从冷到热，称为young；not young就是数据在没有成为热数据情况下就被刷走的量(累计值)。

2、non-youngs/s，这个数值如果很高，一般情况下就是系统存在严重的全表扫描，自然意味着很高的物理读。(上面分析过)

3、youngs/s，如果这个值相对较高，最好增加一个innodb_old_blocks_time，降低innodb_old_blocks_pct，保护热数据。

总结

本文总结了Innodb中的LRU是如何做的，希望大家有所收获。 另外，唉，最近有一番新的感慨。

• 代码写的好，bug少，看起来像是一个闲人
• 注释多，代码清晰，任何人可以接手，看起来就是谁都可以替代
• 代码写的烂，每天惊动各大领导提流程改生产代码，解决生产问题，就是公司亮眼人才
• 代码写的烂，只有自己看得懂，就是公司不可替代的重要人才

心累，社会呀～

你可能会喜欢

1、腾讯面试题：有了二叉查找树、平衡树为啥还需要红黑树？

2、为什么你学不会递归？告别递归，谈谈我的一些经验

3、一文读懂一台计算机是如何把数据发送给另一台计算机的

4、一个故事讲完哈希洪荒攻击

5、算法数据结构中有哪些奇技淫巧？