Redis删除策略和内存淘汰机制

删除策略

redis采用的是定期删除+惰性删除策略。

为什么不用定时删除策略?

定时删除,用一个定时器来负责监视key,过期则自动删除。虽然内存及时释放,但是十分消耗CPU资源。在大并发请求下,CPU要将时间应用在处理请求,而不是删除key,因此没有采用这一策略.

定期删除+惰性删除是如何工作的呢?

定期删除,redis默认每个100ms检查,是否有过期的key,有过期key则删除。需要说明的是,redis不是每个100ms将所有的key检查一次,而是随机抽取进行检查(如果每隔100ms,全部key进行检查,redis岂不是卡死)。因此,如果只采用定期删除策略,会导致很多key到时间没有删除。

于是,惰性删除派上用场。也就是说在你获取某个key的时候,redis会检查一下,这个key如果设置了过期时间那么是否过期了?如果过期了此时就会删除。

采用定期删除+惰性删除就没其他问题了么?

不是的,如果定期删除没删除key。然后你也没即时去请求key,也就是说惰性删除也没生效。这样,redis的内存会越来越高。那么就应该采用内存淘汰机制。

内存淘汰机制

在redis.conf中有一行配置

1
maxmemory-policy volatile-lru

该配置就是配内存淘汰策略的

  • noeviction:当内存使用超过配置的时候会返回错误,不会驱逐任何键
  • allkeys-lru:加入键的时候,如果过限,首先通过LRU算法驱逐最久没有使用的键
  • volatile-lru:加入键的时候如果过限,首先从设置了过期时间的键集合中驱逐最久没有使用的键
  • allkeys-random:加入键的时候如果过限,从所有key随机删除
  • volatile-random:加入键的时候如果过限,从过期键的集合中随机驱逐
  • volatile-ttl:从配置了过期时间的键中驱逐马上就要过期的键
  • volatile-lfu:从所有配置了过期时间的键中驱逐使用频率最少的键
  • allkeys-lfu:从所有键中驱逐使用频率最少的键

一般的经验规则:

  • 使用allkeys-lru策略:当预期请求符合一个幂次分布(二八法则等),比如一部分的子集元素比其它其它元素被访问的更多时,可以选择这个策略。
  • 使用allkeys-random:循环连续的访问所有的键时,或者预期请求分布平均(所有元素被访问的概率都差不多)
  • 使用volatile-ttl:要采取这个策略,缓存对象的TTL值最好有差异

volatile-lruvolatile-random策略,当你想要使用单一的Redis实例来同时实现缓存淘汰和持久化一些经常使用的键集合时很有用。未设置过期时间的键进行持久化保存,设置了过期时间的键参与缓存淘汰。不过一般运行两个实例是解决这个问题的更好方法。

为键设置过期时间也是需要消耗内存的,所以使用allkeys-lru这种策略更加节省空间,因为这种策略下可以不为键设置过期时间。

LRU

Redis配置中和LRU有关的有三个:

  • maxmemory: 配置Redis存储数据时指定限制的内存大小,比如100m。当缓存消耗的内存超过这个数值时, 将触发数据淘汰。该数据配置为0时,表示缓存的数据量没有限制, 即LRU功能不生效。64位的系统默认值为0,32位的系统默认内存限制为3GB
  • maxmemory_policy: 触发数据淘汰后的淘汰策略
  • maxmemory_samples: 随机采样的精度,也就是随即取出key的数目。该数值配置越大, 越接近于真实的LRU算法,但是数值越大,相应消耗也变高,对性能有一定影响,样本值默认为5。

我们知道,LRU算法需要一个双向链表来记录数据的最近被访问顺序,但是出于节省内存的考虑,RedisLRU算法并非完整的实现。Redis并不会选择最久未被访问的键进行回收,相反它会尝试运行一个近似LRU的算法,通过对少量键进行取样,然后回收其中的最久未被访问的键。通过调整每次回收时的采样数量maxmemory-samples,可以实现调整算法的精度。

根据Redis作者的说法,每个Redis Object可以挤出24 bits的空间,但24 bits是不够存储两个指针的,而存储一个低位时间戳是足够的,Redis Object以秒为单位存储了对象新建或者更新时的unix time,也就是LRU clock,24 bits数据要溢出的话需要194天,而缓存的数据更新非常频繁,已经足够了。

Redis的键空间是放在一个哈希表中的,要从所有的键中选出一个最久未被访问的键,需要另外一个数据结构存储这些源信息,这显然不划算。最初,Redis只是随机的选3个key,然后从中淘汰,后来算法改进到了N个key的策略,默认是5个。

Redis3.0之后又改善了算法的性能,会提供一个待淘汰候选key的pool,里面默认有16个key,按照空闲时间排好序。更新时从Redis键空间随机选择N个key,分别计算它们的空闲时间idle,key只会在pool不满或者空闲时间大于pool里最小的时,才会进入pool,然后从pool中选择空闲时间最大的key淘汰掉。

真实LRU算法与近似LRU的算法可以通过下面的图像对比: img

浅灰色带是已经被淘汰的对象,灰色带是没有被淘汰的对象,绿色带是新添加的对象。可以看出,maxmemory-samples值为5时Redis 3.0效果比Redis 2.8要好。使用10个采样大小的Redis 3.0的近似LRU算法已经非常接近理论的性能了。

数据访问模式非常接近幂次分布时,也就是大部分的访问集中于部分键时,LRU近似算法会处理得很好。

Redis为什么不使用原生LRU算法?

  • 原生LRU算法需要 双向链表 来管理数据,需要额外内存
  • 数据访问时涉及数据移动,有性能损耗
  • Redis现有数据结构需要改造

LFU

LFU算法中,可以为每个key维护一个计数器。每次key被访问的时候,计数器增大。计数器越大,可以约等于访问越频繁。

上述简单算法存在两个问题:

  • LRU算法中可以维护一个双向链表,然后简单的把被访问的节点移至链表开头,但在LFU中是不可行的,节点要严格按照计数器进行排序,新增节点或者更新节点位置时,时间复杂度可能达到O(N)。
  • 只是简单的增加计数器的方法并不完美。访问模式是会频繁变化的,一段时间内频繁访问的key一段时间之后可能会很少被访问到,只增加计数器并不能体现这种趋势。

第一个问题很好解决,可以借鉴LRU实现的经验,维护一个待淘汰key的pool。第二个问题的解决办法是,记录key最后一个被访问的时间,然后随着时间推移,降低计数器。

Redis对象的结构如下:

1
2
3
4
5
6
7
8
9
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;

LRU算法中,24 bits的lru是用来记录LRU time的,在LFU中也可以使用这个字段,不过是分成16 bits与8 bits使用:

1
2
3
4
     16 bits      8 bits
+----------------+--------+
+ Last decr time | LOG_C |
+----------------+--------+

高16 bits用来记录最近一次计数器降低的时间ldt,单位是分钟,低8 bits记录计数器数值counter

LFU配置

Redis4.0之后为maxmemory_policy淘汰策略添加了两个LFU模式:

  • volatile-lfu:对有过期时间的key采用LFU淘汰算法
  • allkeys-lfu:对全部key采用LFU淘汰算法

还有2个配置可以调整LFU算法:

1
2
lfu-log-factor 10
lfu-decay-time 1

lfu-log-factor可以调整计数器counter的增长速度,lfu-log-factor越大,counter增长的越慢。

lfu-decay-time是一个以分钟为单位的数值,可以调整counter的减少速度

参考: