Redisbook學習筆記（3）資料類型之清單

REDIS_LIST （清單） 是LPUSH 、LRANGE 等指令的操作對象， 它使用

REDIS_ENCODING_ZIPLIST 和REDIS_ENCODING_LINKEDLIST 這兩種方式編碼：

<a href="http://s3.51cto.com/wyfs02/M02/12/77/wKioL1MITs2QL2gQAACErY08a4I028.jpg" target="_blank"></a>

編碼的選擇

建立新清單時Redis 預設使用REDIS_ENCODING_ZIPLIST 編碼，當以下任意一個條件被滿足

時，清單會被轉換成REDIS_ENCODING_LINKEDLIST 編碼：

試圖往清單新添加一個字元串值， 且這個字元串的長度超過

server.list_max_ziplist_value （預設值為64 ）。

ziplist 包含的節點超過server.list_max_ziplist_entries （預設值為512 ）。

清單指令的實作

因為兩種底層實作的抽象方式和清單的抽象方式非常接近，是以清單指令幾乎就是通過一對一

地映射到底層資料結構的操作來實作的。

我們将焦點放在BLPOP 、BRPOP 和BRPOPLPUSH 這個幾個阻塞指令的實作原理上。

阻塞的條件

BLPOP 、BRPOP 和BRPOPLPUSH 三個指令都可能造成用戶端被阻塞，以下将這些指令統

稱為清單的阻塞原語。

阻塞原語并不是一定會造成用戶端阻塞：

隻有當這些指令被用于空清單時，它們才會阻塞用戶端。

如果被處理的清單不為空的話，它們就執行無阻塞版本的LPOP 、RPOP 或RPOPLPUSH

指令。

作為例子，以下流程圖展示了BLPOP 決定是否對用戶端進行阻塞過程：

<a href="http://s3.51cto.com/wyfs02/M00/12/77/wKioL1MITxuS-8G0AADG24Rbqgo857.jpg" target="_blank"></a>

阻塞

當一個阻塞原語的處理目标為空鍵時，執行該阻塞原語的用戶端就會被阻塞。

阻塞一個用戶端需要執行以下步驟：

1. 将用戶端的狀态設為“正在阻塞” ，并記錄阻塞這個用戶端的各個鍵，以及阻塞的最長時限

（timeout）等資料。

2. 将用戶端的資訊記錄到server.db[i]-&gt;blocking_keys 中（其中i 為用戶端所使用的數

據庫号碼）。

3. 繼續維持用戶端和伺服器之間的網絡連接配接，但不再向用戶端傳送任何資訊，造成用戶端

阻塞。

步驟2 是将來解除阻塞的關鍵，server.db[i]-&gt;blocking_keys 是一個字典，字典的鍵是那

些造成用戶端阻塞的鍵，而字典的值是一個連結清單，連結清單裡儲存了所有因為這個鍵而被阻塞的客

戶端（被同一個鍵所阻塞的用戶端可能不止一個）：

<a href="http://s3.51cto.com/wyfs02/M02/12/77/wKiom1MIT2aySd1_AAClIHH4ifM237.jpg" target="_blank"></a>

在上圖展示的blocking_keys 例子中，client2 、client5 和client1 三個用戶端就正被

key1 阻塞，而其他幾個用戶端也正在被别的兩個key 阻塞。

當用戶端被阻塞之後，脫離阻塞狀态有以下三種方法：

1. 被動脫離：有其他用戶端為造成阻塞的鍵推入了新元素。

2. 主動脫離：到達執行阻塞原語時設定的最大阻塞時間。

3. 強制脫離：用戶端強制終止和伺服器的連接配接，或者伺服器停機。

以下内容将分别介紹被動脫離和主動脫離的實作方式。

阻塞因LPUSH 、RPUSH 、LINSERT 等添加指令而被取消

通過将新元素推入造成用戶端阻塞的某個鍵中，可以讓相應的用戶端從阻塞狀态中脫離出來

（取消阻塞的用戶端數量取決于推入元素的數量）。

LPUSH 、RPUSH 和LINSERT 這三個添加新元素到清單的指令， 在底層都由一個

pushGenericCommand 的函數實作，這個函數的運作流程如下圖：

<a href="http://s3.51cto.com/wyfs02/M01/12/77/wKioL1MIT5agg5ZJAAFkgli-0eE983.jpg" target="_blank"></a>

當向一個空鍵推入新元素時，pushGenericCommand 函數執行以下兩件事：

1. 檢查這個鍵是否存在于前面提到的server.db[i]-&gt;blocking_keys 字典裡，如果是的

話，那麼說明有至少一個用戶端因為這個key 而被阻塞，程式會為這個鍵建立一個

redis.h/readyList 結構，并将它添加到server.ready_keys 連結清單中。

2. 将給定的值添加到清單鍵中。

readyList 結構的定義如下：

1

2

3

4

<code>typedef</code> <code>struct</code> <code>readyList {</code>

<code>redisDb *db;</code>

<code>robj *key;</code>

<code>} readyList;</code>

readyList 結構的key 屬性指向造成阻塞的鍵，而db 則指向該鍵所在的資料庫。

