一、LRU

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

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

LRU的實現(xiàn)

傳統(tǒng) LRU 算法的實現(xiàn)是基于「鏈表」結(jié)構(gòu)，鏈表中的元素按照操作順序從前往后排列，最新操作的鍵會被移動到表頭，當(dāng)需要內(nèi)存淘汰時，只需要刪除鏈表尾部的元素即可，因為鏈表尾部的元素就代表最久未被使用的元素。

Redis 并沒有使用這樣的方式實現(xiàn) LRU 算法，因為傳統(tǒng)的 LRU 算法存在兩個問題：

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

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

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

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

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

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

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

二、LFU

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

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

簡單來說就是淘汰用的最少的數(shù)據(jù)或項目。

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

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

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

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

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

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

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

最新評論