深入浅出-Redis过期删除策略手术式源码刨析,小白也能看懂

之前就说了要来西索Redis,现在来辣!
本文的部分基础内容参考自《小林Coding》,深入的地方根据源代码进行剖析。
Redis源码地址:https://github.com/redis/redis.git

过期删除策略

基础的命令就不做过多解释了,如下

  • expire <key> <n>:设置 key 在 n 秒后过期,比如 expire key 100 表示设置 key 在 100 秒后过期;
  • pexpire <key> <n>:设置 key 在 n 毫秒后过期,比如 pexpire key2 100000 表示设置 key2 在 100000 毫秒(100 秒)后过期。
  • expireat <key> <n>:设置 key 在某个时间戳(精确到秒)之后过期,比如 expireat key3 1655654400 表示 key3 在时间戳 1655654400 后过期(精确到秒);
  • pexpireat <key> <n>:设置 key 在某个时间戳(精确到毫秒)之后过期,比如 pexpireat key4 1655654400000 表示 key4 在时间戳 1655654400000 后过期(精确到毫秒)

当然,在设置字符串时,也可以同时对 key 设置过期时间,共有 3 种命令:

  • set <key> <value> ex <n> :设置键值对的时候,同时指定过期时间(精确到秒);
  • set <key> <value> px <n> :设置键值对的时候,同时指定过期时间(精确到毫秒);
  • setex <key> <n> <valule> :设置键值对的时候,同时指定过期时间(精确到秒)。

查询和删除过期指令

  • TTL <key>
  • PERSIST <key>

判断过期

我们回到第一章(神奇,Redis存储原理竟然是这样! – Karos (wzl.fyi)),当时讲过Redis存储结构

/* Redis database representation. There are multiple databases identified
 * by integers from 0 (the default database) up to the max configured
 * database. The database number is the 'id' field in the structure. */
//Redis数据库结构,通过ID来识别多个数据库
typedef struct redisDb {
    // 当前数据口的所有键值对空间
    dict *dict;                 /* The keyspace for this DB */
    // 存放已设置exptime的key的集合
    dict *expires;              /* Timeout of keys with a timeout set */
    ....
    ....
    // 数据库id
    int id;                     /* Database ID */
    // 数据库的平均TTL
    long long avg_ttl;          /* Average TTL, just for stats */
    unsigned long expires_cursor; /* Cursor of the active expire cycle. */
    list *defrag_later;         /* List of key names to attempt to defrag one by one, gradually. */
    clusterSlotToKeyMapping *slots_to_keys; /* Array of slots to keys. Only used in cluster mode (db 0). */
} redisDb;

那么expires中entry的key和value代表什么呢?

  • key:某个键对象

  • value:long long类型的整数,表示key的过期时间

    img

当我们在dict查找一个key的之前,先检查这个key是否存在于expires的哈希表中,如果不存在,继续查找,存在的话获取过期时间和系统时间比较,判断是否过期。

image-20230724061154402

当然,还有个判断过期的函数

// db.c
/* Check if the key is expired. */
int keyIsExpired(redisDb *db, robj *key) {
    /* Don't expire anything while loading. It will be done later. */
    if (server.loading) return 0;   // 如果redis服务器还在启动 ,俺么这个时候还没有过期key,直接 发安徽0

    mstime_t when = getExpire(db,key);      //获取key的过期时间
    mstime_t now;

    if (when < 0) return 0; /* No expire for this key */

    now = commandTimeSnapshot();

    /* The key expired if the current (virtual or real) time is greater
     * than the expire time of the key. */
    return now > when;
}

/* Return the expire time of the specified key, or -1 if no expire
 * is associated with this key (i.e. the key is non volatile) */
long long getExpire(redisDb *db, robj *key) {
    dictEntry *de;

    /* No expire? return ASAP */
    if (dictSize(db->expires) == 0 ||
       (de = dictFind(db->expires,key->ptr)) == NULL) return -1;  // 当在epxires哈希表中不能存在,就返回-1

    /* The entry was found in the expire dict, this means it should also
     * be present in the main dict (safety check). */
    serverAssertWithInfo(NULL,key,dictFind(db->dict,key->ptr) != NULL);   // 日志输出
    // 放回过期时间
    return dictGetSignedIntegerVal(de);
}

