Redis 所有的数据都是存储在内存中的，在某些情况下需要对占用的内存空间进行回收。内存回收主要分为两类，一类是 key 过期，一类是内存使用达到上限（max_memory）触发内存淘汰。

查看Redis内存使用情况的命令：

  1. info memory

Redis内存打满再往里面存储数据会报OOM。

一，过期策略&淘汰策略

1.过期策略

主动淘汰【定时过期】：每个设置过期时间的 key 都需要创建一个定时器，到过期时间就会立即清除。该策略可以立即清除过期的数据，对内存很友好；但是会占用大量的 CPU 资源去处理过期的数据，从而影响缓存的响应时间和吞吐量。

被动淘汰【惰性淘汰】：只有当访问一个 key 时，才会判断该 key 是否已过期，过期则清除。该策略可以最大化地节省 CPU 资源，却对内存非常不友好。极端情况可能出现大量的过期 key 没有再次被访问，从而不会被清除，占用大量内存。

Redis实际采用的相当于是这两种策略的折中【同时使用了惰性过期和定时过期】，每隔一定的时间，会扫描一定数量的数据库的 expires 字典中一定数量的 key，并清除其中已过期的 key，通过调整定时扫描的时间间隔和每次扫描的限定耗时，可以在不同情况下使得 CPU 和内存资源达到最优的平衡效果。

假如所有数据都不过期，Redis内存满了怎么办？

2.淘汰策略

Redis 的内存淘汰策略，是指当内存使用达到最大内存极限时，需要使用淘汰算法来决定清理掉哪些数据，以保证新数据的存入。

2.1 最大内存设置

我们可以在redis.conf中设置Redis占用的最大内存：

  1. # maxmemory <bytes>

如果不设置 maxmemory 或者设置为 0，64 位系统不限制内存，32 位系统最多使用 3GB 内存。

我们也可以通过客户端的命令行动态修改Redis占用的最大内存：

config set maxmemory 2GB

2.2 淘汰策略

在redis.conf配置文件有一段配置：

# maxmemory-policy noeviction
# volatile-lru -> Evict using approximated LRU among the keys with an expire set.
# allkeys-lru -> Evict any key using approximated LRU.
# volatile-lfu -> Evict using approximated LFU among the keys with an expire set.
# allkeys-lfu -> Evict any key using approximated LFU.
# volatile-random -> Remove a random key among the ones with an expire set.
# allkeys-random -> Remove a random key, any key.
# volatile-ttl -> Remove the key with the nearest expire time (minor TTL)
# noeviction -> Don't evict anything, just return an error on write operations.

LRU:最近最少使用，判断最近被使用的事件，目前最远的数据优先被淘汰。 LFU：最不常用的数据会被淘汰。 random：随机删除。

noeviction 不会驱逐任何key
volatile-ttl 删除马上要过期的key
allkeys-lru 对所有key使用LRU算法进行删除（*）
volatile-lru 对所有设置了过期时间的key使用LRU算法进行删除
allkeys-random 对所有key随机删除
volatile-random 对所有设置了过期时间的key随机删除
allkeys-lfu 对所有key使用LFU算法进行删除
volatile-lfu 对所有设置了过期时间的key使用LFU算法进行删除

如果没有符合前提条件的 key 被淘汰，那么 volatile-lru、volatile-random 、volatile-ttl 相当于 noeviction（不做内存回收）。

我们也可以通过客户端动态修改内存淘汰策略：

config set maxmemory-policy volatile-lru

建议使用 volatile-lru，在保证正常服务的情况下，优先删除最近最少使用的 key。

二，源码分析

1.设置过期时间

在前面的文章中我们提到过，在redisDB数据结构中，有一个专门的 expires 字典用于存储显式设置了过期时间的数据(如 SETEX 命令设置的数据)。接下来我们以setex为例看一下过期时间是如何设置的。

首先我们在server.c文件中找到setex命令对应的执行函数。

{"setex",setexCommand,4,"write use-memory @string",0, NULL,1, 1,  1, 0, 0, 0}

