redis是一個(gè)內(nèi)存型數(shù)據(jù)庫(kù)，我們的數(shù)據(jù)都是放在內(nèi)存里面的!但是內(nèi)存是有大小的！比如，redis有個(gè)很重要的配置文件，redis.conf，里面有個(gè)配置

# maxmemory <bytes> //redis占用的最大內(nèi)存

如果我們不淘汰，那么它的數(shù)據(jù)就會(huì)滿，滿了肯定就不能再放數(shù)據(jù)，發(fā)揮不了redis的作用！

比如冰箱，你如果放滿了，那么你的菜就不能放冰箱了！

過期策略：拿出redis中已經(jīng)過期了的數(shù)據(jù)，就像你從冰箱把壞的菜拿出來！！但是有一種情況，就是冰箱里面的菜都沒壞，redis里面的數(shù)據(jù)都沒過期，它也是會(huì)放滿的，那怎么辦？

那么當(dāng)redis里面的數(shù)據(jù)都沒過期。但是內(nèi)存滿了的時(shí)候，我們就得從未過期的數(shù)據(jù)里面去拿出一些扔掉，那么這個(gè)就是我們的淘汰策略。

過期策略

Redis 所有的數(shù)據(jù)結(jié)構(gòu)都可以設(shè)置過期時(shí)間，時(shí)間一到，就會(huì)自動(dòng)刪除?？梢韵胂罄锩嬗幸粋€(gè)專門刪除過期數(shù)據(jù)的線程，數(shù)據(jù)已過期就立馬刪除。

這個(gè)時(shí)候可以思考一下，會(huì)不會(huì)因?yàn)橥粫r(shí)間太多的 key 過期，以至于線程忙不過來。同時(shí)因?yàn)?Redis 是單線程的，刪除的時(shí)間也會(huì)占用線程的處理時(shí)間，如果刪除的太過于繁忙，會(huì)不會(huì)導(dǎo)致線上讀寫指令出現(xiàn)卡頓。

立即刪除

• 它會(huì)在設(shè)置鍵的過期時(shí)間的同時(shí)，創(chuàng)建一個(gè)定時(shí)器， 當(dāng)鍵到了過期時(shí)間，定時(shí)器會(huì)立即對(duì)鍵進(jìn)行刪除。
• 這個(gè)策略能夠保證過期鍵的盡快刪除，快速釋放內(nèi)存空間。

優(yōu)點(diǎn)：

• 立即刪除能保證內(nèi)存中數(shù)據(jù)的最大新鮮度，因?yàn)樗ＷC過期鍵值會(huì)在過期后馬上被刪除，其所占用的內(nèi)存也會(huì)隨之釋放。
• 對(duì)內(nèi)存來說是非常友好的。

缺點(diǎn)：

• 立即刪除對(duì)cpu是最不友好的。
• 因?yàn)閯h除操作會(huì)占用cpu的時(shí)間，如果剛好碰上了cpu很忙的時(shí)候，比如正在做交集或排序等計(jì)算的時(shí)候，就會(huì)給cpu造成額外的壓力。

總結(jié)：

• 立即刪除對(duì)cpu不友好，但是對(duì)內(nèi)存友好，實(shí)際性質(zhì)就是用處理器性能換區(qū)內(nèi)存空間。

惰性刪除（被動(dòng)過期）

• 數(shù)據(jù)到達(dá)過期時(shí)間，不做處理。等下次訪問該數(shù)據(jù)時(shí)，如果未過期，返回?cái)?shù)據(jù) ；發(fā)現(xiàn)已過期，刪除，返回不存在。
• 開啟惰性刪除：lazyfree-lazy-eviction=yes

優(yōu)點(diǎn)：

• 對(duì)于cpu來說是非常友好的，減少了cpu資源的占有。

缺點(diǎn)：

• 如果一個(gè)鍵已經(jīng)過期，而這個(gè)鍵又仍然保留在redis中，那么只要這個(gè)過期鍵不被刪除，它所占用的內(nèi)存就不會(huì)釋放。因此對(duì)于內(nèi)存是很不友好的。
• 在使用惰性刪除策略時(shí)，如果數(shù)據(jù)庫(kù)中有非常多的過期鍵，而這些過期鍵又恰好沒有被訪問到的話，那么它們也許永遠(yuǎn)也不會(huì)被刪除(除非用戶手動(dòng)執(zhí)行FLUSHDB)，我們甚至可以將這種情況看作是一種內(nèi)存泄漏–無用的垃圾數(shù)據(jù)占用了大量的內(nèi)存，而服務(wù)器卻不會(huì)自己去釋放它們，這對(duì)于運(yùn)行狀態(tài)非常依賴于內(nèi)存的Redis服務(wù)器來說,肯定不是一個(gè)好消息

