Redis的LRU緩存淘汰算法怎么實現

157次閱讀

共計 5312 個字符，預計需要花費 14 分鐘才能閱讀完成。

本文丸趣 TV 小編為大家詳細介紹“Redis 的 LRU 緩存淘汰算法怎么實現”，內容詳細，步驟清晰，細節處理妥當，希望這篇“Redis 的 LRU 緩存淘汰算法怎么實現”文章能幫助大家解決疑惑，下面跟著丸趣 TV 小編的思路慢慢深入，一起來學習新知識吧。

1 標準 LRU 的實現原理

LRU，最近最少使用（Least Recently Used，LRU），經典緩存算法。

LRU 會使用一個鏈表維護緩存中每個數據的訪問情況，并根據數據的實時訪問，調整數據在鏈表中的位置，然后通過數據在鏈表中的位置，表示數據是最近剛訪問的，還是已有段時間未訪問。

LRU 會把鏈頭、尾分別設為 MRU 端和 LRU 端：

MRU，Most Recently Used 縮寫，表示此處數據剛被訪問

LRU 端，此處數據最近最少被訪問的數據

LRU 可分成如下情況：

case1：當有新數據插入，LRU 會把該數據插入到鏈首，同時把原來鏈表頭部的數據及其之后的數據，都向尾部移動一位

case2：當有數據剛被訪問一次后，LRU 會把該數據從它在鏈表中當前位置，移動到鏈首。把從鏈表頭部到它當前位置的其他數據，都向尾部移動一位

case3：當鏈表長度無法再容納更多數據，再有新數據插入，LRU 去除鏈表尾部的數據，這也相當于將數據從緩存中淘汰掉

case2 圖解：鏈表長度為 5，從鏈表頭部到尾部保存的數據分別是 5，33，9，10，8。假設數據 9 被訪問一次，則 9 就會被移動到鏈表頭部，同時，數據 5 和 33 都要向鏈表尾部移動一位。

所以若嚴格按 LRU 實現，假設 Redis 保存的數據較多，還要在代碼中實現：

為 Redis 使用最大內存時，可容納的所有數據維護一個鏈表

需額外內存空間來保存鏈表

每當有新數據插入或現有數據被再次訪問，需執行多次鏈表操作

在訪問數據的過程中，讓 Redis 受到數據移動和鏈表操作的開銷影響

最終導致降低 Redis 訪問性能。

所以，無論是為節省內存 or 保持 Redis 高性能，Redis 并未嚴格按 LRU 基本原理實現，而是提供了一個近似 LRU 算法實現。

2 Redis 的近似 LRU 算法實現

Redis 的內存淘汰機制是如何啟用近似 LRU 算法的？redis.conf 中的如下配置參數：

maxmemory，設定 Redis server 可使用的最大內存容量，一旦 server 使用實際內存量超出該閾值，server 會根據 maxmemory-policy 配置策略，執行內存淘汰操作

maxmemory-policy，設定 Redis server 內存淘汰策略，包括近似 LRU、LFU、按 TTL 值淘汰和隨機淘汰等

所以，一旦設定 maxmemory 選項，且將 maxmemory-policy 配為 allkeys-lru 或 volatile-lru，近似 LRU 就被啟用。allkeys-lru 和 volatile-lru 都會使用近似 LRU 淘汰數據，區別在于：

allkeys-lru 是在所有的 KV 對中篩選將被淘汰的數據

volatile-lru 在設置了 TTL 的 KV 對中篩選將被淘汰數據

Redis 如何實現近似 LRU 算法的呢？

全局 LRU 時鐘值的計算

如何計算全局 LRU 時鐘值的，以用來判斷數據訪問的時效性

鍵值對 LRU 時鐘值的初始化與更新

哪些函數中對每個鍵值對對應的 LRU 時鐘值，進行初始化與更新

近似 LRU 算法的實際執行

如何執行近似 LRU 算法，即何時觸發數據淘汰，以及實際淘汰的機制實現

2.1 全局 LRU 時鐘值的計算

近似 LRU 算法仍需區分不同數據的訪問時效性，即 Redis 需知道數據的最近一次訪問時間。因此，有了 LRU 時鐘：記錄數據每次訪問的時間戳。

