一、內(nèi)存回收

長時間不使用的緩存

• 降低IO性能
• 物理內(nèi)存不夠

很多人了解了Redis的好處之后，于是把任何數(shù)據(jù)都往Redis中放，如果使用不合理很容易導(dǎo)致數(shù)據(jù)超過Redis的內(nèi)存，這種情況會出現(xiàn)什么問題呢？

• Redis中有很多無效的緩存，這些緩存數(shù)據(jù)會降低數(shù)據(jù)IO的性能，因為不同的數(shù)據(jù)類型時間復(fù)雜度算法不同，數(shù)據(jù)越多可能會造成性能下降
• 隨著系統(tǒng)的運行，redis的數(shù)據(jù)越來越多，會導(dǎo)致物理內(nèi)存不足。通過使用虛擬內(nèi)存（VM），將很少訪問的數(shù)據(jù)交換到磁盤上，騰出內(nèi)存空間的方法來解決物理內(nèi)存不足的情況。雖然能夠解決物理內(nèi)存不足導(dǎo)致的問題，但是由于這部分數(shù)據(jù)是存儲在磁盤上，如果在高并發(fā)場景中，頻繁訪問虛擬內(nèi)存空間會嚴重降低系統(tǒng)性能。

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

• 對每個存儲到redis中的key設(shè)置過期時間，這個根據(jù)實際業(yè)務(wù)場景來決定。否則，再大的內(nèi)存都會隨著系統(tǒng)運行被消耗完
• 增加內(nèi)存
• 使用內(nèi)存淘汰策略

二、設(shè)置內(nèi)存

在實際生產(chǎn)環(huán)境中，服務(wù)器不僅僅只有Redis，為了避免Redis內(nèi)存使用過多對其他程序造成影響，我們一般會設(shè)置最大內(nèi)存。Redis默認的最大內(nèi)存 maxmemory=0 ，表示不限制Redis內(nèi)存的使用。我們可以修改 redis.conf 文件，設(shè)置Redis最大使用的內(nèi)存。

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

如何查看當(dāng)前Redis最大內(nèi)存設(shè)置呢，進入到Redis-Cli控制臺，輸入下面這個命令。

config get maxmemory

當(dāng)Redis中存儲的內(nèi)存超過maxmemory時，會怎么樣呢？下面我們做一個實驗

在redis-cli控制臺輸入下面這個命令，把最大內(nèi)存設(shè)置為1個字節(jié)。

config set maxmemory 1

通過下面的命令存儲一個string類型的數(shù)據(jù)

set name mvp

此時，控制臺會得到下面這個錯誤信息

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

三、內(nèi)存淘汰策略

設(shè)置了maxmemory的選項，redis內(nèi)存使用達到上限?？梢酝ㄟ^設(shè)置LRU算法來刪除部分key，釋放空間。默認是按照過期時間的，如果set時候沒有加上過期時間就會導(dǎo)致數(shù)據(jù)寫滿maxmemory。Redis中提供了一種內(nèi)存淘汰策略，當(dāng)內(nèi)存不足時，Redis會根據(jù)相應(yīng)的淘汰規(guī)則對key數(shù)據(jù)進行淘汰。Redis一共提供了8種淘汰策略，默認的策略為noeviction，當(dāng)內(nèi)存使用達到閾值的時候，所有引起申請內(nèi)存的命令會都會報錯。

• volatile-lru，針對設(shè)置了過期時間的key，使用lru算法進行淘汰。
• allkeys-lru，針對所有key使用lru算法進行淘汰。
• volatile-lfu，針對設(shè)置了過期時間的key，使用lfu算法進行淘汰。
• allkeys-lfu，針對所有key使用lfu算法進行淘汰。
• volatile-random，從所有設(shè)置了過期時間的key中使用隨機淘汰的方式進行淘汰。
• allkeys-random，針對所有的key使用隨機淘汰機制進行淘汰。
• volatile-ttl，針對設(shè)置了過期時間的key，越早過期的越先被淘汰。
• noeviction，不會淘汰任何數(shù)據(jù)，當(dāng)使用的內(nèi)存空間超過 maxmemory 值時，再有寫請求來時返回錯誤。

