redis設計與實作（七）壓縮清單

壓縮清單（ziplist）是清單鍵和哈希鍵的底層實作之一。當一個清單鍵隻包含少量清單項，并且每個清單項要麼就是小整數值，要麼就是長度比較短的字元串，那麼Redis就會使用壓縮清單做清單鍵的底層實作。

例如，執行以下指令将建立一個壓縮清單實作的清單鍵：

redis>RPUSH 1st 1 3 5 10086 "hello" "world"

(integer)6

redis>OBJECT ENCODING 1st

"ziplist"

清單鍵裡面包含的都是1、3、5、10086這樣的小整數值，以及“hello”、“world”這樣的短字元串。

另外，當一個哈希鍵隻包含少量鍵值對，并且每個鍵值對的鍵和值要麼就是小整數值，要麼就是長度比較短的字元串，那麼Redis就會使用壓縮清單來做哈希鍵的底層實作。

舉個例子，執行以下指令将建立一個壓縮清單實作的哈希鍵：

redis>HMSET profile "name" "age" 28 "job" "Programmer"

OK

redis>OBJECT ENCODING profile

"ziplist"

哈希鍵裡面包含的所有鍵和值都是小整數值或短字元串。後面将對壓縮清單的定義以及相關操作進行詳細的介紹。

壓縮清單的構成

壓縮清單是Redis為了節約記憶體而開發的，是由一系列特殊編碼的連續記憶體塊組成的順序型（sequential）資料結構。一個壓縮清單可以包含任意多個節點（entry），每個節點可以儲存一個位元組數組或者一個整數值。 圖7-1展示了壓縮清單的的各個組成部分，表7-1則記錄了各個組成部分的類型、長度以及用途。

圖7-2展示了一個壓縮清單示例：

• 清單zlbytes屬性的值為0x50（十進制80），表示壓縮雷彪的總廠為80位元組。
• 裡诶報zltail屬性的值為0x3c（十進制60），這表示如果我們有一個執行壓縮清單起始位址的指針p，那麼隻要用指針p加上偏移量60，就可以計算出表尾節點entry3的位址。
• 清單zllen屬性的值為0x3（十進制3），表示壓縮清單包含三個節點。

• 清單zlbytes熟悉你給的值為0xd2（十進制210），表示壓縮清單的總長為210位元組。
• 清單zltail屬性的值為0xb3（179），這表示如果我們有一個指向壓縮雷彪起始位址的指針p，那麼隻要用指針p加上偏移量179，就可以計算出表尾節點entry5的位址。
• 清單zllen屬性的值為0x5（十進制5），表示壓縮清單包含五個節點。

壓縮清單節點的構成

每個壓縮清單節點可以儲存一個位元組數組或者一個整數值，其中，位元組數組可以是以下三種長度的其中一種：

• 長度小于等于63（2的6次方-1）位元組的位元組數組。
• 長度小于等于16383（2的14次方-1）位元組的位元組數組。
• 長度小于等于4294967295（2的32次方-1）位元組的位元組數組。

而整數值則可以是以下六種長度的其中一種：

• 4位長，介于0到12之間的無符号整數
• 1位元組長的有符号整數
• 3位元組長的有符号整數
• int16_t類型整數
• int32_t類型整數
• int64_t類型整數。

每個壓縮清單節點都由previous_entry_length、encoding、content三個部分組成，如圖7-4所示。接下來的内容将分别介紹這三個組成部分。

previous_entry_length

節點的privious_entry_length屬性以位元組為機關，記錄了壓縮清單中前一個節點的長度。privious_entry_length屬性的長度可以是1位元組或者5位元組：

• 如果前一節點的長度小于254位元組，那麼privious_entry_length屬性的長度為1位元組：前一節點的長度就儲存在這一個位元組裡面。
• 如果前一節點的長度大于等于254位元組，那麼privious_entry_length屬性的長度為5位元組：其中屬性的第一位元組會被設定為0xFE（十進制254），而之後的四個位元組則用于儲存前一節點的長度。

因為節點的privious_entry_length屬性記錄了前一個節點的長度，是以程式可以通過指針運算，根據目前節點的起始位址來計算出前一個節點的起始位址。

壓縮清單從表尾向表頭節點進行周遊就是使用這一原理實作的，隻要我們擁有了一個指向就某個節點起始位址的指針，那麼通過這個之中呢以及這個節點的privious_entry_length屬性，程式就可以一直向前一個節點回溯，最終到達壓縮清單的表頭節點。 圖7-8展示了一個從表尾節點向表頭節點周遊的完整過程：

encoding 節點的encoding屬性記錄了節點的content屬性鎖儲存資料的類型以及長度：

• 一位元組、兩位元組或者五位元組長，值的最高位為00、01或者10的是位元組數組編碼：這種編碼表示節點的content屬性儲存着位元組數組，數組的長度由編碼出去最高兩位之後的其他位記錄；
• 一位元組長，值的最高位以11開頭的是整數編碼：這種編碼表示節點的content屬性儲存着整數值，整數值的類型和長度由編碼除去最高兩位之後的其它位記錄；

• 

content

節點的content屬性負責儲存節點的值，節點值可以是一個位元組數組或者整數，值的類型和長度由節點的encoding屬性決定。

• 編碼的最高兩位00表示節點儲存的是一個位元組數組；
• 編碼的後六位001011記錄了位元組數組的長度11；
• content屬性儲存着節點的值“hello world”。

連鎖更新

前面說過，每個節點的privious_entry_length屬性都記錄了前一個節點的長度：

• 如果前一節點的長度小于254位元組，那麼privious_entry_length屬性需要用1位元組長的空間來儲存這個長度值。
• 如果前一節點的長度大于等于254位元組，那麼privious_entry_length屬性需要用5位元組長的空間來儲存這個