前言

Redis緩存淘汰策略與Redis鍵的過期刪除策略并不完全相同，前者是在Redis內(nèi)存使用超過一定值的時候（一般這個值可以配置）使用的淘汰策略；而后者是通過定期刪除+惰性刪除兩者結(jié)合的方式淘汰內(nèi)存過期鍵的。
這里參照官方文檔的解釋重新敘述一遍過期刪除策略：當(dāng)某個key被設(shè)置了過期時間之后，客戶端每次對該key的訪問（讀寫）都會事先檢測該key是否過期，如果過期就直接刪除；但有一些鍵只訪問一次，因此需要主動刪除，默認(rèn)情況下redis每秒檢測10次，檢測的對象是所有設(shè)置了過期時間的鍵集合，每次從這個集合中隨機檢測20個鍵查看他們是否過期，如果過期就直接刪除，如果刪除后還有超過25%的集合中的鍵已經(jīng)過期，那么繼續(xù)檢測過期集合中的20個隨機鍵進(jìn)行刪除。這樣可以保證過期鍵最大只占所有設(shè)置了過期時間鍵的25%。

ZERO、Redis內(nèi)存不足的緩存淘汰策略

• noeviction：當(dāng)內(nèi)存使用超過配置的時候會返回錯誤，不會驅(qū)逐任何鍵
• allkeys-lru：加入鍵的時候，如果過限，首先通過LRU算法驅(qū)逐最久沒有使用的鍵
• volatile-lru：加入鍵的時候如果過限，首先從設(shè)置了過期時間的鍵集合中驅(qū)逐最久沒有使用的鍵
• allkeys-random：加入鍵的時候如果過限，從所有key隨機刪除
• volatile-random：加入鍵的時候如果過限，從過期鍵的集合中隨機驅(qū)逐
• volatile-ttl：從配置了過期時間的鍵中驅(qū)逐馬上就要過期的鍵
• volatile-lfu：從所有配置了過期時間的鍵中驅(qū)逐使用頻率最少的鍵
• allkeys-lfu：從所有鍵中驅(qū)逐使用頻率最少的鍵

一、LRU

1、Java中的LRU實現(xiàn)方式

在Java中LRU的實現(xiàn)方式是使用HashMap結(jié)合雙向鏈表，HashMap的值是雙向鏈表的節(jié)點，雙向鏈表的節(jié)點也保存一份key value。

• 新增key value的時候首先在鏈表結(jié)尾添加Node節(jié)點，如果超過LRU設(shè)置的閾值就淘汰隊頭的節(jié)點并刪除掉HashMap中對應(yīng)的節(jié)點。
• 修改key對應(yīng)的值的時候先修改對應(yīng)的Node中的值，然后把Node節(jié)點移動隊尾。
• 訪問key對應(yīng)的值的時候把訪問的Node節(jié)點移動到隊尾即可。

2、Redis中LRU的實現(xiàn)

• Redis維護了一個24位時鐘，可以簡單理解為當(dāng)前系統(tǒng)的時間戳，每隔一定時間會更新這個時鐘。每個key對象內(nèi)部同樣維護了一個24位的時鐘，當(dāng)新增key對象的時候會把系統(tǒng)的時鐘賦值到這個內(nèi)部對象時鐘。比如我現(xiàn)在要進(jìn)行LRU，那么首先拿到當(dāng)前的全局時鐘，然后再找到內(nèi)部時鐘與全局時鐘距離時間最久的（差最大）進(jìn)行淘汰，這里值得注意的是全局時鐘只有24位，按秒為單位來表示才能存儲194天，所以可能會出現(xiàn)key的時鐘大于全局時鐘的情況，如果這種情況出現(xiàn)那么就兩個相加而不是相減來求最久的key。

struct redisServer {
       pid_t pid; 
       char *configfile; 
       //全局時鐘
       unsigned lruclock:LRU_BITS; 
       ...
};

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    /* key對象內(nèi)部時鐘 */
    unsigned lru:LRU_BITS;
    int refcount;
    void *ptr;
} robj;

• Redis中的LRU與常規(guī)的LRU實現(xiàn)并不相同，常規(guī)LRU會準(zhǔn)確的淘汰掉隊頭的元素，但是Redis的LRU并不維護隊列，只是根據(jù)配置的策略要么從所有的key中隨機選擇N個（N可以配置）要么從所有的設(shè)置了過期時間的key中選出N個鍵，然后再從這N個鍵中選出最久沒有使用的一個key進(jìn)行淘汰。

• 下圖是常規(guī)LRU淘汰策略與Redis隨機樣本取一鍵淘汰策略的對比，淺灰色表示已經(jīng)刪除的鍵，深灰色表示沒有被刪除的鍵，綠色表示新加入的鍵，越往上表示鍵加入的時間越久。從圖中可以看出，在redis 3中，設(shè)置樣本數(shù)為10的時候能夠很準(zhǔn)確的淘汰掉最久沒有使用的鍵，與常規(guī)LRU基本持平。

  
  
  image.png

二、LFU

LFU是在Redis4.0后出現(xiàn)的，LRU的最近最少使用實際上并不精確，考慮下面的情況，如果在|處刪除，那么A距離的時間最久，但實際上A的使用頻率要比B頻繁，所以合理的淘汰策略應(yīng)該是淘汰B。LFU就是為應(yīng)對這種情況而生的。

A~~A~~A~~A~~A~~A~~A~~A~~A~~A~~~|
B~~~~~B~~~~~B~~~~~B~~~~~~~~~~~B|

• LFU把原來的key對象的內(nèi)部時鐘的24位分成兩部分，前16位還代表時鐘，后8位代表一個計數(shù)器。16位的情況下如果還按照秒為單位就會導(dǎo)致不夠用，所以一般這里以時鐘為單位。而后8位表示當(dāng)前key對象的訪問頻率，8位只能代表255，但是redis并沒有采用線性上升的方式，而是通過一個復(fù)雜的公式，通過配置兩個參數(shù)來調(diào)整數(shù)據(jù)的遞增速度。
  下圖從左到右表示key的命中次數(shù)，從上到下表示影響因子，在影響因子為100的條件下，經(jīng)過10M次命中才能把后8位值加滿到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        |
# +--------+------------+------------+------------+------------+------------+

  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;
  }

lfu-log-factor 10
lfu-decay-time 1

• 上面說的情況是key一直被命中的情況，如果一個key經(jīng)過幾分鐘沒有被命中，那么后8位的值是需要遞減幾分鐘，具體遞減幾分鐘根據(jù)衰減因子lfu-decay-time來控制

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;
}

lfu-log-factor 10
lfu-decay-time 1

• 上面遞增和衰減都有對應(yīng)參數(shù)配置，那么對于新分配的key呢？如果新分配的key計數(shù)器開始為0，那么很有可能在內(nèi)存不足的時候直接就給淘汰掉了，所以默認(rèn)情況下新分配的key的后8位計數(shù)器的值為5（應(yīng)該可配置），防止因為訪問頻率過低而直接被刪除。
• 低8位我們描述完了，那么高16位的時鐘是用來干嘛的呢？目前我的理解是用來衰減低8位的計數(shù)器的，就是根據(jù)這個時鐘與全局時鐘進(jìn)行比較，如果過了一定時間（做差）就會對計數(shù)器進(jìn)行衰減。
• 最后，redis會對內(nèi)部時鐘最小的key進(jìn)行淘汰（最小表示最不頻繁使用），注意這個過程也是根據(jù)策略隨機選擇鍵