redis記憶體回收與記憶體淘汰政策
- 給新觀衆老爺的開場
- redis記憶體回收
-
- 記憶體回收的方式
-
- 1. 定時删除
- 2. 惰性删除
- 3. 定期删除
- 4. 大key删除
- redis記憶體淘汰政策
-
- redis記憶體淘汰政策有哪些?
- 為什麼redis預設不進行記憶體淘汰
- redis的LRU記憶體淘汰政策
-
- 嚴格的LRU會有什麼問題
- redis中的近似随機LRU
- redis的LFU記憶體淘汰政策
-
- 嚴格的LFU會有什麼問題
- redis中的近似随機LFU
- 往期部落格回顧
給新觀衆老爺的開場
大家好,我是弟弟!
最近讀了一遍 黃健宏大佬的 <<Redis 設計與實作>>,對Redis 3.0版本有了一些認識
該書作者有一版添加了注釋的 redis 3.0源碼
👉官方redis的github傳送門。
👉黃健宏大佬添加了注釋的 redis 3.0源碼傳送門
👉antirez的部落格
網上說Redis代碼寫得很好,為了加深印象和學習redis大佬的代碼寫作藝術,了解工作中使用的redis 指令背後的源碼邏輯,便有了寫部落格記錄學習redis源碼過程的想法。
redis記憶體回收
日常對redis的使用,除了很少的k/v可以不設定過期時間以外,絕大多數k/v都是帶過期時間的。
這樣當key過期之後redis可以将k/v删除,以釋放出記憶體來存儲其他的k/v。
redis作為一個記憶體型資料庫,所有的資料都放在記憶體裡。
記憶體相對硬碟來說還是比較貴的,記憶體資源比較少。
對記憶體的使用能省就省,能回收就回收,提高一些記憶體資源的使用率。
記憶體回收的方式
對過期k/v的回收方式有三種,分别是定時删除,惰性删除,定期删除。
redis采用的是 惰性删除+定期删除 兩種政策。
1. 定時删除
比如一個key的過期時間是1小時,那麼設定一個1小時後執行的定時器來定時删除這個key。
這個方式乍一看上去是記憶體回收效率最高的方式,但
redis因為主要工作線程是一個單線程的緣故,對cpu的計算耗時非常的敏感
。
每個key一個定時器的話,100萬個帶過期時間的k/v就有100萬個定時器,會極其消耗cpu,進而影響redis性能。
該單線程工作的cpu被阻塞幾十毫秒會造成這期間所有待處理的請求延遲增加幾十毫秒以上
對于redis這種記憶體型資料庫來說,請求延時超過10ms以上都算慢的了。
2. 惰性删除
既然定時删除的定時器消耗cpu,那幹脆對有過期時間的key不加定時器了。這樣cpu也沒有額外的負擔,當過期的key再次被通路時,再檢查key的過期時間是否過期,如果過期就删除掉。
但這樣的缺點也比較明顯,redis中會存在大量過期而又沒被删除的key,記憶體回收效率不高。
3. 定期删除
這種方式算是定時删除 與 惰性删除的一種折中方式。
定期删除每隔一段時間處理部分過期key,
通過少量多次的方式 來提高記憶體回收效率,
同時将cpu消耗分散到了每一次操作上,限制每次定期删除執行的最大時間和處理的k/v個數,避免了因單次重度的cpu計算消耗,影響線上正常請求。
-
通過配置檔案中的 hz 字段來指定 serverCron 1秒運作的次數。
再每次serverCron中 會檢查部分具有過期時間戳的key,如果過期,則将key删除。
預設 hz 10,也就是1秒執行10次serverCron
-
在每次事件輪詢前執行的beforeSleep函數中,會檢查部分具有過期時間戳的key,如果過期,則将key删除。
定期删除的政策,一定程度上彌補了惰性删除的 回收效率不高的問題,也一定程度上避免了定時删除的高cpu消耗的問題。通過少量多次的方式,可以在整體上達到與完美記憶體回收差不多的效果。
可以通過調整配置檔案中的 hz 的大小,來調整過期key回收的頻率。
較大的hz值,意味着較高的過期key回收頻率,也意味着增加了較多的cpu消耗。
4. 大key删除
通過惰性删除和定期删除兩種方式,發現需要删除的過期k/v時,
在redis 4.0版本之前,會直接将過期的k/v删除。
在删除較小的k/v時問題不大。
但是線上不可避免的會出現value較大的k/v,
比如一個實時排行榜,可能一個zset中就會包含幾十萬個成員及其分數。
當value較大時,對大塊記憶體的釋放操作,将對redis的主要工作的線程産生不小的阻塞。
key/value的長度預設最大都是512mb,不過通常key都是很小的,value可能會比較大。
是以僅通過 惰性删除+定期删除兩種方式來删除過期k/v 是還不夠的,必須對大key特殊處理。
于是在redis4.0 中加入了 unlink 指令 以及 lazyfree機制
unlink
對需要删除的k/v僅從全局k/v字典中摘除相關的條目,并不立馬删除真正的k/v。
lazy free
若 value的相關屬性 大于
LAZYFREE_THRESHOLD
(預設值 64) 且引用計數為1 , 屬于較大的value,
會将該value添加到 全局的 lazy_free任務隊列,并由專門進行 lazy free 的線程進行記憶體釋放操作。
對較大value的lazy free不會阻塞主線程。
相關屬性如 value 長度/元素個數/占用位元組數 根據不同資料類型取不同字段
當然key是在主線程被直接釋放的,若value較小也是在主線程被直接釋放。
redis記憶體淘汰政策
redis記憶體淘汰政策有哪些?
雖然可以對具有過期時間的key進行記憶體回收,
但是記憶體存儲的了未過期的k/v的大小超過了設定的 maxmemory (最大記憶體使用量),
新的k/v由于沒有可用記憶體而無法寫入,
這種情況也是很有可能發生的。
redis提供了幾種記憶體淘汰政策,以及其組合政策 來應對這種情況。
redis的記憶體淘汰政策如下👇
/* Redis maxmemory strategies. Instead of using just incremental number
* for this defines, we use a set of flags so that testing for certain
* properties common to multiple policies is faster. */
'LRU'
#define MAXMEMORY_FLAG_LRU (1<<0)
'LFU'
#define MAXMEMORY_FLAG_LFU (1<<1)
'對有所key進行淘汰'
#define MAXMEMORY_FLAG_ALLKEYS (1<<2)
'1. 隻對帶過期時間的key使用LRU'
#define MAXMEMORY_VOLATILE_LRU ((0<<8)|MAXMEMORY_FLAG_LRU)
'2. 隻對帶過期時間的key使用LFU'
#define MAXMEMORY_VOLATILE_LFU ((1<<8)|MAXMEMORY_FLAG_LFU)
'3. 根據key到期時間長短進行淘汰'
#define MAXMEMORY_VOLATILE_TTL (2<<8)
'4. 随機淘汰帶過期時間的key'
#define MAXMEMORY_VOLATILE_RANDOM (3<<8)
'5. 對所有key使用LRU'
#define MAXMEMORY_ALLKEYS_LRU ((4<<8)|MAXMEMORY_FLAG_LRU|MAXMEMORY_FLAG_ALLKEYS)
'6. 對所有key使用LFU'
#define MAXMEMORY_ALLKEYS_LFU ((5<<8)|MAXMEMORY_FLAG_LFU|MAXMEMORY_FLAG_ALLKEYS)
'7. 随機淘汰所有key'
#define MAXMEMORY_ALLKEYS_RANDOM ((6<<8)|MAXMEMORY_FLAG_ALLKEYS)
'8. 不淘汰key,此政策當記憶體占滿時,幾乎大部分寫指令都将失敗,隻能讀'
#define MAXMEMORY_NO_EVICTION (7<<8)
'redis的預設記憶體淘汰政策,不淘汰key'
#define CONFIG_DEFAULT_MAXMEMORY_POLICY MAXMEMORY_NO_EVICTION
從上面redis的源碼定義中可以看到,redis的預設記憶體淘汰政策是不進行淘汰。
此時的觀衆朋友們是否會感到疑惑?
為什麼redis預設不進行記憶體淘汰
讓我們将問題簡化一下,來試着分析一下redis預設不進行淘汰的原因。
以下純屬個人分析
假設的場景是這樣👇
- 假設某個redis伺服器執行個體 最多隻能存儲 100萬個 k/v,且已經存了100萬個k/v。
- 由于線上環境會持續寫入新的k/v,假設每秒新增1萬個 k/v 。
-
按照上述的記憶體淘汰政策,在接下來的時間内,
總是有 1萬個 k/v 被淘汰,記憶體被釋放,有1萬個k/v會配置設定到記憶體并寫入。
可能存在的問題👇
-
對于緩存類資料的影響
寫入redis中k/v一般都是從db或者其他二級緩存裡撈出來放到redis裡的,
這樣操作的目的也是希望通過redis緩存來加速資料的通路,
如果由于有新的緩存資料寫入而把之前放到redis中的緩存資料淘汰,
實際上是在拆東牆補西牆,
當被删除的緩存資料再次被通路還需要重新在db或二級緩存撈一遍
這樣,redis對整體資料通路的加速可能沒有提高
反而可能因為頻繁的釋放/配置設定記憶體、重新緩存db資料到記憶體而導緻性能降低
當然記憶體中存在通路頻率低的資料,被淘汰出記憶體是沒有什麼問題,但随着新的k/v不斷的産生,當通路頻率低的資料大部分都被淘汰出去後,就又回到了這個問題。
-
對功能類資料的影響
redis提供了非常易用的一個 set nx 指令,可以用來做分布式鎖。
用來保證在大部分情況下,某些操作隻能在規定時間内執行一次。
如果該類資料因記憶體淘汰而被删除,将對線上的業務産生不可預估的影響。
綜上可以看出,
redis的記憶體淘汰政策僅僅是作為一個記憶體不夠用時的兜底政策而并非最終解決方案。
單機記憶體不夠用時,可以采用分片的方法,擴大redis的整體容量。
但redis仍然提供了額外的記憶體淘汰政策,
可通過修改配置檔案的maxmemory-policy來滿足特殊用途。
redis中的記憶體淘汰政策,在淘汰記憶體時需要兼顧 盡量小的記憶體占用/以及盡量小的cpu資源消耗,故redis中的記憶體淘汰政策都是 近似&随機 的政策。
redis的LRU記憶體淘汰政策
LRU (Least Recently Used) 也就是淘汰最近最少使用的k/v,
也是 最久未使用的k/v的意思。
嚴格的LRU會有什麼問題
一種能嚴格淘汰 最近最少使用的k/v 的實作方式是
-
一個哈希表存儲所有的k/v
一個雙向連結清單按k/v的通路時間順序排序,假設以降序排序
- 當新增一個k/v時,将其插入哈希表後,再加入雙向連結清單的頭部。
- 當一個k/v被通路時,将其移動到雙向連結清單的頭部。
- 當lru需要淘汰掉若幹個k/v時,從連結清單尾部依次淘汰就可以了。
redis中是有全局哈希表的,但少了一個雙向連結清單。
讓我們來分析一下為什麼沒有這個雙向連結清單。
-
首先一份雙向連結清單會占一份空間,假設采用
‘對所有key使用LRU’
#define MAXMEMORY_ALLKEYS_LRU
的政策,那整個執行個體如果有幾百萬k/v,那就得再有幾百萬的連結清單節點。
顯然,很占記憶體。
-
redis中大部分k/v的通路頻率都是很高的,
大部分的k/v頻繁的通路,會讓對應的k/v在雙向連結清單上頻繁的移動,
而我們想要淘汰掉的是通路頻率不高的資料
顯然多出來的這些熱點k/v的頻繁移動操作
不僅消耗cpu,而且對我們的目的沒什麼幫助
redis中的近似随機LRU
實際上redis的LRU淘汰政策,放棄了嚴格的 淘汰最近最少使用的k/v。
預設随機采樣5個k/v再根據其通路時間,淘汰掉 最近最少使用的 那個k/v。
循環直到釋放出 需要的記憶體空間。
redis LRU的部分細節:
- 每個value都是一個redisObject,其中有一個字段 lru,記錄了value的通路時間。
-
這個lru字段隻有24位,精度是秒,194天後24位的lru字段會溢出,
從0開始從新計算。
- redisObject的lru字段,是根據全局的 server.lruclock 字段指派的,這也是個24位變量。若server.hz 等于 10,那系統的lru時鐘每隔100ms會更新一次。
取系統時間是系統調用,會切到核心執行,大量的取實時系統時鐘也是很消耗系統資源的。
redis出于對性能的優化,以秒為精度,緩存了系統的時鐘。
對系統時鐘有特殊需求的,比如對key設定毫秒級過期時間時,會取實時的系統時鐘。
- 采樣的5個k/v,會根據value的lru與全局的 server.lruclock計算出 該value多長時間未被通路,并選出最長時間未被通路的key删除。
如果 value.lru <= server.lruclock ,距離上次被通路的時間是
server.lruclock - value.lru
如果 value.lru > server.lruclock ,距離上次被通路的時間是
(1 << 24 - 1 ) + server.lruclock - value.lru
雖然redis的LRU是近似随機的局部算法,但從整體效果來看,其實跟嚴格的lru效果差不多,對于redis的LRU的精度的提高,可以通過提高采樣值。
antirez在redis.conf的備注中寫到👇
# The default of 5 produces good enough results. 10 Approximates very closely
# true LRU but costs more CPU. 3 is faster but not very accurate.
#
# maxmemory-samples 5
再來一張網上的對比圖檔😈
淺灰色是被回收的對象
灰色是沒有被回收的對象
綠色是被添加的對象
但,lru本身會有什麼問題嗎?
lru如果按照它的淘汰思路,能夠完美的淘汰掉最近最少使用的k/v嗎?
試想這樣一種情況,某一個通路頻率很低的資料,冷不丁的被通路了一下,
此時在lru看來,這個key是一個通路頻率很高的key,但實際不是這樣。
于是,redis在4.0開始加入了 lfu淘汰政策,也就是按最近使用的頻率高低來決定淘汰key。
redis的LFU記憶體淘汰政策
LFU ((Least Frequently Use) 也就是淘汰最近通路頻率最少的k/v,
嚴格的LFU會有什麼問題
嚴格的LFU實作與嚴格的LRU實作,在我看來在redis中落地的話會有相同的問題。
需要花費額外的空間來存儲,各個通路次數下的k/v。
假設這裡的實作方式是
- 一個連結清單按升序記錄通路的次數
- 每個次數的連結清單節點上,挂着另外一個連結清單,用來記錄 相同通路次數的k/v
可能出現的問題
-
redis中大部分資料都是會被頻繁通路的,面對頻繁通路的熱點資料,
不得不消耗額外的cpu資源來維護嚴格的LFU資料結構,
比如一個key被通路,通路次數+1,
需要将key從低通路次數連結清單 移動到高通路次數連結清單。
-
因redis中的熱點key,通路頻率可以分分鐘上萬次,
如果政策是對所有KEY使用LFU進行記憶體淘汰。
花費的額外的記憶體空間也是不小的。
-
k/v通路次數的衰減也是一個耗費cpu資源的問題,
如果k/v通路次數不衰減,那如果業務上突然不使用一個熱點key了,那這個熱點key會一直保持很高的通路次數,并且很難被LFU淘汰。
- 若記憶體長時間被占滿,會陷入循環反複淘汰的尴尬局面
-
而且,redis的LFU記憶體淘汰政策 僅當記憶體不可用時,才會發揮作用,用來淘汰通路頻次低的key。
是以在絕大部分時間,redis花費的額外的空間和cpu 用來維護嚴格的LFU資料結構在平時是沒什麼作用的。
綜上嚴格的LFU在redis中落地的話還是有比較多的問題。
redis中的近似随機LFU
redis中的LFU采用了和LRU類似的 近似随機政策。
同樣也是随機采樣預設5個樣本,計算最近通路次數,并淘汰通路次數最低的那個k/v
循環直到釋放出需要的記憶體空間。
具體redis中的LFU是怎麼回事呢?
antirez在redis.conf中做了詳細的描述,那自然是看大佬的描述是最原汁原味的了👇
# Redis LFU eviction (see maxmemory setting) can be tuned. However it is a good
# idea to start with the default settings and only change them after investigating
# how to improve the performances and how the keys LFU change over time, which
# is possible to inspect via the OBJECT FREQ command.
#
# There are two tunable parameters in the Redis LFU implementation: the
# counter logarithm factor and the counter decay time. It is important to
# understand what the two parameters mean before changing them.
#
# The LFU counter is just 8 bits per key, it's maximum value is 255, so Redis
# uses a probabilistic increment with logarithmic behavior. Given the value
# of the old counter, when a key is accessed, the counter is incremented in
# this way:
#
# 1. A random number R between 0 and 1 is extracted.
# 2. A probability P is calculated as 1/(old_value*lfu_log_factor+1).
# 3. The counter is incremented only if R < P.
#
# The default lfu-log-factor is 10. This is a table of how the frequency
# counter changes with a different number of accesses with different
# logarithmic factors:
#
# +--------+------------+------------+------------+------------+------------+
# | 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 |
# +--------+------------+------------+------------+------------+------------+
#
# NOTE: The above table was obtained by running the following commands:
#
# redis-benchmark -n 1000000 incr foo
# redis-cli object freq foo
#
# NOTE 2: The counter initial value is 5 in order to give new objects a chance
# to accumulate hits.
#
# The counter decay time is the time, in minutes, that must elapse in order
# for the key counter to be divided by two (or decremented if it has a value
# less <= 10).
#
# The default value for the lfu-decay-time is 1. A Special value of 0 means to
# decay the counter every time it happens to be scanned.
#
# lfu-log-factor 10
# lfu-decay-time 1
具體上面在說個啥呢?
當redis啟用LFU記憶體淘汰政策時,redisObject中的lru字段,會被用來記錄通路時間和通路頻率
是的,原本24位的lru,
- 高16位被用來記錄通路時間,精度是分鐘,大概45天後溢出從0開始重新計算
- 後8位被用來記錄 頻率,最大值是255,這個值的增加是按機率來算的。
# 1. A random number R between 0 and 1 is extracted. # 2. A probability P is calculated as 1/(old_value*lfu_log_factor+1). # 3. The counter is incremented only if R < P.
隻有當r <p的時候會+1,也就是說如果通路的次數越大,+1的機率就越高。
具體通路頻率大小 與相關 lfu_log_factor 的關系 大緻如下面這張圖。
# +--------+------------+------------+------------+------------+------------+ # | 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 | # +--------+------------+------------+------------+------------+------------+
lfu_log_factor預設值位10,也就是說 redis不需要知道k/v精确的通路頻率,
隻要大部分情況下知道哪些k/v的通路頻率相對比較小就可以了/
整體的LFU的維護是在 一個k/v被通路的時候,
-
會先根據 lfu-decay-time 值對value的通路頻率進行衰減,
lfu-decay-time預設值為1,意思是每過去1分鐘,通路頻率衰減1
- 然後對通路頻率嘗試+1操作,并更新value的 通路時間。
具體代碼邏輯如下:
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 {
return NULL;
}
}
void updateLFU(robj *val) {
unsigned long counter = LFUDecrAndReturn(val);
counter = LFULogIncr(counter);
val->lru = (LFUGetTimeInMinutes()<<8) | counter;
}
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;
}
#define RAND_MAX 0x7fffffff
#define LFU_INIT_VAL 5
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;
}
unsigned long LFUGetTimeInMinutes(void) {
return (server.unixtime/60) & 65535; //server.unixtime 是一個全局變量會被定時更新,精度是秒
}
往期部落格回顧
- redis伺服器的部分啟動過程
- GET指令背後的源碼邏輯
- redis的基礎資料結構之 sds
- redis的基礎資料結構之 list
- redis的基礎資料結構 之 ziplist
- redis 基礎資料結構之 hash表
- redis不穩定字典的周遊
- redis 基礎資料結構 之 集合
- redis 基礎資料結構 之 有序集合
- redisObject 以及 對抽象的了解
- redis持久化 之 反面面試官