Redis的内存淘汰策略

Redis的内存设置

Redis的内存及缓存策略，可以通过redis的配置文件redis.conf设置，也可以在运行的时候通过指令动态设置。

配置文件设置

内存大小通过设置参数 maxmemory 内存策略通过设置参数 maxmemory-policy

maxmemory 256 
maxmemory-policy allkeys-lru

动态设置

通过 CONFIG-SET指令进行设置

CONFIG SET maxmemory 256 
CONFIG SET maxmemory-policy allkeys-lru

Redis的内存淘汰策略

当Redis的内存达到maxmemory，Redis会采用maxmemory-policy设置的淘汰策略，去淘汰数据。
Redis提供了8种淘汰策略分别是

• noeviction 达到最大内存限制时，不删除任何数据，直接返回错误。
• allkeys-lru 基于最近最少使用(LRU)算法，删除所有key中最近最少使用的key。
• allkeys-lfu基于最近最不常用(LFU)算法，删除所有key中最近最不常用的key。
• allkeys-random 随机删除所有key中最近最不常用的key。
• volatile-lru 基于最近最少使用(LRU)算法，删除已设置过期时间的key中最近最少使用的key。
• volatile-lfu基于最近最不常用(LFU)算法，删除已设置过期时间的key中最近最不常用的key。
• volatile-random 随机删除已设置过期时间的key中最近最不常用的key。
• volatile-ttl 删除已设置过期时间的key中最早过期的key

按照淘汰范围来看，内存淘汰策略分为

• 不淘汰数据
• 从所有的key中进行淘汰
• 只从设置了过期时间的key中进行淘汰

淘汰算法又分为

• Random
• LRU
• `LFU

Redis LRU的实现（近似LRU）

常见的LRU实现，是通过维护一个双向链表，当访问节点时，将节点移动到链表的头部。这样节点就会按照最近访问的时间顺序进行排序，当需要移除节点时，直接移除链表的尾节点即可。[[LRU Java实现]]

而对于Redis来说，采用这样的方式来实现LRU会有以下问题。

• 维护这样的双向链表花销大
• 因为需要额外存储双向链表的指针，所以内存占用大

所以Redis采用的是近似LRU算法，每次访问key时，通过其存储结构中的lru字段去存储key本次访问的时间，当需要淘汰key时，将会从全部数据中进行随机抽样，然后移除样本中上次访问时间最早的key。

优点如下：

• 当需要淘汰key时，才进行抽样，所以不需要维护双向链表，避免了额外的内存开销。
• 访问时只需要记录访问时间，不需要操作链表节点，避免了额外的性能开销

显然抽样的样本数量越多，LRU淘汰的key越准确，但是抽取的样本数量越多带来的花销也更大。
我们可以通过maxmemory-samples参数来配置采样数量（默认为5）。

使用LRU淘汰策略可能会引发缓存污染问题 ，指的是系统低频率的进行批量查询，大量数据被放入缓存中，导致热点数据可能误淘汰，从而导致缓存污染

Redis LFU的实现（近似LFU）

同样的Redis的LFU算法也是通过随机抽样的方式来实现，只不过移除样本的是参考的不再是访问时间，而是访问频率，优先淘汰样本中访问频率最低的key。

访问频率的计算

Redis没有引入新的数据结构去实现LFU，而是将LRU中使用到的lru字段进行拆分

• 高位的16bits用于存储访问时间戳，并且是以分钟为单位的时间戳
• 低位的8bits，用于存储热度值(counter)，也就是访问频率。

当我们每次访问key时，counter的值会基于时间衰减机制以及概率机制进行动态改变。

这种基于概率，使用极小内存对大量事件进行计数的计数器被称为莫里斯计数器，它是一种概率计数法的实现。

时间衰减机制

通过计算（这一次的访问时间 - 上一次的访问时间）/ 衰减周期，从而计算出counter的衰减值，
counter = counter - 衰减值。
在Redis中，我们可以通过参数lfu_decay_time(默认值1)进行配置。

概率递增机制

概率递增算法如下

#define LFU_INIT_VAL 5
 
/* 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) {
  if (counter == 255) return 255;
  double r = (double)rand()/RAND_MAX;
  double baseval = counter - LFU_INIT_VAL;
  if (baseval < 0) baseval = 0;
  double p = 1.0/(baseval*server.lfu_log_factor+1);
  if (r < p) counter++;
  return counter;
}

• 当counter等于255时，将不会再递增
• 当counter的值小于初始值5的时候，将百分百概率进行递增。
• 当counter的值大于初始值5的时候，先计算两者的差值，然后作为分母参与递增概率的计算，当递增概率大于随机概率时，才会递增
• 随着counter的增大，递增的概率会原来越小，会出现多次访问，counter也不会递增的情况出现。

我们可以通过配置递增衰减因子lfu_log_factor(默认值10),来调整递增概率的计算。
通过时间衰减机制以及概率递增机制计算访问频率，解决了只参考访问次数，忽略访问时间带来的问题。