从源码分析 Redis 惰性删除的实现逻辑

陈臣 2023-10-22 11:27:00
作者介绍

陈臣,甲骨文MySQL首席解决方案工程师,公众号《MySQL实战》作者,有大规模的MySQL,Redis,MongoDB,ES的管理和维护经验,擅长MySQL数据库的性能优化及日常操作的原理剖析

 

正文

 

在 Redis 中,对于过期 key 是通过以下两种方式来删除的:

 

  • 惰性删除

 

客户端在访问时,会检查对应的 key 是否过期。如果过期,才删除。

 

需要注意的是,如果过期 key 的访问频率很低,那么它们可能会一直存储在 Redis 中,占用内存资源。

 

  • 定期删除

 

Redis 默认每隔 100ms (执行的频率由 hz 决定,默认为 10)检查一次过期 key,并删除部分过期 key。

 

关于定期删除的实现逻辑,下一篇文章再介绍。

 

看网上很多资料都将 Redis 4.0 引入的 lazyfree 称之为惰性删除,为了避免混淆,这里将 lazyfree 称之为异步删除。惰性删除特指访问时删除。

 

本文将从源码角度分析 Redis 惰性删除的实现逻辑,主要包括以下几部分:

 

  • Redis 访问 key 的实现逻辑。

  • 主动访问过期 key,什么场景下不会删除?

  • 删除操作的实现逻辑,包括 key 的内存及 value 的内存是如何释放的?

  • 同步删除和异步删除的区别。

 

Redis 访问 key 的实现逻辑

 

lookupKey是 Redis 中一个很重要的函数,无论是 key 的查询操作还是写入操作,最后都会调用这个函数。

 

下面,我们看看这个函数的处理逻辑。

 

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
robj *lookupKey(redisDb *db, robj *key, int flags) {    // 基于 key 从 db->dict 中查找对应的元素    dictEntry *de = dictFind(db->dict,key->ptr);    robj *val = NULL;    if (de) {        // 获取 key 对应的 value        val = dictGetVal(de);        // 判断当前实例是否为只读从库        int is_ro_replica = server.masterhost && server.repl_slave_ro;        // expire_flags 是标志位,用来标识 key 能否被删除        int expire_flags = 0;        /* 如果是写操作,且当前实例不是只读从库,           则会将 expire_flags 设置为 EXPIRE_FORCE_DELETE_EXPIRED,即强制删除过期 key */        if (flags & LOOKUP_WRITE && !is_ro_replica)            expire_flags |= EXPIRE_FORCE_DELETE_EXPIRED;        // 如果 flags 中设置了 LOOKUP_NOEXPIRE,则会将 expire_flags 设置为 EXPIRE_AVOID_DELETE_EXPIRED        // 对于设置了 EXPIRE_AVOID_DELETE_EXPIRED 的 key,即使 key 过期了,也不会执行删除操作        if (flags & LOOKUP_NOEXPIRE)             expire_flags |= EXPIRE_AVOID_DELETE_EXPIRED;         // 调用 expireIfNeeded 函数判断 key 是否过期及处理过期 key。        if (expireIfNeeded(db, key, expire_flags)) {            val = NULL;        }    }    // 如果 val 不为 NULL,则会更新它的 LFU 或者 LRU。    if (val) {        if (!hasActiveChildProcess() && !(flags & LOOKUP_NOTOUCH)){            // MAXMEMORY_FLAG_LFU 对应的内存淘汰策略是 volatile-lfu 和 allkeys-lfu            if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {                updateLFU(val);            } else {                val->lru = LRU_CLOCK();            }        }        // 将 stat_keyspace_hits 的值加 1        // stat_keyspace_hits 对应 info stats 中的 keyspace_hits        if (!(flags & (LOOKUP_NOSTATS | LOOKUP_WRITE)))            server.stat_keyspace_hits++;    } else {        if (!(flags & (LOOKUP_NONOTIFY | LOOKUP_WRITE)))            notifyKeyspaceEvent(NOTIFY_KEY_MISS, "keymiss", key, db->id);        // 如果对应的 key 不存在,则会将 stat_keyspace_misses 的值加 1        // stat_keyspace_misses 对应 info stats 中的 keyspace_misses        if (!(flags & (LOOKUP_NOSTATS | LOOKUP_WRITE)))            server.stat_keyspace_misses++;    }
    return val;}

 

