緩存替換策略及應(yīng)用(以Redis、InnoDB為例)

1 概述

在操作系統(tǒng)的頁面管理中，內(nèi)存會維護(hù)一部分?jǐn)?shù)據(jù)以備進(jìn)程使用，但是由于內(nèi)存的大小必然是遠(yuǎn)遠(yuǎn)小于硬盤的，當(dāng)某些進(jìn)程訪問到內(nèi)存中沒有的數(shù)據(jù)時(shí)，必然需要從硬盤中讀進(jìn)內(nèi)存，所以迫于內(nèi)存容量的壓力下迫使操作系統(tǒng)將一些頁換出，或者說踢出，而決定將哪些（個）頁面踢出就是內(nèi)存替換策略。

我們考慮內(nèi)存中的頁實(shí)際上是整個系統(tǒng)頁的子集，所以內(nèi)存可以當(dāng)成系統(tǒng)中虛擬內(nèi)存的緩存（Cache），所以頁面置換算法就是緩存替換的方法。

一般意義下，選取頁面置換算法即選取一個緩存命中率更高的或者說缺頁率更低的算法，但實(shí)際上有時(shí)候隨著算法緩存命中率提升，算法復(fù)雜度也在上升，所以帶來的系統(tǒng)開銷也是在上升的，所以我們不得不在系統(tǒng)開銷和算法復(fù)雜程度中間取一個折中，比如Redis中采取的類LRU緩存置換策略實(shí)際上在大多數(shù)情況下比起理想LRU緩存命中率是低的，但理想LRU實(shí)現(xiàn)起來會給系統(tǒng)帶來更大的開銷，得不償失。

2 頁面置換算法

下面介紹最常見的五種置換策略，其中最佳置換算法是理論上很難實(shí)現(xiàn)的，其余的FIFO、LRU、LFU，其算法復(fù)雜度、開銷是遞增的，但是缺頁率也是越來越低，或者說越來越接近最佳置換策略的。最后一種時(shí)鐘置換算法是一種近似的LRU算法，是保證了低系統(tǒng)開銷下同時(shí)較低的缺頁率的一種折中選擇。

2.1 最佳（Optimal）置換算法

最佳置換算法，其所選擇的被淘汰的頁面將是以后永不使用的，或是在最長（未來）時(shí)間內(nèi)不再被訪問的頁面。聽名字定義很顯然頁面未來的使用情況它就不可預(yù)測，所以最佳置換算法只是理論上的最優(yōu)方法，實(shí)際上在大多數(shù)情況下并沒法完成，所以更多的是作為衡量其他置換算法的標(biāo)準(zhǔn)。

2.2 先進(jìn)先出（FIFO）置換算法

許多早期的操作系統(tǒng)為了保證算法的簡單，避免高復(fù)雜度的算法，嘗試了最簡單的置換策略，即FIFO置換策略，顧名思義就是維護(hù)一個頁的隊(duì)列，最先進(jìn)入內(nèi)存的頁最先被淘汰，這樣的算法復(fù)雜度低，系統(tǒng)開銷也極低，但是顯然命中率會下降。

另外考慮一種情況，增大緩存時(shí)，一般意義下緩存的命中率必然會上升，但是FIFO算法則在有的時(shí)候則會下降，這種現(xiàn)象叫做Belady現(xiàn)象。原因是FIFO算法沒有考慮到程序的局部性原則，踢出的頁面很可能是程序經(jīng)常性訪問的頁面。

Belady現(xiàn)象的實(shí)例分析可以參考belady

2.3 最近最少使用（Least Recently Used,LRU）置換算法

為了解決Belady現(xiàn)象，同時(shí)也是基于程序的局部性原則（Locality of reference，指的是在計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué)領(lǐng)域中應(yīng)用程序在訪問內(nèi)存的時(shí)候，傾向于訪問內(nèi)存中較為靠近的值。）就有了LRU置換策略，從程序代碼的角度理解局部性原則就是，程序一般傾向于頻繁的訪問某些代碼（比如循環(huán)）或者數(shù)據(jù)結(jié)構(gòu)（比如循環(huán)訪問的數(shù)組），因此我們應(yīng)該使用歷史訪問數(shù)據(jù)來決定，哪些頁應(yīng)該被踢出，哪些頁不應(yīng)該被踢出，具體的就是，最近沒有被訪問的頁優(yōu)先被踢出。這個其實(shí)不難理解，通過一個訪問順序的隊(duì)列，每次訪問某個頁，就將此頁移到隊(duì)首，當(dāng)內(nèi)存（緩存）滿了時(shí)優(yōu)先從隊(duì)尾踢出相應(yīng)的頁。（下面給出一個例子，表來自操作系統(tǒng)導(dǎo)論第22章）

