Redis 內存滿了怎麼辦？

1 簡介

我們知道 Redis 是一個非常常用的內存型數據庫，數據從內存中讀取是它非常高效的原因之一，那麼但是如果有一天，「Redis 分配的內存滿了怎麼辦」？遇到這個面試題不要慌，這種問題我們分爲兩角度回答就可以：

「Redis 會怎麼做」
「我們可以怎麼做」

2 增加 Redis 可用內存

這種方法很暴力，也很好用。我們直接通過增加 Redis 可用內存就可以了，有兩種方式：

「通過配置文件配置」：通過在 Redis 安裝目錄下面的 redis.conf 配置文件中添加以下配置設置內存大小。

1//設置 Redis最大佔用內存大小爲1000M 
2maxmemory 1000mb
3

「通過命令修改」：Redis 支持運行時通過命令動態修改內存大小。

1//設置redis最大佔用內存大小爲1000M  
2127.0.0.1:6379> config set maxmemory 1000mb
3

這種方法的確立竿見影，Redis 內存總歸受限於機器的內存，也不能無限制的增長。那麼如果沒有辦法再增加 Redis 的可用內存怎麼辦呢？

3 內存淘汰策略

實際上 Redis 定義了「8 種內存淘汰策略」用來處理 Redis 內存滿的情況：

noeviction：直接返回錯誤，不淘汰任何已經存在的 Redis 鍵；
allkeys-lru：所有的鍵使用 LRU 算法進行淘汰；
volatile-lru：有過期時間的使用 LRU 算法進行淘汰；
allkeys-random：隨機刪除 Redis 鍵；
volatile-random：隨機刪除有過期時間的 Redis 鍵；
volatile-ttl：刪除快過期的 Redis 鍵；
volatile-lfu：根據 LFU 算法從有過期時間的鍵刪除；
allkeys-lfu：根據 LFU 算法從所有鍵刪除。

這些內存淘汰策略都很好理解，我們着重講解一下 LRU、LFU、TTL 是如何實現。

3.1 LRU 最佳實踐

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

「3. 當插入一條新數據的時候，刪除最久沒有使用過的數據」。

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

但是這兩種數據結構單獨使用都有其弊端、那麼說，有沒有一種數據結構，既能夠保證查詢效率，又能夠保證插入效率呢？於是 hash + 鏈表 這種結構出現了。

hash 表用來查詢在鏈表中的數據位置，鏈表負責數據的插入。當新數據插入到鏈表頭部時有兩種情況：

當鏈表滿的時候，將鏈表尾部的數據丟棄。這個比較簡單，直接將鏈表尾部指針抹去，並且清除對應 hash 中的信息就好了。
每當緩存命中（即緩存數據被訪問），則將數據移到鏈表頭部。這種情況我們發現，如果命中到鏈表中間節點，我們需要做的是：

將該節點移到頭節點；
「將該節點的上一個節點的下一個節點，設置爲該節點的下一個節點」。這裏就會有一個問題，因爲是單向鏈表，我們無法找到該節點的上一個節點。所以，新的模型產生了。

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

所以最終的解決方案就是採用「哈希表 + 雙向鏈表」的結構。

3.2 LFU 最佳實踐

LFU：Least Frequently Used，最不經常使用策略。在一段時間內，數據被「使用頻次最少」的, 優先被淘汰。最少使用（LFU）是一種用於管理計算機內存的緩存算法，主要是記錄和追蹤內存塊的使用次數。

當緩存已滿並且需要更多空間時，系統將以最低內存塊使用頻率清除內存。採用 LFU 算法的最簡單方法是爲每個加載到緩存的塊分配一個計數器。每次引用該塊時，計數器將增加一。當緩存達到容量並有一個新的內存塊等待插入時，系統將搜索計數器最低的塊並將其從緩存中刪除。

這裏我們提出一種達到 O(1) 時間複雜度的 LFU 實現方案，它支持的操作包括插入、訪問以及刪除。如下圖所示：

由兩個雙向鏈表 + 哈希表組成。上方的雙向鏈表用來計數，下方的雙向鏈表用來記錄存儲的數據。該鏈表的頭節點存儲了數字，哈希表的 value 對象記錄下方雙向鏈表的數據、

我們這裏按照插入的流程走一遍：

將需要存儲的數據插入；
在 hash 表中「存在」，找到對應的下方雙向鏈表，將該節點的上一個節點和該節點的下一個節點相連（這裏可能只有自己，直接移除就好）。然後判斷自己所在上方雙向鏈表的計數是否比當前計數大 1：
「如果是」，則將自己移到該上方雙向鏈表，並且「判斷該雙向鏈表下是否還有元素」。如果沒有，則要刪除該節點；
「如果不是或者該上方雙向列表無下個節點」則新加節點，將計數設爲當前計數 + 1。
在 hash 表「不存在」，將數據存入 hash 表，將數據與雙向鏈表的頭節點相連（這裏有可能鏈表未初始化）。

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

4 Redis TTL 是怎麼實現的

4.1 TTL 存儲的數據結構

4.2 TTL 設置過期時間

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

expire：按照相對時間且以秒爲單位的過期策略；
expireat：按照絕對時間且以秒爲單位的過期策略；
pexpire：按照相對時間且以毫秒爲單位的過期策略；
pexpireat：按照絕對時間且以毫秒爲單位的過期策略。

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

