• 进入"运维那点事"后,希望您第一件事就是阅读“关于”栏目,仔细阅读“关于Ctrl+c问题”,不希望误会!

Redis内存淘汰策略

Redis 彭东稳 8年前 (2016-08-16) 24923次浏览 已收录 0个评论

Redis使用场景

Redis内存淘汰指的是用户存储的一些键被可以被Redis主动地从实例中删除,从而产生读miss的情况,那么Redis为什么要有这种功能?这就是我们需要探究的设计初衷。Redis最常见的两种应用场景为缓存和持久存储,首先要明确的一个问题是内存淘汰策略更适合于那种场景?是持久存储还是缓存?这个问题很显然的我就不回答了。

当Redis被当做缓存来使用,当你新增数据时,让它自动地回收旧数据是件很方便的事情。这个行为在开发者社区非常有名,因为它是流行的memcached系统的默认行为。而LRU是Redis唯一支持的回收方法。本页面包括一些常规话题,Redis的maxmemory指令用于将可用内存限制成一个固定大小,还包括了Redis使用的LRU算法,这个实际上只是近似的LRU。

如何开启淘汰策略?

maxmemory配置指令用于配置Redis存储数据时指定限制的内存大小。通过redis.conf可以设置该指令,或者之后使用CONFIG SET命令来进行运行时配置。

例如为了配置内存限制为100mb,以下的指令可以放在redis.conf文件中。

当指定的内存限制大小达到时,需要选择不同的行为,也就是策略。 Redis可以仅仅对命令返回错误,这将使得内存被使用得更多,或者回收一些旧的数据来使得添加数据时可以避免内存限制。

至于这个值到底有什么意义,我们可以通过了解内存淘汰的过程来理解它的意义:

  1. 客户端发起了需要申请更多内存的命令(如set)。
  2. Redis检查内存使用情况,如果已使用的内存大于maxmemory则开始根据用户配置的不同淘汰策略来淘汰内存(key),从而换取一定的内存。
  3. 如果上面都没问题,则这个命令执行成功。

maxmemory为0的时候表示我们对Redis的内存使用没有限制。对于64位的系统这是个默认值,对于32位的系统默认内存限制为3GB。

内存淘汰策略

内存淘汰只是Redis提供的一个功能,为了更好地实现这个功能,必须为不同的应用场景提供不同的策略,内存淘汰策略讲的是为实现内存淘汰我们具体怎么做,要解决的问题包括淘汰键空间如何选择?在键空间中淘汰键如何选择?

当maxmemory限制达到的时候,Redis淘汰key的策略由Redis的maxmemory-policy配置指令来进行配置。Redis提供了下面几种淘汰策略供用户选择,其中默认的策略为noeviction策略:

  • noeviction:当内存不足以容纳新写入数据时,新写入操作会报错。
  • allkeys-lru:当内存不足以容纳新写入数据时,在键空间中,移除最近最少使用的key。
  • volatile-lru:当内存不足以容纳新写入数据时,在设置了过期时间的键空间中,移除最近最少使用的key。
  • allkeys-random:当内存不足以容纳新写入数据时,在键空间中,随机移除某个key。
  • volatile-random:当内存不足以容纳新写入数据时,在设置了过期时间的键空间中,随机移除某个key。
  • volatile-ttl:当内存不足以容纳新写入数据时,在设置了过期时间的键空间中,有更早过期时间的key优先移除。
  • volatile-lfu:从所有配置了过期时间的键中驱逐使用频率最少的键。

  • allkeys-lfu:从所有键中驱逐使用频率最少的键。

这里补充一下主键空间和设置了过期时间的键空间,举个例子,假设我们有一批键存储在Redis中,则有那么一个哈希表用于存储这批键及其值,如果这批键中有一部分设置了过期时间,那么这批键还会被存储到另外一个哈希表中,这个哈希表中的值对应的是键被设置的过期时间。设置了过期时间的键空间为主键空间的子集。

如何选择淘汰策略?

我们了解了Redis大概提供了这么几种淘汰策略,那么如何选择呢?

