redis过期key删除不得不说的事情
2021/4/19 2:26:26
本文主要是介绍redis过期key删除不得不说的事情,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
redis过期key删除不得不说的事情
1.过期key的删除策略
- 定时删除:当为key设置过期时间的时候,设置一个定时任务,到时间后即刻调用并删除
- 定期删除:每隔一定的时间,对某些key进行扫描,并删除掉其中已经过期的key
- 惰性删除:不进行任何操作,只有访问到当前key时,如果已经过期再去删除该key
定时删除策略对于内存来说是最友好的,过期的key立刻被删除,不会过多的占用内存,但是会消耗大部分的时间片,对cpu很不友好。
惰性删除平时不做任何操作,只有key被访问到的时候才会进行判断与删除,对于cpu非常友好,但是这些已经过期的key会占用大量的内存,造成极大的浪费。
定期删除是每隔一段时间进行一次扫描,这是一种折衷的方案,既不会对cpu造成很高的负担,也不会让大量过期的key未被删除而造成浪费,但是对于扫描的频率和时间间隔设置较为复杂,如果设置的不科学,也会产生与其他方式类似的问题。
redis使用了后面两种方式来进行过期key的删除,在内存使用和cpu使用率上做了一定的取舍。与过期key删除策略经常弄混的是redis的内存逐出策略,redis的逐出策略只有在内存容量到达上线maxmemory之后才会使用,平时状态是不会使用的;而redis的过期key删除策略是每次循环都会使用的。
redis的redis的内存逐出策略有八种算法:
- volatile-lru:设置了过期时间的key使用LRU算法淘汰;
- allkeys-lru:所有key使用LRU算法淘汰;
- volatile-lfu:设置了过期时间的key使用LFU算法淘汰;
- allkeys-lfu:所有key使用LFU算法淘汰;
- volatile-random:设置了过期时间的key使用随机淘汰;
- allkeys-random:所有key使用随机淘汰;
- volatile-ttl:设置了过期时间的key根据过期时间淘汰,越早过期越早淘汰;
- noeviction:默认策略,当内存达到设置的最大值时,所有申请内存的操作都会报错,只读命令可以正常执行;
2.redis过期key删除详解
2.1 reids中的字典
redis作为一种k-v数据库,支持多种数据类型,这些数据的保存都和一个结构体redisDB相关。在redis中,有一个链表用来做数据上的逻辑区分,链表上的每个节点都是一个redisDb,编号从0到n(可以在配置文件中修改,默认为16,通过select命令可以切换编号,编号对应结构体中的id字段)。
typedef struct redisDb { dict *dict; /* DB的键空间,保存了所有的key */ dict *expires; /* 保存了所有的过期key,dict的子集 */ dict *blocking_keys; /* 实现阻塞客户端使用该字典 */ dict *ready_keys; /* 唤醒阻塞客户端使用该字典 */ dict *watched_keys; /* 实现简单事物使用该字典 */ int id; /* 数据库ID */ long long avg_ttl; /* 平均过期时间 */ }
每次对数据库进行写命令操作时,就会在字典dict中进行相应的操作(增加或者修改),如果对该key的过期时间有操作,则去expires字典中进行操作(增加或者修改)。
字典的实现主要是由下面的结构体来实现,与本文有关的两个结构是ht[2]和rehashidx。ht[2]里面含有两个哈希表,哈希表1用来进行节点的存储,哈希表2通常情况下是空指针,没有被真实分配空间;当哈希表1的负载因子达到了扩容的要求时,则对哈希表2进行内存分配,用于进行哈希表扩容。由于redis主线程是单线程的reactor模型,为了防止rehash造成线程阻塞,所以redis采用了渐进式rehash来进行哈希表的扩缩容,每次对一定数量的槽位进行rehash,并将下一次需要进行rehash的槽位索引位置保存在rehashidx中,方便下一次进行rehash。
// 字典结构体 typedef struct dict { dictType *type; /* 保存了一些功能函数 */ void *privdata; /* 保存一些数据用于修改字典 */ dictht ht[2]; /* 哈希表 */ long rehashidx; /* rehash进行到的索引位置 */ unsigned long iterators; /* 当前迭代器的运行数量 */ }
redis中的哈希表的实现方式可以归结为数组加链表,使用拉链法(链地址法)来解决哈希地址冲突;哈希表的槽位(哈希桶)个数为2^n个,每次扩缩容的结果都是2的幂次。 进行key操作的时候,首先计算放入的索引位置,idx=hash(key)%sizemark,由于掩码的值为 2^n-1,所以这里的取模运算可以简化为按位与,提高运算速度。
typedef struct dictht { dictEntry **table; // 哈希槽数组 unsigned long size; // 哈希槽的个数(数组长度) unsigned long sizemask; // 哈希掩码,size-1 unsigned long used; // 哈希表实际所拥有的元素个数 } dictht;
哈希表里有一个重要的指标:负载因子,可以通过used/size来计算。当负载超过一定限制的时候,需要进行扩容。与java不同的是,redis的哈希表在某个槽位过多的时候,并不会转化为红黑树;同时在负载因子过高的时候,进行渐进式的rehash。
- 当没有bgsave或者bgrewriteaof的时候,负载因子大于1.0时
- 当进行bgsave或者bgrewriteaof的时候,负载因子大于5.0时
- 当为ht[1]预分配空间后,内存超过了maxmemory且负载因子大于1.618时(黄金比例0.618的倒数,此功能在redis6.2版本加入)
redis从4.0之后开始使用siphash算法来进行运算,相比之前相比(murmurhash)提高了运行速度,并且降低了哈希碰撞的概率,可以有效防止hash-dos。一个良好的hash算法能够将key分散的比较均匀,在负载因子较小的情况下,可以保证每个槽位上的元素个数都是比较少的。hash表中每个槽位上的元素个数符合Poisson分布:
当负载因子为0.5时,每个槽位上的元素个数概率分布如下所示: P(x=k) = exp(-0.5) * pow(0.5, k) / factorial(k) *0 0.606530659713 *1 0.303265329856 *2 0.0758163324641 *3 0.0126360554107 *4 0.00157950692633 *5 0.000157950692633 *6 1.31625577195e-05 *7 9.40182694247e-07 *8 5.87614183904e-08 当元素个数多于8个时,概率小于千万分之一 当负载因子为1.0时,每个槽位上当元素个数如下所示: P(x=k) = exp(-1) * pow(1, k) / factorial(k) *0 0.367879441171 *1 0.367879441171 *2 0.183939720586 *3 0.0613132401952 *4 0.0153283100488 *5 0.00306566200976 *6 0.000510943668294 *7 7.29919526134e-05 *8 9.12399407667e-06 当元素个数多于8个时,概率约为十万分之一
在正常情况下,每个哈希槽位上的节点一般都很少,可以认为在常数级时间复杂度O(1) 获取到元素。
2.2 redis的内存删除逻辑
2.2.1 redis的事件驱动模型
redis是一个单线程事件驱动的模型,主线程主要在aeMain中进行,通过配置文件中的属性hz来确定每秒钟含有几个循环周期,默认为10。redis在初始化和加载后,就在aeMain中进行循环,直到接收到信号或发生错误才会退出,每个周期都会按照如下步骤进行处理:
- a.处理beforesleep回调函数相关功能
- b.处理时间事件
- c.处理aftersleep回调函数相关功能
- d.处理文件事件
- e.进入下一次循环(回到a)
void aeMain(aeEventLoop *eventLoop) { eventLoop->stop = 0; while (!eventLoop->stop) { if (eventLoop->beforesleep != NULL) eventLoop->beforesleep(eventLoop); aeProcessEvents(eventLoop, AE_ALL_EVENTS|AE_CALL_AFTER_SLEEP); } }
- beforesleep回调函数主要功能有进行一次快速的过期key淘汰,发送命令要求slave上报backlog偏移量,尝试释放blocking的客户端,aof文件刷盘等
- 时间事件主要放在一个无序链表里,正常运行的redis只有一个事件事件ServerCron(redis启动加载数据时,有两个时间事件),发起一次慢速的过期key淘汰,尝试进行rehash,发送定时心跳,检测部分后台bio线程的状态等
- aftersleep回调函数目前只有module相关功能的处理
- 文件事件主要是通过io多路复用功能,获取就绪的文件事件进行相应的读写处理
2.2.2 redis过期key删除的实现
这里使用了pyhton的伪代码代替了原始的c代码做说明,主要承接上文介绍了两种清理模式(快速清理和慢速清理),这个函数是过期key淘汰功能的核心,可以动态的调节cpu用在扫描过期键的时间,当过期键较少时,使用更少的cpu时间片;当过期key较多时,则会表现的比较激进。
在beforesleep回调函数调用时,会尝试一次快速清理功能,这种清理最大能持续EXPIRE_FAST_CYCLE_DURATION时间,并且在相同的时间内不会重复调用;在aftersleep回调函数阶段,会调用慢速清理功能,最大能调用每个redis处理周期ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC百分比的时间片。
通常情况下慢速淘汰功能能够淘汰大量的key,只有频繁触发时间限制的时候,说明慢速清理还剩下很多过期的key没有清理,需要穿插一些快速清理功能来尽可能的删除过期key。
ACTIVE_EXPIRE_CYCLE_SLOW = 0 # type标志位,持续时间比较久的慢速清理模式 ACTIVE_EXPIRE_CYCLE_FAST = 1 # type标志位,持续时间比短的快速清理模式 ACTIVE_EXPIRE_CYCLE_FAST_DURATION = 1000 # 快速清理模式的最长持续时间,单位:微秒 ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP = 20 # 每次扫描随机抽取的key个数 ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC = 25 # 扫描key所占用的cpu最长时间片 CRON_DBS_PER_CALL = 16 # 每次随机扫描的db个数 dbnums = 0 # server里面设置了多少个redisDb的逻辑分区 current_db = 0 # 当前遍历到的数据库编号 timelimit_exit = 0 # flag标识位,用于判断是否是到达了时间上限才退出循环 last_fast_cycle = 0 # 上一次快速淘汰开始的时间 def activeExpireCycle(type): # 获取现在的运行时间,用于信息push和计算是否需要退出的baseline start = time.time() # 设定每次需要遍历的数据库 dbs_per_call = CRON_DBS_PER_CALL if type == ACTIVE_EXPIRE_CYCLE_FAST: # 如果上一次扫描没有触发时间限制就退出了,说明过期key数量不多,不要浪费性能在扫描key上 if not timelimit_exit: return # 如果距离上次快速淘汰开始的时间间隔小于2倍的快速淘汰持续时间,直接返回 if start < last_fast_cycle + ACTIVE_EXPIRE_CYCLE_FAST_DURATION * 2: return # 设定本次快速淘汰开始的时间,为下一次调用做时间baseline last_fast_cycle = start # 如果每次扫描的数据库数量大于实际系统分配的逻辑分区数量,按照实际逻辑分区数量进行扫描 # 如果上次扫描触发了时间限制,说明过期key比较多,需要进行全部逻辑分区的扫描 if dbs_per_call > server.dbnum or timelimit_exit: dbs_per_call = dbnums # 计算本次循环最多能持续的时间,1000000微秒*(25/100)/ 10 # 1秒钟10hz,每次redis的处理周期为100毫秒(100000微秒),25%cpu时间分片就是25000微秒 timelimit = 1000000 * ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC / server.hz / 100 # 如果是快速清理模式,则每次最多能持续1000微秒 if type == ACTIVE_EXPIRE_CYCLE_FAST: timelimit = ACTIVE_EXPIRE_CYCLE_FAST_DURATION # 遍历指定数量(dbs_per_call)的数据库 for i in range(0, dbs_per_call): # 如果触发了时间限制,直接退出循环 if time.time() - start > timelimit: break # 当前数据库中不存在过期的key,直接扫描下一个数据库 if redisDb[i].expires.size() == 0: continue # 如果当前数据库含有过期时间的key数量小于1%,直接扫描下一个数据库 if redisDb[i].expires.size() * 100.0 / redisDb[i].dict.size() < 1: continue while True: # 获取每次扫描的key的数量 lookup_nums = min(redisDb[i].expires.size(), ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP) # 已经过期的key的数量 expired = 0 while lookup_nums > 0: # 随机获取一个key判断是否过期 lookup_key = random_get_key_from_expire(redisDb[i]) # 如果过期了,就删除 if is_expire(lookup_key): del (lookup_key) expired += 1 # 判断当前时刻是否触发了时间限制,如果触发了限制,直接退出 if time.time() - start > timelimit: break break # 两个break,不符合python语法,这里表示结束全部的循环 # 如果本次循环扫描出来的key已经过期的比例小于25%,则去扫描下一个数据库 # 否则说明本数据库过期的key较多,立刻在本数据库中再次扫描和清理 if expired * 4 / lookup_nums < 1: break
2.2.3 redis过期key优化点
上文中提到了,过期key是随机从全部的含有过期时间的key中进行选择。使用的算法如下,这里存在的不足是,当过期key数量较少时,哈希桶槽位上大部分的元素为空,随机数生成后所得到的哈希桶槽位经常miss,需要再次进行随机,会消耗过多的时间片在生成随机数上,而不是清理过期key。
def random_get_key_from_expire(redisDb): slot_nums = 0 # 如果在进行rehash,则两个哈希表都可能有key存在,需要从中随机选择一个 if (is_rehash(redisDb.expires)): slot_nums = ht[0].size + ht[1].size else: slot_nums = ht[0].size headEntry = None while True: # 从所有的槽位中随机选择一个 slot_idx = random.randint(0, slot_nums) # 直到找到一个槽位不为空的哈希桶,就停止循环 if (slot_idx > ht[0].size): # 如果所得到的索引大于ht[0]的大小,说明落在了ht[1]中 tempEntry = ht[1].get_index(slot_idx - ht[0].size) if tempEntry != None: headEntry = tempEntry break else: tempEntry = ht[0].get_index(slot_idx) if tempEntry != None: headEntry = tempEntry break currEntry = headEntry len = 0 # 遍历链表获得长度 while currEntry.next: currEntry = currEntry.next len += 1 # 从链表中随机选择一个节点返回 listele = random.randint(0, len) while listele: headEntry = headEntry.next listele -= 1 return headEntry
此外,如果redis的写入量比较大,且key过期时间比较短,即使两种淘汰方式同时进行,也会超过redis的处理能力,依然会造成数据的堆积,如果容量继续上涨超过,就会进行内存淘汰(使用allkeys-lru淘汰策略,会优先删除lru较小的key,由于惰性删除的原因,已过期的key的lru会通常情况下比较小,会被优先逐出)。由于走了另外一套逻辑(逐出逻辑)造成了cpu时间片的浪费,它们最终的结果都是key删除,但是却进行了不同的筛选策略。实际使用场景中遇到这种情况的时刻不多,对于性能和吞吐量的影响不大,但是也是一个可以优化的点。
实际使用中,还有一种人为触发过期key淘汰的方法,就是通过scan命令来进行全库的扫描,通过控制scan命令的游标和count数量,可以预期的控制淘汰的激烈程度,不会对主线程造成阻塞。redis在进行key的删除的时候,如果开启了异步删除,则当被删除的key所对应的val占用空间大于64字节时,会将这个key标记为删除后直接返回+OK,然后将val放到后台的bio线程里面进行删除,防止阻塞主线程;如果占用的空间小于64字节,即使开启了异步删除,在最后运行的时候也会同步的进行删除(redis优秀的性能优化在细节之末随处可见,针对很多场景都做了优化,并抽象出参数给用户动态配置,它的高性能是与redis作者精益求精的修改分不开的)。
2.2.4 redis6对过期key删除的优化
redis6针对以上的问题提出了几个改进点,首先将原来的随机抽样检查过期key变成了按照哈希桶顺序遍历检查过期key。通过在redisDb结构体中增加long expires_cursor字段,用来记录上一次遍历到的游标位置,每次遍历都会取到这个游标位置对应的索引,然后继续下去,使得cpu的时间片更多的用来进行key过期的判断和删除上。
typedef struct redisDb { dict *dict; dict *expires; dict *blocking_keys; dict *ready_keys; dict *watched_keys; int id; long long avg_ttl; unsigned long expires_cursor; /* 主动过期循环的游标*/ list *defrag_later; /* key组成的链表,用来进行内存碎片整理 */ } redisDb;
另外在server的配置中增加了activate_expire_effort标识位,可以被设定为1-10,用来表示定期删除淘汰key的激烈程度。在系统设定好activate_expire_effort之后,redis的定期删除循环逻辑每次都会重新计算阈值,比如快速淘汰循环最大的持续时间,慢速淘汰循环最大的持续时间,这些参数在之前的淘汰算法中都是一个确定的值。通过抽象成一个配置文件的参数,可以通过命令热加载动态的调节,达到redis吞吐量和容量使用的“均衡”。
struct redisServer { ... int active_expire_enabled; /* Can be disabled for testing purposes. */ int active_expire_effort; /* From 1 (default) to 10, active effort. */ ... }
ACTIVE_EXPIRE_CYCLE_SLOW = 0 # type标志位,持续时间比较久的慢速清理模式 ACTIVE_EXPIRE_CYCLE_FAST = 1 # type标志位,持续时间比短的快速清理模式 ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP = 20 # 每次每个db扫描的key个数 ACTIVE_EXPIRE_CYCLE_FAST_DURATION = 1000 # 快速清理模式的最长持续时间,这里只是一个基线 ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC = 25 # 扫描key所占用的cpu最长时间片 ACTIVE_EXPIRE_CYCLE_ACCEPTABLE_STALE = 10 # 开启efforts后,过期key占据的百分比 CRON_DBS_PER_CALL = 16 # 每次随机扫描的db个数 current_db = 0 # 当前遍历到的数据库编号 timelimit_exit = 0 # flag标识位,用于判断是否是到达了时间上限才退出循环 last_fast_cycle = 0 # 上一次快速淘汰开始的时间 def activeExpireCycle(type): # 一个统计量,表示系统对于过期key扫描的激进程度(0~9) # 该配置可以通过配置文件来进行设置,根据集群的平均过期时间,动态的设定 effort = server.active_expire_effort - 1, # 每次循环扫描的key的数量 config_keys_per_loop = ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP + ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP / 4 * effort # 快速清理循环的持续时间 config_cycle_fast_duration = ACTIVE_EXPIRE_CYCLE_FAST_DURATION + ACTIVE_EXPIRE_CYCLE_FAST_DURATION / 4 * effort # 清理循环周期所占用的最大cpu时间片百分比 config_cycle_slow_time_perc = ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC + 2 * effort # 有过期时间的key所全部key占的最多的百分比 config_cycle_acceptable_stale = ACTIVE_EXPIRE_CYCLE_ACCEPTABLE_STALE - effort # 全局变量,函数退出后值仍然保存,留待下一次函数调用 global last_fast_cycle global current_db global timelimit_exit start = time.time() dbs_per_call = CRON_DBS_PER_CALL iteration = 0 if type == ACTIVE_EXPIRE_CYCLE_FAST: # 如果上一次扫描没有触发时间限制就退出,并且系统所含有的过期key的比例小于配置的阈值直接返回 # 因为此时过期快key的数量不多,并不需要浪费过多的cpu时间片在扫描过期key上 if (not timelimit_exit) and (server.stat_expired_stale_perc < config_cycle_acceptable_stale): return # 如果距离上次快速周期循环开始的时间间隔小于2倍的快速周期循环持续时间,直接返回 if start < last_fast_cycle + config_cycle_fast_duration * 2: return # 设定本次快速淘汰开始的时间,为下一次调用做时间baseline last_fast_cycle = start # 如果每次扫描的数据库数量大于实际系统分配的逻辑分区数量,按照实际逻辑分区数量进行扫描 # 如果上次扫描触发了时间限制,说明过期key比较多,需要进行全部逻辑分区的扫描 if dbs_per_call > server.dbnum or timelimit_exit: dbs_per_call = server.dbnums # 计算本次循环最多能持续的时间,1000000微秒*(25/100)/ 10 # 1秒钟10hz,每次redis的处理周期为100毫秒(100000微秒),25%cpu时间分片就是25000微秒 # 如果设置了effort,则会增加用于过期key删除的cpu时间片,例如effort=6,那么将有35000微秒用于处理过期key timelimit = 1000000 * config_cycle_slow_time_perc / server.hz / 100 # 如果是快速清理模式,则每次最多能持续config_cycle_fast_duration微秒 if type == ACTIVE_EXPIRE_CYCLE_FAST: timelimit = config_cycle_fast_duration # 遍历指定数量(dbs_per_call)的数据库 for i in range(0, dbs_per_call): # 如果触发了时间限制,直接退出循环 if time.time() - start > timelimit: break # 获取每次要扫描的数据库编号,并记录下来,这样可以让cpu将时间片公平的分给每个数据库 db_idx = current_db % server.dbnum # 先变更下一次要扫描的数据库,方式程序因超时返回时忘记变更需要扫描的数据库, # 也是为了将时间片公平的分散到每个数据库 db_idx += 1 while True: # 当前数据库中不存在过期的key,直接扫描下一个数据库 if redisDb[db_idx].expires.size() == 0: break # 如果当前数据库含有过期时间的key数量小于1%,直接扫描下一个数据库 if redisDb[db_idx].expires.size() * 100.0 / redisDb[db_idx].dict.size() < 1: break # 获取每次扫描的key的数量 num = redisDb[db_idx].expires.size() if num > config_keys_per_loop: num = config_keys_per_loop # 每次至多只会选择config_keys_per_loop个key进行查询 # 最多遍历的哈希桶数量 max_buckets = num * 20 # 已经遍历的哈希桶数量 checked_buckets = 0 # 已经扫描的过期key的个数 sampled = 0 # 已经过期key的个数 expires = 0 # 如果扫描的哈希桶数量过多或者已经扫描了规定数量的key,就退出循环防止占用过多时间 while sampled < num and checked_buckets < max_buckets: # 字典里只有两个哈希表ht[0],ht[1],每次循环会选择其中的一个 for table in (0, 1): # 没有进行rehash时,ht[1]为空,遍历到此处时直接返回 if table == 1 and is_rehash(redisDb[db_idx].expires): break # 保存了上一次遍历到的哈希桶索引位置 idx = redisDb[db_idx].expires_cursor # 与掩码进行计算,确定本次开始遍历的哈希桶索引位置 idx = idx & redisDb[db_idx].expires.ht[i].sizemark # 获取哈希桶索引位置对应的链表的头节点 dictEntry = redisDb[db_idx].expires.ht[i].bucket[idx] while dictEntry: # 遍历链表,如果过期了就删除,并计数已经过期的key if is_expire(dictEntry): del (dictEntry) expires += 1 dictEntry = dictEntry.next sampled += 1 # 记录下一次要遍历的哈希桶的索引位置 redisDb[db_idx].expires_cursor += 1 # 如果扫描时间过长达到了规定的阈值,则直接返回 if time.time() - start > timelimit: return # 直接返回全部的 # 如果过期的key占比高于阈值,说明当前库里面的过期key很多,需要再次遍历进行淘汰 if expires * 100.0 / sampled > config_cycle_acceptable_stale: continue # 如果扫描到的所有的桶都是空的,触发了max_buckets限制而退出,说明没有清理到过期的key # 过期的key都在其他的桶之中,需要进行再次的扫描 elif sampled == 0: continue else: break
这篇关于redis过期key删除不得不说的事情的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-31Tiny RDM:你的下一代Redis桌面GUI神器-icode9专业技术文章分享
- 2024-03-21redisinsight-v2
- 2024-02-26Typed property App\Api\Mapper\GamePropsConfigMapper::$apiRedis must not be accessed before initia-icode9专业技术文章分享
- 2024-02-21redisson getlock
- 2024-02-20redis config
- 2024-02-20redis leaderboard
- 2024-01-23缓存选型:Redis or MemCache
- 2024-01-22面试官:Redis持久化能关吗?怎么关?
- 2024-01-21Redis压测工具redis-benchmark-icode9专业技术文章分享
- 2024-01-19这才是你应该了解的Redis数据结构!