前言 Redis作为缓存使用时,一些场景下要考虑内存的空间消耗问题。Redis会删除过期键以释放空间,过期键的删除策略有两种: 惰性删除:每次从键空间中获取键时,都检查取得的键是否过期,如果过期的话,
前言
Redis作为缓存使用时,一些场景下要考虑内存的空间消耗问题。Redis会删除过期键以释放空间,过期键的删除策略有两种:
另外,Redis也可以开启LRU功能来自动淘汰一些键值对。
LRU算法
当需要从缓存中淘汰数据时,我们希望能淘汰那些将来不可能再被使用的数据,保留那些将来还会频繁访问的数据,但最大的问题是缓存并不能预言未来。一个解决方法就是通过LRU进行预测:最近被频繁访问的数据将来被访问的可能性也越大。缓存中的数据一般会有这样的访问分布:一部分数据拥有绝大部分的访问量。当访问模式很少改变时,可以记录每个数据的最后一次访问时间,拥有最少空闲时间的数据可以被认为将来最有可能被访问到。
举例如下的访问模式,A每5s访问一次,B每2s访问一次,C与D每10s访问一次,|代表计算空闲时间的截止点:
~~~~~A~~~~~A~~~~~A~~~~A~~~~~A~~~~~A~~|
~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~|
~~~~~~~~~~C~~~~~~~~~C~~~~~~~~~C~~~~~~|
~~~~~D~~~~~~~~~~D~~~~~~~~~D~~~~~~~~~D|
可以看到,LRU对于A、B、C工作的很好,完美预测了将来被访问到的概率B>A>C,但对于D却预测了最少的空闲时间。
但是,总体来说,LRU算法已经是一个性能足够好的算法了
LRU配置参数
Redis配置中和LRU有关的有三个:
淘汰策略
淘汰策略即maxmemory_policy的赋值有以下几种:
volatile-lru, volatile-random和volatile-ttl这三个淘汰策略使用的不是全量数据,有可能无法淘汰出足够的内存空间。在没有过期键或者没有设置超时属性的键的情况下,这三种策略和noeviction差不多。
一般的经验规则:
volatile-lru 和 volatile-random策略,当你想要使用单一的Redis实例来同时实现缓存淘汰和持久化一些经常使用的键集合时很有用。未设置过期时间的键进行持久化保存,设置了过期时间的键参与缓存淘汰。不过一般运行两个实例是解决这个问题的更好方法。
为键设置过期时间也是需要消耗内存的,所以使用allkeys-lru这种策略更加节省空间,因为这种策略下可以不为键设置过期时间。
近似LRU算法
我们知道,LRU算法需要一个双向链表来记录数据的最近被访问顺序,但是出于节省内存的考虑,Redis的LRU算法并非完整的实现。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的算法可以通过下面的图像对比:
浅灰色带是已经被淘汰的对象,灰色带是没有被淘汰的对象,绿色带是新添加的对象。可以看出,maxmemory-samples值为5时Redis 3.0效果比Redis 2.8要好。使用10个采样大小的Redis 3.0的近似LRU算法已经非常接近理论的性能了。
数据访问模式非常接近幂次分布时,也就是大部分的访问集中于部分键时,LRU近似算法会处理得很好。
在模拟实验的过程中,我们发现如果使用幂次分布的访问模式,真实LRU算法和近似LRU算法几乎没有差别。
LRU源码分析
Redis中的键与值都是redisObject对象:
typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:LRU_BITS;
int refcount;
void *ptr;
} robj;
--结束END--
本文标题: Redis中LRU淘汰策略的深入分析
本文链接: https://www.lsjlt.com/news/50961.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-05-03
2024-05-03
2024-05-03
2024-05-03
2024-05-03
2024-05-03
2024-05-03
2024-05-03
2024-05-03
2024-05-03
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0