在setexCommand函数中主要就是尝试对存入的数据进行编码，然后调用setGenericCommand执行相关主流程。在setGenericCommand中首先会根据过期时间进行判断，如果设置了过期时间，且时间小于0会抛出异常，如果是大于0的话会继续判断是不是需要进行单位转换。接下来会将key-value添加到redisDB中，然后如果设置了过期时间，将key和过期时间通过setExpire函数保存在redis数据库的过期字典中，接下来就是键空间通知和响应客户端的逻辑。

我们再来看一下setExpire函数的逻辑：

  1. 从数据库保存普通数据的字典中查找key所在节点
  2. 如果key存在的话使用这个key在数据库的过期字典中插入一个新节点或者找到已经存在的节点
  3. 将过期时间设置为这个节点的value

  4. 判断如果当前服务端是可写的从节点，将过期数据专门记录下来

    void setExpire(client *c, redisDb *db, robj *key, long long when) {
 dictEntry *kde, *de;

 /* 从数据库保存普通数据的字典【db->dict】中找到key所在的节点 */
 kde = dictFind(db->dict,key->ptr);
 serverAssertWithInfo(NULL,key,kde != NULL);
 //如果key存在的话，使用这个key在数据库的过期字典【db->expires】中插入一个新节点或者找到已经存在的节点，
 de = dictAddOrFind(db->expires,dictGetKey(kde));
 //将过期时间设置为这个节点的value
 dictSetSignedIntegerVal(de,when);

 int writable_slave = server.masterhost && server.repl_slave_ro == 0;
 //判断如果当前服务端是可写的从节点 【重要：redis的从机可以在配置文件配置可以写入数据】
 if (c && writable_slave && !(c->flags & CLIENT_MASTER))
     //将过期数据专门记录下来
     rememberSlaveKeyWithExpire(db,key);
}

    2.数据淘汰

上面第一大节我们介绍了，Redis一共有8种内存淘汰策略，接下来我们分析下redis是如何执行这些策略的。

  1. 主动删除：发生在redis处理读写请求的过程，例如执行get/set等命令
  2. 定期删除：发生在redis定时任务执行过程

2.1 主动删除

主动删除数据的动作其实也会多处触发，首先服务端解析完客户端传输过来的命令，准备执行前会检查 redis 占用内存是否超过了配置值，从而判断是否需要释放空间。另外在命令执行的过程中也会检查 key 是否过期了，对过期的 key 需要删除处理。

①命令执行前触发

