redis之key过期源码分析

redis

简述

redis的所有数据结构都可以设置过期时间，当key过期后再查询该key返回null。

redis实现key自动过期是通过额外保存需要自动过期的key和该key的过期时间，然后通过主动删除和定时任务删除两种机制来将过期的key移除并回收内存。在redis4.0版本引入了异步删除的机制，对于删除对象大小大于64字节的key，先通过Unlink方法软删除后放入回收队列中，由其他线程异步回收内存空间，减少主线程的在内存回收上消耗的时间。

1
2
3
4
5
6
7
8
9
10
typedef struct redisDb {
    dict *dict; // 保存key-value数据
    dict *expires;  // 保存等待过期时间的key和对应的过期时间
    dict *blocking_keys;
    dict *ready_keys;
    dict *watched_keys;
    int id;
    long long avg_ttl;
    list *defrag_later;
} redisDb;

image

设置过期

redis添加自动过期的key时，先向hash结构数据redisDb.dict添加该key和key对应的值。添加成功后，调用setExpire方法向hash结构数据redisDb.expires添加该key和key对应的过期时间，过期时间的单位为毫秒。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
void setGenericCommand(client *c, int flags, robj *key, robj *val, robj *expire, int unit, robj *ok_reply, robj *abort_reply) {
    long long milliseconds = 0; /* initialized to avoid any harmness warning */

    // 计算key的过期时间
    if (expire) {
        if (getLongLongFromObjectOrReply(c, expire, &milliseconds, NULL) != C_OK)
            return;
        if (milliseconds <= 0) {
            addReplyErrorFormat(c,"invalid expire time in %s",c->cmd->name);
            return;
        }
        if (unit == UNIT_SECONDS) milliseconds *= 1000;
    }

    if ((flags & OBJ_SET_NX && lookupKeyWrite(c->db,key) != NULL) ||
        (flags & OBJ_SET_XX && lookupKeyWrite(c->db,key) == NULL))
    {
        addReply(c, abort_reply ? abort_reply : shared.null[c->resp]);
        return;
    }
    // 添加key
    setKey(c->db,key,val);
    server.dirty++;
    // 给key设置过期时间
    if (expire) setExpire(c,c->db,key,mstime()+milliseconds);
    notifyKeyspaceEvent(NOTIFY_STRING,"set",key,c->db->id);
    if (expire) notifyKeyspaceEvent(NOTIFY_GENERIC,
        "expire",key,c->db->id);
    addReply(c, ok_reply ? ok_reply : shared.ok);
}

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

    // 从db.dict查询key，校验该key已经保存到redis
    kde = dictFind(db->dict,key->ptr);
    serverAssertWithInfo(NULL,key,kde != NULL);
    // 向hash表db.expires添加key和key的过期时间，用于过期删除key
    de = dictAddOrFind(db->expires,dictGetKey(kde));
    dictSetSignedIntegerVal(de,when);

    int writable_slave = server.masterhost && server.repl_slave_ro == 0;
    if (c && writable_slave && !(c->flags & CLIENT_MASTER))
        rememberSlaveKeyWithExpire(db,key);
}

自动过期

过期key的删除回收分为主动删除和定时删除两种策略：

  • 主动删除：对key删改查操作时先判断该key是否已过期，如过期则删除回收该key
  • 定时删除：主线程每100毫秒从redisDb.expires中随机选择20个key，删除其中已过期的key。如果过期的key的比例超过1/4则重复该操作直到达到时间上限（默认25毫秒）

主动删除

对于key的删改查操作，先查询hash表redisDb.expires判断该key是否已经过期，如果key已过期，则默认调用dbAsyncDelete方法异步删除回收该key的内存空间；若key未过期，继续进行删改查操作。