Redis 對每個 KV 對中的 V，會使用個 redisObject 結構體保存指向 V 的指針。那 redisObject 除記錄值的指針，還會使用 24 bits 保存 LRU 時鐘信息，對應的是 lru 成員變量。這樣，每個 KV 對都會把它最近一次被訪問的時間戳，記錄在 lru 變量。

redisObject 定義包含 lru 成員變量的定義：

每個 KV 對的 LRU 時鐘值是如何計算的？Redis Server 使用一個實例級別的全局 LRU 時鐘，每個 KV 對的 LRU time 會根據全局 LRU 時鐘進行設置。

這全局 LRU 時鐘保存在 Redis 全局變量 server 的成員變量 lruclock

當 Redis Server 啟動后，調用 initServerConfig 初始化各項參數時，會調用 getLRUClock 設置 lruclock 的值：

于是，就得注意，** 若一個數據前后兩次訪問的時間間隔<1s，那這兩次訪問的時間戳就是一樣的！** 因為 LRU 時鐘精度就是 1s，它無法區分間隔小于 1 秒的不同時間戳！

getLRUClock 函數將獲得的 UNIX 時間戳，除以 LRU_CLOCK_RESOLUTION 后，就得到了以 LRU 時鐘精度來計算的 UNIX 時間戳，也就是當前的 LRU 時鐘值。

getLRUClock 會把 LRU 時鐘值和宏定義 LRU_CLOCK_MAX（LRU 時鐘能表示的最大值）做與運算。

所以默認情況下，全局 LRU 時鐘值是以 1s 為精度計算得 UNIX 時間戳，且是在 initServerConfig 中進行的初始化。

那 Redis Server 運行過程中，全局 LRU 時鐘值是如何更新的？和 Redis Server 在事件驅動框架中，定期運行的時間事件所對應的 serverCron 有關。

serverCron 作為時間事件的回調函數，本身會周期性執行，其頻率值由 redis.conf 的 hz 配置項決定，默認值 10，即 serverCron 函數會每 100ms（1s/10 = 100ms）運行一次。serverCron 中，全局 LRU 時鐘值就會按該函數執行頻率，定期調用 getLRUClock 進行更新：

這樣，每個 KV 對就能從全局 LRU 時鐘獲取最新訪問時間戳。

對于每個 KV 對，它對應的 redisObject.lru 在哪些函數進行初始化和更新的呢？

2.2 鍵值對 LRU 時鐘值的初始化與更新

對于一個 KV 對，其 LRU 時鐘值最初是在這 KV 對被創建時，進行初始化設置的，這初始化操作在 createObject 函數中調用，當 Redis 要創建一個 KV 對，就會調用該函數。

createObject 除了會給 redisObject 分配內存空間，還會根據 maxmemory_policy 配置，初始化設置 redisObject.lru。

若 maxmemory_policy=LFU，則 lru 變量值會被初始化設置為 LFU 算法的計算值

maxmemory_policy≠LFU，則 createObject 調用 LRU_CLOCK 設置 lru 值，即 KV 對對應的 LRU 時鐘值。

LRU_CLOCK 返回當前全局 LRU 時鐘值。因為一個 KV 對一旦被創建，就相當于有了次訪問，其對應 LRU 時鐘值就表示了它的訪問時間戳：

那一個 KV 對的 LRU 時鐘值又是何時再被更新？

只要一個 KV 對被訪問，其 LRU 時鐘值就會被更新！而當一個 KV 對被訪問時，訪問操作最終都會調用 lookupKey。

lookupKey 會從全局哈希表中查找要訪問的 KV 對。若該 KV 對存在，則 lookupKey 會根據 maxmemory_policy 的配置值，來更新鍵值對的 LRU 時鐘值，也就是它的訪問時間戳。

而當 maxmemory_policy 沒有配置為 LFU 策略時，lookupKey 函數就會調用 LRU_CLOCK 函數，來獲取當前的全局 LRU 時鐘值，并將其賦值給鍵值對的 redisObject 結構體中的 lru 變量

這樣，每個 KV 對一旦被訪問，就能獲得最新的訪問時間戳。但你可能好奇：這些訪問時間戳最終是如何被用于近似 LRU 算法進行數據淘汰的？

2.3 近似 LRU 算法的實際執行

