走近源碼：Redis如何清除過期key

走近源碼：Redis如何清除過期key

“叮……”，美好的周六就這麼被一陣釘釘消息吵醒了。

業務組的同學告訴我說很多使用者的帳号今天被強制下線。我們的帳号系統正常的邏輯是使用者登入一次後，token的有效期可以維持一天的時間。現在的問題是使用者大概每10分鐘左右就需要重新登入一次。這種情況一般有兩種原因：1、token生成時出問題。2、驗證token時出現問題。

通過檢查日志，我發現是驗證token時，Redis中已經沒有對應的token了。并且确定了生成新的token時，set到Redis中的有效期是正确的，那麼就基本可以确定是Redis的問題了。

于是又去檢查了Redis的監控，發現在那段時間Redis由于記憶體占用過高強制清理了幾次key。但從日志上來看，這段時間并沒有出現流量暴漲的情況，而且Redis中key的數量也沒有顯著增加。那是什麼原因導緻Redis記憶體占用過高呢？确定了Redis記憶體升高不是我們造成的之後，我們又聯系了業務組的同學協助他們，他們表示最近确實有上線，并且新上線的功能有使用到Redis。但我仍然感覺很奇怪，為什麼Redis中的key沒有增多，并且沒看到有其他業務的key。經過一番詢問，才了解到，業務組同學使用的是這個Redis的db1，而我用的（和剛查的）是db0。這裡确實是我在排查問題時出現了疏忽。

那麼Redis的不同db之間會互相影響嗎？通常情況下，我們使用不同的db進行資料隔離，這沒問題。但Redis進行清理時，并不是隻清理資料量占用最大的那個db，而是會對所有的db進行清理。在這之前我并不是很了解這方面知識，這裡也隻是根據現象進行的猜測。

好奇心驅使我來驗證一下這個想法。于是我決定直接來看Redis的源碼。清理key相關的代碼在evict.c檔案中。

Redis中會儲存一個“過期key池”，這個池子中存放了一些可能會被清理的key。其中儲存的資料結構如下：

struct evictionPoolEntry {

unsigned long long idle;    /* Object idle time (inverse frequency for LFU) */
sds key;                    /* Key name. */
sds cached;                 /* Cached SDS object for key name. */
int dbid;                   /* Key DB number. */           

};

其中idle是對象空閑時間，在Reids中，key的過期算法有兩種：一種是近似LRU，一種是LFU。預設使用的是近似LRU。

近似LRU

在解釋近似LRU之前，先來簡單了解一下LRU。當Redis的記憶體占用超過我們設定的maxmemory時，會把長時間沒有使用的key清理掉。按照LRU算法，我們需要對所有key（也可以設定成隻淘汰有過期時間的key）按照空閑時間進行排序，然後淘汰掉空閑時間最大的那部分資料，使得Redis的記憶體占用降到一個合理的值。

LRU算法的缺點是，我們需要維護一個全部（或隻有過期時間）key的清單，還要按照最近使用時間排序。這會消耗大量記憶體，并且每次使用key時更新排序也會占用額外的CPU資源。對于Redis這樣對性能要求很高的系統來說是不被允許的。

是以，Redis采用了一種近似LRU的算法。當Redis接收到新的寫入指令，而記憶體又不夠時，就會觸發近似LRU算法來強制清理一些key。具體清理的步驟是，Redis會對key進行采樣，通常是取5個，然後會把過期的key放到我們上面說的“過期池”中，過期池中的key是按照空閑時間來排序的，Redis會優先清理掉空閑時間最長的key，直到記憶體小于maxmemory。

近似LRU算法的清理效果圖如圖（圖檔來自Redis官方文檔）

這麼說可能不夠清楚，我們直接上代碼。

源碼分析

上圖展示了代碼中近似LRU算法的主要邏輯調用路徑。

其中主要邏輯是在freeMemoryIfNeeded函數中

首先調用getMaxmemoryState函數判斷目前記憶體的狀态

int getMaxmemoryState(size_t total, size_t logical, size_t tofree, float level) {

size_t mem_reported, mem_used, mem_tofree;

mem_reported = zmalloc_used_memory();
if (total) *total = mem_reported;

int return_ok_asap = !server.maxmemory || mem_reported <= server.maxmemory;
if (return_ok_asap && !level) return C_OK;

mem_used = mem_reported;
size_t overhead = freeMemoryGetNotCountedMemory();
mem_used = (mem_used > overhead) ? mem_used-overhead : 0;

if (level) {
    if (!server.maxmemory) {
        *level = 0;
    } else {
        *level = (float)mem_used / (float)server.maxmemory;
    }
}

if (return_ok_asap) return C_OK;

if (mem_used <= server.maxmemory) return C_OK;

mem_tofree = mem_used - server.maxmemory;

if (logical) *logical = mem_used;
if (tofree) *tofree = mem_tofree;

return C_ERR;           

}

如果使用記憶體低于maxmemory的話，就傳回C_OK，否則傳回C_ERR。另外，這個函數還通過傳遞指針型的參數來傳回一些額外的資訊。

total：已使用的位元組總數，無論是C_OK還是C_ERR都有效。

logical：已使用的記憶體減去slave或AOF緩沖區後的大小，隻有傳回C_ERR時有效。

