Redis記憶體淘汰機制（包括LRU原理和實作）

背景

Redis采用的過期政策是

定期删除

+

惰性删除

，但由于定期删除的随機性和惰性删除的被動性，仍然可能出現大量過期key堆積在記憶體裡，導緻redis的記憶體快耗盡。

為了避免這種情況，redis的記憶體資料集大小上升到一定大小的時候，就會開啟

記憶體淘汰

功能。

Redis提供了下面幾種記憶體淘汰政策供使用者選擇：

• noeviction：當記憶體使用達到門檻值的時候，所有引起申請記憶體的指令會報錯。
• allkeys-lru：在主鍵空間中，優先移除最近未使用的key。
• allkeys-random：在主鍵空間中，随機移除某個key。
• volatile-lru：在設定了過期時間的鍵空間中，優先移除最近未使用的key。
• volatile-random：在設定了過期時間的鍵空間中，随機移除某個key。
• volatile-ttl：在設定了過期時間的鍵空間中，具有更早過期時間的key優先移除。

其中allkeys-lru政策是最推薦，最常使用的。

LRU

1. LRU緩存的思想

• 固定緩存大小，需要給緩存配置設定一個固定的大小。
• 每次讀取緩存都會改變緩存的使用時間，将緩存的存在時間重新重新整理。
• 需要在緩存滿了後，将最近最久未使用的緩存删除，再添加最新的緩存。

2. 實作思路

基于HashMap和雙向連結清單實作LRU緩存。

其中head代表雙向連結清單的頭部，tail代表尾部。

首先預先設定LRU的容量，如果存儲滿了，則删除雙向連結清單的尾部，每次新增和通路資料，則把新的節點增加到頭部，或者把已經存在的節點移動到頭部。

3. Java代碼

import java.util.HashMap;

class DLinkedNode {
    String key;
    int value;
    DLinkedNode pre;
    DLinkedNode next;
}

public class LRUCache {
	 private HashMap cache = new HashMap();
	 private int count;
	 private int capacity;
	 private DLinkedNode head, tail;
	 
	 public LRUCache(int capacity) {
		 this.count = 0;
		 this.capacity = capacity;
		 head = new DLinkedNode();
		 tail = new DLinkedNode();
		 head.next = tail;
		 tail.pre = head;
	 }
	 
	 public int get(String key) {
		 DLinkedNode node = (DLinkedNode) cache.get(key);
		 if(node == null){
		     return -1; // 若通路的節點不存在，傳回-1
		 }
		 // 将被通路的節點移動到頭部
		 this.moveToHead(node);
		 return node.value;
	 }
	 
	 public void set(String key, int value) {
		 DLinkedNode node = (DLinkedNode) cache.get(key);
		 if(node == null){
		     DLinkedNode newNode = new DLinkedNode();
		     newNode.key = key;
		     newNode.value = value;
		     this.cache.put(key, newNode);
		     this.addNode(newNode);
		     ++count;
		     if(count > capacity){
		         // 移除尾部節點
		         DLinkedNode tail = this.popTail();
		         this.cache.remove(tail.key);
		         --count;
		     }
		 }else{
		     // 更新value.
		     node.value = value;
		     this.moveToHead(node);
		 }
	 }
	 
	/**
	* 在頭節點後添加新節點
	*/
	private void addNode(DLinkedNode node){
		node.pre = head;
		node.next = head.next;
		head.next.pre = node;
		head.next = node;
	}
	
	/**
	* 從連結清單中删除存在的節點
	*/
	private void removeNode(DLinkedNode node){
		DLinkedNode pre = node.pre;
		DLinkedNode next = node.next;
		pre.next = next;
		next.pre = pre;
	}
	
	/**
	* 将節點移動到頭部
	*/
	private void moveToHead(DLinkedNode node){
		this.removeNode(node);
		this.addNode(node);
	}
	
	// 移除尾部節點
	private DLinkedNode popTail(){
		DLinkedNode res = tail.pre;
		this.removeNode(res);
		return res;
	}
	
	@Override
	public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        DLinkedNode node = head.next;
        while (node.next != null) {
            stringBuilder.append(String.format("%s:%d ", node.key, node.value));
            node = node.next;
        }
        return stringBuilder.toString();
	}
		
	public static void main(String[] args) {
		LRUCache lruCache = new LRUCache(3);//緩存容量為3
		lruCache.set("1", 1);
		lruCache.set("2", 2);
		lruCache.set("3", 3);
		System.out.println("初始緩存\n"+lruCache);
		lruCache.get("2");
		System.out.println("通路Key為2的緩存\n"+lruCache);
		lruCache.get("1");
		System.out.println("通路Key為1的緩存\n"+lruCache);
		lruCache.set("4", 4);
		System.out.println("添加Key為4的緩存\n"+lruCache);
	}
}
           

• 輸出結果

  

Redis的LRU實作

如果按照HashMap和雙向連結清單實作，需要額外的存儲存放next和prev指針，犧牲比較大的存儲空間，顯然是不劃算的。

是以Redis采用了一個近似的做法，就是随機取出若幹個key，即基于server.maxmemory_samples配置選取固定數目的key，然後比較它們的lru通路時間，然後淘汰最近最久沒有通路的key，maxmemory_samples的值越大，Redis的近似LRU算法就越接近于嚴格LRU算法，但是相應消耗也變高，對性能有一定影響，樣本值預設為5。