InnoDB如何将LRU性能优化到极致

引言

通过对Buffer Pool工作原理的讲解，我们知道一次查询操作可能会经历hash查找，磁盘加载数据到Buffer Pool，缓存页，free链，flush链的协调才能完成。当Buffer Pool内缓存页不足以支撑本次操作时，会通过LRU策略对缓存页进行淘汰，从而清理出足够的空间来完成本次的查询。那LRU这种方式会不会有什么弊端？InnoDB存储引擎又是如何解决弊端的呢？这就是本文要讲解的内容。

回顾LRU原理

原理

LRU（Least Recently Used）：最近最少使用，作为一种缓存淘汰策略，它的核心思想就是淘汰最久没有被访问过的内存页。原理如下图所示：

图中，绿色代表空闲内存页，红色代表被淘汰内存页。

实现

为了在维护内存页的顺序的同时保证高效率，LRU一般采用的是双向链表+哈希表的结构。其中双向链表的增加、删除操作都能在O(1)的时间里完成，通过哈希表的性质在O(1)的时间里对内存页进行高效查找。

在Java集合类中，LinkedHashMap这种数据刚好就是这种结构，并且它也提供了按照访问顺序的排序方案，我们只需要重写removeEldestEntry方法即可，当该方法返回true的时候，就会删除最旧的节点，所以我们可以用这种结构快速的实现LRU，如下图所示：

Buffer Pool中LRU策略的隐患

隐患1、 MySQL的预读机制

MySQL预读： 就是从磁盘加载数据页到Buffer Pool时，往往连带着目标数据页相邻的数据页一起加载到Buffer Pool中。

为什么MySQL会存在预读机制呢？

其实就是提升性能。原因很简单：当你读取了数据页01,数据页02时，是不是很可能还会读取数据页03。

一次磁盘加载数据到Buffer Pool其实就是一次磁盘IO，是比较消耗性能的。

所以MySQL设计了预读机制，在某些情况下就会进行预读，提前将一些相邻的数据页读到Buffer Pool中，这样你下次真的要访问这个数据页的时候就不用去磁盘加载了，直接从Buffer Pool中读取，从而提高了效率。

预读触发场景： 前面说完了预读机制，那么接着聊聊哪些场景下会触发预读。

1. innodb_read_ahead_threshold：通过参数设置，默认值56，表示如果顺序访问了一个区的数据页数量达到56个，就会触发预读，把相邻的下一个区中所有数据页预读到Buffer Pool中；
2. innodb_random_read_ahead：默认是OFF，表示如果Buffer Pool中缓存了一个数据区的连续13个数据页，且这些数据页都被频繁访问，那么就会把这个数据区的其他数据页预读到Buffer Pool中。

隐患： 这样做一方面可以提高性能；但是另一方面可能会发生，预读进去的数据页几乎不被访问，但是由于LRU的特性，这部分数据页在预读进去后会处于链表的头节点附近，还可能淘汰一部分本身访问比较频繁的数据页。

隐患2、 全表扫描

全表扫描可能会把一些访问不频繁的数据页加载到Buffer Pool中，从而淘汰一部分本身访问比较频繁的缓存页。从而影响性能，因为访问频繁的缓存页又得重新从磁盘中加载进来。

基于冷热隔离的LRU策略

回顾上面的问题，其实最大的问题就是把一些不该淘汰的缓存页（访问频繁的缓存页）给淘汰了，也就是热数据被淘汰；应该被淘汰的（几乎不怎么被访问的缓存页）保留下来了，即冷数据被保留。这明显不是我们想要的结果。

为了解决这个问题，LRU链被拆为两部分：一部分存储热数据，一部分存储冷数据，冷数据比例由参数：innodb_old_blocks_pct 控， 默认占37%。

数据页加载到缓存的过程

当数据初次加载到Buffer Pool中时，会首先放在冷链的头部，经过1s后如果再被访问，则将缓存页移动至热链头部，这个间隔时间由参数：innodb_old_blocks_time 控制，默认1000，即1000ms （1s）。

将LRU链性能优化到极致

