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

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

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。

讀到這里，這篇“Redis的LRU緩存淘汰算法怎么實現”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。