Redis 過期删除政策和記憶體淘汰機制

Redis 有四個不同的指令可以用于設定鍵的生存時間（鍵可以存在多久）或過期時間（鍵什麼時候會被删除）：

EXPIRE <key> <ttl> ——将鍵 key 的生存時間設定為 ttl 秒。

PEXPIRE <key> <ttl>——将鍵 key 的生存時間設定為 ttl 毫秒。

EXPIREAT <key> <timestamp>——将鍵 key 的過期時間設定為 timestamp 所指定的秒數時間戳。

PEXPIREAT <key> <timestamp>——将鍵 key 的過期時間設定為 timestamp 所指定的毫秒數時間戳。

雖然有多種不同機關和不同形式的設定指令，但實際上 EXPIRE 、PEXPIRE 、EXPIREAT 三個指令都是使用 PEXPIREAT 指令來實作的：無論用戶端執行的是四個指令中的哪一個，經過轉換之後，最終的執行效果都和執行 PEXPIREAT 指令一樣。

Redis 提供了兩個指令，其中 TTL 指令以秒為機關傳回鍵的剩餘生存時間；PTTL 指令則以毫秒為機關傳回鍵的剩餘生存時間。TTL 和 PTTL 兩個指令都是通過計算鍵的過期時間和目前時間之間的差來實作的。

redisDb 結構的 expires 字典儲存了資料庫中所有鍵的過期時間，我們稱這個字典為過期字典：

過期字典的鍵是一個指針，這個指針指向鍵空間的某個鍵對象（也即是某個資料庫鍵）。

過期字典的值是一個 long long 類型的整數，這個整數儲存了鍵所指向的資料庫鍵的過期時間——一個毫秒精度的 UNIX 時間戳。

通過過期字典，程式可以用以下步驟檢查一個給定鍵是否過期：

檢查給定鍵是否存在于過期字典，如果存在，那麼取得鍵的過期時間。

檢查目前 UNIX 時間戳是否大于鍵的過期時間，如果是的話，那麼鍵已經過期，否則的話，鍵未過期。

在設定鍵的過期時間的同時，建立一個定時器（timer），讓定時器在鍵的過期時間來臨時，立即執行對鍵的删除操作。

對記憶體是最友好的。通過使用定時器，定時删除政策可以保證過期鍵會盡可能快地被删除，并釋放過期鍵所占用地記憶體。

對 CPU 時間是最不友好的。在過期鍵比較多的情況下，删除過期鍵這一行為可能會占用相當一部分 CPU 時間，在記憶體不緊張但是 CPU 時間非常緊張的情況下，将 CPU 時間用在删除和目前任務無關的過期鍵上，無疑會對伺服器的響應時間和吞吐量造成影響。

建立一個定時器需要用到 Redis 伺服器中的時間事件，而目前時間事件的實作方式是無序連結清單，查找一個事件的時間複雜度為 O(N)，這并不能高效地處理大量時間事件。

放任鍵過期不管，但是每次從鍵空間中擷取鍵時，都檢查取得的鍵是否過期，如果過期的話，就删除該鍵；如果沒有過期，就傳回該鍵。

對 CPU 時間來說是最友好的。程式隻會在取出鍵時才對鍵進行過期檢查，這可以保證删除過期鍵的操作隻會在非做不可的情況下進行，并且删除的目标僅限于目前處理的鍵，這個政策不會在删除其他無關的過期鍵上花費任何 CPU 時間。

對記憶體是最不友好的。如果一個鍵已經過期，而這個鍵又仍然保留在資料庫中，那麼隻要這個過期鍵不被删除，它所占用的記憶體就不會釋放。如果資料庫中有非常多的過期鍵，而這些過期鍵又恰好沒有被通路到的話，那麼它們也許永遠也不會被删除（除非使用者手動執行 FLUSHDB），我們甚至可以将這種情況看作是一種記憶體洩露，無用的垃圾資料占用了大量記憶體，而伺服器卻不會自己去釋放它們。

每隔一段時間，程式就對資料庫進行一次檢查，删除裡面的過期鍵。至于要删除多少過期鍵，以及要檢查多少個資料庫，則由算法決定。

之前讨論的兩種删除政策都有明顯的缺陷，定期删除政策是前兩種政策的一種整合和折中。

定期删除政策每隔一段時間執行一次删除過期鍵操作，并通過限制删除操作執行的時長和頻率來減少删除操作對 CPU 時間的影響。

除此以外，通過定期删除過期鍵，定期删除政策有效地減少了因為過期鍵而帶來的記憶體浪費。

定期删除的難點是确定删除操作執行的時長和頻率。

如果删除操作執行得太頻繁，或者執行的時間太長，定期删除政策就會退化成定時删除政策，以至于将 CPU 時間過多地消耗在删除過期鍵上面。

如果删除操作執行得太少，或者執行的時間太短，定期删除政策又會和惰性删除政策一樣，出現浪費記憶體的情況。

