自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

閱讀 Redis 源碼，學(xué)習(xí)緩存淘汰算法 W-TinyLFU

作者： 董澤潤
存儲 算法 Redis
所有 IT 從業(yè)者都接觸過緩存，一定了解基本工作原理，業(yè)界流行一句話：緩存就是萬金油，哪里有問題哪里抹一下。那他的本質(zhì)是什么呢?

 

[[433812]]

文末本文轉(zhuǎn)載自微信公眾號「董澤潤的技術(shù)筆記」，作者董澤潤  。轉(zhuǎn)載本文請聯(lián)系董澤潤的技術(shù)筆記公眾號。

所有 IT 從業(yè)者都接觸過緩存，一定了解基本工作原理，業(yè)界流行一句話：緩存就是萬金油，哪里有問題哪里抹一下。那他的本質(zhì)是什么呢?

上圖代表從 cpu 到底層硬盤不同層次，不同模塊的運行速度，上層多加一層 cache, 就能解決下層的速度慢的問題，這里的慢是指兩點：IO 慢和 cpu 重復(fù)計算緩存中間結(jié)果

但是 cache 受限于成本，cache size 一般都是固定的，所以數(shù)據(jù)需要淘汰，由此引出一系列其它問題：緩存一致性、擊穿、雪崩、污染等等，本文通過閱讀 redis 源碼，學(xué)習(xí)主流淘汰算法

如果不是 leetcode 146 LRU[1] 刷題需要，我想大家也不會手寫 cache, 簡單的實現(xiàn)和工程實踐相距十萬八千里，真正 production ready 的緩存庫非?？简灱毠?jié)

Redis 緩存淘汰配置

一般 redis 不建義當(dāng)成存儲使用，只允許當(dāng)作 cache, 并設(shè)置 max-memory, 當(dāng)內(nèi)存使用達到最大值時，redis-server 會根據(jù)不同配置開始刪除 keys. Redis 從 4.0 版本引進了 LFU[2], 即 Least Frequently Used，4.0 以前默認使用 LRU 即 Least Recently Used

  • volatile-lru 只針對設(shè)置 expire 過期的 key 進行 lru 淘汰
  • allkeys-lru 對所有的 key 進行 lru 淘汰
  • volatile-lfu 只針對設(shè)置 expire 過期的 key 進行 lfu 淘汰
  • allkeys-lfu 對所有的 key 進行 lfu 淘汰
  • volatile-random 只針對設(shè)置 expire 過期的進行隨機淘汰
  • allkeys-random 所有的 key 隨機淘汰
  • volatile-ttl 淘汰 ttl 過期時間最小的 key
  • noeviction 什么都不做，如果此時內(nèi)存已滿，系統(tǒng)無法寫入

默認策略是 noeviction, 也就是不驅(qū)逐，此時如果寫滿，系統(tǒng)無法寫入，建義設(shè)置為 LFU 相關(guān)的。LRU 優(yōu)先淘汰最近未被使用，無法應(yīng)對冷數(shù)據(jù)，比如熱 keys 短時間沒有訪問，就會被只使用一次的冷數(shù)據(jù)沖掉，無法反應(yīng)真實的使用情況

LFU 能避免上述情況，但是樸素 LFU 實現(xiàn)無法應(yīng)對突發(fā)流量，無法驅(qū)逐歷史熱 keys，所以 redis LFU 實現(xiàn)類似于 W-TinyLFU[3], 其中 W 是 windows 的意思，即一定時間窗口后對頻率進行減半，如果不減的話，cache 就成了對歷史數(shù)據(jù)的統(tǒng)計，而不是緩存

上面還提到突發(fā)流量如果應(yīng)對呢?答案是給新訪問的 key 一個初始頻率值，不至于由于初始值為 0 無法更新頻率

LRU 實現(xiàn)

  1. int processCommand(redisClient *c) { 
  2.     ...... 
  3.     /* Handle the maxmemory directive. 
  4.      * 
  5.      * First we try to free some memory if possible (if there are volatile 
  6.      * keys in the dataset). If there are not the only thing we can do 
  7.      * is returning an error. */ 
  8.     if (server.maxmemory) { 
  9.         int retval = freeMemoryIfNeeded(); 
  10.         if ((c->cmd->flags & REDIS_CMD_DENYOOM) && retval == REDIS_ERR) { 
  11.             flagTransaction(c); 
  12.             addReply(c, shared.oomerr); 
  13.             return REDIS_OK; 
  14.         } 
  15.     } 
  16.     ...... 
  17. } 