但是顯然的是，LRU會帶來更大的系統(tǒng)開銷，因?yàn)槲覀冃枰l繁的將訪問過的頁置于訪問序列的首部，這就需要對訪問隊(duì)列的內(nèi)容進(jìn)行頻繁的增刪，而FIFO只需要簡單排列即可。

2.4 最不經(jīng)常使用（Least Frequently Used,LFU）置換算法

如果說LRU是通過所有頁面的最近使用情況或者說訪問時(shí)間來看，那么LFU即通過訪問頻率來決定哪些頁面需要被踢出，根據(jù)程序的局部性原則，顯然LFU會帶來更高的緩存命中率，但是考慮到需要記錄頻率并且頻繁的調(diào)整隊(duì)列，實(shí)際上帶來的系統(tǒng)開銷會比LRU更大。

下圖描述了一個LFU的執(zhí)行過程，大寫字母為相應(yīng)的頁，圓圈中的數(shù)字代表訪問頻率，訪問頻率最低的在隊(duì)列的最后，當(dāng)需要踢出時(shí)，優(yōu)先踢出隊(duì)列末尾的頁。

2.5 時(shí)鐘（CLOCK）置換算法

上文談到了LRU和LFU會帶來更高的緩存命中率，但是計(jì)算開銷顯然會更大，給系統(tǒng)帶來更高的時(shí)間開銷，而一些類LRU算法就出現(xiàn)了，比如時(shí)鐘算法。

系統(tǒng)中的所有頁都放在一個循環(huán)列表中。時(shí)鐘指針（clock hand）開始時(shí)指向某個特定的頁（哪個頁不重要）。當(dāng)必須進(jìn)行頁替換時(shí)，操作系統(tǒng)檢查當(dāng)前指向的頁P(yáng)的使用位是1還是0。如果是1，則意味著頁面P最近被使用， 因此不適合被替換。然后，P的使用位設(shè)置為0，時(shí)鐘指針遞增到下一頁（P+1）。該算法一直持續(xù)到找到一個使用位為 0 的頁，使用位為 0 意味著這個頁最近沒有被使用過（在最壞的情況下，所有的頁都已經(jīng)被使用了，那么就將所有頁的使用位都設(shè)置為 0）。

3 樸素LRU的實(shí)現(xiàn)

以leetcode146. LRU 緩存機(jī)制為例，最直觀樸素的LRU緩存機(jī)制可以使用哈希表以及雙向鏈表實(shí)現(xiàn)，當(dāng)然Java的集合LinkedHashMap即實(shí)現(xiàn)了一個哈希表+鏈表的組合，可以直接調(diào)用實(shí)現(xiàn)。

但為了更形象的理解LRU的機(jī)制，采用HashMap以及手寫一個雙向鏈表來實(shí)現(xiàn)。具體的結(jié)構(gòu)如下圖所示

維護(hù)一個大小為緩存容量的map，key值為緩存數(shù)據(jù)的key，value存儲指向相應(yīng)節(jié)點(diǎn)的引用，數(shù)據(jù)鏈表使用雙向鏈表便于增刪，當(dāng)訪問到某條數(shù)據(jù)時(shí)，通過map以O(shè)（1）復(fù)雜度定位到數(shù)據(jù)的應(yīng)用，然后

• 刪除訪問節(jié)點(diǎn)
• 添加訪問節(jié)點(diǎn)到隊(duì)首

當(dāng)節(jié)點(diǎn)數(shù)量>緩存容量時(shí)，刪除隊(duì)尾元素，同時(shí)移除map中的數(shù)據(jù)，具體實(shí)現(xiàn)如下。