前面讨論了定時删除、惰性删除和定期删除三種過期鍵删除政策，Redis 伺服器實際使用的是惰性删除和定期删除兩種政策。通過配合使用這兩種政策，伺服器可以很好地在合理使用 CPU 時間和避免浪費記憶體空間之間取得平衡。

過期鍵的惰性删除政策由 db.c/expireIfNeeded 函數實作，所有讀寫資料庫的 Redis 指令在執行之前都會調用 expireIfNeeded 函數對輸入鍵進行檢查：

如果輸入鍵已經過期，那麼 expireIfNeeded 函數将輸入鍵從資料庫中删除。

如果輸入鍵未過期，那麼 expireIfNeeded 函數不做動作。

過期鍵的定期删除政策由 redis.c/activeExpireCycle 函數實作，每當 Redis 的伺服器周期性操作 redis.c/serverCron 函數執行時，activeExpireCycle 函數就會調用，它在規定的時間内，分多次周遊伺服器中的各個資料庫，從資料庫的 expires 字典中随機檢查一部分鍵的過期時間，并删除其中的過期鍵。

Redis 預設每秒進行 10 次過期掃描（Redis 的配置檔案裡面的 hz 參數配置），過期掃描不會周遊過期字典中所有的 key，而是采用了一種簡單的貪心政策，步驟如下：

從過期字典中随機選出 20 個 key。

删除這 20 個 key 中已經過期的 key。

如果過期的 key 的比例超過 1/4，那就重複步驟（1）。

同時，為了保證過期掃描不會出現循環過度，導緻線程卡死的現象，算法還增加了掃描時間的上限，預設不會超過 25ms。

為了限制最大使用記憶體，Redis 提供了配置參數 maxmemory 來限制記憶體超出期望大小。

當實際記憶體超出 maxmemory 時，Redis 提供了幾種可選政策（maxmemory-policy）來讓使用者自己決定該如何騰出新的空間以繼續提供讀寫服務。

noeviction：不會繼續服務寫請求（del 請求可以繼續服務），讀請求可以繼續進行。這樣可以保證不會丢失資料，但是會讓線上的業務不能持續進行。這是預設的淘汰政策。

volatile-lru：嘗試淘汰設定了過期時間的 key，最少使用的 key 優先被淘汰。沒有設定過期時間的 key 不會被淘汰，這樣可以保證需要持久化的資料不會突然丢失。

volatile-ttl：跟上面幾乎一樣，不過淘汰的政策不是 LRU，而是比較 key 的剩餘壽命 ttl 的值，ttl 越小越優先被淘汰。

volatile-random：跟上面幾乎一樣，不過淘汰的 key 是過期 key 集合中随機的 key。

alllkeys-lru：差別于 volatille-lru，這個政策要淘汰的 key 對象是全體的 key 集合，而不隻是過期的 key 集合，這意味着一些沒有設定過期時間的 key 也會被淘汰。

alllkeys-random：跟上面幾乎一樣，不過淘汰的 key 是随機的 key。

volatile-xxx 政策隻會針對帶過期時間的 key 進行淘汰，allkeys-xxx 政策會對所有的 key 進行淘汰。如果你隻是拿 Redis 做緩存，那麼應該使用 allkeys-xxx 政策，用戶端寫緩存時不必攜帶過期時間。如果你還想同時使用 Redis 的持久化功能，那就使用 volatile-xxx 政策，這樣可以保留沒有設定過期時間的 key，它們是永久的 key，不會被 LRU 算法淘汰。

　　Redis 使用的是一種近似 LRU 算法。之是以不使用 LRU 算法，是因為其需要消耗大量的額外記憶體，需要對現有的資料結構進行較大的改造。近似 LRU 算法很簡單，在現有資料結構的基礎上使用随機采樣法來淘汰元素，能達到和 LRU 算法非常近似的效果。

　　當 Redis 執行寫操作時，發現記憶體超出 maxmemory，就會執行一次 LRU 淘汰算法。這個算法也很簡單，就是随機采樣出 5 個 key（數量可以配置，maxmemory_samples），然後淘汰掉最舊的 key，如果淘汰後記憶體還是超出 maxmemory，那就繼續随機采樣淘汰，直到記憶體低于 maxmemory 為止。

如何采樣要看 maxmemory-policy 的設定，如果是 allkeys，就從所有的 key 字典中随機采樣，如果是 volatile，就從帶過期時間的 key 字典中随機采樣。每次采樣多少個 key 取決于 maxmemory_samples 的設定，預設為 5。

　　Redis 3.0 在算法中增加了淘汰池，進一步提升了近似 LRU 算法的效果。淘汰池是一個數組，它的大小是 maxmemory_samples，在每一次淘汰循環中，新的随機得出的 key 清單會和淘汰池中的 key 清單進行融合，淘汰掉最舊的一個 key 之後，保留剩餘較舊的 key 清單放入淘汰池中留待下一個循環。