定期刪除

• 定期刪除策略是前兩種策略的折中：
• 定期刪除策略每隔一段時(shí)間執(zhí)行一次刪除過期鍵操作并通過限制刪除操作執(zhí)行時(shí)長(zhǎng)和頻率來減少刪除操作對(duì)CPU時(shí)間的影響。

過期key的集合

redis 會(huì)將每個(gè)設(shè)置了過期時(shí)間的 key 放入到一個(gè)獨(dú)立的字典中，以后會(huì)定時(shí)遍歷這個(gè) 字典來刪除到期的 key。除了定時(shí)遍歷之外，它還會(huì)使用惰性策略來刪除過期的 key。定期刪除是集中處理，惰性刪除是零散處理。

定時(shí)掃描策略

Redis 默認(rèn)會(huì)每秒進(jìn)行十次過期掃描，過期掃描不會(huì)遍歷過期字典中所有的 key，而是 采用了一種簡(jiǎn)單的貪心策略。

1. 從過期字典中隨機(jī) 20 個(gè) key；
2. 刪除這 20 個(gè) key 中已經(jīng)過期的 key；
3. 如果過期的 key 比率超過 1/4，那就重復(fù)步驟 1；

于此同時(shí)為了保證過期掃描不會(huì)出現(xiàn)循環(huán)過度，導(dǎo)致線程卡死現(xiàn)象，算法還增加了掃描時(shí)間的上限，默認(rèn)不會(huì)超過 25ms。

（1）定時(shí)過期到底是怎么實(shí)現(xiàn)？

定期去循環(huán)找過期的key，然后去刪掉！

（2）去循環(huán)誰(shuí)？是不是所有的key？

并不是去循環(huán)所有的key，因?yàn)镽edis里經(jīng)常會(huì)存放巨多的數(shù)據(jù)，對(duì)我們需要經(jīng)常清理，全部遍歷一遍顯然不現(xiàn)實(shí)，而Redis采取的是取樣這個(gè)操作。

• 1-不是一次性把所有設(shè)置了過期時(shí)間的數(shù)據(jù)拿出來，而是按hash桶維度取 里面取值，取到20個(gè)值為止，如果第一個(gè)有30個(gè)，那么也會(huì)取30個(gè)！ 如果一直取不到20，那么最多400個(gè)桶
• 2-刪除取出值的過期key
• 3-如果400個(gè)桶都取不到值，或者取出的key 刪除的比例大于10%,繼續(xù)上 面的操作
• 4-每循環(huán)16次會(huì)去檢測(cè)時(shí)間，超過指定時(shí)間就跳出

ps:按hash桶維度取key的邏輯是：最后一個(gè)桶會(huì)取完桶內(nèi)所有的key，不論里面有多少個(gè)，每取完一個(gè)桶判斷一下是否取到了20個(gè)，最多取400個(gè)桶。

（3）多久循環(huán)一次？

redis里面有個(gè)很重要的概念叫做時(shí)間事件，那么這個(gè)時(shí)間事件是什么意思了，就是定時(shí)去做一些事情，那么redis里面有個(gè)方法叫serverCron()，在文件server.c中；就是它的時(shí)間事件去調(diào)用的清理
它里面干了很多事情，比如：

• 1-更新服務(wù)器的各類統(tǒng)計(jì)信息，比如時(shí)間、內(nèi)存占用、數(shù)據(jù)庫(kù)占用情況等
• 2-清理數(shù)據(jù)庫(kù)中的過期鍵值對(duì)。
• 3-關(guān)閉和清理連接失效的客戶端
• 4-嘗試進(jìn)行持久化操作

那么這個(gè)時(shí)間事件多久去執(zhí)行一次呢，其實(shí)是由你們自己決定的！

redis.conf 中通過 hz 配置，hz代表的意思是每秒執(zhí)行多少次！默認(rèn)10次，也就是100ms我們就會(huì)去執(zhí)行定期過期！！

