Redis中的LRU算法有什么用

這篇文章給大家分享的是有關(guān)Redis中的LRU算法有什么用的內(nèi)容。小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，一起跟隨小編過(guò)來(lái)看看吧。

Redis是基于內(nèi)存存儲(chǔ)的key-value數(shù)據(jù)庫(kù)，我們知道內(nèi)存雖然快但空間小，當(dāng)物理內(nèi)存達(dá)到上限時(shí)，系統(tǒng)就會(huì)跑的很慢，這是因?yàn)閟wap機(jī)制會(huì)將部分內(nèi)存的數(shù)據(jù)轉(zhuǎn)移到swap分區(qū)中，通過(guò)與swap的交換保證系統(tǒng)繼續(xù)運(yùn)行；但是swap屬于硬盤存儲(chǔ)，速度遠(yuǎn)遠(yuǎn)比不上內(nèi)存，尤其是對(duì)于Redis這種QPS非常高的服務(wù)，發(fā)生這種情況是無(wú)法接收的。（注意如果swap分區(qū)內(nèi)存也滿了，系統(tǒng)就會(huì)發(fā)生錯(cuò)誤?。鞠嚓P(guān)推薦：Redis視頻教程】

Linux操作系統(tǒng)可以通過(guò)free -m查看swap大小:\

因此如何防止Redis發(fā)生這種情況非常重要（面試官問(wèn)到Redis幾乎沒有不問(wèn)這個(gè)知識(shí)點(diǎn)的）。

2、maxmemory配置

Redis針對(duì)上述問(wèn)題提供了maxmemory配置，這個(gè)配置可以指定Redis存儲(chǔ)器的最大數(shù)據(jù)集，通常情況都是在redis.conf文件中進(jìn)行配置，也可以運(yùn)行時(shí)使用CONFIG SET命令進(jìn)行一次性配置。
redis.conf文件中的配置項(xiàng)示意圖：\

默認(rèn)情況maxmemory配置項(xiàng)并未啟用，Redis官方介紹64位操作系統(tǒng)默認(rèn)無(wú)內(nèi)存限制，32位操作系統(tǒng)默認(rèn)3GB隱式內(nèi)存配置，如果maxmemory 為0，代表內(nèi)存不受限。

因此我們?cè)谧鼍彺婕軜?gòu)時(shí)，要根據(jù)硬件資源+業(yè)務(wù)需求做合適的maxmemory配置。

3、內(nèi)存達(dá)到maxmemory怎么辦

很顯然配置了最大內(nèi)存，當(dāng)maxmemory達(dá)到了最大上限之后Redis不可能不干活了，那么Redis是怎么來(lái)處理這個(gè)問(wèn)題的呢？這就是本文的重點(diǎn)，Redis 提供了maxmemory-policy淘汰策略（本文只講述LRU不涉及LFU，LFU在下一篇文章講述），對(duì)滿足條件的key進(jìn)行刪除，辭舊迎新。
maxmemory-policy淘汰策略：

• noeviction： 當(dāng)達(dá)到內(nèi)存限制并且客戶端嘗試執(zhí)行可能導(dǎo)致使用更多內(nèi)存的命令時(shí)返回錯(cuò)誤，簡(jiǎn)單來(lái)說(shuō)讀操作仍然允許，但是不準(zhǔn)寫入新的數(shù)據(jù)，del（刪除）請(qǐng)求可以。

• allkeys-lru： 從全體key中，通過(guò)lru（Least Recently Used - 最近最少使用）算法進(jìn)行淘汰

• allkeys-random： 從全體key中，隨機(jī)進(jìn)行淘汰

• volatile-lru： 從設(shè)置了過(guò)期時(shí)間的全部key中，通過(guò)lru（Least Recently Used - 最近最少使用）算法進(jìn)行淘汰，這樣可以保證未設(shè)置過(guò)期時(shí)間需要被持久化的數(shù)據(jù)，不會(huì)被選中淘汰

• volatile-random： 從設(shè)置了過(guò)期時(shí)間的全部key中，隨機(jī)進(jìn)行淘汰

• volatile-ttl： 從設(shè)置了過(guò)期時(shí)間的全部key中，通過(guò)比較key的剩余過(guò)期時(shí)間TTL的值，TTL越小越先被淘汰

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

random隨機(jī)淘汰只需要隨機(jī)取一些key進(jìn)行刪除，釋放內(nèi)存空間即可；ttl過(guò)期時(shí)間小先淘汰也可以通過(guò)比較ttl的大小，將ttl值小的key進(jìn)行刪除，釋放內(nèi)存空間即可。
那么LRU是怎么實(shí)現(xiàn)的呢？Redis又是如何知道哪個(gè)key最近被使用了，哪個(gè)key最近沒有被使用呢？

4、LRU算法實(shí)現(xiàn)

我們先用Java的容器實(shí)現(xiàn)一個(gè)簡(jiǎn)單的LRU算法，我們使用ConcurrentHashMap做key-value結(jié)果存儲(chǔ)元素的映射關(guān)系，使用ConcurrentLinkedDeque來(lái)維持key的訪問(wèn)順序。
LRU實(shí)現(xiàn)代碼：

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簡(jiǎn)單實(shí)現(xiàn)
 * </p>
 *
 * @Author: Liziba
 * @Date: 2021/9/17 23:47
 */
public class SimpleLru {

    /** 數(shù)據(jù)緩存 */
    private ConcurrentHashMap<String, Object> cacheData;
    /** 訪問(wèn)順序記錄 */
    private ConcurrentLinkedDeque<String> sequence;
    /** 緩存容量 */
    private int capacity;

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