另外在redis主从架构下，从节点不处理过期机制，通过等待主节点的指令直接删除对应的key。因此当网络延迟较大时，存在主节点中已过期的key能在从节点查询出来的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
robj *lookupKeyRead(redisDb *db, robj *key) {
    // 查询操作
    return lookupKeyReadWithFlags(db,key,LOOKUP_NONE);
}

robj *lookupKeyReadWithFlags(redisDb *db, robj *key, int flags) {
    robj *val;

    // 查询key的值前先检查该key是否已过期
    // 如果key过期则删除回收该key
    if (expireIfNeeded(db,key) == 1) {
        if (server.masterhost == NULL) {
            server.stat_keyspace_misses++;
            notifyKeyspaceEvent(NOTIFY_KEY_MISS, "keymiss", key, db->id);
            return NULL;
        }

        if (server.current_client &&
            server.current_client != server.master &&
            server.current_client->cmd &&
            server.current_client->cmd->flags & CMD_READONLY)
        {
            server.stat_keyspace_misses++;
            notifyKeyspaceEvent(NOTIFY_KEY_MISS, "keymiss", key, db->id);
            return NULL;
        }
    }
    // key未过期，查询key对应的值
    val = lookupKey(db,key,flags);
    if (val == NULL) {
        server.stat_keyspace_misses++;
        notifyKeyspaceEvent(NOTIFY_KEY_MISS, "keymiss", key, db->id);
    }
    else
        server.stat_keyspace_hits++;
    return val;
}

int expireIfNeeded(redisDb *db, robj *key) {
    // 查询redisDb.expires判断该key是否过期
    if (!keyIsExpired(db,key)) return 0;

    // 从节点不处理过期机制，等待主节点的指令直接删除对应的key
    // 因此存在网络延迟大时，已过期的key能在从节点查询出来的问题
    if (server.masterhost != NULL) return 1;

    server.stat_expiredkeys++;
    propagateExpire(db,key,server.lazyfree_lazy_expire);
    notifyKeyspaceEvent(NOTIFY_EXPIRED,
        "expired",key,db->id);
    // 默认使用dbAsyncDelete异步删除回收
    return server.lazyfree_lazy_expire ? dbAsyncDelete(db,key) :
                                         dbSyncDelete(db,key);
}

定时删除

databasesCron方法由主线程每100毫秒调用一次，其中的activeExpireCycle方法则是删除回收过期key的关键方法，其入参有两个值：ACTIVE_EXPIRE_CYCLE_FAST和ACTIVE_EXPIRE_CYCLE_SLOW：

  • ACTIVE_EXPIRE_CYCLE_FAST：表示快速删除回收过期key，该场景下每次删除回收的时间上限为1毫秒，当主线程处理完外部请求后等待新请求前阻塞时会使用该参数；
  • ACTIVE_EXPIRE_CYCLE_SLOW：表示慢删除回收过期key，该场景下每次删除回收的时间上限为25毫秒，当主线程每100毫秒执行定时任务时使用该参数；

由于主线程每100毫秒会调用一次activeExpireCycle方法回收过期key，因此存在极端情况下同一时刻redis中大量数据同时过期，会导致每100毫秒一次的定时任务activeExpireCycle需要花费25毫秒的时间删除回收过期key，从而出现客户端请求等待阻塞的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
void databasesCron(void) {
    if (server.active_expire_enabled) {
        if (server.masterhost == NULL) {
            // 定时任务使用慢扫描回收，扫描回收的时间上限为25毫秒
            activeExpireCycle(ACTIVE_EXPIRE_CYCLE_SLOW);
        } else {
            expireSlaveKeys();
        }
    }
    ...
}

