深入理解Redis記憶體淘汰策略

2022-07-05 18:07:22

一、記憶體回收

長時間不使用的快取

降低IO效能
實體記憶體不夠

很多人瞭解了Redis的好處之後，於是把任何資料都往Redis中放，如果使用不合理很容易導致資料超過Redis的記憶體，這種情況會出現什麼問題呢？

Redis中有很多無效的快取，這些快取資料會降低資料IO的效能，因為不同的資料型別時間複雜度演演算法不同，資料越多可能會造成效能下降
隨著系統的執行，redis的資料越來越多，會導致實體記憶體不足。通過使用虛擬記憶體（VM），將很少存取的資料交換到磁碟上，騰出記憶體空間的方法來解決實體記憶體不足的情況。雖然能夠解決實體記憶體不足導致的問題，但是由於這部分資料是儲存在磁碟上，如果在高並行場景中，頻繁存取虛擬記憶體空間會嚴重降低系統效能。

所以遇到這類問題的時候，我們一般有幾種方法。

對每個儲存到redis中的key設定過期時間，這個根據實際業務場景來決定。否則，再大的記憶體都會隨著系統執行被消耗完
增加記憶體
使用記憶體淘汰策略

二、設定記憶體

在實際生產環境中，伺服器不僅僅只有Redis，為了避免Redis記憶體使用過多對其他程式造成影響，我們一般會設定最大記憶體。Redis預設的最大記憶體 maxmemory=0 ，表示不限制Redis記憶體的使用。我們可以修改 redis.conf 檔案，設定Redis最大使用的記憶體。

# 單位為byte
maxmemory <bytes> 2147483648（2G）

如何檢視當前Redis最大記憶體設定呢，進入到Redis-Cli控制檯，輸入下面這個命令。

config get maxmemory

當Redis中儲存的記憶體超過maxmemory時，會怎麼樣呢？下面我們做一個實驗

在redis-cli控制檯輸入下面這個命令，把最大記憶體設定為1個位元組。

config set maxmemory 1

通過下面的命令儲存一個string型別的資料

set name mvp

此時，控制檯會得到下面這個錯誤資訊

(error) OOM command not allowed when used memory > 'maxmemory'.

三、記憶體淘汰策略

設定了maxmemory的選項，redis記憶體使用達到上限。可以通過設定LRU演演算法來刪除部分key，釋放空間。預設是按照過期時間的，如果set時候沒有加上過期時間就會導致資料寫滿maxmemory。Redis中提供了一種記憶體淘汰策略，當記憶體不足時，Redis會根據相應的淘汰規則對key資料進行淘汰。Redis一共提供了8種淘汰策略，預設的策略為noeviction，當記憶體使用達到閾值的時候，所有引起申請記憶體的命令會都會報錯。

volatile-lru，針對設定了過期時間的key，使用lru演演算法進行淘汰。
allkeys-lru，針對所有key使用lru演演算法進行淘汰。
volatile-lfu，針對設定了過期時間的key，使用lfu演演算法進行淘汰。
allkeys-lfu，針對所有key使用lfu演演算法進行淘汰。
volatile-random，從所有設定了過期時間的key中使用隨機淘汰的方式進行淘汰。
allkeys-random，針對所有的key使用隨機淘汰機制進行淘汰。
volatile-ttl，針對設定了過期時間的key，越早過期的越先被淘汰。
noeviction，不會淘汰任何資料，當使用的記憶體空間超過 maxmemory 值時，再有寫請求來時返回錯誤。

字首為volatile-和allkeys-的區別在於二者選擇要清除的鍵時的字典不同，volatile-字首的策略代表從redisDb中的expire字典中選擇鍵進行清除；allkeys-開頭的策略代表從dict字典中選擇鍵進行清除。
記憶體淘汰演演算法的具體工作原理是：

