Redis 为何使用Nearly LRU 算法淘汰数据

Redis 使用该 LRU 算法淘汰过期数据吗？不是的。

• 由于 LRU 算法需要用链表管理所有的数据，会造成大量额外的空间消耗。
• 大量的节点被访问就会带来频繁的链表节点移动操作，从而降低了 Redis 性能。

Redis的内存空间是很宝贵的，而维护LRU的双向链表需要使用比较多的额外空间，至少需要一个前向指针、一个后向指针和一个指向数据的指针。

Redis的作者使用了一种基于随机采样的近似LRU（NearlyLRU），并不是真正的 LRU，Redis 通过对少量的 key 采样，并淘汰采样的数据中最久没被访问过的 key，它在Redis里面是不需要花费额外空间的。

一、随机采样

随机访问更加一般的情况我们想要的是频繁被访问的元素不会被淘汰，而LRU刚好就有这种思想，其实LRU也可以实现为一个根据元素被访问时间戳排序的列表，每次淘汰列表的尾部的元素，也就是时间戳最小的元素。

而NearlyLRU就是利用了这个时间戳的思想，也就是每个元素带有最后一次被访问的时间戳（Redis里面本来就有记录，因此不需要额外的空间），但是它没有去维护一个堆，因此它只能随机进行采样。淘汰算法流程如下：

1. 从所有元素里面随机采样5个元素
2. 淘汰5个里面最后一次被访问的时间戳最小的元素

可以发现第2步其实就有LRU的思想，只是LRU是选取全部元素里面最后一次被访问的时间戳最小的元素，而NearlyLRU则是采样一小批。

因此NearlyLRU其实命中率是不如LRU的，但是它的好处也是明显的，不需要额外的数据结构。

如果想提高命中率，可以增大采样数量，这样会更加接近LRU，当然时间成本也会相应的上升。

二、优化场景总结

1、Memcached

Memcached 前面有文章已讲解过，思想与Multi Queue类似。

2、MySQL buffer pool

MySQL change buffer缓存，使用的是类LRU-k的算法，读取新数据页页，不是放于LRU列表首部，而是放于5/8处，因为索引或数据扫描需要访问很多页，非活跃热点数据，放于首部，可能会移除真正的热点数据

3、Redis

Redis中的数据整体上是一个大的字典，Redis采用了基于采样的近似LRU算法，redis并没有去遍历所有对象，每个对象都记有最近访问时间戳。

LRU算法也比较简单，Redis有一个全局的LRU时钟，每次随机取出5（maxmemory-samples默认参数）个redis对象，淘汰时间戳最小的。