Redis 內存淘汰策略，從根兒上理解

前言

本文參考源碼版本 redis6.2

Redis 基於內存設計，所有數據存放在內存，隨着時間推移，內存佔用也越來也高 ...

由於內存容量這個物理限制，我們需要在內存使用量達到一定比例後，做一些內存清理工作，以保證有足夠的空間來完成正常的處理。

在 Redis 中，完成這個工作的就是本文的主角 ------- Redis 內存淘汰機制。

• 一定比例：在 redis 中就是 maxmemory 閾值

• 淘汰策略：在 redis 中目前有兩種流行的算法：LRU 與 LFU 算法

如果讓你來設計一款內存淘汰策略，你會考慮哪些方面？

1）首先，從用戶體驗上看：

• 不要影響服務正常使用，實現平滑淘汰

• 用戶透明，用戶不需要做任何額外操作

2）其次，從系統層面來看：

• 何時清理？

• 清理哪些？

• 清理多少？

• 怎樣清理？

• 清理頻次？

帶着這些問題，我們一起來探索下，Redis 是如何考慮並實現的。

一、淘汰策略

淘汰策略也是可以在 redis.config 中指定：

maxmemory-policy ...

截止目前，共有 8 種淘汰策略，如下：

1. 全局淘汰：

1）allkeys-lru：淘汰範圍是所有 keys，淘汰最久未使用的 key

2）allkeys-lfu：淘汰範圍是所有 keys，淘汰使用頻次最少的

3）allkeys-random：淘汰範圍：所有 keys，隨機淘汰 key

2. 淘汰 expire ：

1）volatile-lru：淘汰範圍：所有設置了 expire 時間的 keys，淘汰最久未使用的 key

2）volatile-lfu：淘汰範圍：所有設置了 expire 時間的 keys，淘汰使用頻次最少的 key

3）volatile-random：淘汰範圍：所有設置了 expire 時間的 keys，隨機淘汰 key

4）volatile-ttl：淘汰範圍：所有設置了 expire 時間的 keys，淘汰 ttl 剩餘時間最少的 key

3. 不淘汰：

1）noeviction：不淘汰，意味着達到限制時，將無法存儲

二、淘汰算法

目前有兩種常用的內存淘汰算法，分別致力於從 訪問時間 和 訪問頻次 上解決內存問題。

1. LRU 算法

Least Recently Used，最近未使用淘汰算法，是一種按照訪問時間進行淘汰的算法。

假如只從設計上考慮，我們一般會定義一個隊列來存儲訪問記錄，然後每次從隊列末尾刪除元素即可。

• 隊首新增：訪問記錄不存在，則在隊列尾部新增訪問 key

• 元素位置調整：訪問記錄存在，則調整元素 key 至隊首

• 隊尾刪除：當需要淘汰 key 時，從隊尾開始判斷即可。

但是在 redis 中，內存、CPU 是稀缺物，要儘可能減少內存使用量、CPU 的消耗，因此，在實現上也就更加放鬆。

redis 採用近似 LRU 算法，每次隨機選擇一個樣本集，並從樣本集中挑選最長時間未使用的 key 淘汰。這樣一來就不用維護訪問隊列，而是選擇一個合適的樣本集大小，也能達到近似 LRU 算法效果。

我們來看看官方測試效果：

• 淺灰色代表被淘汰的數據

• 深灰色代表沒有被淘汰的數據

• 綠色代表新增數據

在 redis3.0 之後，當選擇樣本集 maxmemory-samples = 10，其效果基本已經接近 LRU 算法，但是會更消耗 CPU。

redis.config 中的 maxmemory-samples 默認值爲 5，一般情況下應該夠用了。

接着，我們來看看 LRU 算法的工作原理，以及存在哪些問題：

~~~~~A~~~~~A~~~~~A~~~~A~~~~~A~~~~~A~~|
~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~|
~~~~~~~~~~C~~~~~~~~~C~~~~~~~~~C~~~~~~|
~~~~~D~~~~~~~~~~D~~~~~~~~~D~~~~~~~~~D|

其中，~ 字符表示 1 秒，| 表示結束，A 每 5 秒訪問一次，B 每兩秒訪問一次，C、D 每 10 秒訪問一次。

我們先看 A、B、C，由於 B 訪問頻次最高，你會看到 B 幾乎總是處於訪問隊列隊首，C 頻次最低，大概會出現在訪問隊列隊尾。

不同的是 D，和 C 一樣的頻率，目前卻出現在了隊首。

LRU 算法認爲，最近訪問過的 key，再次訪問的概率比較大，而很久沒有訪問的 key 再次訪問的概率比較小（隊尾），因此隊尾可以優先淘汰。

但是，從以上案例，D 的情況也可以看出，會存在一些極端情況。不過，LRU 總的來說，是比較 OK 的。

每一個 key 在 redis 中都是以 redisObject 形式存在，其中 lru 字段便是記錄訪問時間：

#define LRU_BITS 24

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    void *ptr;
} robj;