在每次處理 client 命令時都會調(diào)用 freeMemoryIfNeeded 檢查是否有必有驅(qū)逐某些 key, 當(dāng) redis 實際使用內(nèi)存達到上限時開始淘汰。但是 redis 做的比較取巧，并沒有對所有的 key 做 lru 隊列，而是按照 maxmemory_samples 參數(shù)進行采樣，系統(tǒng)默認是 5 個 key

上面是很經(jīng)典的一個圖，當(dāng)?shù)竭_ 10 個 key 時效果更接近理論上的 LRU 算法，但是 cpu 消耗會變高，所以系統(tǒng)默認值就夠了。

LFU 實現(xiàn)

  1. robj *lookupKey(redisDb *db, robj *key, int flags) { 
  2.     dictEntry *de = dictFind(db->dict,key->ptr); 
  3.     if (de) { 
  4.         robj *val = dictGetVal(de); 
  5.  
  6.         /* Update the access time for the ageing algorithm. 
  7.          * Don't do it if we have a saving child, as this will trigger 
  8.          * a copy on write madness. */ 
  9.         if (!hasActiveChildProcess() && !(flags & LOOKUP_NOTOUCH)){ 
  10.             if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) { 
  11.                 updateLFU(val); 
  12.             } else { 
  13.                 val->lru = LRU_CLOCK(); 
  14.             } 
  15.         } 
  16.         return val; 
  17.     } else { 
  18.         returnNULL; 
  19.     } 
  20. } 

當(dāng) lookupKey 訪問某 key 時，會更新 LRU. 從 redis 4.0 開始逐漸引入了 LFU 算法，由于復(fù)用了 LRU 字段，所以只能使用 24 bits

  1. * We split the 24 bits into two fields: 
  2. * 
  3. *     16 bits      8 bits 
  4. * +----------------+--------+ 
  5. * + Last decr time | LOG_C  | 
  6. * +----------------+--------+ 

其中低 8 位 counter 用于計數(shù)頻率，取值為從 0~255, 但是經(jīng)過取對數(shù)的，所以可以表示很大的訪問頻率

高 16 位 ldt (Last Decrement Time)表示最后一次訪問的 miniutes 時間戳, 用于衰減 counter 值，如果 counter 不衰減的話就變成了對歷史 key 訪問次數(shù)的統(tǒng)計了，而不是 LFU

  1. unsigned long LFUTimeElapsed(unsigned long ldt) { 
  2.     unsigned long now = LFUGetTimeInMinutes(); 
  3.     if (now >= ldt) return now-ldt; 
  4.     return 65535-ldt+now; 
  5. } 

注意由于 ldt 只用了 16位計數(shù)，最大值 65535，所以會出現(xiàn)回卷 rewind

LFU 獲取己有計數(shù)

  1.  * counter of the scanned objects if needed. */ 
  2. unsigned long LFUDecrAndReturn(robj *o) { 
  3.     unsigned long ldt = o->lru >> 8; 
  4.     unsigned long counter = o->lru & 255; 
  5.     unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0; 
  6.     if (num_periods) 
  7.         counter = (num_periods > counter) ? 0 : counter - num_periods; 
  8.     return counter; 
  9. } 

num_periods 代表計算出來的待衰減計數(shù)，lfu_decay_time 代表衰減系數(shù)，默認值是 1，如果 lfu_decay_time 大于 1 衰減速率會變得很慢

最后返回的計數(shù)值為衰減之后的，也有可能是 0

LFU 計數(shù)更新并取對數(shù)

  1. /* Logarithmically increment a counter. The greater is the current counter value 
  2.  * the less likely is that it gets really implemented. Saturate it at 255. */ 
  3. uint8_t LFULogIncr(uint8_t counter) { 
  4.     if (counter == 255) return 255; 
  5.     double r = (double)rand()/RAND_MAX; 
  6.     double baseval = counter - LFU_INIT_VAL; 
  7.     if (baseval < 0) baseval = 0; 
  8.     double p = 1.0/(baseval*server.lfu_log_factor+1); 
  9.     if (r < p) counter++; 
  10.     return counter; 
  11. } 

計數(shù)超過 255, 就不用算了，直接返回即可。LFU_INIT_VAL 是初始值，默認是 5

如果減去初始值后 baseval 小于 0 了，說明快過期了，就更傾向于遞增 counter 值

  1. double p = 1.0/(baseval*server.lfu_log_factor+1); 

