首頁私信 Github 博客園管理

Loading...

redis-過期策略

redis內存淘汰策略

作者：w08e

在線博客：http://www.rzrgm.cn/w08e

??

面試官：你們公司redi設置的什么淘汰策略？

答題思路

從淘汰范圍來說可以分為不淘汰任何數據、只從設置了到期時間的鍵中淘汰和從所有鍵中淘汰三類。而從淘汰算法來分，又主要分為 Random（隨機），LRU（最近最少使用），以及 LFU（最近最不常使用）三種。

回答話術

內存總是有限的，因此當 Redis 內存超出最大內存時，就需要根據一定的策略去主動的淘汰一些 Key，來騰出內存，這就是內存淘汰策略。我們可以在配置文件中通過 maxmemory-policy 配置指定策略。

與到期刪除策略不同，內存淘汰策略主要目的則是為了防止運行時內存超過最大內存，所以盡管最終目的都是清理內存中的一些 Key，但是它們的應用場景和觸發時機是不同的。

算上在 4.0 添加的兩種基于 LFU 算法的策略， Redis 一共提供了八種策略供我們選擇：

noeviction，不淘汰任何 key，直接報錯。它是默認策略。
volatile-random：從所有設置了到期時間的 Key 中，隨機淘汰一個 Key。
volatile-lru：從所有設置了到期時間的 Key 中，淘汰最近最少使用的 Key。
volatile-lfu：從所有設置了到期時間的 Key 中，淘汰最近最不常用使用的 Key（4.0 新增）。
volatile-ttl：從所有設置了到期時間的 Key 中，優先淘汰最早過期的 Key。
allkeys-random：從所有 Key 中，隨機淘汰一個鍵（4.0 新增）。
allkeys-lru：從所有 Key 中，淘汰最近最少使用的 Key。
allkeys-lfu：從所有 Key 中，淘汰最近最不常用使用的鍵。

從淘汰范圍來說可以分為不淘汰任何數據、只從設置了到期時間的鍵中淘汰和從所有鍵中淘汰三類。而從淘汰算法來分，又主要分為 Random（隨機），LRU（最近最少使用），以及 LFU（最近最不常使用）三種。

其中，關于 LRU 算法，它是一種非常常見的緩存淘汰算法。我們可以簡單理解為 Redis 會在每次訪問 Key 的時候記錄訪問時間，當淘汰時，優先淘汰最后一次訪問距離現在最早的 Key。

而對于 LFU 算法，我們可以理解為 Redis 會在訪問 Key 時，根據兩次訪問時間的間隔計算并累加訪問頻率指標，當淘汰時，優先淘汰訪問頻率指標最低的 key。相比 LRU 算法，它避免了低頻率的大批量查詢造成的緩存污染問題。

順帶一提，只要是有類似緩存機制的應用或多或少都會面對這種問題，比如老生常談的 MySQL 連表查詢，在數據量大的時候也會造成緩存污染。

此外，當選擇 LFU 算法時，如果數據量比較大，為了避免因為抽樣數量過小導致冷熱 Key 之間因為時間衰減造成的權重差異難以體現，最好將抽樣大小設置的大一些，減小熱數據被誤傷的可能性。

問題詳解

1. 淘汰策略

按 Key 的淘汰范圍來分，我們可以把這些策略分為三類

1）不淘汰任何數據

也就是noeviction，它是默認的策略。

2）只從設置的了到期時間的 Key 中淘汰

volatile-random：從所有設置了到期時間的 Key 中，隨機淘汰一個 Key。
volatile-lru：從所有設置了到期時間的 Key 中，淘汰最近最少使用的 Key。
volatile-lfu：從所有設置了到期時間的 Key 中，淘汰最近最不常用使用的 Key，4.0 版本新增。
volatile-ttl：從所有設置了到期時間的 Key 中，優先淘汰最早過期的 Key。

3）從所有的 Key 中進行淘汰

allkeys-rando：從所有 Key 中，隨機淘汰一個鍵，4.0 版本新增。
allkeys-lru：從所有 Key 中，淘汰最近最少使用的 Key。
allkeys-lfu：從所有 Key 中，淘汰最近最不常用使用的鍵。

2. 淘汰過程

每次當 Redis 執行命令時，若設置了最大內存大小 maxmemory，并設置了淘汰策略式，則會嘗試進行一次 Key 淘汰；
Redis 首先會評估已使用內存（這里不包含主從復制使用的兩個緩沖區占用的內存）是否大于 maxmemory，如果沒有則直接返回，否則將計算當前需要釋放多少內存，隨后開始根據策略淘汰符合條件的 Key；當開始進行淘汰時，將會依次對每個數據庫進行抽樣，抽樣的數據范圍由策略決定，而樣本數量則由 maxmemory-samples配置決定；
完成抽樣后，Redis 會嘗試將樣本放入提前初始化好 EvictionPoolLRU 數組中，它相當于一個臨時緩沖區，當數組填滿以后即將里面全部的 Key 進行刪除。
若一次刪除后內存仍然不足，則再次重復上一步驟，將樣本中的剩余 Key 再次填入數組中進行刪除，直到釋放了足夠的內存，或者本次抽樣的所有 Key 都被刪除完畢（如果此時內存還是不足，那么就重新執行一次淘汰流程）。

