6. key删除策略

redis中，对于过期key的淘汰机制，可以分为以下两种：

  • 定期删除：一种主动删除策略，定期去轮询存储了key的过期时间的字典。
  • 惰性删除：在寻找/写入dictEntry的时候判断是否过期，属于被动删除策略。

6.1 惰性删除

惰性删除的代码，入口在db.c中的expireIfNeeded，该方法由执行查找命令或写入命令的方法调用，在执行真正的命令之前，做key的删除判断以及删除操作：

int expireIfNeeded(redisDb *db, robj *key) {
  	//设定了过期时间且未过期的key会在这一步直接返回
    if (!keyIsExpired(db,key)) return 0;
		//当前redis节点过期了，但是存在master节点。
  	//意味着当前属于slave节点，返回1，由master执行删除后同步至slave
    if (server.masterhost != NULL) return 1;
  	
  	//过期key的数量+1
    server.stat_expiredkeys++;
  	
  	//把过期的key的消息传播到slave，同时将该key的删除命令写入到aof文件
    propagateExpire(db,key,server.lazyfree_lazy_expire);
  	//通知监听了该key的客户端，通知key的过期事件
    notifyKeyspaceEvent(NOTIFY_EXPIRED,
        "expired",key,db->id);
  	//根据设定的删除方式，决定采用同步删除还是异步删除
    return server.lazyfree_lazy_expire ? dbAsyncDelete(db,key) :
                                         dbSyncDelete(db,key);
}

int keyIsExpired(redisDb *db, robj *key) {
  	//获得设定的过期时间戳
    mstime_t when = getExpire(db,key);
    mstime_t now;
		//如果时间戳小于0，说明没有设置过期时间
    if (when < 0) return 0; 

    //loading状态下不允许进行过期判断
    if (server.loading) return 0;

    //获得系统当前时间
    if (server.lua_caller) {
        now = server.lua_time_start;
    }
    else if (server.fixed_time_expire > 0) {
        now = server.mstime;
    }
    else {
        now = mstime();
    }

    //执行判断
    return now > when;
}

long long getExpire(redisDb *db, robj *key) {
    dictEntry *de;

   	//如果存储expireTime的字典为空 或者 当前key没有设置过期时间，返回-1
    if (dictSize(db->expires) == 0 ||
       (de = dictFind(db->expires,key->ptr)) == NULL) return -1;

    //安全保护机制，确保存储在expireDict中的key也存在于dataDict中
    serverAssertWithInfo(NULL,key,dictFind(db->dict,key->ptr) != NULL);
  	//取得过期时间戳并返回
    return dictGetSignedIntegerVal(de);
}

简略画出这段代码调用的时序图：

sequenceDiagram 　　participant expireIfNeeded 　　participant keyIsExpired 　　participant getExpire 　　participant dictFind 　　expireIfNeeded->>keyIsExpired:invoke 　　keyIsExpired->>getExpire:invoke 　　getExpire->>dictFind:invoke 　　Note OVER dictFind: 从expireDict中获取value 　　dictFind-->>getExpire:return value 　　Note OVER getExpire: 解析value获取过期时间戳 　　getExpire-->>keyIsExpired:return 　　Note OVER keyIsExpired: 将时间戳和系统当前时间比较 　　keyIsExpired-->>expireIfNeeded:return 　　Note OVER expireIfNeeded: 判断是否过期、是否为master节点 　　Note OVER expireIfNeeded: 通知slave节点进行key删除，并将删除命令写入AOF文件 　　Note OVER expireIfNeeded: 向监听了key的客户端发布key过期事件 　　Note OVER expireIfNeeded: 根据预设的删除方式，选择同步或者是异步删除key对应的dictEntry

其中，在使用具体的删除方式时，涉及到一个值lazyfree_lazy_expire，它需要我们在redis.conf文件中进行配置：

lazyfree-lazy-expire no

可以看到默认值为no，即代表在删除是会采用同步删除，如果将该项置为yes，则采用异步删除的模式。

接下来，分别来看一下同步删除和异步删除的代码实现。

6.1.1 同步删除

同步删除的代码比较简单：

