LRU算法在Redis和MySQL中的区别

LRU（least recently used-最近最少使用算法），是一种内存数据淘汰策略，使用常见是当内存不足时，需要淘汰最近最少使用的数据。LRU常用作缓存系统的淘汰策略

标准LRU算法

LRU（Least Recently Used）缓存淘汰算法同时使用哈希表（Hash Map）和双向链表（Doubly Linked List）。

为什么需要两者结合？

这是为了在满足LRU策略的同时，保证核心操作（get 和 put）的时间复杂度为 O(1)。

只用哈希表：

可以 O(1) 时间查找。

问题： 无法维护访问顺序！哈希表本身是无序的。当需要淘汰时，我们不知道哪个是最久未使用的项。遍历整个哈希表找 LRU 项需要 O(n) 时间，违背了 O(1) 的要求。

只用双向链表：

可以完美维护访问顺序（头是 MRU，尾是 LRU），移动节点和插入删除头/尾节点都是 O(1)。

Redis中的LRU

Redis并没有按照标准的LRU算法进行实现，而是采取了一种“近似LRU”的实现方式。

原因：

1、Redis内部只实现了Hash表，而标准的LRU算法则需要双向链表 + Hash表两种数据结构。换言之，需要在Redis内存中再额外增加一个双向链表，这个内存消耗的代价是不可接受的。

2、每个Redis请求，LRU的双向链表也需要进行同步操作，这种实现方式对性能影响不小。

实现细节：

Redis 为每个键的对象结构添加了 lru字段，记录其最近访问时间（非绝对时间，是一个全局逻辑时钟）。

Redis 每次进行内存淘汰时，并不会遍历所有键，而是从所有键中随机采样若干个（默认 5 个），然后挑出其中访问最久远的键淘汰。

这个采样数量可通过参数maxmemory-samples 配置。

优点：

无需维护全局链表，节省空间；

不需要每次访问都做链表操作，大幅提高性能；

适用于高性能场景的内存淘汰

缺点：

由于是近似LRU，并非全局最久未使用的键一定会被淘汰，存在一定误差；

可能出现缓存污染问题：某些键被短时间大量访问后遗留在内存中，却很少被再次使用

缓存污染问题说的是缓存中一些只会被访问一次或者几次的的数据，被访问完后，再也不会被访问到，但这部分数据依然留存在缓存中，消耗缓存空间

缓存污染本质还是因为随机清理，所以要解决缓存污染问题，最关键的技术点就是能识别出这些只访问一次或是访问次数很少的数据，在淘汰数据时，优先把它们筛选出来并淘汰掉

MySQL中的LRU

相对于标准和Redis,MySQL中BufferPool的LRU应用

如上图所示，整个链表被分为New Sublist和Old Sublist两个部分，

前者占整个链表长度的5/8，存储的是最近被频繁访问的Page；

后者只占3/8，存储的是最近访问次数较低的Page，这些Page会有被淘汰的可能。

当一个新的Page被写入到Buffer Pool中，InnoDB会将其放至上图中Midpoint的位置上，也就是Old Sublist的Head位置。

一个Page会由于两种情况被加载到BufferPool中

一个是当用户执行SQL语句进行访问，

另一个则是InnoDB自动执行预读访问。

预读操作，顾名思义，在SQL查询操作中，InnoDB会提前读取“后续很有可能被访问到”的Data Page写入到Buffer Pool中，以减少磁盘IO次数的方式来提升后续查询性能。

在数据库运行过程中，如果BufferPool的Old Sublist中有Page被用户执行的SQL语句访问到，那该Page会被移动到New Sublist的Head位置，使其“返老还童”。

热数据中的数据,访问一次就会立马移动到头部吗?

既然数据在热数据中,那么被访问的频率肯定是比较高的,如果访问一次就直接移动到最前面,那么这样的话,频繁的移动也是对性能的损耗,这个时候mysql又设计了一个比较优雅的地方:

在热数据区,如果这个被访问的缓存页在前25%,就不会移动了,只有在后25%范围内,每次访问的时候才被移动到头部,这样就能大大减少一些不必要的移动而造成的损失

在热数据区,如果这个被访问的缓存页在前25%,就不会移动了,只有在后25%范围内,每次访问的时候才被移动到头部,这样就能大大减少一些不必要的移动而造成的损失

那些最近未被访问的Page会逐渐地向链表的Tail方向移动，以表示其“逐渐老化”，并且随着新的Page被写入到Buffer Pool中Old Sublist的Head位置，Old Sublist中的Page也会“逐渐老化”。

最终，一个长时间未被使用的Page到达了Old Sublist中的Tail位置，被执行了淘汰操作。