從到期字典中抽樣

在抽樣這一步，涉及到從字典中隨機抽樣這個過程，由于哈希表的 Key 是散列分布的，因此會有很多桶都是空的，純隨機效率可能會很低。因此，Redis 采用了一個特別的做法，那就是先連續遍歷數個桶，如果都是空的，再隨機調到另一個位置，再連續遍歷幾個桶……如此循環，直到結束抽樣。

你可以參照源碼理解這個過程：

unsigned int dictGetSomeKeys(dict *d, dictEntry **des, unsigned int count) {
    unsigned long j; /* internal hash table id, 0 or 1. */
    unsigned long tables; /* 1 or 2 tables? */
    unsigned long stored = 0, maxsizemask;
    unsigned long maxsteps;

    if (dictSize(d) < count) count = dictSize(d);
    maxsteps = count*10;

    // 如果字典正在遷移，則協助遷移
    for (j = 0; j < count; j++) {
        if (dictIsRehashing(d))
            _dictRehashStep(d);
        else
            break;
    }

    tables = dictIsRehashing(d) ? 2 : 1;
    maxsizemask = d->ht[0].sizemask;
    if (tables > 1 && maxsizemask < d->ht[1].sizemask)
        maxsizemask = d->ht[1].sizemask;

    unsigned long i = random() & maxsizemask;
    unsigned long emptylen = 0;

    // 當已經采集到足夠的樣本，或者重試已達上限則結束采樣
    while(stored < count && maxsteps--) {
        for (j = 0; j < tables; j++) {
            if (tables == 2 && j == 0 && i < (unsigned long) d->rehashidx) {
                if (i >= d->ht[1].size)
                    i = d->rehashidx;
                else
                    continue;
            }

            // 如果一個庫的到期字典已經處理完畢，則處理下一個庫
            if (i >= d->ht[j].size) continue;
            dictEntry *he = d->ht[j].table[i];

            // 連續遍歷多個桶，如果多個桶都是空的，那么隨機跳到另一個位置，然后再重復此步驟           
            if (he == NULL) {
                emptylen++;
                if (emptylen >= 5 && emptylen > count) {
                    i = random() & maxsizemask;
                    emptylen = 0;
                }
            } else {
                emptylen = 0;
                while (he) {
                    *des = he;
                    des++;
                    he = he->next;
                    stored++;
                    if (stored == count) return stored;
                }
            }
        }

        // 查找下一個桶
        i = (i+1) & maxsizemask;
    }
    return stored;
}

3. LRU 的實現

LRU 的全稱為 Least Recently Used，也就是最近最少使用。一般來說，LRU 會從一批 Key 中淘汰上次訪問時間最早的 key。

它是一種非常常見的緩存回收算法，在諸如 Guava Cache、Caffeine等緩存庫中都提供了類似的實現。我們自己也可以基于 JDK 的 LinkedHashMap 實現支持 LRU 算法的緩存功能。

3.1. 近似 LRU

傳統的 LRU 算法實現通常會維護一個鏈表，當訪問過某個節點后就將該節點移至鏈表頭部。如此反復后，鏈表的節點就會按最近一次訪問時間排序。當緩存數量到達上限后，我們直接移除尾節點，即可移除最近最少訪問的緩存。

不過，對于 Redis 來說，如果每個 Key 添加的時候都需要額外的維護并操作這樣一條鏈表，要額外付出的代價顯然是不可接受的，因此 Redis 中的 LRU 是近似 LRU（NearlyLRU）。

當每次訪問 Key 時，Redis 會在結構體中記錄本次訪問時間，而當需要淘汰 Key 時，將會從全部數據中進行抽樣，然后再移除樣本中上次訪問時間最早的 key。

它的特點是：

僅當需要時再抽樣，因而不需要維護全量數據組成的鏈表，這避免了額外內存消耗。
訪問時僅在結構體上記錄操作時間，而不需要操作鏈表節點，這避免了額外的性能消耗。

當然，有利就有弊，這種實現方式也決定 Redis 的 LRU 是并不是百分百準確的，被淘汰的 Key 未必真的就是所有 Key 中最后一次訪問時間最早的。

3.2. 抽樣大小

根據上述的內容，我們不難理解，當抽樣的數量越大，LRU 淘汰 Key 就越準確，相對的開銷也更大。因此，Redis 允許我們通過 maxmemory-samples 配置采樣數量（默認為 5），從而在性能和精度上取得平衡。

3.3. 緩存污染

