过期数据删除策略
redis的过期数据删除策略使用了惰性删除和定期删除两种策略：
- 惰性删除发生在redis处理读写请求的过程，如get/set等命令。
- 定期删除发生在redis内部定时任务执行过程中，限制占用cpu的时间。
定期删除
redis的定期删除是通过定时任务实现的，也就是定时任务会循环调用serverCron方法。然后定时检查过期数据的方法是databasesCron。
定期删除的一大特点就是考虑了定时删除过期数据会占用cpu时间，所以每次执行databasesCron的时候会限制cpu的占用不超过25%。
int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientData) {
// 省略了很多无关代码
/* We need to do a few operations on clients asynchronously. */
// 检查客户端，关闭超时客户端，并释放客户端多余的缓冲区
clientsCron();
/* Handle background operations on Redis databases. */
// 对数据库执行各种操作
databasesCron();
activeExpireCycle执行过期数据的删除，其他的动作不在该部分讨论当中。
// 对数据库执行删除过期键，调整大小，以及主动和渐进式 rehash
void databasesCron(void) {
// 如果服务器不是从服务器，那么执行主动过期键清除
if (server.active_expire_enabled && server.masterhost == NULL)
// 清除模式为 CYCLE_SLOW ，这个模式会尽量多清除过期键
activeExpireCycle(ACTIVE_EXPIRE_CYCLE_SLOW);
// 在没有 BGSAVE 或者 BGREWRITEAOF 执行时，对哈希表进行 rehash
if (server.rdb_child_pid == -1 && server.aof_child_pid == -1) {
static unsigned int resize_db = 0;
static unsigned int rehash_db = 0;
unsigned int dbs_per_call = REDIS_DBCRON_DBS_PER_CALL;
unsigned int j;
/* Don't test more DBs than we have. */
// 设定要测试的数据库数量
if (dbs_per_call > server.dbnum) dbs_per_call = server.dbnum;
/* Resize */
// 调整字典的大小
for (j = 0; j < dbs_per_call; j++) {
tryResizeHashTables(resize_db % server.dbnum);
resize_db++;
}
/* Rehash */
// 对字典进行渐进式 rehash
if (server.activerehashing) {
for (j = 0; j < dbs_per_call; j++) {
int work_done = incrementallyRehash(rehash_db % server.dbnum);
rehash_db++;
if (work_done) {
/* If the function did some work, stop here, we'll do
* more at the next cron loop. */
break;
}
}
}
}
}
删除过期数据的整个过程主要按照下面的逻辑进行：
- 遍历指定个数的db（如16）进行删除操作
- 针对每个db随机获取过期数据每次遍历不超过指定数量（如20），发现过期数据并进行删除。
- 每个db的次数累积到16次的时候会进行判断时间是否超过25%，超过就停止删除数据过程。
- 最后如果删除的过期数据耗时（通过开始结束时间统计）超过待过期时间数量的25%的时候就停止删除过期数据过程。
- timelimit = 1000000*ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC/server.hz/100的解释是：server.hz代表每秒调用的次数,所以上面这个公司就是每次执行占用的时候的25%用于过期数据删除。
void activeExpireCycle(int type) {
// 静态变量，用来累积函数连续执行时的数据
static unsigned int current_db = 0; /* Last DB tested. */
static int timelimit_exit = 0; /* Time limit hit in previous call? */
static long long last_fast_cycle = 0; /* When last fast cycle ran. */
unsigned int j, iteration = 0;
// 默认每次处理的数据库数量
unsigned int dbs_per_call = REDIS_DBCRON_DBS_PER_CALL;
// 函数开始的时间
long long start = ustime(), timelimit;
// 快速模式
if (type == ACTIVE_EXPIRE_CYCLE_FAST) {
// 如果上次函数没有触发 timelimit_exit ，那么不执行处理
if (!timelimit_exit) return;
// 如果距离上次执行未够一定时间，那么不执行处理
if (start < last_fast_cycle + ACTIVE_EXPIRE_CYCLE_FAST_DURATION*2) return;
// 运行到这里，说明执行快速处理，记录当前时间
last_fast_cycle = start;
}
/*
* 一般情况下，函数只处理 REDIS_DBCRON_DBS_PER_CALL 个数据库，
* 除非：
*
* 1) 当前数据库的数量小于 REDIS_DBCRON_DBS_PER_CALL
* 2) 如果上次处理遇到了时间上限，那么这次需要对所有数据库进行扫描，
* 这可以避免过多的过期键占用空间
*/
if (dbs_per_call > server.dbnum || timelimit_exit)
dbs_per_call = server.dbnum;
// 函数处理的微秒时间上限
// ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC 默认为 25 ，也即是 25 % 的 CPU 时间
timelimit = 1000000*ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC/server.hz/100;
timelimit_exit = 0;
if (timelimit <= 0) timelimit = 1;
// 如果是运行在快速模式之下
// 那么最多只能运行 FAST_DURATION 微秒
// 默认值为 1000 （微秒）
if (type == ACTIVE_EXPIRE_CYCLE_FAST)
timelimit = ACTIVE_EXPIRE_CYCLE_FAST_DURATION; /* in microseconds. */
// 遍历数据库
for (j = 0; j < dbs_per_call; j++) {
int expired;
// 指向要处理的数据库
redisDb *db = server.db+(current_db % server.dbnum);
// 为 DB 计数器加一，如果进入 do 循环之后因为超时而跳出
// 那么下次会直接从下个 DB 开始处理
current_db++;
do {
unsigned long num, slots;
long long now, ttl_sum;
int ttl_samples;
/* If there is nothing to expire try next DB ASAP. */
// 获取数据库中带过期时间的键的数量
// 如果该数量为 0 ，直接跳过这个数据库
if ((num = dictSize(db->expires)) == 0) {
db->avg_ttl = 0;
break;
}
// 获取数据库中键值对的数量
slots = dictSlots(db->expires);
// 当前时间
now = mstime();
// 这个数据库的使用率低于 1% ，扫描起来太费力了（大部分都会 MISS）
// 跳过，等待字典收缩程序运行
if (num && slots > DICT_HT_INITIAL_SIZE &&
(num*100/slots < 1)) break;
/*
* 样本计数器
*/
// 已处理过期键计数器
expired = 0;
// 键的总 TTL 计数器
ttl_sum = 0;
// 总共处理的键计数器
ttl_samples = 0;
// 每次最多只能检查 LOOKUPS_PER_LOOP 个键
if (num > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP)
num = ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP;
// 开始遍历数据库
while (num--) {
dictEntry *de;
long long ttl;
// 从 expires 中随机取出一个带过期时间的键
if ((de = dictGetRandomKey(db->expires)) == NULL) break;
// 计算 TTL
ttl = dictGetSignedIntegerVal(de)-now;
// 如果键已经过期，那么删除它，并将 expired 计数器增一
if (activeExpireCycleTryExpire(db,de,now)) expired++;
if (ttl < 0) ttl = 0;
// 累积键的 TTL
ttl_sum += ttl;
// 累积处理键的个数
ttl_samples++;
}
/* Update the average TTL stats for this database. */
// 为这个数据库更新平均 TTL 统计数据
if (ttl_samples) {
// 计算当前平均值
long long avg_ttl = ttl_sum/ttl_samples;
// 如果这是第一次设置数据库平均 TTL ，那么进行初始化
if (db->avg_ttl == 0) db->avg_ttl = avg_ttl;
/* Smooth the value averaging with the previous one. */
// 取数据库的上次平均 TTL 和今次平均 TTL 的平均值
db->avg_ttl = (db->avg_ttl+avg_ttl)/2;
}
// 我们不能用太长时间处理过期键，
// 所以这个函数执行一定时间之后就要返回
// 更新遍历次数
iteration++;
// 每遍历 16 次执行一次
if ((iteration & 0xf) == 0 && /* check once every 16 iterations. */
(ustime()-start) > timelimit)
{
// 如果遍历次数正好是 16 的倍数
// 并且遍历的时间超过了 timelimit
// 那么断开 timelimit_exit
timelimit_exit = 1;
}
// 已经超时了，返回
if (timelimit_exit) return;
// 如果已删除的过期键占当前总数据库带过期时间的键数量的 25 %
// 那么不再遍历
} while (expired > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP/4);
}
}
惰性过期
执行数据写入过程中，首先通过expireIfNeeded函数对写入的key进行过期判断。
/*
* 为执行写入操作而取出键 key 在数据库 db 中的值。
*
* 和 lookupKeyRead 不同，这个函数不会更新服务器的命中/不命中信息。
*
* 找到时返回值对象，没找到返回 NULL 。
*/
robj *lookupKeyWrite(redisDb *db, robj *key) {
// 删除过期键
expireIfNeeded(db,key);
// 查找并返回 key 的值对象
return lookupKey(db,key);
}
执行数据读取过程中，首先通过expireIfNeeded函数对写入的key进行过期判断。
/*
* 为执行读取操作而取出键 key 在数据库 db 中的值。
*
* 并根据是否成功找到值，更新服务器的命中/不命中信息。
*
* 找到时返回值对象，没找到返回 NULL 。
*/
robj *lookupKeyRead(redisDb *db, robj *key) {
robj *val;
// 检查 key 释放已经过期
expireIfNeeded(db,key);
// 从数据库中取出键的值
val = lookupKey(db,key);
// 更新命中/不命中信息
if (val == NULL)
server.stat_keyspace_misses++;
else
server.stat_keyspace_hits++;
// 返回值
return val;
}
执行过期动作expireIfNeeded其实内部做了三件事情，分别是：
- 查看key判断是否过期
- 向slave节点传播执行过期key的动作并发送事件通知
- 删除过期key
/*
* 检查 key 是否已经过期，如果是的话，将它从数据库中删除。
*
* 返回 0 表示键没有过期时间，或者键未过期。
*
* 返回 1 表示键已经因为过期而被删除了。
*/
int expireIfNeeded(redisDb *db, robj *key) {
// 取出键的过期时间
mstime_t when = getExpire(db,key);
mstime_t now;
// 没有过期时间
if (when < 0) return 0; /* No expire for this key */
/* Don't expire anything while loading. It will be done later. */
// 如果服务器正在进行载入，那么不进行任何过期检查
if (server.loading) return 0;
// 当服务器运行在 replication 模式时
// 附属节点并不主动删除 key
// 它只返回一个逻辑上正确的返回值
// 真正的删除操作要等待主节点发来删除命令时才执行
// 从而保证数据的同步
if (server.masterhost != NULL) return now > when;
// 运行到这里，表示键带有过期时间，并且服务器为主节点
/* Return when this key has not expired */
// 如果未过期，返回 0
if (now <= when) return 0;
/* Delete the key */
server.stat_expiredkeys++;
// 向 AOF 文件和附属节点传播过期信息
propagateExpire(db,key);
// 发送事件通知
notifyKeyspaceEvent(REDIS_NOTIFY_EXPIRED,
"expired",key,db->id);
// 将过期键从数据库中删除
return dbDelete(db,key);
}
判断key是否过期的数据结构是db->expires，也就是通过expires的数据结构判断数据是否过期。
内部获取过期时间并返回。
/* Return the expire time of the specified key, or -1 if no expire
* is associated with this key (i.e. the key is non volatile)
*
* 返回给定 key 的过期时间。
*
* 如果键没有设置过期时间，那么返回 -1 。
*/
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). */
redisAssertWithInfo(NULL,key,dictFind(db->dict,key->ptr) != NULL);
// 返回过期时间,#define dictGetSignedIntegerVal(he) ((he)->v.s64)
return dictGetSignedIntegerVal(de);
}
整个数据查找过程类比hashtab的查找过程，首先定位hash桶，然后遍历hash桶下挂的链查找对应的节点。
/*
* 返回字典中包含键 key 的节点
*
* 找到返回节点，找不到返回 NULL
*
* T = O(1)
*/
dictEntry *dictFind(dict *d, const void *key)
{
dictEntry *he;
unsigned int h, idx, table;
// 字典（的哈希表）为空
if (d->ht[0].size == 0) return NULL; /* We don't have a table at all */
// 如果条件允许的话，进行单步 rehash
if (dictIsRehashing(d)) _dictRehashStep(d);
// 计算键的哈希值
h = dictHashKey(d, key);
// 在字典的哈希表中查找这个键
// T = O(1)
for (table = 0; table <= 1; table++) {
// 计算索引值
idx = h & d->ht[table].sizemask;
// 遍历给定索引上的链表的所有节点，查找 key
he = d->ht[table].table[idx];
// T = O(1)
while(he) {
if (dictCompareKeys(d, key, he->key))
return he;
he = he->next;
}
// 如果程序遍历完 0 号哈希表，仍然没找到指定的键的节点
// 那么程序会检查字典是否在进行 rehash ，
// 然后才决定是直接返回 NULL ，还是继续查找 1 号哈希表
if (!dictIsRehashing(d)) return NULL;
}
// 进行到这里时，说明两个哈希表都没找到
return NULL;
}