public class LRUCache {
class DLinkedNode {
    int key, value;
    DLinkedNode pre;
    DLinkedNode next;
    public DLinkedNode(){}
    public DLinkedNode(int key, int value){this.key = key; this.value = value;}
}
    private MapInteger, DLinkedNode> cache = new HashMap>();
    private int size;
    private int cal;
    private DLinkedNode head, tail;
    public LRUCache(int capacity) {
        size = 0;
        cal = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.pre = head;
    }
    
    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        moveToHead(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            DLinkedNode newNode = new DLinkedNode(key, value);
            cache.put(key, newNode);
            size++;
            addToHead(newNode);
            if (size > cal) {
                DLinkedNode tail = removeTail();
                cache.remove(tail.key);
                size--;
            }
        } else {
            node.value = value;
            moveToHead(node);
        }
    }

    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    private void removeNode(DLinkedNode node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    private void addToHead(DLinkedNode node) {
        node.pre = head;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
    }

    private DLinkedNode removeTail() {
        DLinkedNode realTail = tail.pre;
        removeNode(realTail);
        return realTail;
    }
}

4 LRU的實(shí)際應(yīng)用

4.1 以Redis為例

上面談到要實(shí)現(xiàn)一個樸素的LRU算法，需要維護(hù)一個雙向鏈表，存儲前驅(qū)、后繼指針，必然會在寸金寸土的緩存（內(nèi)存）中帶來不必要的開銷。上述提到的時(shí)鐘算法就是一種類LRU算法，用更少的系統(tǒng)開銷帶來了接近樸素LRU的命中率。而事實(shí)上，Redis中采取的LRU算法也是一種類LRU算法，它也帶來了時(shí)鐘算法類似的效果。具體的是Redis通過隨機(jī)選取幾個key值，淘汰時(shí)間戳最靠前的key，涉及到LRU的淘汰策略maxmemory_policy（這個字段可以選擇不同的緩存淘汰策略，Redis一種提供了8種，本文只分析其中與LRU有關(guān)的）的賦值兩種：

• allkeys-lru: 對所有的鍵都采取LRU淘汰
• volatile-lru: 僅對設(shè)置了過期時(shí)間的鍵采取LRU淘汰

可以根據(jù)實(shí)際情況選擇上述兩種LRU淘汰策略，在一般情況下，程序都存在局部性，或者說冪次分布（二八法則），即少數(shù)數(shù)據(jù)比其他大多數(shù)數(shù)據(jù)訪問的更多，所以通常使用allkeys-lru策略，而當(dāng)有需求需要長期保留一部分?jǐn)?shù)據(jù)在內(nèi)存中時(shí)選取volatile-lru即只規(guī)定部分需要淘汰的數(shù)據(jù)。

下面看一下具體是如何設(shè)置的，Redis整體上是一個大的字典，key是一個string，而value都會保存為一個robj（Redis Object），對于robj的定義如下

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    void *ptr;
} robj;

其中LRU_BITS即Redis為每個鍵值對配備的一個記錄時(shí)間戳的bit位，Redis的LFU替換策略中也使用這個空間，創(chuàng)建對象時(shí)會寫入到lru_clock這個字段中，訪問對象時(shí)會對其進(jìn)行更新，具體的空間的大小被定義為一個常量

#define REDIS_LRU_BITS 24

大小為24，即使用一個額外的24bit的空間記錄相對時(shí)間戳（即對unix time取模之后的結(jié)果），默認(rèn)的時(shí)間戳分辨率是1秒，在這種情況下，24bits的空間如果溢出的話需要194天，而作為頻繁更新的緩存而言，這個空間夠用了。

上面提到了Redis會隨機(jī)采樣，比較其訪問時(shí)間哪個更靠前，當(dāng)需要替換時(shí)優(yōu)先踢出采樣結(jié)果最靠前的鍵值對，具體的采樣個數(shù)在最開始是選取3個key，但是效果并不好，后來增加到N個key，但是默認(rèn)是5個，即默認(rèn)隨機(jī)選取5個key，最先淘汰掉這5個中距離上次訪問時(shí)間最久的，Redis3.0中又改善了算法的性能，即提供了一個采樣池（pool），候選采樣池默認(rèn)大小為16，能夠填充16個key，更新時(shí)從Redis鍵空間隨機(jī)選擇N個key，分別計(jì)算它們的空閑時(shí)間idle，key只會在pool不滿或者空閑時(shí)間大于pool里最小的時(shí)，才會進(jìn)入pool，然后從pool中選擇空閑時(shí)間最大的key淘汰掉。

