簡單理解Redis的LRU快取淘汰演算法實現

這篇文章為大家帶來了關於Redis教程中的相關知識，其中主要介紹了Redis的LRU緩存淘汰演算法實現相關問題，LRU會使用一個鍊錶維護緩存中每個數據的訪問情況，並根據數據的實時訪問，調整數據在鍊錶中的位置，希望對大家有幫助。

推薦學習：Redis學習教學

#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：

1. dictGetSomeKeys取樣的雜湊表，由maxmemory_policy配置項目決定：
   • 若maxmemory_policy=allkeys_lru，則待取樣雜湊表是Redis Server的全域雜湊表，即在所有KV對中取樣
   • 否則，待取樣雜湊表就是儲存設定了TTL的K的雜湊表。

2. dictGetSomeKeys取樣的K的數量由配置項maxmemory-samples決定，預設為5：

於是，dictGetSomeKeys傳回取樣的KV對集合。 evictionPoolPopulate根據實際取樣到的KV對數量count，執行循環：呼叫estimateObjectIdleTime計算在取樣集合中的每一個KV對的空閒時間：

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

1. 能在數組中找到一個尚未插入KV對的空位
2. 能在數組中找到一個KV對的空閒時間＜採樣KV對的空閒時間

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

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

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

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

這個過程執行邏輯：

一旦選到被淘汰的K，performEvictions就會根據Redis server的惰性刪除配置，執行同步刪除或非同步刪除：

至此，performEvictions就淘汰了一個K。若此時釋放的記憶體空間還不夠，即沒有達到待釋放空間，則performEvictions還會重複執行前面所說的更新待淘汰候選KV對集合、選擇最終淘汰K的過程，直到滿足待釋放空間的大小要求。

performEvictions流程：

近似LRU演算法並未使用耗時且耗空間的鍊錶，而使用固定大小的待淘汰資料集合，每次隨機選擇一些K加入待淘汰資料集合。

最後，依待淘汰集合中K的空閒時間長度，刪除空閒時間最長的K。

總結

根據LRU演算法的基本原理，發現若嚴格以基本原理實作LRU演算法，則開發的系統就需要額外記憶體空間保存LRU鍊錶，系統運作時也會受到LRU鍊錶操作的開銷影響。

而Redis的記憶體資源和效能都很重要，所以Redis實作近似LRU演算法：

• 首先是設定了全域LRU時鐘，並且在KV對建立時取得全域LRU時鐘值作為存取時間戳，及每次造訪時取得全域LRU時鐘值，更新存取時間戳
• 然後，當Redis每處理一個指令，都會呼叫performEvictions判斷是否需釋放記憶體。若已使用記憶體超出maxmemory，則隨機選擇一些KV對，組成待淘汰候選集合，並根據它們的存取時間戳，選出最舊資料淘汰

一個演算法的基本原理和演算法的實際執行，在系統開發上會有一定折中，需綜合考慮所開發的系統，在資源和性能方面的要求，以避免嚴格按照演算法實現帶來的資源和性能開銷。

推薦學習：Redis教學

以上是簡單理解Redis的LRU快取淘汰演算法實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！