tofree：需要釋放的記憶體大小，隻有傳回C_ERR時有效。

level：已使用記憶體的比例，通常是0到1之間，當超出記憶體限制時，就大于1。無論是C_OK還是C_ERR都有效。

判斷完記憶體狀态以後，如果記憶體沒有超過使用限制就會直接傳回，否則就繼續向下執行。此時我們已經知道需要釋放多少記憶體空間了，下面就開始進行釋放記憶體的操作了。每次釋放記憶體都會記錄釋放記憶體的大小，直到釋放的記憶體不小于tofree。

首先根據maxmemory_policy進行判斷，對于不同的清除政策有不同的實作方法，我們來看LRU的具體實作。

for (i = 0; i < server.dbnum; i++) {

db = server.db+i;

dict = (server.maxmemory_policy & MAXMEMORY_FLAG_ALLKEYS) ?

db->dict : db->expires;           

if ((keys = dictSize(dict)) != 0) {

evictionPoolPopulate(i, dict, db->dict, pool);
total_keys += keys;           

首先是填充“過期池”，這裡周遊了每一個db（驗證了我最開始的想法），調用evictionPoolPopulate函數進行填充。

void evictionPoolPopulate(int dbid, dict sampledict, dict keydict, struct evictionPoolEntry *pool) {

int j, k, count;
dictEntry *samples[server.maxmemory_samples];

count = dictGetSomeKeys(sampledict,samples,server.maxmemory_samples);
for (j = 0; j < count; j++) {
    unsigned long long idle;
    sds key;
    robj *o;
    dictEntry *de;

    de = samples[j];
    key = dictGetKey(de);
            /* some code */
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LRU) {
        idle = estimateObjectIdleTime(o);
    }

    /* some code */
    k = 0;
    while (k < EVPOOL_SIZE &&
           pool[k].key &&
           pool[k].idle < idle) k++;
    if (k == 0 && pool[EVPOOL_SIZE-1].key != NULL) {
        continue;
    } else if (k < EVPOOL_SIZE && pool[k].key == NULL) {
    } else {
        if (pool[EVPOOL_SIZE-1].key == NULL) {
            sds cached = pool[EVPOOL_SIZE-1].cached;
            memmove(pool+k+1,pool+k,
                sizeof(pool[0])*(EVPOOL_SIZE-k-1));
            pool[k].cached = cached;
        } else {
            k--;
            sds cached = pool[0].cached; /* Save SDS before overwriting. */
            if (pool[0].key != pool[0].cached) sdsfree(pool[0].key);
            memmove(pool,pool+1,sizeof(pool[0])*k);
            pool[k].cached = cached;
        }
    }
    /* some code */
}           

由于篇幅原因，我截取了部分代碼，通過這段代碼我們可以看到，Redis首先是采樣了一部分key，這裡采樣數量maxmemory_samples通常是5，我們也可以自己設定，采樣數量越大，結果就越接近LRU算法的結果，帶來的影響是性能随之變差。

采樣之後我們需要獲得每個key的空閑時間，然後将其填充到“過期池”中的指定位置。這裡“過期池”是按照空閑時間從小到大排序的，也就是說，idle大大key排在最右邊。

填充完“過期池”之後，會從後向前擷取到最适合清理的key。

/ Go backward from best to worst element to evict. /

for (k = EVPOOL_SIZE-1; k >= 0; k--) {

if (pool[k].key == NULL) continue;

bestdbid = pool[k].dbid;

if (server.maxmemory_policy & MAXMEMORY_FLAG_ALLKEYS) {

de = dictFind(server.db[pool[k].dbid].dict,
              pool[k].key);           

} else {

de = dictFind(server.db[pool[k].dbid].expires,
              pool[k].key);           

/ some code /

if (de) {

bestkey = dictGetKey(de);
break;           

找到需要删除的key後，就需要根據設定清理政策進行同步/異步清理。

if (server.lazyfree_lazy_eviction)

dbAsyncDelete(db,keyobj);

else

dbSyncDelete(db,keyobj)

最後記下本次清理的空間大小，用來在循環條件判斷是否要繼續清理。

delta -= (long long) zmalloc_used_memory();

mem_freed += delta;

清理政策

最後我們來看一下Redis支援的幾種清理政策

noeviction：不會繼續處理寫請求（DEL可以繼續處理）。

allkeys-lru：對所有key的近似LRU

volatile-lru：使用近似LRU算法淘汰設定了過期時間的key

allkeys-random：從所有key中随機淘汰一些key

volatile-random：對所有設定了過期時間的key随機淘汰

volatile-ttl：淘汰有效期最短的一部分key

Redis4.0開始支援了LFU政策，和LRU類似，它分為兩種：

volatile-lfu：使用LFU算法淘汰設定了過期時間的key

allkeys-lfu：從全部key中進行淘汰，使用LFU

寫在最後

現在我知道了Redis在記憶體達到上限時做了哪些事了。以後出問題時也就不會隻檢查自己的db了。

關于這次事故的後續處理，我首先是讓業務同學復原了代碼，然後讓他們使用一個單獨的Redis，這樣業務再出現類似問題就不會影響到我們的帳号服務了，整體的影響範圍也會變得更加可控。

原文位址

https://www.cnblogs.com/Jackeyzhe/p/12616624.html