一、內(nèi)存回收

長(zhǎng)時(shí)間不使用的緩存

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

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

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

所以遇到這類問(wèn)題的時(shí)候，我們一般有幾種方法。

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

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

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

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

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

config get maxmemory

當(dāng)Redis中存儲(chǔ)的內(nèi)存超過(guò)maxmemory時(shí)，會(huì)怎么樣呢？下面我們做一個(gè)實(shí)驗(yàn)

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

config set maxmemory 1

通過(guò)下面的命令存儲(chǔ)一個(gè)string類型的數(shù)據(jù)

set name mvp

此時(shí)，控制臺(tái)會(huì)得到下面這個(gè)錯(cuò)誤信息

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

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

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

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

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

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

四、LRU

4.1 LRU算法

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

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

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

這樣，經(jīng)過(guò)多次Cache操作之后，最近被命中的緩存，都會(huì)存在鏈表頭部的方向，沒有命中的，都會(huì)在鏈表尾部方向，當(dāng)需要替換內(nèi)容時(shí)，由于鏈表尾部是最少被命中的，我們只需要淘汰鏈表尾部的數(shù)據(jù)即可。
java代碼實(shí)現(xiàn)簡(jiǎ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é)點(diǎn)
    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é)點(diǎn)（tail節(jié)點(diǎn)是屬于要被淘汰數(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算法

實(shí)際上，Redis使用的LRU算法其實(shí)是一種不可靠的LRU算法，它實(shí)際淘汰的鍵并不一定是真正最少使用的數(shù)據(jù)，它的工作機(jī)制是：

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

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

maxmemory-samples 5

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

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

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

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

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

五、LFU

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

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

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

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

最新評(píng)論