同时InnoDB对LRU链还有个小的优化，就是如果一个缓存页被访问时，它已经位于热链的前1/4的位置里，那么将不会移动这个缓存页到头部。这样做的目的也是为了提高性能，因为即使采用了双向链表+哈希的结构，但是移动缓存页仍然会有性能开销。

LRU链结构如下所示：

缓存页刷回磁盘

首先不管是不是基于冷热数据隔离的LRU链，基于我们前面所讲，会有后台线程定期将缓存页刷回磁盘，那么刷的是什么缓存页？ 很显然：冷链末尾的缓存页。

其次当内存不够的时候，需要淘汰部分缓存页的时候，淘汰哪些缓存页？很显然：依然是冷链末尾的缓存页。

如何解决上述隐患

对于预读机制带来的隐患，由于刚刚加载进来的数据都是存放在冷链的头部，1s以后如果再被访问才会进入热链头部，那些预读加载进来但是又几乎不会被访问的的数据页，根本没有机会进入热链，所以在进行淘汰时，也自然不会影响到那些热数据，而是优先选择冷链的尾部。

小结

同“池化”一样，冷热数据隔离，也是一种很好的思想。在我们自己设计缓存的时候，也可以想想是否可以使用类似的思想。

我们经常就使用redis作为缓存，当我们需要缓存的数据量很大，同时又有明显的冷热数据差别。你不可能把所有的数据都缓存到redis里，而是把一些热数据放在缓存，来提高缓存的命中率，从而提高性能的同时节省资源，其实这也就是热数据的缓存预加载。 通常在用户访问量少的时候，通过计算出一系列热数据，然后预加载到redis里，从而提高在访问高峰期的性能。

既然说到redis,那么redis作为一种高性能的key-value数据库，它的缓存淘汰策略是怎么做的呢？

redis的缓存淘汰策略

当redis实际内存超出设置的maxmemory时，redis提供了几种策略让用户自己决定该如何腾出新的空间以继续提供读写服务，策略通过参数maxmemory-policy进行设置，相关淘汰策略如下：

1. noeviction：不会继续服务写请求（DEL请求可以继续服务），读请求可以继续进行。这样可以保证不会丢失数据，但是会让线上的业务不能持续进行，默认的淘汰策略；
2. volatile-lru：从所有设置了过期时间的key中淘汰最久未被使用的key；
3. allkeys-lru：区别于volatile-lru，它是从所有的key中淘汰最久没被使用的key；
4. volatile-random：从所有设置了过期时间的key中随机选中key进行淘汰；
5. allkeys-random：从所有key中随机淘汰key；
6. volatile-ttl：从所有设置了过期时间的key中选择剩余寿命ttl最小的key进行淘汰；

Redis中的LRU算法

同样redis中也不是直接使用原始的LRU算法，而是采用一种近似LRU的算法。原始的LRU算法会对内存带来较大的额外消耗，因为需要对现有的Redis数据结构进行改造。

近似的LRU算法就是在现有的数据结构结构基础上，采用随机采样淘汰元素。为了实现近似LRU算法，Redis会给每个key额外增加24bit，用来存储这个key最后一次被访问的时间戳。

在Redis中，LRU淘汰时惰性淘汰，也就是当Redis执行写操作的时候，发现内存超出了maxmemory，则进行LRU淘汰。方法很简单，随机采样几个key（数量可以），然后淘汰掉最旧的key，如果淘汰后还是超出maxmemory，则继续淘汰，知道内存小于maxmemory。

在Redis3.0中，还新增加了一个淘汰池，本质上它是一个大顶堆，新随机出来的key会添加到淘汰池，然后淘汰最旧的key。具体我就不详细在这里展开了。

总结

本文讲解了常见的页面置换算法：LRU，讲解了基本原理及实现方式。并同时分析了InnoDB中的LRU的实现方式，简单LRU带来的隐患，及InnoDB如何通过冷热数据隔离解决隐患及对性能的极致优化。最后简要分析了Redis中的LRU算法的实现。

学习本文的关键在于掌握思想，并用在自己的设计中。