過期鍵刪除策略

在Redis實現之數據庫（二）一小節中，我們知道了數據庫鍵的過期時間都保存在過期字典中，又知道了如果根據過期時間去判斷一個鍵是否過期，現在剩下的問題是：如果一個鍵過期了，那么它什么時候會被刪除呢？這個問題有三種可能的答案，它們分別代表了三種不同的刪除策略：

• 定時刪除：在設置鍵的過期時間的同時，創建一個定時器，讓定時器在鍵的過期時間來臨時，立即執行對鍵的刪除操作
• 惰性刪除：放任鍵過期不管，但是每次從鍵空間中獲取鍵時，都檢查取得的鍵是否過期。如果過期的話，就刪除該鍵；如果沒有過期，就返回該鍵
• 定期刪除：每隔一段時間，程序就對數據庫進行一次檢查，刪除里面的過期鍵。至于要刪除多少過期鍵，以及要檢查多少個數據庫，則由算法決定

在這三種策略中，第一種和第三種為主動刪除，而第二種則為被動刪除

定時刪除

定時刪除策略對內存是最友好的，通過使用定時器，定時刪除策略可以保證過期鍵會盡可能快地被刪除，并釋放過期鍵所占用的內存。另一方面，定期刪除策略的缺點是，它對CPU時間是不友好的：在過期鍵比較多的情況下，刪除過期鍵這一行為可能會占用相當一部分CPU時間，在內存不緊張但是CPU時間非常緊張的情況下，將CPU時間用在刪除和當前任務無關的過期鍵上，無疑會對服務器的響應時間和吞吐量造成影響

例如，如果正有大量的命令請求在等待服務器處理，并且服務器當前不缺少內存，那么服務器應該優先將CPU時間用在處理客戶端的命令請求上面，而不是用在刪除過期鍵上面。除此之外，創建一個定時器需要用到Redis服務器中的時間事件，而當前時間事件的實現方式——無序鏈表，查找一個事件的時間復雜度為O(N)——并不能高效地處理大量時間事件。因此，要讓服務器創建大量的定時器，從而實現定時器刪除策略，現階段來說并不現實

惰性刪除

惰性刪除策略對CPU時間來說是最友好的：程序只會在取出鍵時才對鍵進行過期檢查，這可以保證刪除過期鍵的操作只會在非做不可的情況下進行，并且刪除的目標僅限于當前處理的鍵，這個策略不會在刪除其他無關的過期鍵上花費任何CPU時間。惰性刪除策略的缺點是，它對內存是不友好的：如果一個鍵已經過期，而這個鍵又仍然保留在數據庫中，那么只要這個過期鍵不被刪除，它所占用的內存就不會釋放

在使用惰性刪除策略時，如果數據庫中有非常多的過期鍵，而這些過期鍵又恰好沒有被訪問到的話，那么它們也許永遠不會被刪除（除非用戶手動執行FLUSHDB），我們甚至可以將這種情況看作一種內存泄露——無用的垃圾數據占用了大量內存，而服務器卻不會自己去釋放它們，這對于運行狀態非常依賴內存的Redis服務器來說，肯定不是一個好消息

定期刪除

從上面對定時刪除和惰性刪除的討論來看，這兩種刪除方式在單一使用時都有明顯的缺陷：

• 定期刪除占用太多CPU時間，影響服務器響應時間和吞吐量
• 惰性刪除浪費太多內存，有內存泄露的危險

定期刪除策略是兩種策略的一種整合和折中：

• 定期刪除策略每隔一段時間執行一次刪除過期鍵操作，并通過限制刪除操作執行的時長和頻率來減少刪除操作對CPU時間的影響
• 除此之外，通過定期刪除過期鍵，定期刪除策略有效地減少了因為過期鍵而帶來的內存浪費

定期刪除策略的難點是確定刪除操作執行的時長和效率：

• 如果刪除操作執行得太頻繁，或者執行的時間太長，定期刪除策略就會退化成定時刪除策略，以至于將CPU時間過多地消耗在刪除過期鍵上面
• 如果刪除操作執行得太少，或者執行的時間太短，定期刪除策略又會和惰性刪除策略一樣，出現浪費內存的情況