特別注意的情況

設(shè)想一個(gè)大型的 Redis 實(shí)例中所有的 key 在同一時(shí)間過期了。Redis 會(huì)持續(xù)掃描過期字典 (循環(huán)多次)，直到過期字典中過期的 key 變得稀 疏，才會(huì)停止 (循環(huán)次數(shù)明顯下降)。這就會(huì)導(dǎo)致線上讀寫請(qǐng)求出現(xiàn)明顯的卡頓現(xiàn)象。導(dǎo)致這 種卡頓的另外一種原因是內(nèi)存管理器需要頻繁回收內(nèi)存頁(yè)，這也會(huì)產(chǎn)生一定的 CPU 消耗。

即使算法還增加了掃描時(shí)間的上限，也是會(huì)出現(xiàn)卡頓現(xiàn)象。假如有 101 個(gè)客戶端同時(shí)將請(qǐng)求發(fā)過來了，然后前 100 個(gè)請(qǐng)求的執(zhí)行時(shí)間都是 25ms，那么第 101 個(gè)指令需要等待多久才能執(zhí)行？2500ms，這個(gè)就是客戶端的卡頓時(shí)間，是由服務(wù)器不間斷的小卡頓積少成多導(dǎo)致的（假如每次都達(dá)到了掃描上線25ms）。

所以開發(fā)的時(shí)候就需要特別注意，避免大量key在同一時(shí)間過期。可以給key在固定的過期時(shí)間上+隨機(jī)范圍的時(shí)間

定期刪除注意事項(xiàng)

如果刪除操作執(zhí)行次數(shù)過多、執(zhí)行時(shí)間太長(zhǎng)，就會(huì)導(dǎo)致和定時(shí)刪除同樣的問題：占用大量cpu資源去進(jìn)行刪除操作

如果刪除操作次數(shù)太少、執(zhí)行時(shí)間短，就會(huì)導(dǎo)致和惰性刪除同樣的問題：內(nèi)存資源被持續(xù)占用，得不到釋放。

所以定時(shí)刪除最關(guān)鍵的就在于執(zhí)行時(shí)長(zhǎng)和頻率的設(shè)置，可在redis的配置文件中配置

對(duì)于hz參數(shù)，官方不建議超過100，否則會(huì)把cpu造成比較大的壓力

緩存淘汰策略

緩存淘汰策略的作用

（1）當(dāng) Redis 內(nèi)存超出物理內(nèi)存限制時(shí)，內(nèi)存的數(shù)據(jù)會(huì)開始和磁盤產(chǎn)生頻繁的交換，交換會(huì)讓 Redis 的性能急劇下降，對(duì)于訪問量比較頻繁的 Redis 來說，這樣龜速的存取效率 基本上等于不可用。

（2）一般生產(chǎn)上的redis內(nèi)存都會(huì)設(shè)置一個(gè)內(nèi)存上限（maxmemory），如果有許多沒有加過期時(shí)間的數(shù)據(jù)，長(zhǎng)期下來就會(huì)把redis內(nèi)存打滿，出現(xiàn)OOM異常。

（3）定期刪除是使用簡(jiǎn)單的貪心算法，會(huì)出現(xiàn)一些沒有被抽查到的數(shù)據(jù)，而惰性刪除也會(huì)出現(xiàn)一些長(zhǎng)時(shí)間沒有訪問得數(shù)據(jù)，這就會(huì)導(dǎo)致大量過期的key堆積在內(nèi)存中，導(dǎo)致redis內(nèi)存空間緊張或者很快耗盡。所以必須要有一個(gè)兜底方案。這個(gè)方案就是緩存淘汰策略。

八種緩存淘汰策略