這個概率算法中 lfu_log_factor 是對數(shù)底，默認是 10, 當(dāng) counter 值較小時自增的概率較大，如果 counter 較大，傾向于不做任何操作

counter 值從 0~255 可以表示很大的訪問頻率，足夠用了

  1. # +--------+------------+------------+------------+------------+------------+ 
  2. # | factor | 100 hits   | 1000 hits  | 100K hits  | 1M hits    | 10M hits   | 
  3. # +--------+------------+------------+------------+------------+------------+ 
  4. # | 0      | 104        | 255        | 255        | 255        | 255        | 
  5. # +--------+------------+------------+------------+------------+------------+ 
  6. # | 1      | 18         | 49         | 255        | 255        | 255        | 
  7. # +--------+------------+------------+------------+------------+------------+ 
  8. # | 10     | 10         | 18         | 142        | 255        | 255        | 
  9. # +--------+------------+------------+------------+------------+------------+ 
  10. # | 100    | 8          | 11         | 49         | 143        | 255        | 
  11. # +--------+------------+------------+------------+------------+------------+ 

基于這個特性，我們就可以用 redis-cli --hotkeys 命令，來查看系統(tǒng)中的最近一段時間的熱 key, 非常實用。老版本中是沒這個功能的，需要人工統(tǒng)計

  1. $ redis-cli --hotkeys 
  2. # Scanning the entire keyspace to find hot keys as well as 
  3. # average sizes per key type.  You can use -i 0.1 to sleep 0.1 sec 
  4. # per 100 SCAN commands (not usually needed). 
  5. ...... 
  6. [47.62%] Hot key 'key17' found so far with counter 6 
  7. [57.14%] Hot key 'key43' found so far with counter 7 
  8. [57.14%] Hot key 'key14' found so far with counter 6 
  9. [85.71%] Hot key 'key42' found so far with counter 7 
  10. [85.71%] Hot key 'key45' found so far with counter 8 
  11. [95.24%] Hot key 'key50' found so far with counter 7 
  12.  
  13. -------- summary ------- 
  14.  
  15. Sampled 105 keys in the keyspace! 
  16. hot key found with counter: 7 keyname: key40 
  17. hot key found with counter: 7 keyname: key42 
  18. hot key found with counter: 7 keyname: key50 

談?wù)劸彺娴闹笜?biāo)

前面提到的是 redis LFU 實現(xiàn)，這是集中式的緩存，我們還有很多進程的本地緩存。如何評價一個緩存實現(xiàn)的好壞，有好多指標(biāo)，細節(jié)更重要

吞吐量：常說的 QPS, 對標(biāo) bucket 實現(xiàn)的 hashmap 復(fù)雜度是 O(1), 緩存復(fù)雜度要高一些，還有鎖競爭要處理，總之緩存庫實現(xiàn)的效率要高

緩存命中率：光有吞吐量還不夠，緩存命中率也非常關(guān)鍵，命中率越高說明引入緩存作用越大

 

高級特性：緩存指標(biāo)統(tǒng)計，如何應(yīng)對緩存擊穿等等

 

責(zé)任編輯：武曉燕 來源： 董澤潤的技術(shù)筆記
redis 淘汰算法
相關(guān)推薦

2021-07-12 22:50:29

Caffeine數(shù)據(jù)結(jié)構(gòu)

2021-07-11 18:06:18

緩存過期淘汰

2020-02-19 19:18:02

緩存查詢速度淘汰算法

2021-01-19 10:39:03

Redis緩存數(shù)據(jù)

2024-08-19 09:13:02

2024-06-04 07:38:10

2024-11-11 17:12:22

2017-06-07 14:58:39

Redis源碼學(xué)習(xí)Redis事務(wù)

2018-07-31 14:49:45

編程語言Java源碼

2013-12-24 10:05:04

memcached

2018-07-05 16:15:26

緩存數(shù)據(jù)cache miss

2021-03-01 18:42:02

緩存LRU算法

2022-05-09 19:59:15

RedisLRU 算法

2017-06-12 10:31:17

Redis源碼學(xué)習(xí)事件驅(qū)動

2020-07-17 21:15:08

Redis內(nèi)存數(shù)據(jù)庫

2024-10-08 10:13:17

2012-12-17 14:54:55

算法緩存Java

2018-11-16 16:35:19

Java源碼編程語言

2020-05-12 10:00:14

緩存算法贈源碼

2022-10-08 08:01:17

Spring源碼服務(wù)
點贊
收藏

51CTO技術(shù)棧公眾號