系列
redis數(shù)據(jù)淘汰原理
redis過(guò)期數(shù)據(jù)刪除策略
redis server事件模型
redis cluster mget 引發(fā)的討論
redis 3.x windows 集群搭建
redis 命令執(zhí)行過(guò)程
redis string底層數(shù)據(jù)結(jié)構(gòu)
redis list底層數(shù)據(jù)結(jié)構(gòu)
redis hash底層數(shù)據(jù)結(jié)構(gòu)
redis set底層數(shù)據(jù)結(jié)構(gòu)
redis zset底層數(shù)據(jù)結(jié)構(gòu)
redis 客戶端管理
redis 主從同步-slave端
redis 主從同步-master端
redis 主從超時(shí)檢測(cè)
redis aof持久化
redis rdb持久化
redis 數(shù)據(jù)恢復(fù)過(guò)程
redis TTL實(shí)現(xiàn)原理
redis cluster集群建立
redis cluster集群選主
過(guò)期數(shù)據(jù)刪除策略
?redis的過(guò)期數(shù)據(jù)刪除策略使用了惰性刪除和定期刪除兩種策略：
- 惰性刪除發(fā)生在redis處理讀寫(xiě)請(qǐng)求的過(guò)程，如get/set等命令驾凶。
- 定期刪除發(fā)生在redis內(nèi)部定時(shí)任務(wù)執(zhí)行過(guò)程中宏榕，限制占用cpu的時(shí)間玖瘸。
定期刪除
?redis的定期刪除是通過(guò)定時(shí)任務(wù)實(shí)現(xiàn)的两波，也就是定時(shí)任務(wù)會(huì)循環(huán)調(diào)用serverCron方法埃唯。然后定時(shí)檢查過(guò)期數(shù)據(jù)的方法是databasesCron免糕。
?定期刪除的一大特點(diǎn)就是考慮了定時(shí)刪除過(guò)期數(shù)據(jù)會(huì)占用cpu時(shí)間善镰，所以每次執(zhí)行databasesCron的時(shí)候會(huì)限制cpu的占用不超過(guò)25%是目。
int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientData) {
// 省略了很多無(wú)關(guān)代碼
/* We need to do a few operations on clients asynchronously. */
// 檢查客戶端谤饭，關(guān)閉超時(shí)客戶端，并釋放客戶端多余的緩沖區(qū)
clientsCron();
/* Handle background operations on Redis databases. */
// 對(duì)數(shù)據(jù)庫(kù)執(zhí)行各種操作
databasesCron();
?activeExpireCycle執(zhí)行過(guò)期數(shù)據(jù)的刪除懊纳，其他的動(dòng)作不在該部分討論當(dāng)中揉抵。
// 對(duì)數(shù)據(jù)庫(kù)執(zhí)行刪除過(guò)期鍵，調(diào)整大小嗤疯，以及主動(dòng)和漸進(jìn)式 rehash
void databasesCron(void) {
// 如果服務(wù)器不是從服務(wù)器冤今，那么執(zhí)行主動(dòng)過(guò)期鍵清除
if (server.active_expire_enabled && server.masterhost == NULL)
// 清除模式為 CYCLE_SLOW ，這個(gè)模式會(huì)盡量多清除過(guò)期鍵
activeExpireCycle(ACTIVE_EXPIRE_CYCLE_SLOW);
// 在沒(méi)有 BGSAVE 或者 BGREWRITEAOF 執(zhí)行時(shí)茂缚，對(duì)哈希表進(jìn)行 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è)定要測(cè)試的數(shù)據(jù)庫(kù)數(shù)量
if (dbs_per_call > server.dbnum) dbs_per_call = server.dbnum;
/* Resize */
// 調(diào)整字典的大小
for (j = 0; j < dbs_per_call; j++) {
tryResizeHashTables(resize_db % server.dbnum);
resize_db++;
}
/* Rehash */
// 對(duì)字典進(jìn)行漸進(jìn)式 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;
}
}
}
}
}
?刪除過(guò)期數(shù)據(jù)的整個(gè)過(guò)程主要按照下面的邏輯進(jìn)行：
- 遍歷指定個(gè)數(shù)的db（如16）進(jìn)行刪除操作
- 針對(duì)每個(gè)db隨機(jī)獲取過(guò)期數(shù)據(jù)每次遍歷不超過(guò)指定數(shù)量（如20）戏罢，發(fā)現(xiàn)過(guò)期數(shù)據(jù)并進(jìn)行刪除。
- 每個(gè)db的次數(shù)累積到16次的時(shí)候會(huì)進(jìn)行判斷時(shí)間是否超過(guò)25%脚囊，超過(guò)就停止刪除數(shù)據(jù)過(guò)程龟糕。
- 最后如果刪除的過(guò)期數(shù)據(jù)耗時(shí)（通過(guò)開(kāi)始結(jié)束時(shí)間統(tǒng)計(jì)）超過(guò)待過(guò)期時(shí)間數(shù)量的25%的時(shí)候就停止刪除過(guò)期數(shù)據(jù)過(guò)程。
- timelimit = 1000000*ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC/server.hz/100的解釋是：server.hz代表每秒調(diào)用的次數(shù),所以上面這個(gè)公司就是每次執(zhí)行占用的時(shí)候的25%用于過(guò)期數(shù)據(jù)刪除悔耘。
void activeExpireCycle(int type) {
// 靜態(tài)變量讲岁，用來(lái)累積函數(shù)連續(xù)執(zhí)行時(shí)的數(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;
// 默認(rèn)每次處理的數(shù)據(jù)庫(kù)數(shù)量
unsigned int dbs_per_call = REDIS_DBCRON_DBS_PER_CALL;
// 函數(shù)開(kāi)始的時(shí)間
long long start = ustime(), timelimit;
// 快速模式
if (type == ACTIVE_EXPIRE_CYCLE_FAST) {
// 如果上次函數(shù)沒(méi)有觸發(fā) timelimit_exit ，那么不執(zhí)行處理
if (!timelimit_exit) return;
// 如果距離上次執(zhí)行未夠一定時(shí)間衬以，那么不執(zhí)行處理
if (start < last_fast_cycle + ACTIVE_EXPIRE_CYCLE_FAST_DURATION*2) return;
// 運(yùn)行到這里缓艳，說(shuō)明執(zhí)行快速處理，記錄當(dāng)前時(shí)間
last_fast_cycle = start;
}
/*
* 一般情況下看峻，函數(shù)只處理 REDIS_DBCRON_DBS_PER_CALL 個(gè)數(shù)據(jù)庫(kù)郎任，
* 除非：
*
* 1) 當(dāng)前數(shù)據(jù)庫(kù)的數(shù)量小于 REDIS_DBCRON_DBS_PER_CALL
* 2) 如果上次處理遇到了時(shí)間上限，那么這次需要對(duì)所有數(shù)據(jù)庫(kù)進(jìn)行掃描备籽，
* 這可以避免過(guò)多的過(guò)期鍵占用空間
*/
if (dbs_per_call > server.dbnum || timelimit_exit)
dbs_per_call = server.dbnum;
// 函數(shù)處理的微秒時(shí)間上限
// ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC 默認(rèn)為 25 舶治，也即是 25 % 的 CPU 時(shí)間
timelimit = 1000000*ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC/server.hz/100;
timelimit_exit = 0;
if (timelimit <= 0) timelimit = 1;
// 如果是運(yùn)行在快速模式之下
// 那么最多只能運(yùn)行 FAST_DURATION 微秒
// 默認(rèn)值為 1000 （微秒）
if (type == ACTIVE_EXPIRE_CYCLE_FAST)
timelimit = ACTIVE_EXPIRE_CYCLE_FAST_DURATION; /* in microseconds. */
// 遍歷數(shù)據(jù)庫(kù)
for (j = 0; j < dbs_per_call; j++) {
int expired;
// 指向要處理的數(shù)據(jù)庫(kù)
redisDb *db = server.db+(current_db % server.dbnum);
// 為 DB 計(jì)數(shù)器加一分井，如果進(jìn)入 do 循環(huán)之后因?yàn)槌瑫r(shí)而跳出
// 那么下次會(huì)直接從下個(gè) DB 開(kāi)始處理
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ù)庫(kù)中帶過(guò)期時(shí)間的鍵的數(shù)量
// 如果該數(shù)量為 0 ，直接跳過(guò)這個(gè)數(shù)據(jù)庫(kù)
if ((num = dictSize(db->expires)) == 0) {
db->avg_ttl = 0;
break;
}
// 獲取數(shù)據(jù)庫(kù)中鍵值對(duì)的數(shù)量
slots = dictSlots(db->expires);
// 當(dāng)前時(shí)間
now = mstime();
// 這個(gè)數(shù)據(jù)庫(kù)的使用率低于 1% 霉猛，掃描起來(lái)太費(fèi)力了（大部分都會(huì) MISS）
// 跳過(guò)尺锚，等待字典收縮程序運(yùn)行
if (num && slots > DICT_HT_INITIAL_SIZE &&
(num*100/slots < 1)) break;
/*
* 樣本計(jì)數(shù)器
*/
// 已處理過(guò)期鍵計(jì)數(shù)器
expired = 0;
// 鍵的總 TTL 計(jì)數(shù)器
ttl_sum = 0;
// 總共處理的鍵計(jì)數(shù)器
ttl_samples = 0;
// 每次最多只能檢查 LOOKUPS_PER_LOOP 個(gè)鍵
if (num > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP)
num = ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP;
// 開(kāi)始遍歷數(shù)據(jù)庫(kù)
while (num--) {
dictEntry *de;
long long ttl;
// 從 expires 中隨機(jī)取出一個(gè)帶過(guò)期時(shí)間的鍵
if ((de = dictGetRandomKey(db->expires)) == NULL) break;
// 計(jì)算 TTL
ttl = dictGetSignedIntegerVal(de)-now;
// 如果鍵已經(jīng)過(guò)期，那么刪除它惜浅，并將 expired 計(jì)數(shù)器增一
if (activeExpireCycleTryExpire(db,de,now)) expired++;
if (ttl < 0) ttl = 0;
// 累積鍵的 TTL
ttl_sum += ttl;
// 累積處理鍵的個(gè)數(shù)
ttl_samples++;
}
/* Update the average TTL stats for this database. */
// 為這個(gè)數(shù)據(jù)庫(kù)更新平均 TTL 統(tǒng)計(jì)數(shù)據(jù)
if (ttl_samples) {
// 計(jì)算當(dāng)前平均值
long long avg_ttl = ttl_sum/ttl_samples;
// 如果這是第一次設(shè)置數(shù)據(jù)庫(kù)平均 TTL 瘫辩，那么進(jìn)行初始化
if (db->avg_ttl == 0) db->avg_ttl = avg_ttl;
/* Smooth the value averaging with the previous one. */
// 取數(shù)據(jù)庫(kù)的上次平均 TTL 和今次平均 TTL 的平均值
db->avg_ttl = (db->avg_ttl+avg_ttl)/2;
}
// 我們不能用太長(zhǎng)時(shí)間處理過(guò)期鍵，
// 所以這個(gè)函數(shù)執(zhí)行一定時(shí)間之后就要返回
// 更新遍歷次數(shù)
iteration++;
// 每遍歷 16 次執(zhí)行一次
if ((iteration & 0xf) == 0 && /* check once every 16 iterations. */
(ustime()-start) > timelimit)
{
// 如果遍歷次數(shù)正好是 16 的倍數(shù)
// 并且遍歷的時(shí)間超過(guò)了 timelimit
// 那么斷開(kāi) timelimit_exit
timelimit_exit = 1;
}
// 已經(jīng)超時(shí)了坛悉，返回
if (timelimit_exit) return;
// 如果已刪除的過(guò)期鍵占當(dāng)前總數(shù)據(jù)庫(kù)帶過(guò)期時(shí)間的鍵數(shù)量的 25 %
// 那么不再遍歷
} while (expired > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP/4);
}
}
惰性過(guò)期
?執(zhí)行數(shù)據(jù)寫(xiě)入過(guò)程中伐厌，首先通過(guò)expireIfNeeded函數(shù)對(duì)寫(xiě)入的key進(jìn)行過(guò)期判斷。
/*
* 為執(zhí)行寫(xiě)入操作而取出鍵 key 在數(shù)據(jù)庫(kù) db 中的值裸影。
*
* 和 lookupKeyRead 不同挣轨，這個(gè)函數(shù)不會(huì)更新服務(wù)器的命中/不命中信息。
*
* 找到時(shí)返回值對(duì)象轩猩，沒(méi)找到返回 NULL 卷扮。
*/
robj *lookupKeyWrite(redisDb *db, robj *key) {
// 刪除過(guò)期鍵
expireIfNeeded(db,key);
// 查找并返回 key 的值對(duì)象
return lookupKey(db,key);
}
?執(zhí)行數(shù)據(jù)讀取過(guò)程中，首先通過(guò)expireIfNeeded函數(shù)對(duì)寫(xiě)入的key進(jìn)行過(guò)期判斷均践。
/*
* 為執(zhí)行讀取操作而取出鍵 key 在數(shù)據(jù)庫(kù) db 中的值晤锹。
*
* 并根據(jù)是否成功找到值，更新服務(wù)器的命中/不命中信息彤委。
*
* 找到時(shí)返回值對(duì)象鞭铆，沒(méi)找到返回 NULL 。
*/
robj *lookupKeyRead(redisDb *db, robj *key) {
robj *val;
// 檢查 key 釋放已經(jīng)過(guò)期
expireIfNeeded(db,key);
// 從數(shù)據(jù)庫(kù)中取出鍵的值
val = lookupKey(db,key);
// 更新命中/不命中信息
if (val == NULL)
server.stat_keyspace_misses++;
else
server.stat_keyspace_hits++;
// 返回值
return val;
}
?執(zhí)行過(guò)期動(dòng)作expireIfNeeded其實(shí)內(nèi)部做了三件事情焦影，分別是：
- 查看key判斷是否過(guò)期
- 向slave節(jié)點(diǎn)傳播執(zhí)行過(guò)期key的動(dòng)作并發(fā)送事件通知
- 刪除過(guò)期key
/*
* 檢查 key 是否已經(jīng)過(guò)期衔彻，如果是的話，將它從數(shù)據(jù)庫(kù)中刪除偷办。
*
* 返回 0 表示鍵沒(méi)有過(guò)期時(shí)間，或者鍵未過(guò)期澄港。
*
* 返回 1 表示鍵已經(jīng)因?yàn)檫^(guò)期而被刪除了椒涯。
*/
int expireIfNeeded(redisDb *db, robj *key) {
// 取出鍵的過(guò)期時(shí)間
mstime_t when = getExpire(db,key);
mstime_t now;
// 沒(méi)有過(guò)期時(shí)間
if (when < 0) return 0; /* No expire for this key */
/* Don't expire anything while loading. It will be done later. */
// 如果服務(wù)器正在進(jìn)行載入，那么不進(jìn)行任何過(guò)期檢查
if (server.loading) return 0;
// 當(dāng)服務(wù)器運(yùn)行在 replication 模式時(shí)
// 附屬節(jié)點(diǎn)并不主動(dòng)刪除 key
// 它只返回一個(gè)邏輯上正確的返回值
// 真正的刪除操作要等待主節(jié)點(diǎn)發(fā)來(lái)刪除命令時(shí)才執(zhí)行
// 從而保證數(shù)據(jù)的同步
if (server.masterhost != NULL) return now > when;
// 運(yùn)行到這里回梧，表示鍵帶有過(guò)期時(shí)間废岂，并且服務(wù)器為主節(jié)點(diǎn)
/* Return when this key has not expired */
// 如果未過(guò)期，返回 0
if (now <= when) return 0;
/* Delete the key */
server.stat_expiredkeys++;
// 向 AOF 文件和附屬節(jié)點(diǎn)傳播過(guò)期信息
propagateExpire(db,key);
// 發(fā)送事件通知
notifyKeyspaceEvent(REDIS_NOTIFY_EXPIRED,
"expired",key,db->id);
// 將過(guò)期鍵從數(shù)據(jù)庫(kù)中刪除
return dbDelete(db,key);
}
?判斷key是否過(guò)期的數(shù)據(jù)結(jié)構(gòu)是db->expires狱意，也就是通過(guò)expires的數(shù)據(jù)結(jié)構(gòu)判斷數(shù)據(jù)是否過(guò)期湖苞。
內(nèi)部獲取過(guò)期時(shí)間并返回。
/* 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 的過(guò)期時(shí)間详囤。
*
* 如果鍵沒(méi)有設(shè)置過(guò)期時(shí)間财骨，那么返回 -1 镐作。
*/
long long getExpire(redisDb *db, robj *key) {
dictEntry *de;
/* No expire? return ASAP */
// 獲取鍵的過(guò)期時(shí)間
// 如果過(guò)期時(shí)間不存在，那么直接返回
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);
// 返回過(guò)期時(shí)間,#define dictGetSignedIntegerVal(he) ((he)->v.s64)
return dictGetSignedIntegerVal(de);
}
?整個(gè)數(shù)據(jù)查找過(guò)程類比hashtab的查找過(guò)程隆箩，首先定位hash桶该贾，然后遍歷hash桶下掛的鏈查找對(duì)應(yīng)的節(jié)點(diǎn)。
/*
* 返回字典中包含鍵 key 的節(jié)點(diǎn)
*
* 找到返回節(jié)點(diǎn)捌臊，找不到返回 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 */
// 如果條件允許的話杨蛋，進(jìn)行單步 rehash
if (dictIsRehashing(d)) _dictRehashStep(d);
// 計(jì)算鍵的哈希值
h = dictHashKey(d, key);
// 在字典的哈希表中查找這個(gè)鍵
// T = O(1)
for (table = 0; table <= 1; table++) {
// 計(jì)算索引值
idx = h & d->ht[table].sizemask;
// 遍歷給定索引上的鏈表的所有節(jié)點(diǎn)，查找 key
he = d->ht[table].table[idx];
// T = O(1)
while(he) {
if (dictCompareKeys(d, key, he->key))
return he;
he = he->next;
}
// 如果程序遍歷完 0 號(hào)哈希表理澎，仍然沒(méi)找到指定的鍵的節(jié)點(diǎn)
// 那么程序會(huì)檢查字典是否在進(jìn)行 rehash 逞力，
// 然后才決定是直接返回 NULL ，還是繼續(xù)查找 1 號(hào)哈希表
if (!dictIsRehashing(d)) return NULL;
}
// 進(jìn)行到這里時(shí)糠爬，說(shuō)明兩個(gè)哈希表都沒(méi)找到
return NULL;
}