因此，如果采用定期刪除策略的話，服務器必須根據情況，合理地設置刪除操作的執行時長和執行效率

Redis的過期鍵刪除策略

在前一節，我們討論了定時刪除、惰性刪除和定期刪除三種過期鍵刪除策略，Redis服務器實際使用的是惰性刪除和定期刪除兩種策略，通過配合使用這兩種策略，服務器可以很好地在合理使用CPU時間和避免浪費內存空間之間取得平衡。因為前一節已經介紹過惰性刪除和定期刪除兩種策略的概念了，在接下來的兩個小節中，我們將對Redis服務器中惰性刪除和定期刪除的實現進行說明

惰性刪除策略的實現

過期鍵的惰性刪除策略由db.c/expireIfNeeded函數實現，所有讀寫數據庫的Redis命令在執行之前都會調用expireIfNeeded函數對輸入鍵進行檢查：

• 如果輸入鍵已經過期，那么expireIfNeeded函數將輸入鍵從數據庫中刪除
• 如果輸入鍵未過期，那么expireIfNeeded函數不做任何動作

命令調用expireIfNeeded函數的過程如圖1-15所示

圖1-15? ?命令調用expireIfNeeded來刪除過期鍵

expireIfNeeded函數就像一個過濾器，它可以在命令真正執行之前，過濾掉過期的輸入鍵，從而避免命令接觸到過期鍵。另外，因為每個被訪問的鍵都可能因為過期而被expireIfNeeded函數刪除，所以每個命令的實現函數都必須能同時處理鍵存在以及鍵不存在這兩種情況：

• 當鍵存在，命令按照鍵存在的情況執行
• 當鍵不存在或者鍵因為過期而被expireIfNeeded函數刪除時，命令按照鍵不存在的情況進行

舉個栗子，圖1-16展示了GET命令的執行過程，在這個過程中，命令需要判斷鍵是否存在以及鍵是否過期，然后根據判斷執行合適的操作

圖1-16? ?GET命令的執行過程

定期刪除策略的實現

過期鍵的定期刪除策略由redis.c/activeExpireCycle函數實現，每當Redis的服務器周期性操作redis.c/serverCron函數執行時，activeExpireCycle函數就會被調用，它在規定的時間內，分多次遍歷服務器中的各個數據庫，從數據庫的expires字典中隨機檢查一部分鍵的過期時間，并刪除其中的過期鍵

整個過程可以用偽代碼描述如下：

#默認每次檢查的數據庫數量 DEFAULT_DB_NUMBERS = 16 #默認每個數據庫檢查的鍵數量 DEFAULT_KEY_NUMBERS = 20 #全局變量，記錄檢查進度 current_db = 0 def activeExpireCycle():#初始化要檢查的數據庫數量#如果服務器的數據庫數量比DEFAULT_DB_NUMBERS要小#那么以服務器的數據庫數量為標準if server.dbnum < DEFAULT_DB_NUMBERS：db_numbers = server.dbnumelse:db_numbers = DEFAULT_DB_NUMBERS#遍歷各個數據庫for i in range(db_numbers):#如果current_db的值等于服務器的數據庫數量#這表示檢查程序已經遍歷了服務器的所有數據庫一次#將current_db重置為0，開始新的一輪遍歷if current_db == server.dbnum:current_db = 0#獲取當前要處理的數據庫redisDb = sever.db[current_db]#將數據庫索引加1，指向下一個要處理的數據庫current_db++#檢查數據庫鍵for j in range(DEFAULT_KEY_NUMBERS):#如果數據庫中沒有一個鍵帶有過期時間，那么跳過這個數據庫if redisDb.expires.size() == 0: break#隨機獲取一個帶有過期時間的鍵key_with_ttl = redisDb.expires.get_random_key()#檢查鍵是否過期，如果過期就刪除它if is_expired(key_with_ttl):delete_key(key_with_ttl)#已達到時間上線，停止處理if reach_time_limit(): return

　　

activeExpireCycle函數的工作模式可以總結如下：

