LRU算法

• 根據最近訪問時間，離當前時間最遠的數(shù)據優(yōu)點被淘汰
• 實現(xiàn) LRU 算法除了需要 key/value 字典外，還需要附加一個鏈表，鏈表中的元素按照一定的順序進行排列。
• 當空間滿的時候，會踢掉鏈表尾部的元素。當字典的某個元素被訪問時，它在鏈表中的位置會被移動到表頭。
  • 鏈表的元素排列順序就是元素最近被訪問的時間順序。

近似 LRU 算法

• redis 使用的不是完全 LRU 算法
  • 不使用 LRU 算法，為了節(jié)省內存，采用隨機 LRU 算法
  • Redis 為每一個 key 增加了一個 24bit 的字段，用來記錄這個 ke y 最后一次被訪問的時間戳
• Redis 3.0 對 LRU 進行了優(yōu)化
  • 它會維護一個大小 16 的候選池，其數(shù)據根據【訪問時間】進行排序
  • 第一次隨機選取的 5 個 key 都會放入池中
  • 后續(xù)每次隨機選取的 key，只有【訪問時間】小于候選池中【最小時間】的 key 才會放入池中，直到候選池被放滿。
    • 也就是比候選池更老的數(shù)據才會放入
  • 當放滿后，如果有新的 key 放入，則移除候選池中【訪問時間】最小的 key
  • 當需要淘汰時，則直接淘汰候選池中【訪問時間】最小的 key
• 如何采樣就是看 maxmemory-policy 的配置
  • 如果是 allkeys 就是從所有的 key 字典中隨機
  • 如果是 volatile 就從帶過期時間的 key 字典中隨機。
• 每次采樣多少個 key 看的是 maxmemory_samples 的配置，默認為 5

LFU

• Redis 4.0 里引入了一個新的淘汰策略 —— LFU（Least Frequently Used） ，作者認為它比 LRU 更加優(yōu)秀。
• LFU 表示按照最近【訪問頻率】進行淘汰，它比 LRU 更加精準地表示了一個 key 被訪問的熱度。
  • 如果一個 key 長時間不被訪問，只是剛剛偶然被用戶訪問了一下，那么在使用 LRU 算法下它是不容易被淘汰的，因為 LRU 算法認為當前這個 key 是很熱的。
  • 而 LFU 是需要追蹤最近一段時間的訪問頻率，如果某個 key 只是偶然被訪問一次是不足以變得很熱的，它需要在近期一段時間內被訪問很多次才有機會被認為很熱。

Redis 對象熱度的數(shù)據結構

Redis 的所有對象頭中都有一個字段，用來記錄對象的熱度， 大小為 24bit。

// redis 的對象頭
typedef struct redisObject {
    unsigned type:4; // 對象類型如 zset/set/hash 等等
    unsigned encoding:4; // 對象編碼如 ziplist/intset/skiplist 等等
    unsigned lru:24; // lfu：熱度/ lru：時間戳
    int refcount; // 引用計數(shù)
    void *ptr; // 對象的 body
} robj;

LRU 模式

• 在 LRU 模式下，lru 字段存儲的是 Redis 時鐘 server.lruclock
• 它是一個 24bit 的時間戳
  • 默認是 Unix 時間戳對 2^24 取模的結果，大約 97 天清零一次。
• 當某個 key 被訪問一次，它的對象頭的 lru 字段值就會被更新為 server.lruclock。

LFU 模式

• 在 LFU 模式下，lru 字段 24 個 bit 用來存儲兩個值，它分別是訪問頻次（logc，logistic counter）和上一次訪問的更新時間（ldt，last decrement time）
• 訪問頻次
  • logc 是 8 個 bit，用來存儲訪問頻次
  • 因為 8 個 bit 能表示的最大整數(shù)值為 255，存儲頻次肯定遠遠不夠，所以這 8 個 bit 存儲的是頻次的對數(shù)值，并且這個值還會隨時間衰減。
  • 如果它的值比較小，那么就很容易被回收。為了確保新創(chuàng)建的對象不被回收，新對象的這 8 個 bit 會初始化為一個大于零的值，默認是 LFU_INIT_VAL=5。
• 上一次訪問頻次的更新時間
  • ldt 是 16 個位，用來存儲上一次 logc 的更新時間
  • 因為只有 16 位，所以精度不可能很高。
  • 它取的是分鐘時間戳對 2^16 進行取模，大約每隔 45 天就會折返