    /**
     * 設(shè)置值
     *
     * @param key
     * @param value
     * @return
     */
    public Object setValue(String key, Object value) {
        // 判斷是否需要進(jìn)行LRU淘汰
        this.maxMemoryHandle();
        // 包含則移除元素，新訪問(wèn)的元素一直保存在隊(duì)列最前面
        if (sequence.contains(key)) {
            sequence.remove();
        }
        sequence.addFirst(key);
        cacheData.put(key, value);
        return value;
    }


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


    /**
     * 獲取訪問(wèn)LRU順序
     *
     * @return
     */
    public List<String> getAll() {
        return Arrays.asList(sequence.toArray(new String[] {}));
    }
}復(fù)制代碼

測(cè)試代碼：

package com.lizba.redis.lru;

/**
 * <p>
 *      測(cè)試最近最少使用
 * </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 < 10; i++) {
            lru.setValue(i+"", i);
        }
        System.out.println(lru.getAll());
    }

}復(fù)制代碼

測(cè)試結(jié)果：\

從上數(shù)的測(cè)試結(jié)果可以看出，先加入的key0，key1被淘汰了，最后加入的key也是最新的key保存在sequence的隊(duì)頭。
通過(guò)這種方案，可以很簡(jiǎn)單的實(shí)現(xiàn)LRU算法；但缺點(diǎn)也十分明顯，方案需要使用額外的數(shù)據(jù)結(jié)構(gòu)來(lái)保存key的訪問(wèn)順序，這樣會(huì)使Redis內(nèi)存消耗增加，本身用來(lái)優(yōu)化內(nèi)存的方案，卻要消耗不少內(nèi)存，顯然是不行的。

5、Redis的近似LRU

針對(duì)這種情況，Redis使用了近似LRU算法，并不是完完全全準(zhǔn)確的淘汰掉最近最不經(jīng)常使用的key，但是總體的準(zhǔn)確度也可以得到保證。
近似LRU算法非常簡(jiǎn)單，在Redis的key對(duì)象中，增加24bit用于存儲(chǔ)最近一次訪問(wèn)的系統(tǒng)時(shí)間戳，當(dāng)客戶端對(duì)Redis服務(wù)端發(fā)送key的寫入相關(guān)請(qǐng)求時(shí)，發(fā)現(xiàn)內(nèi)存達(dá)到maxmemory，此時(shí)觸發(fā)惰性刪除；Redis服務(wù)通過(guò)隨機(jī)采樣，選擇5個(gè)滿足條件的key（注意這個(gè)隨機(jī)采樣allkeys-lru是從所有的key中隨機(jī)采樣，volatile-lru是從設(shè)置了過(guò)期時(shí)間的所有key中隨機(jī)采樣），通過(guò)key對(duì)象中記錄的最近訪問(wèn)時(shí)間戳進(jìn)行比較，淘汰掉這5個(gè)key中最舊的key；如果內(nèi)存仍然不夠，就繼續(xù)重復(fù)這個(gè)步驟。

注意，5是Redis默認(rèn)的隨機(jī)采樣數(shù)值大小，它可以通過(guò)redis.conf中的maxmemory_samples進(jìn)行配置：\

針對(duì)上述的隨機(jī)LRU算法，Redis官方給出了一張測(cè)試準(zhǔn)確性的數(shù)據(jù)圖：

• 最上層淺灰色表示被淘汰的key，圖一是標(biāo)準(zhǔn)的LRU算法淘汰的示意圖

• 中間深灰色層表示未被淘汰的舊key

• 最下層淺綠色表示最近被訪問(wèn)的key

在Redis 3.0 maxmemory_samples設(shè)置為10的時(shí)候，Redis的近似LRU算法已經(jīng)非常的接近真實(shí)LRU算法了，但是顯然maxmemory_samples設(shè)置為10比maxmemory_samples 設(shè)置為5要更加消耗CPU計(jì)算時(shí)間，因?yàn)槊看尾蓸拥臉颖緮?shù)據(jù)增大，計(jì)算時(shí)間也會(huì)增加。
Redis3.0的LRU比Redis2.8的LRU算法更加準(zhǔn)確，是因?yàn)镽edis3.0增加了一個(gè)與maxmemory_samples相同大小的淘汰池，每次淘汰key的時(shí)候，先與淘汰池中等待被淘汰的key進(jìn)行比較，最后淘汰掉最老舊的key，其實(shí)就是被選中淘汰的key放到一起再比較一下，淘汰其中最舊的。

6、存在問(wèn)題

LRU算法看似比較好用，但是也存在不合理的地方，比如A和B兩個(gè)key，在發(fā)生淘汰時(shí)的前一個(gè)小時(shí)前同一時(shí)刻添加到Redis，A在前49分鐘被訪問(wèn)了1000次，但是后11分鐘沒有被訪問(wèn)；B在這一個(gè)小時(shí)內(nèi)僅僅第59分鐘被訪問(wèn)了1次；此時(shí)如果使用LRU算法，如果A、B均被Redis采樣選中，A將會(huì)被淘汰很顯然這個(gè)是不合理的。
針對(duì)這種情況Redis 4.0添加了LFU算法，(Least frequently used) 最不經(jīng)常使用，這種算法比LRU更加合理。

感謝各位的閱讀！關(guān)于“Redis中的LRU算法有什么用”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，讓大家可以學(xué)到更多知識(shí)，如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！