• 函數每次運行時，都從一定數量的數據庫中取出一定數量的隨機鍵進行檢查，并刪除其中的過期鍵
• 全局變量current_db會記錄當前activeExpireCycle函數檢查的進度，并在下一次activeExpireCycle函數調用時，接著上一次的進度進行處理。比如說，如果當前activeExpireCycle函數在遍歷10號數據庫時返回了，那么下次activeExpireCycle函數執行時，將從11號數據庫開始查找并刪除過期鍵
• 隨著activeExpireCycle函數的不斷執行，服務器中的所有數據庫都會被檢查一遍，這時函數將current_db變量重置為0，然后再次開始新一輪的檢查工作

AOF、RDB和復制功能對過期鍵的處理

這一節，我們來看看RDB持久化功能、AOF持久化功能以及復制功能是如何處理數據庫的過期鍵

生成RDB文件

在執行SAVE命令或者BGSAVE命令創建一個新的RDB文件時，程序會對數據庫中的鍵進行檢查，已過期的鍵不會被保存到新創建的RDB文件中。舉個栗子，如果數據庫中包含三個鍵k1、k2、k3，并且k2已經過期，那么當執行SAVE命令或者BGSAVE命令時，程序只會將k1和k3的數據保存到RDB文件中，而k2則會被忽略。因此，數據庫中包含過期鍵不會對生成新的RDB文件造成影響

載入RDB文件

在啟動Redis服務器時，如果服務器開啟了RDB功能，那么服務器將對RDB文件進行載入：

• 如果服務器以主服務器模式運行，那么在載入RDB文件時，程序會對文件中保存的鍵進行檢查，未過期的鍵會被載入到數據庫中，而過期鍵則會被忽略，所以過期鍵對載入RDB文件的主服務器不會造成影響
• 如果服務器以從服務器模式運行，那么在載入RDB文件時，文件中保存的所有鍵，不論是否過期，都會被載入到數據庫中。不過，因為主從服務器在進行數據同步的時候，從服務器的數據庫就會被清空，所以一般來講，過期鍵對載入RDB文件的從服務器也不會造成影響

舉個栗子，如果數據庫中包含三個鍵k1、k2、k3，并且k2已經過期，那么當服務器啟動時：

• 如果服務器以主服務器模式運行，那么程序只會將k1、k3載入到數據庫，k2會被忽略
• 如果服務器以從服務器模式運行，那么k1、k2、k3都會被載入到數據庫

AOF文件寫入

當服務器以AOF持久化模式運行時，如果數據庫中的某個鍵已經過期，但它還沒有被惰性刪除或定期刪除，那么AOF文件不會因為這個過期鍵而產生任何影響。當過期鍵被惰性刪除或者定期刪除之后，程序會向AOF文件追加（append）一條DEL命令，來顯示地記錄該鍵已被刪除。舉個栗子，如果客戶端使用GET message命令，試圖訪問過期的message鍵，那么服務器將執行以下三個動作：

• 從數據庫中刪除message鍵
• 追加一條DEL message命令到AOF文件
• 向執行GET命令的客戶端返回空回復

AOF重寫

和生成RDB文件類似，在執行AOF重寫的過程中，程序會對數據庫中的鍵進行檢查，已過期的鍵不會被保存到重寫后的AOF文件中。舉個栗子，如果數據庫包含三個鍵k1、k2、k3，并且k2已經過期，那么在進行重寫工作時，程序只會對k1、k3進行重寫，而k2則會被忽略。因此，數據庫中包含過期鍵不會對AOF重寫造成影響

復制

當服務器運行在復制模式下時，從服務器的過期鍵刪除動作由主服務器控制：

• 主服務器在刪除一個過期鍵之后，會顯示地向所有服務器發送一個DEL命令，告知從服務器刪除這個過期鍵
• 從服務器在執行客戶端發送的讀命令時，即使碰到過期鍵也不會將過期鍵刪除，而是繼續像未過期鍵一樣來處理過期鍵
• 從服務器只有在接收到主服務器發來的DEL命令之后，才會刪除過期鍵

通過由主服務器來控制從服務器統一地刪除過期鍵，可以保證主從服務器數據的一致性，也正是因為這個原因，當一個過期鍵仍然存在于主服務器的數據庫時，這個過期鍵在從服務器的復制品也會繼續存在。舉個栗子，有一對主從服務器，它們的數據庫中都保存著同樣的三個鍵message、xxx和yyy，其中message為過期鍵，如圖1-17所示

