Redis

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 redis中的字典

    redis作为一种k-v数据库，支持多种数据类型，这些数据的保存都和一个结构体redisDB相关。
    在redis中，有一个链表用来做数据上的逻辑区分，链表上的每个节点都是一个redisDb，编号从0到n（可以在配置文件中修改，默认为16，通过select命令可以切换编号，编号对应结构体中的id字段）。

    1. typedef struct redisDb {
    2.   dict *dict;                 /* DB的键空间，保存了所有的key */
    3.   dict *expires;              /* 保存了所有的过期key，dict的子集 */
    4.   dict *blocking_keys;        /* 实现阻塞客户端使用该字典 */
    5.   dict *ready_keys;           /*  唤醒阻塞客户端使用该字典 */
    6.   dict *watched_keys;         /* 实现简单事物使用该字典 */
    7.   int id;                     /* 数据库ID */
    8.   long long avg_ttl;          /* 平均过期时间 */
    9. }

    每次对数据库进行写命令操作时，就会在字典dict中进行相应的操作（增加或者修改），如果对该key的过期时间有操作，则去expires字典中进行操作（增加或者修改）。
    字典的实现主要是由下面的结构体来实现，与本文有关的两个结构是ht[2]和rehashidx。ht[2]里面含有两个哈希表，哈希表1用来进行节点的存储，哈希表2通常情况下是空指针，没有被真实分配空间；当哈希表1的负载因子达到了扩容的要求时，则对哈希表2进行内存分配，用于进行哈希表扩容。
    由于redis主线程是单线程的reactor模型，为了防止rehash造成线程阻塞，所以redis采用了渐进式rehash来进行哈希表的扩缩容，每次对一定数量的槽位进行rehash，并将下一次需要进行rehash的槽位索引位置保存在rehashidx中，方便下一次进行rehash。

    1. // 字典结构体
    2. typedef struct dict {
    3.   dictType *type;  /* 保存了一些功能函数 */
    4.   void *privdata;  /* 保存一些数据用于修改字典 */
    5.   dictht ht[2];    /* 哈希表 */
    6.   long rehashidx; /* rehash进行到的索引位置 */  
    7.   unsigned long iterators; /* 当前迭代器的运行数量 */
    8. }

    redis中的哈希表的实现方式可以归结为数组加链表，使用拉链法（链地址法）来解决哈希地址冲突；哈希表的槽位（哈希桶）个数为2^n个，每次扩缩容的结果都是2的幂次。
    进行key操作的时候，首先计算放入的索引位置，idx=hash(key)%sizemark，由于掩码的值为 2^n-1，所以这里的取模运算可以简化为按位与，提高运算速度。

    1. typedef struct dictht {
    2.   dictEntry **table; // 哈希槽数组
    3.   unsigned long size; // 哈希槽的个数（数组长度）
    4.   unsigned long sizemask; // 哈希掩码，size-1
    5.   unsigned long used; // 哈希表实际所拥有的元素个数
    6. } 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分布：
Redis 过期 key 删除原理分析 - 图1
当负载因子为0.5时，每个槽位上的元素个数概率分布如下所示：

  1. P(x=k) = exp(-0.5) * pow(0.5, k) / factorial(k)
  2. *0     0.606530659713
  3. *1     0.303265329856
  4. *2     0.0758163324641
  5. *3     0.0126360554107
  6. *4     0.00157950692633
  7. *5     0.000157950692633
  8. *6     1.31625577195e-05
  9. *7     9.40182694247e-07
  10. *8     5.87614183904e-08

当元素个数多于8个时，概率小于千万分之一
当负载因子为1.0时，每个槽位上当元素个数如下所示：

  1. P(x=k) = exp(-1) * pow(1, k) / factorial(k)
  2. *0     0.367879441171
  3. *1     0.367879441171
  4. *2     0.183939720586
  5. *3     0.0613132401952
  6. *4     0.0153283100488
  7. *5     0.00306566200976
  8. *6     0.000510943668294
  9. *7     7.29919526134e-05
  10. *8     9.12399407667e-06