舉個例子，假設某個非阻塞用戶端正在使用0 号資料庫，而這個資料庫目前的blocking_keys

屬性的值如下：

<a href="http://s3.51cto.com/wyfs02/M02/12/77/wKioL1MIT_Hwx0q9AACa453oTDI826.jpg" target="_blank"></a>

如果這時用戶端對該資料庫執行PUSH key3 value ，那麼pushGenericCommand 将建立一個

db 屬性指向0 号資料庫、key 屬性指向key3 鍵對象的readyList 結構，并将它添加到伺服器

server.ready_keys 屬性的連結清單中：

<a href="http://s3.51cto.com/wyfs02/M01/12/77/wKiom1MIUDTRmqrEAACEjWBbm8A032.jpg" target="_blank"></a>

在我們這個例子中，到目前為止，pushGenericCommand 函數完成了以下兩件事：

1. 将readyList 添加到伺服器。

2. 将新元素value 添加到鍵key3 。

雖然key3 已經不再是空鍵，但到目前為止，被key3 阻塞的用戶端還沒有任何一個被解除阻塞

狀态。

為了做到這一點，Redis 的主程序在執行完pushGenericCommand 函數之後，會繼續調用

handleClientsBlockedOnLists 函數，這個函數執行以下操作：

1. 如果server.ready_keys 不為空， 那麼彈出該連結清單的表頭元素， 并取出元素中的

readyList 值。

2. 根據readyList 值所儲存的key 和db ，在server.blocking_keys 中查找所有因為key

而被阻塞的用戶端（以連結清單的形式儲存）。

3. 如果key 不為空，那麼從key 中彈出一個元素，并彈出用戶端連結清單的第一個用戶端，然

後将被彈出元素傳回給被彈出用戶端作為阻塞原語的傳回值。

4. 根據readyList 結構的屬性，删除server.blocking_keys 中相應的用戶端資料，取消

用戶端的阻塞狀态。

5. 繼續執行步驟3 和4 ，直到key 沒有元素可彈出，或者所有因為key 而阻塞的用戶端都

取消阻塞為止。

6. 繼續執行步驟1 ，直到ready_keys 連結清單裡的所有readyList 結構都被處理完為止。

用一段僞代碼描述以上操作可能會更直覺一些：

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

<code>def handleClientsBlockedOnLists():</code>

<code># 執行直到ready_keys 為空</code>

<code>while</code> <code>server.ready_keys != NULL:</code>

<code># 彈對外連結表中的第一個readyList</code>

<code>rl = server.ready_keys.pop_first_node()</code>

<code># 周遊所有因為這個鍵而被阻塞的用戶端</code>

<code>for</code> <code>client in all_client_blocking_by_key(rl.key, rl.db):</code>

<code># 隻要還有用戶端被這個鍵阻塞，就一直從鍵中彈出元素</code>

<code># 如果被阻塞用戶端執行的是BLPOP ，那麼對鍵執行LPOP</code>

<code># 如果執行的是BRPOP ，那麼對鍵執行RPOP</code>

<code>element = rl.key.pop_element()</code>

<code>if</code> <code>element == NULL:</code>

<code># 鍵為空，跳出for 循環</code>

<code># 餘下的未解除阻塞的用戶端隻能等待下次新元素的進入了</code>

<code>break</code>

<code>else</code><code>:#</code>

<code>清除用戶端的阻塞資訊</code>

<code>server.blocking_keys.remove_blocking_info(client)</code>

<code># 将元素傳回給用戶端，脫離阻塞狀态</code>

<code>client.reply_list_item(element)</code>

先阻塞先服務（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 依然處于

阻塞狀态：

<a href="http://s3.51cto.com/wyfs02/M00/12/77/wKioL1MIUM_QyeHRAACpMpSE3CI368.jpg" target="_blank"></a>

阻塞因超過最大等待時間而被取消

前面提到過，當用戶端被阻塞時，所有造成它阻塞的鍵，以及阻塞的最長時限會被記錄在客戶

端裡面，并且該用戶端的狀态會被設定為“正在阻塞” 。

每次Redis 伺服器正常操作函數（server cron job）執行時，程式都會檢查所有連接配接到伺服器

的用戶端，檢視那些處于“正在阻塞”狀态的用戶端的最大阻塞時限是否已經過期，如果是的話，

就給用戶端傳回一個空白回複，然後撤銷對用戶端的阻塞。

可以用一段僞代碼來描述這個過程：

<code>def server_cron_job():</code>

<code># 其他操作...</code>

<code># 周遊所有已連接配接用戶端</code>

<code>for</code> <code>client in server.all_connected_client:</code>

<code># 如果用戶端狀态為“正在阻塞”，并且最大阻塞時限已到達</code>

<code>if</code> <code>client.state == BLOCKING and \</code>

<code>client.max_blocking_timestamp &lt; current_timestamp():</code>

<code># 那麼給用戶端發送空回複, 脫離阻塞狀态</code>

<code>client.send_empty_reply()</code>

<code># 并清除用戶端在伺服器上的阻塞資訊</code>

<code></code>

本文轉自shayang8851CTO部落格，原文連結：http://blog.51cto.com/janephp/1362056，如需轉載請自行聯系原作者