圖1-17? ?主從服務器刪除過期鍵（1）

如果這時有客戶端向從服務器發送命令GET message，那么從服務器將發現message鍵已過期，但從服務器不會刪除message鍵，而是繼續將message鍵的值返回給客戶端，就好像message鍵沒有過期一樣，如圖1-18所示

圖1-18? ?主從服務器刪除過期鍵（2）

假設在此之后，有客戶端向主從服務器發送命令GET message，那么服務器發現鍵message已經過期，主服務器會刪除message鍵，向客戶端返回空回復，并向主從服務器發送DEL message命令，如圖1-19所示

圖1-19? ?主從服務器刪除過期鍵（3）

從服務器在接收到主服務器發來的DEL message命令之后，也會從數據庫中刪除message鍵，在這之后，主從服務器不再保存過期鍵message了，如圖1-20所示

圖1-20? ?主從服務器刪除過期鍵（4）

數據庫通知

數據庫通知是Redis2.8版本新增加的功能，這個功能可以讓客戶端通過訂閱給定的頻道或者模式，來獲知數據庫中鍵的變化，以及數據庫中命令的執行情況。舉個栗子，以下代碼展示了客戶端如何獲取0號數據庫中針對message鍵執行的所有命令：

客戶端A訂閱message消息

127.0.0.1:6379> config set notify-keyspace-events KEA OK 127.0.0.1:6379> SUBSCRIBE __keyspace@0__:message Reading messages... (press Ctrl-C to quit) 1) "subscribe" #訂閱消息 2) "__keyspace@0__:message" 3) (integer) 1 1) "message" #執行SET命令 2) "__keyspace@0__:message" 3) "set" 1) "message" #執行EXPIRE命令 2) "__keyspace@0__:message" 3) "expire" 1) "message" #執行DEL命令 2) "__keyspace@0__:message" 3) "del"

　　　　

客戶端B修改message

127.0.0.1:6379> SET message "hello world" OK 127.0.0.1:6379> EXPIRE message 300 (integer) 1 127.0.0.1:6379> DEL message (integer) 1

　　

根據發回的通知顯示，先后共有SET、EXPIRE、DEL三個命令對message進行了操作，對比客戶端B，確實是這樣。這一類關注“某個鍵執行了什么命令”的通知稱為鍵空間通知，除此之外，還有另一類稱為事件通知，它們關注的是“某個命令被什么鍵執行了”

以下就是一個鍵事件通知的例子，代碼展示了客戶端如何獲取0號數據庫的所有執行DEL命令的鍵

客戶端訂閱了DEL事件

127.0.0.1:6379> config set notify-keyspace-events KEA OK 127.0.0.1:6379> SUBSCRIBE __keyevent@0__:del Reading messages... (press Ctrl-C to quit) 1) "subscribe" #訂閱消息 2) "__keyevent@0__:del" 3) (integer) 1 1) "message" #鍵message執行了DE命令 2) "__keyevent@0__:del" 3) "message" 1) "message" #鍵numbers執行了DE命令 2) "__keyevent@0__:del" 3) "numbers" 1) "message" #鍵key執行了DE命令 2) "__keyevent@0__:del" 3) "key"

　　

客戶端B所做的操作

127.0.0.1:6379> SET message "hello world" OK 127.0.0.1:6379> DEL message (integer) 1 127.0.0.1:6379> RPUSH numbers 1 3 5 (integer) 3 127.0.0.1:6379> DEL numbers (integer) 1 127.0.0.1:6379> SET key value OK 127.0.0.1:6379> DEL key (integer) 1

　　

根據發回的通知顯示，message、numbers、key三個鍵先后執行了DEL命令。服務器配置的notify-keyspace-events選項決定了服務器所發送通知的類型：

• 想讓服務器發送所有類型的鍵空間通知和鍵事件通知，可以將選項設置為KEA
• 想讓服務器發送所有類型的鍵空間通知，可以將選項設置為AK
• 想讓服務器發送所有類型的鍵事件通知，可以將選項設置為AE
• 讓服務器只和字符串鍵有關的鍵空間通知，可以將選項設置為K$
• 想讓服務器只發送和列表鍵有關的鍵事件通知，可以將選項設置為El

