redis 數(shù)據(jù)刪除策略和逐出算法的問題小結

/*
 * 為執(zhí)行寫入操作而取出鍵 key 在數(shù)據(jù)庫 db 中的值。
 *
 * 和 lookupKeyRead 不同，這個函數(shù)不會更新服務器的命中/不命中信息。
 *
 * 找到時返回值對象，沒找到返回 NULL 。
 */
robj *lookupKeyWrite(redisDb *db, robj *key) {

 // 刪除過期鍵
 expireIfNeeded(db,key);

 // 查找并返回 key 的值對象
 return lookupKey(db,key);
}

/*
 * 為執(zhí)行讀取操作而取出鍵 key 在數(shù)據(jù)庫 db 中的值。
 *
 * 并根據(jù)是否成功找到值，更新服務器的命中/不命中信息。
 *
 * 找到時返回值對象，沒找到返回 NULL 。
 */
robj *lookupKeyRead(redisDb *db, robj *key) {
 robj *val;

 // 檢查 key 釋放已經(jīng)過期
 expireIfNeeded(db,key);

 // 從數(shù)據(jù)庫中取出鍵的值
 val = lookupKey(db,key);

 // 更新命中/不命中信息
 if (val == NULL)
 server.stat_keyspace_misses++;
 else
 server.stat_keyspace_hits++;

 // 返回值
 return val;
}

/*
 * 檢查 key 是否已經(jīng)過期，如果是的話，將它從數(shù)據(jù)庫中刪除。
 *
 * 返回 0 表示鍵沒有過期時間，或者鍵未過期。
 *
 * 返回 1 表示鍵已經(jīng)因為過期而被刪除了。
 */
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 模式時
 // 附屬節(jié)點并不主動刪除 key
 // 它只返回一個邏輯上正確的返回值
 // 真正的刪除操作要等待主節(jié)點發(fā)來刪除命令時才執(zhí)行
 // 從而保證數(shù)據(jù)的同步
 if (server.masterhost != NULL) return now > when;

 // 運行到這里，表示鍵帶有過期時間，并且服務器為主節(jié)點

 /* Return when this key has not expired */
 // 如果未過期，返回 0
 if (now = when) return 0;

 /* Delete the key */
 server.stat_expiredkeys++;

 // 向 AOF 文件和附屬節(jié)點傳播過期信息
 propagateExpire(db,key);

 // 發(fā)送事件通知
 notifyKeyspaceEvent(REDIS_NOTIFY_EXPIRED,
 "expired",key,db->id);

 // 將過期鍵從數(shù)據(jù)庫中刪除
 return dbDelete(db,key);
}

/*
 * 返回字典中包含鍵 key 的節(jié)點
 *
 * 找到返回節(jié)點，找不到返回 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;

 // 遍歷給定索引上的鏈表的所有節(jié)點，查找 key
 he = d->ht[table].table[idx];
 // T = O(1)
 while(he) {

 if (dictCompareKeys(d, key, he->key))
 return he;

 he = he->next;
 }

 // 如果程序遍歷完 0 號哈希表，仍然沒找到指定的鍵的節(jié)點
 // 那么程序會檢查字典是否在進行 rehash ，
 // 然后才決定是直接返回 NULL ，還是繼續(xù)查找 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. */
 // 檢查客戶端，關閉超時客戶端，并釋放客戶端多余的緩沖區(qū)
 clientsCron();

 /* Handle background operations on Redis databases. */
 // 對數(shù)據(jù)庫執(zhí)行各種操作
 databasesCron(); /* ！我們關注的方法！ */