2. LFU 算法

Least Frequently Used，即 最近最少使用淘汰策略，是一種按照訪問頻次處理的淘汰算法。相對於 LRU 算法，在某些方面效果可能更佳。

LRU 算法有個缺點是，臨時數據可能會取代真正經常使用的數據。比如，短時間內，大量臨時數據湧入 redis，而觸發發生內存淘汰，可能會將那些真正經常使用的數據驅逐。

LFU 是一種按頻次處理的淘汰算法，可以很好解決臨時數據問題。

假如只從設計上考慮 LFU，一般情況下：要記錄每個 key 的使用次數 + 統計窗口：

• int 存儲使用次數：4 字節，基本滿足需求

• 統計窗口：當窗口滑動時，要累加新的次數，同時也要減去過期數據；本質來說，就是要記錄訪問明細，看起來挺繁瑣。

前面說了，redis 內存和 CPU 都是稀缺品，可以猜測下，不會採用上述方案。

redis LFU 也是採用給一個近似算法：

• 計數器：使用次數，僅採用 8 byte 存儲，最大值 255

• 衰減時間：不使用滑動窗口，採用衰減時間，達到一定條件使計數器減小。

對應 redis.config 的配置是：

lfu-log-factor 10
lfu-decay-time 1

計算規則是這樣的：

• 隨機數 R，取數範圍：0 ～ 1

• 概率參數 P = 1 / (old_value * lfu_log_factor + 1)，這裏 old_value 就是計數器的值。

• 計數器累加：條件是 R < P

從這個公式可以看出，影響累加器的有兩個變量：

• old_value：當前計數值，隨着計數值的累加，參數 P 就會越小，也就是說越往後累計越困難，這就確保了計數器不會快速膨脹至 255。

• lfu_log_factor：在 redis.conf 配置的參數，用於控制累加速度。

我來來看看官方給出的參數 lfu_log_factor，控制累加速度效果：

+--------+------------+------------+------------+------------+------------+
| 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        |
+--------+------------+------------+------------+------------+------------+

可以看到，隨着 lfu_log_factor 值的變大，計數器累加的速度越來越慢 ...

redis 爲了節省內存空間，LFU 的記錄仍然複用了 24 bit 的 LRU 字段：

           16 bits      8 bits
      +----------------+--------+
      + Last decr time | LOG_C  |
      +----------------+--------+

• 高 16 bits 用來記錄時間

• 低 8 bits 用來記錄累加數值

計數器累加相關邏輯：

  uint8_t LFULogIncr(uint8_t counter) {
      if (counter == 255) return 255;
      double r = (double)rand()/RAND_MAX;
      double baseval = counter - LFU_INIT_VAL;
      if (baseval < 0) baseval = 0;
      double p = 1.0/(baseval*server.lfu_log_factor+1);
      if (r < p) counter++;
      return counter;
  }

三、淘汰

前面我們已經討論瞭如何淘汰策略以及淘汰算法，這部分我們將討論真正的淘汰過程：

• 何時清理？

• 清理哪些？

• 清理多少？

• 怎樣清理？

我畫了張淘汰的整體流程圖，你可以參考下：

1. 何時清理？

這也是一種惰性思想，一個用戶請求過來了，順便檢查下內存使用情況，當 redis 內存使用量達到預定閾值 maxmemory 時，便會觸發淘汰機制。

• 每一條客戶端的請求處理之後，看是否有必要進行內存淘汰。如果需要，走淘汰邏輯。

淘汰時也分兩種情況：

• 淘汰數據少：這種很理想，一次性可以搞定。

• 淘汰數據多：如果數據過多，爲避免長時間阻塞，提供了一些可配置的限制，如果達到限制條件還沒有清理完成，暫時放入到時間事件中，等待下一輪清理。

2. 清理哪些？

這個你基本也清楚了，哪些數據需要被清理，主要是看你選擇的淘汰策略，以及淘汰算法。

從淘汰策略來看：

• allkeys- ... 策略，就是全局範圍內淘汰。

• volatile-... 則是在設置了過期 key 範圍裏淘汰。

從淘汰算法來看：

• 如果選擇 LRU，一般就是先淘汰訪問記錄末端的數據

• 而選擇 LFU 則淘汰最近最少訪問的數據

3. 清理多少？

待清理的大小 = used - maxmemory，即當前使用內存大小 - 設定的閾值。

一次性沒處理完（可以設置一定時長限制），可以扔到時間事件中，週期性的處理，直到達到目標 ...

4. 怎樣清理？

這就是兩種淘汰算法的工作了。LRU 和 LFU 在 redis 中都是近似算法，本質是爲了減少內存和 CPU 的消耗。

• 隨機選出一個樣本集

• 從樣本集選出一個最合適淘汰的 key，這裏通過 LRU 或者 LFU 算法選擇

• 清理選擇的 key，如果有必要可以使用惰性刪除

來源： https://juejin.cn/post/7142851076293656583

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/jFzAdV-FKl-HtYYAsMWg1g