[[387389]]

本文轉(zhuǎn)載自微信公眾號(hào)「moon聊技術(shù)」，作者moon聊技術(shù)。轉(zhuǎn)載本文請(qǐng)聯(lián)系moon聊技術(shù)公眾號(hào)。

簡(jiǎn)介

我們知道redis是一個(gè)非常常用的內(nèi)存型數(shù)據(jù)庫(kù)，數(shù)據(jù)從內(nèi)存中讀取是它非常高效的原因之一，那么但是如果有一天，「redis分配的內(nèi)存滿了怎么辦」?遇到這個(gè)面試題不要慌，這種問(wèn)題我們分為兩角度回答就可以：

• 「redis會(huì)怎么做」?
• 「我們可以怎么做」?

增加redis可用內(nèi)存

這種方法很暴力，也很好用，我們直接通過(guò)增加redis的可用內(nèi)存就可以了， 有兩種方式

「通過(guò)配置文件配置」

//設(shè)置redis最大占用內(nèi)存大小為1000M   
maxmemory 1000mb  

通過(guò)在redis安裝目錄下面的redis.conf配置文件中添加以下配置設(shè)置內(nèi)存大小

「通過(guò)命令修改」

//設(shè)置redis最大占用內(nèi)存大小為1000M   
127.0.0.1:6379> config set maxmemory 1000mb   

• redis支持運(yùn)行時(shí)通過(guò)命令動(dòng)態(tài)修改內(nèi)存大小

這種方法是立竿見影的，reids 內(nèi)存總歸受限于機(jī)器的內(nèi)存，也不能無(wú)限制的增長(zhǎng)，那么如果沒有辦法再增加 redis 的可用內(nèi)存怎么辦呢?

內(nèi)存淘汰策略

實(shí)際上Redis定義了「8種內(nèi)存淘汰策略」用來(lái)處理redis內(nèi)存滿的情況：

1.noeviction：直接返回錯(cuò)誤，不淘汰任何已經(jīng)存在的redis鍵

2.allkeys-lru：所有的鍵使用lru算法進(jìn)行淘汰

3.volatile-lru：有過(guò)期時(shí)間的使用lru算法進(jìn)行淘汰

4.allkeys-random：隨機(jī)刪除redis鍵

5.volatile-random：隨機(jī)刪除有過(guò)期時(shí)間的redis鍵

6.volatile-ttl：刪除快過(guò)期的redis鍵

7.volatile-lfu：根據(jù)lfu算法從有過(guò)期時(shí)間的鍵刪除

8.allkeys-lfu：根據(jù)lfu算法從所有鍵刪除

這些內(nèi)存淘汰策略都很好理解，我們著重講解一下lru，lfu，ttl是怎么去實(shí)現(xiàn)的

lru的最佳實(shí)踐?

lru是Least Recently Used的縮寫,也就是「最近很少使用」,也可以理解成最久沒有使用。最近剛剛使用過(guò)的，后面接著會(huì)用到的概率也就越大。由于內(nèi)存是非常金貴的，導(dǎo)致我們可以存儲(chǔ)在緩存當(dāng)中的數(shù)據(jù)是有限的。比如說(shuō)我們固定只能存儲(chǔ)1w條，當(dāng)內(nèi)存滿了之后，緩存每插入一條新數(shù)據(jù)，都要拋棄一條最長(zhǎng)沒有使用的舊數(shù)據(jù)。我們把上面的內(nèi)容整理一下，可以得到幾點(diǎn)要求：

• 「1.保證其的讀寫效率，比如讀寫的復(fù)雜度都是O(1)」
• 「2.當(dāng)一條數(shù)據(jù)被讀取，將它最近使用的時(shí)間更新」
• 「3.當(dāng)插入一條新數(shù)據(jù)的時(shí)候，刪除最久沒有使用過(guò)的數(shù)據(jù)」

所以我們要盡可能的保證查詢效率很高，插入效率很高，我們知道如果只考慮查詢效率，那么hash表可能就是最優(yōu)的選擇，如果只考慮插入效率，那么鏈表必定有它的一席之地。

但是這兩種數(shù)據(jù)結(jié)構(gòu)單獨(dú)使用，都有它的弊端，那么說(shuō)，有沒有一種數(shù)據(jù)結(jié)構(gòu)，既能夠保證查詢效率，又能夠保證插入效率呢?于是 hash+鏈表這種結(jié)構(gòu)出現(xiàn)了

hash表用來(lái)查詢?cè)阪湵碇械臄?shù)據(jù)位置，鏈表負(fù)責(zé)數(shù)據(jù)的插入 當(dāng)新數(shù)據(jù)插入到鏈表頭部時(shí)有兩種情況;