在前面的《服务端启动流程源码分析》中曾经提到过一个processonCommand函数，在这个函数中有一段判断：如果Redis配置中设置了最大内存，并且lua脚本没有超时，则会调用performEvictions函数进行数据淘汰处理。接下来我们分析下performEvictions函数的逻辑:

  1. 首先进行各项检查
    1. 调用getMaxmemoryState函数检查服务端当前占用内存是不是超过了最大内存设置
    2. 检查redis服务端最大内存的处理策略 (server.maxmemory_policy)是不是禁止删除数据
  2. 根据服务端最大内存的处理策略的不同，会有不同的处理：
    1. 对于最近最少使用 LRU，最少使用 LFU 以及到达过期时间 TTL
      1. 遍历所有 redis 数据库
      2. 根据最大内存的处理策略进一步确定删除key的范围（所有数据(db->dict)或者过期数据(db->expires))
      3. 调用evictionPoolPopulate函数从中挑选出可以删除的候选key
      4. 确定一个最佳的 bestkey
    2. 对于随机淘汰这种对key没太多要求的删除策略
      1. 遍历所有redis数据库
      2. 根据最大内存的处理策略确定删除 key 的范围
      3. 调用dictGetRandomKey挑选bestkey
  3. 确定了要删除的bestkey，将其删除

  4. 如果释放的内存还是没有达到要求，while 循环继续 ```c int performEvictions(void) { if (!isSafeToPerformEvictions()) return EVICT_OK;

    int keys_freed = 0; size_t mem_reported, mem_tofree; long long mem_freed; / May be negative / mstime_t latency, eviction_latency; long long delta; int slaves = listLength(server.slaves); int result = EVICT_FAIL; //检查服务端当前占用内存是不是超过了最大内存设置 if (getMaxmemoryState(&mem_reported,NULL,&mem_tofree,NULL) == C_OK)

     return EVICT_OK;

    //检查服务端最大内存的处理策略是不是禁止删除数据 if (server.maxmemory_policy == MAXMEMORY_NO_EVICTION)

     return EVICT_FAIL;  /* We need to free memory, but policy forbids. */

    unsigned long eviction_time_limit_us = evictionTimeLimitUs();

    mem_freed = 0;

    latencyStartMonitor(latency);

    monotime evictionTimer; elapsedStart(&evictionTimer);

    while (mem_freed < (long long)mem_tofree) {

     int j, k, i;
 static unsigned int next_db = 0;
 sds bestkey = NULL;
 int bestdbid;
 redisDb *db;
 dict *dict;
 dictEntry *de;
 //最近最少使用的LRU，最少使用的LFU，到达过期时间TTL 对key有一定要求的删除策略：
 if (server.maxmemory_policy & (MAXMEMORY_FLAG_LRU|MAXMEMORY_FLAG_LFU) ||
     server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL)
 {
     struct evictionPoolEntry *pool = EvictionPoolLRU;

     while(bestkey == NULL) {
         unsigned long total_keys = 0, keys;

         //遍历所有的redis数据库
         for (i = 0; i < server.dbnum; i++) {
             db = server.db+i;
             //根据最大内存的处理策略进一步确定删除 key 的范围（所有数据(db->dict)或者过期数据(db->expires))
             dict = (server.maxmemory_policy & MAXMEMORY_FLAG_ALLKEYS) ?
                     db->dict : db->expires;
             if ((keys = dictSize(dict)) != 0) {
                 //从中挑选出可以删除的候选 key
                 evictionPoolPopulate(i, dict, db->dict, pool);
                 total_keys += keys;
             }
         }
         if (!total_keys) break; /* No keys to evict. */

         /* 确定一个最佳的 bestkey */
         for (k = EVPOOL_SIZE-1; k >= 0; k--) {
             if (pool[k].key == NULL) continue;
             bestdbid = pool[k].dbid;

             if (server.maxmemory_policy & MAXMEMORY_FLAG_ALLKEYS) {
                 de = dictFind(server.db[pool[k].dbid].dict,
                     pool[k].key);
             } else {
                 de = dictFind(server.db[pool[k].dbid].expires,
                     pool[k].key);
             }

             /* Remove the entry from the pool. */
             if (pool[k].key != pool[k].cached)
                 sdsfree(pool[k].key);
             pool[k].key = NULL;
             pool[k].idle = 0;

             /* If the key exists, is our pick. Otherwise it is
              * a ghost and we need to try the next element. */
             if (de) {
                 bestkey = dictGetKey(de);
                 break;
             } else {
                 /* Ghost... Iterate again. */
             }
         }
     }
 }

 /* 随机删除，对设置了过期事件的key删除  */
 else if (server.maxmemory_policy == MAXMEMORY_ALLKEYS_RANDOM ||
          server.maxmemory_policy == MAXMEMORY_VOLATILE_RANDOM)
 {
     /* 遍历所有 redis 数据库 */
     for (i = 0; i < server.dbnum; i++) {
         j = (++next_db) % server.dbnum;
         db = server.db+j;
         //根据最大内存的处理策略确定删除 key 的范围
         dict = (server.maxmemory_policy == MAXMEMORY_ALLKEYS_RANDOM) ?
                 db->dict : db->expires;
         if (dictSize(dict) != 0) {
             //挑选 bestkey
             de = dictGetRandomKey(dict);
             bestkey = dictGetKey(de);
             bestdbid = j;
             break;
         }
     }
 }

 /* 确定了要删除的 bestkey，将其删除即可。 */
 if (bestkey) {
     db = server.db+bestdbid;
     robj *keyobj = createStringObject(bestkey,sdslen(bestkey));
     propagateExpire(db,keyobj,server.lazyfree_lazy_eviction);
     /* We compute the amount of memory freed by db*Delete() alone.
      * It is possible that actually the memory needed to propagate
      * the DEL in AOF and replication link is greater than the one
      * we are freeing removing the key, but we can't account for
      * that otherwise we would never exit the loop.
      *
      * Same for CSC invalidation messages generated by signalModifiedKey.
      *
      * AOF and Output buffer memory will be freed eventually so
      * we only care about memory used by the key space. */
     delta = (long long) zmalloc_used_memory();
     latencyStartMonitor(eviction_latency);
     if (server.lazyfree_lazy_eviction)
         dbAsyncDelete(db,keyobj);
     else
         dbSyncDelete(db,keyobj);
     latencyEndMonitor(eviction_latency);
     latencyAddSampleIfNeeded("eviction-del",eviction_latency);
     delta -= (long long) zmalloc_used_memory();
     mem_freed += delta;
     server.stat_evictedkeys++;
     signalModifiedKey(NULL,db,keyobj);
     notifyKeyspaceEvent(NOTIFY_EVICTED, "evicted",
         keyobj, db->id);
     decrRefCount(keyobj);
     keys_freed++;

     if (keys_freed % 16 == 0) {
         /* When the memory to free starts to be big enough, we may
          * start spending so much time here that is impossible to
          * deliver data to the replicas fast enough, so we force the
          * transmission here inside the loop. */
         if (slaves) flushSlavesOutputBuffers();

         /* Normally our stop condition is the ability to release
          * a fixed, pre-computed amount of memory. However when we
          * are deleting objects in another thread, it's better to
          * check, from time to time, if we already reached our target
          * memory, since the "mem_freed" amount is computed only
          * across the dbAsyncDelete() call, while the thread can
          * release the memory all the time. */
         if (server.lazyfree_lazy_eviction) {
             if (getMaxmemoryState(NULL,NULL,NULL,NULL) == C_OK) {
                 break;
             }
         }

         /* After some time, exit the loop early - even if memory limit
          * hasn't been reached.  If we suddenly need to free a lot of
          * memory, don't want to spend too much time here.  */
         if (elapsedUs(evictionTimer) > eviction_time_limit_us) {
             // We still need to free memory - start eviction timer proc
             if (!isEvictionProcRunning) {
                 isEvictionProcRunning = 1;
                 aeCreateTimeEvent(server.el, 0,
                         evictionTimeProc, NULL, NULL);
             }
             break;
         }
     }
 } else {
     goto cant_free; /* nothing to free... */
 }
 //如果释放的内存还是没有达到要求，while 循环继续

    } / at this point, the memory is OK, or we have reached the time limit / result = (isEvictionProcRunning) ? EVICT_RUNNING : EVICT_OK;

cant_free: if (result == EVICT_FAIL) { /* At this point, we have run out of evictable items. It’s possible

     * that some items are being freed in the lazyfree thread.  Perform a
     * short wait here if such jobs exist, but don't wait long.  */
    if (bioPendingJobsOfType(BIO_LAZY_FREE)) {
        usleep(eviction_time_limit_us);
        if (getMaxmemoryState(NULL,NULL,NULL,NULL) == C_OK) {
            result = EVICT_OK;
        }
    }
}

latencyEndMonitor(latency);
latencyAddSampleIfNeeded("eviction-cycle",latency);
return result;

}

<a name="zZaz1"></a>
#### ②命令执行时触发

继续上面分析的setex流程，其中genericSetKey函数将数据添加到redisDb 中，这里我们主要关注lookupKeyWrite函数，它的主要作用是查找redis数据库中是否存在指定的key，最终在寻找key之前会调用到一个**expireIfNeeded**函数，而这个函数就是redis命令执行过程中删除过期数据的关键。**expireIfNeeded**函数的逻辑比较简单：先判断key是否过期，然后向slave节点传播执行过期 key 的动作并发送事件通知，最终删除key。

```c
int expireIfNeeded(redisDb *db, robj *key) {
    //判断 key 是否过期
    if (!keyIsExpired(db,key)) return 0;

    if (server.masterhost != NULL) return 1;

    /* Delete the key */
    server.stat_expiredkeys++;
    //向slave节点传播执行过期 key 的动作并发送事件通知
    propagateExpire(db,key,server.lazyfree_lazy_expire);
    notifyKeyspaceEvent(NOTIFY_EXPIRED,
        "expired",key,db->id);
    //删除过期 key
    int retval = server.lazyfree_lazy_expire ? dbAsyncDelete(db,key) :
                                               dbSyncDelete(db,key);
    if (retval) signalModifiedKey(NULL,db,key);
    return retval;
}

