LRU算法
- 根據(jù)最近訪問時間，離當(dāng)前時間最遠(yuǎn)的數(shù)據(jù)優(yōu)點(diǎn)被淘汰
- 實(shí)現(xiàn) LRU 算法除了需要 key/value 字典外，還需要附加一個鏈表，鏈表中的元素按照一定的順序進(jìn)行排列。
- 當(dāng)空間滿的時候，會踢掉鏈表尾部的元素。當(dāng)字典的某個元素被訪問時，它在鏈表中的位置會被移動到表頭。
- 鏈表的元素排列順序就是元素最近被訪問的時間順序。
近似 LRU 算法
- redis 使用的不是完全 LRU 算法
- 不使用 LRU 算法，為了節(jié)省內(nèi)存，采用隨機(jī) LRU 算法
- Redis 為每一個 key 增加了一個 24bit 的字段，用來記錄這個 ke y 最后一次被訪問的時間戳
- Redis 3.0 對 LRU 進(jìn)行了優(yōu)化
- 它會維護(hù)一個大小 16 的候選池，其數(shù)據(jù)根據(jù)【訪問時間】進(jìn)行排序
- 第一次隨機(jī)選取的 5 個 key 都會放入池中
- 后續(xù)每次隨機(jī)選取的 key，只有【訪問時間】小于候選池中【最小時間】的 key 才會放入池中，直到候選池被放滿。
- 也就是比候選池更老的數(shù)據(jù)才會放入
- 當(dāng)放滿后，如果有新的 key 放入，則移除候選池中【訪問時間】最小的 key
- 當(dāng)需要淘汰時，則直接淘汰候選池中【訪問時間】最小的 key
- 如何采樣就是看 maxmemory-policy 的配置
- 如果是 allkeys 就是從所有的 key 字典中隨機(jī)
- 如果是 volatile 就從帶過期時間的 key 字典中隨機(jī)。
- 每次采樣多少個 key 看的是 maxmemory_samples 的配置，默認(rèn)為 5
LFU
- Redis 4.0 里引入了一個新的淘汰策略 —— LFU（Least Frequently Used） ，作者認(rèn)為它比 LRU 更加優(yōu)秀。
- LFU 表示按照最近【訪問頻率】進(jìn)行淘汰，它比 LRU 更加精準(zhǔn)地表示了一個 key 被訪問的熱度。
- 如果一個 key 長時間不被訪問，只是剛剛偶然被用戶訪問了一下，那么在使用 LRU 算法下它是不容易被淘汰的，因?yàn)?LRU 算法認(rèn)為當(dāng)前這個 key 是很熱的。
- 而 LFU 是需要追蹤最近一段時間的訪問頻率，如果某個 key 只是偶然被訪問一次是不足以變得很熱的，它需要在近期一段時間內(nèi)被訪問很多次才有機(jī)會被認(rèn)為很熱。
Redis 對象熱度的數(shù)據(jù)結(jié)構(gòu)
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; // 引用計(jì)數(shù)
void *ptr; // 對象的 body
} robj;
LRU 模式
- 在 LRU 模式下，lru 字段存儲的是 Redis 時鐘 server.lruclock
- 它是一個 24bit 的時間戳
- 默認(rèn)是 Unix 時間戳對 2^24 取模的結(jié)果，大約 97 天清零一次。
- 當(dāng)某個 key 被訪問一次，它的對象頭的 lru 字段值就會被更新為 server.lruclock。
LFU 模式
- 在 LFU 模式下，lru 字段 24 個 bit 用來存儲兩個值，它分別是訪問頻次（logc，logistic counter）和上一次訪問的更新時間（ldt，last decrement time）
- 訪問頻次
- logc 是 8 個 bit，用來存儲訪問頻次
- 因?yàn)?8 個 bit 能表示的最大整數(shù)值為 255，存儲頻次肯定遠(yuǎn)遠(yuǎn)不夠，所以這 8 個 bit 存儲的是頻次的對數(shù)值，并且這個值還會隨時間衰減。
- 如果它的值比較小，那么就很容易被回收。為了確保新創(chuàng)建的對象不被回收，新對象的這 8 個 bit 會初始化為一個大于零的值，默認(rèn)是 LFU_INIT_VAL=5。
- 上一次訪問頻次的更新時間
- ldt 是 16 個位，用來存儲上一次 logc 的更新時間
- 因?yàn)橹挥?16 位，所以精度不可能很高。
- 它取的是分鐘時間戳對 2^16 進(jìn)行取模，大約每隔 45 天就會折返
