微信公眾號：moon聊技術(shù)

本文約5300字，完整閱讀大概會花費你13分鐘左右的時間

[如果你覺得文章對你有幫助，歡迎關(guān)注，點贊，轉(zhuǎn)發(fā)]

簡介

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

• redis會怎么做？
• 我們可以怎么做？

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

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

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

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

• 通過命令修改
  • redis支持運行時通過命令動態(tài)修改內(nèi)存大小

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

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

內(nèi)存淘汰策略

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

• 1. noeviction：直接返回錯誤，不淘汰任何已經(jīng)存在的redis鍵
• 2. allkeys-lru：所有的鍵使用lru算法進行淘汰
• 3. volatile-lru：有過期時間的使用lru算法進行淘汰
• 4. allkeys-random：隨機刪除redis鍵
• 5. volatile-random：隨機刪除有過期時間的redis鍵
• 6. volatile-ttl：刪除快過期的redis鍵
• 7. volatile-lfu：根據(jù)lfu算法從有過期時間的鍵刪除
• 8. allkeys-lfu：根據(jù)lfu算法從所有鍵刪除

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

lru的最佳實踐？

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

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

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

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

image

hash表用來查詢在鏈表中的數(shù)據(jù)位置，鏈表負責數(shù)據(jù)的插入
當新數(shù)據(jù)插入到鏈表頭部時有兩種情況；

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

image.png

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

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

lfu的最佳實踐？

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

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

如圖：

image.png

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

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

這樣當查找，插入時效率都為O(1)

redis TTL 是怎么實現(xiàn)的？

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

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

image

image

TTL 設(shè)置過期時間

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

• expire 按照相對時間且以秒為單位的過期策略
• expireat 按照絕對時間且以秒為單位的過期策略
• pexpire 按照相對時間且以毫秒為單位的過期策略
• pexpireat 按照絕對時間且以毫秒為單位的過期策略

{"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è)置過期時間的實現(xiàn)函數(shù)來看，相對時間的策略會有一個當前時間作為基準時間，絕對時間的策略會以0作為一個基準時間。

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

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

/* 
*
* 這個函數(shù)是 EXPIRE 、 PEXPIRE 、 EXPIREAT 和 PEXPIREAT 命令的底層實現(xiàn)函數(shù)。
*
* 命令的第二個參數(shù)可能是絕對值，也可能是相對值。
* 當執(zhí)行 *AT 命令時， basetime 為 0 ，在其他情況下，它保存的就是當前的絕對時間。
*
* unit 用于指定 argv[2] （傳入過期時間）的格式，
* 它可以是 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;

   // 如果傳入的過期時間是以秒為單位的，那么將它轉(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ù)時，或者服務器為附屬節(jié)點時，
    * 即使 EXPIRE 的 TTL 為負數(shù)，或者 EXPIREAT 提供的時間戳已經(jīng)過期，
    * 服務器也不會主動刪除這個鍵，而是等待主節(jié)點發(fā)來顯式的 DEL 命令。
    *
    * 程序會繼續(xù)將（一個可能已經(jīng)過期的 TTL）設(shè)置為鍵的過期時間，
    * 并且等待主節(jié)點發(fā)來 DEL 命令。
    */
   if (when <= mstime() && !server.loading && !server.masterhost) {

       // when 提供的時間已經(jīng)過期，服務器為主節(jié)點，并且沒在載入數(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è)置鍵的過期時間
       // 如果服務器為附屬節(jié)點，或者服務器正在載入，
       // 那么這個 when 有可能已經(jīng)過期的
       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ù)主要是對db->expires中的key對應的dictEntry設(shè)置過期時間。

/*
* 將鍵 key 的過期時間設(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ù)鍵取出鍵的過期時間
   de = dictReplaceRaw(db->expires,dictGetKey(kde));

   // 設(shè)置鍵的過期時間
   // 這里是直接使用整數(shù)值來保存過期時間，不是用 INT 編碼的 String 對象
   dictSetSignedIntegerVal(de,when);
}

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

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

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

巨人的肩膀

TTL實現(xiàn)原理 http://www.itdecent.cn/p/53083f5f2ddc
lru https://zhuanlan.zhihu.com/p/265597517
lfu https://tech.ipalfish.com/blog/2020/03/25/lfu/![image.png](https://upload-