2.2 定期删除

定期删除是通过redis定时任务实现的，而前面我们说过定时任务入口为server.c文件的serverCron函数。这个函数实现代码较多，忽略不相关的部分，我们只关注定期删除数据的部分，关键函数为databasesCron函数。他的主要逻辑是处理我们需要在 Redis 数据库中增量执行的“后台”操作，例如活动密钥过期、调整大小、重新散列。这里我们主要关注清理过期key的函数activeExpireCycle，我们来分析下activeExpireCycle函数的核心逻辑：

  1. 遍历指定个数的db（如16）进行删除过期数据的操作
    1. 针对每个db每轮遍历不超过指定数量（如20）的节点
    2. 随机获取有过期时间的节点数据
    3. 调用activeExpireCycleTryExpire函数尝试删除数据
  2. 每个db 的遍历的轮数累积到16次的时候
    1. 判断使用的时间是否超过定时任务执行时间的 25%(timelimit =1000000*ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC/server.hz/100)超过就停止删除数据过程

  3. 如果已经删除的过期数据与随机选中的待过期数据的比值超过了配置值也停止删除数据

    void activeExpireCycle(int type) {
 /* Adjust the running parameters according to the configured expire
  * effort. The default effort is 1, and the maximum configurable effort
  * is 10. */
 unsigned long
 effort = server.active_expire_effort-1, /* Rescale from 0 to 9. */
 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,
 config_cycle_slow_time_perc = ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC +
                               2*effort,
 config_cycle_acceptable_stale = ACTIVE_EXPIRE_CYCLE_ACCEPTABLE_STALE-
                                 effort;

 /* This function has some global state in order to continue the work
  * incrementally across calls. */
 static unsigned int current_db = 0; /* Last DB tested. */
 static int timelimit_exit = 0;      /* Time limit hit in previous call? */
 static long long last_fast_cycle = 0; /* When last fast cycle ran. */

 int j, iteration = 0;
 int dbs_per_call = CRON_DBS_PER_CALL;
 long long start = ustime(), timelimit, elapsed;

 /* When clients are paused the dataset should be static not just from the
  * POV of clients not being able to write, but also from the POV of
  * expires and evictions of keys not being performed. */
 if (clientsArePaused()) return;

 if (type == ACTIVE_EXPIRE_CYCLE_FAST) {
     /* Don't start a fast cycle if the previous cycle did not exit
      * for time limit, unless the percentage of estimated stale keys is
      * too high. Also never repeat a fast cycle for the same period
      * as the fast cycle total duration itself. */
     if (!timelimit_exit &&
         server.stat_expired_stale_perc < config_cycle_acceptable_stale)
         return;

     if (start < last_fast_cycle + (long long)config_cycle_fast_duration*2)
         return;

     last_fast_cycle = start;
 }

 /* We usually should test CRON_DBS_PER_CALL per iteration, with
  * two exceptions:
  *
  * 1) Don't test more DBs than we have.
  * 2) If last time we hit the time limit, we want to scan all DBs
  * in this iteration, as there is work to do in some DB and we don't want
  * expired keys to use memory for too much time. */
 if (dbs_per_call > server.dbnum || timelimit_exit)
     dbs_per_call = server.dbnum;

 /* We can use at max 'config_cycle_slow_time_perc' percentage of CPU
  * time per iteration. Since this function gets called with a frequency of
  * server.hz times per second, the following is the max amount of
  * microseconds we can spend in this function. */
 timelimit = config_cycle_slow_time_perc*1000000/server.hz/100;
 timelimit_exit = 0;
 if (timelimit <= 0) timelimit = 1;

 if (type == ACTIVE_EXPIRE_CYCLE_FAST)
     timelimit = config_cycle_fast_duration; /* in microseconds. */

 /* Accumulate some global stats as we expire keys, to have some idea
  * about the number of keys that are already logically expired, but still
  * existing inside the database. */
 long total_sampled = 0;
 long total_expired = 0;
 //遍历指定个数的db（如16）进行删除过期数据的操作
 for (j = 0; j < dbs_per_call && timelimit_exit == 0; j++) {
     /* Expired and checked in a single loop. */
     unsigned long expired, sampled;

     redisDb *db = server.db+(current_db % server.dbnum);

     /* Increment the DB now so we are sure if we run out of time
      * in the current DB we'll restart from the next. This allows to
      * distribute the time evenly across DBs. */
     current_db++;

     /* 针对每个 db 每轮遍历不超过指定数量（如20）的节点，随机获取有过期时间的节点数据*/
     do {
         unsigned long num, slots;
         long long now, ttl_sum;
         int ttl_samples;
         iteration++;

         /* If there is nothing to expire try next DB ASAP. */
         if ((num = dictSize(db->expires)) == 0) {
             db->avg_ttl = 0;
             break;
         }
         slots = dictSlots(db->expires);
         now = mstime();

         /* When there are less than 1% filled slots, sampling the key
          * space is expensive, so stop here waiting for better times...
          * The dictionary will be resized asap. */
         if (num && slots > DICT_HT_INITIAL_SIZE &&
             (num*100/slots < 1)) break;

         /* The main collection cycle. Sample random keys among keys
          * with an expire set, checking for expired ones. */
         expired = 0;
         sampled = 0;
         ttl_sum = 0;
         ttl_samples = 0;

         if (num > config_keys_per_loop)
             num = config_keys_per_loop;

         /* Here we access the low level representation of the hash table
          * for speed concerns: this makes this code coupled with dict.c,
          * but it hardly changed in ten years.
          *
          * Note that certain places of the hash table may be empty,
          * so we want also a stop condition about the number of
          * buckets that we scanned. However scanning for free buckets
          * is very fast: we are in the cache line scanning a sequential
          * array of NULL pointers, so we can scan a lot more buckets
          * than keys in the same time. */
         long max_buckets = num*20;
         long checked_buckets = 0;

         while (sampled < num && checked_buckets < max_buckets) {
             for (int table = 0; table < 2; table++) {
                 if (table == 1 && !dictIsRehashing(db->expires)) break;

                 unsigned long idx = db->expires_cursor;
                 idx &= db->expires->ht[table].sizemask;
                 dictEntry *de = db->expires->ht[table].table[idx];
                 long long ttl;

                 /* Scan the current bucket of the current table. */
                 checked_buckets++;
                 while(de) {
                     /* Get the next entry now since this entry may get
                      * deleted. */
                     dictEntry *e = de;
                     de = de->next;

                     ttl = dictGetSignedIntegerVal(e)-now;
                     //尝试删除数据
                     if (activeExpireCycleTryExpire(db,e,now)) expired++;
                     if (ttl > 0) {
                         /* We want the average TTL of keys yet
                          * not expired. */
                         ttl_sum += ttl;
                         ttl_samples++;
                     }
                     sampled++;
                 }
             }
             db->expires_cursor++;
         }
         total_expired += expired;
         total_sampled += sampled;

         /* Update the average TTL stats for this database. */
         if (ttl_samples) {
             long long avg_ttl = ttl_sum/ttl_samples;

             /* Do a simple running average with a few samples.
              * We just use the current estimate with a weight of 2%
              * and the previous estimate with a weight of 98%. */
             if (db->avg_ttl == 0) db->avg_ttl = avg_ttl;
             db->avg_ttl = (db->avg_ttl/50)*49 + (avg_ttl/50);
         }

         /* We can't block forever here even if there are many keys to
          * expire. So after a given amount of milliseconds return to the
          * caller waiting for the other active expire cycle. */
         if ((iteration & 0xf) == 0) { /* check once every 16 iterations. */
             elapsed = ustime()-start;
             if (elapsed > timelimit) {
                 timelimit_exit = 1;
                 server.stat_expired_time_cap_reached_count++;
                 break;
             }
         }
         /* We don't repeat the cycle for the current database if there are
          * an acceptable amount of stale keys (logically expired but yet
          * not reclaimed). */
     } while (sampled == 0 ||
              (expired*100/sampled) > config_cycle_acceptable_stale);
 }

 elapsed = ustime()-start;
 server.stat_expire_cycle_time_used += elapsed;
 latencyAddSampleIfNeeded("expire-cycle",elapsed/1000);

 /* Update our estimate of keys existing but yet to be expired.
  * Running average with this sample accounting for 5%. */
 double current_perc;
 if (total_sampled) {
     current_perc = (double)total_expired/total_sampled;
 } else
     current_perc = 0;
 server.stat_expired_stale_perc = (current_perc*0.05)+
                                  (server.stat_expired_stale_perc*0.95);
}

    activeExpireCycleTryExpire函数是真正尝试删除过期数据的处理函数：

  4. 获取节点的过期时间

  5. 如果当前节点没过期，直接返回
  6. 如果当前节点过期了
    1. 获取key
    2. 传播过期行为
    3. 如果配置了惰性删除
      1. 异步删除 【所谓的Redis6.0的异步删除就在这里】
    4. 否则，直接删除
    5. 键空间通知
      int activeExpireCycleTryExpire(redisDb *db, dictEntry *de, long long now) {
//获取节点的过期时间
long long t = dictGetSignedIntegerVal(de);
//过期了
if (now > t) {
  //获取key
  sds key = dictGetKey(de);
  robj *keyobj = createStringObject(key,sdslen(key));
  //传播过期行为
  propagateExpire(db,keyobj,server.lazyfree_lazy_expire);
  //如果配置了惰性删除
  if (server.lazyfree_lazy_expire)
      //异步删除 【所谓的Redis6.0的异步删除就在这里】
      dbAsyncDelete(db,keyobj);
  else
      //同步删除
      dbSyncDelete(db,keyobj);
  //键空间通知
  notifyKeyspaceEvent(NOTIFY_EXPIRED,
      "expired",keyobj,db->id);
  signalModifiedKey(NULL, db, keyobj);
  decrRefCount(keyobj);
  server.stat_expiredkeys++;
  return 1;
} else {
  return 0;
}
}