• 1.當(dāng)鏈表滿的時(shí)候，將鏈表尾部的數(shù)據(jù)丟棄。
  • 這個(gè)比較簡(jiǎn)單，直接將鏈表尾部指針抹去，并且清除對(duì)應(yīng)hash中的信息就好了
• 2.每當(dāng)緩存命中(即緩存數(shù)據(jù)被訪問(wèn))，則將數(shù)據(jù)移到鏈表頭部;
  • 這種情況我們發(fā)現(xiàn)，如果命中到鏈表中間節(jié)點(diǎn)，我們需要做的是
  • 1).將該節(jié)點(diǎn)移到頭節(jié)點(diǎn)
  • 2).「將該節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，設(shè)置為該節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)」，這里就會(huì)有一個(gè)問(wèn)題，我們無(wú)法找到該節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)，因?yàn)槭菃蜗蜴湵?，所以，新的模型產(chǎn)生了。

這時(shí)雙向鏈表的作用也提現(xiàn)出來(lái)了。能直接定位到父節(jié)點(diǎn)。這效率就很高了。而且由于雙向鏈表有尾指針，所以剔除最后的尾節(jié)點(diǎn)也十分方便，快捷

所以最終的解決方案就是采用「哈希表+雙向鏈表」的結(jié)構(gòu)

lfu的最佳實(shí)踐?

LFU:Least Frequently Used，最不經(jīng)常使用策略,在一段時(shí)間內(nèi),數(shù)據(jù)被「使用頻次最少」的,優(yōu)先被淘汰。最少使用(LFU)是一種用于管理計(jì)算機(jī)內(nèi)存的緩存算法。主要是記錄和追蹤內(nèi)存塊的使用次數(shù),當(dāng)緩存已滿并且需要更多空間時(shí)，系統(tǒng)將以最低內(nèi)存塊使用頻率清除內(nèi)存.采用LFU算法的最簡(jiǎn)單方法是為每個(gè)加載到緩存的塊分配一個(gè)計(jì)數(shù)器。每次引用該塊時(shí)，計(jì)數(shù)器將增加一。當(dāng)緩存達(dá)到容量并有一個(gè)新的內(nèi)存塊等待插入時(shí)，系統(tǒng)將搜索計(jì)數(shù)器最低的塊并將其從緩存中刪除。

這里我們提出一種達(dá)到 O(1) 時(shí)間復(fù)雜度的 LFU 實(shí)現(xiàn)方案，它支持的操作包括插入、訪問(wèn)以及刪除

如圖：

由兩個(gè)雙向鏈表+哈希表組成，上方的雙向鏈表用來(lái)計(jì)數(shù)，下方的雙向鏈表用來(lái)記錄存儲(chǔ)的數(shù)據(jù)，該鏈表的頭節(jié)點(diǎn)存儲(chǔ)了數(shù)字，哈希表的value對(duì)象記錄下方雙向鏈表的數(shù)據(jù) 我們這里按照插入的流程走一遍:

• 將需要存儲(chǔ)的數(shù)據(jù)插入
• 在hash表中「存在」，找到對(duì)應(yīng)的下方雙向鏈表，將該節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)和該節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)相連(這里可能只有自己，直接移除就好)，然后判斷自己所在上方雙向鏈表的計(jì)數(shù)是否比當(dāng)前計(jì)數(shù)大1
  • 「如果是」，則將自己移到該上方雙向鏈表，并且「判斷該雙向鏈表下是否還有元素」，如果沒有，則要?jiǎng)h除該節(jié)點(diǎn)
  • 「如果不是或者該上方雙向列表無(wú)下個(gè)節(jié)點(diǎn)」則新加節(jié)點(diǎn)，將計(jì)數(shù)設(shè)為當(dāng)前計(jì)數(shù)+1
• 在hash表「不存在」，將數(shù)據(jù)存入hash表，將數(shù)據(jù)與雙向鏈表的頭節(jié)點(diǎn)相連(這里有可能鏈表未初始化)

這樣當(dāng)查找，插入時(shí)效率都為O(1)

redis TTL 是怎么實(shí)現(xiàn)的?

TTL存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)

redis針對(duì)TTL時(shí)間有專門的dict進(jìn)行存儲(chǔ)，就是redisDb當(dāng)中的dict *expires字段，dict顧名思義就是一個(gè)hashtable，key為對(duì)應(yīng)的rediskey，value為對(duì)應(yīng)的TTL時(shí)間。?dict的數(shù)據(jù)結(jié)構(gòu)中含有2個(gè)dictht對(duì)象，主要是為了解決hash沖突過(guò)程中重新hash數(shù)據(jù)使用。

