Redis 4.0版本开始就提供了8种内存淘汰策略，其中有4种策略算法都是基于LRU与LFU算法来实现的，如下图所示：

在《从理论到实践，深入解析Redis过期删除策略与内存淘汰机制》文章中我们也阐述了这8种内存淘汰策略，本文主要就Redis种的LRU与LFU算法进行讨论。

1. LRU算法

LRU（The Least Recently Used）最近最少使用算法，它基于"最近使用原则"，以最近被访问的数据对象具有更高的保留优先级，即如果一个数据对象在最近一段时间没有被访问到，那么在将来它被访问的可能性也会很低。当缓存空间已满，而需要插入新的数据对象时，LRU算法会替换最近最少使用的数据对象。

在Redis中，它是每次随机选取一批数据对象进行LRU淘汰，而不是针对所有的数据对象，从而通过牺牲部分准确率来提高LRU算法的执行效率。

Redis实现的是一种近似的LRU算法，它并没有创建一个专门针对于传统意义上的LRU算法的双向链表，而是只简单地使用了Hash表。这是因为Redis其自身就是基于内存的数据库，维护一个拥有所有键值对的链表会占用大量的内存资源，另外每次访问数据时频繁的移动数据到链表头部也需要增加性能开销。

Redis中的每个键都有一个额外的时间戳字段来记录最后一次访问该键的时间。Redis维护一个全局的LRU时钟，它是一个递增的整数值，表示键的访问顺序。当一个键被访问时，Redis会将该键的时间戳更新为当前时间，并将LRU时钟的值赋给该键。当Redis需要淘汰数据时，会根据LRU时钟的值选择最久（即时间戳最小）未被访问的键进行淘汰。

如下面的代码所示：

#define LRU_BITS 24
typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:LRU_BITS; 
    /* LRU time (relative to global lru_clock) or
     * LFU data (least significant 8 bits frequency
     * and most significant 16 bits access time). */
int refcount;
void *ptr;
} robj;

在Redis的redisObject数据结构中，变量“lru”用于记录了此键最近一次被访问的LRU时钟，每次键被访问或修改都会引起“lru”的更新。

由此可见，LRU算法仅仅是只关注数据对象的访问时间或者访问顺序，而忽略了访问次数的价值，因此在淘汰数据对象的过程中很可能会淘汰掉热点数据。

2. LFU算法

LFU（The Least frequently used）最不常使用算法，它基于"最不常使用原则"，以使用频率次数最少的数据对象具有较低的保留优先级。当缓存空间已满，而需要插入新数据对象时，LFU算法会替换使用频率次数最少的数据对象。这种算法假设如果一个数据对象在近期被高频率地使用，那么在未来它被再次使用的概率也会很高；而使用频率次数较少的数据对象在未来使用的概率也会较少，因此将使用频率次数较少的数据对象替换出去。

在Redis中，它与LRU一样，也是每次随机选取一批数据对象进行LRU淘汰，而不是针对所有的数据对象。

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

同时，在数据结构中，LFU算法并没有使用额外的数据结构，而是复用了redisObject数据结构的“lru”字段，把这 24 bits 空间拆分成两部分去使用。即：

1）在 LRU 算法中，redisObject中 24 bits 的 lru 字段是用来记录 Key 的访问时间戳；

2）在 LFU 算法中，redisObject中 24 bits 的 lru 字段被分成两段来存储：高 16 bits 存储 ldt(Last Decrement Time)，用来记录Key 的访问时间戳；低 8 bits 存储 logc(Logistic Counter)，用来记录 Key 的访问频次。

在实际使用中，如果业务数据的访问较为均匀，OPS或CPU利用率一般不会出现周期性的陡升或陡降，数据也没有体现出相对的“冷热”特性，即建议采用LRU算法，可以满足一般的运维需求；如果业务具有很强的时效性，在活动推广或者促销等期间，业务某些数据会突然成为热点数据，监控上呈现出OPS或CPU利用率的大幅波动，为了能抓取热点数据便于后期的分析或优化，建议采用LFU算法。