int64_t dictGetSignedIntegerVal(const dictEntry *de) {
    assert(entryHasValue(de));
    return de->v.s64;
}

删除策略

常见的删除策略有3中

  • 定时删除

    在设置 key 的过期时间时,同时创建一个定时事件,当时间到达时,由事件处理器自动执行 key 的删除操作。

    定时事件,虽然说可以及时释放内存,但是一定会长时间占用cpu,少量键还好,当键的数量够多的时候,无疑会大大降低服务器的吞吐量,所以Redis并未采用。

  • 惰性删除

  • 定期删除

而惰性删除和定期删除我们在下文细说

惰性删除

不主动删除过期键,每次从数据库访问 key 时,都检测 key 是否过期,如果过期则删除该 key。

那么我很多键都过期了,这时候我也不访问,就一直不删除,像垃圾一样占用内存,这个方法对cpu占用很少,特别友好,但是对于内存来说,那有可能是巨大的灾难。

image-20230725050609605

哎,其实就是在之前判断过期的方法上面加了个删除,看看Redis的实现吧。

/* Flags for expireIfNeeded */
#define EXPIRE_FORCE_DELETE_EXPIRED 1       // 二进制为 01
#define EXPIRE_AVOID_DELETE_EXPIRED 2       // 二进制为 10

// 用处是检验一个键是否过期,并不一定会删除,下面是官方对于这个函数的解释
/* This function is called when we are going to perform some operation
 * in a given key, but such key may be already logically expired even if
 * it still exists in the database. The main way this function is called
 * is via lookupKey*() family of functions.
 *
 * The behavior of the function depends on the replication role of the
 * instance, because by default replicas do not delete expired keys. They
 * wait for DELs from the master for consistency matters. However even
 * replicas will try to have a coherent return value for the function,
 * so that read commands executed in the replica side will be able to
 * behave like if the key is expired even if still present (because the
 * master has yet to propagate the DEL).
 *
 * In masters as a side effect of finding a key which is expired, such
 * key will be evicted from the database. Also this may trigger the
 * propagation of a DEL/UNLINK command in AOF / replication stream.
 *
 * On replicas, this function does not delete expired keys by default, but
 * it still returns 1 if the key is logically expired. To force deletion
 * of logically expired keys even on replicas, use the EXPIRE_FORCE_DELETE_EXPIRED
 * flag. Note though that if the current client is executing
 * replicated commands from the master, keys are never considered expired.
 *
 * On the other hand, if you just want expiration check, but need to avoid
 * the actual key deletion and propagation of the deletion, use the
 * EXPIRE_AVOID_DELETE_EXPIRED flag.
 *
 * The return value of the function is 0 if the key is still valid,
 * otherwise the function returns 1 if the key is expired. */
int expireIfNeeded(redisDb *db, robj *key, int flags) {
    if (server.lazy_expire_disabled) return 0;  // 判断是否开启惰性删除
    /**
     * 没有过期就不删除,这一块儿的源代码我们在上面就已经讲过了
     * 要注意的是,判断键是否过期,里面使用了DictFind方法来查找键值对
     * 这个方法在使用的时候会判断是否处于渐进式Hash的过程中,如果是的话,会执行一次部分ReHash。
    **/
    if (!keyIsExpired(db,key)) return 0;        

    // 如果当前Redis数据库是从库,那么将数据返回,我们要保证数据和主库的一致性,从库删除数据是从主库广播DEL命令来进行删除的
    if (server.masterhost != NULL) {
        /**
         * 在从库上,默认情况下,该函数不会删除过期的键,但如果键在逻辑上已过期,它仍然会返回1。
         * 要强制在从库上删除逻辑上过期的键,请使用EXPIRE_FORCE_DELETE_EXPIRED标志。
         * 注意,如果当前客户端正在从主库执行复制命令,则永远不会认为键已过期。
        */
        if (server.current_client && (server.current_client->flags & CLIENT_MASTER)) return 0;
        // 下面这个语句用的比较妙,对于flag,我们可以选择1[01]和2[10]来进行&运算,当强制删除的时候,就会往下面运行
        if (!(flags & EXPIRE_FORCE_DELETE_EXPIRED)) return 1;
    }

    /* In some cases we're explicitly instructed to return an indication of a
     * missing key without actually deleting it, even on masters. */
    // 如果只需要检查过期情况,但需要避免实际删除键并传播删除操作,请使用EXPIRE_AVOID_DELETE_EXPIRED标志
    if (flags & EXPIRE_AVOID_DELETE_EXPIRED)
        return 1;

    /* If 'expire' action is paused, for whatever reason, then don't expire any key.
     * Typically, at the end of the pause we will properly expire the key OR we
     * will have failed over and the new primary will send us the expire. */
    // 有时候会暂停过期key的处理,但是这个时候我们依然返回1,就当是一个过期检测吧
    if (isPausedActionsWithUpdate(PAUSE_ACTION_EXPIRE)) return 1;

    /* Delete the key */
    deleteExpiredKeyAndPropagate(db,key);
    return 1;
}

