Redis內存滿了怎么辦？讓你玩懂8種內存淘汰策略
本文轉載自微信公眾號「moon聊技術」，作者moon聊技術。轉載本文請聯系moon聊技術公眾號。
簡介
我們知道redis是一個非常常用的內存型數據庫，數據從內存中讀取是它非常高效的原因之一，那么但是如果有一天，「redis分配的內存滿了怎么辦」?遇到這個面試題不要慌，這種問題我們分為兩角度回答就可以：
- 「redis會怎么做」?
- 「我們可以怎么做」?
增加redis可用內存
這種方法很暴力，也很好用，我們直接通過增加redis的可用內存就可以了， 有兩種方式
「通過配置文件配置」
- //設置redis最大占用內存大小為1000M
- maxmemory 1000mb
通過在redis安裝目錄下面的redis.conf配置文件中添加以下配置設置內存大小
「通過命令修改」
- //設置redis最大占用內存大小為1000M
- 127.0.0.1:6379> config set maxmemory 1000mb
- redis支持運行時通過命令動態修改內存大小
這種方法是立竿見影的，reids 內存總歸受限于機器的內存，也不能無限制的增長，那么如果沒有辦法再增加 redis 的可用內存怎么辦呢?
內存淘汰策略
實際上Redis定義了「8種內存淘汰策略」用來處理redis內存滿的情況：
1.noeviction：直接返回錯誤，不淘汰任何已經存在的redis鍵
2.allkeys-lru：所有的鍵使用lru算法進行淘汰
3.volatile-lru：有過期時間的使用lru算法進行淘汰
4.allkeys-random：隨機刪除redis鍵
5.volatile-random：隨機刪除有過期時間的redis鍵
6.volatile-ttl：刪除快過期的redis鍵
7.volatile-lfu：根據lfu算法從有過期時間的鍵刪除
8.allkeys-lfu：根據lfu算法從所有鍵刪除
這些內存淘汰策略都很好理解，我們著重講解一下lru，lfu，ttl是怎么去實現的
lru的最佳實踐?
lru是Least Recently Used的縮寫,也就是「最近很少使用」,也可以理解成最久沒有使用。最近剛剛使用過的，后面接著會用到的概率也就越大。由于內存是非常金貴的，導致我們可以存儲在緩存當中的數據是有限的。比如說我們固定只能存儲1w條，當內存滿了之后，緩存每插入一條新數據，都要拋棄一條最長沒有使用的舊數據。我們把上面的內容整理一下，可以得到幾點要求：
- 「1.保證其的讀寫效率，比如讀寫的復雜度都是O(1)」
- 「2.當一條數據被讀取，將它最近使用的時間更新」
- 「3.當插入一條新數據的時候，刪除最久沒有使用過的數據」
所以我們要盡可能的保證查詢效率很高，插入效率很高，我們知道如果只考慮查詢效率，那么hash表可能就是最優的選擇，如果只考慮插入效率，那么鏈表必定有它的一席之地。
但是這兩種數據結構單獨使用，都有它的弊端，那么說，有沒有一種數據結構，既能夠保證查詢效率，又能夠保證插入效率呢?于是 hash+鏈表這種結構出現了
hash表用來查詢在鏈表中的數據位置，鏈表負責數據的插入 當新數據插入到鏈表頭部時有兩種情況;
- 1.當鏈表滿的時候，將鏈表尾部的數據丟棄。
- 這個比較簡單，直接將鏈表尾部指針抹去，并且清除對應hash中的信息就好了
- 2.每當緩存命中(即緩存數據被訪問)，則將數據移到鏈表頭部;
- 這種情況我們發現，如果命中到鏈表中間節點，我們需要做的是
- 1).將該節點移到頭節點
- 2).「將該節點的上一個節點的下一個節點，設置為該節點的下一個節點」，這里就會有一個問題，我們無法找到該節點的上一個節點，因為是單向鏈表，所以，新的模型產生了。
這時雙向鏈表的作用也提現出來了。能直接定位到父節點。這效率就很高了。而且由于雙向鏈表有尾指針，所以剔除最后的尾節點也十分方便，快捷
所以最終的解決方案就是采用「哈希表+雙向鏈表」的結構
lfu的最佳實踐?
LFU:Least Frequently Used，最不經常使用策略,在一段時間內,數據被「使用頻次最少」的,優先被淘汰。最少使用(LFU)是一種用于管理計算機內存的緩存算法。主要是記錄和追蹤內存塊的使用次數,當緩存已滿并且需要更多空間時，系統將以最低內存塊使用頻率清除內存.采用LFU算法的最簡單方法是為每個加載到緩存的塊分配一個計數器。每次引用該塊時，計數器將增加一。當緩存達到容量并有一個新的內存塊等待插入時，系統將搜索計數器最低的塊并將其從緩存中刪除。
這里我們提出一種達到 O(1) 時間復雜度的 LFU 實現方案，它支持的操作包括插入、訪問以及刪除
如圖：
由兩個雙向鏈表+哈希表組成，上方的雙向鏈表用來計數，下方的雙向鏈表用來記錄存儲的數據，該鏈表的頭節點存儲了數字，哈希表的value對象記錄下方雙向鏈表的數據 我們這里按照插入的流程走一遍:
- 將需要存儲的數據插入
- 在hash表中「存在」，找到對應的下方雙向鏈表，將該節點的上一個節點和該節點的下一個節點相連(這里可能只有自己，直接移除就好)，然后判斷自己所在上方雙向鏈表的計數是否比當前計數大1
- 「如果是」，則將自己移到該上方雙向鏈表，并且「判斷該雙向鏈表下是否還有元素」，如果沒有，則要刪除該節點
- 「如果不是或者該上方雙向列表無下個節點」則新加節點，將計數設為當前計數+1
- 在hash表「不存在」，將數據存入hash表，將數據與雙向鏈表的頭節點相連(這里有可能鏈表未初始化)
這樣當查找，插入時效率都為O(1)
redis TTL 是怎么實現的?
TTL存儲的數據結構
redis針對TTL時間有專門的dict進行存儲，就是redisDb當中的dict *expires字段，dict顧名思義就是一個hashtable，key為對應的rediskey，value為對應的TTL時間。?dict的數據結構中含有2個dictht對象，主要是為了解決hash沖突過程中重新hash數據使用。
TTL 設置過期時間
TTL設置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
從實際設置過期時間的實現函數來看，相對時間的策略會有一個當前時間作為基準時間，絕對時間的策略會「以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。?中途考慮設置的過期時間是否已經過期，如果已經過期那么在master就會刪除該數據并同步刪除動作到slave。?正常的設置過期時間是通過setExpire方法保存到 dict *expires對象當中。
- /*
- *
- * 這個函數是 EXPIRE 、 PEXPIRE 、 EXPIREAT 和 PEXPIREAT 命令的底層實現函數。
- *
- * 命令的第二個參數可能是絕對值，也可能是相對值。
- * 當執行 *AT 命令時， basetime 為 0 ，在其他情況下，它保存的就是當前的絕對時間。
- *
- * unit 用于指定 argv[2] （傳入過期時間）的格式，
- * 它可以是 UNIT_SECONDS 或 UNIT_MILLISECONDS ，
- * basetime 參數則總是毫秒格式的。
- */
- 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 參數
- if (getLongLongFromObjectOrReply(c, param, &when, NULL) != REDIS_OK)
- return;
- // 如果傳入的過期時間是以秒為單位的，那么將它轉換為毫秒
- if (unit == UNIT_SECONDS) when *= 1000;
- when += basetime;
- /* No key, return zero. */
- // 取出鍵
- if (lookupKeyRead(c->db,key) == NULL) {
- addReply(c,shared.czero);
- return;
- }
- /*
- * 在載入數據時，或者服務器為附屬節點時，
- * 即使 EXPIRE 的 TTL 為負數，或者 EXPIREAT 提供的時間戳已經過期，
- * 服務器也不會主動刪除這個鍵，而是等待主節點發來顯式的 DEL 命令。
- *
- * 程序會繼續將（一個可能已經過期的 TTL）設置為鍵的過期時間，
- * 并且等待主節點發來 DEL 命令。
- */
- if (when <= mstime() && !server.loading && !server.masterhost) {
- // when 提供的時間已經過期，服務器為主節點，并且沒在載入數據
- 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 {
- // 設置鍵的過期時間
- // 如果服務器為附屬節點，或者服務器正在載入，
- // 那么這個 when 有可能已經過期的
- 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函數主要是對db->expires中的key對應的dictEntry設置過期時間。
- /*
- * 將鍵 key 的過期時間設為 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);
- // 根據鍵取出鍵的過期時間
- de = dictReplaceRaw(db->expires,dictGetKey(kde));
- // 設置鍵的過期時間
- // 這里是直接使用整數值來保存過期時間，不是用 INT 編碼的 String 對象
- dictSetSignedIntegerVal(de,when);
- }
redis什么時候執行淘汰策略?
在redis種有三種刪除的操作此策略
- 定時刪除：對于設有過期時間的key，時間到了，定時器任務立即執行刪除
- 因為要維護一個定時器，所以就會占用cpu資源，尤其是有過期時間的redis鍵越來越多損耗的性能就會線性上升
- 惰性刪除：每次只有再訪問key的時候，才會檢查key的過期時間，若是已經過期了就執行刪除。
- 這種情況只有在訪問的時候才會刪除，所以有可能有些過期的redis鍵一直不會被訪問，就會一直占用redis內存
- 定期刪除：每隔一段時間，就會檢查刪除掉過期的key。
- 這種方案相當于上述兩種方案的折中，通過最合理控制刪除的時間間隔來刪除key，減少對cpu的資源的占用消耗，使刪除操作合理化。
巨人的肩膀
https://www.jianshu.com/p/53083f5f2ddc https://zhuanlan.zhihu.com/p/265597517
