本文主要介紹Redis的幾種數(shù)據(jù)淘汰機制。
I测僵、上帝視角
由于Redis是內(nèi)存型數(shù)據(jù)庫缕探，其允許用戶設(shè)置最大使用內(nèi)存大小為maxmemory缅疟，在內(nèi)存有限的情況下，為減少內(nèi)存緊張的情況淮菠，當內(nèi)存數(shù)據(jù)集大小上升至一定值時男公，就會實施數(shù)據(jù)淘汰機制。
Redis提供了以下幾種數(shù)據(jù)淘汰策略：
1合陵、 volatile-lru：從設(shè)置過期的數(shù)據(jù)集中淘汰最少使用的數(shù)據(jù)枢赔；
2、volatile-ttl：從設(shè)置過期的數(shù)據(jù)集中淘汰即將過期的數(shù)據(jù)（離過期時間最近）拥知；
3踏拜、volatile-random：從設(shè)置過期的數(shù)據(jù)集中隨機選取數(shù)據(jù)淘汰；
4低剔、allkeys-lru：從所有 數(shù)據(jù)集中選取使用最少的數(shù)據(jù)速梗；
5、allkeys-random：從所有數(shù)據(jù)集中任意選取數(shù)據(jù)淘汰襟齿；
6姻锁、no-envicition：不進行淘汰；
II猜欺、LRU數(shù)據(jù)淘汰
1位隶、redisServer中保存了lru計數(shù)器server.lrulock，會定時更新开皿，這是根據(jù)server.unixtime計算出來的：
// redisServer 保存了lru 計數(shù)器
/*src/redis.h/redisServer*/
struct redisServer {
...
unsigned lruclock:22; /* Clock incrementing every minute, for LRU */
...
};
2涧黄、LRU數(shù)據(jù)淘汰機制使這樣的：從數(shù)據(jù)集中隨機挑選幾個鍵值對篮昧，取出其中l(wèi)ru最大的鍵值對淘汰。
III弓熏、TTL數(shù)據(jù)淘汰
1恋谭、TTL淘汰機制使從過期時間redisDB.expires表中隨機挑選幾個鍵值對，取出其中ttl最大的鍵值對淘汰挽鞠。
IV疚颊、淘汰發(fā)生
1、Redis服務(wù)器沒執(zhí)行一個命令信认，都會檢測內(nèi)存材义，判斷是否需要進行數(shù)據(jù)淘汰：
// 執(zhí)行命令
/*src/redis.cprocessCommand*/
int processCommand(redisClient *c) {
......
// 內(nèi)存超額
/* Handle the maxmemory directive.
**
First we try to free some memory if possible (if there are volatile
* keys in the dataset). If there are not the only thing we can do
* is returning an error. */
if (server.maxmemory) {
int retval = freeMemoryIfNeeded();
if ((c->cmd->flags & REDIS_CMD_DENYOOM) && retval == REDIS_ERR) {
flagTransaction(c);
addReply(c, shared.oomerr);
return REDIS_OK;
}
}
......
}
2、這其中主要調(diào)用了freeMemoryIfNeeded函數(shù)嫁赏，它完成了完整的數(shù)據(jù)淘汰機制：
int freeMemoryIfNeeded(void) {
size_t mem_used, mem_tofree, mem_freed;
int slaves = listLength(server.slaves);
/* Remove the size of slaves output buffers and AOF buffer from the
* count of used memory. */
// 計算出 Redis 目前占用的內(nèi)存總數(shù)其掂，但有兩個方面的內(nèi)存不會計算在內(nèi)：
// 1）從服務(wù)器的輸出緩沖區(qū)的內(nèi)存
// 2）AOF 緩沖區(qū)的內(nèi)存
mem_used = zmalloc_used_memory();
if (slaves) {
listIter li;
listNode *ln;
listRewind(server.slaves,&li);
while((ln = listNext(&li))) {
redisClient *slave = listNodeValue(ln);
unsigned long obuf_bytes = getClientOutputBufferMemoryUsage(slave);
if (obuf_bytes > mem_used)
mem_used = 0;
else
mem_used -= obuf_bytes;
}
}
if (server.aof_state != REDIS_AOF_OFF) {
mem_used -= sdslen(server.aof_buf);
mem_used -= aofRewriteBufferSize();
}
/* Check if we are over the memory limit. */
// 如果目前使用的內(nèi)存大小比設(shè)置的 maxmemory 要小，那么無須執(zhí)行進一步操作
if (mem_used <= server.maxmemory) return REDIS_OK;
// 如果占用內(nèi)存比 maxmemory 要大潦蝇，但是 maxmemory 策略為不淘汰款熬，那么直接返回
if (server.maxmemory_policy == REDIS_MAXMEMORY_NO_EVICTION)
return REDIS_ERR; /* We need to free memory, but policy forbids. */
/* Compute how much memory we need to free. */
// 計算需要釋放多少字節(jié)的內(nèi)存
mem_tofree = mem_used - server.maxmemory;
// 初始化已釋放內(nèi)存的字節(jié)數(shù)為 0
mem_freed = 0;
// 根據(jù) maxmemory 策略，
// 遍歷字典攘乒，釋放內(nèi)存并記錄被釋放內(nèi)存的字節(jié)數(shù)
while (mem_freed < mem_tofree) {
int j, k, keys_freed = 0;
// 遍歷所有字典
for (j = 0; j < server.dbnum; j++) {
long bestval = 0; /* just to prevent warning */
sds bestkey = NULL;
dictEntry *de;
redisDb *db = server.db+j;
dict *dict;
if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM)
{
// 如果策略是 allkeys-lru 或者 allkeys-random
// 那么淘汰的目標為所有數(shù)據(jù)庫鍵
dict = server.db[j].dict;
} else {
// 如果策略是 volatile-lru 贤牛、 volatile-random 或者 volatile-ttl
// 那么淘汰的目標為帶過期時間的數(shù)據(jù)庫鍵
dict = server.db[j].expires;
}
// 跳過空字典
if (dictSize(dict) == 0) continue;
/* volatile-random and allkeys-random policy */
// 如果使用的是隨機策略，那么從目標字典中隨機選出鍵
if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM ||
server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_RANDOM)
{
de = dictGetRandomKey(dict);
bestkey = dictGetKey(de);
}
/* volatile-lru and allkeys-lru policy */
// 如果使用的是 LRU 策略则酝，
// 那么從一集 sample 鍵中選出 IDLE 時間最長的那個鍵
else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
{
struct evictionPoolEntry *pool = db->eviction_pool;
while(bestkey == NULL) {
//隨機取一集鍵值對
evictionPoolPopulate(dict, db->dict, db->eviction_pool);
/* Go backward from best to worst element to evict. */
for (k = REDIS_EVICTION_POOL_SIZE-1; k >= 0; k--) {
if (pool[k].key == NULL) continue;
de = dictFind(dict,pool[k].key);
/* Remove the entry from the pool. */
sdsfree(pool[k].key);
/* Shift all elements on its right to left. */
memmove(pool+k,pool+k+1,
sizeof(pool[0])*(REDIS_EVICTION_POOL_SIZE-k-1));
/* Clear the element on the right which is empty
* since we shifted one position to the left. */
pool[REDIS_EVICTION_POOL_SIZE-1].key = NULL;
pool[REDIS_EVICTION_POOL_SIZE-1].idle = 0;
/* If the key exists, is our pick. Otherwise it is
* a ghost and we need to try the next element. */
if (de) {
bestkey = dictGetKey(de);
break;
} else {
/* Ghost... */
continue;
}
}
}
}
/* volatile-ttl */
// 策略為 volatile-ttl 殉簸，從一集 sample 鍵中選出過期時間距離當前時間最接近的鍵
else if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_TTL) {
for (k = 0; k < server.maxmemory_samples; k++) {
sds thiskey;
long thisval;
de = dictGetRandomKey(dict);
thiskey = dictGetKey(de);
thisval = (long) dictGetVal(de);
/* Expire sooner (minor expire unix timestamp) is better
* candidate for deletion */
if (bestkey == NULL || thisval < bestval) {
bestkey = thiskey;
bestval = thisval;
}
}
}
/* Finally remove the selected key. */
// 刪除被選中的鍵
if (bestkey) {
long long delta;
robj *keyobj = createStringObject(bestkey,sdslen(bestkey));
propagateExpire(db,keyobj);
/* We compute the amount of memory freed by dbDelete() alone.
* It is possible that actually the memory needed to propagate
* the DEL in AOF and replication link is greater than the one
* we are freeing removing the key, but we can't account for
* that otherwise we would never exit the loop.
*
* AOF and Output buffer memory will be freed eventually so
* we only care about memory used by the key space. */
// 計算刪除鍵所釋放的內(nèi)存數(shù)量
delta = (long long) zmalloc_used_memory();
dbDelete(db,keyobj);
delta -= (long long) zmalloc_used_memory();
mem_freed += delta;
// 對淘汰鍵的計數(shù)器增一
server.stat_evictedkeys++;
notifyKeyspaceEvent(REDIS_NOTIFY_EVICTED, "evicted",
keyobj, db->id);
decrRefCount(keyobj);
keys_freed++;
/* When the memory to free starts to be big enough, we may
* start spending so much time here that is impossible to
* deliver data to the slaves fast enough, so we force the
* transmission here inside the loop. */
if (slaves) flushSlavesOutputBuffers();
}
}
if (!keys_freed) return REDIS_ERR; /* nothing to free... */
}
return REDIS_OK;
}
【參考】
[1] 《Redis設(shè)計與實現(xiàn)》
[2] 《Redis源碼日志》
