閱讀 Redis 源碼，學習緩存淘汰算法 W-TinyLFU
文末本文轉載自微信公眾號「董澤潤的技術筆記」，作者董澤潤 。轉載本文請聯系董澤潤的技術筆記公眾號。
所有 IT 從業者都接觸過緩存，一定了解基本工作原理，業界流行一句話：緩存就是萬金油，哪里有問題哪里抹一下。那他的本質是什么呢?
上圖代表從 cpu 到底層硬盤不同層次，不同模塊的運行速度，上層多加一層 cache, 就能解決下層的速度慢的問題，這里的慢是指兩點：IO 慢和 cpu 重復計算緩存中間結果
但是 cache 受限于成本，cache size 一般都是固定的，所以數據需要淘汰，由此引出一系列其它問題：緩存一致性、擊穿、雪崩、污染等等，本文通過閱讀 redis 源碼，學習主流淘汰算法
如果不是 leetcode 146 LRU[1] 刷題需要，我想大家也不會手寫 cache, 簡單的實現和工程實踐相距十萬八千里，真正 production ready 的緩存庫非常考驗細節
Redis 緩存淘汰配置
一般 redis 不建義當成存儲使用，只允許當作 cache, 并設置 max-memory, 當內存使用達到最大值時，redis-server 會根據不同配置開始刪除 keys. Redis 從 4.0 版本引進了 LFU[2], 即 Least Frequently Used，4.0 以前默認使用 LRU 即 Least Recently Used
- volatile-lru 只針對設置 expire 過期的 key 進行 lru 淘汰
- allkeys-lru 對所有的 key 進行 lru 淘汰
- volatile-lfu 只針對設置 expire 過期的 key 進行 lfu 淘汰
- allkeys-lfu 對所有的 key 進行 lfu 淘汰
- volatile-random 只針對設置 expire 過期的進行隨機淘汰
- allkeys-random 所有的 key 隨機淘汰
- volatile-ttl 淘汰 ttl 過期時間最小的 key
- noeviction 什么都不做，如果此時內存已滿，系統無法寫入
默認策略是 noeviction, 也就是不驅逐，此時如果寫滿，系統無法寫入，建義設置為 LFU 相關的。LRU 優先淘汰最近未被使用，無法應對冷數據，比如熱 keys 短時間沒有訪問，就會被只使用一次的冷數據沖掉，無法反應真實的使用情況
LFU 能避免上述情況，但是樸素 LFU 實現無法應對突發流量，無法驅逐歷史熱 keys，所以 redis LFU 實現類似于 W-TinyLFU[3], 其中 W 是 windows 的意思，即一定時間窗口后對頻率進行減半，如果不減的話，cache 就成了對歷史數據的統計，而不是緩存
上面還提到突發流量如果應對呢?答案是給新訪問的 key 一個初始頻率值，不至于由于初始值為 0 無法更新頻率
LRU 實現
- int processCommand(redisClient *c) {
- ......
- /* Handle the maxmemory directive.
- *
- * First we try to free some memory if possible (if there are volatile
- * keys in the dataset). If there are not the only thing we can do
- * is returning an error. */
- if (server.maxmemory) {
- int retval = freeMemoryIfNeeded();
- if ((c->cmd->flags & REDIS_CMD_DENYOOM) && retval == REDIS_ERR) {
- flagTransaction(c);
- addReply(c, shared.oomerr);
- return REDIS_OK;
- }
- }
- ......
- }
在每次處理 client 命令時都會調用 freeMemoryIfNeeded 檢查是否有必有驅逐某些 key, 當 redis 實際使用內存達到上限時開始淘汰。但是 redis 做的比較取巧，并沒有對所有的 key 做 lru 隊列，而是按照 maxmemory_samples 參數進行采樣，系統默認是 5 個 key
上面是很經典的一個圖，當到達 10 個 key 時效果更接近理論上的 LRU 算法，但是 cpu 消耗會變高，所以系統默認值就夠了。
LFU 實現
- robj *lookupKey(redisDb *db, robj *key, int flags) {
- dictEntry *de = dictFind(db->dict,key->ptr);
- if (de) {
- robj *val = dictGetVal(de);
- /* Update the access time for the ageing algorithm.
- * Don't do it if we have a saving child, as this will trigger
- * a copy on write madness. */
- if (!hasActiveChildProcess() && !(flags & LOOKUP_NOTOUCH)){
- if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
- updateLFU(val);
- } else {
- val->lru = LRU_CLOCK();
- }
- }
- return val;
- } else {
- returnNULL;
- }
- }
當 lookupKey 訪問某 key 時，會更新 LRU. 從 redis 4.0 開始逐漸引入了 LFU 算法，由于復用了 LRU 字段，所以只能使用 24 bits
- * We split the 24 bits into two fields:
- *
- * 16 bits 8 bits
- * +----------------+--------+
- * + Last decr time | LOG_C |
- * +----------------+--------+
其中低 8 位 counter 用于計數頻率，取值為從 0~255, 但是經過取對數的，所以可以表示很大的訪問頻率
高 16 位 ldt (Last Decrement Time)表示最后一次訪問的 miniutes 時間戳, 用于衰減 counter 值，如果 counter 不衰減的話就變成了對歷史 key 訪問次數的統計了，而不是 LFU
- unsigned long LFUTimeElapsed(unsigned long ldt) {
- unsigned long now = LFUGetTimeInMinutes();
- if (now >= ldt) return now-ldt;
- return 65535-ldt+now;
- }
注意由于 ldt 只用了 16位計數，最大值 65535，所以會出現回卷 rewind
LFU 獲取己有計數
- * counter of the scanned objects if needed. */
- unsigned long LFUDecrAndReturn(robj *o) {
- unsigned long ldt = o->lru >> 8;
- unsigned long counter = o->lru & 255;
- unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;
- if (num_periods)
- counter = (num_periods > counter) ? 0 : counter - num_periods;
- return counter;
- }
num_periods 代表計算出來的待衰減計數，lfu_decay_time 代表衰減系數，默認值是 1，如果 lfu_decay_time 大于 1 衰減速率會變得很慢
最后返回的計數值為衰減之后的，也有可能是 0
LFU 計數更新并取對數
- /* Logarithmically increment a counter. The greater is the current counter value
- * the less likely is that it gets really implemented. Saturate it at 255. */
- uint8_t LFULogIncr(uint8_t counter) {
- if (counter == 255) return 255;
- double r = (double)rand()/RAND_MAX;
- double baseval = counter - LFU_INIT_VAL;
- if (baseval < 0) baseval = 0;
- double p = 1.0/(baseval*server.lfu_log_factor+1);
- if (r < p) counter++;
- return counter;
- }
計數超過 255, 就不用算了，直接返回即可。LFU_INIT_VAL 是初始值，默認是 5
如果減去初始值后 baseval 小于 0 了，說明快過期了，就更傾向于遞增 counter 值
- double p = 1.0/(baseval*server.lfu_log_factor+1);
這個概率算法中 lfu_log_factor 是對數底，默認是 10, 當 counter 值較小時自增的概率較大，如果 counter 較大，傾向于不做任何操作
counter 值從 0~255 可以表示很大的訪問頻率，足夠用了
- # +--------+------------+------------+------------+------------+------------+
- # | factor | 100 hits | 1000 hits | 100K hits | 1M hits | 10M hits |
- # +--------+------------+------------+------------+------------+------------+
- # | 0 | 104 | 255 | 255 | 255 | 255 |
- # +--------+------------+------------+------------+------------+------------+
- # | 1 | 18 | 49 | 255 | 255 | 255 |
- # +--------+------------+------------+------------+------------+------------+
- # | 10 | 10 | 18 | 142 | 255 | 255 |
- # +--------+------------+------------+------------+------------+------------+
- # | 100 | 8 | 11 | 49 | 143 | 255 |
- # +--------+------------+------------+------------+------------+------------+
基于這個特性，我們就可以用 redis-cli --hotkeys 命令，來查看系統中的最近一段時間的熱 key, 非常實用。老版本中是沒這個功能的，需要人工統計
- $ redis-cli --hotkeys
- # Scanning the entire keyspace to find hot keys as well as
- # average sizes per key type. You can use -i 0.1 to sleep 0.1 sec
- # per 100 SCAN commands (not usually needed).
- ......
- [47.62%] Hot key 'key17' found so far with counter 6
- [57.14%] Hot key 'key43' found so far with counter 7
- [57.14%] Hot key 'key14' found so far with counter 6
- [85.71%] Hot key 'key42' found so far with counter 7
- [85.71%] Hot key 'key45' found so far with counter 8
- [95.24%] Hot key 'key50' found so far with counter 7
- -------- summary -------
- Sampled 105 keys in the keyspace!
- hot key found with counter: 7 keyname: key40
- hot key found with counter: 7 keyname: key42
- hot key found with counter: 7 keyname: key50
談談緩存的指標
前面提到的是 redis LFU 實現，這是集中式的緩存，我們還有很多進程的本地緩存。如何評價一個緩存實現的好壞，有好多指標，細節更重要
吞吐量：常說的 QPS, 對標 bucket 實現的 hashmap 復雜度是 O(1), 緩存復雜度要高一些，還有鎖競爭要處理，總之緩存庫實現的效率要高
緩存命中率：光有吞吐量還不夠，緩存命中率也非常關鍵，命中率越高說明引入緩存作用越大
高級特性：緩存指標統計，如何應對緩存擊穿等等