#define ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP 20
void activeExpireCycle(int type) {
    ...

    // timelimit = 1000000*25/10/100 = 25_000微妙 = 25毫秒
    timelimit = 1000000*ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC/server.hz/100;
    timelimit_exit = 0;
    if (timelimit <= 0) timelimit = 1;

    // 快速扫描回收，扫描回收时间上限为1毫秒
    // 慢扫描回收，扫描回收时间上限默认timelimit = 25毫秒
    if (type == ACTIVE_EXPIRE_CYCLE_FAST)
        timelimit = ACTIVE_EXPIRE_CYCLE_FASTf_DURATION; /* in microseconds. */

    long total_sampled = 0;
    long total_expired = 0;

    for (j = 0; j < dbs_per_call && timelimit_exit == 0; j++) {
        int expired;
        redisDb *db = server.db+(current_db % server.dbnum);

        current_db++;

        do {
            unsigned long num, slots;
            long long now, ttl_sum;
            int ttl_samples;
            iteration++;

            if ((num = dictSize(db->expires)) == 0) {
                db->avg_ttl = 0;
                break;
            }
            slots = dictSlots(db->expires);
            now = mstime();

            if (num && slots > DICT_HT_INITIAL_SIZE &&
                (num*100/slots < 1)) break;

            expired = 0;
            ttl_sum = 0;
            ttl_samples = 0;

            // 每次从redisDb.expires随机获取20个key
            if (num > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP)
                num = ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP;

            while (num--) {
                dictEntry *de;
                long long ttl;

                // 从redisDb.expires随机获取一个key
                if ((de = dictGetRandomKey(db->expires)) == NULL) break;
                ttl = dictGetSignedIntegerVal(de)-now;
                // 如果key已过期，默认调用dbAsyncDelete异步删除回收，并累计过期的key数量
                if (activeExpireCycleTryExpire(db,de,now)) expired++;
                if (ttl > 0) {
                    ttl_sum += ttl;
                    ttl_samples++;
                }
                total_sampled++;
            }
            total_expired += expired;

            if (ttl_samples) {
                long long avg_ttl = ttl_sum/ttl_samples;

                if (db->avg_ttl == 0) db->avg_ttl = avg_ttl;
                db->avg_ttl = (db->avg_ttl/50)*49 + (avg_ttl/50);
            }

            // 如果过期key的扫描回收时间达到了上限，则结束此次扫描回收操作
            if ((iteration & 0xf) == 0) {
                elapsed = ustime()-start;
                if (elapsed > timelimit) {
                    timelimit_exit = 1;
                    server.stat_expired_time_cap_reached_count++;
                    break;
                }
            }
        // 每次随机获取的20个key如果超过1/4已经过期，则重复操作删除回收过期的key
        } while (expired > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP/4);
    }
    ...
}

异步删除

在redis4.0版本默认调用dbAsyncDelete方法删除回收key，但实际上dbAsyncDelete会判断该key的对象大小，如果key的对象大小超过64字节时才会真正使用异步删除逻辑，将该key放入BIO队列由其他线程删除回收内存空间；否则仍然使用同步删除逻辑直接回收内存空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#define LAZYFREE_THRESHOLD 64
int dbAsyncDelete(redisDb *db, robj *key) {
    if (dictSize(db->expires) > 0) dictDelete(db->expires,key->ptr);

    dictEntry *de = dictUnlink(db->dict,key->ptr);
    if (de) {
        robj *val = dictGetVal(de);
        size_t free_effort = lazyfreeGetFreeEffort(val);

        // 如果待删除key的长度超过64字节，异步删除
        if (free_effort > LAZYFREE_THRESHOLD && val->refcount == 1) {
            atomicIncr(lazyfree_objects,1);
            // 放入BIO队列中由其他进程回收内存空间
            bioCreateBackgroundJob(BIO_LAZY_FREE,val,NULL,NULL);
            dictSetVal(db->dict,de,NULL);
        }
    }

    // 待删除key长度不超过64字节，依然使用同步删除
    if (de) {
        dictFreeUnlinkedEntry(db->dict,de); // 同步回收内存空间
        if (server.cluster_enabled) slotToKeyDel(key);
        return 1;
    } else {
        return 0;
    }
}
>