MySQL中的free链表，flush链表，LRU链表

一、free链表

1、概述

        free链表是一个双向链表数据结构，这个free链表里，每个节点就是一个空闲的缓存页的描述数据块的地址，也就是说，只要你一个缓存页是空闲的，那么他的描述数据块就会被放入这个free链表中。 刚开始数据库启动的时候，可能所有的缓存页都是空闲的，因为此时可能是一个空的数据库，一条数据都没有，所以此时所有缓存页的描述数据块，都会被放入这个free链表中,我们看下图所示 。

 

2、free链表的数据结构

        可能有的人会以为这个描述数据块，在Buffer Pool里有一份，在free链表里也有一份，好像在内存里有两个一模一样的描述数据块，是么？ 其实这么想就大错特错了。 这里要给大家讲明白一点，这个free链表，他本身其实就是由Buffer Pool里的描述数据块组成的，你可以认为是每个描述数据块里都有两个指针，一个是free_pre，一个是free_next，分别指向自己的上一个free链表的节点，以及下一个free链表的节点。 通过Buffer Pool中的描述数据块的free_pre和free_next两个指针，就可以把所有的描述数据块串成一个free链表，大家可以自己去思考一下这个问题。上面为了画图需要，所以把描述数据块单独画了一份出来，表示他们之间的指针引用关系。

        对于free链表而言，只有一个基础节点是不属于Buffer Pool的，他是40字节大小的一个节点，里面就存放了free链表的头节点的地址，尾节点的地址，还有free链表里当前有多少个节点。

3、磁盘数据缓存的过程

首先，我们需要从free链表里获取一个描述数据块，然后就可以对应的获取到这个描述数据块对应的空闲缓存页，我们看下图所示。

        接着我们就可以把磁盘上的数据页读取到对应的缓存页里去，同时把相关的一些描述数据写入缓存页的描述数据块里去，比如这个数据页所属的表空间之类的信息，最后把那个描述数据块从free链表里去除就可以了，如下图所示。

 

4、怎么知道数据页有没有被缓存

        数据库还会有一个哈希表数据结构，他会用表空间号+数据页号，作为一个key，然后缓存页的地址作为value。当你要使用一个数据页的时候，通过“ 表空间号+数据页号 ”作为key去这个哈希表里查一下，如果没有就读取数据页，如果已经有了，就说明数据页已经被缓存了。 我们看下图，又引入了一个数据页缓存哈希表的结构。

        也就是说，每次你读取一个数据页到缓存之后，都会在这个哈希表中写入一个key-value对，key就是表空间号+数据页号，value就是缓存页的地址，那么下次如果你再使用这个数据页，就可以从哈希表里直接读取出来他已经被放入一个缓存页了。

 

二、flush链表

1、概述

        你在执行增删改的时候，如果发现数据页没缓存，那么必然会基于free链表找到一个空闲的缓

存页，然后读取到缓存页里去，但是如果已经缓存了，那么下一次就必然会直接使用缓存页。

反正不管怎么样，你要更新的数据页都会在Buffer Pool的缓存页里，供你在内存中直接执行增删改的操作。

        接着你肯定会去更新Buffer Pool的缓存页中的数据，此时一旦你更新了缓存页中的数据，那么缓存页里的数据和磁盘上的数据页里的数据，是不是就不一致了？ 这个时候，我们就说缓存页是脏数据，脏页。

2、哪些缓存页是脏页

        其实通过之前的学习，我们都是知道一点的，最终这些在内存里更新的脏页的数据，都是要被刷新回磁盘文件的。

        但是这里就有一个问题了，不可能所有的缓存页都刷回磁盘的，因为有的缓存页可能是因为查询的时候被读取到Buffer Pool里去的，可能根本没修改过！

        所以数据库在这里引入了另外一个跟free链表类似的flush链表 ，这个flush链表本质也是通过缓存页的描述数据块中的两个指针，让被修改过的缓存页的描述数据块，组成一个双向链表。 凡是被修改过的缓存页，都会把他的描述数据块加入到flush链表中去，flush的意思就是这些都是脏页，后续都是要flush刷新到磁盘上去的。所以flush链表的结构如下图所示，跟free链表几乎是一样的。

 

三、LRU链表

1、工作原理

        简单来说，我们看下图，假设我们从磁盘加载一个数据页到缓存页的时候，就把这个缓存页的描述数据块放到LRU链表头部去，那么只要有数据的缓存页，他都会在LRU里了，而且最近被加载数据的缓存页，都会放到LRU链表的头部去。

         然后假设某个缓存页的描述数据块本来在LRU链表的尾部，后续你只要查询或者修改了这个缓存页的数据，也要把这个缓存页挪动到LRU链表的头部去，也就是说最近被访问过的缓存页，一定在LRU链表的头部，如下图。

 

        那么这样的话，当你的缓存页没有一个空闲的时候，你是不是要找出来那个最近最少被访问的缓存页去刷入磁盘？此时你就直接在LRU链表的尾部找到一个缓存页，他一定是最近最少被访问的那个缓存页！

        然后你就把LRU链表尾部的那个缓存页刷入磁盘中，然后把你需要的磁盘数据页加载到腾出来的空闲缓存页中就可以

了！

2、冷热数据分离

        真正的LRU链表，会被拆分为两个部分，一部分是热数据，一部分是冷数据，这个冷热数据的比例是由innodb_old_blocks_pct参数控制的，他默认是37，也就是说冷数据占比37%。 个时候，LRU链表实际上看起来是下面这样子的。

3、数据页第一次被加载到缓存的时候

        数据页第一次被加载到缓存的时候，这个时候缓存页会被放在LRU链表的哪个位置呢？ 实际上这个时候，缓存页会被放在冷数据区域的链表头部，我们看下面的图，也就是第一次把一个数据页加载到缓存页之后，这个缓存页实际上是被放在下图箭头的位置，也就是冷数据区域的链表头部位置。

4、冷数据区域的缓存页什么时候会被放入到热数据区域

        MySQL设定了一个规则，他设计了一个innodb_old_blocks_time参数，默认值1000，也就是1000毫秒 。也就是说，必须是一个数据页被加载到缓存页之后，在1s之后，你访问这个缓存页，他才会被挪动到热数据区域的链表头部去。

        因为假设你加载了一个数据页到缓存去，然后过了1s之后你还访问了这个缓存页，说明你后续很可能会经常要访问它，这个时间限制就是1s，因此只有1s后你访问了这个缓存页，他才会给你把缓存页放到热数据区域的链表头部去。

        所以我们看下面的图，文字说明做了一点改动，是数据加载到缓存页之后过了1s，你再访问这个缓存页，他就会被放入热数据区域的链表头部，如果是你数据刚加载到缓存页，在1s内你就访问缓存页，此时他是不会把这个缓存页放入热数据区域的头部的。

5、LRU链表的淘汰机制

        接着我们看，假设此时缓存页不够了，需要淘汰一些缓存页，此时会怎么做？ 那就很简单了，直接就是可以找到LRU链表中的冷数据区域的尾部的缓存页，他们肯定是之前被加载进来的，而且加载进来1s过后都没人访问过，说明这个缓存页压根儿就没人愿意去访问他！他就是冷数据！所以此时就直接淘汰冷数据区域的尾部的缓存页，刷入磁盘，就可以了，我们看下图。