4.3 expire expireat pexpire pexpireat

從實際設置過期時間的實現函數來看，相對時間的策略會有一個當前時間作爲基準時間，絕對時間的策略會「以 0 作爲一個基準時間」。

 1void expireCommand(redisClient *c) {
 2    expireGenericCommand(c,mstime(),UNIT_SECONDS);
 3}
 4void expireatCommand(redisClient *c) {
 5    expireGenericCommand(c,0,UNIT_SECONDS);
 6}
 7void pexpireCommand(redisClient *c) {
 8    expireGenericCommand(c,mstime(),UNIT_MILLISECONDS);
 9}
10void pexpireatCommand(redisClient *c) {
11    expireGenericCommand(c,0,UNIT_MILLISECONDS);
12}
13

整個過期時間最後都會換算到絕對時間進行存儲，通過公式基準時間 + 過期時間來進行計算。

對於相對時間而言基準時間就是當前時間，對於絕對時間而言相對時間就是 0。中途考慮設置的過期時間是否已經過期，如果已經過期那麼在 master 就會刪除該數據並同步刪除動作到 slave。

正常的設置過期時間是通過 setExpire 方法保存到 dict *expires 對象當中。

 1/* 
 2*
 3* 這個函數是 EXPIRE 、 PEXPIRE 、 EXPIREAT 和 PEXPIREAT 命令的底層實現函數。
 4*
 5* 命令的第二個參數可能是絕對值，也可能是相對值。
 6* 當執行 *AT 命令時， basetime 爲 0 ，在其他情況下，它保存的就是當前的絕對時間。
 7*
 8* unit 用於指定 argv[2] （傳入過期時間）的格式，
 9* 它可以是 UNIT_SECONDS 或 UNIT_MILLISECONDS ，
10* basetime 參數則總是毫秒格式的。
11*/
12void expireGenericCommand(redisClient *c, long long basetime, int unit) {
13   robj *key = c->argv[1], *param = c->argv[2];
14   long long when; /* unix time in milliseconds when the key will expire. */
15   // 取出 when 參數
16   if (getLongLongFromObjectOrReply(c, param, &when, NULL) != REDIS_OK)
17       return;
18   // 如果傳入的過期時間是以秒爲單位的，那麼將它轉換爲毫秒
19   if (unit == UNIT_SECONDS) when *= 1000;
20   when += basetime;
21   /* No key, return zero. */
22   // 取出鍵
23   if (lookupKeyRead(c->db,key) == NULL) {
24       addReply(c,shared.czero);
25       return;
26   }
27   /* 
28    * 在載入數據時，或者服務器爲附屬節點時，
29    * 即使 EXPIRE 的 TTL 爲負數，或者 EXPIREAT 提供的時間戳已經過期，
30    * 服務器也不會主動刪除這個鍵，而是等待主節點發來顯式的 DEL 命令。
31    *
32    * 程序會繼續將（一個可能已經過期的 TTL）設置爲鍵的過期時間，
33    * 並且等待主節點發來 DEL 命令。
34    */
35   if (when <= mstime() && !server.loading && !server.masterhost) {
36       // when 提供的時間已經過期，服務器爲主節點，並且沒在載入數據
37       robj *aux;
38       redisAssertWithInfo(c,key,dbDelete(c->db,key));
39       server.dirty++;
40       /* Replicate/AOF this as an explicit DEL. */
41       // 傳播 DEL 命令
42       aux = createStringObject("DEL",3);
43       rewriteClientCommandVector(c,2,aux,key);
44       decrRefCount(aux);
45       signalModifiedKey(c->db,key);
46       notifyKeyspaceEvent(REDIS_NOTIFY_GENERIC,"del",key,c->db->id);
47       addReply(c, shared.cone);
48       return;
49   } else {
50       // 設置鍵的過期時間
51       // 如果服務器爲附屬節點，或者服務器正在載入，
52       // 那麼這個 when 有可能已經過期的
53       setExpire(c->db,key,when);
54       addReply(c,shared.cone);
55       signalModifiedKey(c->db,key);
56       notifyKeyspaceEvent(REDIS_NOTIFY_GENERIC,"expire",key,c->db->id);
57       server.dirty++;
58       return;
59   }
60}
61 setExpire函數主要是對db->expires中的key對應的dictEntry設置過期時間。
62/*
63* 將鍵 key 的過期時間設爲 when
64*/
65void setExpire(redisDb *db, robj *key, long long when) {
66   dictEntry *kde, *de;
67   /* Reuse the sds from the main dict in the expire dict */
68   // 取出鍵
69   kde = dictFind(db->dict,key->ptr);
70   redisAssertWithInfo(NULL,key,kde != NULL);
71   // 根據鍵取出鍵的過期時間
72   de = dictReplaceRaw(db->expires,dictGetKey(kde));
73   // 設置鍵的過期時間
74   // 這裏是直接使用整數值來保存過期時間，不是用 INT 編碼的 String 對象
75   dictSetSignedIntegerVal(de,when);
76}
77

4.4 Redis 什麼時候執行淘汰策略

在 Redis 中有三種刪除的操作此策略：

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

5 參考文檔

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

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/7UipC5kC18eeSDBWEdYYIg