TTL 設(shè)置過(guò)期時(shí)間

TTL設(shè)置key過(guò)期時(shí)間的方法主要是下面4個(gè)：

• expire 按照相對(duì)時(shí)間且以秒為單位的過(guò)期策略
• expireat 按照絕對(duì)時(shí)間且以秒為單位的過(guò)期策略
• pexpire 按照相對(duì)時(shí)間且以毫秒為單位的過(guò)期策略
• pexpireat 按照絕對(duì)時(shí)間且以毫秒為單位的過(guò)期策略

{"expire",expireCommand,3,"w",0,NULL,1,1,1,0,0}, 
{"expireat",expireatCommand,3,"w",0,NULL,1,1,1,0,0}, 
{"pexpire",pexpireCommand,3,"w",0,NULL,1,1,1,0,0}, 
{"pexpireat",pexpireatCommand,3,"w",0,NULL,1,1,1,0,0}, 

expire expireat pexpire pexpireat

從實(shí)際設(shè)置過(guò)期時(shí)間的實(shí)現(xiàn)函數(shù)來(lái)看，相對(duì)時(shí)間的策略會(huì)有一個(gè)當(dāng)前時(shí)間作為基準(zhǔn)時(shí)間，絕對(duì)時(shí)間的策略會(huì)「以0作為一個(gè)基準(zhǔn)時(shí)間」。

void expireCommand(redisClient *c) { 
    expireGenericCommand(c,mstime(),UNIT_SECONDS); 
} 
 
void expireatCommand(redisClient *c) { 
    expireGenericCommand(c,0,UNIT_SECONDS); 
} 
 
void pexpireCommand(redisClient *c) { 
    expireGenericCommand(c,mstime(),UNIT_MILLISECONDS); 
} 
 
void pexpireatCommand(redisClient *c) { 
    expireGenericCommand(c,0,UNIT_MILLISECONDS); 
} 

整個(gè)過(guò)期時(shí)間最后都會(huì)換算到絕對(duì)時(shí)間進(jìn)行存儲(chǔ)，通過(guò)公式基準(zhǔn)時(shí)間+過(guò)期時(shí)間來(lái)進(jìn)行計(jì)算。?對(duì)于相對(duì)時(shí)間而言基準(zhǔn)時(shí)間就是當(dāng)前時(shí)間，對(duì)于絕對(duì)時(shí)間而言相對(duì)時(shí)間就是0。?中途考慮設(shè)置的過(guò)期時(shí)間是否已經(jīng)過(guò)期，如果已經(jīng)過(guò)期那么在master就會(huì)刪除該數(shù)據(jù)并同步刪除動(dòng)作到slave。?正常的設(shè)置過(guò)期時(shí)間是通過(guò)setExpire方法保存到 dict *expires對(duì)象當(dāng)中。