该函数的处理流程如下:

 

1)基于 key 从 db->dict 中查找对应的元素。如果元素不存在,则返回 NULL。

 

db->dict 是一张哈希表,用来存储一个数据库中的所有键值对数据。哈希表中的元素(一个键值对)使用 dictEntry 结构体来表示。

 

2)如果元素存在,则会调用 dictGetVal(de) 获取 key 对应的 value。

 

3)设置 expire_flags。expire_flags 是标志位,用来标识 key 能否被删除。

 

不同的场景会设置不同的 expire_flags。

 

4)调用 expireIfNeeded 函数判断 key 是否过期及进行相应处理。

 

5)如果 value 不为 NULL,则会更新 value 的 LFU 或者 LRU。

 

具体是更新 LFU 还是 LRU,由内存淘汰策略 maxmemory-policy 决定。

 

同时,将 stat_keyspace_hits(对应 info stats 中的 keyspace_hits) 的值加 1。

 

6)如果 value 为 NULL,则会将 stat_keyspace_misses(对应 info stats 中的 keyspace_misses)的值加 1。

 

7)返回 value。

 

接下来,我们看看 expireIfNeeded 函数的处理逻辑。

 

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
int expireIfNeeded(redisDb *db, robj *key, int flags) {    // 判断 key 是否过期,如果过期了,则继续处理,否则,直接返回 0    if (!keyIsExpired(db,key)) return 0;     // 如果当前实例是个从库    if (server.masterhost != NULL) {        // 如果执行操作的客户端是从库的 master,则返回 0        if (server.current_client == server.master) return 0;         // 如果没有设置 EXPIRE_FORCE_DELETE_EXPIRED,则返回 1        if (!(flags & EXPIRE_FORCE_DELETE_EXPIRED)) return 1;     }    // 如果设置了 EXPIRE_AVOID_DELETE_EXPIRED,则直接返回 1。    if (flags & EXPIRE_AVOID_DELETE_EXPIRED)        return 1;    // 检查客户端是否处于暂停状态    if (checkClientPauseTimeoutAndReturnIfPaused()) return 1;    // 删除 key    deleteExpiredKeyAndPropagate(db,key);    return 1;}

 

该函数的处理流程如下:

 

1)调用 keyIsExpired(db,key) 函数判断 key 是否过期了。如果过期了,则继续处理。如果没有过期,则返回 0。返回 0,则意味着 key 没有过期,这个时候,lookupKey  会直接返回 value 的值。如果返回 1,lookupKey 会将 value 设置为 NULL,然后返回给客户端。

 

2)如果当前实例是个从库,且 flags 中没有设置 EXPIRE_FORCE_DELETE_EXPIRED,则返回 1。

 

什么时候从库的 flags 会设置  EXPIRE_FORCE_DELETE_EXPIRED 呢?写操作,且从库的 slave-read-only 为 no。

 

3)如果 flags 中设置了 EXPIRE_AVOID_DELETE_EXPIRED,则返回 1。

 

什么时候 flags 会设置 EXPIRE_AVOID_DELETE_EXPIRED 呢?

 

在集群模式下,在执行具体命令之前,首先会判断命令中的 key 所属的节点。在判断的过程中,如果 key 所属的 slot 处于 migrating 或 importing 状态,则会进一步判断 key 是否在当前节点中。判断使用的还是 lookupKey 函数,只不过 flag 中带有 LOOKUP_NOEXPIRE。

 

4)如果客户端处于暂停状态,也会返回 1。

 

5)调用 deleteExpiredKeyAndPropagate 删除 key。

 

 

访问过期 key,什么场景不会删除?

 

基于上述的分析,可以看到,在访问一个过期 key 时,在以下场景,它只会返回 NULL,并不会执行删除操作。

 

  • 从库上的只读操作。注意,对于可写从库(slave-read-only 为 no)上的写操作,同样会执行删除操作。

  • 集群模式,判断命令中的 key 所属的节点时。

  • 客户端处于暂停状态。

 

 

客户端处于暂停状态的几种场景

 