使用者端執行一條新命令，導致資料庫需要增加資料（比如set key value）
Redis會檢查記憶體使用情況，如果記憶體使用超過 maxmemory，就會按照記憶體淘汰策略刪除一些 key
新的命令執行成功

四、LRU

4.1 LRU演演算法

LRU是Least Recently Used的縮寫，也就是表示最近很少使用，也可以理解成最久沒有使用。也就是說當記憶體不夠的時候，每次新增一條資料，都需要拋棄一條最久時間沒有使用的舊資料。標準的LRU演演算法為了降低查詢和刪除元素的時間複雜度，一般採用Hash表和雙向連結串列結合的資料結構，hash表可以賦予連結串列快速查詢到某個key是否存在連結串列中，同時可以快速刪除、新增節點，如下圖所示。

雙向連結串列的查詢時間複雜度是O(n)，刪除和插入是O(1)，藉助HashMap結構，可以使得查詢的時間複雜度變成O(1)。
Hash表用來查詢在連結串列中的資料位置，連結串列負責資料的插入，當新資料插入到連結串列頭部時有兩種情況。

連結串列滿了，把連結串列尾部的資料丟棄掉，新加入的快取直接加入到連結串列頭中。
當連結串列中的某個快取被命中時，直接把資料移到連結串列頭部，原本在頭節點的快取就向連結串列尾部移動。

這樣，經過多次Cache操作之後，最近被命中的快取，都會存在連結串列頭部的方向，沒有命中的，都會在連結串列尾部方向，當需要替換內容時，由於連結串列尾部是最少被命中的，我們只需要淘汰連結串列尾部的資料即可。
java程式碼實現簡單的LRU演演算法

import java.util.HashMap;

public class LRUCache {

    private Node head;
        private Node tail;

        private final HashMap<String,Node> nodeHashMap;
        private int capacity; //容量

    public LRUCache(int capacity) {
        this.capacity = capacity;
        nodeHashMap=new HashMap<>();
        tail=new Node();
        head=new Node();
        head.next=tail;
        tail.prev=head;
    }

    //移除節點
    private void removeNode(Node node){
        if(node==tail){
            tail=tail.prev;
            tail.next=null;
        }else if(node==head){
            head=head.next;
            head.prev=null;
        }else{
            node.prev.next=node.next;
            node.next.prev=node.prev;
        }
    }
    private void addNodeToHead(Node node){
        node.next=head.next;
        head.next.prev=node;
        node.prev=head;
        head.next=node;
    }

    private void moveNodeToHead(Node node){
        removeNode(node);
        addNodeToHead(node);
    }
    public String get(String key){
        Node node=nodeHashMap.get(key);
        if(node==null){
            return null;
        }
        //重新整理當前key的位置
        moveNodeToHead(node);
        return node.value;
    }
    public void put(String key,String value){
        Node node=nodeHashMap.get(key);
        if(node==null){ //如果不存在，則新增到連結串列
            if(nodeHashMap.size()>=capacity){ //大於容量，則需要移除老的資料
                removeNode(tail); //移除尾部節點（tail節點是屬於要被淘汰資料）
                nodeHashMap.remove(tail.key); //從hashmap中移除
            }
            node=new Node(key,value);
            nodeHashMap.put(key,node);
            addNodeToHead(node);
        }else{
            node.value=value;
            moveNodeToHead(node);
        }
    }

    class Node{
        private String key;
        private String value;
        Node prev;
        Node next;

        public Node(){}

        public Node(String key,String value){
            this.key=key;
            this.value=value;
        }
    }
}

4.2 redis中的LRU演演算法

實際上，Redis使用的LRU演演算法其實是一種不可靠的LRU演演算法，它實際淘汰的鍵並不一定是真正最少使用的資料，它的工作機制是：

隨機採集淘汰的key，每次隨機選出5個key
然後淘汰這5個key中最少使用的key

這5個key是預設的個數，具體的數值可以在redis.conf中設定

maxmemory-samples 5

