Redis 對過期資料的處理
在 redis 中，對于已經過期的資料，Redis 采用兩種策略來處理這些資料，分別是惰性洗掉和定期洗掉
惰性洗掉
惰性洗掉不會去主動洗掉資料，而是在訪問資料的時候，再檢查當前鍵值是否過期，如果過期則執行洗掉并回傳 null 給客戶端，如果沒有過期則回傳正常資訊給客戶端，
它的優點是簡單，不需要對過期的資料欄位外的處理，只有在每次訪問的時候才會檢查鍵值是否過期，缺點是洗掉過期鍵不及時，造成了一定的空間浪費，
原始碼
robj *lookupKeyReadWithFlags(redisDb *db, robj *key, int flags) {
robj *val;
if (expireIfNeeded(db,key) == 1) {
/* Key expired. If we are in the context of a master, expireIfNeeded()
* returns 0 only when the key does not exist at all, so it's safe
* to return NULL ASAP. */
if (server.masterhost == NULL) {
server.stat_keyspace_misses++;
notifyKeyspaceEvent(NOTIFY_KEY_MISS, "keymiss", key, db->id);
return NULL;
}
/* However if we are in the context of a slave, expireIfNeeded() will
* not really try to expire the key, it only returns information
* about the "logical" status of the key: key expiring is up to the
* master in order to have a consistent view of master's data set.
*
* However, if the command caller is not the master, and as additional
* safety measure, the command invoked is a read-only command, we can
* safely return NULL here, and provide a more consistent behavior
* to clients accessign expired values in a read-only fashion, that
* will say the key as non existing.
*
* Notably this covers GETs when slaves are used to scale reads. */
if (server.current_client &&
server.current_client != server.master &&
server.current_client->cmd &&
server.current_client->cmd->flags & CMD_READONLY)
{
server.stat_keyspace_misses++;
notifyKeyspaceEvent(NOTIFY_KEY_MISS, "keymiss", key, db->id);
return NULL;
}
}
val = lookupKey(db,key,flags);
if (val == NULL) {
server.stat_keyspace_misses++;
notifyKeyspaceEvent(NOTIFY_KEY_MISS, "keymiss", key, db->id);
}
else
server.stat_keyspace_hits++;
return val;
}
定期洗掉
定期洗掉：Redis會周期性的隨機測驗一批設定了過期時間的key并進行處理，測驗到的已過期的key將被洗掉，
具體的演算法如下：
-
Redis配置項hz定義了serverCron任務的執行周期，默認為10，代表了每秒執行10次；
-
每次過期key清理的時間不超過CPU時間的25%,比如hz默認為10,則一次清理時間最大為25ms;
-
清理時依次遍歷所有的db;
-
從db中隨機取20個key,判斷是否過期，若過期，則逐出;
-
若有5個以上key過期，則重復步驟4,否則遍歷下一個db;
-
在清理程序中，若達到了25%CPU時間，退出清理程序;
雖然redis的確是不斷的洗掉一些過期資料，但是很多沒有設定過期時間的資料也會越來越多，那么redis記憶體不夠用的時候是怎么處理的呢？這里我們就會談到淘汰策略
Redis記憶體淘汰策略
當redis的記憶體超過最大允許的記憶體之后，Redis會觸發記憶體淘汰策略，洗掉一些不常用的資料，以保證redis服務器的正常運行
在redis 4.0以前，redis的記憶體淘汰策略有以下6種
- noeviction：當記憶體使用超過配置的時候會回傳錯誤，不會驅逐任何鍵
- allkeys-lru：加入鍵的時候，如果過限，首先通過LRU演算法驅逐最久沒有使用的鍵
- volatile-lru：加入鍵的時候如果過限，首先從設定了過期時間的鍵集合中驅逐最久沒有使用的鍵
- allkeys-random：加入鍵的時候如果過限，從所有key隨機洗掉
- volatile-random：加入鍵的時候如果過限，從過期鍵的集合中隨機驅逐
- volatile-ttl：從配置了過期時間的鍵中驅逐馬上就要過期的鍵
在redis 4.0以后，又增加了以下兩種 - volatile-lfu：從所有配置了過期時間的鍵中驅逐使用頻率最少的鍵
- allkeys-lfu：從所有鍵中驅逐使用頻率最少的鍵
記憶體淘汰策略可以通過組態檔來修改，redis.conf對應的配置項是maxmemory-policy 修改對應的值就行，默認是noeviction
LRU（the least recently used 最近最少使用）演算法
如果一個資料在最近沒有被訪問到，那么在未來被訪問的可能性也很小，因此當空間滿的時候，最久沒有被訪問的資料最先被置換(淘汰)
LRU演算法通常通過雙向鏈表來實作，添加元素的時候，直接插入表頭，訪問元素的時候，先判斷元素是否在鏈表中存在，如果存在就把該元素移動至表頭，所以鏈表的元素排列順序就是元素最近被訪問的順序，當記憶體達到設定閾值時，LRU隊尾的元素由于被訪問的時間線較遠，會優先踢出
但是在redis中，并沒有嚴格實行LRU演算法，之所以這樣是因為LRU需要消耗大量的額外記憶體，需要對現有的資料結構進行較大的改造，近似LRU演算法采用在現有資料結構的基礎上使用隨機采樣法來淘汰元素，能達到和LRU演算法非常近似的效果，Redis的 LRU演算法給每個key增加了一個額外的長度為24bit的小欄位，記錄最后一次被訪問的時間戳，
redis通過maxmemory-samples 5配置，對key進行采樣淘汰，同時在Redis3.0以后添加了淘汰池進一步提升了淘汰準確度，
但是LRU演算法是存在一定的問題
例如，這表示隨著時間的推移，四個不同的鍵訪問，每個“?”字符為一秒鐘，而“ |” 最后一行是當前時刻，
~~ B ~~ B ~~ B ~~ B ~~ B ~~ B ~~ B ~~ B ~~ B ~~ B ~~ B ~~ B?|
~~~~~~~~~~ C ~~~~~~~~ C ~~~~~~~~~ C ~~~~~~ |
~~~~~ D ~~~~~~~~~ D ~~~~~~~ D ~~~~~~~~ D |
在上圖中，按照LRU機制洗掉的話洗掉的順序應該是C->A->B->D 其實這并不是我們想要的，因為B被訪問的頻率是最高的，而D被訪問的頻率比較低，所以我們更想讓B保留，把D洗掉，所以我們接下來看另一種策略 LFU
**LFU（leastFrequently used 最不經常使用）**
如果一個資料在最近一段時間內很少被訪問到，那么可以認為在將來他被訪問到的概率也很小，所以，當空間滿時，最小頻率訪問的資料最先被淘汰
Redis使用redisObject中的24bit lru欄位來存盤lfu欄位， 這24bit被分為兩部分：
1:高16位用來記錄訪問時間(單位為分鐘)
2:低8位用來記錄訪問頻率，簡稱counter
16 bits 8 bits
+----------------+--------+
Last decr time | LOG_C |
但是counter 8bit很容易就溢位了，技巧是用一個邏輯計數器，給予概率的對數計數器，而不是一個普通的遞增計數器
```
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;
}
```
對應的概率分布計算公式為
```
1.0/((counter - LFU_INIT_VAL)*server.lfu_log_factor+1);
```
其中LFU_INIT_VAL為5，其實簡單說就是，越大的數，遞增的概率越低
嚴格按照LFU演算法，時間越久的key，counter越有可能越大，被剔除的可能性就越小，counter只增長不衰減就無法區分熱點key，為了解決這個問題，redis提供了衰減因子server.lfu_decay_time,其單位為分鐘，計算方法也很簡單，如果一個key長時間沒有訪問那么他的計數器counter就要減少，減少的值由衰減因子來控制
> 關注我的技術公眾號，每周都有優質技術文章推送，
微信掃一掃下方二維碼即可關注：
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/179060.html
標籤：其他
下一篇：pk Round-1