Redis
作为缓存使用时,一些场景下要考虑内存的空间消耗问题。Redis
会删除过期键以释放空间,过期键的删除策略有两种:
另外,Redis
也可以开启LRU
功能来自动淘汰一些键值对。
当需要从缓存中淘汰数据时,我们希望能淘汰那些将来不可能再被使用的数据,保留那些将来还会频繁访问的数据,但最大的问题是缓存并不能预言未来。一个解决方法就是通过LRU
进行预测:最近被频繁访问的数据将来被访问的可能性也越大。缓存中的数据一般会有这样的访问分布:一部分数据拥有绝大部分的访问量。当访问模式很少改变时,可以记录每个数据的最后一次访问时间,拥有最少空闲时间的数据可以被认为将来最有可能被访问到。
举例如下的访问模式,A每5s访问一次,B每2s访问一次,C与D每10s访问一次,|
代表计算空闲时间的截止点:
可以看到,LRU
对于A、B、C工作的很好,完美预测了将来被访问到的概率B>A>C,但对于D却预测了最少的空闲时间。
但是,总体来说,LRU
算法已经是一个性能足够好的算法了
Redis
配置中和LRU
有关的有三个:
淘汰策略即maxmemory_policy
的赋值有以下几种:
volatile-lru
, volatile-random
和volatile-ttl
这三个淘汰策略使用的不是全量数据,有可能无法淘汰出足够的内存空间。在没有过期键或者没有设置超时属性的键的情况下,这三种策略和noeviction
差不多。
一般的经验规则:
volatile-lru
和 volatile-random
策略,当你想要使用单一的Redis
实例来同时实现缓存淘汰和持久化一些经常使用的键集合时很有用。未设置过期时间的键进行持久化保存,设置了过期时间的键参与缓存淘汰。不过一般运行两个实例是解决这个问题的更好方法。
为键设置过期时间也是需要消耗内存的,所以使用allkeys-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个。
Redis
3.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
算法几乎没有差别。
Redis
中的键与值都是redisObject
对象:
unsigned
的低24 bits的lru
记录了redisObj
的LRU time。
Redis命令访问缓存的数据时,均会调用函数lookupKey
:
该函数在策略为LRU(非LFU)
时会更新对象的lru
值, 设置为LRU_CLOCK()
值:
LRU_CLOCK()
取决于LRU_CLOCK_RESOLUTION(默认值1000)
,LRU_CLOCK_RESOLUTION
代表了LRU
算法的精度,即一个LRU
的单位是多长。server.hz
代表服务器刷新的频率,如果服务器的时间更新精度值比LRU
的精度值要小,LRU_CLOCK()
直接使用服务器的时间,减小开销。
Redis
处理命令的入口是processCommand
:
只列出了释放内存空间的部分,freeMemoryIfNeededAndSafe
为释放内存的函数:
几种淘汰策略maxmemory_policy
就是在这个函数里面实现的。
当采用LRU
时,可以看到,从0号数据库开始(默认16个),根据不同的策略,选择redisDb
的dict(全部键)
或者expires(有过期时间的键)
,用来更新候选键池子pool
,pool
更新策略是evictionPoolPopulate
:
Redis
随机选择maxmemory_samples
数量的key,然后计算这些key的空闲时间idle time
,当满足条件时(比pool中的某些键的空闲时间还大)就可以进pool。pool更新之后,就淘汰pool中空闲时间最大的键。
estimateObjectIdleTime
用来计算Redis
对象的空闲时间:
空闲时间基本就是就是对象的lru
和全局的LRU_CLOCK()
的差值乘以精度LRU_CLOCK_RESOLUTION
,将秒转化为了毫秒。