Redis：LRU算法和LFU算法的区别

今天药忘吃喽~ 2024-03-24 21:51 80阅读 0赞

## 一、LRU ##

LRU（最近最少使用）：LRU策略基于"最近使用原则"，即最近被访问的项目具有更高的保留优先级。当缓存空间已满，而需要插入新项目时，LRU策略会替换最近最少使用的项目。这种策略假设最近被访问的项目更有可能在近期再次使用，因此将较长时间没有被使用的项目替换出去。

**简单来说就是淘汰很久没用的数据或项目。**

### LRU的实现 ###

传统 LRU 算法的实现是基于「链表」结构，链表中的元素按照操作顺序从前往后排列，最新操作的键会被移动到表头，当需要内存淘汰时，只需要删除链表尾部的元素即可，因为链表尾部的元素就代表最久未被使用的元素。

Redis 并没有使用这样的方式实现 LRU 算法，因为传统的 LRU 算法存在两个问题：

*  需要用链表管理所有的缓存数据，这会带来额外的空间开销；
 *  当有数据被访问时，需要在链表上把该数据移动到头端，如果有大量数据被访问，就会带来很多链表移动操作，会很耗时，进而会降低 Redis 缓存性能。

> Redis 是如何实现 LRU 算法的？

Redis 实现的是一种**近似 LRU 算法**，目的是为了更好的节约内存，它的**实现方式是在 Redis 的对象结构体中添加一个额外的字段，用于记录此数据的最后一次访问时间**。

当 Redis 进行内存淘汰时，会使用**随机采样的方式来淘汰数据**，它是随机取 5 个值（此值可配置），然后**淘汰最久没有使用的那个**。

Redis 实现的 LRU 算法的优点：

*  不用为所有的数据维护一个大链表，节省了空间占用；
 *  不用在每次数据访问时都移动链表项，提升了缓存的性能；

但是 LRU 算法有一个问题，**无法解决缓存污染问题**，比如应用一次读取了大量的数据，而这些数据只会被读取这一次，那么这些数据会留存在 Redis 缓存中很长一段时间，造成缓存污染。

## 二、LFU ##

LFU（最不经常使用）：LFU策略基于"最不经常使用原则"，即使用次数最少的项目具有较低的保留优先级。当缓存空间已满，而需要插入新项目时，LFU策略会替换使用次数最少的项目。这种策略假设使用频率较低的项目在未来也会继续被较少地使用，因此将使用次数较少的项目替换出去。

LFU 算法会记录每个数据的访问次数。当一个数据被再次访问时，就会增加该数据的访问次数。这样就解决了偶尔被访问一次之后，数据留存在缓存中很长一段时间的问题，相比于 LRU 算法也更合理一些。

**简单来说就是淘汰用的最少的数据或项目。**

> Redis 是如何实现 LFU 算法的？

LFU 算法相比于 LRU 算法的实现，多记录了「数据的访问频次」的信息。Redis 对象的结构如下：

typedef struct redisObject {
        ...
          
        // 24 bits，用于记录对象的访问信息
        unsigned lru:24;  
        ...
    } robj;

Redis 对象头中的 lru 字段，在 LRU 算法下和 LFU 算法下使用方式并不相同。

**在 LRU 算法中**，Redis 对象头的 24 bits 的 lru 字段是用来记录 key 的访问时间戳，因此在 LRU 模式下，Redis可以根据对象头中的 lru 字段记录的值，来比较最后一次 key 的访问时间长，从而淘汰最久未被使用的 key。

**在 LFU 算法中**，Redis对象头的 24 bits 的 lru 字段被分成两段来存储，高 16bit 存储 ldt(Last Decrement Time)，用来记录 key 的访问时间戳；低 8bit 存储 logc(Logistic Counter)，用来记录 key 的访问频次。

还没有评论，来说两句吧...