LRU 有個最大問題，就是它只認最近一次訪問時間。而如果出現系統偶爾需要一次性讀取大量數據的時候，會大規模更新 Key 的最近訪問時間，從而導致真正需要被頻繁訪問的 Key 因為最近一次訪問時間更早而被直接淘汰。這種情況被稱為緩存污染。為此，我們需要使用 LFU 算法來解決。

具體可直接參見：vivo LRU 與 LFU 算法實現 sourl.cn/4yZ6e2

4. LFU 的實現

LFU 全稱為 Least Frequently Used ，也就是最近最不常用。它的特點如下：

同樣是基于抽樣實現的近似算法，maxmemory-samples 對其同樣有效。
比較的不是最后一次訪問時間，而是數據的訪問頻率。當淘汰的時候，優先淘汰范圍頻率最低 Key。

它的實現與 LRU 基本一致，但是在計數部分則有所改進。

4.1. 概率計數器

在 Redis 用來存儲數據的結構體 redisObj 中，有一個 24 位的 lru數值字段：

當使用 LRU 算法時，它用于記錄最后一次訪問時間的時間戳。
當使用 LFU 算法時，它被分為兩部分，高 16 位關于記錄最近一次訪問時間（Last Decrement Time），而低 8 位作為記錄訪問頻率計數器（Logistic Counter）。

LFU 的核心就在于低 8 位表示的訪問頻率計數器（下面我們簡稱為 counter），是一個介于 0 ~ 255 的特殊數值，它會每次訪問 Key 時，基于時間衰減和概率遞增機制動態改變。

這種基于概率，使用極小內存對大量事件進行計數的計數器被稱為莫里斯計數器，它是一種概率計數法的實現。

4.2. 時間衰減

每當訪問 Key 時，根據當前實際與該 Key 的最后一次訪問時間的時間差對 counter 進行衰減。

衰減值取決于 lfu_decay_time 配置，該配置表示一個衰減周期。我們可以簡單的認為，每當時間間隔滿足一個衰減周期時，就會對 counter 減一。

比如，我們設置 lfu_decay_time為 1 分鐘，那么如果 Key 最后一次訪問距離現在已有 3 分 30 秒，那么 counter 就需要減 3。

4.3. 概率遞增

在完成衰減后，Redis 將根據 lfu_log_factor 配置對應概率值對 counter 進行遞增。

這里直接放上源碼：

/* Logarithmically increment a counter. The greater is the current counter value
 * the less likely is that it gets really implemented. Saturate it at 255. */
uint8_t LFULogIncr(uint8_t counter) {
    // 若已達最大值 255，直接返回
    if (counter == 255) return 255;
    // 獲取一個介于 0 到 1 之間的隨機值
    double r = (double)rand()/RAND_MAX;
    // 根據當前 counter 減去初始值得到 baseval
    double baseval = counter - LFU_INIT_VAL; 
    if (baseval < 0) baseval = 0;
    // 使用 baseval*server.lfu_log_factor+1 得到一個概率值 p
    double p = 1.0/(baseval*server.lfu_log_factor+1);
    // 當 r < p 時，遞增 counter
    if (r < p) counter++;
    return counter;
}

簡而言之，直接從代碼上理解，我們可以認為 counter和 lfu_log_factor 越大，則遞增的概率越小：

當然，實際上也要考慮到訪問次數對其的影響，Redis 官方給出了相關數據：

當 lfu_log_factor 設置的越大，遞增的越慢

具體可直接參見：vivo LRU 與 LFU 算法實現 sourl.cn/4yZ6e2

4.4. 計數器的初始值

為了防止新的 Key 由于 counter 為 0 導致直接被淘汰，Redis 會默認將 counter設置為 5。

4.5. 抽樣大小的選擇

值得注意的是，當數據量比較大的時候，如果抽樣大小設置的過小，因為一次抽樣的樣本數量有限，冷熱數據因為時間衰減導致的權重差異將會變得不明顯，此時 LFU 算法的優勢就難以體現，即使的相對較熱的數據也有可能被頻繁“誤傷”。

所以，如果你選擇了 LFU 算法作為淘汰策略，并且同時又具備比較大的數據量，那么不妨將抽樣大小也設置的大一些。

5. 如何選擇

軟件工程沒有銀彈，我們不可能指望存在一個能完美適用于所有場景的內存淘汰策略。在實際場景中，我們需要結合業務特點、數據量大小、數據的冷熱……等多個維度來選擇合適的淘汰策略。

簡單的來說，如果你的業務數據的訪問比較平均，不存在明顯的冷熱區別，那么 LRU 可以滿足一般的使用需求。如果你的業務具備很強的時效性，而且是存在大促商品這種明顯的熱點數據，那么推薦你使用 LFU。

當然，思路要打開，調整淘汰策略只是優化方案的一種，條件允許的話，在特定情況下直接增加內存、將單機改為集群或者緩存預熱同樣可以帶來顯著的收益。

posted @ 2024-08-27 17:11 早點下班回家吃飯叻閱讀(83) 評論(0) 收藏舉報

刷新頁面返回頂部

← → ↓ ↑

小王不會寫代碼