PS:本文已收錄到1.1K Star數(shù)開源學(xué)習(xí)指南——《大廠面試指北》，如果想要了解更多大廠面試相關(guān)的內(nèi)容及獲取《大廠面試指北》離線PDF版，請掃描下方二維碼碼關(guān)注公眾號“大廠面試”，謝謝大家了！項目地址：http://notfound9.github.io/interviewGuide/#/docs/BATInterview
《大廠面試指北》項目截圖：
獲取《大廠面試指北》離線PDF版，請掃描下方二維碼關(guān)注公眾號“大廠面試”
【大廠面試02期】Redis過期key是怎么樣清理的？
在Redis中，對于過期key的清理主要有惰性清除，定時清理，內(nèi)存不夠時清理三種方法，下面我們就來具體看看這三種清理方法。
(1)惰性清除
在訪問key時，如果發(fā)現(xiàn)key已經(jīng)過期，那么會將key刪除。
(2)定時清理
Redis配置項hz定義了serverCron任務(wù)的執(zhí)行周期，默認(rèn)每次清理時間為25ms，每次清理會依次遍歷所有DB，從db隨機取出20個key，如果過期就刪除，如果其中有5個key過期，那么就繼續(xù)對這個db進(jìn)行清理，否則開始清理下一個db。
(3)內(nèi)存不夠時清理
當(dāng)執(zhí)行寫入命令時，如果發(fā)現(xiàn)內(nèi)存不夠，那么就會按照配置的淘汰策略清理內(nèi)存，淘汰策略一般有6種，Redis4.0版本后又增加了2種，主要由分為三類
-
第一類 不處理，等報錯(默認(rèn)的配置)
- noeviction，發(fā)現(xiàn)內(nèi)存不夠時，不刪除key，執(zhí)行寫入命令時直接返回錯誤信息。（Redis默認(rèn)的配置就是noeviction）
-
第二類 從所有結(jié)果集中的key中挑選，進(jìn)行淘汰
- allkeys-random 就是從所有的key中隨機挑選key，進(jìn)行淘汰
- allkeys-lru 就是從所有的key中挑選最近使用時間距離現(xiàn)在最遠(yuǎn)的key，進(jìn)行淘汰
- allkeys-lfu 就是從所有的key中挑選使用頻率最低的key，進(jìn)行淘汰。（這是Redis 4.0版本后新增的策略）
-
第三類 從設(shè)置了過期時間的key中挑選，進(jìn)行淘汰
這種就是從設(shè)置了expires過期時間的結(jié)果集中選出一部分key淘汰，挑選的算法有：
volatile-random 從設(shè)置了過期時間的結(jié)果集中隨機挑選key刪除。
volatile-lru 從設(shè)置了過期時間的結(jié)果集中挑選上次使用時間距離現(xiàn)在最久的key開始刪除
volatile-ttl 從設(shè)置了過期時間的結(jié)果集中挑選可存活時間最短的key開始刪除(也就是從哪些快要過期的key中先刪除)
volatile-lfu 從過期時間的結(jié)果集中選擇使用頻率最低的key開始刪除（這是Redis 4.0版本后新增的策略）
LRU算法
LRU算法的設(shè)計原則是如果一個數(shù)據(jù)近期沒有被訪問到，那么之后一段時間都不會被訪問到。所以當(dāng)元素個數(shù)達(dá)到限制的值時，優(yōu)先移除距離上次使用時間最久的元素。
可以使用雙向鏈表Node+HashMap<String, Node>來實現(xiàn)，每次訪問元素后，將元素移動到鏈表頭部，當(dāng)元素滿了時，將鏈表尾部的元素移除，HashMap主要用于根據(jù)key獲得Node以及添加時判斷節(jié)點是否已存在和刪除時快速找到節(jié)點。
PS:使用單向鏈表能不能實現(xiàn)呢，也可以，單向鏈表的節(jié)點雖然獲取不到pre節(jié)點的信息，但是可以將下一個節(jié)點的key和value設(shè)置在當(dāng)前節(jié)點上，然后把當(dāng)前節(jié)點的next指針指向下下個節(jié)點，這樣相當(dāng)于把下一個節(jié)點刪除了
//雙向鏈表
public static class ListNode {
String key;//這里存儲key便于元素滿時，刪除尾節(jié)點時可以快速從HashMap刪除鍵值對
Integer value;
ListNode pre = null;
ListNode next = null;
ListNode(String key, Integer value) {
this.key = key;
this.value = value;
}
}
ListNode head;
ListNode last;
int limit=4;
HashMap<String, ListNode> hashMap = new HashMap<String, ListNode>();
public void add(String key, Integer val) {
ListNode existNode = hashMap.get(key);
if (existNode!=null) {
//從鏈表中刪除這個元素
ListNode pre = existNode.pre;
ListNode next = existNode.next;
if (pre!=null) {
pre.next = next;
}
if (next!=null) {
next.pre = pre;
}
//更新尾節(jié)點
if (last==existNode) {
last = existNode.pre;
}
//移動到最前面
head.pre = existNode;
existNode.next = head;
head = existNode;
//更新值
existNode.value = val;
} else {
//達(dá)到限制，先刪除尾節(jié)點
if (hashMap.size() == limit) {
ListNode deleteNode = last;
hashMap.remove(deleteNode.key);
//正是因為需要刪除，所以才需要每個ListNode保存key
last = deleteNode.pre;
deleteNode.pre = null;
last.next = null;
}
ListNode node = new ListNode(key,val);
hashMap.put(key,node);
if (head==null) {
head = node;
last = node;
} else {
//插入頭結(jié)點
node.next = head;
head.pre = node;
head = node;
}
}
}
public ListNode get(String key) {
return hashMap.get(key);
}
public void remove(String key) {
ListNode deleteNode = hashMap.get(key);
ListNode preNode = deleteNode.pre;
ListNode nextNode = deleteNode.next;
if (preNode!=null) {
preNode.next = nextNode;
}
if (nextNode!=null) {
nextNode.pre = preNode;
}
if (head==deleteNode) {
head = nextNode;
}
if (last == deleteNode) {
last = preNode;
}
hashMap.remove(key);
}
LFU算法
LFU算法的設(shè)計原則時，如果一個數(shù)據(jù)在最近一段時間被訪問的時次數(shù)越多，那么之后被訪問的概率會越大，基本實現(xiàn)是每個數(shù)據(jù)都有一個引用計數(shù)，每次數(shù)據(jù)被訪問后，引用計數(shù)加1，需要淘汰數(shù)據(jù)時，淘汰引用計數(shù)最小的數(shù)據(jù)。在Redis的實現(xiàn)中，每次key被訪問后，引用計數(shù)是加一個介于0到1之間的數(shù)p，并且訪問越頻繁p值越大，而且在一定的時間間隔內(nèi)，
如果key沒有被訪問，引用計數(shù)會減少。
最后
大家有什么想法，可以一起討論！
