一文詳解Redis中的LRU演算法

這篇文章帶大家了解Redis中的LRU（Least Recently Used），希望對大家有幫助！

Redis是基於記憶體儲存的key-value資料庫，我們知道記憶體雖然快但空間小，當實體記憶體達到上限時，系統就會跑的很慢，這是因為swap機制會將部分內存的數據轉移到swap分區中，通過與swap的交換保證系統繼續運行；但是swap屬於硬碟存儲，速度遠遠比不上內存，尤其是對於Redis這種QPS非常高的服務，發生這種情況是無法接收的。 （注意如果swap分割記憶體也滿了，系統就會發生錯誤！）【相關推薦：Redis影片教學】

Linux作業系統可以透過free -m查看swap大小:\

因此如何防止Redis發生這種情況非常重要（面試官問到Redis幾乎沒有不問這個知識點的）。

2、maxmemory配置

Redis針對上述問題提供了maxmemory配置，這個配置可以指定Redis記憶體的最大資料集，通常情況都是在redis.conf檔中進行配置，也可以運作時使用CONFIG SET指令進行一次性配置。
redis.conf檔案中的設定項目示意圖：\

#預設情況maxmemory設定項並未啟用，Redis官方介紹64位元操作系統預設無記憶體限制，32位元作業系統預設3GB隱式記憶體配置，若maxmemory 為0，代表記憶體不受限。

因此我們在做快取架構時，要根據硬體資源 業務需求做適合的maxmemory配置。

3、記憶體達到maxmemory怎麼辦

很顯然配置了最大內存，當maxmemory達到了最大上限之後Redis不可能不干活了，那麼Redis是怎麼來處理這個問題的呢？這就是本文的重點，Redis 提供了maxmemory-policy淘汰策略（本文只講述LRU不涉及LFU，LFU在下一篇文章講述），對滿足條件的key進行刪除，辭舊迎新。
maxmemory-policy淘汰策略：

• noeviction： 當達到記憶體限制並且客戶端嘗試執行可能導致使用更多記憶體的命令時回傳錯誤，簡單來說讀取操作仍然允許，但是不准寫入新的數據，del（刪除）請求可以。
• allkeys-lru： 從全體key中，透過lru（Least Recently Used - 最近最少使用）演算法進行淘汰
• allkeys-random： 從全體key中，隨機進行淘汰
• volatile-lru： 從設定了過期時間的全部key中，透過lru（Least Recently Used - 最近最少使用）演算法進行淘汰，這樣可以保證未設定過期時間需要被持久化的數據，不會被選中淘汰
• volatile-random： 從設定了過期時間的全部key中，隨機進行淘汰
• volatile-ttl： 從設定了過期時間的全部key中，透過比較key的剩餘過期時間TTL的值，TTL越小越先被淘汰

#還有volatile-lfu/allkeys-lfu這個留到下文一起探討，兩個演算法不一樣！

random隨機淘汰只需要隨機取一些key來刪除，釋放記憶體空間即可；ttl過期時間小先淘汰也可以透過比較ttl的大小，將ttl值小的key刪除，釋放記憶體空間即可。
那LRU是怎麼實現的呢？ Redis又是如何知道哪個key最近被使用了，哪個key最近沒有被使用呢？

4、LRU演算法實作

我們先用Java的容器實作一個簡單的LRU演算法，我們使用ConcurrentHashMap做key-value結果儲存元素的映射關係，使用ConcurrentLinkedDeque來維持key的訪問順序。
LRU實作程式碼：

package com.lizba.redis.lru;

import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedDeque;

/**
 * <p>
 *      LRU简单实现
 * </p>
 *
 * @Author: Liziba
 * @Date: 2021/9/17 23:47
 */
public class SimpleLru {

    /** 数据缓存 */
    private ConcurrentHashMap<string> cacheData;
    /** 访问顺序记录 */
    private ConcurrentLinkedDeque<string> sequence;
    /** 缓存容量 */
    private int capacity;

    public SimpleLru(int capacity) {
        this.capacity = capacity;
        cacheData = new ConcurrentHashMap(capacity);
        sequence = new ConcurrentLinkedDeque();
    }


    /**
     * 设置值
     *
     * @param key
     * @param value
     * @return
     */
    public Object setValue(String key, Object value) {
        // 判断是否需要进行LRU淘汰
        this.maxMemoryHandle();
        // 包含则移除元素，新访问的元素一直保存在队列最前面
        if (sequence.contains(key)) {
            sequence.remove();
        }
        sequence.addFirst(key);
        cacheData.put(key, value);
        return value;
    }


    /**
     * 达到最大内存，淘汰最近最少使用的key
     */
    private void maxMemoryHandle() {
        while (sequence.size() >= capacity) {
            String lruKey = sequence.removeLast();
            cacheData.remove(lruKey);
            System.out.println("key: " + lruKey + "被淘汰！");
        }
    }


