blog | percy

life

0%

redis的过期策略及源码分析

发表于 更新于 分类于

[TOC]

设置过期时间的常见方式

1
2
3
4
5
6
7
8
9
10
11
expire key ttl
expireat key unix_timestamp

pexpire key ttl
pexpireat key unix_timestamp

SETEX key seconds value
PSETEX key milliseconds value
SET key value [EX seconds] [PX milliseconds] [NX|XX]

# 在 redis 的实现中，expire, expireat, pexpire 这三种最终都是使用 pexpireat 来实现的

过期键值对的删除有三种策略

定时删除

设置一个定时器和回调函数，时间一到就调用回调函数删除键值对。优点是及时删除，缺点是需要为每个键值对都设置定时器，比较麻烦(其实可以用timer_fd的，参考muduo定时任务的实现)

惰性删除

只有当再次访问该键时才判断是否过期，如果过期将其删除。优点是不需要为每个键值对进行时间监听，缺点是如果这个键值对一直不被访问，那么即使过期也会一直残留在数据库中，占用不必要的内存

周期删除

每隔一段时间执行一次删除过期键值对的操作。优点是既不需要监听每个键值对导致占用CPU，也不会一直不删除导致占用内存，缺点是不容易确定删除操作的执行时长和频率
Redis采用惰性删除和周期删除两种策略，通过配合使用，服务器可以很好的合理使用CPU时间和避免内不能空间的浪费

redis 过期策略的实现

redis expire api

Redis是如何实现定时删除的，在数据库结构redisDb中，可以发现除了上篇提到的用于保存键值对的dict字典外，另有一个字典变量expires，实际上正是它保存着键和其过期时间(绝对时间)。当执行完SET命令后，两个字典的数据分布为:

1
2
3
4
typedef struct redisDb {
    dict *dict;                 /* The keyspace for this DB */
    dict *expires;              /* Timeout of keys with a timeout set */
} redisDb;

设置键的过期时间，setExpire

1
2
3
4
5
6
7
8
9
10
11
12
void setExpire(client *c, redisDb *db, robj *key, long long when) {
    dictEntry *kde, *de;

    /* Reuse the sds from the main dict in the expire dict */
     /* 从数据字典中寻找键节点， kde 中包含 key */
    kde = dictFind(db->dict,key->ptr);
    serverAssertWithInfo(NULL,key,kde != NULL);
    /* 从时间字典中寻找键节点，如果不存在则创建一个 */
    de = dictAddOrFind(db->expires,dictGetKey(kde));
    /* 设置键节点的值，值为过期时间(绝对时间) */
    dictSetSignedIntegerVal(de,when);
}

dictSetSignedIntegerVal是宏定义，设置键节点de的值为when。因为哈希节点中的值结构是联合，可以存储不同大小的数字，也可以通过void*指针存储其它类型，这里过期时间是long long类型，所以可以存在int64_t类型上。

获取键的过期时间，getExpire

1
2
3
4
5
6
7
8
9
10
11
12
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;

    /* 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);
}

删除键的过期时间，removeExpire

1
2
3
4
5
6
int removeExpire(redisDb *db, robj *key) {
    /* An expire may only be removed if there is a corresponding entry in the
     * main dict. Otherwise, the key will never be freed. */
    serverAssertWithInfo(NULL,key,dictFind(db->dict,key->ptr) != NULL);
    return dictDelete(db->expires,key->ptr) == DICT_OK;
}

redis 过期删除的实现

Redis 采用惰性删除和周期删除两种策略，通过配合使用，服务器可以很好的合理使用CPU时间和避免内不能空间的浪费。

惰性删除

惰性删除是指在对每一个键进行读写操作时，先判断一下这个键是否已经过期，如果过期则将其删除。该操作由expireIfNeeded函数完成。

get 操作的流程
1
2
3
4
5
6
7
8
9
10
11
12
13
int getGenericCommand(client *c)
    
robj *lookupKeyReadOrReply(client *c, robj *key, robj *reply) {}

robj *lookupKeyRead(redisDb *db, robj *key) {
    return lookupKeyReadWithFlags(db,key,LOOKUP_NONE);
}

// 进入这个函数会调用  (expireIfNeeded(db,key)， 判断 key 是否过期
robj *lookupKeyReadWithFlags(redisDb *db, robj *key, int flags) {}

// lookup 最终寻找 key 对应的 val。 在redis中，所有的键值对都会用内置的哈希表保存在内存里，因此，在lookupKey的实现里，先使用dictFind函数查找传进来的key是否存在哈希表中，如果找到，则调用dictGetVal获取哈希节点对象的value属性，否则，返回NULL，函数的时间复杂度是O(1)。
robj *lookupKey(redisDb *db, robj *key, int flags) {}
主从实现惰性删除的方法
  • 如果当前请求是在 master 节点上，且当前的 key 已经过期，那么直接删除过期的 key。
  • 如果当前请求是在 slave 节点上，且当前 key 已经过期， 直接返回 null，不做删除。（删除操作只能由 master 执行并同步给 slave 节点）

周期删除

Redis服务器会周期性地执行server.c/serverCron函数，在这个函数中执行的databasesCron函数会调用activeExpireCycle函数，这个函数在时间字典(expires)中随机选择若干键节点，判断其是否过期，如果过期则将其删除。

循环函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void activeExpireCycle(int type) {
    // 循环次数和时间：dbs_per_call：上一次执行越就久，dbs_per_call越大， timelimit_exit：最多执行这么多时间
    for (j = 0; j < dbs_per_call && timelimit_exit == 0; j++) {
         // 循环 db：当前 db 过期的多才重复执行
        do {
            while (sampled < num && checked_buckets < max_buckets) {
                /* Get the next entry now since this entry may get deleted. */
                 while(de) {
                        dictEntry *e = de;
                        de = de->next;

                        ttl = dictGetSignedIntegerVal(e)-now;
                        if (activeExpireCycleTryExpire(db,e,now)) expired++;
                 }
            }
           
        } (sampled == 0 || (expired*100/sampled) > config_cycle_acceptable_stale);
    }
    
}
真正删除的代码
1
2
// 真正删除一个 key， Helper function for the activeExpireCycle() function.
int activeExpireCycleTryExpire(redisDb *db, dictEntry *de, long long now) {}

总结

Redis 采用惰性删除和周期删除两种策略，通过配合使用，服务器可以很好的合理使用CPU时间和避免内不能空间的浪费。

参考

redis 指令的执行过程

redis源码–key的过期策略： 这个源码有点老了，可以看最新的源码。

ASAP: as sonn as possible