一、內存回收

長時間不使用的緩存

• 降低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，隨著訪問次數的增加，頻率不斷遞增。而當前被訪問的元素也會隨著頻率增加進行移動。