官方解释的大概意思如下:
该函数在执行某些操作时被调用,操作可能针对给定的键,但即使该键仍然存在于数据库中,它可能已经逻辑上过期了。

  • 主要通过lookupKey*()函数系列调用该函数。
  • 函数的行为取决于实例的复制角色,因为默认情况下从库不会删除过期的键。它们等待主库发送DEL命令以确保一致性。
  • 不过,即使在从库上,该函数仍会努力返回一致的值,这样在从库执行的读取命令将能够像键已过期一样执行,
  • 即使键仍然存在(因为主库尚未传播DEL命令)。
  • 在主库上,发现过期键的副作用是将该键从数据库中逐出。这也可能触发AOF/复制流中的DEL/UNLINK命令的传播。
  • 在从库上,默认情况下,该函数不会删除过期的键,但如果键在逻辑上已过期,它仍然会返回1。
  • 要强制在从库上删除逻辑上过期的键,请使用EXPIRE_FORCE_DELETE_EXPIRED标志。
  • 注意,如果当前客户端正在从主库执行复制命令,则永远不会认为键已过期。
  • 另一方面,如果只需要检查过期情况,但需要避免实际删除键并传播删除操作,请使用EXPIRE_AVOID_DELETE_EXPIRED标志。
  • 函数的返回值为0,如果键仍然有效,否则如果键已过期,则返回1。

定期删除

每隔一段时间==随机==从数据库中取出一定数量的 key 进行检查,并删除其中的过期key。

通过限制操作时长和频率,来减少对cpu的影响,同时也只能删除一部分数据。

所以这样会导致:部分数据可能删除不了,内存清理效果没有定时删除好,同时对操作系统的小号也没有惰性删除好,并且频率和操作时长难以控制。

在讲源码之前,我们先补充一些数据结构:

// Data used by the expire dict scan callback.  这个结构用于回调扫描,后面细说
 typedef struct {
     redisDb *db;
     long long now;        // 当前时间戳
     unsigned long sampled; // num keys checked 已抽样的键数量
     unsigned long expired; // num keys expired 过期键数量
     long long ttl_sum; // sum of ttl for key with ttl not yet expired 尚未过期键的过期时间总和
     int ttl_samples; // num keys with ttl not yet expired 尚未过期键的数量
  } expireScanData;

下面我们来看看源码是如何解释的,官方的解释我使用chatgpt简单翻译了一下

