Redis的LRU緩存淘汰算法怎么實(shí)現(xiàn)

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

1 標(biāo)準(zhǔn)LRU的實(shí)現(xiàn)原理

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

LRU會使用一個鏈表維護(hù)緩存中每個數(shù)據(jù)的訪問情況，并根據(jù)數(shù)據(jù)的實(shí)時訪問，調(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：當(dāng)有新數(shù)據(jù)插入，LRU會把該數(shù)據(jù)插入到鏈?zhǔn)?，同時把原來鏈表頭部的數(shù)據(jù)及其之后的數(shù)據(jù)，都向尾部移動一位

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

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

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

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

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

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

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

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

最終導(dǎo)致降低Redis訪問性能。

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

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

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

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

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

所以，一旦設(shè)定maxmemory選項(xiàng)，且將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如何實(shí)現(xiàn)近似LRU算法的呢？

• 全局LRU時鐘值的計(jì)算

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

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

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

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

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

2.1 全局LRU時鐘值的計(jì)算

近似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時鐘值是如何計(jì)算的？Redis Server使用一個實(shí)例級別的全局LRU時鐘，每個KV對的LRU time會根據(jù)全局LRU時鐘進(jìn)行設(shè)置。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Redis之所以實(shí)現(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 判斷當(dāng)前內(nèi)存使用情況

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

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

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

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

而若當(dāng)前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進(jìn)行初始化時，會調(diào)用evictionPoolAlloc為EvictionPoolLRU數(shù)組分配內(nèi)存空間，該數(shù)組大小由EVPOOL_SIZE決定，默認(rèn)可保存16個待淘汰的候選KV對。

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

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

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

1. dictGetSomeKeys采樣的哈希表，由maxmemory_policy配置項(xiàng)決定：

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

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

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

于是，dictGetSomeKeys返回采樣的KV對集合。evictionPoolPopulate根據(jù)實(shí)際采樣到的KV對數(shù)量count，執(zhí)行循環(huán)：調(diào)用estimateObjectIdleTime計(jì)算在采樣集合中的每一個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)存空間還不夠，即沒有達(dá)到待釋放空間，則performEvictions還會重復(fù)執(zhí)行前面所說的更新待淘汰候選KV對集合、選擇最終淘汰K的過程，直到滿足待釋放空間的大小要求。

performEvictions流程：

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

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

讀到這里，這篇“Redis的LRU緩存淘汰算法怎么實(shí)現(xiàn)”文章已經(jīng)介紹完畢，想要掌握這篇文章的知識點(diǎn)還需要大家自己動手實(shí)踐使用過才能領(lǐng)會，如果想了解更多相關(guān)內(nèi)容的文章，歡迎關(guān)注億速云行業(yè)資訊頻道。