前綴為volatile-和allkeys-的區(qū)別在于二者選擇要清除的鍵時的字典不同，volatile-前綴的策略代表從redisDb中的expire字典中選擇鍵進行清除；allkeys-開頭的策略代表從dict字典中選擇鍵進行清除。
內(nèi)存淘汰算法的具體工作原理是：

• 客戶端執(zhí)行一條新命令，導(dǎo)致數(shù)據(jù)庫需要增加數(shù)據(jù)（比如set key value）
• Redis會檢查內(nèi)存使用情況，如果內(nèi)存使用超過 maxmemory，就會按照內(nèi)存淘汰策略刪除一些 key
• 新的命令執(zhí)行成功

四、LRU

4.1 LRU算法

LRU是Least Recently Used的縮寫，也就是表示最近很少使用，也可以理解成最久沒有使用。也就是說當(dāng)內(nèi)存不夠的時候，每次添加一條數(shù)據(jù)，都需要拋棄一條最久時間沒有使用的舊數(shù)據(jù)。標(biāo)準(zhǔn)的LRU算法為了降低查找和刪除元素的時間復(fù)雜度，一般采用Hash表和雙向鏈表結(jié)合的數(shù)據(jù)結(jié)構(gòu)，hash表可以賦予鏈表快速查找到某個key是否存在鏈表中，同時可以快速刪除、添加節(jié)點，如下圖所示。

雙向鏈表的查找時間復(fù)雜度是O(n)，刪除和插入是O(1)，借助HashMap結(jié)構(gòu)，可以使得查找的時間復(fù)雜度變成O(1)。
Hash表用來查詢在鏈表中的數(shù)據(jù)位置，鏈表負責(zé)數(shù)據(jù)的插入，當(dāng)新數(shù)據(jù)插入到鏈表頭部時有兩種情況。

• 鏈表滿了，把鏈表尾部的數(shù)據(jù)丟棄掉，新加入的緩存直接加入到鏈表頭中。
• 當(dāng)鏈表中的某個緩存被命中時，直接把數(shù)據(jù)移到鏈表頭部，原本在頭節(jié)點的緩存就向鏈表尾部移動。

這樣，經(jīng)過多次Cache操作之后，最近被命中的緩存，都會存在鏈表頭部的方向，沒有命中的，都會在鏈表尾部方向，當(dāng)需要替換內(nèi)容時，由于鏈表尾部是最少被命中的，我們只需要淘汰鏈表尾部的數(shù)據(jù)即可。
java代碼實現(xiàn)簡單的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;
    }
    //移除節(jié)點
    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;
        }
        //刷新當(dāng)前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){ //大于容量，則需要移除老的數(shù)據(jù)
                removeNode(tail); //移除尾部節(jié)點（tail節(jié)點是屬于要被淘汰數(shù)據(jù)）
                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算法，它實際淘汰的鍵并不一定是真正最少使用的數(shù)據(jù)，它的工作機制是：

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

這5個key是默認的個數(shù)，具體的數(shù)值可以在redis.conf中配置

maxmemory-samples 5

當(dāng)近似LRU算法取值越大的時候就會越接近真實的LRU算法，因為取值越大獲取的數(shù)據(jù)越完整，淘汰中的數(shù)據(jù)就更加接近最少使用的數(shù)據(jù)。這里其實涉及一個權(quán)衡問題，如果需要在所有的數(shù)據(jù)中搜索最符合條件的數(shù)據(jù)，那么一定會增加系統(tǒng)的開銷，Redis是單線程的，所以耗時的操作會謹慎一些。為了在一定成本內(nèi)實現(xiàn)相對的LRU，早期的Redis版本是基于采樣的LRU，也就是放棄了從所有數(shù)據(jù)中搜索解改為采樣空間搜索最優(yōu)解。Redis3.0版本之后，Redis作者對于基于采樣的LRU進行了一些優(yōu)化：