關于數據庫通知功能的詳細用法，以及notify-keyspace-events選項的更多設置，請看Redis的官方文檔

發送通知

發送數據庫通知的功能由notify.c/notifyKeyspaceEvent函數實現：

void notifyKeyspaceEvent(int type, char *event, robj *key, int dbid);

?

函數的type參數是當前想要發送的通知的類型，程序會根據這個值來判斷通知是否就是服務器配置notify-keyspace-events選項所選定的通知類型，從而決定是否發送通知。event、keys和dbid分別是事件的名稱、產生事件的鍵，以及產生事件的數據庫號碼，函數會根據type參數以及三個參數來構建事件通知的內容，以及接收通知的頻道名

每當一個Redis命令需要發送數據庫通知的時候，該命令的實現函數就會調用notifyKeyspaceEvent函數，并向函數傳遞該命令所引發的事件的相關信息。例如，以下是SADD命令的實現函數saddCommand的其中一部分代碼

void saddCommand(client *c) {……//如果至少有一個元素被成功添加，那么執行以下程序if (added) {//發送事件通知notifyKeyspaceEvent(NOTIFY_SET,"sadd",c->argv[1],c->db->id);}…… }

　　

當SADD命令至少成功地向集合添加一個集合元素之后，命令就會發送通知，該通知的類型為REDIS_NOTIFY_SET（表示這是一個集合鍵通知），名稱為sadd（表示這是執行SADD命令所產生的通知）

以下是另一個例子，展示了DEL命令的實現函數delCommand的其中一部分代碼：

void delCommand(redisClient *c) { int deleted = 0, j; //遍歷所有輸入鍵for (j = 1; j < c->argc; j++) { ……//嘗試刪除鍵if (dbDelete(c->db,c->argv[j])) { ……//刪除鍵成功，發送通知notifyKeyspaceEvent(REDIS_NOTIFY_GENERIC, "del",c->argv[j],c->db->id); …… } } …… }

　　

在delCommand函數中，函數遍歷所有輸入鍵，并在刪除鍵成功時，發送通知，通知類型為REDIS_NOTIFY_GENERIC（表示這是一個通用類型的通知），名稱為del（表示這是執行del命令所產生的通知）

其他發送通知的函數調用notifyKeyspaceEvent函數的方式也和saddCommand、delCommand類似，只是給定的參數不同，接下來，我們看看notifyKeyspaceEvent函數的實現

發送通知的實現

def notifyKeyspaceEvent(type,event,key,dbid):#如果給定的通知不是服務器允許發送的通知，那么直接返回if not(server.notify_keyspace_events & type) :return#發送鍵空間通知if server.notify_keyspace_events & REDIS_NOTIFY_KEYSPACE:#將通知發送給頻道__ keyspace@<dbid>__ :<key>#內容為鍵所發生的事件<event>#構建頻道名字chan="keyspace@{dbid}:{key}".format(dbid=dbid,key=key)#發送通知pubsubPublishMessage(chan,event)#發送鍵事件通知if server.notify_keyspace_events&REDIS_NOTIFY_KEYEVENT:#將通知發送給頻道_keyevent@<dbid>_:<event>#內容為發生事件的鍵<key>#構建頻道名字chan="keyevent@{dbid}:{event}".format(dbid=dbid, event=event)#發送通知pubsubPublishMessage(chan, key)

　　

notifyKeyspaceEvent函數執行以下操作：

server.notify_keyspace_events屬性就是服務器配置notify-keyspace-events選項所設置的值，如果給定的通知事件type不是服務器允許發送的通知類型，那么函數會直接返回，不做任何操作

如果給定的通知是服務器允許發送的通知，那么下一步函數會檢測服務器是否允許發送鍵空間的通知，如果允許的話，程序就會構建發送事件通知

最后，函數檢測服務器是否允許發送事件通知，如果允許的話，程序就會構建并發送事件通知

另外pubsubPublishMessage函數時PUBLISH命令的實現函數，執行這個函數等同于執行PUBLISH命令，訂閱數據庫通知的客戶端收到的信息就是由這個函數發出的

轉載于:https://www.cnblogs.com/beiluowuzheng/p/9739309.html

總結

以上是生活随笔為你收集整理的Redis实现之数据库（三）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。