3.LRU

基于一个数据结构做缓存，怎么实现 LRU——最长时间不被访问的元素在超过容量时删除？

如果基于传统 LRU 算法实现 Redis LRU 会有什么问题？需要额外的数据结构存储，消耗内存。Redis LRU 对传统的 LRU 算法进行了改良，通过随机采样来调整算法的精度。

如果淘汰策略是 LRU，则根据配置的采样值 maxmemory_samples（默认是 5 个）,随机从数据库中选择 m 个 key, 淘汰其中热度最低的 key 对应的缓存数据。所以采样参数m配置的数值越大, 就越能精确的查找到待淘汰的缓存数据,但是也消耗更多的CPU计算,执行效率降低。

如何找出热度最低的数据？

Redis 中所有对象结构都有一个 lru 字段, 且使用了 unsigned 的低 24 位，这个字段用来记录对象的热度。对象被创建时会记录 lru 值。在被访问的时候也会更新 lru 的值。但是不是获取系统当前的时间戳，而是设置为全局变量 server.lruclock 的值。

server.lruclock 的值怎么来的？

前面说过Redis 中 有 个 定 时 处 理 的 函 数 serverCron ， 默 认 每 100 毫 秒 调 用 函 数updateCachedTime 更新一次全局变量的 server.lruclock 的值，它记录的是当前 unix时间戳。

