上面谈到要实现一个朴素的LRU算法，需要维护一个双向链表，存储前驱、后继指针，必然会在寸金寸土的缓存（内存）中带来不必要的开销。上述提到的时钟算法就是一种类LRU算法，用更少的系统开销带来了接近朴素LRU的命中率。而事实上，Redis中采取的LRU算法也是一种类LRU算法，它也带来了时钟算法类似的效果。具体的是Redis通过随机选取几个key值，淘汰时间戳最靠前的key，涉及到LRU的淘汰策略maxmemory_policy（这个字段可以选择不同的缓存淘汰策略，Redis一种提供了8种，本文只分析其中与LRU有关的）的赋值两种：
allkeys-lru: 对所有的键都采取LRU淘汰 volatile-lru: 仅对设置了过期时间的键采取LRU淘汰可以根据实际情况选择上述两种LRU淘汰策略，在一般情况下，程序都存在局部性，或者说幂次分布（二八法则），即少数数据比其他大多数数据访问的更多，所以通常使用allkeys-lru策略，而当有需求需要长期保留一部分数据在内存中时选取volatile-lru即只规定部分需要淘汰的数据。
下面看一下具体是如何设置的，Redis整体上是一个大的字典，key是一个string，而value都会保存为一个robj（Redis Object），对于robj的定义如下
其中LRU_BITS即Redis为每个键值对配备的一个记录时间戳的bit位，Redis的LFU替换策略中也使用这个空间，创建对象时会写入到lru_clock这个字段中，访问对象时会对其进行更新，具体的空间的大小被定义为一个常量
大小为24，即使用一个额外的24bit的空间记录相对时间戳（即对unix time取模之后的结果），默认的时间戳分辨率是1秒，在这种情况下，24bits的空间如果溢出的话需要194天，而作为频繁更新的缓存而言，这个空间够用了。
上面提到了Redis会随机采样，比较其访问时间哪个更靠前，当需要替换时优先踢出采样结果最靠前的键值对，具体的采样个数在最开始是选取3个key，但是效果并不好，后来增加到N个key，但是默认是5个，即默认随机选取5个key，最先淘汰掉这5个中距离上次访问时间最久的，Redis3.0中又改善了算法的性能，即提供了一个采样池（pool），候选采样池默认大小为16，能够填充16个key，更新时从Redis键空间随机选择N个key，分别计算它们的空闲时间idle，key只会在pool不满或者空闲时间大于pool里最小的时，才会进入pool，然后从pool中选择空闲时间最大的key淘汰掉。
具体的这个候选集合结构体如下
所以关键在pool中的idle字段的计算，实际上只需要使用当前的时间戳减去lru_clock即可，但是所记录的时间戳都是取模之后的结果，所以还需要比较当前计算出来的时间戳是否大于lru_clock，如果不是，则需要将当前
时间戳+194天（模数）再减去lru_clock。具体的计算过程如下
另外Redis官方文档里有对于候选数为5、10在redis2.8无侯选池，以及3.0加侯选池的对比。
四张图依次是，理论LRU的使用情况、有pool采样数为10的候选情况、无pool采样数为5的情况、有pool采样数为10的情况。其中
绿色部分是新添加的key 灰色部分是最近使用的key浅 灰色部分是替换的key可以看出采取Redis3.0的采取维护一个候选淘汰池的方法已经能够接近全局比较情况下也即朴素LRU的结果。
详细的分析可以参考https://redis.io/topics/lru-cache
4.2 以MySQL的InnoDB引擎为例此处InnoDB的缓存概念不做过多赘述，只简单介绍其中LRU的应用，InnoDB会把cpu频繁使用的数据存储在主存的缓冲池（Buffer Pool）中，鉴于MySQL在使用过程中存在着经常性的全表扫描，所以如果使用朴素LRU必然会频繁的大面积替换，造成极低的缓存命中率。
所以InnoDB采取了一种冷热分离的思路，即将整个缓冲池分为冷区和热区或者说年轻区（New Sublist）和老区（Old Sublist）
默认情况下距离链表尾3/8以上的位置称为新子列表（热点区域），以下的位置称为旧子列表（冷区域），某个页面初次加载到缓冲池时，放在old区域的头部。在对某个处于old区域的缓冲页进行第一次访问时，就在它对应的控制块中记录下这个访问时间，如果后续的访问时间和第一次访问的时间在某个时间间隔内（默认为1000ms），那么该页面就不会从老的区域移动到年轻区域的头部，否则将他移动到年轻区域的头部。
而当缓冲池满时需要淘汰数据就从old区域的尾部进行淘汰，这样数据起码需要两次（一次为加载到内存，第二次为大于间隔时间的读取）合理的操作才能移动到年轻区域，有效的预防了全表扫描带来的命中率降低问题。
更加详细具体的描述可以参见MySQL官方文档对InnoDB buffer poll的解释。
到此这篇关于缓存替换策略及应用(以Redis、InnoDB为例)的文章就介绍到这了,更多相关redis缓存替换策略内容请搜索七叶笔记以前的文章或继续浏览下面的相关文章希望大家以后多多支持七叶笔记！
