列表 · Redis 設計與實現（第一版）

# 列表 [TOC=2,3] `REDIS_LIST` （列表）是 [LPUSH](http://redis.readthedocs.org/en/latest/list/lpush.html#lpush "(in Redis 命令參考 v2.8)") 、 [LRANGE](http://redis.readthedocs.org/en/latest/list/lrange.html#lrange "(in Redis 命令參考 v2.8)") 等命令的操作對象，它使用 `REDIS_ENCODING_ZIPLIST` 和 `REDIS_ENCODING_LINKEDLIST` 這兩種方式編碼： ![digraph redis_list { node[shape=plaintext, style = filled]; edge [style = bold]; // type REDIS_LIST [label="列表\nREDIS_LIST", fillcolor = "#95BBE3"]; // encoding REDIS_ENCODING_ZIPLIST [label="壓縮列表\nREDIS_ENCODING_ZIPLIST", fillcolor = "#FADCAD"]; REDIS_ENCODING_LINKEDLIST [label="雙端鏈表\nREDIS_ENCODING_LINKEDLIST", fillcolor = "#FADCAD"]; // edge REDIS_LIST -> REDIS_ENCODING_LINKEDLIST; REDIS_LIST -> REDIS_ENCODING_ZIPLIST; REDIS_ENCODING_LINKEDLIST -> list; REDIS_ENCODING_ZIPLIST -> ziplist; // datastruct 1 list [label="adlist.h/list"]; // datastruct 2 ziplist [label="ziplist"];}](https://box.kancloud.cn/2015-09-13_55f4effc92abf.svg) ### 編碼的選擇創建新列表時 Redis 默認使用 `REDIS_ENCODING_ZIPLIST` 編碼，當以下任意一個條件被滿足時，列表會被轉換成 `REDIS_ENCODING_LINKEDLIST` 編碼： - 試圖往列表新添加一個字符串值，且這個字符串的長度超過 `server.list_max_ziplist_value` （默認值為 `64` ）。 - `ziplist` 包含的節點超過 `server.list_max_ziplist_entries` （默認值為 `512` ）。 ### 列表命令的實現因為兩種底層實現的抽象方式和列表的抽象方式非常接近，所以列表命令幾乎就是通過一對一地映射到底層數據結構的操作來實現的。既然這些映射都非常直觀，這里就不做贅述了，在以下的內容中，我們將焦點放在 [BLPOP](http://redis.readthedocs.org/en/latest/list/blpop.html#blpop "(in Redis 命令參考 v2.8)") 、 [BRPOP](http://redis.readthedocs.org/en/latest/list/brpop.html#brpop "(in Redis 命令參考 v2.8)") 和 [BRPOPLPUSH](http://redis.readthedocs.org/en/latest/list/brpoplpush.html#brpoplpush "(in Redis 命令參考 v2.8)") 這個幾個阻塞命令的實現原理上。 ### 阻塞的條件 [BLPOP](http://redis.readthedocs.org/en/latest/list/blpop.html#blpop "(in Redis 命令參考 v2.8)") 、 [BRPOP](http://redis.readthedocs.org/en/latest/list/brpop.html#brpop "(in Redis 命令參考 v2.8)") 和 [BRPOPLPUSH](http://redis.readthedocs.org/en/latest/list/brpoplpush.html#brpoplpush "(in Redis 命令參考 v2.8)") lpush] 三個命令都可能造成客戶端被阻塞，以下將這些命令統稱為列表的阻塞原語。阻塞原語并不是一定會造成客戶端阻塞： - 只有當這些命令被用于空列表時，它們才會阻塞客戶端。 - 如果被處理的列表不為空的話，它們就執行無阻塞版本的 [LPOP](http://redis.readthedocs.org/en/latest/list/lpop.html#lpop "(in Redis 命令參考 v2.8)") 、 [RPOP](http://redis.readthedocs.org/en/latest/list/rpop.html#rpop "(in Redis 命令參考 v2.8)") 或 [RPOPLPUSH](http://redis.readthedocs.org/en/latest/list/rpoplpush.html#rpoplpush "(in Redis 命令參考 v2.8)") 命令。作為例子，以下流程圖展示了 [BLPOP](http://redis.readthedocs.org/en/latest/list/blpop.html#blpop "(in Redis 命令參考 v2.8)") 決定是否對客戶端進行阻塞過程： ![digraph blpop_decide_block_or_not { node [shape=plaintext, style = filled]; edge [style = bold]; // call_blpop [label = "BLPOP key", fillcolor = "#A8E270"]; wrong_type_or_not [label = "key 非空且不是列表？", shape = diamond, fillcolor = "#95BBE3"]; return_wrong_type [label = "返回類型錯誤"]; key_empty_or_not [label = "key 是否為空?", shape = diamond, fillcolor = "#95BBE3"]; block_client [label = "阻塞客戶端"]; lpop [label = "執行 LPOP key 命令", fillcolor = "#A8E270"]; // call_blpop -> wrong_type_or_not; wrong_type_or_not -> return_wrong_type [label = "是"]; wrong_type_or_not -> key_empty_or_not [label = "否"]; key_empty_or_not -> block_client [label = "是"]; key_empty_or_not -> lpop [label = "否"];}](https://box.kancloud.cn/2015-09-13_55f4effc9a74c.svg) ### 阻塞當一個阻塞原語的處理目標為空鍵時，執行該阻塞原語的客戶端就會被阻塞。阻塞一個客戶端需要執行以下步驟： 1. 將客戶端的狀態設為“正在阻塞”，并記錄阻塞這個客戶端的各個鍵，以及阻塞的最長時限（timeout）等數據。 1. 將客戶端的信息記錄到 `server.db[i]->blocking_keys` 中（其中 `i` 為客戶端所使用的數據庫號碼）。 1. 繼續維持客戶端和服務器之間的網絡連接，但不再向客戶端傳送任何信息，造成客戶端阻塞。步驟 2 是將來解除阻塞的關鍵，`server.db[i]->blocking_keys` 是一個字典，字典的鍵是那些造成客戶端阻塞的鍵，而字典的值是一個鏈表，鏈表里保存了所有因為這個鍵而被阻塞的客戶端（被同一個鍵所阻塞的客戶端可能不止一個）： ![digraph db_blocking_keys { rankdir = LR; node [shape = record, style = filled]; edge [style = bold]; // keys blocking_keys [label = "blocking_keys |<key1> key1 |<key2> key2 |<key3> key3 | ... |<keyN> keyN", fillcolor = "#A8E270"]; // clients blocking for key1 client1 [label = "client1", fillcolor = "#95BBE3"]; client5 [label = "client5", fillcolor = "#95BBE3"]; client2 [label = "client2", fillcolor = "#95BBE3"]; null_1 [label = "NULL", shape=plaintext]; blocking_keys:key1 -> client2; client2 -> client5; client5 -> client1; client1 -> null_1; // clients blocking for key2 client7 [label = "client7", fillcolor = "#95BBE3"]; null_2 [label = "NULL", shape=plaintext]; blocking_keys:key2 -> client7; client7 -> null_2; // key3 client3 [label = "client3", fillcolor = "#95BBE3"]; client4 [label = "client4", fillcolor = "#95BBE3"]; client6 [label = "client6", fillcolor = "#95BBE3"]; null_3 [label = "NULL", shape=plaintext]; blocking_keys:key3 -> client3; client3 -> client4; client4 -> client6; client6 -> null_3;}](https://box.kancloud.cn/2015-09-13_55f4effca597c.svg) 在上圖展示的 `blocking_keys` 例子中， `client2` 、 `client5` 和 `client1` 三個客戶端就正被 `key1` 阻塞，而其他幾個客戶端也正在被別的兩個 key 阻塞。當客戶端被阻塞之后，脫離阻塞狀態有以下三種方法： 1. 被動脫離：有其他客戶端為造成阻塞的鍵推入了新元素。 1. 主動脫離：到達執行阻塞原語時設定的最大阻塞時間。 1. 強制脫離：客戶端強制終止和服務器的連接，或者服務器停機。以下內容將分別介紹被動脫離和主動脫離的實現方式。 ### 阻塞因 LPUSH 、 RPUSH 、 LINSERT 等添加命令而被取消通過將新元素推入造成客戶端阻塞的某個鍵中，可以讓相應的客戶端從阻塞狀態中脫離出來（取消阻塞的客戶端數量取決于推入元素的數量）。 [LPUSH](http://redis.readthedocs.org/en/latest/list/lpush.html#lpush "(in Redis 命令參考 v2.8)") 、 [RPUSH](http://redis.readthedocs.org/en/latest/list/rpush.html#rpush "(in Redis 命令參考 v2.8)") 和 [LINSERT](http://redis.readthedocs.org/en/latest/list/linsert.html#linsert "(in Redis 命令參考 v2.8)") 這三個添加新元素到列表的命令，在底層都由一個 `pushGenericCommand` 的函數實現，這個函數的運作流程如下圖： ![digraph push_generic_command { node [shape = plaintext, style = filled]; edge [style = bold]; /* lpush [label = "LPUSH key value [value ...]"]; rpush [label = "RPUSH key value [value ...]"]; linsert [label = "LINSERT key BEFORE\|AFTER pivot value"]; */ pushGenericCommand [label = "pushGenericCommand", fillcolor = "#A8E270"]; key_wrong_type_or_not [label = "key 非空且不是列表？", shape = diamond, fillcolor = "#95BBE3"]; return_wrong_type_error [label = "返回類型錯誤"]; key_empty_or_not [label = "key 為空？", shape = diamond, fillcolor = "#95BBE3"]; // call_signal_list_as_ready [label = "調用 signalListAsReady"]; add_key_to_ready_list_if_need [label = "如果 key 存在于 server.db[i]-\>blocking_keys\n那么為 key 創建一個 readyList 結構\n并將它添加到 server.ready_keys 鏈表中"]; push_value_to_list [label = "將輸入值推入列表"]; /* lpush -> pushGenericCommand; rpush -> pushGenericCommand; linsert -> pushGenericCommand; */ pushGenericCommand -> key_wrong_type_or_not; key_wrong_type_or_not -> return_wrong_type_error [label = "是"]; key_wrong_type_or_not -> key_empty_or_not [label = "否"]; // key_empty_or_not -> call_signal_list_as_ready [label = "是"]; // call_signal_list_as_ready -> add_key_to_ready_list_if_need; key_empty_or_not -> add_key_to_ready_list_if_need [label = "是"]; key_empty_or_not -> push_value_to_list [label = "否"]; add_key_to_ready_list_if_need -> push_value_to_list;}](https://box.kancloud.cn/2015-09-13_55f4effcb0651.svg) 當向一個空鍵推入新元素時，`pushGenericCommand` 函數執行以下兩件事： 1. 檢查這個鍵是否存在于前面提到的 `server.db[i]->blocking_keys` 字典里，如果是的話，那么說明有至少一個客戶端因為這個 key 而被阻塞，程序會為這個鍵創建一個 `redis.h/readyList` 結構，并將它添加到 `server.ready_keys` 鏈表中。 1. 將給定的值添加到列表鍵中。 `readyList` 結構的定義如下： ~~~ typedef struct readyList { redisDb *db; robj *key; } readyList; ~~~ `readyList` 結構的 `key` 屬性指向造成阻塞的鍵，而 `db` 則指向該鍵所在的數據庫。舉個例子，假設某個非阻塞客戶端正在使用 `0` 號數據庫，而這個數據庫當前的 `blocking_keys` 屬性的值如下： ![digraph db_blocking_keys { rankdir = LR; node [shape = record, style = filled]; edge [style = bold]; // keys blocking_keys [label = "blocking_keys |<key1> key1 |<key2> key2 |<key3> key3 | ... |<keyN> keyN", fillcolor = "#A8E270"]; // clients blocking for key1 client1 [label = "client1", fillcolor = "#95BBE3"]; client5 [label = "client5", fillcolor = "#95BBE3"]; client2 [label = "client2", fillcolor = "#95BBE3"]; null_1 [label = "NULL", shape=plaintext]; blocking_keys:key1 -> client2; client2 -> client5; client5 -> client1; client1 -> null_1; // clients blocking for key2 client7 [label = "client7", fillcolor = "#95BBE3"]; null_2 [label = "NULL", shape=plaintext]; blocking_keys:key2 -> client7; client7 -> null_2; // key3 client3 [label = "client3", fillcolor = "#95BBE3"]; client4 [label = "client4", fillcolor = "#95BBE3"]; client6 [label = "client6", fillcolor = "#95BBE3"]; null_3 [label = "NULL", shape=plaintext]; blocking_keys:key3 -> client3; client3 -> client4; client4 -> client6; client6 -> null_3;}](https://box.kancloud.cn/2015-09-13_55f4effcba8ec.svg) 如果這時客戶端對該數據庫執行 `PUSH key3 value` ，那么 `pushGenericCommand` 將創建一個 `db` 屬性指向 `0` 號數據庫、`key` 屬性指向 `key3` 鍵對象的 `readyList` 結構，并將它添加到服務器 `server.ready_keys` 屬性的鏈表中： ![digraph update_ready_keys { rankdir = LR; node [shape = record, style = filled]; edge [style = bold]; redisServer [label = "redisServer | ... |<ready_keys> ready_keys | ...", fillcolor = "#A8E270"]; readyList [label = "<head>readyList |<db> db |<key> key", fillcolor = "#95BBE3"]; listNode [label = "<head>listNode |{<prev> prev |<next> next |<value> value} ", fillcolor = "#FADCAD"]; null [label = "NULL", shape = plaintext]; redisServer:ready_keys -> listNode:head [label = "list"]; listNode:next -> null; listNode:prev -> null; listNode:value -> readyList:head; redisDb [label = "<head> redisDb | ... |<dict> dict | ...", fillcolor = "#FFC1C1"]; readyList:db -> redisDb:head; dict [label = "<head>dict\n(key space of DB) | ... |<key3> key3 | ...", fillcolor = "#F2F2F2"]; redisDb:dict -> dict:head; readyList:key -> dict:key3;}](https://box.kancloud.cn/2015-09-13_55f4effcc1d7d.svg) 在我們這個例子中，到目前為止，`pushGenericCommand` 函數完成了以下兩件事： 1. 將 `readyList` 添加到服務器。 1. 將新元素 `value` 添加到鍵 `key3` 。雖然 `key3` 已經不再是空鍵，但到目前為止，被 `key3` 阻塞的客戶端還沒有任何一個被解除阻塞狀態。為了做到這一點，Redis 的主進程在執行完 `pushGenericCommand` 函數之后，會繼續調用 `handleClientsBlockedOnLists` 函數，這個函數執行以下操作： 1. 如果 `server.ready_keys` 不為空，那么彈出該鏈表的表頭元素，并取出元素中的 `readyList` 值。 1. 根據 `readyList` 值所保存的 `key` 和 `db` ，在 `server.blocking_keys` 中查找所有因為 `key` 而被阻塞的客戶端（以鏈表的形式保存）。 1. 如果 `key` 不為空，那么從 `key` 中彈出一個元素，并彈出客戶端鏈表的第一個客戶端，然后將被彈出元素返回給被彈出客戶端作為阻塞原語的返回值。 1. 根據 `readyList` 結構的屬性，刪除 `server.blocking_keys` 中相應的客戶端數據，取消客戶端的阻塞狀態。 1. 繼續執行步驟 3 和 4 ，直到 `key` 沒有元素可彈出，或者所有因為 `key` 而阻塞的客戶端都取消阻塞為止。 1. 繼續執行步驟 1 ，直到 `ready_keys` 鏈表里的所有 `readyList` 結構都被處理完為止。用一段偽代碼描述以上操作可能會更直觀一些： ~~~ def handleClientsBlockedOnLists(): # 執行直到 ready_keys 為空 while server.ready_keys != NULL: # 彈出鏈表中的第一個 readyList rl = server.ready_keys.pop_first_node() # 遍歷所有因為這個鍵而被阻塞的客戶端 for client in all_client_blocking_by_key(rl.key, rl.db): # 只要還有客戶端被這個鍵阻塞，就一直從鍵中彈出元素 # 如果被阻塞客戶端執行的是 BLPOP ，那么對鍵執行 LPOP # 如果執行的是 BRPOP ，那么對鍵執行 RPOP element = rl.key.pop_element() if element == NULL: # 鍵為空，跳出 for 循環 # 余下的未解除阻塞的客戶端只能等待下次新元素的進入了 break else: # 清除客戶端的阻塞信息 server.blocking_keys.remove_blocking_info(client) # 將元素返回給客戶端，脫離阻塞狀態 client.reply_list_item(element) ~~~ ### 先阻塞先服務（FBFS）策略值得一提的是，當程序添加一個新的被阻塞客戶端到 `server.blocking_keys` 字典的鏈表中時，它將該客戶端放在鏈表的最后，而當 `handleClientsBlockedOnLists` 取消客戶端的阻塞時，它從鏈表的最前面開始取消阻塞：這個鏈表形成了一個 FIFO 隊列，最先被阻塞的客戶端總是最先脫離阻塞狀態，Redis 文檔稱這種模式為先阻塞先服務（FBFS，first-block-first-serve）。舉個例子，在下圖所示的阻塞狀況中，如果客戶端對數據庫執行 `PUSH key3 value` ，那么只有 `client3` 會被取消阻塞，`client6` 和 `client4` 仍然阻塞；如果客戶端對數據庫執行 `PUSH key3 value1 value2` ，那么 `client3` 和 `client4` 的阻塞都會被取消，而客戶端 `client6` 依然處于阻塞狀態： ![digraph db_blocking_keys { rankdir = LR; node [shape = record, style = filled]; edge [style = bold]; // keys blocking_keys [label = "blocking_keys |<key1> key1 |<key2> key2 |<key3> key3 | ... |<keyN> keyN", fillcolor = "#A8E270"]; // clients blocking for key1 client1 [label = "client1", fillcolor = "#95BBE3"]; client5 [label = "client5", fillcolor = "#95BBE3"]; client2 [label = "client2", fillcolor = "#95BBE3"]; null_1 [label = "NULL", shape=plaintext]; blocking_keys:key1 -> client2; client2 -> client5; client5 -> client1; client1 -> null_1; // clients blocking for key2 client7 [label = "client7", fillcolor = "#95BBE3"]; null_2 [label = "NULL", shape=plaintext]; blocking_keys:key2 -> client7; client7 -> null_2; // key3 client3 [label = "client3", fillcolor = "#95BBE3"]; client4 [label = "client4", fillcolor = "#95BBE3"]; client6 [label = "client6", fillcolor = "#95BBE3"]; null_3 [label = "NULL", shape=plaintext]; blocking_keys:key3 -> client3; client3 -> client4; client4 -> client6; client6 -> null_3;}](https://box.kancloud.cn/2015-09-13_55f4effccc0a5.svg) ### 阻塞因超過最大等待時間而被取消前面提到過，當客戶端被阻塞時，所有造成它阻塞的鍵，以及阻塞的最長時限會被記錄在客戶端里面，并且該客戶端的狀態會被設置為“正在阻塞”。每次 Redis 服務器常規操作函數（server cron job）執行時，程序都會檢查所有連接到服務器的客戶端，查看那些處于“正在阻塞”狀態的客戶端的最大阻塞時限是否已經過期，如果是的話，就給客戶端返回一個空白回復，然后撤銷對客戶端的阻塞。可以用一段偽代碼來描述這個過程： ~~~ def server_cron_job(): # 其他操作 ... # 遍歷所有已連接客戶端 for client in server.all_connected_client: # 如果客戶端狀態為“正在阻塞”，并且最大阻塞時限已到達 if client.state == BLOCKING and \ client.max_blocking_timestamp < current_timestamp(): # 那么給客戶端發送空回復,脫離阻塞狀態 client.send_empty_reply() # 并清除客戶端在服務器上的阻塞信息 server.blocking_keys.remove_blocking_info(client) # 其他操作 ... ~~~