• noeviction：不會(huì)繼續(xù)服務(wù)寫請(qǐng)求 (DEL 請(qǐng)求可以繼續(xù)服務(wù))，讀請(qǐng)求可以繼續(xù)進(jìn)行。這樣 可以保證不會(huì)丟失數(shù)據(jù)，但是會(huì)讓線上的業(yè)務(wù)不能持續(xù)進(jìn)行。這是默認(rèn)的淘汰策略。
• volatile-lru：嘗試淘汰設(shè)置了過期時(shí)間的 key，最少使用的 key 優(yōu)先被淘汰。沒有設(shè)置過 期時(shí)間的 key： 不會(huì)被淘汰，這樣可以保證需要持久化的數(shù)據(jù)不會(huì)突然丟失。
• allkeys-lru： 區(qū)別于 volatile-lru，這個(gè)策略要淘汰的 key 對(duì)象是全體的 key 集合，而不 只是過期的 key 集合。這意味著沒有設(shè)置過期時(shí)間的 key 也會(huì)被淘汰。
• volatile-ttl： 跟上面一樣，除了淘汰的策略不是 LRU，而是 key 的剩余壽命 ttl 的值，ttl 越小越優(yōu)先被淘汰。
• volatile-random：對(duì)所有設(shè)置了過期時(shí)間的key隨機(jī)淘汰。
• allkeys-random：對(duì)所有key隨機(jī)淘汰
• volatile-lfu：對(duì)設(shè)置了過期時(shí)間的key使用lfu算法進(jìn)行刪除
• allkeys-lfu：對(duì)所有key使用lfu算法進(jìn)行刪除

總結(jié)：

• volatile-xxx： 策略只會(huì)針對(duì)帶過期時(shí)間的 key 進(jìn)行淘汰，allkeys-xxx 策略會(huì)對(duì)所有的 key 進(jìn)行淘汰。
• 如果你只是拿 Redis 做緩存，那應(yīng)該使用 allkeys-xxx，客戶端寫緩存時(shí) 不必?cái)y帶過期時(shí)間。
• 如果你還想同時(shí)使用 Redis 的持久化功能，那就使用 volatile-xxx 策略，這樣可以保留沒有設(shè)置過期時(shí)間的 key，它們是永久的 key 不會(huì)被 LRU 算法淘 汰。

PS：是在config文件中配置的策略：

#maxmemory-policy noeviction

默認(rèn)就是不淘汰，如果滿了，能讀不能寫！

LRU和LFU

LRU（Least Recently Used：最久未使用）

根據(jù)時(shí)間軸來走，很久沒用的數(shù)據(jù)只要最近有用過，我就默認(rèn)是有效的。也就是說這個(gè)策略的意思是先淘汰長(zhǎng)時(shí)間沒用過的，那么怎么去判斷一個(gè)redis數(shù)據(jù)有多久沒訪問了，Redis是這樣做的：

redis的所有數(shù)據(jù)結(jié)構(gòu)的對(duì)外對(duì)象里，它里面有個(gè)字段叫做lru

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;

每個(gè)對(duì)象都有1個(gè)LRU的字段，看它的說明，好像LRU跟我們后面講的LFU都跟這個(gè)字段有關(guān)，并且這個(gè)lru代表的是一個(gè)時(shí)間相關(guān)的內(nèi)容。

那么我們大概能猜出來，redis去實(shí)現(xiàn)lru肯定跟我們這個(gè)對(duì)象的lru相關(guān)?。?/p>

首先，我告訴大家，這個(gè)lru在LRU算法的時(shí)候代表的是這個(gè)數(shù)據(jù)的訪問時(shí)間的秒單位??！但是只有24bit，無符號(hào)位，所以這個(gè)lru記錄的是它訪問時(shí)候的秒單位時(shí)間的后24bit！

用Java來寫就是：

long timeMillis=System.currentTimeMillis();
System.out.println(timeMillis/1000); //獲取當(dāng)前秒
System.out.println(timeMillis/1000 & ((1<<24)-1));//獲取秒的后24位

是獲取當(dāng)前時(shí)間的最后24位，那么當(dāng)我們最后的24bit都是1了的時(shí)候，時(shí)間繼續(xù)往前走，那么我們獲取到的時(shí)間是不是就是24個(gè)0了！

舉個(gè)例子：

11111111111111111000000000011111110 假如這個(gè)是我當(dāng)前秒單位的時(shí)間，獲取后8位 是 11111110
11111111111111111000000000011111111 獲取后8位 是11111111
11111111111111111000000000100000000 獲取后8位 是00000000

所以，它有個(gè)輪詢的概念，它如果超過24位，又會(huì)從0開始！所以我們不能直接的用系統(tǒng)時(shí)間秒單位的24bit位去減對(duì)象的lru,而是要判斷一下，還有一點(diǎn)，為了性能，我們系統(tǒng)的時(shí)間不是實(shí)時(shí)獲取的，而是用redis的時(shí)間事件來獲取，所以，我們這個(gè)時(shí)間獲取是100ms去獲取一次。