當近似LRU演演算法取值越大的時候就會越接近真實的LRU演演算法，因為取值越大獲取的資料越完整，淘汰中的資料就更加接近最少使用的資料。這裡其實涉及一個權衡問題，如果需要在所有的資料中搜尋最符合條件的資料，那麼一定會增加系統的開銷，Redis是單執行緒的，所以耗時的操作會謹慎一些。為了在一定成本內實現相對的LRU，早期的Redis版本是基於取樣的LRU，也就是放棄了從所有資料中搜尋解改為取樣空間搜尋最優解。Redis3.0版本之後，Redis作者對於基於取樣的LRU進行了一些優化：

Redis中維護一個大小為16的候選池，當第一次隨機選取採用資料時，會把資料放入到候選池中，並且候選池中的資料會根據key的空閒時間進行排序。
當第二次以後選取資料時，只有大於候選池內最小空閒時間的key才會被放進候選池。
當候選池的資料滿了之後，那麼空閒時間最大的key就會被擠出候選池。當執行淘汰時，直接從候選池中選取空閒時間最大的key進行淘汰。

如下圖所示，首先從目標字典中採集出maxmemory-samples個鍵，快取在一個samples陣列中，然後從samples陣列中一個個取出來，和回收池中的鍵進行鍵的空閒時間比較，從而更新回收池。在更新過程中，首先利用遍歷找到的每個鍵的實際插入位置x，然後根據不同情況進行處理。

回收池滿了，並且當前插入的key的空閒時間最小（也就是回收池中的所有key都比當前插入的key的空閒時間都要大），則不作任何操作。
回收池未滿，並且插入的位置x沒有鍵，則直接插入即可
回收池未滿，且插入的位置x原本已經存在要淘汰的鍵，則把第x個以後的元素都往後挪一個位置，然後再執行插入操作。
回收池滿了，將當前第x個以前的元素往前挪一個位置（實際就是淘汰了），然後執行插入操作。

這樣做的目的是能夠選出最真實的最少被存取的key，能夠正確選擇不常使用的key。因為在Redis3.0之前是隨機選取樣本，這樣的方式很有可能不是真正意義上的最少存取的key。LRU演演算法有一個弊端，假如一個key值存取頻率很低，但是最近一次被存取到了，那LRU會認為它是熱點資料，不會被淘汰。同樣，經常被存取的資料，最近一段時間沒有被存取，這樣會導致這些資料被淘汰掉，導致誤判而淘汰掉熱點資料，於是在Redis 4.0中，新加了一種LFU演演算法。

五、LFU

LFU（Least Frequently Used），表示最近最少使用，它和key的使用次數有關，其思想是：根據key最近被存取的頻率進行淘汰，比較少存取的key優先淘汰，反之則保留。LFU的原理是使用計數器來對key進行排序，每次key被存取時，計數器會增大，當計數器越大，意味著當前key的存取越頻繁，也就是意味著它是熱點資料。它很好的解決了LRU演演算法的缺陷：一個很久沒有被存取的key，偶爾被存取一次，導致被誤認為是熱點資料的問題。LFU的實現原理如下圖所示，LFU維護了兩個連結串列，橫向組成的連結串列用來儲存存取頻率，每個存取頻率的節點下儲存另外一個具有相同存取頻率的快取資料。具體的工作原理是：

當新增元素時，找到相同存取頻次的節點，然後新增到該節點的資料連結串列的頭部。如果該資料連結串列滿了，則移除連結串列尾部的節點
當獲取元素或者修改元素時，都會增加對應key的存取頻次，並把當前節點移動到下一個頻次節點

新增元素時，存取頻率預設為1，隨著存取次數的增加，頻率不斷遞增。而當前被存取的元素也會隨著頻率增加進行移動。

到此這篇關於深入理解Redis記憶體淘汰策略的文章就介紹到這了,更多相關Redis記憶體淘汰內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！