LRU背景介紹

LRU，全稱Least Recently Used-最近最少使用，是一種內(nèi)存淘汰算法，筆者最早接觸到這個(gè)算法是在本科操作系統(tǒng)的課程上，講到操作系統(tǒng)的虛擬內(nèi)存頁(yè)面置換的時(shí)候提到的。
這個(gè)經(jīng)典內(nèi)存淘汰算法也被很多其它地方使用，經(jīng)常作為緩存的淘汰策略，緩存作為一種提升查詢速度的手段，本身就是為了將持久化到硬盤(pán)上的數(shù)據(jù)中的熱點(diǎn)部分加載到讀取速度更快的內(nèi)存中（局部性原理），而內(nèi)存肯定是加載不了磁盤(pán)中的全部數(shù)據(jù)的，那就涉及到如果加載到緩存時(shí)發(fā)現(xiàn)內(nèi)存滿了怎么辦？需要從緩存中淘汰掉誰(shuí)？于是很自然的會(huì)想到淘汰內(nèi)存中最冷門(mén)的記錄*，于是LRU算法定義了標(biāo)記跟蹤到這個(gè)最冷門(mén)數(shù)據(jù)的方法。

手機(jī)后臺(tái)也是一種LRU

操作系統(tǒng)中的LRU

虛擬內(nèi)存

操作系統(tǒng)作為用戶應(yīng)用與硬件設(shè)備之間的代理人，有著屏蔽底層不同硬件邏輯的職責(zé)，例如內(nèi)存條，

內(nèi)存條

操作系統(tǒng)的這種封裝底層硬件、為上層用戶應(yīng)用提供API接口的思想也是計(jì)算機(jī)領(lǐng)域的核心思想，即分層思想，每一層只做當(dāng)前這一層的封裝功能，屏蔽掉底層的異構(gòu)特性后為上一層提供抽象的統(tǒng)一的API接口，學(xué)會(huì)抽象是程序員的核心思維，無(wú)論是操作系統(tǒng)、TCP/IP網(wǎng)絡(luò)架構(gòu)、Java的Spring容器，都是這種思想的體現(xiàn)。

操作系統(tǒng)的虛擬內(nèi)存通過(guò)頁(yè)表為硬件和用戶應(yīng)用之間提供了固定內(nèi)存大小和隔離不同進(jìn)程內(nèi)存空間的功能，本文重點(diǎn)討論固定內(nèi)存大小的實(shí)現(xiàn)。操作系統(tǒng)屏蔽了底層硬件內(nèi)存的大小，例如對(duì)于32位操作系統(tǒng)來(lái)說(shuō)，不論你用多少G的內(nèi)存條，進(jìn)程可用的內(nèi)存空間都是4G（用戶態(tài)+核心態(tài)），如果實(shí)際內(nèi)存條根本沒(méi)有這么大的時(shí)候，就只能在內(nèi)存條中存放部分?jǐn)?shù)據(jù)，其它的內(nèi)存數(shù)據(jù)存儲(chǔ)在磁盤(pán)中，這就涉及到誰(shuí)留在內(nèi)存，誰(shuí)又該放在磁盤(pán)上的經(jīng)典哲學(xué)問(wèn)題。

虛擬內(nèi)存

虛擬內(nèi)存與LRU

操作系統(tǒng)往往采用的就是LRU算法判斷那些經(jīng)常被訪問(wèn)的熱點(diǎn)數(shù)據(jù)，把它們留在內(nèi)存中，而將最近最少使用的內(nèi)存數(shù)據(jù)淘汰到磁盤(pán)上。龍龍的奇妙比喻：想象你是一個(gè)皇帝，操作系統(tǒng)是一個(gè)太監(jiān)，太監(jiān)總管根據(jù)你翻牌子的歷史行為預(yù)判你今晚找哪位嬪妃侍寢，后宮佳麗三千，皇上選擇的耐心有限，于是太監(jiān)總管將最近最少翻牌子的嬪妃直接移出牌子池了。

翻牌子

其它頁(yè)面置換（淘汰）算法

• 最佳置換算法（OPT），太監(jiān)總管能預(yù)知未來(lái)，知道哪個(gè)嬪妃將來(lái)永遠(yuǎn)不會(huì)被寵幸，直接將她們淘汰，但這是不可能的，所以作為淘汰算法的評(píng)價(jià)標(biāo)準(zhǔn)
• 先進(jìn)先出置換算法（FIFO），太監(jiān)總管比較耿直，永遠(yuǎn)公平公正，嚴(yán)格按照嬪妃的先來(lái)后到放牌子
• 最少使用（LFU）置換算法，LRU關(guān)注每個(gè)嬪妃最后被臨幸的時(shí)間，LFU關(guān)注每個(gè)嬪妃歷史被寵幸的頻率，例如華妃歷史上天天被臨幸，但是剛好最近一周不被臨幸了，對(duì)于LRU來(lái)說(shuō)可能會(huì)被淘汰，對(duì)于LFU來(lái)說(shuō)可能會(huì)保留；甄嬛早期天天不被臨幸，但是最近一周被皇帝看上了，如果太監(jiān)總管使用LRU-甄嬛必定是放到第一位，如果使用LFU-甄嬛這個(gè)新寵可能還是上不了牌子池

emmm...所以顯然LRU更得圣心啊。。。

redis與LRU

redis的過(guò)期時(shí)間淘汰方式

一般情況中redis作為緩存是通過(guò)Expire KEY_NAME TIME_IN_SECONDS命令給key設(shè)置一個(gè)固定的淘汰時(shí)間，key到期后redis通過(guò)惰性刪除或定期刪除將過(guò)期的key從內(nèi)存中清理掉。