現(xiàn)在我們知道了原來redis對(duì)象里面原來有個(gè)字段是記錄它訪問時(shí)間的，那么接下來肯定有個(gè)東西去跟這個(gè)時(shí)間去比較，拿到差值！

我們?nèi)タ聪略创aevict.c文件

unsigned long long estimateObjectIdleTime(robj *o) {
	//獲取秒單位時(shí)間的最后24位
	unsigned long long lruclock = LRU_CLOCK();
	//因?yàn)橹挥?4位，所有最大的值為2的24次方-1
	//超過最大值從0開始，所以需要判斷l(xiāng)ruclock（當(dāng)前系統(tǒng)時(shí)間）跟緩存對(duì)象的lru字段的大小
	if (lruclock >= o->lru) {
	//如果lruclock>=robj.lru，返回lruclock-o->lru，再轉(zhuǎn)換單位
	return (lruclock - o->lru) * LRU_CLOCK_RESOLUTION;
	} else {
	//否則采用lruclock + (LRU_CLOCK_MAX - o->lru)，得到對(duì)象的值越小，返回的值越大，越大越容易被淘汰
	return (lruclock + (LRU_CLOCK_MAX - o->lru)) *
	LRU_CLOCK_RESOLUTION;
	}
}

我們發(fā)現(xiàn)，跟對(duì)象的lru比較的時(shí)間也是serverCron下面的當(dāng)前時(shí)間的秒單位的后面24位！但是它有個(gè)判斷，有種情況是系統(tǒng)時(shí)間跟對(duì)象的LRU的大小，因?yàn)樽畲笾挥?4位，會(huì)超過??！

所以，我們可以總結(jié)下我們的結(jié)論：

Redis數(shù)據(jù)對(duì)象的LRU用的是server.lruclock這個(gè)值，server.lruclock又是每隔100ms生成的系統(tǒng)時(shí)間的秒單位的后24位！所以server.lruclock可以理解為延遲了100ms的當(dāng)前時(shí)間秒單位的后24位！

用server.lruclock 與 對(duì)象的lru字段進(jìn)行比較，因?yàn)閟erver.lruclock只獲取了當(dāng)前秒單位時(shí)間的后24位，所以肯定有個(gè)輪詢。所以，我們會(huì)判斷server.lruclock跟對(duì)象的lru字段進(jìn)行比較，如 server.lruclock>obj.lru，那么我們用server.lruclock-obj.lru,否則server.lruclock+(LRU_CLOCK_MAX-obj.lru),得到lru越小，那么返回的數(shù)據(jù)越大，相差越大的就會(huì)被淘汰！

LFU（Least Frequently Used：最不常用）

但是LFU的有個(gè)致命的缺點(diǎn)！就是它只會(huì)加不會(huì)減！為什么說這是個(gè)缺點(diǎn)

舉個(gè)例子：去年有一個(gè)熱搜，今年有一個(gè)熱搜，熱度相當(dāng)，但是去年的那個(gè)因?yàn)橛袝r(shí)間的積累，所以點(diǎn)擊次數(shù)高，今年的點(diǎn)擊次數(shù)因?yàn)閯偘l(fā)生，所以累積起來的次數(shù)沒有去年的高，那么我們?nèi)绻腰c(diǎn)擊次數(shù)作為衡量，是不是應(yīng)該刪除的就是今年的？這就導(dǎo)致了新的進(jìn)不來舊的出不去

所以我們來看redis它是怎么實(shí)現(xiàn)的！怎么解決這個(gè)缺點(diǎn)！

我們還是來看我們的redisObject

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;

我們看它的lru，它如果被用作LFU的時(shí)候！它前面16位代表的是時(shí)間，后8位代表的是一個(gè)數(shù)值，frequency是頻率，應(yīng)該就是代表這個(gè)對(duì)象的訪問次數(shù)，我們先給它叫做counter。

那么這個(gè)16位的時(shí)間跟8位的counter到底有啥用呢？8位我們還能猜測(cè)下，可能就是這個(gè)對(duì)象的訪問次數(shù)！

