我要评论redis过期键删除策略
redis是内存型数据库，可对键设置过期时间，当键过期时时怎么淘汰这些键的呢？
我们先来想一想，如果让我们设计，我们会想到哪些过期删除策略呢？
- 定时器，创建一个定时器，定时器经过expire时间后开始执行键的删除操作。
- 周期删除，启动一个周期性的后台任务，扫描键，发现过期键则进行删除。
- 惰性删除，当访问一个键时，如果发现键过期，再执行删除。
- 首先，定时器方式，资源消耗很大，不可能为每一个键创建一个定时器；另外当过期时间被重置时，定时器需要复位和重置，相当繁琐。
- 其次，周期删除，过期键的删除与周期执行时间有关，可能会存在过期键很长时间没有被删除的情况，同时如果本周期内过期键很多，删除耗时会很长，增加服务负担。
- 最后，惰性删除，只针对热点数据有效，有些冷数据可能会常驻内存。
而redis采用了周期删除和惰性删除结合的方式，同时定期删除会限制删除耗时和键数来防止依次定期删除执行太久。
- 惰性删除(访问到过期键时删除)，
- 定期删除(周期性的后台删除任务)。在源码中两种方式的入口如下:
定期删除
redis在启动初始化时（initserver）会注册周期任务aecreatetimeevent(server.el, 1, servercron, null, null), servercron函数中包含了所有周期任务，其中databasescron 是操作数据库的函数。
- 对于master节点执行过期键删除
activeexpirecycle - 对于从节点执行
expireslavekeys, 这里注意如果从节点只读，那么是不会有过期键淘汰的，此时依靠的是master节点同步删除命令。但是对于可写的从节点，会有一个dict(slavekeyswithexpire)记录从节点设置了过期键的节点，从这个dict中进行过期淘汰
周期淘汰过期键的任务activeexpirecycle，该函数会一次遍历db，检查db->expires字典(存储设置了过期时间键的ttl)，对过期键进行删除。
activeexpirecycle核心流程
下面是activeexpirecycle函数的主要逻辑，我们省略很多代码，来看下淘汰的主要流程是什么。
- 首先是根据本次淘汰需要遍历的db数(
dbs_per_call), 接着上一次遍历的db开始继续遍历。timelimit_exit 表示一次定期淘汰策略执行是有时间限制的。 - 对每个db来说，在
do{}while()中进行键的淘汰，我们来看一下退出条件：直到过期比例(expired*100/sampled)小于配置参数(config_cycle_acceptable_stale),退出循环，认为该db淘汰任务执行完毕。 - 然后对每个db来说，需要依次遍历两个dict(0:前台字典，1:rehash用的字典)。此时的退出条件是
sampled >= num || checked_buckets >= max_buckets,也就是说采样键数量(sampled)达到设定值或者hash槽数量(checked_buckets)达到设定值。这里说明，在淘汰每个db中的键时，采样和检查的键数时有限的。 - 对于两个字典来说，依赖
db->expires_cursor的自增来访问每个hash槽，验证该槽上的键是否过期。
// 依次遍历db
for (j = 0; j < dbs_per_call && timelimit_exit == 0; j++) {
unsigned long expired, sampled;
redisdb *db = server.db+(current_db % server.dbnum);
current_db++;
// 针对每个db
do {
while (sampled < num && checked_buckets < max_buckets) {
// 针对每个字典
for (int table = 0; table < 2; table++) {
if (table == 1 && !dictisrehashing(db->expires)) break;
unsigned long idx = db->expires_cursor;
idx &= dictht_size_mask(db->expires->ht_size_exp[table]);
dictentry *de = db->expires->ht_table[table][idx];
checked_buckets++;
while(de) {
dictentry *e = de;
de = de->next;
if (activeexpirecycletryexpire(db,e,now)) expired++;
sampled++;
}
}
db->expires_cursor++;
}
} while (sampled == 0 || (expired*100/sampled) > config_cycle_acceptable_stale);
}
淘汰相关的关键参数
有一些关键参数用于控制周期任务执行的时间在一个可接受的范围。
- 采样键数
num的设置。num是控制每个db的采样键数。num取的是过期字典db->expire的键数量和config_keys_per_loop中的最小值，config_keys_per_loop = active_expire_cycle_keys_per_loop + active_expire_cycle_keys_per_loop/4*effort, active_expire_cycle_keys_per_loop=20， effort是配置参数属于[0,9]区间，则config_keys_per_loop 属于[20, 65]区间。 - 采样槽数
max_buckets, 控制的是最大hash槽数。而访问hash槽采用的是自增index的方式，所以可能存在大量的hash槽对应的空节点，因此最大hash槽的设置是大于采样键数的，取得是20倍采样键数。
- 单次执行时间限制 timelimit、timelimit_exit。
timelimit = config_cycle_slow_time_perc*1000000/server.hz/100;, 执行时间是根据cpu占比(active_expire_cycle_slow_time_perc +2*effort)估算出来的一个时间。每执行16次do{}while()中的内容会计算一次耗时。 - active_expire_cycle_fast，快速淘汰模式。在快速淘汰模式下，会增加单词执行的时间限制和遍历的db数。
activeexpirecycletryexpire
该函数会判断键是否过期，过期的话执行删除。首先计算节点de是否过期， now > t(改键的过期时间戳) 时表明该键已经过期，然后生成一个key对象，执行从db中删除指定key的操作。
int activeexpirecycletryexpire(redisdb *db, dictentry *de, long long now) {
long long t = dictgetsignedintegerval(de);
if (now > t) {
sds key = dictgetkey(de);
robj *keyobj = createstringobject(key,sdslen(key));
deleteexpiredkeyandpropagate(db,keyobj);
decrrefcount(keyobj);
return 1;
} else {
return 0;
}
}
惰性删除
expireifneeded 该函数会在查找指定键时被调用，用于检查该键是否过期，过期的话执行删除(deleteexpiredkeyandpropagate)。
void deleteexpiredkeyandpropagate(redisdb *db, robj *keyobj) {
mstime_t expire_latency;
latencystartmonitor(expire_latency);
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);
propagatedeletion(db,keyobj,server.lazyfree_lazy_expire);
server.stat_expiredkeys++;
}
删除接口
下图对redis的删除接口进行了总结，方便进行理解和源码阅读。
从字典中删除key接口
1. 真正从字典中删除对应key(dictfreeunlinkedentry)
void dictfreeunlinkedentry(dict *d, dictentry *he) {
if (he == null) return;
dictfreekey(d, he);
dictfreeval(d, he);
zfree(he);
}
dictfreeunlinkedentry 函数会调用字典d的key,value销毁函数先销毁he的key,value，然后释放he。
2. 从字典中搜索并删除对应key(dictgenericdelete)
static dictentry *dictgenericdelete(dict *d, const void *key, int nofree) {
uint64_t h, idx;
dictentry *he, *prevhe;
int table;
/* dict is empty */
if (dictsize(d) == 0) return null;
if (dictisrehashing(d)) _dictrehashstep(d);
h = dicthashkey(d, key);
for (table = 0; table <= 1; table++) {
idx = h & dictht_size_mask(d->ht_size_exp[table]);
he = d->ht_table[table][idx];
prevhe = null;
while(he) {
if (key==he->key || dictcomparekeys(d, key, he->key)) {
/* unlink the element from the list */
if (prevhe)
prevhe->next = he->next;
else
d->ht_table[table][idx] = he->next;
if (!nofree) {
dictfreeunlinkedentry(d, he);
}
d->ht_used[table]--;
return he;
}
prevhe = he;
he = he->next;
}
if (!dictisrehashing(d)) break;
}
return null; /* not found */
}
- 检查字典是否正在进行rehash，由于redis采用的是渐进式rehash，对于处在rehash状态的字典这里会执行一步rehash操作
- 计算key的hash值
- 遍历字典。我们知道redis的字典中实际存在两个hashtable, 依次遍历这两个hashtable，查找对应的key是否存在
- 找到对应key后首先改变链表链接关系，若nofree为0则执行真实删除操作，从字典中删除key
- 最终返回找到的节点地址
3. 真实删除（dictdelete）
int dictdelete(dict *ht, const void *key) {
return dictgenericdelete(ht,key,0) ? dict_ok : dict_err;
}
从字典中删除key对应节点并释放对应内存。
4. unlink(dictunlink)
dictentry *dictunlink(dict *d, const void *key) {
return dictgenericdelete(d,key,1);
}
从字典中移除key对应的节点并返回，但并不释放节点内存。
从db中删除key接口
1. dbgenericdelete
static int dbgenericdelete(redisdb *db, robj *key, int async) {
/* deleting an entry from the expires dict will not free the sds of
* the key, because it is shared with the main dictionary. */
if (dictsize(db->expires) > 0) dictdelete(db->expires,key->ptr);
dictentry *de = dictunlink(db->dict,key->ptr);
if (de) {
robj *val = dictgetval(de);
/* tells the module that the key has been unlinked from the database. */
modulenotifykeyunlink(key,val,db->id);
/* we want to try to unblock any client using a blocking xreadgroup */
if (val->type == obj_stream)
signalkeyasready(db,key,val->type);
if (async) {
freeobjasync(key, val, db->id);
dictsetval(db->dict, de, null);
}
if (server.cluster_enabled) slottokeydelentry(de, db);
dictfreeunlinkedentry(db->dict,de);
return 1;
} else {
return 0;
}
}
- 首先从过期字典中删除对应key
- 从字典中unlink掉key对应节点
总结
redis对于设置了过期时间的键，会在db->expires中存储该键对应的过期时间戳。过期键删除策略是定期删除和惰性删除相结合的策略。惰性删除是指访问到该键时校验是否过期，过期执行删除。
对于周期删除，策略较复杂，为了保证定期删除可控，严格控制了每次定期删除时遍历db数量、采样键数量、执行时间等指标。定期删除提供了fast模式，该模式下会放宽执行时间和遍历的db数。
通过这两种方式，来处理redis的过期键，保证过期逻辑和内存可控。
以上就是redis过期键的删除策略分享的详细内容，更多关于redis过期键删除的资料请关注代码网其它相关文章！
发表评论