Redis如何實現(xiàn)LRU緩存淘汰算法

小編給大家分享一下Redis如何實現(xiàn)LRU緩存淘汰算法，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

1 標準LRU的實現(xiàn)原理

LRU，最近最少使用（Least Recently Used，LRU），經(jīng)典緩存算法。

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

LRU會把鏈頭、尾分別設(shè)為MRU端和LRU端：

• MRU，Most Recently Used 縮寫，表示此處數(shù)據(jù)剛被訪問

• LRU端，此處數(shù)據(jù)最近最少被訪問的數(shù)據(jù)

LRU可分成如下情況：

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

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

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

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

所以若嚴格按LRU實現(xiàn)，假設(shè)Redis保存的數(shù)據(jù)較多，還要在代碼中實現(xiàn)：

• 為Redis使用最大內(nèi)存時，可容納的所有數(shù)據(jù)維護一個鏈表

  需額外內(nèi)存空間來保存鏈表

• 每當有新數(shù)據(jù)插入或現(xiàn)有數(shù)據(jù)被再次訪問，需執(zhí)行多次鏈表操作

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

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

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

2 Redis的近似LRU算法實現(xiàn)

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

• maxmemory，設(shè)定Redis server可使用的最大內(nèi)存容量，一旦server使用實際內(nèi)存量超出該閾值，server會根據(jù)maxmemory-policy配置策略，執(zhí)行內(nèi)存淘汰操作

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

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

• allkeys-lru是在所有的KV對中篩選將被淘汰的數(shù)據(jù)

• volatile-lru在設(shè)置了TTL的KV對中篩選將被淘汰數(shù)據(jù)

Redis如何實現(xiàn)近似LRU算法的呢？

• 全局LRU時鐘值的計算

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

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

  哪些函數(shù)中對每個鍵值對對應(yīng)的LRU時鐘值，進行初始化與更新

• 近似LRU算法的實際執(zhí)行

  如何執(zhí)行近似LRU算法，即何時觸發(fā)數(shù)據(jù)淘汰，以及實際淘汰的機制實現(xiàn)

2.1 全局LRU時鐘值的計算

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

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

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

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

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

當Redis Server啟動后，調(diào)用initServerConfig初始化各項參數(shù)時，會調(diào)用getLRUClock設(shè)置lruclock的值：

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

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

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

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

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

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

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

對于每個KV對，它對應(yīng)的redisObject.lru在哪些函數(shù)進行初始化和更新的呢？

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

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

createObject除了會給redisObject分配內(nèi)存空間，還會根據(jù)maxmemory_policy配置，初始化設(shè)置redisObject.lru。

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

• maxmemory_policy≠LFU，則createObject調(diào)用LRU_CLOCK設(shè)置lru值，即KV對對應(yīng)的LRU時鐘值。

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

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

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

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

而當maxmemory_policy沒有配置為LFU策略時，lookupKey函數(shù)就會調(diào)用LRU_CLOCK函數(shù)，來獲取當前的全局LRU時鐘值，并將其賦值給鍵值對的redisObject結(jié)構(gòu)體中的lru變量

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

2.3 近似LRU算法的實際執(zhí)行

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

2.3.1 何時觸發(fā)算法執(zhí)行？

近似LRU主要邏輯在performEvictions。

performEvictions被evictionTimeProc調(diào)用，而evictionTimeProc函數(shù)又是被processCommand調(diào)用。

processCommand，Redis處理每個命令時都會調(diào)用：

然后，isSafeToPerformEvictions還會再次根據(jù)如下條件判斷是否繼續(xù)執(zhí)行performEvictions：

一旦performEvictions被調(diào)用，且maxmemory-policy被設(shè)置為allkeys-lru或volatile-lru，近似LRU就被觸發(fā)執(zhí)行了。

2.3.2 近似LRU具體執(zhí)行過程

執(zhí)行可分成如下步驟：

2.3.2.1 判斷當前內(nèi)存使用情況

調(diào)用getMaxmemoryState評估當前內(nèi)存使用情況，判斷當前Redis Server使用內(nèi)存容量是否超過maxmemory配置值。

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

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

但已使用內(nèi)存量并不包括用于主從復制的復制緩沖區(qū)大小，這是getMaxmemoryState通過調(diào)用freeMemoryGetNotCountedMemory計算的。

而若當前Server使用的內(nèi)存量超出maxmemory上限，則performEvictions會執(zhí)行while循環(huán)淘汰數(shù)據(jù)釋放內(nèi)存。

為淘汰數(shù)據(jù)，Redis定義數(shù)組EvictionPoolLRU，保存待淘汰的候選KV對，元素類型是evictionPoolEntry結(jié)構(gòu)體，保存了待淘汰KV對的空閑時間idle、對應(yīng)K等信息：

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

performEvictions在淘汰數(shù)據(jù)的循環(huán)流程中，就會更新這個待淘汰的候選KV對集合，即EvictionPoolLRU數(shù)組。

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

performEvictions調(diào)用evictionPoolPopulate，其會先調(diào)用dictGetSomeKeys，從待采樣哈希表隨機獲取一定數(shù)量K：

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

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

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

2. dictGetSomeKeys采樣的K的數(shù)量由配置項maxmemory-samples決定，默認5：

于是，dictGetSomeKeys返回采樣的KV對集合。evictionPoolPopulate根據(jù)實際采樣到的KV對數(shù)量count，執(zhí)行循環(huán)：調(diào)用estimateObjectIdleTime計算在采樣集合中的每一個KV對的空閑時間：

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

1. 能在數(shù)組中找到一個尚未插入KV對的空位

2. 能在數(shù)組中找到一個KV對的空閑時間＜采樣KV對的空閑時間

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

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

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

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

該過程執(zhí)行邏輯：

一旦選到被淘汰的K，performEvictions就會根據(jù)Redis server的惰性刪除配置，執(zhí)行同步刪除或異步刪除：

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

performEvictions流程：

近似LRU算法并未使用耗時且耗空間的鏈表，而使用固定大小的待淘汰數(shù)據(jù)集合，每次隨機選擇一些K加入待淘汰數(shù)據(jù)集合。

最后，按待淘汰集合中K的空閑時間長度，刪除空閑時間最長的K。

總結(jié)

根據(jù)LRU算法的基本原理，發(fā)現(xiàn)若嚴格按基本原理實現(xiàn)LRU算法，則開發(fā)的系統(tǒng)就需要額外內(nèi)存空間保存LRU鏈表，系統(tǒng)運行時也會受到LRU鏈表操作的開銷影響。

而Redis的內(nèi)存資源和性能都很重要，所以Redis實現(xiàn)近似LRU算法：

• 首先是設(shè)置了全局LRU時鐘，并在KV對創(chuàng)建時獲取全局LRU時鐘值作為訪問時間戳，及在每次訪問時獲取全局LRU時鐘值，更新訪問時間戳

• 然后，當Redis每處理一個命令，都調(diào)用performEvictions判斷是否需釋放內(nèi)存。若已使用內(nèi)存超出maxmemory，則隨機選擇一些KV對，組成待淘汰候選集合，并根據(jù)它們的訪問時間戳，選出最舊數(shù)據(jù)淘汰

一個算法的基本原理和算法的實際執(zhí)行，在系統(tǒng)開發(fā)中會有一定折中，需綜合考慮所開發(fā)的系統(tǒng)，在資源和性能方面的要求，以避免嚴格按照算法實現(xiàn)帶來的資源和性能開銷。

以上是“Redis如何實現(xiàn)LRU緩存淘汰算法”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學習更多知識，歡迎關(guān)注億速云行業(yè)資訊頻道！