詳解Redis 緩存刪除機(jī)制(源碼解析)
刪除的范圍
- 過(guò)期的 key
- 在內(nèi)存滿了的情況下，如果繼續(xù)執(zhí)行 set 等命令，且所有 key 都沒有過(guò)期，那么會(huì)按照緩存淘汰策略選中的 key
過(guò)期刪除
redis 中設(shè)置了過(guò)期時(shí)間的 key 會(huì)單獨(dú)存儲(chǔ)一份
typedef struct redisDb {
dict *dict; // 所有的鍵值對(duì)
dict *expires; //設(shè)置了過(guò)期時(shí)間的鍵值對(duì)
// ...
} redisDb;
設(shè)置有效期
Redis 中有 4 個(gè)命令可以給 key 設(shè)置過(guò)期時(shí)間，分別是 expire pexpire expireat pexpireat
設(shè)置相對(duì)時(shí)間
expire <key> <ttl>：將 key 值的過(guò)期時(shí)間設(shè)置為 ttl 秒。
// src/expire.c
/* EXPIRE key seconds */
void expireCommand(client *c) {
expireGenericCommand(c,mstime(),UNIT_SECONDS);
}
pexpire <key> <ttl>：將 key 值的過(guò)期時(shí)間設(shè)置為 ttl 毫秒。
// src/expire.c
/* PEXPIRE key milliseconds */
void pexpireCommand(client *c) {
expireGenericCommand(c,mstime(),UNIT_MILLISECONDS);
}
設(shè)置絕對(duì)時(shí)間
expireat <key> <timestamp>：將 key 值的過(guò)期時(shí)間設(shè)置為指定的 timestamp 秒數(shù)。
// src/expire.c
/* EXPIREAT key time */
void expireatCommand(client *c) {
expireGenericCommand(c,0,UNIT_SECONDS);
}
pexpireat <key> <timestamp>：將 key 值的過(guò)期時(shí)間設(shè)置為指定的 timestamp 毫秒數(shù)。
// src/expire.c
/* PEXPIREAT key ms_time */
void pexpireatCommand(client *c) {
expireGenericCommand(c,0,UNIT_MILLISECONDS);
}
以上 4 種方法最終都會(huì)調(diào)用下面的通用函數(shù) expireGenericCommand ：
// src/expire.c
void expireGenericCommand(client *c, long long basetime, int unit) {
robj *key = c->argv[1], *param = c->argv[2];
// 獲取數(shù)據(jù)對(duì)象
long long when;
if (getLongLongFromObjectOrReply(c, param, &when, NULL) != C_OK)
return;
// 將時(shí)間轉(zhuǎn)化成以 ms 為單位
if (unit == UNIT_SECONDS) when *= 1000;
when += basetime;
// 在 master 節(jié)點(diǎn)上，如果設(shè)置的過(guò)期時(shí)間小于當(dāng)前時(shí)間，那么將命令轉(zhuǎn)化成 DEL 指令
if (when <= mstime() && !server.loading && !server.masterhost) {
robj *aux;
int deleted = server.lazyfree_lazy_expire ? dbAsyncDelete(c->db,key) :
dbSyncDelete(c->db,key);
// ...
// 將刪除命令同步給 slave 和 AOF
// ...
} else {
// 設(shè)置過(guò)期時(shí)間
setExpire(c,c->db,key,when);
// ...
// 構(gòu)造返回值和發(fā)布對(duì)象更新消息
// ...
return;
}
}
設(shè)置過(guò)期時(shí)間的操作由 setExpire 執(zhí)行，他將 dictEntry 的 union v 中的 s64 設(shè)為過(guò)期時(shí)間
// src/db.c
void setExpire(client *c, redisDb *db, robj *key, long long when) {
dictEntry *kde, *de;
// 找出 db->dict 中對(duì)應(yīng)的存儲(chǔ)對(duì)象，這里的查詢和用 get 查詢數(shù)據(jù)是邏輯一樣，通過(guò) hashFunc(key) & sizemask
// 找到 bucket 后在鏈表中遍歷
kde = dictFind(db->dict,key->ptr);
// 找出 db->expires 中對(duì)應(yīng)的存儲(chǔ)對(duì)象，如果沒有則新建一個(gè)
de = dictAddOrFind(db->expires,dictGetKey(kde));
//
dictSetSignedIntegerVal(de,when);
// ...
}
#define dictSetSignedIntegerVal(entry, _val_) \
do { (entry)->v.s64 = _val_; } while(0)
db->expires 中存儲(chǔ)的 dictEntry 表示的是過(guò)期 key 和過(guò)期時(shí)間，存儲(chǔ)過(guò)期時(shí)間的 v 是一個(gè) union ，可見在 redis 中不同使用場(chǎng)景或不同編碼下 v 的意義不同
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;
查詢過(guò)期時(shí)間
ttl key 返回 key 剩余過(guò)期秒數(shù)。
// src/expire.c
/* TTL key */
void ttlCommand(client *c) {
ttlGenericCommand(c, 0);
}
pttl key 返回 key 剩余過(guò)期的毫秒數(shù)。
// src/expire.c
/* PTTL key */
void pttlCommand(client *c) {
ttlGenericCommand(c, 1);
}
以上 2 種查看方式最終都會(huì)調(diào)用下面的通用函數(shù) ttlGenericCommand ：
// src/expire.c
/* Implements TTL and PTTL */
void ttlGenericCommand(client *c, int output_ms) {
// ...
// key 不存在時(shí)報(bào)錯(cuò)
// ...
// 獲取過(guò)期時(shí)間，如果沒有過(guò)期時(shí)間則
expire = getExpire(c->db,c->argv[1]);
if (expire != -1) {
ttl = expire-mstime();
if (ttl < 0) ttl = 0;
}
if (ttl == -1) {
addReplyLongLong(c,-1);
} else {
// 根據(jù)指定的單位返回結(jié)果，以秒為單位時(shí)向上取整
addReplyLongLong(c,output_ms ? ttl : ((ttl+500)/1000));
}
}
獲取過(guò)期時(shí)間的操作由 getExpire 執(zhí)行，在 db->expires 中查詢到對(duì)象后，獲取 union v 中的成員 s64
// src/expire.c
// 返回過(guò)期時(shí)間的絕對(duì)時(shí)間
long long getExpire(redisDb *db, robj *key) {
dictEntry *de;
// 查詢對(duì)象
if (dictSize(db->expires) == 0 ||
// 如果返回為 NULL 表示沒有設(shè)置過(guò)期時(shí)間，向上返回 -1
(de = dictFind(db->expires,key->ptr)) == NULL) return -1;
// 獲取 v.s64
return dictGetSignedIntegerVal(de);
}
#define dictGetSignedIntegerVal(he) ((he)->v.s64)
過(guò)期策略
Redis 綜合使用 惰性刪除 和 定期掃描 實(shí)現(xiàn)
惰性刪除
每次訪問(wèn)時(shí)會(huì)調(diào)用 expireIfNeeded 判斷 key 是否過(guò)期，如果過(guò)期就刪除該鍵，否則返回鍵對(duì)應(yīng)的值。單獨(dú)使用這種策略可能會(huì)浪費(fèi)很多內(nèi)存。
// src/db.c
int expireIfNeeded(redisDb *db, robj *key) {
mstime_t when = getExpire(db,key);
mstime_t now;
// 沒有設(shè)置過(guò)期時(shí)間，直接返回
if (when < 0) return 0;
// 從硬盤中加載數(shù)據(jù)時(shí)不執(zhí)行過(guò)期操作
if (server.loading) return 0;
// 參考 GitHub Issue #1525
// 對(duì)于 master，在執(zhí)行 Lua Script 的過(guò)程中，可能會(huì)用某個(gè) key 是否存在當(dāng)作判斷條件
// 為了避免一個(gè)腳本中前后條件不一致，將當(dāng)前時(shí)間強(qiáng)制設(shè)為腳本開始時(shí)間
now = server.lua_caller ? server.lua_time_start : mstime();
// 對(duì)于 slave，返回此時(shí) key 是否已過(guò)期，但不執(zhí)行后續(xù)刪除操作
if (server.masterhost != NULL) return now > when;
// key 未過(guò)期
if (now <= when) return 0;
// 統(tǒng)計(jì)過(guò)期 key 的個(gè)數(shù)
server.stat_expiredkeys++;
// 向所有的 slave 和 AOF 文件寫入一條 DEL 指令
propagateExpire(db,key,server.lazyfree_lazy_expire);
// 向 keyspace channel 中發(fā)布一條 key 過(guò)期的消息
notifyKeyspaceEvent(NOTIFY_EXPIRED,
"expired",key,db->id);
// 根據(jù)配置決定是同步刪除還是異步刪除（僅刪除引用，由后臺(tái)線程執(zhí)行物理刪除）
return server.lazyfree_lazy_expire ? dbAsyncDelete(db,key) :
dbSyncDelete(db,key);
}
特殊處理
在 master 節(jié)點(diǎn)執(zhí)行 Lua 腳本時(shí)
參考 GitHub Issue #1525，對(duì)于 master，在執(zhí)行 Lua Script 的過(guò)程中，可能會(huì)用某個(gè) key 是否存在當(dāng)作判斷條件。為了避免一個(gè)腳本中前后條件不一致，將當(dāng)前時(shí)間強(qiáng)制設(shè)為腳本開始時(shí)間。
例如多次執(zhí)行如下 Lua 腳本 /tmp/myscript.lua 出現(xiàn)的結(jié)果可能不一致
-- /tmp/myscript.lua
if redis.call("exists",KEYS[1]) == 1
then
redis.call("incr","mycounter")
end
if redis.call("exists",KEYS[1]) == 1
then
return redis.call("incr","mycounter")
end
具體復(fù)現(xiàn)操作可以參考下面的 bash 腳本：
while [ 1 ] do redis-cli set x foo px 100 > /dev/null sleep 0.092 redis-cli --eval /tmp/myscript.lua x > /dev/null sleep 0.1 redis-cli get mycounter redis-cli -p 6380 get mycounter done
對(duì)于 slave 節(jié)點(diǎn)
在 slave 節(jié)點(diǎn)上，key 的刪除操作由 master 發(fā)來(lái)的 DEL 執(zhí)行，因此這里只返回是否過(guò)期的結(jié)果給客戶端，而不執(zhí)行刪除操作
正在從 RDB 和 AOF 讀取數(shù)據(jù)時(shí)跳過(guò)這個(gè)步驟
定期掃描
系統(tǒng)每隔一段時(shí)間就定期掃描一次，發(fā)現(xiàn)過(guò)期的鍵就進(jìn)行刪除。單獨(dú)使用這種策略可能出現(xiàn)鍵已經(jīng)過(guò)期但沒有刪除的情況
Redis 默認(rèn)每 100ms 執(zhí)行一次（通過(guò) hz 參數(shù)配置，執(zhí)行周期為 1s/hz）過(guò)期掃描。由于 redisDb 中設(shè)置了過(guò)期時(shí)間的 key 會(huì)單獨(dú)存儲(chǔ)，所以不會(huì)出現(xiàn)掃描所有 key 的情況
具體步驟由 activeExpireCycle 函數(shù)執(zhí)行
activeExpireCycle、incrementallyRehash 等后臺(tái)操作都是由 databasesCron 觸發(fā)的
void activeExpireCycle(int type) {
// ...
// 依次遍歷各個(gè) db
for (j = 0; j < dbs_per_call && timelimit_exit == 0; j++) {
int expired;
redisDb *db = server.db+(current_db % server.dbnum);
// 記錄下一個(gè)執(zhí)行的 db，這樣如果因?yàn)槌瑫r(shí)意外退出，下次可以繼續(xù)從這個(gè) db 開始，
// 從而在所有 db 上均勻執(zhí)行清除操作
current_db++;
do {
// ...
// 跳過(guò)沒有設(shè)置過(guò)期時(shí)間的 key 等不需要執(zhí)行的情況
// ...
// 抽樣個(gè)數(shù)，默認(rèn)為 20
if (num > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP)
num = ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP;
// 從設(shè)置了過(guò)期時(shí)間的 key 中隨機(jī)抽取 20 個(gè)
while (num--) {
dictEntry *de;
long long ttl;
// 隨機(jī)挑選 dict 中的一個(gè) key
if ((de = dictGetRandomKey(db->expires)) == NULL) break;
ttl = dictGetSignedIntegerVal(de)-now;
// 執(zhí)行刪除，具體刪除操作和惰性刪除中類似
if (activeExpireCycleTryExpire(db,de,now)) expired++;
// ...
}
// ...
// 更新統(tǒng)計(jì)數(shù)據(jù)等操作
// ...
// 如果每次刪除的 key 超過(guò)了樣本數(shù)的 25%，說(shuō)明過(guò)期鍵占的比例較高，需要再重復(fù)執(zhí)行依次
} while (expired > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP/4);
}
// ...
}
隨機(jī)抽樣由 dictGetRandomKey 執(zhí)行
// src/dict.c
/* Return a random entry from the hash table. Useful to
* implement randomized algorithms */
dictEntry *dictGetRandomKey(dict *d)
{
dictEntry *he, *orighe;
unsigned long h;
int listlen, listele;
// 沒有數(shù)據(jù)，返回為 NULL，外層函數(shù)接收到 NULL 后會(huì)中斷過(guò)期操作的執(zhí)行
if (dictSize(d) == 0) return NULL;
// 根據(jù) rehashidx 參數(shù)判斷是否正在執(zhí)行 rehash，如果正在執(zhí)行，
// 則先執(zhí)行 rehash 中的一個(gè)步驟
if (dictIsRehashing(d)) _dictRehashStep(d);
if (dictIsRehashing(d)) {
do {
// 正在執(zhí)行 rehash，所以兩個(gè) ht 中的對(duì)象都要考慮
//
// 由于正在執(zhí)行 rehash，所以可以肯定 ht[0] 中下標(biāo)小于等于 rehashidx 的 bucket
// 肯定沒有數(shù)據(jù)，所以只從 ht[0] 中大于 rehashidx 的 bucket 和 ht[1] 中抽取
h = d->rehashidx + (random() % (d->ht[0].size +
d->ht[1].size -
d->rehashidx));
he = (h >= d->ht[0].size) ? d->ht[1].table[h - d->ht[0].size] :
d->ht[0].table[h];
// 取到空 bucket 時(shí)重試
} while(he == NULL);
} else {
do {
// 參考寫入 ht 時(shí)計(jì)算下標(biāo)的規(guī)則 hashFunc(key) & sizemake
// 這里 random() & sizemask 是隨機(jī)取一個(gè)下標(biāo)
h = random() & d->ht[0].sizemask;
he = d->ht[0].table[h];
// 取到空 bucket 時(shí)重試
} while(he == NULL);
}
// 到這一步 he 是 ht[n] 中某個(gè) bucket 中完整的鏈表
// 所以還要從這個(gè)鏈表中隨機(jī)取一個(gè)對(duì)象
// 遍歷計(jì)算整個(gè)鏈表的長(zhǎng)度
listlen = 0;
orighe = he;
while(he) {
he = he->next;
listlen++;
}
// 隨機(jī)取鏈表中某個(gè)對(duì)象的下標(biāo)
listele = random() % listlen;
he = orighe;
// 重新遍歷鏈表獲取指定下標(biāo)的對(duì)象
while(listele--) he = he->next;
return he;
}
緩存淘汰
配置最大內(nèi)存限制
在 redis.conf 中配置
redis server 啟動(dòng)時(shí)加載配置文件和命令行參數(shù)中的 maxmemory ，存入 Server 對(duì)象的 maxmemory 字段
main 中在 redis server 啟動(dòng)時(shí)執(zhí)行初始化等操作，其中會(huì)執(zhí)行加載配置文件的 loadServerConfig 函數(shù)
// src/server.c
int main(int argc, char **argv) {
// ..
// 加載配置
loadServerConfig(configfile,options);
// ..
// 警告過(guò)小的配置
if (server.maxmemory > 0 && server.maxmemory < 1024*1024) {
serverLog(LL_WARNING,"WARNING: You specified a maxmemory value that is less than 1MB (current value is %llu bytes). Are you sure this is what you really want?", server.maxmemory);
}
}
loadServerConfig 中將配置文件、stdin、命令行參數(shù)加載到 config 字符串中，然后調(diào)用 loadServerConfigFromString
// src/config.c
void loadServerConfig(char *filename, char *options) {
sds config = sdsempty();
char buf[CONFIG_MAX_LINE+1];
// 加載配置文件
if (filename) {
FILE *fp;
// 啟動(dòng)命令為 ./redis-server - 則從 stdin 中讀取，需要用 <C-D> 觸發(fā) EOF
if (filename[0] == '-' && filename[1] == '\0') {
fp = stdin;
} else {
// 第一個(gè)參數(shù)不是 -，則嘗試打開這個(gè)參數(shù)指定的文件
if ((fp = fopen(filename,"r")) == NULL) {
serverLog(LL_WARNING,
"Fatal error, can't open config file '%s'", filename);
exit(1);
}
}
// 將配置文件中的每一行追加到 config 中
while(fgets(buf,CONFIG_MAX_LINE+1,fp) != NULL)
config = sdscat(config,buf);
if (fp != stdin) fclose(fp);
}
// 添加其他選項(xiàng)，例如 ./redis-server --port 8080 后面的參數(shù)，直接加到 config 中
if (options) {
config = sdscat(config,"\n");
config = sdscat(config,options);
}
loadServerConfigFromString(config);
sdsfree(config);
}
loadServerConfigFromString 從上一步中的 config 字符串中逐行讀取配置，并寫入 server 對(duì)象
// src/config.c
void loadServerConfigFromString(char *config) {
// ...
// 按行讀取配置文件
lines = sdssplitlen(config,strlen(config),"\n",1,&totlines);
for (i = 0; i < totlines; i++) {
// 跳過(guò)無(wú)效的配置和注釋
// ...
argv = sdssplitargs(lines[i],&argc);
// 將配置命令轉(zhuǎn)化成小寫
sdstolower(argv[0]);
// 根據(jù)配置命令初始化配置，strcasecmp 比較
if (!strcasecmp(argv[0],"timeout") && argc == 2) {
server.maxidletime = atoi(argv[1]);
if (server.maxidletime < 0) {
err = "Invalid timeout value"; goto loaderr;
}
// ...
} else if (!strcasecmp(argv[0],"maxmemory") && argc == 2) {
// memtoll 將字符串形式的配置轉(zhuǎn)化成對(duì)應(yīng)的 long long 值
// 例如 1kb -> 1024
server.maxmemory = memtoll(argv[1],NULL);
}
}
}
使用 CONFIG SET 命令配置
Redis Server 接收到客戶端的 CONFIG SET 命令后調(diào)用 configSetCommand 函數(shù)
服務(wù)端接收到命令時(shí)將命令和參數(shù)存入 Redis Server 的 argc 和 argv
argc: 4 argv: 0 1 2 3 config set maxmemory 10mb
動(dòng)態(tài)配置 maxmemory 后會(huì)立即嘗試觸發(fā)內(nèi)存回收，而修改其他內(nèi)存相關(guān)配置(例如: maxmemory_policy)時(shí)不會(huì)觸發(fā)
if (0) {
// ...
} config_set_memory_field("maxmemory",server.maxmemory) {
// 配置不為 0，表示之前限制過(guò)內(nèi)存
if (server.maxmemory) {
if (server.maxmemory < zmalloc_used_memory()) {
serverLog(LL_WARNING,"WARNING: the new maxmemory value set via CONFIG SET is smaller than the current memory usage. This will result in keys eviction and/or inability to accept new write commands depending on the maxmemory-policy.");
}
freeMemoryIfNeeded();
}
// ...
}
32 位機(jī)器的內(nèi)存限制
對(duì)于 64 位機(jī)器，將 maxmemory 設(shè)置為 0 表示不限制內(nèi)存，但由于 32 位尋址空間最多只有 4 GB，所以默認(rèn)內(nèi)存限制設(shè)為 3 GB，緩存淘汰策略設(shè)為 noeviction
// src/server.c
// ...
if (server.arch_bits == 32 && server.maxmemory == 0) {
serverLog(LL_WARNING,"Warning: 32 bit instance detected but no memory limit set. Setting 3 GB maxmemory limit with 'noeviction' policy now.");
server.maxmemory = 3072LL*(1024*1024); /* 3 GB */
server.maxmemory_policy = MAXMEMORY_NO_EVICTION;
}
淘汰策略
淘汰策略使用 CONFIG SET maxmemory-policy 配置
默認(rèn)：
- **noeviction: **內(nèi)存滿了后對(duì)于 set 等命令直接返回錯(cuò)誤
針對(duì)所有 key：
- allkeys-lru: 在所有 key 的范圍內(nèi)使用 LRU 算法執(zhí)行刪除，如果內(nèi)存仍然不夠，則報(bào)錯(cuò)
- **allkeys-lfu: **在所有 key 的范圍內(nèi)使用 LRU 算法執(zhí)行刪除，如果內(nèi)存仍然不夠，則報(bào)錯(cuò)
- **allkeys-random: **在所有 key 的范圍內(nèi)隨機(jī)執(zhí)行刪除，如果內(nèi)存仍然不夠，則報(bào)錯(cuò)
針對(duì)設(shè)置了過(guò)期時(shí)間的 key：
- **volatile-lru: **在設(shè)置了過(guò)期時(shí)間的 key 中使用 LRU 算法執(zhí)行刪除，如果內(nèi)存仍然不夠，則報(bào)錯(cuò)
- **volatile-lfu: **在設(shè)置了過(guò)期時(shí)間的 key 中使用 LRU 算法執(zhí)行刪除，如果內(nèi)存仍然不夠，則報(bào)錯(cuò)
- **volatile-random: **在設(shè)置了過(guò)期時(shí)間的 key 中隨機(jī)執(zhí)行刪除，如果內(nèi)存仍然不夠，則報(bào)錯(cuò)
- **volatile-ttl: **刪除即將過(guò)期的 key，如果內(nèi)存仍然不夠，則報(bào)錯(cuò)
Redis 在執(zhí)行淘汰之前會(huì)計(jì)算部分對(duì)象的 idle 值，使用不同淘汰策略時(shí)計(jì)算 idle 值的方法也不同， idle 值越大表示這個(gè)值越需要優(yōu)先刪除。
下面主要介紹 LRU 和 LFU 中 idle 值的計(jì)算方法
LRU 淘汰策略
抽樣刪除，樣本數(shù)量通過(guò) CONFIG SET maxmemory-samples 100 控制，對(duì)應(yīng) RedisObject 中的 maxmemory_samples 參數(shù)，抽樣數(shù)量越多和傳統(tǒng)的 LRU 算法越接近
優(yōu)化策略
為了避免傳統(tǒng)的 LRU 算法通常使用 hashmap + 鏈表實(shí)現(xiàn)帶來(lái)的開銷，Redis 進(jìn)行了如下優(yōu)化：
RedisObject 結(jié)構(gòu)中設(shè)置了一個(gè) lru 字段，用來(lái)記錄數(shù)據(jù)的訪問(wèn)時(shí)間戳，而不是每次調(diào)整對(duì)象在鏈表中的位置
typedef struct redisObject {
// 對(duì)象類型
unsigned type:4;
// 對(duì)象編碼
unsigned encoding:4;
// LRU 算法和 LFU 算法公用 lru 這個(gè)字段
//
// LRU_BITS 默認(rèn)為 24，因此最大只能存儲(chǔ) 194 天的時(shí)間戳,
// 創(chuàng)建對(duì)象時(shí)會(huì)寫入這個(gè)字段，訪問(wèn)對(duì)象時(shí)會(huì)更新這個(gè)字段，
// 超過(guò)之后再?gòu)?0 開始計(jì)算
unsigned lru:LRU_BITS;
int refcount;
void *ptr;
} robj;
使用抽樣數(shù)組代替鏈表，后續(xù)在候選集合中根據(jù) lru 字段值的大小進(jìn)行篩選，避免了鏈表帶來(lái)的開銷。候選集合中的對(duì)象用 evictionPoolEntry 表示
struct evictionPoolEntry {
unsigned long long idle; // 用于淘汰排序，在不同算法中意義不同
sds key; // 鍵的名字
// ...
};
計(jì)算方法
全局對(duì)象 lru_clock 記錄了當(dāng)前的 unix 時(shí)間戳，由 serverCron 調(diào)用 updateCachedTime 默認(rèn)每 100 ms 更新一次。更新頻率與 hz 參數(shù)有關(guān)， 1s/hz 即為更新間隔時(shí)間。
LRU_CLOCK_RESOLUTION 的值為 1000，因此使用 LRU_CLOCK 函數(shù)獲取 lru_clock 時(shí)，如果每秒更新頻率在 1 次以上，會(huì)使用全局變量中緩存的 lrulcock
unsigned int LRU_CLOCK(void) {
unsigned int lruclock;
if (1000/server.hz <= LRU_CLOCK_RESOLUTION) {
atomicGet(server.lruclock,lruclock);
} else {
lruclock = getLRUClock();
}
return lruclock;
}
如果更新頻率不到每秒 1 次，則會(huì)用函數(shù) getLRUClock 實(shí)時(shí)計(jì)算 lruclock
unsigned int getLRUClock(void) {
// mstime() 獲取 unix 時(shí)間戳，單位時(shí)毫秒
// 除以 LRU_CLOCK_RESOLUTION(值為 1000)，將時(shí)間戳轉(zhuǎn)化為秒
return (mstime()/LRU_CLOCK_RESOLUTION) & LRU_CLOCK_MAX;
}
其中 LRU_CLOCK_MAX 表示 lru_clock 最大的可能值，這個(gè)值與 redisObject 中 lru 最大的可能值一樣，定義如下：
#define LRU_CLOCK_MAX ((1<<LRU_BITS)-1)
所以最終比較時(shí) lru_clock 和 robj.lru 的值都在 [0, LRU_CLOCK_MAX] 的范圍內(nèi)。
從邏輯上講， 當(dāng)前時(shí)間戳應(yīng)該永遠(yuǎn)大于上次訪問(wèn)的時(shí)間戳 ,因此正常的計(jì)算規(guī)則應(yīng)該是 lru_clock-robj.lru 。
但是由于 lru_clock 和 robj.lru 是當(dāng)前時(shí)間戳取模后的值，所以可能出現(xiàn) lru_clock 小于 robj.lru 的情況，所以這種情況下計(jì)算規(guī)則應(yīng)該改為 lru_clock+194天-robj.lru
但是對(duì)于 lru_clock 和 robj.lru 間隔超過(guò) 194 天的情況仍然無(wú)法判斷，所以更能存在刪除不準(zhǔn)確的情況。
將上述的邏輯組合起來(lái)就是 LRU 算法下獲取 idle 值的函數(shù):
// src/evict.c
// 以秒為精度計(jì)算對(duì)象距離上一次訪問(wèn)的間隔時(shí)間，然后轉(zhuǎn)化成毫秒返回
unsigned long long estimateObjectIdleTime(robj *o) {
unsigned long long lruclock = LRU_CLOCK();
if (lruclock >= o->lru) {
return (lruclock - o->lru) * LRU_CLOCK_RESOLUTION;
} else {
return (lruclock + (LRU_CLOCK_MAX - o->lru)) *
LRU_CLOCK_RESOLUTION;
}
}
在 Redis 3.0 中，當(dāng)取樣數(shù)量設(shè)為 10 時(shí)，已經(jīng)和傳統(tǒng)的 LRU 算法效果很接近了
LFU 淘汰策略
LFU 算法復(fù)用 robj.lru 字段，將這個(gè) 24 bit 的字段拆分成了兩部分：
- ldt(last decrement time，單位：分鐘)：lru 字段的前 16bit，表示數(shù)據(jù)的訪問(wèn)時(shí)間戳，最多只能存儲(chǔ) 45 天。
- counter 值：lru 字段的后 8bit，表示數(shù)據(jù)的訪問(wèn)頻率
遞增策略
counter 能表示的最大值是 255，因此 counter 與訪問(wèn)次數(shù)不能是線性關(guān)系，這里采用的計(jì)算步驟如下：
- 隨機(jī)取 0 到 1 之間的隨機(jī)數(shù) r
- 比較 r 與 1/((counter-LFU_INIT_VAL)*lfu_log_factor+1) 的大小，其中 LFU_INIT_VAL 是常量，默認(rèn)為 5，lfu_log_factor 是可配置參數(shù)，默認(rèn)為 10
- 如果 r 小則 counter 增加 1，否則 counter 不變
實(shí)現(xiàn)代碼如下：
uint8_t LFULogIncr(uint8_t counter) {
// counter 值已經(jīng)到達(dá)了 255，不能再增加，直接返回
if (counter == 255) return 255;
double r = (double)rand()/RAND_MAX;
double baseval = counter - LFU_INIT_VAL; // LFU_INIT_VAL 值為 5
if (baseval < 0) baseval = 0;
double p = 1.0/(baseval*server.lfu_log_factor+1);
if (r < p) counter++;
return counter;
}
訪問(wèn)次數(shù)與 counter 值之間大概是對(duì)數(shù)關(guān)系，counter 值越大，增速越低
// https://redis.io/topics/lru-cache +--------+------------+------------+------------+------------+------------+ | factor | 100 hits | 1000 hits | 100K hits | 1M hits | 10M hits | +--------+------------+------------+------------+------------+------------+ | 0 | 104 | 255 | 255 | 255 | 255 | +--------+------------+------------+------------+------------+------------+ | 1 | 18 | 49 | 255 | 255 | 255 | +--------+------------+------------+------------+------------+------------+ | 10 | 10 | 18 | 142 | 255 | 255 | +--------+------------+------------+------------+------------+------------+ | 100 | 8 | 11 | 49 | 143 | 255 | +--------+------------+------------+------------+------------+------------+
衰減策略
除了訪問(wèn)對(duì)象時(shí) counter 需要增加，對(duì)于一段時(shí)間內(nèi)沒有訪問(wèn)的對(duì)象還要相應(yīng)地減少 counter 值，遞減的速率由 lfu-decay-time 參數(shù)控制。
counter 衰減步驟如下：
取當(dāng)前時(shí)間戳（單位：分鐘）的低 16 位記為 now ，計(jì)算與 ldt 的差值。這里與 LRU 算法中計(jì)算 lru_clock 和 robj.lru 時(shí)可能出現(xiàn)一樣的問(wèn)題，由于 ldt 最多只能表示 45 天，所以如果距離對(duì)象上次訪問(wèn)超過(guò) 45 天，則無(wú)法準(zhǔn)確計(jì)算訪問(wèn)的時(shí)間間隔
unsigned long LFUDecrAndReturn(robj *o) {
// 取高 16 位
unsigned long ldt = o->lru >> 8;
// 取低 8 位
unsigned long counter = o->lru & 255;
// 如果 lfu_decay_time 為 0，則步修改 counter，否則將 counter 減少 LFUTimeElapsed(ldt)/lfu_decay_time
unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;
if (num_periods)
// 保證 counter 的最小值位 0
counter = (num_periods > counter) ? 0 : counter - num_periods;
return counter;
}
// 計(jì)算距離上次訪問(wèn)的間隔時(shí)間
unsigned long LFUTimeElapsed(unsigned long ldt) {
// 取當(dāng)前時(shí)間戳（單位：分鐘）
unsigned long now = LFUGetTimeInMinutes();
// 計(jì)算時(shí)間差
if (now >= ldt) return now-ldt;
return 65535-ldt+now;
}
// 獲取當(dāng)前時(shí)間戳，以分鐘為單位，取低 8 位
unsigned long LFUGetTimeInMinutes(void) {
return (server.unixtime/60) & 65535;
}
如果 lfu_decay_time 為 0，則步修改 counter，否則將 counter 減少 LFUTimeElapsed(ldt)/lfu_decay_time
例如，在 lfu_decay_time 為 1 的情況下，如果有 N 分鐘沒有訪問(wèn)這個(gè)對(duì)象，那么 counter 值減 N
每次訪問(wèn)一個(gè)對(duì)象時(shí)都會(huì)調(diào)用 updateLFU 更新 counter 的值：
void updateLFU(robj *val) {
unsigned long counter = LFUDecrAndReturn(val);
counter = LFULogIncr(counter);
val->lru = (LFUGetTimeInMinutes()<<8) | counter;
}
執(zhí)行淘汰
當(dāng) Redis 需要淘汰一批數(shù)據(jù)時(shí)，會(huì)調(diào)用 evictionPoolPopulate 獲取一批待刪除對(duì)象，根據(jù)設(shè)置的淘汰范圍的不同，會(huì)決定傳遞給 evictionPoolPopulate 的 sampledict 參數(shù)是存有全部數(shù)據(jù)的 db->dict 還是只有設(shè)置了過(guò)期時(shí)間的數(shù)據(jù)的 db->expires
void evictionPoolPopulate(int dbid, dict *sampledict, dict *keydict, struct evictionPoolEntry *pool) {
int j, k, count;
dictEntry *samples[server.maxmemory_samples];
// 隨機(jī)獲取 server.maxmemory_samples 個(gè)對(duì)象，寫入 samples 中
count = dictGetSomeKeys(sampledict,samples,server.maxmemory_samples);
// 遍歷每個(gè)對(duì)象
for (j = 0; j < count; j++) {
// ...
// 初始化
// ...
de = samples[j];
key = dictGetKey(de);
// 如果獲取樣本的字典不是 db->dict（還可能是 db->expires），并且不是按 volatile-ttl 淘汰
// 那么還要將對(duì)象轉(zhuǎn)化成數(shù)據(jù)字典中對(duì)應(yīng)的對(duì)象，然后取其值
if (server.maxmemory_policy != MAXMEMORY_VOLATILE_TTL) {
if (sampledict != keydict) de = dictFind(keydict, key);
// #define dictGetVal(he) ((he)->v.val)
// 這里還是利用 union 的特性，如果是 db->dict 中的元素，返回的是鍵的值
// 如果是 db->expires 中的元素，返回的是過(guò)期時(shí)間
o = dictGetVal(de);
}
// 按各算法計(jì)算 idle 分值，idle 越大的越應(yīng)該被先淘汰
//
// 如果使用 LRU 淘汰算法，則計(jì)算對(duì)象的空閑時(shí)間
if (server.maxmemory_policy & MAXMEMORY_FLAG_LRU) {
idle = estimateObjectIdleTime(o);
// 使用 LFU 淘汰算法，
} else if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
idle = 255-LFUDecrAndReturn(o);
// 使用 volatile-ttl 算法，用 ULLONG_MAX 減去過(guò)期時(shí)間作為分值
} else if (server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL) {
idle = ULLONG_MAX - (long)dictGetVal(de);
} else {
serverPanic("Unknown eviction policy in evictionPoolPopulate()");
}
k = 0;
// 與原 pool 中的 idle 值進(jìn)行比較，找出應(yīng)該比當(dāng)前對(duì)象先淘汰出去的對(duì)象
while (k < EVPOOL_SIZE &&
pool[k].key &&
pool[k].idle < idle) k++;
if (k == 0 && pool[EVPOOL_SIZE-1].key != NULL) {
// 沒有發(fā)現(xiàn)更需要被淘汰的對(duì)象，并且 pool 中也沒有多余的位置
// 那么當(dāng)前對(duì)象仍然留在 samples 中
continue;
} else if (k < EVPOOL_SIZE && pool[k].key == NULL) {
// 沒有發(fā)現(xiàn)更需要被淘汰的對(duì)象，但 pool 中有多余的位置
// 于是將這個(gè)對(duì)象插入 pool 中
} else {
// 當(dāng)前對(duì)象
// |
// V
// Pool: [ 0 1 2 3 ...k-1 k ... EVPOOL_SIZE-1]
// 為了保證 pool 中的數(shù)據(jù)按 idle 從小到大排列，這里將當(dāng)前對(duì)象插入第 k 個(gè)對(duì)象后面的位置
if (pool[EVPOOL_SIZE-1].key == NULL) {
// pool 的右邊還有空余的位置，因此將從第 k 個(gè)開始后面的元素整體后移
memmove(pool+k+1,pool+k,
sizeof(pool[0])*(EVPOOL_SIZE-k-1));
} else {
// pool 的右邊沒有空余的位置了，那么將 pool 中前 k 個(gè)元素整體左移
sds cached = pool[0].cached;
memmove(pool,pool+1,sizeof(pool[0])*k);
}
}
// ...
// 將當(dāng)前對(duì)象的屬性賦值到下標(biāo)為 k 的元素
// ...
}
}
完成上述操作后，pool 中剩下的就是新篩選出來(lái)的最需要淘汰的對(duì)象了。
在 freeMemoryIfNeeded 中會(huì)調(diào)用 evictionPoolPopulate 來(lái)篩選需要淘汰的對(duì)象，每次刪除一個(gè)，直到釋放了足夠的內(nèi)存。如果始終無(wú)法達(dá)到內(nèi)存需求，則會(huì)報(bào)錯(cuò)。
到此這篇關(guān)于Redis 緩存刪除機(jī)制(源碼解析)的文章就介紹到這了,更多相關(guān)Redis 緩存刪除內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Linux下安裝Redis并設(shè)置相關(guān)服務(wù)
這篇文章主要為大家介紹了Linux下安裝Redis并設(shè)置相關(guān)服務(wù)，感興趣的小伙伴們可以參考一下2016-01-01
簡(jiǎn)介L(zhǎng)ua腳本與Redis數(shù)據(jù)庫(kù)的結(jié)合使用
這篇文章主要介紹了簡(jiǎn)介L(zhǎng)ua腳本與Redis數(shù)據(jù)庫(kù)的結(jié)合使用,Redis是基于主存的高性能數(shù)據(jù)庫(kù),需要的朋友可以參考下2015-06-06
本文主要介紹了詳解redis big key 排查思路，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-06-06
在現(xiàn)代的分布式系統(tǒng)中,Redis作為一種高性能的鍵值存儲(chǔ)數(shù)據(jù)庫(kù),被廣泛應(yīng)用于緩存、消息隊(duì)列、會(huì)話存儲(chǔ)等場(chǎng)景,隨著業(yè)務(wù)的發(fā)展,Redis實(shí)例的數(shù)據(jù)遷移需求也變得越來(lái)越常見,本文將詳細(xì)介紹Redis數(shù)據(jù)遷移的多種方法,并通過(guò)命令行工具幫助你輕松完成遷移任務(wù)2025-01-01
本篇文章主要介紹了SSH框架和Redis的整合，詳細(xì)的介紹了Struts+Spring+Hibernate和Redis整合，有興趣的可以了解一下。2017-03-03
MyBatis緩存和二級(jí)緩存整合Redis的解決方案
這篇文章主要介紹了MyBatis緩存和二級(jí)緩存整合Redis,將MyBatis緩存和二級(jí)緩存整合Redis，可以提高查詢效率，同時(shí)也能保證數(shù)據(jù)的可靠性和一致性，需要的朋友可以參考下2023-07-07
如何使用注解方式實(shí)現(xiàn)?Redis?分布式鎖
這篇文章主要介紹了如何使用注解方式實(shí)現(xiàn)Redis分布式鎖，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，教大家如何優(yōu)雅的使用Redis分布式鎖，感興趣的小伙伴可以參考一下2022-07-07
本文主要介紹了IDEA中的Redis插件連接Redis服務(wù)器，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-02-02
在ssm項(xiàng)目中使用redis緩存查詢數(shù)據(jù)的方法
本文主要簡(jiǎn)單的使用Java代碼進(jìn)行redis緩存，即在查詢的時(shí)候先在service層從redis緩存中獲取數(shù)據(jù)。如果大家對(duì)在ssm項(xiàng)目中使用redis緩存查詢數(shù)據(jù)的相關(guān)知識(shí)感興趣的朋友跟隨腳本之家小編一起看看吧2018-03-03
Redis延遲隊(duì)列和分布式延遲隊(duì)列的簡(jiǎn)答實(shí)現(xiàn)
在我們的工作中，很多地方使用延遲隊(duì)列，比如訂單到期沒有付款取消訂單，制訂一個(gè)提醒的任務(wù)等都需要延遲隊(duì)列，那么我們需要實(shí)現(xiàn)延遲隊(duì)列，本文就來(lái)介紹一下如何實(shí)現(xiàn)，感興趣的可以了解一下2021-05-05