數據庫 · Redis 設計與實現（第一版）

# 數據庫 [TOC=2,3] 本章將對 Redis 數據庫的構造和實現進行討論。除了說明數據庫是如何儲存數據對象之外，本章還會討論鍵的過期信息是如何保存，而 Redis 又是如何刪除過期鍵的。 ### 數據庫的結構 Redis 中的每個數據庫，都由一個 `redis.h/redisDb` 結構表示： ~~~ typedef struct redisDb { // 保存著數據庫以整數表示的號碼 int id; // 保存著數據庫中的所有鍵值對數據 // 這個屬性也被稱為鍵空間（key space） dict *dict; // 保存著鍵的過期信息 dict *expires; // 實現列表阻塞原語，如 BLPOP // 在列表類型一章有詳細的討論 dict *blocking_keys; dict *ready_keys; // 用于實現 WATCH 命令 // 在事務章節有詳細的討論 dict *watched_keys; } redisDb; ~~~ 下文將詳細討論 `id` 、 `dict` 和 `expires` 三個屬性，以及針對這三個屬性所執行的數據庫操作。 ### 數據庫的切換 `redisDb` 結構的 `id` 域保存著數據庫的號碼。這個號碼很容易讓人將它和切換數據庫的 [SELECT](http://redis.readthedocs.org/en/latest/connection/select.html#select "(in Redis 命令參考 v2.8)") 命令聯系在一起，但是，實際上，`id` 屬性并不是用來實現 [SELECT](http://redis.readthedocs.org/en/latest/connection/select.html#select "(in Redis 命令參考 v2.8)") 命令，而是給 Redis 內部程序使用的。當 Redis 服務器初始化時，它會創建出 `redis.h/REDIS_DEFAULT_DBNUM` 個數據庫，并將所有數據庫保存到 `redis.h/redisServer.db` 數組中，每個數據庫的 `id` 為從 `0` 到 `REDIS_DEFAULT_DBNUM - 1` 的值。當執行 `SELECT number` 命令時，程序直接使用 `redisServer.db[number]` 來切換數據庫。但是，一些內部程序，比如 AOF 程序、復制程序和 RDB 程序，需要知道當前數據庫的號碼，如果沒有 `id` 域的話，程序就只能在當前使用的數據庫的指針，和 `redisServer.db` 數組中所有數據庫的指針進行對比，以此來弄清楚自己正在使用的是那個數據庫。以下偽代碼描述了這個對比過程： ~~~ def PSEUDO_GET_CURRENT_DB_NUMBER(current_db_pointer): i = 0 for db_pointer in redisServer.db: if db_pointer == current_db_pointer: break i += 1 return i ~~~ 有了 `id` 域的話，程序就可以通過讀取 `id` 域來了解自己正在使用的是哪個數據庫，這樣就不用對比指針那么麻煩了。 ### 數據庫鍵空間因為 Redis 是一個鍵值對數據庫（key-value pairs database），所以它的數據庫本身也是一個字典（俗稱 key space）： - 字典的鍵是一個[字符串](#)對象。 - 字典的值則可以是包括[字符串](#)、[列表](#)、[哈希表](#)、[集合](#)或[有序集](#)在內的任意一種 Redis 類型對象。在 `redisDb` 結構的 `dict` 屬性中，保存著數據庫的所有鍵值對數據。下圖展示了一個包含 `number` 、 `book` 、 `message` 三個鍵的數據庫 ——其中 `number` 鍵是一個列表，列表中包含三個整數值；`book` 鍵是一個哈希表，表中包含三個鍵值對；而 `message` 鍵則指向另一個字符串： ![digraph db { rankdir = LR; node [shape = record, style = filled]; edge [style = bold]; // node redisDb [label = "redisDb | id |<dict> dict | ...", fillcolor = "#A8E270"]; dict [label = "<head>dict\n(key space) |<number>StringObject\n \"number\" | NULL |<book>StringObject\n \"book\" |<message>StringObject\n \"message\"", fillcolor = "#95BBE3"]; number [label = "<head>ListObject | { 123 | 456 | 789 }", fillcolor = "#FADCAD"]; book [label = "<head>HashObject |<name>StringObject\n \"name\" |<author>StringObject\n \"author\" |<publisher>StringObject\n \"publisher\"", fillcolor = "#F2F2F2"]; book_name [label = "<head>StringObject | \"Mastering C++ in 21 days\""]; book_author [label = "<head>StringObject | \"Someone\""]; book_publisher [label = "<head>StringObject | \"Oh-Really? Publisher\""]; message [label = "<head>StringObject | \"hello moto\""]; // edge redisDb:dict -> dict:head; dict:number -> number:head; dict:book -> book:head; dict:message -> message:head; book:name -> book_name:head; book:author -> book_author:head; book:publisher -> book_publisher:head;}](https://box.kancloud.cn/2015-09-13_55f4effddf93b.svg) ### 鍵空間的操作因為數據庫本身是一個字典，所以對數據庫的操作基本上都是對字典的操作，加上以下一些維護操作： - 更新鍵的命中率和不命中率，這個值可以用 [INFO](http://redis.readthedocs.org/en/latest/server/info.html#info "(in Redis 命令參考 v2.8)") 命令查看； - 更新鍵的 LRU 時間，這個值可以用 [OBJECT](http://redis.readthedocs.org/en/latest/key/object.html#object "(in Redis 命令參考 v2.8)") 命令來查看； - 刪除過期鍵（稍后會詳細說明）； - 如果鍵被修改了的話，那么將鍵設為臟（用于事務監視），并將服務器設為臟（等待 RDB 保存）； - 將對鍵的修改發送到 AOF 文件和附屬節點，保持數據庫狀態的一致；作為例子，以下幾個小節會展示鍵的添加、刪除、更新、取值等幾個主要操作。 ### 添加新鍵添加一個新鍵對到數據庫，實際上就是將一個新的鍵值對添加到鍵空間字典中，其中鍵為字符串對象，而值則是任意一種 Redis 類型值對象。舉個例子，如果數據庫的目前狀態如下圖所示（和前面展示的數據庫狀態圖一樣）： ![digraph db { rankdir = LR; node [shape = record, style = filled]; edge [style = bold]; // node redisDb [label = "redisDb | id |<dict> dict | ...", fillcolor = "#A8E270"]; dict [label = "<head>dict\n(key space) |<number>StringObject\n \"number\" | NULL |<book>StringObject\n \"book\" |<message>StringObject\n \"message\"", fillcolor = "#95BBE3"]; number [label = "<head>ListObject | { 123 | 456 | 789 }", fillcolor = "#FADCAD"]; book [label = "<head>HashObject |<name>StringObject\n \"name\" |<author>StringObject\n \"author\" |<publisher>StringObject\n \"publisher\"", fillcolor = "#F2F2F2"]; book_name [label = "<head>StringObject | \"Mastering C++ in 21 days\""]; book_author [label = "<head>StringObject | \"Someone\""]; book_publisher [label = "<head>StringObject | \"Oh-Really? Publisher\""]; message [label = "<head>StringObject | \"hello moto\""]; // edge redisDb:dict -> dict:head; dict:number -> number:head; dict:book -> book:head; dict:message -> message:head; book:name -> book_name:head; book:author -> book_author:head; book:publisher -> book_publisher:head;}](https://box.kancloud.cn/2015-09-13_55f4effdeec5c.svg) 那么在客戶端執行 `SET date 2013.2.1` 命令之后，數據庫更新為下圖狀態： ![digraph db_after_insert_new_key { rankdir = LR; node [shape = record, style = filled]; edge [style = bold]; // node redisDb [label = "redisDb | id |<dict> dict | ...", fillcolor = "#A8E270"]; dict [label = "<head>dict\n(key space) |<number>StringObject\n \"number\" |<date>StringObject\n \"date\" |<book>StringObject\n \"book\" |<message>StringObject\n \"message\"", fillcolor = "#95BBE3"]; number [label = "<head>ListObject | { 123 | 456 | 789 }", fillcolor = "#FADCAD"]; book [label = "<head>HashObject |<name>StringObject\n \"name\" |<author>StringObject\n \"author\" |<publisher>StringObject\n \"publisher\"", fillcolor = "#F2F2F2"]; book_name [label = "<head>StringObject | \"Mastering C++ in 21 days\""]; book_author [label = "<head>StringObject | \"Someone\""]; book_publisher [label = "<head>StringObject | \"Oh-Really? Publisher\""]; message [label = "<head>StringObject | \"hello moto\""]; date [label = "<head>StringObject | \"2013.2.1\"", fillcolor = "#FFC1C1"]; // edge redisDb:dict -> dict:head; dict:number -> number:head; dict:date -> date; dict:book -> book:head; dict:message -> message:head; book:name -> book_name:head; book:author -> book_author:head; book:publisher -> book_publisher:head;}](https://box.kancloud.cn/2015-09-13_55f4effe04320.svg) ### 刪除鍵刪除數據庫中的一個鍵，實際上就是刪除字典空間中對應的鍵對象和值對象。舉個例子，如果數據庫的目前狀態如下圖所示（和前面展示的數據庫狀態圖一樣）： ![digraph db { rankdir = LR; node [shape = record, style = filled]; edge [style = bold]; // node redisDb [label = "redisDb | id |<dict> dict | ...", fillcolor = "#A8E270"]; dict [label = "<head>dict\n(key space) |<number>StringObject\n \"number\" | NULL |<book>StringObject\n \"book\" |<message>StringObject\n \"message\"", fillcolor = "#95BBE3"]; number [label = "<head>ListObject | { 123 | 456 | 789 }", fillcolor = "#FADCAD"]; book [label = "<head>HashObject |<name>StringObject\n \"name\" |<author>StringObject\n \"author\" |<publisher>StringObject\n \"publisher\"", fillcolor = "#F2F2F2"]; book_name [label = "<head>StringObject | \"Mastering C++ in 21 days\""]; book_author [label = "<head>StringObject | \"Someone\""]; book_publisher [label = "<head>StringObject | \"Oh-Really? Publisher\""]; message [label = "<head>StringObject | \"hello moto\""]; // edge redisDb:dict -> dict:head; dict:number -> number:head; dict:book -> book:head; dict:message -> message:head; book:name -> book_name:head; book:author -> book_author:head; book:publisher -> book_publisher:head;}](https://box.kancloud.cn/2015-09-13_55f4effe0c971.svg) 那么在客戶端執行 `DEL message` 命令之后，數據庫更新為下圖狀態： ![digraph db { rankdir = LR; node [shape = record, style = filled]; edge [style = bold]; // node redisDb [label = "redisDb | id |<dict> dict | ...", fillcolor = "#A8E270"]; dict [label = "<head>dict\n(key space) |<number>StringObject\n \"number\" | NULL |<book>StringObject\n \"book\" | NULL", fillcolor = "#FFC1C1"]; number [label = "<head>ListObject | { 123 | 456 | 789 }", fillcolor = "#FADCAD"]; book [label = "<head>HashObject |<name>StringObject\n \"name\" |<author>StringObject\n \"author\" |<publisher>StringObject\n \"publisher\"", fillcolor = "#F2F2F2"]; book_name [label = "<head>StringObject | \"Mastering C++ in 21 days\""]; book_author [label = "<head>StringObject | \"Someone\""]; book_publisher [label = "<head>StringObject | \"Oh-Really? Publisher\""]; // edge redisDb:dict -> dict:head; dict:number -> number:head; dict:book -> book:head; book:name -> book_name:head; book:author -> book_author:head; book:publisher -> book_publisher:head;}](https://box.kancloud.cn/2015-09-13_55f4effe165fe.svg) ### 更新鍵當對一個已存在于數據庫的鍵執行更新操作時，數據庫釋放鍵原來的值對象，然后將指針指向新的值對象。舉個例子，如果數據庫的目前狀態如下圖所示（和前面展示的數據庫狀態圖一樣）： ![digraph db { rankdir = LR; node [shape = record, style = filled]; edge [style = bold]; // node redisDb [label = "redisDb | id |<dict> dict | ...", fillcolor = "#A8E270"]; dict [label = "<head>dict\n(key space) |<number>StringObject\n \"number\" | NULL |<book>StringObject\n \"book\" |<message>StringObject\n \"message\"", fillcolor = "#95BBE3"]; number [label = "<head>ListObject | { 123 | 456 | 789 }", fillcolor = "#FADCAD"]; book [label = "<head>HashObject |<name>StringObject\n \"name\" |<author>StringObject\n \"author\" |<publisher>StringObject\n \"publisher\"", fillcolor = "#F2F2F2"]; book_name [label = "<head>StringObject | \"Mastering C++ in 21 days\""]; book_author [label = "<head>StringObject | \"Someone\""]; book_publisher [label = "<head>StringObject | \"Oh-Really? Publisher\""]; message [label = "<head>StringObject | \"hello moto\""]; // edge redisDb:dict -> dict:head; dict:number -> number:head; dict:book -> book:head; dict:message -> message:head; book:name -> book_name:head; book:author -> book_author:head; book:publisher -> book_publisher:head;}](https://box.kancloud.cn/2015-09-13_55f4effe2257a.svg) 那么在客戶端執行 `SET message "blah blah"` 命令之后，數據庫更新為下圖狀態： ![digraph db { rankdir = LR; node [shape = record, style = filled]; edge [style = bold]; // node redisDb [label = "redisDb | id |<dict> dict | ...", fillcolor = "#A8E270"]; dict [label = "<head>dict\n(key space) |<number>StringObject\n \"number\" | NULL |<book>StringObject\n \"book\" |<message>StringObject\n \"message\"", fillcolor = "#95BBE3"]; number [label = "<head>ListObject | { 123 | 456 | 789 }", fillcolor = "#FADCAD"]; book [label = "<head>HashObject |<name>StringObject\n \"name\" |<author>StringObject\n \"author\" |<publisher>StringObject\n \"publisher\"", fillcolor = "#F2F2F2"]; book_name [label = "<head>StringObject | \"Mastering C++ in 21 days\""]; book_author [label = "<head>StringObject | \"Someone\""]; book_publisher [label = "<head>StringObject | \"Oh-Really? Publisher\""]; message [label = "<head>StringObject | \"blah blah\"", fillcolor = "#FFC1C1"]; // edge redisDb:dict -> dict:head; dict:number -> number:head; dict:book -> book:head; dict:message -> message:head; book:name -> book_name:head; book:author -> book_author:head; book:publisher -> book_publisher:head;}](https://box.kancloud.cn/2015-09-13_55f4effe2b4c6.svg) ### 取值在數據庫中取值實際上就是在字典空間中取值，再加上一些額外的類型檢查： - 鍵不存在，返回空回復； - 鍵存在，且類型正確，按照通訊協議返回值對象； - 鍵存在，但類型不正確，返回類型錯誤。舉個例子，如果數據庫的目前狀態如下圖所示（和前面展示的數據庫狀態圖一樣）： ![digraph db { rankdir = LR; node [shape = record, style = filled]; edge [style = bold]; // node redisDb [label = "redisDb | id |<dict> dict | ...", fillcolor = "#A8E270"]; dict [label = "<head>dict\n(key space) |<number>StringObject\n \"number\" | NULL |<book>StringObject\n \"book\" |<message>StringObject\n \"message\"", fillcolor = "#95BBE3"]; number [label = "<head>ListObject | { 123 | 456 | 789 }", fillcolor = "#FADCAD"]; book [label = "<head>HashObject |<name>StringObject\n \"name\" |<author>StringObject\n \"author\" |<publisher>StringObject\n \"publisher\"", fillcolor = "#F2F2F2"]; book_name [label = "<head>StringObject | \"Mastering C++ in 21 days\""]; book_author [label = "<head>StringObject | \"Someone\""]; book_publisher [label = "<head>StringObject | \"Oh-Really? Publisher\""]; message [label = "<head>StringObject | \"hello moto\""]; // edge redisDb:dict -> dict:head; dict:number -> number:head; dict:book -> book:head; dict:message -> message:head; book:name -> book_name:head; book:author -> book_author:head; book:publisher -> book_publisher:head;}](https://box.kancloud.cn/2015-09-13_55f4effe333bf.svg) 當客戶端執行 `GET message` 時，服務器返回 `"hello moto"` 。當客戶端執行 `GET not-exists-key` 時，服務器返回空回復。當服務器執行 `GET book` 時，服務器返回類型錯誤。 ### 其他操作除了上面展示的鍵值操作之外，還有很多針對數據庫本身的命令，也是通過對鍵空間進行處理來完成的： - [FLUSHDB](http://redis.readthedocs.org/en/latest/server/flushdb.html#flushdb "(in Redis 命令參考 v2.8)") 命令：刪除鍵空間中的所有鍵值對。 - [RANDOMKEY](http://redis.readthedocs.org/en/latest/key/randomkey.html#randomkey "(in Redis 命令參考 v2.8)") 命令：從鍵空間中隨機返回一個鍵。 - [DBSIZE](http://redis.readthedocs.org/en/latest/server/dbsize.html#dbsize "(in Redis 命令參考 v2.8)") 命令：返回鍵空間中鍵值對的數量。 - [EXISTS](http://redis.readthedocs.org/en/latest/key/exists.html#exists "(in Redis 命令參考 v2.8)") 命令：檢查給定鍵是否存在于鍵空間中。 - [RENAME](http://redis.readthedocs.org/en/latest/key/rename.html#rename "(in Redis 命令參考 v2.8)") 命令：在鍵空間中，對給定鍵進行改名。等等。 ### 鍵的過期時間在前面的內容中，我們討論了很多涉及數據庫本身、以及對數據庫中的鍵值對進行處理的操作，但是，關于數據庫如何保存鍵的過期時間，以及如何處理過期鍵這一問題，我們還沒有討論到。通過 [EXPIRE](http://redis.readthedocs.org/en/latest/key/expire.html#expire "(in Redis 命令參考 v2.8)") 、 [PEXPIRE](http://redis.readthedocs.org/en/latest/key/pexpire.html#pexpire "(in Redis 命令參考 v2.8)") 、 [EXPIREAT](http://redis.readthedocs.org/en/latest/key/expireat.html#expireat "(in Redis 命令參考 v2.8)") 和 [PEXPIREAT](http://redis.readthedocs.org/en/latest/key/pexpireat.html#pexpireat "(in Redis 命令參考 v2.8)") 四個命令，客戶端可以給某個存在的鍵設置過期時間，當鍵的過期時間到達時，鍵就不再可用： ~~~ redis> SETEX key 5 value OK redis> GET key "value" redis> GET key // 5 秒過后 (nil) ~~~ 命令 [TTL](http://redis.readthedocs.org/en/latest/key/ttl.html#ttl "(in Redis 命令參考 v2.8)") 和 [PTTL](http://redis.readthedocs.org/en/latest/key/pttl.html#pttl "(in Redis 命令參考 v2.8)") 則用于返回給定鍵距離過期還有多長時間： ~~~ redis> SETEX key 10086 value OK redis> TTL key (integer) 10082 redis> PTTL key (integer) 10068998 ~~~ 在接下來的內容中，我們將探討和鍵的過期時間相關的問題：比如鍵的過期時間是如何保存的，而過期鍵又是如何被刪除的，等等。 ### 過期時間的保存在數據庫中，所有鍵的過期時間都被保存在 `redisDb` 結構的 `expires` 字典里： ~~~ typedef struct redisDb { // ... dict *expires; // ... } redisDb; ~~~ `expires` 字典的鍵是一個指向 `dict` 字典（鍵空間）里某個鍵的指針，而字典的值則是鍵所指向的數據庫鍵的到期時間，這個值以 `long long` 類型表示。下圖展示了一個含有三個鍵的數據庫，其中 `number` 和 `book` 兩個鍵帶有過期時間： ![digraph db_with_expire_time { rankdir = LR; node [shape = record, style = filled]; edge [style = bold]; // node redisDb [label = "redisDb | id |<dict> dict |<expires> expires | ...", fillcolor = "#A8E270"]; // dict dict [label = "<head>dict\n(key space) |<number>StringObject\n \"number\" | NULL |<book>StringObject\n \"book\" |<message>StringObject\n \"message\"", fillcolor = "#95BBE3"]; number [label = "<head>ListObject | { 123 | 456 | 789 }", fillcolor = "#FADCAD"]; book [label = "<head>HashObject |<name>StringObject\n \"name\" |<author>StringObject\n \"author\" |<publisher>StringObject\n \"publisher\"", fillcolor = "#F2F2F2"]; book_name [label = "<head>StringObject | \"Mastering C++ in 21 days\""]; book_author [label = "<head>StringObject | \"Someone\""]; book_publisher [label = "<head>StringObject | \"Oh-Really? Publisher\""]; message [label = "<head>StringObject | \"hello moto\""]; // dict edge redisDb:dict -> dict:head; dict:number -> number:head; dict:book -> book:head; dict:message -> message:head; book:name -> book_name:head; book:author -> book_author:head; book:publisher -> book_publisher:head; // expires expires [label = "<head>dict |<number>StringObject\n \"number\" | NULL |<book>StringObject\n \"book\" | NULL ", fillcolor = "#95BBE3"]; expire_of_number [label = "<head>long long | 1360454400000 "]; expire_of_book [label = "<head>long long | 1360800000000 "]; // expires edge redisDb:expires -> expires:head; expires:number -> expire_of_number:head; expires:book -> expire_of_book:head;}](https://box.kancloud.cn/2015-09-13_55f4effe3c4b3.svg) Note 為了展示的方便，圖中重復出現了兩次 `number` 鍵和 `book` 鍵。在實際中，鍵空間字典的鍵和過期時間字典的鍵都指向同一個字符串對象，所以不會浪費任何空間。 ### 設置生存時間 Redis 有四個命令可以設置鍵的生存時間（可以存活多久）和過期時間（什么時候到期）： - [EXPIRE](http://redis.readthedocs.org/en/latest/key/expire.html#expire "(in Redis 命令參考 v2.8)") 以秒為單位設置鍵的生存時間； - [PEXPIRE](http://redis.readthedocs.org/en/latest/key/pexpire.html#pexpire "(in Redis 命令參考 v2.8)") 以毫秒為單位設置鍵的生存時間； - [EXPIREAT](http://redis.readthedocs.org/en/latest/key/expireat.html#expireat "(in Redis 命令參考 v2.8)") 以秒為單位，設置鍵的過期 UNIX 時間戳； - [PEXPIREAT](http://redis.readthedocs.org/en/latest/key/pexpireat.html#pexpireat "(in Redis 命令參考 v2.8)") 以毫秒為單位，設置鍵的過期 UNIX 時間戳。雖然有那么多種不同單位和不同形式的設置方式，但是 `expires` 字典的值只保存“以毫秒為單位的過期 UNIX 時間戳”，這就是說，通過進行轉換，所有命令的效果最后都和 [PEXPIREAT](http://redis.readthedocs.org/en/latest/key/pexpireat.html#pexpireat "(in Redis 命令參考 v2.8)") 命令的效果一樣。舉個例子，從 [EXPIRE](http://redis.readthedocs.org/en/latest/key/expire.html#expire "(in Redis 命令參考 v2.8)") 命令到 [PEXPIREAT](http://redis.readthedocs.org/en/latest/key/pexpireat.html#pexpireat "(in Redis 命令參考 v2.8)") 命令的轉換可以用偽代碼表示如下： ~~~ def EXPIRE(key, sec): # 將 TTL 從秒轉換為毫秒 ms = sec_to_ms(sec) # 獲取以毫秒計算的當前 UNIX 時間戳 ts_in_ms = get_current_unix_timestamp_in_ms() # 毫秒 TTL 加上毫秒時間戳，就是 key 到期的時間戳 PEXPIREAT(ms + ts_in_ms, key) ~~~ 其他函數的轉換方式也是類似的。作為例子，下圖展示了一個 `expires` 字典示例，字典中 `number` 鍵的過期時間是 2013 年 2 月 10 日（農歷新年），而 `book` 鍵的過期時間則是 2013 年 2 月 14 日（情人節）： ![digraph expires { rankdir = LR; node [shape = record, style =filled]; edge [style = bold]; // node redisDb [label = "redisDb | id | ... |<expires> expires | ...", fillcolor = "#A8E270"]; // expires expires [label = "<head>dict |<number>StringObject\n \"number\" | NULL |<book>StringObject\n \"book\" | NULL ", fillcolor = "#95BBE3"]; expire_of_number [label = "<head>long long | 1360454400000 "]; expire_of_book [label = "<head>long long | 1360800000000 "]; // expires edge redisDb:expires -> expires:head; expires:number -> expire_of_number:head; expires:book -> expire_of_book:head;}](https://box.kancloud.cn/2015-09-13_55f4effe464fd.svg) 這兩個鍵的過期時間可能是用以上四個命令的任意一個設置的，但它們都以統一的格式被保存在 `expires` 字典中。 ### 過期鍵的判定通過 `expires` 字典，可以用以下步驟檢查某個鍵是否過期： 1. 檢查鍵是否存在于 `expires` 字典：如果存在，那么取出鍵的過期時間； 1. 檢查當前 UNIX 時間戳是否大于鍵的過期時間：如果是的話，那么鍵已經過期；否則，鍵未過期。可以用偽代碼來描述這一過程： ~~~ def is_expired(key): # 取出鍵的過期時間 key_expire_time = expires.get(key) # 如果過期時間不為空，并且當前時間戳大于過期時間，那么鍵已經過期 if expire_time is not None and current_timestamp() > key_expire_time: return True # 否則，鍵未過期或沒有設置過期時間 return False ~~~ ### 過期鍵的清除我們知道了過期時間保存在 `expires` 字典里，又知道了該如何判定一個鍵是否過期，現在剩下的問題是，如果一個鍵是過期的，那它什么時候會被刪除？這個問題有三種可能的答案： 1. 定時刪除：在設置鍵的過期時間時，創建一個定時事件，當過期時間到達時，由事件處理器自動執行鍵的刪除操作。 1. 惰性刪除：放任鍵過期不管，但是在每次從 `dict` 字典中取出鍵值時，要檢查鍵是否過期，如果過期的話，就刪除它，并返回空；如果沒過期，就返回鍵值。 1. 定期刪除：每隔一段時間，對 `expires` 字典進行檢查，刪除里面的過期鍵。 ### 定時刪除定時刪除策略對內存是最友好的：因為它保證過期鍵會在第一時間被刪除，過期鍵所消耗的內存會立即被釋放。這種策略的缺點是，它對 CPU 時間是最不友好的：因為刪除操作可能會占用大量的 CPU 時間 ——在內存不緊張、但是 CPU 時間非常緊張的時候（比如說，進行交集計算或排序的時候），將 CPU 時間花在刪除那些和當前任務無關的過期鍵上，這種做法毫無疑問會是低效的。除此之外，目前 Redis 事件處理器對時間事件的實現方式 —— 無序鏈表，查找一個時間復雜度為 \(O(N)\) —— 并不適合用來處理大量時間事件。 ### 惰性刪除惰性刪除對 CPU 時間來說是最友好的：它只會在取出鍵時進行檢查，這可以保證刪除操作只會在非做不可的情況下進行 ——并且刪除的目標僅限于當前處理的鍵，這個策略不會在刪除其他無關的過期鍵上花費任何 CPU 時間。惰性刪除的缺點是，它對內存是最不友好的：如果一個鍵已經過期，而這個鍵又仍然保留在數據庫中，那么 `dict` 字典和 `expires` 字典都需要繼續保存這個鍵的信息，只要這個過期鍵不被刪除，它占用的內存就不會被釋放。在使用惰性刪除策略時，如果數據庫中有非常多的過期鍵，但這些過期鍵又正好沒有被訪問的話，那么它們就永遠也不會被刪除（除非用戶手動執行），這對于性能非常依賴于內存大小的 Redis 來說，肯定不是一個好消息。舉個例子，對于一些按時間點來更新的數據，比如日志（log），在某個時間點之后，對它們的訪問就會大大減少，如果大量的這些過期數據積壓在數據庫里面，用戶以為它們已經過期了（已經被刪除了），但實際上這些鍵卻沒有真正的被刪除（內存也沒有被釋放），那結果肯定是非常糟糕。 ### 定期刪除從上面對定時刪除和惰性刪除的討論來看，這兩種刪除方式在單一使用時都有明顯的缺陷：定時刪除占用太多 CPU 時間，惰性刪除浪費太多內存。定期刪除是這兩種策略的一種折中： - 它每隔一段時間執行一次刪除操作，并通過限制刪除操作執行的時長和頻率，籍此來減少刪除操作對 CPU 時間的影響。 - 另一方面，通過定期刪除過期鍵，它有效地減少了因惰性刪除而帶來的內存浪費。 ### Redis 使用的策略 Redis 使用的過期鍵刪除策略是惰性刪除加上定期刪除，這兩個策略相互配合，可以很好地在合理利用 CPU 時間和節約內存空間之間取得平衡。因為前面已經說了這兩個策略的概念了，下面兩節就來探討這兩個策略在 Redis 中的具體實現。 ### 過期鍵的惰性刪除策略實現過期鍵惰性刪除策略的核心是 `db.c/expireIfNeeded` 函數 ——所有命令在讀取或寫入數據庫之前，程序都會調用 `expireIfNeeded` 對輸入鍵進行檢查，并將過期鍵刪除： ![digraph expire_check { node [style = filled, shape = plaintext]; edge [style = bold]; // node write_commands [label = "SET 、\n LPUSH 、\n SADD 、 \n 等等", fillcolor = "#FADCAD"]; read_commands [label = "GET 、\n LRANGE 、\n SMEMBERS 、 \n 等等", fillcolor = "#FADCAD"]; expire_if_needed [label = "調用 expire_if_needed() \n 刪除過期鍵", shape = box, fillcolor = "#A8E270"]; process [label = "執行實際的命令流程"]; // edge write_commands -> expire_if_needed [label = "寫請求"]; read_commands -> expire_if_needed [label = "讀請求"]; expire_if_needed -> process;}](https://box.kancloud.cn/2015-09-13_55f4effe4fc41.svg) 比如說， `GET` 命令的執行流程可以用下圖來表示： ![digraph get_with_expire { node [style = filled, shape = plaintext]; edge [style = bold]; // node get [label = "GET key", fillcolor = "#FADCAD"]; expire_if_needed [label = "調用\n expire_if_needed() \n 如果鍵已經過期 \n 那么將它刪除", shape = diamond, fillcolor = "#A8E270"]; expired_and_deleted [label = "key 不存在\n 向客戶端返回 NIL"]; not_expired [label = "向客戶端返回 key 的值"]; get -> expire_if_needed; expire_if_needed -> expired_and_deleted [label = "已過期"]; expire_if_needed -> not_expired [label = "未過期"];}](https://box.kancloud.cn/2015-09-13_55f4effe5a585.svg) `expireIfNeeded` 的作用是，如果輸入鍵已經過期的話，那么將鍵、鍵的值、鍵保存在 `expires` 字典中的過期時間都刪除掉。用偽代碼描述的 `expireIfNeeded` 定義如下： ~~~ def expireIfNeeded(key): # 對過期鍵執行以下操作。。。 if key.is_expired(): # 從鍵空間中刪除鍵值對 db.dict.remove(key) # 刪除鍵的過期時間 db.expires.remove(key) # 將刪除命令傳播到 AOF 文件和附屬節點 propagateDelKeyToAofAndReplication(key) ~~~ ### 過期鍵的定期刪除策略對過期鍵的定期刪除由 `redis.c/activeExpireCycle` 函執行：每當 Redis 的例行處理程序 `serverCron` 執行時，`activeExpireCycle` 都會被調用 ——這個函數在規定的時間限制內，盡可能地遍歷各個數據庫的 `expires` 字典，隨機地檢查一部分鍵的過期時間，并刪除其中的過期鍵。整個過程可以用偽代碼描述如下： ~~~ def activeExpireCycle(): # 遍歷數據庫（不一定能全部都遍歷完，看時間是否足夠） for db in server.db: # MAX_KEY_PER_DB 是一個 DB 最大能處理的 key 個數 # 它保證時間不會全部用在個別的 DB 上（避免饑餓） i = 0 while (i < MAX_KEY_PER_DB): # 數據庫為空，跳出 while ，處理下個 DB if db.is_empty(): break # 隨機取出一個帶 TTL 的鍵 key_with_ttl = db.expires.get_random_key() # 檢查鍵是否過期，如果是的話，將它刪除 if is_expired(key_with_ttl): db.deleteExpiredKey(key_with_ttl) # 當執行時間到達上限，函數就返回，不再繼續 # 這確保刪除操作不會占用太多的 CPU 時間 if reach_time_limit(): return i += 1 ~~~ ### 過期鍵對 AOF 、RDB 和復制的影響前面的內容討論了過期鍵對 CPU 時間和內存的影響，現在，是時候說說過期鍵在 RDB 文件、 AOF 文件、 AOF 重寫以及復制中的影響了：過期鍵會被保存在更新后的 RDB 文件、 AOF 文件或者重寫后的 AOF 文件里面嗎？附屬節點會會如何處理過期鍵？處理的方式和主節點一樣嗎？以上這些問題就是本節要解答的。 ### 更新后的 RDB 文件在創建新的 RDB 文件時，程序會對鍵進行檢查，過期的鍵不會被寫入到更新后的 RDB 文件中。因此，過期鍵對更新后的 RDB 文件沒有影響。 ### AOF 文件在鍵已經過期，但是還沒有被惰性刪除或者定期刪除之前，這個鍵不會產生任何影響，AOF 文件也不會因為這個鍵而被修改。當過期鍵被惰性刪除、或者定期刪除之后，程序會向 AOF 文件追加一條 `DEL` 命令，來顯式地記錄該鍵已被刪除。舉個例子，如果客戶端使用 `GET message` 試圖訪問 `message` 鍵的值，但 `message` 已經過期了，那么服務器執行以下三個動作： 1. 從數據庫中刪除 `message` ； 1. 追加一條 `DEL message` 命令到 AOF 文件； 1. 向客戶端返回 `NIL` 。 ### AOF 重寫和 RDB 文件類似，當進行 AOF 重寫時，程序會對鍵進行檢查，過期的鍵不會被保存到重寫后的 AOF 文件。因此，過期鍵對重寫后的 AOF 文件沒有影響。 ### 復制當服務器帶有附屬節點時，過期鍵的刪除由主節點統一控制： - 如果服務器是主節點，那么它在刪除一個過期鍵之后，會顯式地向所有附屬節點發送一個 `DEL` 命令。 - 如果服務器是附屬節點，那么當它碰到一個過期鍵的時候，它會向程序返回鍵已過期的回復，但并不真正的刪除過期鍵。因為程序只根據鍵是否已經過期、而不是鍵是否已經被刪除來決定執行流程，所以這種處理并不影響命令的正確執行結果。當接到從主節點發來的 `DEL` 命令之后，附屬節點才會真正的將過期鍵刪除掉。附屬節點不自主對鍵進行刪除是為了和主節點的數據保持絕對一致，因為這個原因，當一個過期鍵還存在于主節點時，這個鍵在所有附屬節點的副本也不會被刪除。這種處理機制對那些使用大量附屬節點，并且帶有大量過期鍵的應用來說，可能會造成一部分內存不能立即被釋放，但是，因為過期鍵通常很快會被主節點發現并刪除，所以這實際上也算不上什么大問題。 ### 數據庫空間的收縮和擴展因為數據庫空間是由字典來實現的，所以數據庫空間的擴展/收縮規則和字典的擴展/收縮規則完全一樣，具體的信息可以參考《[字典](#)》章節。因為對字典進行收縮的時機是由使用字典的程序決定的，所以 Redis 使用 `redis.c/tryResizeHashTables` 函數來檢查數據庫所使用的字典是否需要進行收縮：每次 `redis.c/serverCron` 函數運行的時候，這個函數都會被調用。 `tryResizeHashTables` 函數的完整定義如下： ~~~ /* * 對服務器中的所有數據庫鍵空間字典、以及過期時間字典進行檢查， * 看是否需要對這些字典進行收縮。 * * 如果字典的使用空間比率低于 REDIS_HT_MINFILL * 那么將字典的大小縮小，讓 USED/BUCKETS 的比率 <= 1 */ void tryResizeHashTables(void) { int j; for (j = 0; j < server.dbnum; j++) { // 縮小鍵空間字典 if (htNeedsResize(server.db[j].dict)) dictResize(server.db[j].dict); // 縮小過期時間字典 if (htNeedsResize(server.db[j].expires)) dictResize(server.db[j].expires); } } ~~~ ### 小結 - 數據庫主要由 `dict` 和 `expires` 兩個字典構成，其中 `dict` 保存鍵值對，而 `expires` 則保存鍵的過期時間。 - 數據庫的鍵總是一個字符串對象，而值可以是任意一種 Redis 數據類型，包括字符串、哈希、集合、列表和有序集。 - `expires` 的某個鍵和 `dict` 的某個鍵共同指向同一個字符串對象，而 `expires` 鍵的值則是該鍵以毫秒計算的 UNIX 過期時間戳。 - Redis 使用惰性刪除和定期刪除兩種策略來刪除過期的鍵。 - 更新后的 RDB 文件和重寫后的 AOF 文件都不會保留已經過期的鍵。 - 當一個過期鍵被刪除之后，程序會追加一條新的 `DEL` 命令到現有 AOF 文件末尾。 - 當主節點刪除一個過期鍵之后，它會顯式地發送一條 `DEL` 命令到所有附屬節點。 - 附屬節點即使發現過期鍵，也不會自作主張地刪除它，而是等待主節點發來 `DEL` 命令，這樣可以保證主節點和附屬節點的數據總是一致的。 - 數據庫的 `dict` 字典和 `expires` 字典的擴展策略和普通字典一樣。它們的收縮策略是：當節點的填充百分比不足 10% 時，將可用節點數量減少至大于等于當前已用節點數量。