Redis内存淘汰及回收策略都是Redis内存优化兜底的策略,那它们是如何进行兜底的呢?先来说明一下什么是内存淘汰和内存回收策略:
Redis内存淘汰策略是指当Redis的内存使用超过配置的最大值时,如何选择一些键进行删除,以释放空间给新的数据。Redis提供了八种内存淘汰策略,分别是:
LRU(least frequently used)算法为最近最少使用算法,根据数据的历史访问记录来进行淘汰数据,优先移除最近最少使用的数据,这种算法认为最近使用的数据很大概率将会再次被使用
LFU(least frequently used)算法为最少频率使用算法,优先移除使用频率最少的数据,这种算法认为使用频率高的数据很大概率将会再次被使用
LRU(least frequently used)算法为最近最少使用算法,根据数据的历史访问记录来进行淘汰数据,优先移除最近最少使用的数据,这种算法认为最近使用的数据很大概率将会再次被使用
在算法的选择上,Redis需要能够快速地查询、添加、删除数据,也就是说查询、添加、删除的时间复杂读需为O(1)。哈希表能保证查询数据的时间复杂度为O(1)。而双向链表能保证添加、删除数据的时间复杂度为O(1),如下:
如前文所述,真实的 LRU 算法需要用链表管理所有的数据,每次访问一个数据就要移动链表节点,这样会占用额外的空间和时间。而Redis通过近似 LRU 算法,随机抽样一些键,然后比较它们的访问时间戳,这样可以节省内存和提高性能。而Redis 的近似 LRU 算法的具体实现如下:
redisObject
)中有一个 24 位的 lru 字段,用于记录每个数据最近一次被访问的时间戳lookupKey
函数,如果配置使用了 LRU 模式,该函数会更新 value 中的 lru 字段为当前秒级别的时间戳pool
),大小为 16maxmemory-samples
参数设置,默认为 5),将 lru 字段值最小的键放入候选集合中,并按照 lru 大小排序举个例子,假设我们按照下面的顺序访问缓存中的数据:h,e,l,l,o,w,o,r,l,d
且内存中只能存储3个字符,下面是每次访问或插入后缓存的状态,其中括号内是lru字段的值,假设初始时间戳为0
缓存
状态
访问h
h(0)
访问e
e(1),h(0)
访问l
l(2),e(1),h(0)
访问l
l(3),e(1),h(0)
插入o
o(4),l(3),e(1)
插入w
w(5),o(4),l(3)
访问o
o(6),w(5),l(3)
插入r
r(7),o(6),w(5)
插入l
l(8),r(7),o(6)
插入d
d(9),l(8),r(7)
LFU(Least Frequently Used)是最不经常使用算法,它的思想是淘汰访问频率最低的数据。Redis在3.0版本之后引入了LFU算法,并对lru字段进行了拆分。
typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:LRU_BITS;
int refcount;
void *ptr;
} robj;
我们看lru:LRU_BITS
这个字段,这个字段在LRU算法中的意义是时间戳,精确到秒。而在LFU 算法中,将它拆为两部分前16bits为时间戳,精确到分;后8为则表示该对象在一定时间段内被访问的次数。
当Redis需要淘汰数据时,它会从内存中随机抽取一定数量(默认为5个,可以通过 maxmemory-samples
参数设置)的键值对对象,然后比较它们的访问次数和访问时间戳,找出其中最小的那个,也就是最不经常使用且最早被访问的那个,将其从内存中删除。
例如,假设我们有以下键值对和频率计数器:
键
值
频率
A
1
3
B
2
2
C
3
1
D
4
4
如果我们要添加一个新的键值对(E,5),并且缓存已经满了,那么我们就需要淘汰一个旧的键值对。我们可以随机选择A,B,C中的一个,并且发现C的频率最低,为1,所以我们就淘汰C,并且添加E到缓存中,并且将E的频率设为1。这样,缓存中的数据就变成了:
键
值
频率
A
1
3
B
2
2
D
4
4
E
5
1
在选择上,需要根据不同的适用场景选择不同策略,如下:
策略
特点
适用场景
noeviction
不删除任何数据,当内存不足时返回错误
数据都是永久有效的,且内存足够大
allkeys-lru
根据所有数据的访问时间来淘汰最久未访问的数据
数据都是永久有效的,且访问时间具有明显规律
volatile-lru
根据设置了过期时间的数据的访问时间来淘汰最久未访问的数据
数据都有过期时间,且访问时间具有明显规律
allkeys-random
随机淘汰所有类型的数据
数据都是永久有效的,且访问时间没有明显规律
volatile-random
随机淘汰设置了过期时间的数据
数据都有过期时间,且访问时间没有明显规律
volatile-ttl
根据设置了过期时间的数据的剩余生命周期来淘汰即将过期的数据
数据都有过期时间,且剩余生命周期具有明显规律
allkeys-lfu
根据所有数据的访问频率来淘汰最少访问的数据
数据都是永久有效的,且访问频率具有明显规律
volatile-lfu
根据设置了过期时间的数据的访问频率来淘汰最少访问的数据
数据都有过期时间,且访问频率具有明显规律
根据8种策略的特性,也从数据完整性、缓存命中率及淘汰效率这三个方面详细对比了,如下:
数据完整性(是否会删除永久有效的数据)
noeviction
、 volatile-lru
、volatile-lfu
和volatile-random
都可以保证数据完整性,因为它们不会删除永久有效的数据allkeys-lru
、allkeys-lfu
和allkeys-random
系列的策略则会影响数据完整性,因为它们会无差别地删除所有类型的数据缓存命中率(是否能够尽可能保留最有价值的数据)
allkeys-lru
和 volatile-lru
策略可以提高缓存命中率,因为它们会根据数据的访问时间来淘汰数据allkeys-random
和 volatile-random
策略则会降低缓存命中率,因为它们会随机淘汰数据allkeys-lfu
和 volatile-lfu
策略也可以提高缓存命中率,因为它们会根据数据的访问频率来淘汰数据volatile-ttl
策略则会降低缓存命中率
,因为它会根据数据的剩余生命周期来淘汰数据淘汰效率(是否能够快速地找到并删除目标数据)
allkeys-random
和 volatile-random
策略可以提高执行效率,因为它们只需要随机选择一些数据进行删除allkeys-lru
和 volatile-lru
策略则会降低执行效率,因为它们需要对所有或部分数据进行排序allkeys-lfu
和 volatile-lfu
策略也会降低执行效率,因为它们需要对所有或部分数据进行计数和排序volatile-ttl
策略则会提高执行效率,因为它只需要对设置了过期时间的数据进行排序Redis的过期键删除有两种方式,一种是定期删除,一种是惰性删除
Redis惰性删除是指当一个键过期后,它并不会立即被删除,而是在客户端尝试访问这个键时,Redis会检查这个键是否过期,如果过期了,就会删除这个键。惰性删除由db.c/expireIfNeeded
函数实现。
惰性删除的优点是节约CPU性能,发现必须删除的时候才删除。缺点是内存压力很大,出现长期占用内存的数据。惰性删除是Redis的默认策略,它不需要额外的配置。
惰性删除的缺点是可能会导致过期键长时间占用内存,如果访问频率较低的键过期了,但没有被访问到,那么它们就不会被惰性删除,从而浪费内存空间。
为了解决这个问题,Redis还采用了定期删除和内存淘汰机制来配合惰性删除,以达到更好的清理效果
Redis会将设置了过期时间的键放到一个独立的字典中,称为过期字典。Redis会对这个字典进行每秒10次(由配置文件中的hz参数控制)的过期扫描,过期扫描不会遍历字典中所有的键,而是采用了一种简单的贪心策略。该策略的删除逻辑如下:
这种策略可以在一定程度上保证过期键能够及时被删除,同时也避免了对CPU时间的过度占用。但是它也有一些缺点,比如可能会误删一些有效的键(因为随机性),或者漏删一些无效的键(因为限制了扫描时间)
因此,Redis还结合了惰性删除策略,即在每次访问一个键之前,都会检查这个键是否过期,如果过期就删除,然后返回空值。这样可以保证不返回过期的数据,也可以节省CPU时间,但是它可能会导致一些过期的键长期占用内存,如果这些键很少被访问或者一直不被访问,那么它们就永远不会被删除
Redis内存淘汰、内存回收策略相关的配置文件如下:
# 内存淘汰策略
maxmemory-policy noeviction
# 抽取数量
maxmemory-samples 5
# 最大内存
maxmemory 100mb
# 内存淘汰韧性
maxmemory-eviction-tenacity 10
# 后台任务执行间隔
hz 10
# 是否开启动态间隔
dynamic-hz yes
配置文件说明:
hz
的配置值将作为基线,将hz的实际值设置为hz的配置值的整数倍,用来节省CPU资源。总结如下:
手机扫一扫
移动阅读更方便
你可能感兴趣的文章