Redis 為何使用近似 LRU 演算法淘汰資料，而不是真實 LRU？_鼓樓丶

我們知道 Redis 快取滿了之後能通過淘汰策略刪除資料騰出空間給新資料。

淘汰策略如下所示：

編輯

redis記憶體淘汰

設定過期時間的 key

volatile-ttl、volatile-random、volatile-lru、volatile-lfu 這四種策略淘汰的資料範圍是設定了過期時間的資料。

所有的 key

allkeys-lru、allkeys-random、allkeys-lfu 這三種淘汰策略無論這些鍵值對是否設定了過期時間，當記憶體不足都會進行淘汰。

這就意味著，即使它的過期時間還沒到，也會被刪除。當然，如果已經過了過期時間，即使沒有被淘汰策略選中，也會被刪除。

volatile-ttl 和 volatile-randon 很簡單，重點在於 volatile-lru 和 volatile-lfu，他們涉及到 LRU 演算法和 LFU 演算法。

近似 LRU 演算法

❝

什麼是 LRU 演算法呢？

LRU 演算法的全程是 Least Rencently Used，顧名思義就是按照最近最久未使用的演算法進行資料淘汰。

核心思想「如果該資料最近被訪問，那麼將來被訪問的機率也更高」。

我們把所有的資料組織成一個連結串列：

MRU：表示連結串列的表頭，代表著最近最常被訪問的資料；
LRU：表示連結串列的表尾，代表最近最不常使用的資料。

編輯

LRU 演算法

可以發現，LRU 更新和插入新資料都發生在連結串列首，刪除資料都發生在連結串列尾。

被訪問的資料會被移動到 MRU 端，被訪問的資料之前的資料則相應往後移動一位。

❝

使用單鏈表可以麼？

如果選用單鏈表，刪除這個結點，需要 O(n) 遍歷一遍找到前驅結點。所以選用雙向連結串列，在刪除的時候也能 O(1) 完成。

❝

Redis 使用該 LRU 演算法管理所有的快取資料麼？

不是的，由於 LRU 演算法需要用連結串列管理所有的資料，會造成大量額外的空間消耗。

除此之外，大量的節點被訪問就會帶來頻繁的連結串列節點移動操作，從而降低了 Redis 效能。

所以 Redis 對該演算法做了簡化，Redis LRU 演算法並不是真正的 LRU，Redis 通過對少量的 key 取樣，並淘汰取樣的資料中最久沒被訪問過的 key。

這就意味著 Redis 無法淘汰資料庫最久訪問的資料。

Redis LRU 演算法有一個重要的點在於可以更改樣本數量來調整演算法的精度，使其近似接近真實的 LRU 演算法，同時又避免了記憶體的消耗，因為每次只需要取樣少量樣本，而不是全部資料。

配置如下：

maxmemory-samples 50

執行原理

大家還記得麼，資料結構 redisObject 中有一個 lru 欄位，用於記錄每個資料最近一次被訪問的時間戳。

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

Redis 在淘汰資料時，第一次隨機選出 N 個數據放到候選集合，將 lru 欄位值最小的資料淘汰。

當再次需要淘汰資料時，會重新挑選資料放入第一次建立的候選集合，不過有一個挑選標準：進入該集合的資料的 lru 的值必須小於候選集合中最小的 lru 值。

如果新資料進入候選集合的個數達到了 maxmemory-samples 設定的值，那就把候選集合中 lru 最小的資料淘汰。

這樣就大大減少連結串列節點數量，同時不用每次訪問資料都移動連結串列節點，大大提升了效能。

Java 實現 LRU Cahce

LinkedHashMap 實現

完全利用 Java 的LinkedHashMap實現，可以採用組合或者繼承的方式實現，「碼哥」使用組合的形式完成。

``` public class LRUCache { private Map map; private final int cacheSize;

public LRUCache(int initialCapacity) { map = new LinkedHashMap(initialCapacity, 0.75f, true) { @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > cacheSize; } }; this.cacheSize = initialCapacity; } } ```

重點在於 LinkedHashMap的第三個建構函式上，要把這個構造引數accessOrder設為 true，代表LinkedHashMap內部維持訪問順序。

另外，還需要重寫removeEldestEntry()，這個函式如果返回true，代表把最久未被訪問的節點移除，從而實現淘汰資料。

自己實現

其中程式碼是從 LeetCode 146. LRU Cache 上摘下來的。程式碼裡面有註釋。

``` import java.util.Map; import java.util.concurrent.ConcurrentHashMap;

/* * 在鏈頭放最久未被使用的元素，鏈尾放剛剛新增或訪問的元素 / class LRUCache { class Node { int key, value; Node pre, next;

Node(int key, int value) { this.key = key; this.value = value; pre = this; next = this; } }

private final int capacity;// LRU Cache的容量 private Node dummy;// dummy節點是一個冗餘節點，dummy的next是連結串列的第一個節點，dummy的pre是連結串列的最後一個節點 private Map cache;//儲存key-Node對，Node是雙向連結串列節點

public LRUCache(int capacity) { this.capacity = capacity; dummy = new Node(0, 0); cache = new ConcurrentHashMap<>(); }

public int get(int key) { Node node = cache.get(key); if (node == null) return -1; remove(node); add(node); return node.value; }

public void put(int key, int value) { Node node = cache.get(key); if (node == null) { if (cache.size() >= capacity) { cache.remove(dummy.next.key); remove(dummy.next); } node = new Node(key, value); cache.put(key, node); add(node); } else { cache.remove(node.key); remove(node); node = new Node(key, value); cache.put(key, node); add(node); } }

/* * 在連結串列尾部新增新節點 * * @param node 新節點 / private void add(Node node) { dummy.pre.next = node; node.pre = dummy.pre; node.next = dummy; dummy.pre = node; }

/* * 從雙向連結串列中刪除該節點 * * @param node 要刪除的節點 / private void remove(Node node) { node.pre.next = node.next; node.next.pre = node.pre; } } ```