redis实现数据删除策略和逐出算法

/*
 * 为执行写入操作而取出键 key 在数据库 db 中的值。
 *
 * 和 lookupKeyRead 不同，这个函数不会更新服务器的命中/不命中信息。
 *
 * 找到时返回值对象，没找到返回 NULL 。
 */
robj *lookupKeyWrite(redisDb *db, robj *key) {

 // 删除过期键
 expireIfNeeded(db,key);

 // 查找并返回 key 的值对象
 return lookupKey(db,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;
}

/*
 * 检查 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 的节点
 *
 * 找到返回节点，找不到返回 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;
}

way1 : config get hz # "hz" "10"
way2 : info server # server.hz 10

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(); /* ！我们关注的方法！ */

// 对数据库执行删除过期键，调整大小，以及主动和渐进式 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;
 }
 }
 }
 }
}

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

if (server.active_expire_enabled && server.masterhost == NULL) // 判断是否是主节点 从节点不需要执行activeExpireCycle()函数。
 // 清除模式为 CYCLE_SLOW ，这个模式会尽量多清除过期键
 activeExpireCycle(ACTIVE_EXPIRE_CYCLE_SLOW);