思考（作業(yè)）：基于一個(gè)數(shù)據(jù)結(jié)構(gòu)做緩存，怎么實(shí)現(xiàn)LRU——最長(zhǎng)時(shí)間不被訪問(wèn)的元素在超過(guò)容量時(shí)刪除？

問(wèn)題：如果基于傳統(tǒng)LRU 算法實(shí)現(xiàn)Redis LRU 會(huì)有什么問(wèn)題？

需要額外的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)，消耗內(nèi)存。

Redis LRU 對(duì)傳統(tǒng)的LRU 算法進(jìn)行了改良，通過(guò)隨機(jī)采樣來(lái)調(diào)整算法的精度。

如果淘汰策略是LRU，則根據(jù)配置的采樣值maxmemory_samples（默認(rèn)是5 個(gè)）,隨機(jī)從數(shù)據(jù)庫(kù)中選擇m 個(gè)key, 淘汰其中熱度最低的key 對(duì)應(yīng)的緩存數(shù)據(jù)。所以采樣參數(shù)m 配置的數(shù)值越大, 就越能精確的查找到待淘汰的緩存數(shù)據(jù),但是也消耗更多的CPU 計(jì)算,執(zhí)行效率降低。

問(wèn)題：如何找出熱度最低的數(shù)據(jù)？

Redis 中所有對(duì)象結(jié)構(gòu)都有一個(gè)lru 字段, 且使用了unsigned 的低24 位，這個(gè)字段用來(lái)記錄對(duì)象的熱度。對(duì)象被創(chuàng)建時(shí)會(huì)記錄lru 值。在被訪問(wèn)的時(shí)候也會(huì)更新lru 的值。但是不是獲取系統(tǒng)當(dāng)前的時(shí)間戳，而是設(shè)置為全局變量server.lruclock 的值。

源碼：server.h

typedef struct redisObject {unsigned type:4;unsigned encoding:4;unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or* LFU data (least significant 8 bits frequency* and most significant 16 bits access time). */int refcount;void *ptr; } robj;

server.lruclock 的值怎么來(lái)的？

Redis 中有個(gè)定時(shí)處理的函數(shù)serverCron ， 默認(rèn)每100 毫秒調(diào)用函數(shù)updateCachedTime 更新一次全局變量的server.lruclock 的值，它記錄的是當(dāng)前unix時(shí)間戳。

源碼：server.c

void updateCachedTime(void) {time_t unixtime = time(NULL);atomicSet(server.unixtime,unixtime);server.mstime = mstime();struct tm tm;localtime_r(&server.unixtime,&tm);server.daylight_active = tm.tm_isdst; }

問(wèn)題：為什么不獲取精確的時(shí)間而是放在全局變量中？不會(huì)有延遲的問(wèn)題嗎？

這樣函數(shù)lookupKey 中更新數(shù)據(jù)的lru 熱度值時(shí),就不用每次調(diào)用系統(tǒng)函數(shù)time，可以提高執(zhí)行效率。

OK，當(dāng)對(duì)象里面已經(jīng)有了LRU 字段的值，就可以評(píng)估對(duì)象的熱度了。

函數(shù)estimateObjectIdleTime 評(píng)估指定對(duì)象的lru 熱度，思想就是對(duì)象的lru 值和全局的server.lruclock 的差值越大（越久沒(méi)有得到更新）， 該對(duì)象熱度越低。

源碼evict.c

/* Given an object returns the min number of milliseconds the object was never * requested, using an approximated LRU algorithm. */ unsigned long long estimateObjectIdleTime(robj *o) {unsigned long long lruclock = LRU_CLOCK();if (lruclock >= o->lru) {return (lruclock - o->lru) * LRU_CLOCK_RESOLUTION;} else {return (lruclock + (LRU_CLOCK_MAX - o->lru)) *LRU_CLOCK_RESOLUTION;} }

server.lruclock 只有24 位，按秒為單位來(lái)表示才能存儲(chǔ)194 天。當(dāng)超過(guò)24bit 能表示的最大時(shí)間的時(shí)候，它會(huì)從頭開(kāi)始計(jì)算。

server.h

#define LRU_CLOCK_MAX ((1<<LRU_BITS)-1) /* Max value of obj->lru */

在這種情況下，可能會(huì)出現(xiàn)對(duì)象的lru 大于server.lruclock 的情況，如果這種情況出現(xiàn)那么就兩個(gè)相加而不是相減來(lái)求最久的key。

為什么不用常規(guī)的哈希表+雙向鏈表的方式實(shí)現(xiàn)？需要額外的數(shù)據(jù)結(jié)構(gòu)，消耗資源。而Redis LRU 算法在sample 為10 的情況下，已經(jīng)能接近傳統(tǒng)LRU 算法了。

https://redis.io/topics/lru-cache

問(wèn)題：除了消耗資源之外，傳統(tǒng)LRU 還有什么問(wèn)題？

如圖，假設(shè)A 在10 秒內(nèi)被訪問(wèn)了5 次，而B(niǎo) 在10 秒內(nèi)被訪問(wèn)了3 次。因?yàn)锽 最后一次被訪問(wèn)的時(shí)間比A 要晚，在同等的情況下，A 反而先被回收。

問(wèn)題：要實(shí)現(xiàn)基于訪問(wèn)頻率的淘汰機(jī)制，怎么做？

LFU

server.h

typedef struct redisObject {unsigned type:4;unsigned encoding:4;unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or* LFU data (least significant 8 bits frequency* and most significant 16 bits access time). */int refcount;void *ptr; } robj;

當(dāng)這24 bits 用作LFU 時(shí)，其被分為兩部分：

高16 位用來(lái)記錄訪問(wèn)時(shí)間（單位為分鐘，ldt，last decrement time）

低8 位用來(lái)記錄訪問(wèn)頻率，簡(jiǎn)稱counter（logc，logistic counter）

counter 是用基于概率的對(duì)數(shù)計(jì)數(shù)器實(shí)現(xiàn)的，8 位可以表示百萬(wàn)次的訪問(wèn)頻率。

對(duì)象被讀寫的時(shí)候，lfu 的值會(huì)被更新。

db.c——lookupKey

void updateLFU(robj *val) {unsigned long counter = LFUDecrAndReturn(val);counter = LFULogIncr(counter);val->lru = (LFUGetTimeInMinutes()<<8) | counter; }

增長(zhǎng)的速率由，lfu-log-factor 越大，counter 增長(zhǎng)的越慢

redis.conf 配置文件

# lfu-log-factor 10

如果計(jì)數(shù)器只會(huì)遞增不會(huì)遞減，也不能體現(xiàn)對(duì)象的熱度。沒(méi)有被訪問(wèn)的時(shí)候，計(jì)數(shù)器怎么遞減呢？

減少的值由衰減因子lfu-decay-time（分鐘）來(lái)控制，如果值是1 的話，N 分鐘沒(méi)有訪問(wèn)就要減少N。

redis.conf 配置文件

# lfu-decay-time 1

?

總結(jié)

以上是生活随笔為你收集整理的Redis LRU 淘汰原理的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。