1 概述

在操作系統(tǒng)的頁面管理中，內(nèi)存會(huì)維護(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)將一些頁換出，或者說踢出，而決定將哪些（個(gè)）頁面踢出就是內(nèi)存替換策略。

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

一般意義下，選取頁面置換算法即選取一個(gè)緩存命中率更高的或者說缺頁率更低的算法，但實(shí)際上有時(shí)候隨著算法緩存命中率提升，算法復(fù)雜度也在上升，所以帶來的系統(tǒng)開銷也是在上升的，所以我們不得不在系統(tǒng)開銷和算法復(fù)雜程度中間取一個(gè)折中，比如Redis中采取的類LRU緩存置換策略實(shí)際上在大多數(shù)情況下比起理想LRU緩存命中率是低的，但理想LRU實(shí)現(xiàn)起來會(huì)給系統(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ù)一個(gè)頁的隊(duì)列，最先進(jìn)入內(nèi)存的頁最先被淘汰，這樣的算法復(fù)雜度低，系統(tǒng)開銷也極低，但是顯然命中率會(huì)下降。

另外考慮一種情況，增大緩存時(shí)，一般意義下緩存的命中率必然會(huì)上升，但是FIFO算法則在有的時(shí)候則會(huì)下降，這種現(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)先被踢出。這個(gè)其實(shí)不難理解，通過一個(gè)訪問順序的隊(duì)列，每次訪問某個(gè)頁，就將此頁移到隊(duì)首，當(dāng)內(nèi)存（緩存）滿了時(shí)優(yōu)先從隊(duì)尾踢出相應(yīng)的頁。（下面給出一個(gè)例子，表來自操作系統(tǒng)導(dǎo)論第22章）

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

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

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

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

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

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

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

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

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

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

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

• allkeys-lru: 對(duì)所有的鍵都采取LRU淘汰
• volatile-lru: 僅對(duì)設(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整體上是一個(gè)大的字典，key是一個(gè)string，而value都會(huì)保存為一個(gè)robj（Redis Object），對(duì)于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為每個(gè)鍵值對(duì)配備的一個(gè)記錄時(shí)間戳的bit位，Redis的LFU替換策略中也使用這個(gè)空間，創(chuàng)建對(duì)象時(shí)會(huì)寫入到lru_clock這個(gè)字段中，訪問對(duì)象時(shí)會(huì)對(duì)其進(jìn)行更新，具體的空間的大小被定義為一個(gè)常量

#define REDIS_LRU_BITS 24

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

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

具體的這個(gè)候選集合結(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ì)算對(duì)象距離上一次訪問的間隔時(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官方文檔里有對(duì)于候選數(shù)為5、10在redis2.8無侯選池，以及3.0加侯選池的對(duì)比。

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

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

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

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

4.2 以MySQL的InnoDB引擎為例

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

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

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

而當(dāng)緩沖池滿時(shí)需要淘汰數(shù)據(jù)就從old區(qū)域的尾部進(jìn)行淘汰，這樣數(shù)據(jù)起碼需要兩次（一次為加載到內(nèi)存，第二次為大于間隔時(shí)間的讀取）合理的操作才能移動(dòng)到年輕區(qū)域，有效的預(yù)防了全表掃描帶來的命中率降低問題。

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

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