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.
*/
//計算占用內(nèi)存大小時，并不計算slave output buffer和aof buffer，因此maxmemory應(yīng)該比實際內(nèi)存小，為這兩個buffer留足空間。
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.appendonly) {
mem_used -= sdslen(server.aofbuf);
mem_used -= sdslen(server.bgrewritebuf);
}
//判斷已經(jīng)使用內(nèi)存是否超過最大使用內(nèi)存，如果沒有超過就返回REDIS_OK，
/* Check if we are over the memory limit. */
if (mem_used <= server.maxmemory) return REDIS_OK;
//當(dāng)超過了最大使用內(nèi)存時，就要判斷此時redis到底采用的是那種內(nèi)存釋放策略，根據(jù)不同的策略，采取不同的手段。
//（1）首先判斷是否是為no-enviction策略，如果是，則返回REDIS_ERR,然后redis就不再接受任何寫命令了。
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. */
mem_tofree = mem_used - server.maxmemory;
mem_freed = 0;
//（2）接下來就判斷淘汰策略是基于所有的鍵還是只是基于設(shè)置了過期時間的鍵，如果是針對所有的鍵，就從server.db[j].dict中取數(shù)據(jù)，如果是針對設(shè)置了過期時間的鍵，就從server.db[j].expires中取數(shù)據(jù)。
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;
struct dictEntry *de;
redisDb *db = server.db+j;
dict *dict;
//（3）然后判斷是不是random策略，包括volatile-random 和allkeys-random，這兩種策略是最簡單的，就是在上面的數(shù)據(jù)集中隨便去一個鍵，然后刪掉。
if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM)
{
dict = server.db[j].dict;
} else {
dict = server.db[j].expires;
}
if (dictSize(dict) == 0) continue;
//接著又判斷allkeys-random還是volatile-ttl策略
/* 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 = dictGetEntryKey(de);
}//如果是random delete,則從dict中隨機選一個key
//然后就是判斷是lru策略還是ttl策略，如果是lru策略就采用lru近似算法
/* volatile-lru and allkeys-lru policy */
else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
{
for (k = 0; k < server.maxmemory_samples; k++) {
sds thiskey;
long thisval;
robj *o;
de = dictGetRandomKey(dict);
thiskey = dictGetEntryKey(de);
/* When policy is volatile-lru we need an additonal lookup
* to locate the real key, as dict is set to db->expires. */
if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
de = dictFind(db->dict, thiskey); //因為dict->expires維護的數(shù)據(jù)結(jié)構(gòu)里并沒有記錄該key的最后訪問時間
o = dictGetEntryVal(de);
thisval = estimateObjectIdleTime(o);
/* Higher idle time is better candidate for deletion */
if (bestkey == NULL || thisval > bestval) {
bestkey = thiskey;
bestval = thisval;
}
}//為了減少運算量,redis的lru算法和expire淘汰算法一樣，都是非最優(yōu)解，lru算法是在相應(yīng)的dict中，選擇maxmemory_samples(默認(rèn)設(shè)置是3)份key，挑選其中l(wèi)ru的，進行淘汰
}
//如果是ttl策略。ttl策略很簡單，就是取maxmemory_samples個鍵，然后比較他們的過期時間，然后從這些鍵中找到最快過期的那個鍵，就是我們將要刪除的鍵。
/* volatile-ttl */
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 = dictGetEntryKey(de);
thisval = (long) dictGetEntryVal(de);
/* Expire sooner (minor expire unix timestamp) is better
* candidate for deletion */
if (bestkey == NULL || thisval < bestval) {
bestkey = thiskey;
bestval = thisval;
}
}//注意ttl實現(xiàn)和上邊一樣，都是挑選出maxmemory_samples份進行挑選
}
//根據(jù)不同的策略，我們找到了將要刪除的鍵，下面就是將他們刪除的時候了，刪除選定的鍵值對
/* Finally remove the selected key. */
if (bestkey) {
long long delta;
robj *keyobj = createStringObject(bestkey,sdslen(bestkey));
// 發(fā)布數(shù)據(jù)更新消息，主要是AOF 持久化和從機
propagateExpire(db,keyobj); //將del命令擴散給slaves
// 注意， propagateExpire() 可能會導(dǎo)致內(nèi)存的分配，
// propagateExpire() 提前執(zhí)行就是因為redis 只計算
// dbDelete() 釋放的內(nèi)存大小。倘若同時計算dbDelete()
// 釋放的內(nèi)存和propagateExpire() 分配空間的大小，與此
// 同時假設(shè)分配空間大于釋放空間，就有可能永遠退不出這個循環(huán)。
// 下面的代碼會同時計算dbDelete() 釋放的內(nèi)存和propagateExpire() 分配空間的大小
/* 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. */
// 只計算dbDelete() 釋放內(nèi)存的大小
delta = (long long) zmalloc_used_memory();
dbDelete(db,keyobj);
delta -= (long long) zmalloc_used_memory();
mem_freed += delta;
server.stat_evictedkeys++;
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. */
// 將從機回復(fù)空間中的數(shù)據(jù)及時發(fā)送給從機
if (slaves) flushSlavesOutputBuffers();
}
}//在所有的db中遍歷一遍，然后判斷刪除的key釋放的空間是否足夠，未能釋放空間，且此時redis 使用的內(nèi)存大小依舊超額，失敗返回
if (!keys_freed) return REDIS_ERR; /* nothing to free... */
}
return REDIS_OK;
}
//不同的策略，操作的數(shù)據(jù)集不同
if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM)
{
dict = server.db[j].dict;
} else {//操作的是設(shè)置了過期時間的key集
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算法
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) {
//選擇隨機樣式，并從樣本中作用LRU算法選擇需要淘汰的數(shù)據(jù)
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);
sdsfree(pool[k].key);
//將pool+k+1之后的元素向前平移一個單位
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;
//選擇了需要淘汰的數(shù)據(jù)
if (de) {
bestkey = dictGetKey(de);
break;
} else {
/* Ghost... */
continue;
}
}
}
}