我們淘汰的時(shí)候，是不是就是去根據(jù)這個(gè)對(duì)象使用的次數(shù)，按照小的就去給它淘汰掉。

其實(shí)，差不多就是這么個(gè)意思。

還有個(gè)問題，如果8位用作訪問次數(shù)的話，那么8位最大也就2的8次方，就是255次，夠么？如果，按照我們的想法，肯定不夠，那么redis去怎么解決呢？

既然不夠，那么讓它不用每次都加就可以了,能不能讓它值越大，我們加的越慢就能解決這個(gè)問題

redis還加了個(gè)東西，讓你們自己能主宰它加的速率，這個(gè)東西就是lfu-log-factor！它配置的越大，那么對(duì)象的訪問次數(shù)就會(huì)加的越慢。

源碼：

uint8_t LFULogIncr(uint8_t counter) {
	//如果已經(jīng)到最大值255，返回255 ，8位的最大值
	if (counter == 255) return 255;
	//得到隨機(jī)數(shù)（0-1）
	double r = (double)rand()/RAND_MAX;
	//LFU_INIT_VAL表示基數(shù)值（在server.h配置）
	double baseval = counter - LFU_INIT_VAL;
	//如果達(dá)不到基數(shù)值，表示快不行了，baseval =0
	if (baseval < 0) baseval = 0;
	//如果快不行了，肯定給他加counter
	//不然，按照幾率是否加counter，同時(shí)跟baseval與lfu_log_factor相關(guān)
	//都是在分子，所以2個(gè)值越大，加counter幾率越小
	double p = 1.0/(baseval*server.lfu_log_factor+1);
	if (r < p) counter++;
	return counter;
}

所以，LFU加的邏輯我們可以總結(jié)下：

（1）如果已經(jīng)是最大值，我們不再加！因?yàn)榈竭_(dá)255的幾率不是很高！可以支撐很大很大的數(shù)據(jù)量！

（2）counter屬于隨機(jī)添加，添加的幾率根據(jù)已有的counter值和配置lfu-log-factor相關(guān)，counter值越大，添加的幾率越小，lfu-log-factor配置的值越大，添加的幾率越小！

我們的這個(gè)16bit記錄的是這個(gè)對(duì)象的訪問時(shí)間的分單位的后16位，每次訪問或者操作的時(shí)候，都會(huì)去跟當(dāng)前時(shí)間的分單位的后16位去比較，得到多少分鐘沒有訪問了！然后去減去對(duì)應(yīng)的次數(shù)！

那么這個(gè)次數(shù)每分鐘沒訪問減多少了，就是根據(jù)我們的配置lfu-decay-time。

這樣就能夠?qū)崿F(xiàn)我們的LFU，并且還解決了LFU不能減的問題。

• 總結(jié)如圖：

貼出減的源碼：

unsigned long LFUDecrAndReturn(robj *o) {
	//lru字段右移8位，得到前面16位的時(shí)間
	unsigned long ldt = o->lru >> 8;
	//lru字段與255進(jìn)行&運(yùn)算（255代表8位的最大值），
	//得到8位counter值
	unsigned long counter = o->lru & 255;
	//如果配置了lfu_decay_time，用LFUTimeElapsed(ldt) 除以配置的值
	//LFUTimeElapsed(ldt)源碼見下
	//總的沒訪問的分鐘時(shí)間/配置值，得到每分鐘沒訪問衰減多少
	unsigned long num_periods = server.lfu_decay_time ?LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;
	if (num_periods)
	//不能減少為負(fù)數(shù)，非負(fù)數(shù)用couter值減去衰減值
	counter = (num_periods > counter) ? 0 : counter - num_periods;
	return counter;
}

LFUTimeElapsed方法源碼(evict.c)：

//對(duì)象ldt時(shí)間的值越小，則說明時(shí)間過得越久
unsigned long LFUTimeElapsed(unsigned long ldt) {
	//得到當(dāng)前時(shí)間分鐘數(shù)的后面16位
	unsigned long now = LFUGetTimeInMinutes();
	//如果當(dāng)前時(shí)間分鐘數(shù)的后面16位大于緩存對(duì)象的16位
	//得到2個(gè)的差值
	if (now >= ldt) return now-ldt;
	//如果緩存對(duì)象的時(shí)間值大于當(dāng)前時(shí)間后16位值，則用65535-ldt+now得到差值
	return 65535-ldt+now;
}