int dbSyncDelete(redisDb *db, robj *key) {
    //如果expireDict大于0，先进行expireDict的删除
    if (dictSize(db->expires) > 0) dictDelete(db->expires,key->ptr);
  	//再进行dataDict的删除
    if (dictDelete(db->dict,key->ptr) == DICT_OK) {
      	//如果当前是集群模式，则定位到具体存储dictEntry的slot，进行remove操作
        if (server.cluster_enabled) slotToKeyDel(key);
        return 1;
    } else {
        return 0;
    }
}

int dictDelete(dict *ht, const void *key) {
    return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR;
}

static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
    uint64_t h, idx;
    dictEntry *he, *prevHe;
    int table;
		//dataDict和expireDict同时为空的情况下直接返回NULL
    if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL;
		//判断是否正在扩容，如果正在扩容则帮助推进hashTable的expand过程
    if (dictIsRehashing(d)) _dictRehashStep(d);
  	//得到hash值
    h = dictHashKey(d, key);

    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
      	//定位到存储在hash桶中的链表头节点
        he = d->ht[table].table[idx];
        prevHe = NULL;
      	//开始从链表的头部开始，依次向后查找
        while(he) {
            if (key==he->key || dictCompareKeys(d, key, he->key)) {
              	//链表解链操作
                if (prevHe)
                    prevHe->next = he->next;
                else
                    d->ht[table].table[idx] = he->next;
                if (!nofree) {
                  	//nofree传入的值为0，表示立马释放dictEntry以及其中key和value占用的内存
                    dictFreeKey(d, he);
                    dictFreeVal(d, he);
                    zfree(he);
                }
                d->ht[table].used--;
                return he;
            }
            prevHe = he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    return NULL;
}

其中释放内存主要是三个方法dictFreeKey，dictFreeVal，zfree，前两个方法直接调用key和value的destructor，依次看看key和value的释放过程：

define dictFreeKey(d, entry) 
    if ((d)->type->keyDestructor) 
        (d)->type->keyDestructor((d)->privdata, (entry)->key)

define dictFreeVal(d, entry) 
    if ((d)->type->valDestructor) 
        (d)->type->valDestructor((d)->privdata, (entry)->v.val)

在server.c中，可以找到对应的keyDestructor和valDestructor的原型：

dictType dbDictType = {
    dictSdsHash,               
    NULL,                       
    NULL,                       
    dictSdsKeyCompare,     
  	//负责key的销毁
    dictSdsDestructor, 
  	//负责value的销毁
    dictObjectDestructor  
};

可以看到，key的销毁实际上就是释放存储具体key值的sds：

void dictSdsDestructor(void *privdata, void *val)
{
    DICT_NOTUSED(privdata);

    sdsfree(val);
}

但是对于value，就会存在比较多的类型：string、list、set、zset、hash…，根据redisobj中的type调用不同的free方法，同时value的删除依据就是引用计数法：

void dictObjectDestructor(void *privdata, void *val)
{
    DICT_NOTUSED(privdata);

    if (val == NULL) return;
    decrRefCount(val);
}

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--;
    }
}

不同的value类型有着不同的释放内存方法，但是它们都调用了zfree，接下来看看zfree的方法内部实现：

void zfree(void *ptr) {
  	//ptr指针为void类型，可以指向任意数据类型的内存
#ifndef HAVE_MALLOC_SIZE
    void *realptr;
    size_t oldsize;
#endif
		//根据不同的宏定义，释放不同大小的内存，但是都调用了free方法
    if (ptr == NULL) return;
#ifdef HAVE_MALLOC_SIZE
    update_zmalloc_stat_free(zmalloc_size(ptr));
    free(ptr);
#else
    realptr = (char*)ptr-PREFIX_SIZE;
    oldsize = *((size_t*)realptr);
    update_zmalloc_stat_free(oldsize+PREFIX_SIZE);
    free(realptr);
#endif
}

底层调用了free接口，这属于操作系统提供的标准库函数，以我的macos为例，free函数存在于_malloc.h头文件定义中。一些linux系统可能会定义在stdlib标准库头文件中。