redis的惰性刪除與定期刪除：
redis的緩存過(guò)期處理策略有三種實(shí)現(xiàn)方案：

1. 定時(shí)刪除，每當(dāng)給一個(gè)key設(shè)置expire的時(shí)候，都啟動(dòng)一個(gè)定時(shí)器，在key過(guò)期的時(shí)候立刻刪除。優(yōu)點(diǎn)是節(jié)省內(nèi)存，到期立刻清理；缺點(diǎn)是浪費(fèi)CPU時(shí)間做清理工作，創(chuàng)建了大量定時(shí)器，性能影響嚴(yán)重
2. 惰性刪除，每次get key的時(shí)候看看是否過(guò)期。優(yōu)點(diǎn)和1剛好相反，節(jié)省CPU時(shí)間；缺點(diǎn)是可能有長(zhǎng)期不讀的key一直賴在內(nèi)存，浪費(fèi)內(nèi)存（內(nèi)存泄漏）
3. 定期刪除，1和2的方案折衷，自如阿姨定期打掃一次房間，1和2的優(yōu)缺點(diǎn)都有
   最終redis采用的是惰性刪除和定期刪除的結(jié)合。

redis的LRU

以上清理都是發(fā)生在redis內(nèi)存充足的時(shí)候，對(duì)于已經(jīng)過(guò)期的key進(jìn)行清理。
redis作為一種數(shù)據(jù)緩存層而存在的時(shí)候，也會(huì)遇到上文中操作系統(tǒng)的場(chǎng)景，當(dāng)越來(lái)越多數(shù)據(jù)被緩存時(shí)，如果內(nèi)存不夠用了怎么辦，redis提供了六種淘汰方式

config set maxmemory-policy volatile-lru

maxmemory-policy 六種方式

• volatile-lru：只對(duì)設(shè)置了過(guò)期時(shí)間的key進(jìn)行LRU（默認(rèn)值）
• allkeys-lru ： 刪除lru算法的key
• volatile-random：隨機(jī)刪除即將過(guò)期key
• allkeys-random：隨機(jī)刪除
• volatile-ttl ： 刪除即將過(guò)期的
• noeviction ： 永不過(guò)期，返回錯(cuò)誤

筆者使用模塊中的LRU

筆者工作中使用的模塊可以理解為封裝了各個(gè)數(shù)據(jù)源的查詢、篩選、分頁(yè)、排序功能，對(duì)外暴露出簡(jiǎn)單的select xxx from view where ... 的語(yǔ)句，可以理解為對(duì)MySQL view視圖概念的模仿，對(duì)外只提供只讀的功能。因而該模塊也對(duì)查詢操作進(jìn)行了內(nèi)存緩存，而緩存的淘汰算法同樣是采用了經(jīng)典的LRU算法。

筆者使用模塊中的LRU

LRU的實(shí)現(xiàn)——雙向鏈表+哈希表

LRU cache作為一種cache，put/get操作的時(shí)間復(fù)雜度要求是O(1)，因此需要采用哈希表來(lái)存儲(chǔ)KV的映射關(guān)系。
同時(shí)需要有一種數(shù)據(jù)結(jié)構(gòu)，支持將最近最新訪問(wèn)過(guò)的節(jié)點(diǎn)排在最前面 && 將最近最少訪問(wèn)的節(jié)點(diǎn)移除出去，當(dāng)然可以采用在Node[]數(shù)組中記錄Node.lastestVisitTime時(shí)間戳，然后移除的時(shí)候排個(gè)序，這樣的話每次排序都需要O(logn)的快排耗時(shí)，為保證內(nèi)存淘汰的時(shí)間復(fù)雜度也為O(1)，需要采用雙向鏈表，講最新訪問(wèn)的節(jié)點(diǎn)放在表頭，同時(shí)將表尾的節(jié)點(diǎn)踢出去

綜上，LRU的實(shí)現(xiàn)需要將哈希表與雙向鏈表的數(shù)據(jù)結(jié)構(gòu)進(jìn)行組合，通過(guò)冗余的一層數(shù)據(jù)結(jié)構(gòu)來(lái)優(yōu)化put/get的性能。

LRU cache的結(jié)構(gòu)圖如下

哈希表+雙向鏈表

LRU cache的get操作流程動(dòng)圖演示

LRU cache的get操作流程動(dòng)圖演示

LRU cache的put操作流程動(dòng)圖演示

LRU cache的put操作流程動(dòng)圖演示

LRU cache的偽代碼如下

class LRUCached:
    哈希表 # key -> Node(key, value)
    雙向鏈表 # Node -> Node -> Node

    capacity = 10 # 容量，超過(guò)大小按照LRU算法開(kāi)始淘汰

    def get(key):
        if(key 不存在):
            return -1
        else:
            將數(shù)據(jù)挪到雙向鏈表的表頭 # 調(diào)用一次put(key, value)
            return 哈希表.get(key).value
    
    def put(key, value):
        Node node = new Node()
        if(key 已存在):
            雙向鏈表.remove(哈希.get(key))
            雙向鏈表.addFirst(node)
        else: # key不存在
            哈希表.put(key, value)
            雙向鏈表.addFirst(node)
            if(雙向鏈表.size > capacity):
                雙向鏈表.removeLast()
                哈希表.remove(雙向鏈表的lastNode.key)

reference

1. ^LRU-百度百科
2. ^LRU 策略詳解和實(shí)現(xiàn)- LRU緩存機(jī)制- 力扣（LeetCode）
3. ^LRU原理和Redis實(shí)現(xiàn)——一個(gè)今日頭條的面試題- 知乎
4. ^《redis設(shè)計(jì)與實(shí)現(xiàn)》
5. ^《現(xiàn)代操作系統(tǒng)》
6. ^Redis的LRU算法