当元素个数多于8个时，概率约为十万分之一
在正常情况下，每个哈希槽位上的节点一般都很少，可以认为在常数级时间复杂度O(1) 获取到元素。

2.2 redis的内存删除逻辑

2.2.1 redis的事件驱动模型

redis是一个单线程事件驱动的模型，主线程主要在aeMain中进行，通过配置文件中的属性hz来确定每秒钟含有几个循环周期，默认为10。
redis在初始化和加载后，就在aeMain中进行循环，直到接收到信号或发生错误才会退出，每个周期都会按照如下步骤进行处理:

  1. 处理beforesleep回调函数相关功能
  2. 处理时间事件
  3. 处理aftersleep回调函数相关功能
  4. 处理文件事件
  5. 进入下一次循环（回到a）
    1. void aeMain(aeEventLoop *eventLoop) {
    2.  eventLoop->stop = 0;
    3.  while (!eventLoop->stop) {
    4.      if (eventLoop->beforesleep != NULL)
    5.          eventLoop->beforesleep(eventLoop);
    6.      aeProcessEvents(eventLoop, AE_ALL_EVENTS|AE_CALL_AFTER_SLEEP);
    7.  }
    8. }
  • 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。 ```python 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):

  1. # 获取现在的运行时间，用于信息push和计算是否需要退出的baseline
  2. start = time.time()
  3. # 设定每次需要遍历的数据库
  4. dbs_per_call = CRON_DBS_PER_CALL
  6. if type == ACTIVE_EXPIRE_CYCLE_FAST:
  7.     # 如果上一次扫描没有触发时间限制就退出了，说明过期key数量不多，不要浪费性能在扫描key上
  8.     if not timelimit_exit:
  9.         return
  10.     # 如果距离上次快速淘汰开始的时间间隔小于2倍的快速淘汰持续时间，直接返回
  11.     if start < last_fast_cycle + ACTIVE_EXPIRE_CYCLE_FAST_DURATION * 2:
  12.         return
  13.     # 设定本次快速淘汰开始的时间，为下一次调用做时间baseline
  14.     last_fast_cycle = start
  16. # 如果每次扫描的数据库数量大于实际系统分配的逻辑分区数量，按照实际逻辑分区数量进行扫描
  17. # 如果上次扫描触发了时间限制，说明过期key比较多，需要进行全部逻辑分区的扫描
  18. if dbs_per_call > server.dbnum or timelimit_exit:
  19.     dbs_per_call = dbnums
  21. # 计算本次循环最多能持续的时间，1000000微秒*（25/100）/ 10
  22. # 1秒钟10hz，每次redis的处理周期为100毫秒（100000微秒），25%cpu时间分片就是25000微秒
  23. timelimit = 1000000 * ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC / server.hz / 100
  24. # 如果是快速清理模式，则每次最多能持续1000微秒
  25. if type == ACTIVE_EXPIRE_CYCLE_FAST:
  26.     timelimit = ACTIVE_EXPIRE_CYCLE_FAST_DURATION
  28. # 遍历指定数量（dbs_per_call）的数据库
  29. for i in range(0, dbs_per_call):
  30.     # 如果触发了时间限制，直接退出循环
  31.     if time.time() - start > timelimit:
  32.         break
  33.     # 当前数据库中不存在过期的key，直接扫描下一个数据库
  34.     if redisDb[i].expires.size() == 0:
  35.         continue
  36.     # 如果当前数据库含有过期时间的key数量小于1%，直接扫描下一个数据库
  37.     if redisDb[i].expires.size() * 100.0 / redisDb[i].dict.size() < 1:
  38.         continue
  40.     while True:
  41.         # 获取每次扫描的key的数量
  42.         lookup_nums = min(redisDb[i].expires.size(), ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP)
  43.         # 已经过期的key的数量
  44.         expired = 0
  46.         while lookup_nums > 0:
  47.             # 随机获取一个key判断是否过期
  48.             lookup_key = random_get_key_from_expire(redisDb[i])
  49.             # 如果过期了，就删除
  50.             if is_expire(lookup_key):
  51.                 del (lookup_key)
  52.                 expired += 1
  53.         # 判断当前时刻是否触发了时间限制，如果触发了限制，直接退出
  54.         if time.time() - start > timelimit:
  55.             break
  56.             break  # 两个break，不符合python语法，这里表示结束全部的循环
  58.         # 如果本次循环扫描出来的key已经过期的比例小于25%，则去扫描下一个数据库
  59.         # 否则说明本数据库过期的key较多，立刻在本数据库中再次扫描和清理
  60.         if expired * 4 / lookup_nums < 1:
  61.             break
  1. <a name="CZPvY"></a>
  2. #### 2.2.3 redis过期key优化点
  3. 上文中提到了，过期key是随机从全部的含有过期时间的key中进行选择。使用的算法如下，这里存在的不足是，当过期key数量较少时，哈希桶槽位上大部分的元素为空，随机数生成后所得到的哈希桶槽位经常miss，需要再次进行随机，会消耗过多的时间片在生成随机数上，而不是清理过期key。
  4. ```python
  5. def random_get_key_from_expire(redisDb):
  6.     slot_nums = 0
  7.     # 如果在进行rehash，则两个哈希表都可能有key存在,需要从中随机选择一个
  8.     if (is_rehash(redisDb.expires)):
  9.         slot_nums = ht[0].size + ht[1].size
  10.     else:
  11.         slot_nums = ht[0].size
  13.         headEntry = None
  14.         while True:
  15.             # 从所有的槽位中随机选择一个
  16.             slot_idx = random.randint(0, slot_nums)
  17.             # 直到找到一个槽位不为空的哈希桶，就停止循环
  18.             if (slot_idx > ht[0].size):
  19.                 # 如果所得到的索引大于ht[0]的大小，说明落在了ht[1]中
  20.                 tempEntry = ht[1].get_index(slot_idx - ht[0].size)
  21.                 if tempEntry != None:
  22.                     headEntry = tempEntry
  23.                     break
  24.                 else:
  25.                     tempEntry = ht[0].get_index(slot_idx)
  26.                     if tempEntry != None:
  27.                         headEntry = tempEntry
  28.                         break
  30.                         currEntry = headEntry
  31.                         len = 0
  32.                         # 遍历链表获得长度
  33.                         while currEntry.next:
  34.                             currEntry = currEntry.next
  35.                             len += 1
  37.                             # 从链表中随机选择一个节点返回
  38.                             listele = random.randint(0, len)
  39.                             while listele:
  40.                                 headEntry = headEntry.next
  41.                                 listele -= 1
  42.     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过期的判断和删除上。

  1. typedef struct redisDb {
  2.     dict *dict;                 
  3.     dict *expires;              
  4.     dict *blocking_keys;        
  5.     dict *ready_keys;           
  6.     dict *watched_keys;         
  7.     int id;                     
  8.     long long avg_ttl;          
  9.     unsigned long expires_cursor; /* 主动过期循环的游标*/
  10.     list *defrag_later;         /* key组成的链表，用来进行内存碎片整理 */
  11. } redisDb;