为解决这个问题,我们需要了解我们的应用请求对于Redis中存储的数据集的访问方式以及我们的诉求是什么。同时Redis也支持Runtime修改淘汰策略,这使得我们不需要重启Redis实例而实时的调整内存淘汰策略。

下面看看几种策略的适用场景:

  • allkeys-lru:如果我们的应用对缓存的访问符合幂律分布(也就是存在相对热点数据),或者我们不太清楚我们应用的缓存访问分布状况,我们可以选择allkeys-lru策略。
  • allkeys-random:如果我们的应用对于缓存key的访问概率相等,则可以使用这个策略。
  • volatile-ttl:这种策略使得我们可以向Redis提示哪些key更适合被eviction。

另外,volatile-lru策略和volatile-random策略适合我们将一个Redis实例既应用于缓存和又应用于持久化存储的时候,然而我们也可以通过使用两个Redis实例来达到相同的效果,值得一提的是将key设置过期时间实际上会消耗更多的内存,因此我们建议使用allkeys-lru策略从而更有效率的使用内存。

近似LRU算法

Redis 中的LRU 与常规的 LRU 实现并不相同,一般 LRU 算法的实现基于链表结构,链表中的元素按照操作顺序从前往后排列,最新操作的键会被移动到表头,当需要内存淘汰时,只需要删除链表尾部的元素即可。但是 Redis 的 LRU 并不维护队列,只是根据配置的策略要么从所有的 key 中随机选择 N 个(可配置),要么从所有的设置了过期时间的 key 中选出 N 个键,然后再从这 N 个键中选出最久没有使用的一个 key 进行淘汰。所以 Redis LRU 只是名义上的 LRU 算法,一种近似 LRU 算法,但是实际上被淘汰的键并不一定是真正的最久没用的,这里涉及到一个权衡的问题,如果需要在全部键空间内搜索最优解,则必然会增加系统的开销,Redis 是单线程的,也就是同一个实例在每一个时刻只能服务于一个客户端,所以耗时的操作一定要谨慎。

为了在一定成本内实现相对的 LRU,早期的 Redis 版本是基于采样的 LRU,也就是放弃全部键空间内搜索解改为采样空间搜索最优解。从 Redis 3.0 版本之后,对于基于采样的 LRU 进行了一些优化,目的是在一定的成本内让结果更靠近真实的 LRU。

Redis维护了一个24位时钟,可以简单理解为当前系统的时间戳,每隔一定时间会更新这个时钟。每个key对象内部同样维护了一个24位的时钟,当新增key对象的时候会把系统的时钟赋值到这个内部对象时钟。比如我现在要进行LRU,那么首先拿到当前的全局时钟,然后再找到内部时钟与全局时钟距离时间最久的(差最大)进行淘汰,这里值得注意的是全局时钟只有24位,按秒为单位来表示才能存储194天,所以可能会出现key的时钟大于全局时钟的情况,如果这种情况出现那么就两个相加而不是相减来求最久的key。

Redis 在源码中对于每个键值对中的值,会使用一个 redisObject 结构体来保存指向值的指针,这里先来看下 redisObject 的结构。

当一个键值对被创建的时候,就会记录下更新的时间。

同时一个键值对被访问的时候记录的时间也会被更新,当一个键值对被访问时,访问操作最终都会调用 lookupKey 函数。

上面我们分别看了,创建和访问一个键值对的代码,每次操作,redisObject 中记录的 lru 时间就会被同步的更新。

Redis LRU 有个很重要的点,你通过调整每次回收时检查的采样数量,以实现调整算法的精度。这个参数可以通过以下的配置指令调整:

取样数越高越精准,如果你的 CPU 和内存有足够,可以提高取样数看命中率来探测最佳的采样比例。

Redis 会判断当前内存的使用情况,如果超过了 maxmemory 配置的值,就会触发新的内存淘汰了。

如果内存超过了 maxmemory 的值,这时候还需要去计算需要释放的内存量,这个释放的内存大小等于已使用的内存量减去 maxmemory。不过,已使用的内存量并不包括用于主从复制的复制缓冲区大小。

