15 当Buffer Pool中的缓存页不够的时候，如何基于LRU算法淘汰部分缓存？

当Buffer Pool中的缓存页不够的时候，如何基于LRU算法淘汰部分缓存？

1、如果Buffer Pool中的缓存页不够了怎么办？

之前我们已经给大家讲解了Buffer Pool中的缓存页的划分，包括free链表的使用，然后磁盘上的数据页是如何加载到缓存页里去的，包括对缓存页修改之后，flush链表是如何用来记载脏数据页的。

今天我们接着来分析Buffer Pool的工作原理，我们来思考一个问题，当你要执行CRUD操作的时候，无论是查询数据，还是修改数据，实际上都会把磁盘上的数据页加载到缓存页里来，这个大家都是没有问题的吧？

那么在加载数据到缓存页的时候，必然是要加载到空闲的缓存页里去的，所以必须要从free链表中找一个空闲的缓存页，然后把磁盘上的数据页加载到那个空闲的缓存页里去，我们看下图的红色箭头的示意。

           

             

那么大家通过之前的学习肯定都知道了，随着你不停的把磁盘上的数据页加载到空闲的缓存页里去，free链表中的空闲缓存页是不是会越来越少？因为只要你把一个数据页加载到一个空闲缓存页里去，free链表中就会减少一个空闲缓存页。

所以，当你不停的把磁盘上的数据页加载到空闲缓存页里去，free链表中不停的移除空闲缓存页，迟早有那么一瞬间，你会发现free链表中已经没有空闲缓存页了

这个时候，当你还要加载数据页到一个空闲缓存页的时候，怎么办呢？如下图。

           

             

2、如果要淘汰掉一些缓存数据，淘汰谁？

针对上述的问题，大家来思考下一个问题，如果所有的缓存页都被塞了数据了，此时无法从磁盘上加载新的数据页到缓存页里去了，那么此时你只有一个办法，就是淘汰掉一些缓存页。

那什么叫淘汰缓存页呢？

顾名思义，你必须把一个缓存页里被修改过的数据，给他刷到磁盘上的数据页里去，然后这个缓存页就可以清空了，让他重新变成一个空闲的缓存页。

接着你再把磁盘上你需要的新的数据页加载到这个腾出来的空闲缓存页中去，如下图。

           

             

那么下一个问题来了，如果要把一个缓存页里的数据刷入磁盘，腾出来一个空闲缓存页，那么应该把哪个缓存页的数据给刷入磁盘呢？

3、缓存命中率概念的引入

要解答这个问题，我们就得引入一个缓存命中率的概念。

假设现在有两个缓存页，一个缓存页的数据，经常会被修改和查询，比如在100次请求中，有30次都是在查询和修改这个缓存页里的数据。那么此时我们可以说这种情况下，缓存命中率很高

为什么呢？因为100次请求中，30次都可以操作缓存，不需要从磁盘加载数据，这个缓存命中率就比较高了。

另外一个缓存页里的数据，就是刚从磁盘加载到缓存页之后，被修改和查询过1次，之后100次请求中没有一次是修改和查询这个缓存页的数据的，那么此时我们就说缓存命中率有点低，因为大部分请求可能还需要走磁盘查询数据，他们要操作的数据不在缓存中。

所以针对上述两个缓存页，假设此时让你做一个抉择，要把其中缓存页的数据刷入到磁盘去，腾出来一个空闲的缓存页，此时你会选择谁？

那还用想么，当然是选择第二个缓存页刷入磁盘中了！

因为第二个缓存页，压根儿就没什么人来使用他里面的数据，结果这些数据还空占据了一个缓存页，这不是占着茅坑不拉屎么？

4、引入LRU链表来判断哪些缓存页是不常用的

接着我们就要解决下一个问题了，就是你怎么知道哪些缓存页经常被访问，哪些缓存页很少被访问？

此时就要引入一个新的LRU链表了，这个所谓的LRU就是Least Recently Used，最近最少使用的意思。

通过这个LRU链表，我们可以知道哪些缓存页是最近最少被使用的，那么当你缓存页需要腾出来一个刷入磁盘的时候，不就可以选择那个LRU链表中最近最少被使用的缓存页了么？

这个LRU链表大致是怎么个工作原理呢？

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

           

             

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

           

             

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

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

5、上次思考题解答

今天我们在末尾解答一下上次留的那个思考题，就是说，我们在SQL语句里都是用到的是表和行的概念，但是之前我们提到的表空间、数据页，他们之间的关系是什么呢？

其实简单来讲，一个是逻辑概念，一个是物理概念。

表、列和行，都是逻辑概念，我们只知道数据库里有一个表，表里有几个字段，有多少行，但是这些表里的数据，在数据库的磁盘上如何存储的，你知道吗？我们是不关注的，所以他们都是逻辑上的概念。

表空间、数据页，这些东西，都是物理上的概念，实际上在物理层面，你的表里的数据都放在一个表空间中，表空间是由一堆磁盘上的数据文件组成的，这些数据文件里都存放了你表里的数据，这些数据是由一个一个的数据页组织起来的，这些都是物理层面的概念，这就是他们之间的区别。

End

专栏版权归公众号儒猿技术窝所有

未经许可不得传播，如有侵权将追究法律责任