前言

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

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

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

一、LRU

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

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

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

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

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

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

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

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

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

  
  
  image.png

二、LFU

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

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

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

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

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

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