所以，LFU減邏輯我們可以總結(jié)下：

（1）我們可以根據(jù)對(duì)象的LRU字段的前16位得到對(duì)象的訪問時(shí)間（分鐘），根據(jù)跟系統(tǒng)時(shí)間比較獲取到多久沒有訪問過！

（2）根據(jù)lfu-decay-time（配置），代表每分鐘沒訪問減少多少counter，不能減成負(fù)數(shù)

區(qū)別

• LRU：最近最少使用頁(yè)面置換算法，淘汰最長(zhǎng)時(shí)間未被使用的頁(yè)面，看頁(yè)面最后一次被使用到發(fā)生調(diào)度的時(shí)間長(zhǎng)短，首先淘汰最長(zhǎng)時(shí)間未被使用的頁(yè)面。
• LFU：最近最不常用頁(yè)面置換算法，淘汰一定時(shí)期內(nèi)被訪問次數(shù)最少的頁(yè)，看一定時(shí)間段內(nèi)頁(yè)面被使用的頻率，淘汰一定時(shí)期內(nèi)被訪問次數(shù)最少的頁(yè)

舉個(gè)栗子：

• 某次時(shí)期Time為10分鐘，如果每分鐘進(jìn)行一次調(diào)頁(yè),主存塊為3,若所需頁(yè)面走向?yàn)? 1 2 1 2 3 4
• 假設(shè)到頁(yè)面4時(shí)會(huì)發(fā)生缺頁(yè)中斷
• 若按LRU算法,應(yīng)換頁(yè)面1(1頁(yè)面最久未被使用)，但按LFU算法應(yīng)換頁(yè)面3(十分鐘內(nèi),頁(yè)面3只使用了一次)
• 可見LRU關(guān)鍵是看頁(yè)面最后一次被使用到發(fā)生調(diào)度的時(shí)間長(zhǎng)短,而LFU關(guān)鍵是看一定時(shí)間段內(nèi)頁(yè)面被使用的頻率!

手寫LRU算法

底層shuju

• 使用LinkedHashMap實(shí)現(xiàn)

/**
 * @Description :
 * @Author : huangcong
 * @Date : 2023/6/28 9:48
 **/
public class LinkedHashMapLru<K, V> extends LinkedHashMap<K, V> {

    private Integer initialCapacity;

    public LinkedHashMapLru(Integer initialCapacity) {
        super(initialCapacity, 0.75F, Boolean.FALSE);
        this.initialCapacity = initialCapacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return super.size() > initialCapacity;
    }

    public Object getValue(Object key) {
        Object v = super.get(key);
        if (Objects.isNull(v)) {
            return -1;
        }
        return v;
    }

    public static void main(String[] args) {
        LinkedHashMapLru<Object, Object> hashMapLru = new LinkedHashMapLru<>(3);
        hashMapLru.put(1, "a");
        hashMapLru.put(2, "b");
        hashMapLru.put(3, "c");
        System.out.println(hashMapLru.entrySet());

        // key存在變更其數(shù)據(jù)
        hashMapLru.put(3, "l");
        System.out.println(hashMapLru.entrySet());

        // 當(dāng)緩存容量達(dá)到上限時(shí)，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最久未使用的數(shù)據(jù)值
        hashMapLru.put(4, "d");
        System.out.println(hashMapLru.entrySet());

        hashMapLru.put(5, "f");
        System.out.println(hashMapLru.entrySet());

        // 獲取數(shù)據(jù) get(key) - 如果關(guān)鍵字 (key) 存在于緩存中，則獲取關(guān)鍵字的值（總是正數(shù)），否則返回 -1
        Object value =hashMapLru.getValue(1);
        System.out.println(value);
    }
}

• 其他方式實(shí)現(xiàn)

/**
 * @Description : 構(gòu)造一個(gè)node節(jié)點(diǎn)，承載數(shù)據(jù)
 * @Author : hc
 * @Date : 2023/6/28 12:14
 **/
public class Node<K, V> {

    K key;

    V value;

    Node<K, V> pre;

    Node<K, V> next;

    public Node() {
    }

    public Node(K key, V value) {
        this.key = key;
        this.value = value;
        this.pre = this.next = null;
    }

    public void setKey(K key) {
        this.key = key;
    }