为什么不获取精确的时间而是放在全局变量中？不会有延迟的问题吗？

这样函数 lookupKey 中更新数据的 lru 热度值时,就不用每次调用系统函数 time，可以提高执行效率。

当对象里面已经有了 LRU 字段的值，就可以评估对象的热度了。函数 estimateObjectIdleTime 评估指定对象的 lru 热度，思想就是对象的 lru 值和全局的 server.lruclock 的差值越大（越久没有得到更新）， 该对象热度越低。

server.lruclock 只有 24 位，按秒为单位来表示才能存储 194 天。当超过 24bit 能表示的最大时间的时候，它会从头开始计算。在这种情况下，可能会出现对象的 lru 大于 server.lruclock 的情况，如果这种情况出现那么就两个相加而不是相减来求最久的 key。

为什么不用常规的哈希表+双向链表的方式实现？

需要额外的数据结构，消耗资源。而 Redis LRU 算法在 sample 为 10 的情况下，已经能接近传统 LRU 算法了。

除了消耗资源之外，传统 LRU 还有什么问题？

假设 A 在 10 秒内被访问了 5 次，而 B 在 10 秒内被访问了 3 次。因为 B 最后一次被访问的时间比 A 要晚，在同等的情况下，A 反而先被回收。

image.png
要实现基于访问频率的淘汰机制，怎么做？