• Redis中維護一個大小為16的候選池，當(dāng)?shù)谝淮坞S機選取采用數(shù)據(jù)時，會把數(shù)據(jù)放入到候選池中，并且候選池中的數(shù)據(jù)會根據(jù)key的空閑時間進行排序。
• 當(dāng)?shù)诙我院筮x取數(shù)據(jù)時，只有大于候選池內(nèi)最小空閑時間的key才會被放進候選池。
• 當(dāng)候選池的數(shù)據(jù)滿了之后，那么空閑時間最大的key就會被擠出候選池。當(dāng)執(zhí)行淘汰時，直接從候選池中選取空閑時間最大的key進行淘汰。

如下圖所示，首先從目標(biāo)字典中采集出maxmemory-samples個鍵，緩存在一個samples數(shù)組中，然后從samples數(shù)組中一個個取出來，和回收池中的鍵進行鍵的空閑時間比較，從而更新回收池。在更新過程中，首先利用遍歷找到的每個鍵的實際插入位置x，然后根據(jù)不同情況進行處理。

• 回收池滿了，并且當(dāng)前插入的key的空閑時間最?。ㄒ簿褪腔厥粘刂械乃衚ey都比當(dāng)前插入的key的空閑時間都要大），則不作任何操作。
• 回收池未滿，并且插入的位置x沒有鍵，則直接插入即可
• 回收池未滿，且插入的位置x原本已經(jīng)存在要淘汰的鍵，則把第x個以后的元素都往后挪一個位置，然后再執(zhí)行插入操作。
• 回收池滿了，將當(dāng)前第x個以前的元素往前挪一個位置（實際就是淘汰了），然后執(zhí)行插入操作。

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

五、LFU

LFU（Least Frequently Used），表示最近最少使用，它和key的使用次數(shù)有關(guān)，其思想是：根據(jù)key最近被訪問的頻率進行淘汰，比較少訪問的key優(yōu)先淘汰，反之則保留。LFU的原理是使用計數(shù)器來對key進行排序，每次key被訪問時，計數(shù)器會增大，當(dāng)計數(shù)器越大，意味著當(dāng)前key的訪問越頻繁，也就是意味著它是熱點數(shù)據(jù)。 它很好的解決了LRU算法的缺陷：一個很久沒有被訪問的key，偶爾被訪問一次，導(dǎo)致被誤認為是熱點數(shù)據(jù)的問題。LFU的實現(xiàn)原理如下圖所示，LFU維護了兩個鏈表，橫向組成的鏈表用來存儲訪問頻率，每個訪問頻率的節(jié)點下存儲另外一個具有相同訪問頻率的緩存數(shù)據(jù)。具體的工作原理是：

• 當(dāng)添加元素時，找到相同訪問頻次的節(jié)點，然后添加到該節(jié)點的數(shù)據(jù)鏈表的頭部。如果該數(shù)據(jù)鏈表滿了，則移除鏈表尾部的節(jié)點
• 當(dāng)獲取元素或者修改元素時，都會增加對應(yīng)key的訪問頻次，并把當(dāng)前節(jié)點移動到下一個頻次節(jié)點

添加元素時，訪問頻率默認為1，隨著訪問次數(shù)的增加，頻率不斷遞增。而當(dāng)前被訪問的元素也會隨著頻率增加進行移動。

到此這篇關(guān)于深入理解Redis內(nèi)存淘汰策略的文章就介紹到這了,更多相關(guān)Redis內(nèi)存淘汰內(nèi)容請搜索本站以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持本站！

國外服務(wù)器租用

版權(quán)聲明：本站文章來源標(biāo)注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請保持原文完整并注明來源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站，禁止在非www.sddonglingsh.com所屬的服務(wù)器上建立鏡像，否則將依法追究法律責(zé)任。本站部分內(nèi)容來源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來，僅供學(xué)習(xí)參考，不代表本站立場，如有內(nèi)容涉嫌侵權(quán)，請聯(lián)系alex-e#qq.com處理。