Redis 之所以實現近似 LRU，是為減少內存資源和操作時間上的開銷。

2.3.1 何時觸發算法執行？

近似 LRU 主要邏輯在 performEvictions。

performEvictions 被 evictionTimeProc 調用，而 evictionTimeProc 函數又是被 processCommand 調用。

processCommand，Redis 處理每個命令時都會調用：

然后，isSafeToPerformEvictions 還會再次根據如下條件判斷是否繼續執行 performEvictions：

一旦 performEvictions 被調用，且 maxmemory-policy 被設置為 allkeys-lru 或 volatile-lru，近似 LRU 就被觸發執行了。

2.3.2 近似 LRU 具體執行過程

執行可分成如下步驟：

2.3.2.1 判斷當前內存使用情況

調用 getMaxmemoryState 評估當前內存使用情況，判斷當前 Redis Server 使用內存容量是否超過 maxmemory 配置值。

若未超過 maxmemory，則返回 C_OK，performEvictions 也會直接返回。

getMaxmemoryState 評估當前內存使用情況的時候，若發現已用內存超出 maxmemory，會計算需釋放的內存量。這個釋放內存大小 = 已使用內存量 -maxmemory。

但已使用內存量并不包括用于主從復制的復制緩沖區大小，這是 getMaxmemoryState 通過調用 freeMemoryGetNotCountedMemory 計算的。

而若當前 Server 使用的內存量超出 maxmemory 上限，則 performEvictions 會執行 while 循環淘汰數據釋放內存。

為淘汰數據，Redis 定義數組 EvictionPoolLRU，保存待淘汰的候選 KV 對，元素類型是 evictionPoolEntry 結構體，保存了待淘汰 KV 對的空閑時間 idle、對應 K 等信息：

這樣，Redis Server 在執行 initSever 進行初始化時，會調用 evictionPoolAlloc 為 EvictionPoolLRU 數組分配內存空間，該數組大小由 EVPOOL_SIZE 決定，默認可保存 16 個待淘汰的候選 KV 對。

performEvictions 在淘汰數據的循環流程中，就會更新這個待淘汰的候選 KV 對集合，即 EvictionPoolLRU 數組。

2.3.2.2 更新待淘汰的候選 KV 對集合

performEvictions 調用 evictionPoolPopulate，其會先調用 dictGetSomeKeys，從待采樣哈希表隨機獲取一定數量 K：

dictGetSomeKeys 采樣的哈希表，由 maxmemory_policy 配置項決定：

若 maxmemory_policy=allkeys_lru，則待采樣哈希表是 Redis Server 的全局哈希表，即在所有 KV 對中采樣

否則，待采樣哈希表就是保存著設置了 TTL 的 K 的哈希表。

dictGetSomeKeys 采樣的 K 的數量由配置項 maxmemory-samples 決定，默認 5：

于是，dictGetSomeKeys 返回采樣的 KV 對集合。evictionPoolPopulate 根據實際采樣到的 KV 對數量 count，執行循環：調用 estimateObjectIdleTime 計算在采樣集合中的每一個 KV 對的空閑時間：

接著，evictionPoolPopulate 遍歷待淘汰的候選 KV 對集合，即 EvictionPoolLRU 數組，嘗試把采樣的每個 KV 對插入 EvictionPoolLRU 數組，取決于如下條件之一：

能在數組中找到一個尚未插入 KV 對的空位

能在數組中找到一個 KV 對的空閑時間<采樣 KV 對的空閑時間

有一成立，evictionPoolPopulate 就能把采樣 KV 對插入 EvictionPoolLRU 數組。等所有采樣鍵值對都處理完后，evictionPoolPopulate 函數就完成對待淘汰候選鍵值對集合的更新了。

接下來，performEvictions 開始選擇最終被淘汰的 KV 對。

2.3.2.3 選擇被淘汰的 KV 對并刪除

因 evictionPoolPopulate 已更新 EvictionPoolLRU 數組，且該數組里的 K，是按空閑時間從小到大排好序了。所以，performEvictions 遍歷一次 EvictionPoolLRU 數組，從數組的最后一個 K 開始選擇，若選到的 K 非空，就把它作為最終淘汰的 K。

該過程執行邏輯：