4.LFU

我们来看一下redisObject结构体的定义：

typedef struct redisObject {
    unsigned    type : 4;
    unsigned    encoding : 4;
/* LRU time (relative to global lru_clock) or LFU data (least significant 8 bits frequency and most significant 16 bits access time). */
    unsigned    lru : LRU_BITS;
    int    refcount;
    void    *ptr;
} robj;

当这 24 bits 用作 LFU 时，其被分为两部分：

  • 高 16 位用来记录访问时间（单位为分钟，ldt，last decrement time）
  • 低 8 位用来记录访问频率，简称 counter（logc，logistic counter）

counter 是用基于概率的对数计数器实现的，8 位可以表示百万次的访问频率。对象被读写的时候，lfu 的值会被更新。

无论对象的读操作还是写操作都会去调用lookupKey函数去查找这个key，这个方法里面调用了一个方法updateLFU：

void updateLFU(robj *val) {
    unsigned long counter = LFUDecrAndReturn(val);
    counter = LFULogIncr(counter);
    val->lru = (LFUGetTimeInMinutes()<<8) | counter;
}

增长的速率：lfu-log-factor 越大，counter 增长的越慢。在redis.conf 配置文件，可以设置lfu-log-factor的值大小，默认是10。

如果计数器只会递增不会递减，也不能体现对象的热度。没有被访问的时候，计数器怎么递减呢？减少的值由衰减因子 lfu-decay-time（分钟）来控制，如果值是 1 的话，N 分钟没有访问就要减少 N。同样可以在redis.conf配置文件配置，默认是1。

至此，Redis过期策略&内存淘汰策略相关的源码我们就分析完了。

补充一个细节：

比如一个key设置1分钟过期，然后在还有10秒就过期的时候存入rdb，这时候rdb中的过期时间存的是10s？

在redis的setExpire函数注释中有一句话“when”参数是以毫秒为单位的绝对unix时间，超过该时间后，密钥将不再被视为有效。所以存储的不是10s，而是一个时间点。

这时候redis崩了，然后重启这个时间花了30s，那么重启后这个key是立刻过期还是再等10S再过期？

得对比一下key过期的绝对时间和当前时间。

其实在rdb持久化的源码里面也有判断，如果没有达到过期时间，会存储这个key-value以及过期时间，而过期时间是一个绝对时间点。