/* Try to expire a few timed out keys. The algorithm used is adaptive and
 * will use few CPU cycles if there are few expiring keys, otherwise
 * it will get more aggressive to avoid that too much memory is used by
 * keys that can be removed from the keyspace.
 *
 * 尝试过期一些已超时的键。算法是自适应的,如果有很少过期键,则消耗很少的CPU周期;否则,它会更加积极,以避免过多的内存被可删除的键占用。
 *
 * Every expire cycle tests multiple databases: the next call will start
 * again from the next db. No more than CRON_DBS_PER_CALL databases are
 * tested at every iteration.
 *
 * 每个过期周期测试多个数据库:下一次调用将从下一个数据库开始。每次迭代最多测试 CRON_DBS_PER_CALL 个数据库。
 *
 * The function can perform more or less work, depending on the "type"
 * argument. It can execute a "fast cycle" or a "slow cycle". The slow
 * cycle is the main way we collect expired cycles: this happens with
 * the "server.hz" frequency (usually 10 hertz).
 *
 * 此函数根据"type"参数可以执行更多或更少的工作。
 * 它可以执行 "快速循环" 或 "慢速循环"。
 * 慢速循环是主要收集已过期键的方式:通常在每秒 server.hz 的频率下执行(通常为 10 次/秒)。
 *
 * However the slow cycle can exit for timeout, since it used too much time.
 * For this reason the function is also invoked to perform a fast cycle
 * at every event loop cycle, in the beforeSleep() function. The fast cycle
 * will try to perform less work, but will do it much more often.
 *
 * 然而,慢速循环可能因为超时而退出,因为它消耗了太多时间。
 * 因此,该函数还会在每个事件循环周期中执行 "快速循环",在 beforeSleep() 函数中执行。
 * 快速循环会尝试执行较少的工作,但会更频繁地执行。
 *
 * The following are the details of the two expire cycles and their stop
 * conditions:
 *
 * If type is ACTIVE_EXPIRE_CYCLE_FAST the function will try to run a
 * "fast" expire cycle that takes no longer than ACTIVE_EXPIRE_CYCLE_FAST_DURATION
 * microseconds, and is not repeated again before the same amount of time.
 * The cycle will also refuse to run at all if the latest slow cycle did not
 * terminate because of a time limit condition.
 * 
 * 如果 type 为 ACTIVE_EXPIRE_CYCLE_FAST,函数将尝试运行一个 "快速" 过期周期,
 * 该周期的执行时间不超过 ACTIVE_EXPIRE_CYCLE_FAST_DURATION 微秒,并且在相同时间内不会再次重复执行。
 * 如果最近的慢速循环没有因时间限制条件而终止,该循环将拒绝运行。
 *
 * If type is ACTIVE_EXPIRE_CYCLE_SLOW, that normal expire cycle is
 * executed, where the time limit is a percentage of the REDIS_HZ period
 * as specified by the ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC define. In the
 * fast cycle, the check of every database is interrupted once the number
 * of already expired keys in the database is estimated to be lower than
 * a given percentage, in order to avoid doing too much work to gain too
 * little memory.
 *
 * 如果 type 为 ACTIVE_EXPIRE_CYCLE_SLOW,则执行正常的过期循环,其中的时间限制是 REDIS_HZ 周期的百分比,由 
 * ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC 定义指定。
 * 在快速循环中,一旦估计数据库中已过期键的数量低于给定的百分比,对每个数据库的检查将被中断,以避免做太多的工作而获得太少的内存。
 *
 * The configured expire "effort" will modify the baseline parameters in
 * order to do more work in both the fast and slow expire cycles.
 */

/* Keys for each DB loop. */
#define ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP 20    // 每次随机抽查的数量
/* Microseconds. */
#define ACTIVE_EXPIRE_CYCLE_FAST_DURATION 1000  // 快速过期扫描的最长执行时间(以微秒为单位)
/* Max % of CPU to use. */
#define ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC 25   // 每次循环允许使用的最大CPU占用百分比
/* % of stale keys after which we do extra efforts. */
#define ACTIVE_EXPIRE_CYCLE_ACCEPTABLE_STALE 10 // 每个周期内允许的过期键百分比,如果某个数据库过期键超过这个百分比,那该数据库会被处理。

#define ACTIVE_EXPIRE_CYCLE_SLOW 0
#define ACTIVE_EXPIRE_CYCLE_FAST 1

#define CRON_DBS_PER_CALL 16    // 数据库总数

