從記憶體淘汰政策和過期鍵删除來聊一聊Redis記憶體管理機制
我們說過Redis是基于記憶體操作的資料庫，所有的資料儲存在記憶體中，是以讀寫速度非常的快。既然資料都存放在記憶體中，記憶體畢竟有限，遠遠比不上磁盤的存儲空間，是以如果不及時清理掉一部分沒有用的資料，就會導緻記憶體不足。這篇文章就來聊一聊Redis記憶體淘汰政策和過期鍵的删除。
Redis是可以在redis.conf這個配置檔案中設定最大占用記憶體的，如果不設定最大記憶體大小或者設定最大記憶體大小為0，在64位作業系統下不限制記憶體大小，在32位作業系統下最多使用3GB記憶體。一般生産環境設定記憶體為最大實體記憶體的四分之三。
當然也可以直接通過指令
maxmemory
來設定最大占用記憶體
通過
info memory
指令可以檢視redis記憶體使用情況
如果說超過了設定的最大占用記憶體，在沒有設定過期時間的情況下，就會導緻OOM記憶體溢出
Redis為了防止OOM的發生就自己的一套記憶體淘汰政策
- noeviction：不會删除任何的key，當記憶體不足時寫入新的資料，直接報OOM異常
- allkeys-lru：對所有的key使用LRU算法進行删除
- volatile-lru：對所有設定了過期時間的key使用LRU算法進行删除
- allkeys-lfu：對所有key使用LFU算法進行删除
- volatile-lfu：對所有設定了過期時間的key使用LFU算法進行删除
- allkeys-random：對所有key随機删除
- volatile-random：對所有設定了過期時間的key随機删除
- volatile-ttl：删除馬上要過期的key
一共8種記憶體淘汰政策，你可能想這麼多怎麼記得住？
不要慌，我們可以兩個次元、四個方面來考慮
兩個次元：
- 從過期鍵中選擇
- 從所有鍵中選擇
4個方面：
- LRU：最近最少使用
- LFU：使用最不頻繁
- random：随機
- ttl：存活時間
我們先說說這4個方面，random沒什麼好說的，就是随機選擇呗，再就是ttl存活時間，看哪個key最快過期，也就是剩下的存活時間最短，就把這個key删除。是以把重心放在LRU算法和LFU算法上。
LRU算法
LRU指的是最近最少使用，Redis實際上使用的是一種近似的LRU算法，跟LRU算法還不太一樣。之是以不使用LRU算法，是因為實作LRU算法需要維護一個連結清單，會消耗大量的額外記憶體，而近似LRU算法使用的是随機采樣法來淘汰元素。
近似LRU算法會給每個key增加一個額外的長度為24bit的小字段，也就是用來記錄最後一次被通路的時間戳。當Redis執行寫操作時，如果記憶體超出設定的最大占用記憶體，就會執行一次LRU記憶體淘汰算法。會随機采樣出5（預設）個key，然後淘汰掉最舊的key，如果淘汰後記憶體還是超出最大記憶體，那就繼續随機采樣淘汰，直到記憶體夠用為止。
采樣值越大，近似LRU算法的性能就會越接近嚴格的LRU算法，而且Redis還在近似LRU算法中，增加了淘汰池，淘汰池是一個大小為采樣值的數組，在每一次淘汰循環中，新的随機得出的key清單會和淘汰池中的清單進行融合，然後淘汰掉最舊的那一個key，保留剩下的比較舊的key放入到淘汰池中等待下一次的比較淘汰。
LRU算法的底層實作一般都是使用HashMap+雙向連結清單來實作的
第一種方法，我們可以直接繼承LinkedHashMap這個類，直接API實作，這個類相當于一個天然的LRU算法的實作類
第二種方法就是純手寫了，使用HashMap+雙向連結清單實作，HashMap集合用來存放key-Node(key/value)，連結清單中每一個節點都封裝一個key/value鍵值對，連結清單尾節點始終是要删除的那個節點，也就是最近最少使用的那個節點，而頭節點是新插入進來的節點。
public class LRUCacheDemo2 {
class Node<K, V> {
K key;
V value;
Node<K, V> prev;
Node<K, V> next;
public Node() {
this.prev = this.next = null;
}
public Node(K key, V value) {
this.key = key;
this.value = value;
this.prev = this.next = null;
}
}
class DoubleLinkedList<K, V> {
Node<K, V> head;
Node<K, V> tail;
public DoubleLinkedList() {
head = new Node<>();
tail = new Node<>();
head.next = tail;
tail.prev = head;
}
//頭插法，新添加的節點成為頭節點
public void addHead(Node<K, V> node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
//把剛通路過的節點移除
public void removeNode(Node<K, V> node) {
node.next.prev = node.prev;
node.prev.next = node.next;
node.next = null;
node.prev = null;
}
public Node getLast() {
return tail.prev;
}
}
private int cacheSize;
Map<Integer, Node<Integer, Integer>> map;
DoubleLinkedList<Integer, Integer> doubleLinkedList;
public LRUCacheDemo2(int cacheSize) {
this.cacheSize = cacheSize;
map = new HashMap<>();
doubleLinkedList = new DoubleLinkedList<>();
}
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
//get操作相當于通路一個節點，把剛剛通路的節點删除，然後重新插入到頭節點的位置，相當于這個節點最近剛通路過，這樣連結清單尾節點就是最少使用的那個節點
Node<Integer, Integer> node = map.get(key);
doubleLinkedList.removeNode(node);
doubleLinkedList.addHead(node);
return node.value;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
Node<Integer, Integer> node = map.get(key);
node.value = value;
map.put(key, node);
//如果key已存在，相當于更新了value值，也相當于最近剛剛通路了一個節點，是以需要再把這個節點移動到頭節點位置
doubleLinkedList.removeNode(node);
doubleLinkedList.addHead(node);
} else {
//如果超出記憶體大小，就先删除尾節點，也就是最近最少使用的那個節點，然後在map和連結清單中添加這個新節點
if (map.size() == cacheSize) {
Node lastNode = doubleLinkedList.getLast();
map.remove(lastNode.key);
doubleLinkedList.removeNode(lastNode);
}
Node<Integer, Integer> node = new Node<>(key, value);
map.put(key, node);
doubleLinkedList.addHead(node);
}
}
}
LFU算法
LFU算法指的是淘汰最近通路頻率最低的那個key，比LRU算法更加精準的表示了一個key被通路的熱度。如果一個key長時間不被通路，隻是剛剛偶爾被通路了一下，那麼在LRU算法下，這個偶爾被通路的key是不容易被淘汰掉的，但是使用LFU算法，需要計算最近一段時間内這個key的通路頻率，即使某個key被偶爾通路，也很有可能被淘汰掉。
Redis的所有對象頭結構中都有一個24bit的小字段，LRU算法用來記錄最後一次被通路的時間戳，實際上就是通過比較對象的空閑時間來決定哪個key被淘汰的。
而LFU算法，24bit用來存儲兩個值，分别是ldt和logc
8bit的logc用來存儲通路頻次，存儲的是頻次的對數值，并且這個值會随着時間衰減，如果它的值比較小，就很容易被回收。為了確定新建立的對象不被回收，新對象會被初始化為一個大于零的值嗎，預設為5。
16bit的ldt用來存儲上一次logc的更新時間，它取得是分鐘時間戳對2的16次方取模。同LRU模式一樣，也可以計算出對象的空閑時間。與LRU模式不同的是，ldt不是在對象被通路時更新的，而是在redis的淘汰邏輯進行時進行更新的。每次淘汰都是随機政策，随機挑選出若幹個key，更新這個key的“熱度“。淘汰掉”熱度“最低的key。
ldt更新的同時也會一同衰減logc的值。
衰減算法是：（将現有的logc值-對象的空閑時間）/ 衰減系數（預設為1）
換句話說，LFU算法和LRU算法相比，實際上LRU算法對象頭結構中的24bit的字段全用來記錄更新的時間戳，而LFU相當于切分出來了8bit用來記錄通路的次數，有了更新的時間戳，有了通路次數，是以LFU算法就能根據計算出的通路頻率來淘汰通路頻率最低的那個key了。
記憶體淘汰政策的4個方面中最重要的LRU和LFU我們已經講完了，接下來我們就從兩個次元來繼續來講講記憶體淘汰政策。從所有鍵中選擇進行淘汰，這個次元沒有什麼好說的，淘汰政策面對所有key都一視同仁，是以我們主要來說一說從過期鍵中選擇需要淘汰的key。
我們一般在向Redis資料庫中儲存一個資料的時候，會設定資料的過期時間，因為畢竟記憶體是有限的，如果資料沒有設定過期時間，那麼這個資料就會一直存在于記憶體中，遲早記憶體會被耗盡報OOM。我們可以使用
expire
指令給指定key設定過期時間，使用
ttl
指令檢視key還有多長時間過期，到期的key會被删除掉。
設定過期時間除了能夠清除沒有的資料，釋放記憶體，還有一些業務場景會需要設定過期時間，比如驗證碼1分鐘之内有效，使用者登入網站token一天之内有效等等。那麼Redis到底是如何判斷資料是否過期的呢？
實際上Redis是通過一個叫做過期字典來儲存資料的過期時間的，我們之前文章講過，字典的底層實作實際上是Hash表。過期字典的key指向資料庫中某個key，過期字典的value則是一個long long類型的整數，用來儲存key所指向的資料庫中的對應的key的過期時間
typedef struct redisDb {
...
dict *dict; //資料庫鍵空間,儲存着資料庫中所有鍵值對
dict *expires // 過期字典,儲存着鍵的過期時間
...
} redisDb;
那麼如果Redis判斷某個資料已經到期了，Redis是如何删除掉這個資料的呢？這就涉及到了過期鍵的删除政策。
定時删除政策
在設定鍵的過期時間的同時，建立一個定時器，讓定時器在鍵的過期時間來臨時，立即執行對鍵的删除操作。立即删除能夠保證記憶體中資料的最大新鮮度，也就是說能夠及時的删除過期資料釋放記憶體。但是删除操作會占用CPU，如果CPU本來就忙于處理自己的任務，還需要擠出時間來執行删除操作，會造成CPU額外的壓力，尤其是同一時間大量的資料過期，就會占用CPU相當長的一段時間。
是以說定時删除政策對記憶體是友好的，但是對CPU是不友好的，相當于拿時間換空間。
惰性删除政策
當資料到達過期時間時，我們可以先不做删除處理，等待下一次再次通路這個資料時，再進行删除操作。這有點像懶漢式的單例模式。但是這種惰性删除有一個問題，如果一個鍵過期了，這個鍵占用的記憶體空間并不會及時的得到釋放，如果同一時間有大量鍵過期，并且這些過期鍵又恰好在一段時間内沒有再被通路過，那麼就會導緻這些過期鍵不會被删除，記憶體也得不到釋放，從某種程度上來說可以将這種情況看作是記憶體洩漏。
惰性删除隻會在再次通路這個鍵的時候才進行删除，這對CPU是友好的，但是這會使得記憶體不能得到及時的釋放，是對記憶體不友好的。相當于拿空間換時間。
定期删除政策
定期删除政策是對上述兩種方法的折中。定期删除政策會每隔一段時間執行一次删除過期資料的操作，并通過限制删除操作執行的時長和頻率來減少删除操作對占用CPU時間的影響。
定期删除政策的難點在于如何确定删除操作執行的時長和頻率。
Redis預設每秒進行10次過期掃描，過期掃描不會周遊過期字典中的所有的key，而是采用了一種随機采樣的方式：
- 從過期字典中随機選出20個key
- 删除20個key中已經過期的key
- 如果過期的key比例超過1/4，則繼續随機選出20個key再次掃描
是以說定期指的是周期性，删除指的是随機抽查删除，定期删除就是周期性的抽查key，删除已過期的key。
當然，定期删除雖然結合了定時删除和惰性删除，但也不是完美的。如果定期删除時，某些key從來沒有被抽查到過，就會導緻大量過期的key堆積在記憶體中，導緻Redis記憶體不能得到及時的釋放。
從過期鍵的3種删除政策可以看出，雖然能夠比較有效的删除已經過期的資料，但是總會漏掉一些沒能及時删除的過期鍵，造成記憶體不能及時釋放，也就是說很可能會發生OOM，隻不過是時間問題罷了。這時候就需要我們上面講的Redis記憶體淘汰機制來兜底了。
是以，Redis過期鍵删除政策和記憶體淘汰政策共同形成了Redis記憶體管理機制！