// 對數(shù)據(jù)庫執(zhí)行刪除過期鍵，調整大小，以及主動和漸進式 rehash
void databasesCron(void) {

 // 判斷是否是主服務器 如果是 執(zhí)行主動過期鍵清除
 if (server.active_expire_enabled  server.masterhost == NULL)
 // 清除模式為 CYCLE_SLOW ，這個模式會盡量多清除過期鍵
 activeExpireCycle(ACTIVE_EXPIRE_CYCLE_SLOW);

 // 在沒有 BGSAVE 或者 BGREWRITEAOF 執(zhí)行時，對哈希表進行 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. */
 // 設定要測試的數(shù)據(jù)庫數(shù)量
 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) {
 // 靜態(tài)變量，用來累積函數(shù)連續(xù)執(zhí)行時的數(shù)據(jù)
 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;
 // 默認每次處理的數(shù)據(jù)庫數(shù)量
 unsigned int dbs_per_call = REDIS_DBCRON_DBS_PER_CALL;
 // 函數(shù)開始的時間
 long long start = ustime(), timelimit;

 // 快速模式
 if (type == ACTIVE_EXPIRE_CYCLE_FAST) {
 // 如果上次函數(shù)沒有觸發(fā) timelimit_exit ，那么不執(zhí)行處理
 if (!timelimit_exit) return;
 // 如果距離上次執(zhí)行未夠一定時間，那么不執(zhí)行處理
 if (start  last_fast_cycle + ACTIVE_EXPIRE_CYCLE_FAST_DURATION*2) return;
 // 運行到這里，說明執(zhí)行快速處理，記錄當前時間
 last_fast_cycle = start;
 }

 /* 
 * 一般情況下，函數(shù)只處理 REDIS_DBCRON_DBS_PER_CALL 個數(shù)據(jù)庫，
 * 除非：
 *
 * 1) 當前數(shù)據(jù)庫的數(shù)量小于 REDIS_DBCRON_DBS_PER_CALL
 * 2) 如果上次處理遇到了時間上限，那么這次需要對所有數(shù)據(jù)庫進行掃描，
 * 這可以避免過多的過期鍵占用空間
 */
 if (dbs_per_call > server.dbnum || timelimit_exit)
 dbs_per_call = server.dbnum;

 // 函數(shù)處理的微秒時間上限
 // 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. */

 // 遍歷數(shù)據(jù)庫
 for (j = 0; j  dbs_per_call; j++) {
 int expired;
 // 指向要處理的數(shù)據(jù)庫
 redisDb *db = server.db+(current_db % server.dbnum);

 // 為 DB 計數(shù)器加一，如果進入 do 循環(huán)之后因為超時而跳出
 // 那么下次會直接從下個 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. */
 // 獲取數(shù)據(jù)庫中帶過期時間的鍵的數(shù)量
 // 如果該數(shù)量為 0 ，直接跳過這個數(shù)據(jù)庫
 if ((num = dictSize(db->expires)) == 0) {
 db->avg_ttl = 0;
 break;
 }
 // 獲取數(shù)據(jù)庫中鍵值對的數(shù)量
 slots = dictSlots(db->expires);
 // 當前時間
 now = mstime();

 // 這個數(shù)據(jù)庫的使用率低于 1% ，掃描起來太費力了（大部分都會 MISS）
 // 跳過，等待字典收縮程序運行
 if (num  slots > DICT_HT_INITIAL_SIZE 
 (num*100/slots  1)) break;

 /* 
 * 樣本計數(shù)器
 */
 // 已處理過期鍵計數(shù)器
 expired = 0;
 // 鍵的總 TTL 計數(shù)器
 ttl_sum = 0;
 // 總共處理的鍵計數(shù)器
 ttl_samples = 0;

 // 每次最多只能檢查 LOOKUPS_PER_LOOP 個鍵
 if (num > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP)
 num = ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP;

 // 開始遍歷數(shù)據(jù)庫
 while (num--) {
 dictEntry *de;
 long long ttl;

 // 從 expires 中隨機取出一個帶過期時間的鍵
 if ((de = dictGetRandomKey(db->expires)) == NULL) break;
 // 計算 TTL
 ttl = dictGetSignedIntegerVal(de)-now;
 // 如果鍵已經(jīng)過期，那么刪除它，并將 expired 計數(shù)器增一
 if (activeExpireCycleTryExpire(db,de,now)) expired++;
 if (ttl  0) ttl = 0;
 // 累積鍵的 TTL
 ttl_sum += ttl;
 // 累積處理鍵的個數(shù)
 ttl_samples++;
 }

 /* Update the average TTL stats for this database. */
 // 為這個數(shù)據(jù)庫更新平均 TTL 統(tǒng)計數(shù)據(jù)
 if (ttl_samples) {
 // 計算當前平均值
 long long avg_ttl = ttl_sum/ttl_samples;
 
 // 如果這是第一次設置數(shù)據(jù)庫平均 TTL ，那么進行初始化
 if (db->avg_ttl == 0) db->avg_ttl = avg_ttl;
 /* Smooth the value averaging with the previous one. */
 // 取數(shù)據(jù)庫的上次平均 TTL 和今次平均 TTL 的平均值
 db->avg_ttl = (db->avg_ttl+avg_ttl)/2;
 }

 // 我們不能用太長時間處理過期鍵，
 // 所以這個函數(shù)執(zhí)行一定時間之后就要返回

 // 更新遍歷次數(shù)
 iteration++;

 // 每遍歷 16 次執(zhí)行一次
 if ((iteration  0xf) == 0  /* check once every 16 iterations. */
 (ustime()-start) > timelimit)
 {
 // 如果遍歷次數(shù)正好是 16 的倍數(shù)
 // 并且遍歷的時間超過了 timelimit
 // 那么斷開 timelimit_exit
 timelimit_exit = 1;
 }

 // 已經(jīng)超時了，返回
 if (timelimit_exit) return;

 // 如果已刪除的過期鍵占當前總數(shù)據(jù)庫帶過期時間的鍵數(shù)量的 25 %
 // 那么不再遍歷
 } while (expired > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP/4);
 }
}

if (server.active_expire_enabled  server.masterhost == NULL) // 判斷是否是主節(jié)點 從節(jié)點不需要執(zhí)行activeExpireCycle()函數(shù)。
 // 清除模式為 CYCLE_SLOW ，這個模式會盡量多清除過期鍵
 activeExpireCycle(ACTIVE_EXPIRE_CYCLE_SLOW);