以下是客户端处于暂停状态的几种场景:

 

  • 通过 CLIENT PAUSE 命令暂停客户端操作时。

  • 通过 CLUSTER FAILOVER 命令进行手动 FAILOVER 时。

  • FAILOVER 命令。该命令是 Redis 6.2.0 引入的,用于非集群环境的主从切换,功能类似于集群中的 CLUSTER FAILOVER 命令。

  • 通过 SHUTDOWN 命令关闭实例时,如果没有指定 NOW 选项,则会等待 shutdown-timeout(默认 10 秒)让从库追上主库。在等待的这段时间内,会将客户端置为暂停状态。

 

下面我们看看 deleteExpiredKeyAndPropagate 函数的处理逻辑。

 

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
void deleteExpiredKeyAndPropagate(redisDb *db, robj *keyobj) {    mstime_t expire_latency;    latencyStartMonitor(expire_latency);    // 如果 lazyfree-lazy-expire 为 yes,则会执行异步删除操作,否则还是执行同步删除操作。    // 注意,该参数默认为 no。    if (server.lazyfree_lazy_expire)        dbAsyncDelete(db,keyobj);    else        dbSyncDelete(db,keyobj);    latencyEndMonitor(expire_latency);    latencyAddSampleIfNeeded("expire-del",expire_latency);    notifyKeyspaceEvent(NOTIFY_EXPIRED,"expired",keyobj,db->id);    signalModifiedKey(NULL, db, keyobj);    // 将删除操作发送给从库和 AOF 文件    propagateDeletion(db,keyobj,server.lazyfree_lazy_expire);    // 将 expired_keys 的值加 1    // stat_expiredkeys 对应 info stats 中的 expired_keys    server.stat_expiredkeys++; }

 

该函数的处理流程如下:

 

1)删除 key。具体来说,如果 lazyfree-lazy-expire 为 yes,则会执行异步删除操作,否则还是执行同步删除操作。

 

2)调用 propagateDeletion 函数将删除操作发送给从库和 AOF 文件。

 

3)将 stat_expiredkeys(对应 info stats 中的 expired_keys)的值加 1。

 

删除操作的实现逻辑

 

无论是 dbAsyncDelete 还是 dbSyncDelete,调用的都是 dbGenericDelete。

 

 

  •  
  •  
  •  
  •  
  •  
  •  
  •  
int dbSyncDelete(redisDb *db, robj *key) {    return dbGenericDelete(db, key, 0);}
int dbAsyncDelete(redisDb *db, robj *key) {    return dbGenericDelete(db, key, 1);}

 

接下来我们看看 dbGenericDelete 函数的处理逻辑。

 

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
static int dbGenericDelete(redisDb *db, robj *key, int async) {    // 将 key 从 db->expires 中删除    if (dictSize(db->expires) > 0) dictDelete(db->expires,key->ptr);    // 将 key 从 db->dict 中删除    dictEntry *de = dictUnlink(db->dict,key->ptr);    if (de) {        robj *val = dictGetVal(de);        moduleNotifyKeyUnlink(key,val,db->id);        if (val->type == OBJ_STREAM)            signalKeyAsReady(db,key,val->type);        // 如果是异步删除,则会调用 freeObjAsync 异步释放 value 占用的内存。同时,将 key 对应的 value 设置为 NULL。        if (async) {            freeObjAsync(key, val, db->id);            dictSetVal(db->dict, de, NULL);        }        // 如果是集群模式,还会更新对应 slot 的相关信息        if (server.cluster_enabled) slotToKeyDelEntry(de, db);        // 释放内存        dictFreeUnlinkedEntry(db->dict,de);        return 1;    } else {        return 0;    }}

 

该函数的处理流程如下:

 

1)将 key 从 db->expires 中删除。

 

同 db->dict 一样,db->expires 也是个哈希表,只不过它只存储设置了过期时间的 key,且值是过期时间。

 

2)将 key 从 db->dict 中删除。

 

注意,dictUnlink 只是将键值对从哈希表中删除,并不会释放该键值对占用的内存。

 

3)如果是异步删除,则会调用 freeObjAsync 异步释放 value 占用的内存。同时,将 key 对应的 value 设置为 NULL。

 

4)如果是集群模式,还会更新 key 所在 slot 的相关信息。

 

5)调用 dictFreeUnlinkedEntry 释放内存。

 

