Redis常用内存淘汰策略？
作者：程序员马丁
在线博客：https://open8gu.com
大话面试，技术同学面试必备的八股文小册，以精彩回答应对深度问题，助力你在面试中拿个offer。
答题思路
从淘汰范围来说可以分为不淘汰任何数据、只从设置了到期时间的键中淘汰和从所有键中淘汰三类。而从淘汰算法来分，又主要分为 Random（随机），LRU（最近最少使用），以及 LFU（最近最不常使用）三种。
回答话术
内存总是有限的，因此当 Redis 内存超出最大内存时，就需要根据一定的策略去主动的淘汰一些 Key，来腾出内存，这就是内存淘汰策略。我们可以在配置文件中通过 maxmemory-policy 配置指定策略。
与到期删除策略不同，内存淘汰策略主要目的则是为了防止运行时内存超过最大内存，所以尽管最终目的都是清理内存中的一些 Key，但是它们的应用场景和触发时机是不同的。
算上在 4.0 添加的两种基于 LFU 算法的策略， Redis 一共提供了八种策略供我们选择：
noeviction，不淘汰任何 key，直接报错。它是默认策略。volatile-random：从所有设置了到期时间的 Key 中，随机淘汰一个 Key。volatile-lru： 从所有设置了到期时间的 Key 中，淘汰最近最少使用的 Key。volatile-lfu： 从所有设置了到期时间的 Key 中，淘汰最近最不常用使用的 Key（4.0 新增）。volatile-ttl： 从所有设置了到期时间的 Key 中，优先淘汰最早过期的 Key。allkeys-random：从所有 Key 中，随机淘汰一个键（4.0 新增）。allkeys-lru： 从所有 Key 中，淘汰最近最少使用的 Key。allkeys-lfu： 从所有 Key 中，淘汰最近最不常用使用的键。
从淘汰范围来说可以分为不淘汰任何数据、只从设置了到期时间的键中淘汰和从所有键中淘汰三类。而从淘汰算法来分，又主要分为 Random（随机），LRU（最近最少使用），以及 LFU（最近最不常使用）三种。
其中，关于 LRU 算法，它是一种非常常见的缓存淘汰算法。我们可以简单理解为 Redis 会在每次访问 Key 的时候记录访问时间，当淘汰时，优先淘汰最后一次访问距离现在最早的 Key。
而对于 LFU 算法，我们可以理解为 Redis 会在访问 Key 时，根据两次访问时间的间隔计算并累加访问频率指标，当淘汰时，优先淘汰访问频率指标最低的 key。相比 LRU 算法，它避免了低频率的大批量查询造成的缓存污染问题。
顺带一提，只要是有类似缓存机制的应用或多或少都会面对这种问题，比如老生常谈的 MySQL 连表查询，在数据量大的时候也会造成缓存污染。
此外，当选择 LFU 算法时，如果数据量比较大，为了避免因为抽样数量过小导致冷热 Key 之间因为时间衰减造成的权重差异难以体现，最好将抽样大小设置的大一些，减小热数据被误伤的可能性。
问题详解
1. 淘汰策略
按 Key 的淘汰范围来分，我们可以把这些策略分为三类
1）不淘汰任何数据
也就是noeviction，它是默认的策略。
2）只从设置的了到期时间的 Key 中淘汰
volatile-random：从所有设置了到期时间的 Key 中，随机淘汰一个 Key。volatile-lru：从所有设置了到期时间的 Key 中，淘汰最近最少使用的 Key。volatile-lfu：从所有设置了到期时间的 Key 中，淘汰最近最不常用使用的 Key，4.0 版本新增。volatile-ttl：从所有设置了到期时间的 Key 中，优先淘汰最早过期的 Key。
3）从所有的 Key 中进行淘汰
allkeys-rando：从所有 Key 中，随机淘汰一个键，4.0 版本新增。allkeys-lru：从所有 Key 中，淘汰最近最少使用的 Key。allkeys-lfu：从所有 Key 中，淘汰最近最不常用使用的键。
2. 淘汰过程
- 每次当 Redis 执行命令时，若设置了最大内存大小
maxmemory，并设置了淘汰策略式，则会尝试进行一次 Key 淘汰； - Redis 首先会评估已使用内存（这里不包含主从复制使用的两个缓冲区占用的内存）是否大于
maxmemory，如果没有则直接返回，否则将计算当前需要释放多少内存，随后开始根据策略淘汰符合条件的 Key；当开始进行淘汰时，将会依次对每个数据库进行抽样，抽样的数据范围由策略决定，而样本数量则由maxmemory-samples配置决定； - 完成抽样后，Redis 会尝试将样本放入提前初始化好
EvictionPoolLRU数组中，它相当于一个临时缓冲区，当数组填满以后即将里面全部的 Key 进行删除。 - 若一次删除后内存仍然不足，则再次重复上一步骤，将样本中的剩余 Key 再次填入数组中进行删除，直到释放了足够的内存，或者本次抽样的所有 Key 都被删除完毕（如果此时内存还是不足，那么就重新执行一次淘汰流程）。
从到期字典中抽样
在抽样这一步，涉及到从字典中随机抽样这个过程，由于哈希表的 Key 是散列分布的，因此会有很多桶都是空的，纯随机效率可能会很低。因此，Redis 采用了一个特别的做法，那就是先连续遍历数个桶，如果都是空的，再随机调到另一个位置，再连续遍历几个桶……如此循环，直到结束抽样。
你可以参照源码理解这个过程：
unsigned int dictGetSomeKeys(dict *d, dictEntry **des, unsigned int count) {
unsigned long j; /* internal hash table id, 0 or 1. */
unsigned long tables; /* 1 or 2 tables? */
unsigned long stored = 0, maxsizemask;
unsigned long maxsteps;
if (dictSize(d) < count) count = dictSize(d);
maxsteps = count*10;
// 如果字典正在迁移，则协助迁移
for (j = 0; j < count; j++) {
if (dictIsRehashing(d))
_dictRehashStep(d);
else
break;
}
tables = dictIsRehashing(d) ? 2 : 1;
maxsizemask = d->ht[0].sizemask;
if (tables > 1 && maxsizemask < d->ht[1].sizemask)
maxsizemask = d->ht[1].sizemask;
unsigned long i = random() & maxsizemask;
unsigned long emptylen = 0;
// 当已经采集到足够的样本，或者重试已达上限则结束采样
while(stored < count && maxsteps--) {
for (j = 0; j < tables; j++) {
if (tables == 2 && j == 0 && i < (unsigned long) d->rehashidx) {
if (i >= d->ht[1].size)
i = d->rehashidx;
else
continue;
}
// 如果一个库的到期字典已经处理完毕，则处理下一个库
if (i >= d->ht[j].size) continue;
dictEntry *he = d->ht[j].table[i];
// 连续遍历多个桶，如果多个桶都是空的，那么随机跳到另一个位置，然后再重复此步骤
if (he == NULL) {
emptylen++;
if (emptylen >= 5 && emptylen > count) {
i = random() & maxsizemask;
emptylen = 0;
}
} else {
emptylen = 0;
while (he) {
*des = he;
des++;
he = he->next;
stored++;
if (stored == count) return stored;
}
}
}
// 查找下一个桶
i = (i+1) & maxsizemask;
}
return stored;
}
3. LRU 的实现
LRU 的全称为 Least Recently Used，也就是最近最少使用。一般来说，LRU 会从一批 Key 中淘汰上次访问时间最早的 key。
它是一种非常常见的缓存回收算法，在诸如 Guava Cache、Caffeine等缓存库中都提供了类似的实现。我们自己也可以基于 JDK 的 LinkedHashMap 实现支持 LRU 算法的缓存功能。
3.1. 近似 LRU
传统的 LRU 算法实现通常会维护一个链表，当访问过某个节点后就将该节点移至链表头部。如此反复后，链表的节点就会按最近一次访问时间排序。当缓存数量到达上限后，我们直接移除尾节点，即可移除最近最少访问的缓存。
不过，对于 Redis 来说，如果每个 Key 添加的时候都需要额外的维护并操作这样一条链表，要额外付出的代价显然是不可接受的，因此 Redis 中的 LRU 是近似 LRU（NearlyLRU）。
当每次访问 Key 时，Redis 会在结构体中记录本次访问时间，而当需要淘汰 Key 时，将会从全部数据中进行抽样，然后再移除样本中上次访问时间最早的 key。
它的特点是：
- 仅当需要时再抽样，因而不需要维护全量数据组成的链表，这避免了额外内存消耗。
- 访问时仅在结构体上记录操作时间，而不需要操作链表节点，这避免了额外的性能消耗。
当然，有利就有弊，这种实现方式也决定 Redis 的 LRU 是并不是百分百准确的，被淘汰的 Key 未必真的就是所有 Key 中最后一次访问时间最早的。
3.2. 抽样大小
根据上述的内容，我们不难理解，当抽样的数量越大，LRU 淘汰 Key 就越准确，相对的开销也更大。因此，Redis 允许我们通过 maxmemory-samples 配置采样数量（默认为 5），从而在性能和精度上取得平衡。
3.3. 缓存污染
LRU 有个最大问题，就是它只认最近一次访问时间。而如果出现系统偶尔需要一次性读取大量数据的时候，会大规模更新 Key 的最近访问时间，从而导致真正需要被频繁访问的 Key 因为最近一次访问时间更早而被直接淘汰。这种情况被称为缓存污染。为此，我们需要使用 LFU 算法来解决。
4. LFU 的实现
LFU 全称为 Least Frequently Used ，也就是最近最不常用。它的特点如下：
- 同样是基于抽样实现的近似算法，
maxmemory-samples对其同样有效。 - 比较的不是最后一次访问时间，而是数据的访问频率。当淘汰的时候，优先淘汰范围频率最低 Key。
它的实现与 LRU 基本一致，但是在计数部分则有所改进。
4.1. 概率计数器
在 Redis 用来存储数据的结构体 redisObj 中，有一个 24 位的 lru数值字段：
- 当使用 LRU 算法时，它用于记录最后一次访问时间的时间戳。
- 当使用 LFU 算法时，它被分为两部分，高 16 位关于记录最近一次访问时间（
Last Decrement Time），而低 8 位作为记录访问频率计数器（Logistic Counter）。
LFU 的核心就在于低 8 位表示的访问频率计数器（下面我们简称为 counter），是一个介于 0 ~ 255 的特殊数值，它会每次访问 Key 时，基于时间衰减和概率递增机制动态改变。
这种基于概率，使用极小内存对大量事件进行计数的计数器被称为莫里斯计数器，它是一种概率计数法的实现。
4.2. 时间衰减
每当访问 Key 时，根据当前实际与该 Key 的最后一次访问时间的时间差对 counter 进行衰减。
衰减值取决于 lfu_decay_time 配置，该配置表示一个衰减周期。我们可以简单的认为，每当时间间隔满足一个衰减周期时，就会对 counter 减一。
比如，我们设置 lfu_decay_time为 1 分钟，那么如果 Key 最后一次访问距离现在已有 3 分 30 秒，那么 counter 就需要减 3。
4.3. 概率递增
在完成衰减后，Redis 将根据 lfu_log_factor 配置对应概率值对 counter 进行递增。
这里直接放上源码：
/* Logarithmically increment a counter. The greater is the current counter value
* the less likely is that it gets really implemented. Saturate it at 255. */
uint8_t LFULogIncr(uint8_t counter) {
// 若已达最大值 255，直接返回
if (counter == 255) return 255;
// 获取一个介于 0 到 1 之间的随机值
double r = (double)rand()/RAND_MAX;
// 根据当前 counter 减去初始值得到 baseval
double baseval = counter - LFU_INIT_VAL;
if (baseval < 0) baseval = 0;
// 使用 baseval*server.lfu_log_factor+1 得到一个概率值 p
double p = 1.0/(baseval*server.lfu_log_factor+1);
// 当 r < p 时，递增 counter
if (r < p) counter++;
return counter;
}
简而言之，直接从代码上理解，我们可以认为 counter和 lfu_log_factor 越大，则递增的概率越小：
当然，实际上也要考虑到访问次数对其的影响，Redis 官方给出了相关数据：
4.4. 计数器的初始值
为了防止新的 Key 由于 counter 为 0 导致直接被淘汰，Redis 会默认将 counter设置为 5。
4.5. 抽样大小的选择
值得注意的是，当数据量比较大的时候，如果抽样大小设置的过小，因为一次抽样的样本数量有限，冷热数据因为时间衰减导致的权重差异将会变得不明显，此时 LFU 算法的优势就难以体现，即使的相对较热的数据也有可能被频繁“误伤”。
所以，如果你选择了 LFU 算法作为淘汰策略，并且同时又具备比较大的数据量，那么不妨将抽样大小也设置的大一些。
5. 如何选择
软件工程没有银弹，我们不可能指望存在一个能完美适用于所有场景的内存淘汰策略。在实际场景中，我们需要结合业务特点、数据量大小、数据的冷热……等多个维度来选择合适的淘汰策略。
简单的来说，如果你的业务数据的访问比较平均，不存在明显的冷热区别，那么 LRU 可以满足一般的使用需求。如果你的业务具备很强的时效性，而且是存在大促商品这种明显的热点数据，那么推荐你使用 LFU。
当然，思路要打开，调整淘汰策略只是优化方案的一种，条件允许的话，在特定情况下直接增加内存、将单机改为集群或者缓存预热同样可以带来显著的收益。