另外在server的配置中增加了activate_expire_effort标识位，可以被设定为1-10，用来表示定期删除淘汰key的激烈程度。在系统设定好activate_expire_effort之后，redis的定期删除循环逻辑每次都会重新计算阈值，比如快速淘汰循环最大的持续时间，慢速淘汰循环最大的持续时间，这些参数在之前的淘汰算法中都是一个确定的值。通过抽象成一个配置文件的参数，可以通过命令热加载动态的调节，达到redis吞吐量和容量使用的“均衡”。

  1. struct redisServer {
  2.             ...
  3.     int active_expire_enabled;      /* Can be disabled for testing purposes. */
  4.     int active_expire_effort;       /* From 1 (default) to 10, active effort. */
  5.             ...
  6. }
  1. ACTIVE_EXPIRE_CYCLE_SLOW = 0  # type标志位，持续时间比较久的慢速清理模式
  2. ACTIVE_EXPIRE_CYCLE_FAST = 1  # type标志位，持续时间比短的快速清理模式
  4. ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP = 20  # 每次每个db扫描的key个数
  5. ACTIVE_EXPIRE_CYCLE_FAST_DURATION = 1000  # 快速清理模式的最长持续时间，这里只是一个基线
  6. ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC = 25  # 扫描key所占用的cpu最长时间片
  7. ACTIVE_EXPIRE_CYCLE_ACCEPTABLE_STALE = 10  # 开启efforts后，过期key占据的百分比
  8. CRON_DBS_PER_CALL = 16  # 每次随机扫描的db个数
  10. current_db = 0  # 当前遍历到的数据库编号
  11. timelimit_exit = 0  # flag标识位，用于判断是否是到达了时间上限才退出循环
  12. last_fast_cycle = 0  # 上一次快速淘汰开始的时间
  15. def activeExpireCycle(type):
  16.     # 一个统计量，表示系统对于过期key扫描的激进程度（0~9）
  17.     # 该配置可以通过配置文件来进行设置，根据集群的平均过期时间，动态的设定
  18.     effort = server.active_expire_effort - 1,
  19.     # 每次循环扫描的key的数量
  20.     config_keys_per_loop = ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP + ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP / 4 * effort
  21.     # 快速清理循环的持续时间
  22.     config_cycle_fast_duration = ACTIVE_EXPIRE_CYCLE_FAST_DURATION + ACTIVE_EXPIRE_CYCLE_FAST_DURATION / 4 * effort
  23.     # 清理循环周期所占用的最大cpu时间片百分比
  24.     config_cycle_slow_time_perc = ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC + 2 * effort
  25.     # 有过期时间的key所全部key占的最多的百分比
  26.     config_cycle_acceptable_stale = ACTIVE_EXPIRE_CYCLE_ACCEPTABLE_STALE - effort
  28.     # 全局变量，函数退出后值仍然保存，留待下一次函数调用
  29.     global last_fast_cycle
  30.     global current_db
  31.     global timelimit_exit
  33.     start = time.time()
  34.     dbs_per_call = CRON_DBS_PER_CALL
  35.     iteration = 0
  37.     if type == ACTIVE_EXPIRE_CYCLE_FAST:
  38.         # 如果上一次扫描没有触发时间限制就退出,并且系统所含有的过期key的比例小于配置的阈值直接返回
  39.         # 因为此时过期快key的数量不多，并不需要浪费过多的cpu时间片在扫描过期key上
  40.         if (not timelimit_exit) and (server.stat_expired_stale_perc < config_cycle_acceptable_stale):
  41.             return
  42.         # 如果距离上次快速周期循环开始的时间间隔小于2倍的快速周期循环持续时间，直接返回
  43.         if start < last_fast_cycle + config_cycle_fast_duration * 2:
  44.             return
  45.         # 设定本次快速淘汰开始的时间，为下一次调用做时间baseline
  46.         last_fast_cycle = start
  48.     # 如果每次扫描的数据库数量大于实际系统分配的逻辑分区数量，按照实际逻辑分区数量进行扫描
  49.     # 如果上次扫描触发了时间限制，说明过期key比较多，需要进行全部逻辑分区的扫描
  50.     if dbs_per_call > server.dbnum or timelimit_exit:
  51.         dbs_per_call = server.dbnums
  53.     # 计算本次循环最多能持续的时间，1000000微秒*（25/100）/ 10
  54.     # 1秒钟10hz，每次redis的处理周期为100毫秒（100000微秒），25%cpu时间分片就是25000微秒
  55.     # 如果设置了effort，则会增加用于过期key删除的cpu时间片，例如effort=6，那么将有35000微秒用于处理过期key
  56.     timelimit = 1000000 * config_cycle_slow_time_perc / server.hz / 100
  58.     # 如果是快速清理模式，则每次最多能持续config_cycle_fast_duration微秒
  59.     if type == ACTIVE_EXPIRE_CYCLE_FAST:
  60.         timelimit = config_cycle_fast_duration
  62.     # 遍历指定数量（dbs_per_call）的数据库
  63.     for i in range(0, dbs_per_call):
  64.         # 如果触发了时间限制，直接退出循环
  65.         if time.time() - start > timelimit:
  66.             break
  68.         # 获取每次要扫描的数据库编号，并记录下来，这样可以让cpu将时间片公平的分给每个数据库
  69.         db_idx = current_db % server.dbnum
  70.         # 先变更下一次要扫描的数据库，方式程序因超时返回时忘记变更需要扫描的数据库，
  71.         # 也是为了将时间片公平的分散到每个数据库
  72.         db_idx += 1
  74.         while True:
  76.             # 当前数据库中不存在过期的key，直接扫描下一个数据库
  77.             if redisDb[db_idx].expires.size() == 0:
  78.                 break
  79.             # 如果当前数据库含有过期时间的key数量小于1%，直接扫描下一个数据库
  80.             if redisDb[db_idx].expires.size() * 100.0 / redisDb[db_idx].dict.size() < 1:
  81.                 break
  83.             # 获取每次扫描的key的数量
  84.             num = redisDb[db_idx].expires.size()
  85.             if num > config_keys_per_loop:
  86.                 num = config_keys_per_loop  # 每次至多只会选择config_keys_per_loop个key进行查询
  88.             # 最多遍历的哈希桶数量
  89.             max_buckets = num * 20
  90.             # 已经遍历的哈希桶数量
  91.             checked_buckets = 0
  92.             # 已经扫描的过期key的个数
  93.             sampled = 0
  94.             # 已经过期key的个数
  95.             expires = 0
  97.             # 如果扫描的哈希桶数量过多或者已经扫描了规定数量的key，就退出循环防止占用过多时间
  98.             while sampled < num and checked_buckets < max_buckets:
  99.                 # 字典里只有两个哈希表ht[0],ht[1],每次循环会选择其中的一个
  100.                 for table in (0, 1):
  101.                     # 没有进行rehash时，ht[1]为空，遍历到此处时直接返回
  102.                     if table == 1 and is_rehash(redisDb[db_idx].expires):
  103.                         break
  105.                     # 保存了上一次遍历到的哈希桶索引位置
  106.                     idx = redisDb[db_idx].expires_cursor
  107.                     # 与掩码进行计算，确定本次开始遍历的哈希桶索引位置
  108.                     idx = idx & redisDb[db_idx].expires.ht[i].sizemark
  109.                     # 获取哈希桶索引位置对应的链表的头节点
  110.                     dictEntry = redisDb[db_idx].expires.ht[i].bucket[idx]
  113.                     while dictEntry:
  114.                         # 遍历链表，如果过期了就删除，并计数已经过期的key
  115.                         if is_expire(dictEntry):
  116.                             del (dictEntry)
  117.                             expires += 1
  118.                         dictEntry = dictEntry.next
  119.                         sampled += 1
  121.                 # 记录下一次要遍历的哈希桶的索引位置
  122.                 redisDb[db_idx].expires_cursor += 1
  123.                 # 如果扫描时间过长达到了规定的阈值，则直接返回
  124.                 if time.time() - start > timelimit:
  125.                     return  # 直接返回全部的
  126.             # 如果过期的key占比高于阈值，说明当前库里面的过期key很多，需要再次遍历进行淘汰
  127.             if expires * 100.0 / sampled > config_cycle_acceptable_stale:
  128.                 continue
  129.             # 如果扫描到的所有的桶都是空的，触发了max_buckets限制而退出，说明没有清理到过期的key
  130.             # 过期的key都在其他的桶之中，需要进行再次的扫描
  131.             elif sampled == 0:
  132.                 continue
  133.             else:
  134.                 break