下面我们看看 dictFreeUnlinkedEntry 函数的处理逻辑。

 

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
void dictFreeUnlinkedEntry(dict *d, dictEntry *he) {    if (he == NULL) return;    // 释放 key 的内存    dictFreeKey(d, he);    // 释放 value 的内存    dictFreeVal(d, he);    zfree(he);}

 

该函数的处理流程如下:

 

  • 通过 dictFreeKey 释放 key 的内存。

  • 通过  dictFreeVal 释放 value 的内存。

  • 通过 zfree 释放 he 这个结构体的内存。

 

 

dictFreeKey 和 dictFreeVal

 

dictFreeKey 和 dictFreeVal 是两个宏定义,作用类似,都是检查 d 的类型中是否有对应的 Destructor 函数,如果有,则调用该函数释放 key(value)的内存空间。

 

  •  
  •  
  •  
  •  
  •  
  •  
#define dictFreeKey(d, entry) \    if ((d)->type->keyDestructor) \        (d)->type->keyDestructor((d), (entry)->key) #define dictFreeVal(d, entry) \    if ((d)->type->valDestructor) \        (d)->type->valDestructor((d), (entry)->v.val)

 

d 是字典类型,对应的定义和初始化代码如下所示。

 

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
typedef struct dictType {    ...    void (*keyDestructor)(dict *d, void *key);    void (*valDestructor)(dict *d, void *obj);    ...} dictType;/* Db->dict, keys are sds strings, vals are Redis objects. */dictType dbDictType = {    ...    dictSdsDestructor,          /* key destructor */    dictObjectDestructor,       /* val destructor */    ...};

 

可以看到,d 对应的 keyDestructor 和 valDestructor 分别是 dictSdsDestructor 和 dictObjectDestructor。

 

接下来我们看看 dictSdsDestructor 和 dictObjectDestructor 这两个函数的处理逻辑。

 

 

释放 key 的内存

 

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
void dictSdsDestructor(dict *d, void *val){    UNUSED(d);    sdsfree(val);}
void sdsfree(sds s) {    if (s == NULL) return;    s_free((char*)s-sdsHdrSize(s[-1]));}

 

Redis 中的 key 是用 SDS(Simple Dynamic String,简单动态字符串)实现的。

 

所以这里比较简单,直接使用 s_free 来释放这个 SDS 字符串的内存空间。

 

 

释放 value 的内存

 

  •  
  •  
  •  
  •  
  •  
  •  
void dictObjectDestructor(dict *d, void *val){    UNUSED(d);    if (val == NULL) return; /* Lazy freeing will set value to NULL. */    decrRefCount(val);}

 

函数的逻辑比较简单,如果 val 等于 NULL,则直接返回,否则会调用 decrRefCount 函数释放 value 的内存。

 

在上面分析 dbGenericDelete 函数时提到过,如果是异步删除,则会将 key 对应的 value 设置为 NULL。所以,对于异步删除操作, dictObjectDestructor 会直接返回,不会调用 decrRefCount。

 

如果是同步删除,才会调用 decrRefCount 函数。

 

下面我们分析下 decrRefCount 函数的处理逻辑。

 

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
void decrRefCount(robj *o) {    if (o->refcount == 1) {        switch(o->type) {        case OBJ_STRING: freeStringObject(o); break;        case OBJ_LIST: freeListObject(o); break;        case OBJ_SET: freeSetObject(o); break;        case OBJ_ZSET: freeZsetObject(o); break;        case OBJ_HASH: freeHashObject(o); break;        case OBJ_MODULE: freeModuleObject(o); break;        case OBJ_STREAM: freeStreamObject(o); break;        default: serverPanic("Unknown object type"); break;        }        zfree(o);    } else {        if (o->refcount <= 0) serverPanic("decrRefCount against refcount <= 0");        if (o->refcount != OBJ_SHARED_REFCOUNT) o->refcount--;    }}

 

可以看到,decrRefCount 函数针对不同的数据类型,会调用不同的函数来处理。

 

 

Redis 如何释放列表的内存

 

以列表类型为例,decrRefCount 会调用 freeListObject 函数来处理。

 

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
// 如果列表对象的编码方式是 OBJ_ENCODING_QUICKLIST,则调用 quicklistRelease 函数// quicklist(快速列表)是 Redis 3.2 版本引入的一种新的编码方式,用来替代之前的 ziplist 和 linkedlistvoid freeListObject(robj *o) {    if (o->encoding == OBJ_ENCODING_QUICKLIST) {        quicklistRelease(o->ptr);    } else {        serverPanic("Unknown list encoding type");    }}
void quicklistRelease(quicklist *quicklist) {    unsigned long len;    quicklistNode *current, *next;
    current = quicklist->head;    len = quicklist->len;    while (len--) {        next = current->next;
        zfree(current->entry);        quicklist->count -= current->count;
        zfree(current);
        quicklist->len--;        current = next;    }    quicklistBookmarksClear(quicklist);    zfree(quicklist);}

 

该函数主要是遍历 quicklist 的每个节点,并释放节点中的元素(entry)和节点本身,最后释放 quicklist 本身所占用的内存。

 

这里实际上也给了我们一个启示,在 Redis 4.0 之前(异步删除是 Redis 4.0 才引入的),如果要删除一个大 key,建议批量删除、分而治之,毕竟 Redis 底层也是这么玩的。

 

同步删除和异步删除的区别

 

首先抛出结论,无论是同步删除,还是异步删除,最后都会调用 decrRefCount 函数来释放 value 的内存。

 

只不过同步删除是在主线程中进行的。如果删除的是一个大 key,这个删除操作可能会占用主线程较长的时间,从而导致主线程无法及时响应其它业务请求。

 

而异步删除则是将删除操作放到一个后台任务列表中,通过后台线程异步删除。

 

需要注意的是,不是所有的异步删除操作都会通过后台线程异步处理。

 

关于这一点,我们可以看看 freeObjAsync 函数的实现逻辑。

 

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
void freeObjAsync(robj *key, robj *obj, int dbid) {    // 首先评估释放一个对象所需的成本    size_t free_effort = lazyfreeGetFreeEffort(key,obj,dbid);    // 只有大于 LAZYFREE_THRESHOLD 的异步操作才会通过后台线程异步删除    if (free_effort > LAZYFREE_THRESHOLD && obj->refcount == 1) {        atomicIncr(lazyfree_objects,1);        // lazyfreeFreeObject 同样是调用 decrRefCount 函数来释放 value 的内存        bioCreateLazyFreeJob(lazyfreeFreeObject,1,obj);    } else {        decrRefCount(obj);    }}

 

可以看到,只有 free_effort 大于 LAZYFREE_THRESHOLD(默认 64)的异步操作才会放到异步删除队列中,通过后台线程处理。

 

free_effort 反映了释放一个对象所需的成本。

 

对于字符串类型,free_effort 为 1。对于列表类型,free_effort 等于链表节点(一个节点可以存储多个元素)数量。对于集合和哈希类型,free_effort 等于元素的个数。

 

总结

 

如果访问了从库的过期 key,从库只是返回 NULL,不会执行删除操作。注意,返回 NULL 是 Redis 3.2 之后的行为。

 

在 Redis 3.2 之前,如果访问了从库的过期 key,从库会返回 value。

 

所以,如果使用的是 Redis 3.2 之前的版本,不建议开启读写分离。

 

从库默认是只读的(slave-read-only 为 yes),如果配置为了可写(slave-read-only 为 no),对于写操作,当访问到过期 key 时同样会执行删除操作。

 

无论是同步删除,还是异步删除,本质上,没有太大区别,都是调用同一个函数来释放内存。

 

只不过同步删除是在主线程中进行的,如果碰到大 key,会导致 Redis 被阻塞。而异步删除则是由专门的后台线程异步处理的。

 

lazyfree-lazy-expire 默认为 no,所以在访问到过期 key 时,不会进行异步删除。线上建议将 lazyfree-lazy-expire 设置为 yes。

 

不是所有的异步删除操作都会通过后台线程来处理,这里需考虑成本(free_effort)。

 

对于字符串类型,因为它的 free_effort 永远为 1,所以只会通过主线程来处理。

 

在 Redis 4.0 之前,因为没有引入异步删除(lazyfree),如果要删除一个大 key,建议批量删除。

 

作者丨陈臣
来源丨公众号:MySQL实战(ID:MySQLInAction)
dbaplus社群欢迎广大技术人员投稿,投稿邮箱:editor@dbaplus.cn
最新评论
访客 2024年04月08日

如果字段的最大可能长度超过255字节,那么长度值可能…

访客 2024年03月04日

只能说作者太用心了,优秀

访客 2024年02月23日

感谢详解

访客 2024年02月20日

一般干个7-8年(即30岁左右),能做到年入40w-50w;有…

访客 2023年08月20日

230721

活动预告