void activeExpireCycle(int type) {
    /* 根据配置的过期努力程度(effort)调整运行参数。
     * 默认努力程度是1,最大可配置努力程度是10。 */
    unsigned long
    effort = server.active_expire_effort-1, /* Rescale from 0 to 9. */
    // 每次周期允许最多可以处理的key的数量
    config_keys_per_loop = ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP +
                           ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP/4*effort,
    // 每次快循环周期允许的最长时间 1s -> 3.25s
    config_cycle_fast_duration = ACTIVE_EXPIRE_CYCLE_FAST_DURATION +
                                 ACTIVE_EXPIRE_CYCLE_FAST_DURATION/4*effort,
    // 每次正常循环周期允许占用cpu的占比 25% -> 43%
    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; /* Next DB to test. */                  // 下一个要处理的数据库ID
    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;

    /* If 'expire' action is paused, for whatever reason, then don't expir                                                                  e any key.
     * Typically, at the end of the pause we will properly expire the key OR we
     * will have failed over and the new primary will send us the expire. */
    if (isPausedActionsWithUpdate(PAUSE_ACTION_EXPIRE)) 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 &&
            /*
            在redisServer中有一个字段
            double stat_expired_stale_perc; // Percentage of keys probably expired
            这个字段表示Key可能已过期的百分比,没有超过那么就还能接受,就不处理
            */
            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)
        /**
         * #define REDIS_DEFAULT_DBNUM 16
         * // redisServer中使用的数据库实际总数,默认值为16
         * int dbnum;                      /* Total number of configured DBs .*/
         */
        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. */
    // 根据CPU使用率的阙值和ServerCPU执行频率HZ来进行计算时间限制
    timelimit = config_cycle_slow_time_perc*1000000/server.hz/100;
    timelimit_exit = 0;     //清空强制退出状态
    if (timelimit <= 0) timelimit = 1;   // 默认状态下,1ms为时间上限
    // 如果是快循环,修改时间上限
    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; // 总共过期的键的个数

    /* Try to smoke-out bugs (server.also_propagate should be empty here) */
    serverAssert(server.also_propagate.numops == 0);

    for (j = 0; j < dbs_per_call && timelimit_exit == 0; j++) {
        /* Scan callback data including expired and checked count per iteration. */
        expireScanData data;
        /**
         *  // Data used by the expire dict scan callback. 
         *  typedef struct {
         *      redisDb *db;
         *      long long now;         // 当前时间戳
         *      unsigned long sampled; // num keys checked 已抽样的键数量
         *      unsigned long expired; // num keys expired 过期键数量
         *      long long ttl_sum; // sum of ttl for key with ttl not yet expired 尚未过期键的过期时间总和
         *      int ttl_samples; // num keys with ttl not yet expired 尚未过期键的数量
         *  } expireScanData;
         **/
        // 这里开始获取到本次循环需要清理的DB
        redisDb *db = server.db+(current_db % server.dbnum);
        data.db = db;   // 这个地方进行封装是便于后面函数调用

        /* 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++;

        /* Continue to expire if at the end of the cycle there are still
         * a big percentage of keys to expire, compared to the number of keys
         * we scanned. The percentage, stored in config_cycle_acceptable_stale
         * is not fixed, but depends on the Redis configured "expire effort". */
        do {
            unsigned long num, slots;
            iteration++;

            /* If there is nothing to expire try next DB ASAP. */
            if ((num = dictSize(db->expires)) == 0) {
                db->avg_ttl = 0;     //当前没有过期键,那么平均过期时间就是0
                break;
            }
             /**
             这里是如何计算哈希桶数的
             #define dictSlots(d) 
                (DICTHT_SIZE(
                    (d)->ht_size_exp[0]
                      )+
               DICTHT_SIZE(
                 (d)->ht_size_exp[1])
                      )             
             **/
            slots = dictSlots(db->expires);  // 获取哈希桶的数目
            data.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 (slots > DICT_HT_INITIAL_SIZE &&
                (num*100/slots < 1)) break;      // 如果平均每个桶分配的过期键(过期键填充比例)小于1%,break,等待下次抽样

            /* The main collection cycle. Scan through keys among keys
             * with an expire set, checking for expired ones. */
            // 每次遍历都要重新计算,最后再累加
            data.sampled = 0;
            data.expired = 0;
            data.ttl_sum = 0;
            data.ttl_samples = 0;
            // num = dictSize(db->expires);
            // 修改key的处理量,不可以超过config_keys_per_loop最多可以处理的key的数量
            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;  // 用于限制扫描哈希桶的数量,20是根据实验测得的。。。
            long checked_buckets = 0;

            while (data.sampled < num && checked_buckets < max_buckets) {
                // dictScan 函数是 Redis 中用于遍历字典(哈希表)的函数,它的作用是在哈希表中迭代键值对,并通过回调函数对每个键值对进行处理。
                // 这里expires_cursor感觉像是HashCode一样(呃呃呃,具体看后面跟随源码),可以用于确认索引位域哪个哈希桶
                // expires_cursor 是用于遍历哈希表的游标值(cursor),通常是一个哈希值(hash value)。
                // 在过期键处理的过程中,expires_cursor 用于指示当前迭代的起始位置,从而控制扫描哈希表的开始点。
                // 再回调的时候就已经将过期的数据进行删除了
                db->expires_cursor = dictScan(db->expires, db->expires_cursor,
                                              expireScanCallback, &data);
                checked_buckets++;
            }
            // 因为expired和sampled在遍历回调的时候进行了累加,所以这里得加上
            total_expired += data.expired;
            total_sampled += data.sampled;

            /* Update the average TTL stats for this database. */
            if (data.ttl_samples) {
                long long avg_ttl = data.ttl_sum / data.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. */
            // 每16次迭代检查一次是否超时(16个是因为默认是16个数据库),并完成记录,
            // 同时更新timelimit_exit=1,后续会开启fast-expire模式。
            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 (data.sampled == 0 ||   // 如果还没有开始检测 or
                 // 当当前数据库已过期的数量/抽样的数量 > 10%-effort,这个地方写成*100是为了防止数据溢出
                 (data.expired * 100 / data.sampled) > config_cycle_acceptable_stale);   
    }

    elapsed = ustime()-start;
    // 用于统计定期删除总共耗费的时间
    // long long stat_expire_cycle_time_used; /* Cumulative microseconds used. */
    server.stat_expire_cycle_time_used += elapsed;
    latencyAddSampleIfNeeded("expire-cycle",elapsed/1000);// 将耗时补加到Redis延迟统计中

    /* Update our estimate of keys existing but yet to be expired.
     * Running average with this sample accounting for 5%. */
     /* 更新已过期但仍未被删除的键的估算数量。
     * 通过这个样本估算平均存在的过期键的百分比,权重为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);
}

unsigned long dictScan(dict *d,
                       unsigned long v,
                       dictScanFunction *fn,
                       void *privdata)
{
    return dictScanDefrag(d, v, fn, NULL, privdata);
}

/* Like dictScan, but additionally reallocates the memory used by the dict
 * entries using the provided allocation function. This feature was added for
 * the active defrag feature.
 *
 * The 'defragfns' callbacks are called with a pointer to memory that callback
 * can reallocate. The callbacks should return a new memory address or NULL,
 * where NULL means that no reallocation happened and the old memory is still
 * valid. */
unsigned long dictScanDefrag(dict *d,
                             unsigned long v,
                             dictScanFunction *fn,
                             dictDefragFunctions *defragfns,
                             void *privdata)
{
    int htidx0, htidx1;
    const dictEntry *de, *next;
    unsigned long m0, m1;

    if (dictSize(d) == 0) return 0;

    /* This is needed in case the scan callback tries to do dictFind or alike. */
    dictPauseRehashing(d);  //暂停渐进式hash

    if (!dictIsRehashing(d)) {
        //如果没有进行hash,那么就在第一个表里面
        htidx0 = 0;
        m0 = DICTHT_SIZE_MASK(d->ht_size_exp[htidx0]);//通过指数获取掩码,用于计算桶的索引

        /* Emit entries at cursor */
        if (defragfns) {
            dictDefragBucket(d, &d->ht_table[htidx0][v & m0], defragfns);
        }
        de = d->ht_table[htidx0][v & m0];
        //开始遍历
        while (de) {
            next = dictGetNext(de);
            // 回调调用expireScanCallback()
            fn(privdata, de);
            de = next;
        }

        /* Set unmasked bits so incrementing the reversed cursor
         * operates on the masked bits */
        v |= ~m0;

        /* Increment the reverse cursor */
        v = rev(v);
        v++;
        v = rev(v);

    } else {
        htidx0 = 0;
        htidx1 = 1;

        /* Make sure t0 is the smaller and t1 is the bigger table */
        if (DICTHT_SIZE(d->ht_size_exp[htidx0]) > DICTHT_SIZE(d->ht_size_exp[htidx1])) {
            htidx0 = 1;
            htidx1 = 0;
        }

        m0 = DICTHT_SIZE_MASK(d->ht_size_exp[htidx0]);
        m1 = DICTHT_SIZE_MASK(d->ht_size_exp[htidx1]);

        /* Emit entries at cursor */
        if (defragfns) {
            dictDefragBucket(d, &d->ht_table[htidx0][v & m0], defragfns);
        }
        de = d->ht_table[htidx0][v & m0];
        while (de) {
            next = dictGetNext(de);
            fn(privdata, de);
            de = next;
        }

        /* Iterate over indices in larger table that are the expansion
         * of the index pointed to by the cursor in the smaller table */
        do {
            /* Emit entries at cursor */
            if (defragfns) {
                dictDefragBucket(d, &d->ht_table[htidx1][v & m1], defragfns);
            }
            de = d->ht_table[htidx1][v & m1];
            while (de) {
                next = dictGetNext(de);
                fn(privdata, de);
                de = next;
            }

            /* Increment the reverse cursor not covered by the smaller mask.*/
            v |= ~m1;
            v = rev(v);
            v++;
            v = rev(v);

            /* Continue while bits covered by mask difference is non-zero */
        } while (v & (m0 ^ m1));
    }

    dictResumeRehashing(d);

    return v;
}
// 扫描回调函数
void expireScanCallback(void *privdata, const dictEntry *const_de) {
    dictEntry *de = (dictEntry *)const_de;
    expireScanData *data = privdata;
    long long ttl  = dictGetSignedIntegerVal(de) - data->now;
    //执行删除
    if (activeExpireCycleTryExpire(data->db, de, data->now)) {
        data->expired++;         //计算过期键数量
        /* Propagate the DEL command */
        // 广播del命令给从库
        postExecutionUnitOperations();
    }
    if (ttl > 0) {
        /* We want the average TTL of keys yet not expired. */
        data->ttl_sum += ttl;
        data->ttl_samples++; // 还没有过期
    }
    data->sampled++; //检测数量增加
}

int activeExpireCycleTryExpire(redisDb *db, dictEntry *de, long long now) {
    long long t = dictGetSignedIntegerVal(de);  // 从expire表中获取过期时间
    if (now > t) {
        // 如果过期了就删除
        sds key = dictGetKey(de);   // 获取存储的变量名
        robj *keyobj = createStringObject(key,sdslen(key));
        deleteExpiredKeyAndPropagate(db,keyobj);
        decrRefCount(keyobj);
        return 1;
    } else {
        return 0;
    }
}
int64_t dictGetSignedIntegerVal(const dictEntry *de) {
    assert(entryHasValue(de));
    return de->v.s64;
}
/* Delete the specified expired key and propagate expire. */
void deleteExpiredKeyAndPropagate(redisDb *db, robj *keyobj) {
    mstime_t expire_latency;
    latencyStartMonitor(expire_latency);
    dbGenericDelete(db,keyobj,server.lazyfree_lazy_expire,DB_FLAG_KEY_EXPIRED);
    latencyEndMonitor(expire_latency);
    latencyAddSampleIfNeeded("expire-del",expire_latency);
    notifyKeyspaceEvent(NOTIFY_EXPIRED,"expired",keyobj,db->id);
    signalModifiedKey(NULL, db, keyobj);
    propagateDeletion(db,keyobj,server.lazyfree_lazy_expire);
    server.stat_expiredkeys++;
}
//从代码可以看出,对于过期了的键,删除以后仍然会进行计数处理

这段代码是Redis中的主动过期机制(active expire cycle)的实现函数。该函数负责在后台扫描Redis数据库中的键,并删除已过期的键。这个过程是周期性的,它会在每个函数调用中处理多个数据库(CRON_DBS_PER_CALL)。下面是代码的解释:

  1. 宏定义部分:

    • ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP:每次循环中处理的过期键的数量。
    • ACTIVE_EXPIRE_CYCLE_FAST_DURATION:快速过期扫描的最长执行时间(以微秒为单位)。
    • ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC:每次循环允许使用的最大CPU时间百分比。
    • ACTIVE_EXPIRE_CYCLE_ACCEPTABLE_STALE:每个周期内允许的过期键百分比,如果某个数据库的过期键超过这个百分比,那么该数据库会被重新处理。
  2. activeExpireCycle函数:

    • type参数表示执行的类型,可以是ACTIVE_EXPIRE_CYCLE_FAST(快速过期扫描)或其他值(正常扫描)。
    • 通过调整运行参数,根据配置的过期努力程度来控制过期键的处理:
      • effort:根据配置的努力程度调整运行参数。默认努力程度为1,最大可配置努力程度为10。
      • config_keys_per_loop:每次循环中处理的过期键的数量。随着努力程度的增加,处理的过期键数量也会增加。
      • config_cycle_fast_duration:每次快速过期扫描的最长执行时间。随着努力程度的增加,最长执行时间也会增加。
      • config_cycle_slow_time_perc:每次循环允许使用的最大CPU时间百分比。随着努力程度的增加,允许的CPU时间百分比也会增加。
      • config_cycle_acceptable_stale:每个周期内允许的过期键百分比。随着努力程度的增加,允许的过期键百分比会减少。
    • 函数内部有一些全局状态变量,用于在多次调用之间继续工作。
    • 首先,检查是否有针对"expire"操作的暂停(pause)标志。如果有暂停,则不会处理任何过期键。
    • 快速过期扫描:
      • 通过一些条件判断,决定是否执行快速过期扫描。
      • 如果上一次的快速扫描没有因为时间限制而退出,并且预估的过期键百分比较小,则不会执行快速扫描。
    • 循环处理数据库:
      • 对多个数据库执行循环,直到处理了所有配置的数据库或达到了时间限制。
      • dbs_per_call:每次循环处理的数据库数目,不能超过实际数据库数目。如果上一次运行达到了时间限制,则会在这次迭代中处理所有数据库。
      • 根据配置,计算每次循环最多允许的执行时间timelimit
      • 如果是快速过期扫描,那么执行时间限制为预设的config_cycle_fast_duration
      • 统计全局的过期键状态,以了解已经过期但仍存在于数据库中的键的数量。
      • 对每个数据库进行过期扫描:
      • 按照一定的规则选择一些键进行检查。
      • 在过期键中进行随机抽查,并检查是否过期。
      • 更新全局的过期键状态。
      • 在超过时间限制时退出循环,等待下一次调用。

这段代码实现了Redis数据库中的过期键处理机制,通过不同的努力程度和配置参数来控制过期键的处理方式。不同的配置可以在运行时调整过期键处理的速度和性能。

定期删除如何选择进行快速过期扫描还是普通扫描呢?

我们还是来看源码

void databasesCron(void) {
    /* Expire keys by random sampling. Not required for slaves
     * as master will synthesize DELs for us. */
    if (server.active_expire_enabled) {
        if (iAmMaster()) {
            activeExpireCycle(ACTIVE_EXPIRE_CYCLE_SLOW);
        } else {
            expireSlaveKeys();
        }
    }
    ......
}
/* This function gets called every time Redis is entering the
 * main loop of the event driven library, that is, before to sleep
 * for ready file descriptors.
 *
 * Note: This function is (currently) called from two functions:
 * 1. aeMain - The main server loop
 * 2. processEventsWhileBlocked - Process clients during RDB/AOF load
 *
 * If it was called from processEventsWhileBlocked we don't want
 * to perform all actions (For example, we don't want to expire
 * keys), but we do need to perform some actions.
 *
 * The most important is freeClientsInAsyncFreeQueue but we also
 * call some other low-risk functions. */
void beforeSleep(struct aeEventLoop *eventLoop) {
    ......
    if (server.active_expire_enabled && iAmMaster())
        activeExpireCycle(ACTIVE_EXPIRE_CYCLE_FAST);
    ......
}

一般情况下,都是用的普通扫描,beforeSleep(貌似是Redis事件里面的了)用的快速扫描

  • 微信或QQ扫一扫

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

目录