    /**
     * 获取访问LRU顺序
     *
     * @return
     */
    public List<string> getAll() {
        return Arrays.asList(sequence.toArray(new String[] {}));
    }
}复制代码</string></string></string>

測試程式碼：

package com.lizba.redis.lru;

/**
 * <p>
 *      测试最近最少使用
 * </p>
 *
 * @Author: Liziba
 * @Date: 2021/9/18 0:00
 */
public class TestSimpleLru {

    public static void main(String[] args) {
        SimpleLru lru = new SimpleLru(8);
        for (int i = 0; i <p>##測試結果：<strong>\</strong></p><p><img src="https://img.php.cn/upload/image/775/594/750/163409191823487%E4%B8%80%E6%96%87%E8%A9%B3%E8%A7%A3Redis%E4%B8%AD%E7%9A%84LRU%E6%BC%94%E7%AE%97%E6%B3%95" title="163409191823487一文詳解Redis中的LRU演算法" alt="一文詳解Redis中的LRU演算法"></p>從上數的測試結果可以看出，先加入的key0，key1被淘汰了，最後加入的key也是最新的key保存在sequence的隊頭。 <p>透過這個方案，可以很簡單的實作LRU演算法；但缺點也十分明顯，方案需要使用額外的資料結構來保存key的存取順序，這會使Redis記憶體消耗增加，本身用來優化記憶體的方案，卻要消耗不少內存，顯然是不行的。 <br><br></p><h2 data-id="heading-4">5、Redis的近似LRU</h2><p>針對這種情況，Redis使用了近似LRU演算法，並不是完完全全準確的淘汰掉最近最不經常使用的key，但是總體的準確度也可以得到保證。 <br>近似LRU演算法非常簡單，在Redis的key物件中，增加24bit用於儲存最近一次存取的系統時間戳，當客戶端對Redis服務端發送key的寫入相關請求時，發現記憶體達到maxmemory，此時觸發惰性刪除；Redis服務透過隨機採樣，選擇5個滿足條件的key（注意這個隨機採樣<strong>allkeys-lru</strong>是從所有的key中隨機採樣，<strong>volatile-lru</strong>是從設定了過期時間的所有key中隨機採樣），透過key物件中記錄的最近存取時間戳進行比較，淘汰掉這5個key中最舊的key；如果記憶體仍然不夠，就繼續重複這個步驟。 <br></p><p><strong>注意，5是Redis預設的隨機取樣數值大小，它可以透過redis.conf中的maxmemory_samples進行配置：</strong>\</p><p><img src="https://img.php.cn/upload/image/866/655/134/163409192913128%E4%B8%80%E6%96%87%E8%A9%B3%E8%A7%A3Redis%E4%B8%AD%E7%9A%84LRU%E6%BC%94%E7%AE%97%E6%B3%95" title="163409192913128一文詳解Redis中的LRU演算法" alt="一文詳解Redis中的LRU演算法"></p><p><strong>針對上述的隨機LRU演算法，Redis官方給出了一張測試準確性的數據圖：</strong></p>

• 最上層淺灰色表示被淘汰的key ，圖一是標準的LRU演算法淘汰的示意圖
• 中間深灰色層表示未被淘汰的舊key
• 最下層淺綠色表示最近被訪問的key

在Redis 3.0 maxmemory_samples設定為10的時候，Redis的近似LRU演算法已經非常的接近真實LRU演算法了，但是顯然maxmemory_samples設定為10比maxmemory_samples 設定為5要更加消耗CPU計算時間，因為每次採樣的樣本資料增大，計算時間也會增加。
Redis3.0的LRU比Redis2.8的LRU演算法更準確，是因為Redis3.0增加了一個與maxmemory_samples相同大小的淘汰池，每次淘汰key的時候，先與淘汰池中等待被淘汰的key進行比較，最後淘汰掉最老舊的key，其實就是被選中淘汰的key放到一起再比較一下，淘汰其中最舊的。

6、有問題

LRU演算法看似比較好用，但是也存在不合理的地方，例如A和B兩個key，在發生淘汰時的前一個小時前同一時刻加入Redis，A在前49分鐘被訪問了1000次，但是後11分鐘沒有被訪問；B在這一小時內僅第59分鐘被訪問了1次；此時如果使用LRU演算法，如果A、 B都被Redis採樣選中，A將會被淘汰很顯然這個是不合理的。
針對這種情況Redis 4.0添加了LFU演算法，(Least frequently used) 最不常使用，這種演算法比LRU更加合理，下文將會一起學習中淘汰演算法，如有需要請關注我的專欄。

更多程式相關知識，請造訪：程式設計教學！ ！

以上是一文詳解Redis中的LRU演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！