具體的這個候選集合結(jié)構(gòu)體如下

struct evictionPoolEntry {
    unsigned long long idle; // 用于淘汰排序，在不同算法中意義不同優(yōu)先淘汰值大的，單位是ms
    sds key;  // 鍵的名字
    // ...
};

所以關(guān)鍵在pool中的idle字段的計(jì)算，實(shí)際上只需要使用當(dāng)前的時(shí)間戳減去lru_clock即可，但是所記錄的時(shí)間戳都是取模之后的結(jié)果，所以還需要比較當(dāng)前計(jì)算出來的時(shí)間戳是否大于lru_clock，如果不是，則需要將當(dāng)前

時(shí)間戳+194天（模數(shù)）再減去lru_clock。具體的計(jì)算過程如下

// 以秒為精度計(jì)算對象距離上一次訪問的間隔時(shí)間，然后轉(zhuǎn)化成毫秒返回
unsigned long long estimateObjectIdleTime(robj *o) {
    unsigned long long lruclock = LRU_CLOCK();
    if (lruclock >= o->lru) {
        return (lruclock - o->lru) * LRU_CLOCK_RESOLUTION;
    } else {
        return (lruclock + (LRU_CLOCK_MAX - o->lru)) *
                    LRU_CLOCK_RESOLUTION;
    }
}

另外Redis官方文檔里有對于候選數(shù)為5、10在redis2.8無侯選池，以及3.0加侯選池的對比。

四張圖依次是，理論LRU的使用情況、有pool采樣數(shù)為10的候選情況、無pool采樣數(shù)為5的情況、有pool采樣數(shù)為10的情況。其中

• 綠色部分是新添加的key
• 灰色部分是最近使用的key淺
• 灰色部分是替換的key

可以看出采取Redis3.0的采取維護(hù)一個候選淘汰池的方法已經(jīng)能夠接近全局比較情況下也即樸素LRU的結(jié)果。

詳細(xì)的分析可以參考https://redis.io/topics/lru-cache

4.2 以MySQL的InnoDB引擎為例

此處InnoDB的緩存概念不做過多贅述，只簡單介紹其中LRU的應(yīng)用，InnoDB會把cpu頻繁使用的數(shù)據(jù)存儲在主存的緩沖池（Buffer Pool）中，鑒于MySQL在使用過程中存在著經(jīng)常性的全表掃描，所以如果使用樸素LRU必然會頻繁的大面積替換，造成極低的緩存命中率。

所以InnoDB采取了一種冷熱分離的思路，即將整個緩沖池分為冷區(qū)和熱區(qū)或者說年輕區(qū)（New Sublist）和老區(qū)（Old Sublist）

默認(rèn)情況下距離鏈表尾3/8以上的位置稱為新子列表（熱點(diǎn)區(qū)域），以下的位置稱為舊子列表（冷區(qū)域），某個頁面初次加載到緩沖池時(shí)，放在old區(qū)域的頭部。在對某個處于old區(qū)域的緩沖頁進(jìn)行第一次訪問時(shí)，就在它對應(yīng)的控制塊中記錄下這個訪問時(shí)間，如果后續(xù)的訪問時(shí)間和第一次訪問的時(shí)間在某個時(shí)間間隔內(nèi)（默認(rèn)為1000ms），那么該頁面就不會從老的區(qū)域移動到年輕區(qū)域的頭部，否則將他移動到年輕區(qū)域的頭部。

而當(dāng)緩沖池滿時(shí)需要淘汰數(shù)據(jù)就從old區(qū)域的尾部進(jìn)行淘汰，這樣數(shù)據(jù)起碼需要兩次（一次為加載到內(nèi)存，第二次為大于間隔時(shí)間的讀?。┖侠淼牟僮鞑拍芤苿拥侥贻p區(qū)域，有效的預(yù)防了全表掃描帶來的命中率降低問題。

更加詳細(xì)具體的描述可以參見MySQL官方文檔對InnoDB buffer poll的解釋。

到此這篇關(guān)于緩存替換策略及應(yīng)用(以Redis、InnoDB為例)的文章就介紹到這了,更多相關(guān)redis緩存替換策略內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！