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 算法。

今天碼哥帶大家一起搞定 Redis 的 LRU 算法…

近似 LRU 算法

什麼是 LRU 算法呢？

LRU

算法的全程是

Least Rencently Used

，顧名思義就是按照最近最久未使用的算法進行資料淘汰。

核心思想「如果該資料最近被通路，那麼将來被發放穩的幾率也更高」。

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

• MRU：表示連結清單的表頭，代表着最近最常被通路的資料；
• 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
           

運作原理

大家還記得麼，資料結構

redisObjec

t 中有一個

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<K, V> {
    private Map<K, V> map;
    private final int cacheSize;

    public LRUCache(int initialCapacity) {
        map = new LinkedHashMap<K, V>(initialCapacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> 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<Integer, Node> 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;
    }
}

           

不要吝啬贊美，當别人做的不錯，就給予他正回報。少關注用「贊美」投票的事情，而應該去關注用「交易」投票的事情。

判斷一個人是否牛逼，不是看網上有多少人誇贊他，而是要看有多少人願意跟他發生交易或贊賞、支付、下單。

因為贊美太廉價，而願意與他發生交易的才是真正的信任和支援。

碼哥到現在已經寫了近 23+ 篇 Redis 文章，贈送了很多書籍，收到過許多贊美和少量贊賞，感謝曾經贊賞過我的讀者，謝謝。

我是「碼哥」，大家可以叫我靓仔，好文請點贊，關于 LFU 算法，我們下一篇見。

曆史好文

• Redis 記憶體滿了怎麼辦？
• Redis 的過期資料會被立馬删除麼？
• Redis 緩存擊穿（失效）、緩存穿透、緩存雪崩怎麼解決？

參考文獻

https://redis.io/docs/manual/eviction/

http://antirez.com/news/109