LRU背景介紹

LRU拭嫁，全稱Least Recently Used-最近最少使用，是一種內(nèi)存淘汰算法络凿，筆者最早接觸到這個(gè)算法是在本科操作系統(tǒng)的課程上憨攒，講到操作系統(tǒng)的虛擬內(nèi)存頁面置換的時(shí)候提到的。
這個(gè)經(jīng)典內(nèi)存淘汰算法也被很多其它地方使用惧盹，經(jīng)常作為緩存的淘汰策略乳幸，緩存作為一種提升查詢速度的手段瞪讼，本身就是為了將持久化到硬盤上的數(shù)據(jù)中的熱點(diǎn)部分加載到讀取速度更快的內(nèi)存中（局部性原理），而內(nèi)存肯定是加載不了磁盤中的全部數(shù)據(jù)的粹断，那就涉及到如果加載到緩存時(shí)發(fā)現(xiàn)內(nèi)存滿了怎么辦符欠？需要從緩存中淘汰掉誰？于是很自然的會(huì)想到淘汰內(nèi)存中最冷門的記錄*姿染，于是LRU算法定義了標(biāo)記跟蹤到這個(gè)最冷門數(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ì)抽象是程序員的核心思維奈懒，無論是操作系統(tǒng)奠涌、TCP/IP網(wǎng)絡(luò)架構(gòu)、Java的Spring容器磷杏，都是這種思想的體現(xiàn)溜畅。

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

虛擬內(nèi)存

虛擬內(nèi)存與LRU

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

翻牌子

其它頁面置換（淘汰）算法

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

emmm...所以顯然LRU更得圣心啊嫩痰。。窍箍。

redis與LRU

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

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

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

1. 定時(shí)刪除椰棘，每當(dāng)給一個(gè)key設(shè)置expire的時(shí)候纺棺，都啟動(dòng)一個(gè)定時(shí)器，在key過期的時(shí)候立刻刪除邪狞。優(yōu)點(diǎn)是節(jié)省內(nèi)存祷蝌，到期立刻清理；缺點(diǎn)是浪費(fèi)CPU時(shí)間做清理工作帆卓，創(chuàng)建了大量定時(shí)器巨朦，性能影響嚴(yán)重
2. 惰性刪除米丘，每次get key的時(shí)候看看是否過期。優(yōu)點(diǎn)和1剛好相反糊啡，節(jié)省CPU時(shí)間拄查；缺點(diǎn)是可能有長期不讀的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)過期的key進(jìn)行清理。
redis作為一種數(shù)據(jù)緩存層而存在的時(shí)候睛挚，也會(huì)遇到上文中操作系統(tǒng)的場(chǎng)景邪蛔，當(dāng)越來越多數(shù)據(jù)被緩存時(shí)，如果內(nèi)存不夠用了怎么辦扎狱，redis提供了六種淘汰方式

config set maxmemory-policy volatile-lru

maxmemory-policy 六種方式

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

筆者使用模塊中的LRU

筆者工作中使用的模塊可以理解為封裝了各個(gè)數(shù)據(jù)源的查詢、篩選淤击、分頁匠抗、排序功能，對(duì)外暴露出簡(jiǎn)單的select xxx from view where ... 的語句污抬，可以理解為對(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)射赛，因此需要采用哈希表來存儲(chǔ)KV的映射關(guān)系多柑。
同時(shí)需要有一種數(shù)據(jù)結(jié)構(gòu)，支持將最近最新訪問過的節(jié)點(diǎn)排在最前面 && 將最近最少訪問的節(jié)點(diǎn)移除出去楣责，當(dāng)然可以采用在Node[]數(shù)組中記錄Node.lastestVisitTime時(shí)間戳竣灌，然后移除的時(shí)候排個(gè)序，這樣的話每次排序都需要O(logn)的快排耗時(shí)秆麸，為保證內(nèi)存淘汰的時(shí)間復(fù)雜度也為O(1)初嘹，需要采用雙向鏈表，講最新訪問的節(jié)點(diǎn)放在表頭沮趣，同時(shí)將表尾的節(jié)點(diǎn)踢出去

綜上屯烦，LRU的實(shí)現(xiàn)需要將哈希表與雙向鏈表的數(shù)據(jù)結(jié)構(gòu)進(jìn)行組合，通過冗余的一層數(shù)據(jù)結(jié)構(gòu)來優(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 # 容量驻龟，超過大小按照LRU算法開始淘汰

    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算法