用来填充evictionPool

处理淘汰的数据,Redis 中提供了一个数组 EvictionPoolLRU,用来保存待淘汰的候选键值对。这个数组的元素类型是 evictionPoolEntry 结构体,该结构体保存了待淘汰键值对的空闲时间 idle、对应的 key 等信息。

可以看到上面会选取一定的过期键,然后插入到 EvictionPoolLRU 中。

dictGetSomeKeys 函数采样的 key 的数量,是由配置项 maxmemory-samples 决定的,该配置项的默认值是 5。

然后通过 evictionPoolPopulate 函数,进行采样,然后将采样数据写入到 EvictionPoolLRU 中,插入到 EvictionPoolLRU 中的数据是按照空闲时间从小到大进行排好序的。

freeMemoryIfNeeded 函数会遍历一次 EvictionPoolLRU 数组,从数组的最后一个 key 开始选择,如果选到的 key 不是空值,那么就把它作为最终淘汰的 key。

每次选中一部分过期的键值对,每次淘汰最久没有使用的那个,如果释放的内存空间还不够,就会重复的进行采样,删除的过程。

为什么要使用近似LRU?

1、性能问题,由于近似LRU算法只是最多随机采样N个key并对其进行排序,如果精准需要对所有key进行排序,这样近似LRU性能更高

2、内存占用问题,Redis对内存要求很高,会尽量降低内存使用率,如果是抽样排序可以有效降低内存的占用

3、实际效果基本相等,如果请求符合长尾法则,那么真实LRU与Redis LRU之间表现基本无差异

LFU

LFU是在Redis4.0后出现的,LRU的最近最少使用实际上并不精确,考虑下面的情况,如果在|处删除,那么A距离的时间最久,但实际上A的使用频率要比B频繁,所以合理的淘汰策略应该是淘汰B。LFU就是为应对这种情况而生的。

A~~A~~A~~A~~A~~A~~A~~A~~A~~A~~~|

B~~~~~B~~~~~B~~~~~B~~~~~~~~~~~~B|

LFU把原来的key对象的内部时钟的24位分成两部分,前16位还代表时钟,后8位代表一个计数器。16位的情况下如果还按照秒为单位就会导致不够用,所以一般这里以时钟为单位。而后8位表示当前key对象的访问频率,8位只能代表255,但是redis并没有采用线性上升的方式,而是通过一个复杂的公式,通过配置如下两个参数来调整数据的递增速度。

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

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

所以这两个因素就对应到了LFU的Counter减少策略和增长策略,它们实现逻辑分别如下。

降低LFUDecrAndReturn

1、先从高16位获取最近的降低时间ldt以及低8位的计数器counter值

2、计算当前时间now与ldt的差值(now-ldt),当ldt大于now时,那说明是过了一个周期,按照65535-ldt+now计算(16位一个周期最大65535)

3、使用第2步计算的差值除以lfu_decay_time,即LFUTimeElapsed(ldt) / server.lfu_decay_time,已过去n个lfu_decay_time,则将counter减少n。

增长LFULogIncr

1、获取0-1的随机数r

2、计算0-1之间的控制因子p,它的计算逻辑如下

3、如果r小于p,counter增长1

p取决于当前counter值与lfu_log_factor因子,counter值与lfu_log_factor因子越大,p越小,r小于p的概率也越小,counter增长的概率也就越小。增长情况如下图:

从左到右表示key的命中次数,从上到下表示影响因子,在影响因子为100的条件下,经过10M次命中才能把后8位值加满到255.

新生KEY策略

另外一个问题是,当创建新对象的时候,对象的counter如果为0,很容易就会被淘汰掉,还需要为新生key设置一个初始counter。counter会被初始化为LFU_INIT_VAL,默认5。

<参考>

https://zhuanlan.zhihu.com/p/105587132


如果您觉得本站对你有帮助,那么可以支付宝扫码捐助以帮助本站更好地发展,在此谢过。
喜欢 (1)
[资助本站您就扫码 谢谢]
分享 (0)

您必须 登录 才能发表评论!