    public void setValue(V value) {
        this.value = value;
    }
}

/**
 * @Description :雙向鏈表
 * @Author : hc
 * @Date : 2023/6/28 12:23
 **/
public class LruCache <K,V>{

    Node<K,V> head;
    Node<K,V> tail;

    public LruCache() {
        head = new Node<>();
        tail = new Node<>();
        head.next = tail;
        tail.pre = head;
    }

    // 頭插法，靠近頭部的是最新的數(shù)據(jù)
    public void add(Node<K,V> node){
        node.next = head.next;
        node.pre = head;
        head.next.pre = node;
        head.next = node;
    }

    public void delete(Node<K,V> node){
        node.next.pre =node.pre;
        node.pre.next = node.next;
        node.next = null;
        node.pre = null;
    }

    public Node getNode(){
        return tail.pre;
    }

    // 打印鏈表
    public String getCache(){
        StringBuffer stringBuffer = new StringBuffer();
        Node<K, V> node = head.next;
        while (node != tail){
            stringBuffer.append(node.key+"="+node.value + "\r\n");
            node = node.next;
        }
        return stringBuffer.toString();
    }
}

/**
 * @Description :
 * hash表：通過hash函數(shù)計(jì)算出hash值，然后（hash值 % 數(shù)組大?。┑玫綄?duì)應(yīng)數(shù)組中的位置
 * @Author : hc
 * @Date : 2023/6/28 16:23
 **/
public class Lru {

    private Integer cacheSize; // 規(guī)定容器大小
    private Map<Integer,Node<Integer,Integer>> map; // hash表，方便查找
    private LruCache<Integer,Integer> doubleLinkedMap;// 雙向鏈表，方便插入以及刪除

    public Lru(Integer cacheSize) {
    this.cacheSize = cacheSize;
    map = new HashMap<>();
    doubleLinkedMap = new LruCache<>();
    }

    public int get(Integer key){
        if (!map.containsKey(key)){
            return -1;
        }
        Node<Integer, Integer> node = map.get(key);
        doubleLinkedMap.delete(node);
        doubleLinkedMap.add(node);
        return node.value;
    }

    public Integer put(Integer key,Integer value){
        // 如果哈希表中有，替換節(jié)點(diǎn)的value值
        if (map.containsKey(key)){
            Node<Integer, Integer> node = map.get(key);
            node.setValue(value);
            doubleLinkedMap.delete(node);
            doubleLinkedMap.add(node);
            return key;
        }
        Node<Integer, Integer> node = new Node<>(key, value);
        // 如果hash沒有，且容器中數(shù)據(jù)已經(jīng)達(dá)到了規(guī)定大小，刪除最后一個(gè)數(shù)據(jù)，在頭部添加一個(gè)最新數(shù)據(jù)
        if (map.size() >= cacheSize){
            Node lastNode = doubleLinkedMap.getNode();
            doubleLinkedMap.delete(lastNode);
            doubleLinkedMap.add(node);
            map.remove(key);
            map.put(key,node);
            return key;
        }
        // 如果hash沒有，且容器中數(shù)據(jù)未達(dá)到了規(guī)定大小，直接在頭部添加一個(gè)最新數(shù)據(jù)
        doubleLinkedMap.add(node);
        map.put(key,node);
        return key;
    }

    // 刪除節(jié)點(diǎn)
    public Integer delete(Integer key){
        if (!map.containsKey(key)){
            return -1;
        }
        Node<Integer, Integer> node = map.get(key);
        doubleLinkedMap.delete(node);
        map.remove(key);
        return key;
    }

    public static void main(String[] args) {
        Lru lru = new Lru(3);
        lru.put(1,1);
        lru.put(2,2);
        lru.put(3,3);
        System.out.println(lru.doubleLinkedMap.getCache());

        lru.put(2,4);
        System.out.println(lru.doubleLinkedMap.getCache());

        lru.put(4,4);
        System.out.println(lru.doubleLinkedMap.getCache());

        int i = lru.get(3);
        System.out.println(i);
        System.out.println(lru.doubleLinkedMap.getCache());
    }
}

運(yùn)行結(jié)果：

3=3
2=2
1=1

2=4
3=3
1=1

4=4
2=4
3=3

3
3=3
4=4
2=4

總結(jié)

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

最新評(píng)論