一、LRU

LRU（最近最少使用）：LRU策略基于"最近使用原則"，即最近被訪問的項(xiàng)目具有更高的保留優(yōu)先級(jí)。當(dāng)緩存空間已滿，而需要插入新項(xiàng)目時(shí)，LRU策略會(huì)替換最近最少使用的項(xiàng)目。這種策略假設(shè)最近被訪問的項(xiàng)目更有可能在近期再次使用，因此將較長(zhǎng)時(shí)間沒有被使用的項(xiàng)目替換出去。

簡(jiǎn)單來說就是淘汰很久沒用的數(shù)據(jù)或項(xiàng)目。

LRU的實(shí)現(xiàn)

傳統(tǒng) LRU 算法的實(shí)現(xiàn)是基于「鏈表」結(jié)構(gòu)，鏈表中的元素按照操作順序從前往后排列，最新操作的鍵會(huì)被移動(dòng)到表頭，當(dāng)需要內(nèi)存淘汰時(shí)，只需要?jiǎng)h除鏈表尾部的元素即可，因?yàn)殒湵砦膊康脑鼐痛碜罹梦幢皇褂玫脑亍?/p>

Redis 并沒有使用這樣的方式實(shí)現(xiàn) LRU 算法，因?yàn)閭鹘y(tǒng)的 LRU 算法存在兩個(gè)問題：

• 需要用鏈表管理所有的緩存數(shù)據(jù)，這會(huì)帶來額外的空間開銷；
• 當(dāng)有數(shù)據(jù)被訪問時(shí)，需要在鏈表上把該數(shù)據(jù)移動(dòng)到頭端，如果有大量數(shù)據(jù)被訪問，就會(huì)帶來很多鏈表移動(dòng)操作，會(huì)很耗時(shí)，進(jìn)而會(huì)降低 Redis 緩存性能。

Redis 是如何實(shí)現(xiàn) LRU 算法的？

Redis 實(shí)現(xiàn)的是一種近似 LRU 算法，目的是為了更好的節(jié)約內(nèi)存，它的實(shí)現(xiàn)方式是在 Redis 的對(duì)象結(jié)構(gòu)體中添加一個(gè)額外的字段，用于記錄此數(shù)據(jù)的最后一次訪問時(shí)間。

當(dāng) Redis 進(jìn)行內(nèi)存淘汰時(shí)，會(huì)使用隨機(jī)采樣的方式來淘汰數(shù)據(jù)，它是隨機(jī)取 5 個(gè)值（此值可配置），然后淘汰最久沒有使用的那個(gè)。

Redis 實(shí)現(xiàn)的 LRU 算法的優(yōu)點(diǎn)：

• 不用為所有的數(shù)據(jù)維護(hù)一個(gè)大鏈表，節(jié)省了空間占用；
• 不用在每次數(shù)據(jù)訪問時(shí)都移動(dòng)鏈表項(xiàng)，提升了緩存的性能；

但是 LRU 算法有一個(gè)問題，無法解決緩存污染問題，比如應(yīng)用一次讀取了大量的數(shù)據(jù)，而這些數(shù)據(jù)只會(huì)被讀取這一次，那么這些數(shù)據(jù)會(huì)留存在 Redis 緩存中很長(zhǎng)一段時(shí)間，造成緩存污染。

二、LFU

LFU（最不經(jīng)常使用）：LFU策略基于"最不經(jīng)常使用原則"，即使用次數(shù)最少的項(xiàng)目具有較低的保留優(yōu)先級(jí)。當(dāng)緩存空間已滿，而需要插入新項(xiàng)目時(shí)，LFU策略會(huì)替換使用次數(shù)最少的項(xiàng)目。這種策略假設(shè)使用頻率較低的項(xiàng)目在未來也會(huì)繼續(xù)被較少地使用，因此將使用次數(shù)較少的項(xiàng)目替換出去。

        LFU 算法會(huì)記錄每個(gè)數(shù)據(jù)的訪問次數(shù)。當(dāng)一個(gè)數(shù)據(jù)被再次訪問時(shí)，就會(huì)增加該數(shù)據(jù)的訪問次數(shù)。這樣就解決了偶爾被訪問一次之后，數(shù)據(jù)留存在緩存中很長(zhǎng)一段時(shí)間的問題，相比于 LRU 算法也更合理一些。

簡(jiǎn)單來說就是淘汰用的最少的數(shù)據(jù)或項(xiàng)目。

Redis 是如何實(shí)現(xiàn) LFU 算法的？

LFU 算法相比于 LRU 算法的實(shí)現(xiàn)，多記錄了「數(shù)據(jù)的訪問頻次」的信息。Redis 對(duì)象的結(jié)構(gòu)如下：

typedef struct redisObject {
    ...
      
    // 24 bits，用于記錄對(duì)象的訪問信息
    unsigned lru:24;  
    ...
} robj;

Redis 對(duì)象頭中的 lru 字段，在 LRU 算法下和 LFU 算法下使用方式并不相同。

在 LRU 算法中，Redis 對(duì)象頭的 24 bits 的 lru 字段是用來記錄 key 的訪問時(shí)間戳，因此在 LRU 模式下，Redis可以根據(jù)對(duì)象頭中的 lru 字段記錄的值，來比較最后一次 key 的訪問時(shí)間長(zhǎng)，從而淘汰最久未被使用的 key。

在 LFU 算法中，Redis對(duì)象頭的 24 bits 的 lru 字段被分成兩段來存儲(chǔ)，高 16bit 存儲(chǔ) ldt(Last Decrement Time)，用來記錄 key 的訪問時(shí)間戳；低 8bit 存儲(chǔ) logc(Logistic Counter)，用來記錄 key 的訪問頻次。

到此這篇關(guān)于Redis中LRU算法和LFU算法的區(qū)別小結(jié)的文章就介紹到這了,更多相關(guān)Redis LRU算法和LFU算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論