/*  
* 
* 這個(gè)函數(shù)是 EXPIRE 、 PEXPIRE 、 EXPIREAT 和 PEXPIREAT 命令的底層實(shí)現(xiàn)函數(shù)。 
* 
* 命令的第二個(gè)參數(shù)可能是絕對(duì)值，也可能是相對(duì)值。 
* 當(dāng)執(zhí)行 *AT 命令時(shí)， basetime 為 0 ，在其他情況下，它保存的就是當(dāng)前的絕對(duì)時(shí)間。 
* 
* unit 用于指定 argv[2] （傳入過(guò)期時(shí)間）的格式， 
* 它可以是 UNIT_SECONDS 或 UNIT_MILLISECONDS ， 
* basetime 參數(shù)則總是毫秒格式的。 
*/ 
void expireGenericCommand(redisClient *c, long long basetime, int unit) { 
   robj *key = c->argv[1], *param = c->argv[2]; 
   long long when; /* unix time in milliseconds when the key will expire. */ 
 
   // 取出 when 參數(shù) 
   if (getLongLongFromObjectOrReply(c, param, &when, NULL) != REDIS_OK) 
       return; 
 
   // 如果傳入的過(guò)期時(shí)間是以秒為單位的，那么將它轉(zhuǎn)換為毫秒 
   if (unit == UNIT_SECONDS) when *= 1000; 
   when += basetime; 
 
   /* No key, return zero. */ 
   // 取出鍵 
   if (lookupKeyRead(c->db,key) == NULL) { 
       addReply(c,shared.czero); 
       return; 
   } 
 
   /*  
    * 在載入數(shù)據(jù)時(shí)，或者服務(wù)器為附屬節(jié)點(diǎn)時(shí)， 
    * 即使 EXPIRE 的 TTL 為負(fù)數(shù)，或者 EXPIREAT 提供的時(shí)間戳已經(jīng)過(guò)期， 
    * 服務(wù)器也不會(huì)主動(dòng)刪除這個(gè)鍵，而是等待主節(jié)點(diǎn)發(fā)來(lái)顯式的 DEL 命令。 
    * 
    * 程序會(huì)繼續(xù)將（一個(gè)可能已經(jīng)過(guò)期的 TTL）設(shè)置為鍵的過(guò)期時(shí)間， 
    * 并且等待主節(jié)點(diǎn)發(fā)來(lái) DEL 命令。 
    */ 
   if (when <= mstime() && !server.loading && !server.masterhost) { 
 
       // when 提供的時(shí)間已經(jīng)過(guò)期，服務(wù)器為主節(jié)點(diǎn)，并且沒在載入數(shù)據(jù) 
 
       robj *aux; 
 
       redisAssertWithInfo(c,key,dbDelete(c->db,key)); 
       server.dirty++; 
 
       /* Replicate/AOF this as an explicit DEL. */ 
       // 傳播 DEL 命令 
       aux = createStringObject("DEL",3); 
 
       rewriteClientCommandVector(c,2,aux,key); 
       decrRefCount(aux); 
 
       signalModifiedKey(c->db,key); 
       notifyKeyspaceEvent(REDIS_NOTIFY_GENERIC,"del",key,c->db->id); 
 
       addReply(c, shared.cone); 
 
       return; 
   } else { 
 
       // 設(shè)置鍵的過(guò)期時(shí)間 
       // 如果服務(wù)器為附屬節(jié)點(diǎn)，或者服務(wù)器正在載入， 
       // 那么這個(gè) when 有可能已經(jīng)過(guò)期的 
       setExpire(c->db,key,when); 
 
       addReply(c,shared.cone); 
 
       signalModifiedKey(c->db,key); 
       notifyKeyspaceEvent(REDIS_NOTIFY_GENERIC,"expire",key,c->db->id); 
 
       server.dirty++; 
 
       return; 
   } 
} 
 
 setExpire函數(shù)主要是對(duì)db->expires中的key對(duì)應(yīng)的dictEntry設(shè)置過(guò)期時(shí)間。 
 
/* 
* 將鍵 key 的過(guò)期時(shí)間設(shè)為 when 
*/ 
void setExpire(redisDb *db, robj *key, long long when) { 
 
   dictEntry *kde, *de; 
 
   /* Reuse the sds from the main dict in the expire dict */ 
   // 取出鍵 
   kde = dictFind(db->dict,key->ptr); 
 
   redisAssertWithInfo(NULL,key,kde != NULL); 
 
   // 根據(jù)鍵取出鍵的過(guò)期時(shí)間 
   de = dictReplaceRaw(db->expires,dictGetKey(kde)); 
 
   // 設(shè)置鍵的過(guò)期時(shí)間 
   // 這里是直接使用整數(shù)值來(lái)保存過(guò)期時(shí)間，不是用 INT 編碼的 String 對(duì)象 
   dictSetSignedIntegerVal(de,when); 
} 

redis什么時(shí)候執(zhí)行淘汰策略?

在redis種有三種刪除的操作此策略

• 定時(shí)刪除：對(duì)于設(shè)有過(guò)期時(shí)間的key，時(shí)間到了，定時(shí)器任務(wù)立即執(zhí)行刪除
  • 因?yàn)橐S護(hù)一個(gè)定時(shí)器，所以就會(huì)占用cpu資源，尤其是有過(guò)期時(shí)間的redis鍵越來(lái)越多損耗的性能就會(huì)線性上升
• 惰性刪除：每次只有再訪問(wèn)key的時(shí)候，才會(huì)檢查key的過(guò)期時(shí)間，若是已經(jīng)過(guò)期了就執(zhí)行刪除。
  • 這種情況只有在訪問(wèn)的時(shí)候才會(huì)刪除，所以有可能有些過(guò)期的redis鍵一直不會(huì)被訪問(wèn)，就會(huì)一直占用redis內(nèi)存
• 定期刪除：每隔一段時(shí)間，就會(huì)檢查刪除掉過(guò)期的key。
  • 這種方案相當(dāng)于上述兩種方案的折中，通過(guò)最合理控制刪除的時(shí)間間隔來(lái)刪除key，減少對(duì)cpu的資源的占用消耗，使刪除操作合理化。

巨人的肩膀

https://www.jianshu.com/p/53083f5f2ddc https://zhuanlan.zhihu.com/p/265597517