作者：小林coding
計算機八股文網站：https://xiaolincoding.com
大家好，我是小林。
Redis 的「記憶體淘汰政策」和「過期删除政策」，很多小夥伴容易混淆，這兩個機制雖然都是做删除的操作，但是觸發的條件和使用的政策都是不同的。
今天就跟大家理一理，「記憶體淘汰政策」和「過期删除政策」。
發車！
過期删除政策
Redis 是可以對 key 設定過期時間的，是以需要有相應的機制将已過期的鍵值對删除，而做這個工作的就是過期鍵值删除政策。
如何設定過期時間？
先說一下對 key 設定過期時間的指令。 設定 key 過期時間的指令一共有 4 個：
-
expire <key> <n>
-
pexpire <key> <n>
-
expireat <key> <n>
-
pexpireat <key> <n>
當然，在設定字元串時，也可以同時對 key 設定過期時間，共有 3 種指令：
-
set <key> <value> ex <n>
-
set <key> <value> px <n>
-
setex <key> <n> <valule>
如果你想檢視某個 key 剩餘的存活時間，可以使用
TTL <key>
指令。
# 設定鍵值對的時候，同時指定過期時間位 60 秒
> setex key1 60 value1
OK
# 檢視 key1 過期時間還剩多少
> ttl key1
(integer) 56
> ttl key1
(integer) 52
如果突然反悔，取消 key 的過期時間，則可以使用
PERSIST <key>
指令。
# 取消 key1 的過期時間
> persist key1
(integer) 1
# 使用完 persist 指令之後，
# 查下 key1 的存活時間結果是 -1，表明 key1 永不過期
> ttl key1
(integer) -1
如何判定 key 已過期了？
每當我們對一個 key 設定了過期時間時，Redis 會把該 key 帶上過期時間存儲到一個過期字典（expires dict）中，也就是說「過期字典」儲存了資料庫中所有 key 的過期時間。
過期字典存儲在 redisDb 結構中，如下：
typedef struct redisDb {
dict *dict; /* 資料庫鍵空間，存放着所有的鍵值對 */
dict *expires; /* 鍵的過期時間 */
....
} redisDb;
過期字典資料結構結構如下：
- 過期字典的 key 是一個指針，指向某個鍵對象；
- 過期字典的 value 是一個 long long 類型的整數，這個整數儲存了 key 的過期時間；
過期字典的資料結構如下圖所示：
字典實際上是哈希表，哈希表的最大好處就是讓我們可以用 O(1) 的時間複雜度來快速查找。當我們查詢一個 key 時，Redis 首先檢查該 key 是否存在于過期字典中：
- 如果不在，則正常讀取鍵值；
- 如果存在，則會擷取該 key 的過期時間，然後與目前系統時間進行比對，如果比系統時間大，那就沒有過期，否則判定該 key 已過期。
過期鍵判斷流程如下圖所示：
過期删除政策有哪些？
在說 Redis 過期删除政策之前，先跟大家介紹下，常見的三種過期删除政策：
- 定時删除；
- 惰性删除；
- 定期删除；
接下來，分别分析它們的優缺點。
定時删除政策是怎麼樣的？
定時删除政策的做法是，在設定 key 的過期時間時，同時建立一個定時事件，當時間到達時，由事件處理器自動執行 key 的删除操作。
定時删除政策的優點：
- 可以保證過期 key 會被盡快删除，也就是記憶體可以被盡快地釋放。是以，定時删除對記憶體是最友好的。
定時删除政策的缺點：
- 在過期 key 比較多的情況下，删除過期 key 可能會占用相當一部分 CPU 時間，在記憶體不緊張但 CPU 時間緊張的情況下，将 CPU 時間用于删除和目前任務無關的過期鍵上，無疑會對伺服器的響應時間和吞吐量造成影響。是以，定時删除政策對 CPU 不友好。
惰性删除政策是怎麼樣的？
惰性删除政策的做法是，不主動删除過期鍵，每次從資料庫通路 key 時，都檢測 key 是否過期，如果過期則删除該 key。
惰性删除政策的優點：
- 因為每次通路時，才會檢查 key 是否過期，是以此政策隻會使用很少的系統資源，是以，惰性删除政策對 CPU 時間最友好。
惰性删除政策的缺點：
- 如果一個 key 已經過期，而這個 key 又仍然保留在資料庫中，那麼隻要這個過期 key 一直沒有被通路，它所占用的記憶體就不會釋放，造成了一定的記憶體空間浪費。是以，惰性删除政策對記憶體不友好。
定期删除政策是怎麼樣的？
定期删除政策的做法是，每隔一段時間「随機」從資料庫中取出一定數量的 key 進行檢查，并删除其中的過期key。
定期删除政策的優點：
- 通過限制删除操作執行的時長和頻率，來減少删除操作對 CPU 的影響，同時也能删除一部分過期的資料減少了過期鍵對空間的無效占用。
定期删除政策的缺點：
- 記憶體清理方面沒有定時删除效果好，同時沒有惰性删除使用的系統資源少。
- 難以确定删除操作執行的時長和頻率。如果執行的太頻繁，定期删除政策變得和定時删除政策一樣，對CPU不友好；如果執行的太少，那又和惰性删除一樣了，過期 key 占用的記憶體不會及時得到釋放。
Redis 過期删除政策是什麼？
前面介紹了三種過期删除政策，每一種都有優缺點，僅使用某一個政策都不能滿足實際需求。
是以， Redis 選擇「惰性删除+定期删除」這兩種政策配和使用，以求在合理使用 CPU 時間和避免記憶體浪費之間取得平衡。
Redis 是怎麼實作惰性删除的？
Redis 的惰性删除政策由 db.c 檔案中的
expireIfNeeded
函數實作，代碼如下：
int expireIfNeeded(redisDb *db, robj *key) {
// 判斷 key 是否過期
if (!keyIsExpired(db,key)) return 0;
....
/* 删除過期鍵 */
....
// 如果 server.lazyfree_lazy_expire 為 1 表示異步删除，反之同步删除；
return server.lazyfree_lazy_expire ? dbAsyncDelete(db,key) :
dbSyncDelete(db,key);
}
Redis 在通路或者修改 key 之前，都會調用 expireIfNeeded 函數對其進行檢查，檢查 key 是否過期：
- 如果過期，則删除該 key，至于選擇異步删除，還是選擇同步删除，根據
lazyfree_lazy_expire
- 如果沒有過期，不做任何處理，然後傳回正常的鍵值對給用戶端；
惰性删除的流程圖如下：
Redis 是怎麼實作定期删除的？
再回憶一下，定期删除政策的做法：每隔一段時間「随機」從資料庫中取出一定數量的 key 進行檢查，并删除其中的過期key。
1、這個間隔檢查的時間是多長呢？
在 Redis 中，預設每秒進行 10 次過期檢查一次資料庫，此配置可通過 Redis 的配置檔案 redis.conf 進行配置，配置鍵為 hz 它的預設值是 hz 10。
特别強調下，每次檢查資料庫并不是周遊過期字典中的所有 key，而是從資料庫中随機抽取一定數量的 key 進行過期檢查。
2、随機抽查的數量是多少呢？
我查了下源碼，定期删除的實作在 expire.c 檔案下的
activeExpireCycle
函數中，其中随機抽查的數量由
ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP
定義的，它是寫死在代碼中的，數值是 20。
也就是說，資料庫每輪抽查時，會随機選擇 20 個 key 判斷是否過期。
接下來，詳細說說 Redis 的定期删除的流程：
- 從過期字典中随機抽取 20 個 key；
- 檢查這 20 個 key 是否過期，并删除已過期的 key；
- 如果本輪檢查的已過期 key 的數量，超過 5 個（20/4），也就是「已過期 key 的數量」占比「随機抽取 key 的數量」大于 25%，則繼續重複步驟 1；如果已過期的 key 比例小于 25%，則停止繼續删除過期 key，然後等待下一輪再檢查。
可以看到，定期删除是一個循環的流程。
那 Redis 為了保證定期删除不會出現循環過度，導緻線程卡死現象，為此增加了定期删除循環流程的時間上限，預設不會超過 25ms。
針對定期删除的流程，我寫了個僞代碼：
do {
//已過期的數量
expired = 0；
//随機抽取的數量
num = 20;
while (num--) {
//1. 從過期字典中随機抽取 1 個 key
//2. 判斷該 key 是否過期，如果已過期則進行删除，同時對 expired++
}
// 超過時間限制則退出
if (timelimit_exit) return;
/* 如果本輪檢查的已過期 key 的數量，超過 25%，則繼續随機抽查，否則退出本輪檢查 */
} while (expired > 20/4);
定期删除的流程如下：
記憶體淘汰政策
前面說的過期删除政策，是删除已過期的 key，而當 Redis 的運作記憶體已經超過 Redis 設定的最大記憶體之後，則會使用記憶體淘汰政策删除符合條件的 key，以此來保障 Redis 高效的運作。
如何設定 Redis 最大運作記憶體？
在配置檔案 redis.conf 中，可以通過參數
maxmemory <bytes>
來設定最大運作記憶體，隻有在 Redis 的運作記憶體達到了我們設定的最大運作記憶體，才會觸發記憶體淘汰政策。 不同位數的作業系統，maxmemory 的預設值是不同的：
- 在 64 位作業系統中，maxmemory 的預設值是 0，表示沒有記憶體大小限制，那麼不管使用者存放多少資料到 Redis 中，Redis 也不會對可用記憶體進行檢查，直到 Redis 執行個體因記憶體不足而崩潰也無作為。
- 在 32 位作業系統中，maxmemory 的預設值是 3G，因為 32 位的機器最大隻支援 4GB 的記憶體，而系統本身就需要一定的記憶體資源來支援運作，是以 32 位作業系統限制最大 3 GB 的可用記憶體是非常合理的，這樣可以避免因為記憶體不足而導緻 Redis 執行個體崩潰。
Redis 記憶體淘汰政策有哪些？
Redis 記憶體淘汰政策共有八種，這八種政策大體分為「不進行資料淘汰」和「進行資料淘汰」兩類政策。
1、不進行資料淘汰的政策
noeviction（Redis3.0之後，預設的記憶體淘汰政策） ：它表示當運作記憶體超過最大設定記憶體時，不淘汰任何資料，而是不再提供服務，直接傳回錯誤。
2、進行資料淘汰的政策
針對「進行資料淘汰」這一類政策，又可以細分為「在設定了過期時間的資料中進行淘汰」和「在所有資料範圍内進行淘汰」這兩類政策。
在設定了過期時間的資料中進行淘汰：
- volatile-random：随機淘汰設定了過期時間的任意鍵值；
- volatile-ttl：優先淘汰更早過期的鍵值。
- volatile-lru（Redis3.0 之前，預設的記憶體淘汰政策）：淘汰所有設定了過期時間的鍵值中，最久未使用的鍵值；
- volatile-lfu（Redis 4.0 後新增的記憶體淘汰政策）：淘汰所有設定了過期時間的鍵值中，最少使用的鍵值；
在所有資料範圍内進行淘汰：
- allkeys-random：随機淘汰任意鍵值;
- allkeys-lru：淘汰整個鍵值中最久未使用的鍵值；
- allkeys-lfu（Redis 4.0 後新增的記憶體淘汰政策）：淘汰整個鍵值中最少使用的鍵值。
如何檢視目前 Redis 使用的記憶體淘汰政策？
可以使用
config get maxmemory-policy
指令，來檢視目前 Redis 的記憶體淘汰政策，指令如下：
127.0.0.1:6379> config get maxmemory-policy
1) "maxmemory-policy"
2) "noeviction"
可以看出，目前 Redis 使用的是
noeviction
類型的記憶體淘汰政策，它是 Redis 3.0 之後預設使用的記憶體淘汰政策，表示當運作記憶體超過最大設定記憶體時，不淘汰任何資料，但新增操作會報錯。
如何修改 Redis 記憶體淘汰政策？
設定記憶體淘汰政策有兩種方法：
- 方式一：通過“
config set maxmemory-policy <政策>
- 方式二：通過修改 Redis 配置檔案修改，設定“
maxmemory-policy <政策>
LRU 算法和 LFU 算法有什麼差別？
LFU 記憶體淘汰算法是 Redis 4.0 之後新增記憶體淘汰政策，那為什麼要新增這個算法？那肯定是為了解決 LRU 算法的問題。
接下來，就看看這兩個算法有什麼差別？Redis 又是如何實作這兩個算法的？
什麼是 LRU 算法？
LRU 全稱是 Least Recently Used 翻譯為最近最少使用，會選擇淘汰最近最少使用的資料。
傳統 LRU 算法的實作是基于「連結清單」結構，連結清單中的元素按照操作順序從前往後排列，最新操作的鍵會被移動到表頭，當需要記憶體淘汰時，隻需要删除連結清單尾部的元素即可，因為連結清單尾部的元素就代表最久未被使用的元素。
Redis 并沒有使用這樣的方式實作 LRU 算法，因為傳統的 LRU 算法存在兩個問題：
- 需要用連結清單管理所有的緩存資料，這會帶來額外的空間開銷；
- 當有資料被通路時，需要在連結清單上把該資料移動到頭端，如果有大量資料被通路，就會帶來很多連結清單移動操作，會很耗時，進而會降低 Redis 緩存性能。
Redis 是如何實作 LRU 算法的？
Redis 實作的是一種近似 LRU 算法，目的是為了更好的節約記憶體，它的實作方式是在 Redis 的對象結構體中添加一個額外的字段，用于記錄此資料的最後一次通路時間。
當 Redis 進行記憶體淘汰時，會使用随機采樣的方式來淘汰資料，它是随機取 5 個值（此值可配置），然後淘汰最久沒有使用的那個。
Redis 實作的 LRU 算法的優點：
- 不用為所有的資料維護一個大連結清單，節省了空間占用；
- 不用在每次資料通路時都移動連結清單項，提升了緩存的性能；
但是 LRU 算法有一個問題，無法解決緩存污染問題，比如應用一次讀取了大量的資料，而這些資料隻會被讀取這一次，那麼這些資料會留存在 Redis 緩存中很長一段時間，造成緩存污染。
是以，在 Redis 4.0 之後引入了 LFU 算法來解決這個問題。
什麼是 LFU 算法？
LFU 全稱是 Least Frequently Used 翻譯為最近最不常用的，LFU 算法是根據資料通路次數來淘汰資料的，它的核心思想是“如果資料過去被通路多次，那麼将來被通路的頻率也更高”。
是以， LFU 算法會記錄每個資料的通路次數。當一個資料被再次通路時，就會增加該資料的通路次數。這樣就解決了偶爾被通路一次之後，資料留存在緩存中很長一段時間的問題，相比于 LRU 算法也更合理一些。
Redis 是如何實作 LFU 算法的？
LFU 算法相比于 LRU 算法的實作，多記錄了「資料的通路頻次」的資訊。Redis 對象的結構如下：
typedef struct redisObject {
...
// 24 bits，用于記錄對象的通路資訊
unsigned lru:24;
...
} robj;
Redis 對象頭中的 lru 字段，在 LRU 算法下和 LFU 算法下使用方式并不相同。
在 LRU 算法中，Redis 對象頭的 24 bits 的 lru 字段是用來記錄 key 的通路時間戳，是以在 LRU 模式下，Redis可以根據對象頭中的 lru 字段記錄的值，來比較最後一次 key 的通路時間長，進而淘汰最久未被使用的 key。
在 LFU 算法中，Redis對象頭的 24 bits 的 lru 字段被分成兩段來存儲，高 16bit 存儲 ldt(Last Decrement Time)，低 8bit 存儲 logc(Logistic Counter)。
- ldt 是用來記錄 key 的通路時間戳；
- logc 是用來記錄 key 的通路頻次，它的值越小表示使用頻率越低，越容易淘汰，每個新加入的 key 的logc 初始值為 5。
注意，logc 并不是單純的通路次數，而是通路頻次（通路頻率），因為 logc 會随時間推移而衰減的。
在每次 key 被通路時，會先對 logc 做一個衰減操作，衰減的值跟前後通路時間的差距有關系，如果上一次通路的時間與這一次通路的時間差距很大，那麼衰減的值就越大，這樣實作的 LFU 算法是根據通路頻率來淘汰資料的，而不隻是通路次數。通路頻率需要考慮 key 的通路是多長時間段内發生的。key 的先前通路距離目前時間越長，那麼這個 key 的通路頻率相應地也就會降低，這樣被淘汰的機率也會更大。
對 logc 做完衰減操作後，就開始對 logc 進行增加操作，增加操作并不是單純的 + 1，而是根據機率增加，如果 logc 越大的 key，它的 logc 就越難再增加。
是以，Redis 在通路 key 時，對于 logc 是這樣變化的：
- 先按照上次通路距離目前的時長，來對 logc 進行衰減；
- 然後，再按照一定機率增加 logc 的值
redis.conf 提供了兩個配置項，用于調整 LFU 算法進而控制 logc 的增長和衰減：
-
lfu-decay-time
-
lfu-log-factor
總結
Redis 使用的過期删除政策是「惰性删除+定期删除」，删除的對象是已過期的 key。
記憶體淘汰政策是解決記憶體過大的問題，當 Redis 的運作記憶體超過最大運作記憶體時，就會觸發記憶體淘汰政策，Redis 4.0 之後共實作了 8 種記憶體淘汰政策，我也對這 8 種的政策進行分類，如下：
完！
答應我，下次别再搞混了
系列《圖解 Redis》文章
資料類型篇：
- 2 萬字 + 30 張圖 ｜ 細說 Redis 九種資料類型和應用場景
- 2 萬字 + 50 張圖 ｜ 圖解 Redis 八種資料結構
持久化篇：
- AOF 持久化是怎麼實作的？
- RDB 快照是怎麼實作的？
叢集篇：
- 什麼是緩存雪崩、擊穿、穿透？
- 主從複制是怎麼實作的？
- 為什麼要有哨兵？
架構篇：
- 資料庫和緩存如何保證一緻性？
微信搜尋公衆号：「小林coding」 ，回複「圖解」即可免費獲得「圖解網絡、圖解系統、圖解MySQL、圖解Redis」PDF 電子書