關於ZipList和Redis的實現

ziplist是一個經過特殊編碼的雙向鍊表，它的設計目標就是為了提高存儲效率，本文對其進行一定的分析。

什麼是ziplist

Redis官方對於ziplist的定義是（出自ziplist.c的文件頭部注釋）：

The ziplist is a specially encoded dually linked list that is designed to be very memory efficient. It stores both strings and integer values, where integers are encoded as actual integers instead of a series of characters. It allows push and pop operations on either side of the list in O(1) time.

即，ziplist是一個經過特殊編碼的雙向鍊表，它的設計目標就是為了提高存儲效率。ziplist可以用於存儲字符串或整數，其中整數是按真正的二進位表示進行編碼的，而不是編碼成字符串序列。它能以O (1)的時間複雜度在表的兩端提供push和pop操作。

實際上，ziplist充分體現了Redis對於存儲效率的追求。一個普通的雙向鍊表，鍊表中每一項都占用獨立的一塊內存，各項之間用地址指針（或引用）連接起來。這種方式會帶來大量的內存碎片，而且地址指針也會占用額外的內存。而ziplist卻是將表中每一項存放在前後連續的地址空間內，一個ziplist整體占用一大塊內存。它是一個表（list），但其實不是一個鍊表（linked list）。

ziplist的數據結構定義

• : 32bit，表示ziplist占用的位元組總數（也包括 本身占用的4個位元組）。
• : 32bit，表示ziplist表中最後一項（entry）在ziplist中的偏移位元組數。 的存在，使得我們可以很方便地找到最後一項（不用遍歷整個ziplist ），從而可以在ziplist尾端快速地執行push或pop操作。
• : 16bit， 表示ziplist中數據項（entry）的個數。zllen欄位因為只有16bit，所以可以表達的最大值為2^16-1。這裡需要特別注意的是，如果ziplist 中數據項個數超過了16bit能表達的最大值，ziplist仍然可以來表示。那怎麼表示呢？這裡做了這樣的規定：如果 小於等於2^16-2（也就是不等於2^16-1），那麼 就表示ziplist中數據項的個數；否則，也就是 等於16bit全為1的情況，那麼 就不表示數據項個數了，這時候要想知道ziplist中數據項總數，那麼必須對ziplist從頭到尾遍歷各個數據項，才能計數出來。
• : 表示真正存放數據的數據項，長度不定。一個數據項（entry）也有它自己的內部結構，這個稍後再解釋。
• : ziplist最後1個位元組，是一個結束標記，值固定等於255。

上面的定義中還值得注意的一點是： , , 既然占據多個位元組，那麼在存儲的時候就有大端（big endian）和小端（little endian）的區別。ziplist採取的是小端模式來存儲。在解析多個位元組序列時需要特別注意調換順序。

為什麼最後一個值固定為255呢？

這是因為：255已經定義為ziplist結束標記 的值了。在ziplist的很多操作的實現中，都會根據數據項的第1個位元組是不是255來判斷當前是不是到達ziplist的結尾了，因此一個正常的數據的第1個位元組（也就是 的第1個位元組）是不能夠取255這個值的，否則就衝突了。

ziplist entry

pre_entry_length

根據編碼方式的不同， pre_entry_length 域可能占用 1 位元組或者 5 位元組：

• 1 位元組：如果前一節點的長度小於 254 位元組，便使用一個位元組保存它的值。
• 5 位元組：如果前一節點的長度大於等於 254 位元組，那麼將第 1 個位元組的值設為 254 ，然後用接下來的 4 個位元組保存實際長度。

encoding 和 length

encoding 和 length 兩部分一起決定了 content 部分所保存的數據的類型（以及長度）。

其中， encoding 域的長度為兩個 bit ， 它的值可以是 00 、 01 、 10 和 11 ：

• 00 、 01 和 10 表示 content 部分保存著字符數組。
• 11 表示 content 部分保存著整數。

content

content 部分保存著節點的內容，類型和長度由 encoding 和 length 決定。 先分析前兩個bit的值，對應到具體的數據類型，然後再根據上表分析後面的內容的真實長度。

例子

這個例子來自 zhangtielei ：

上圖是一份真實的ziplist數據。我們逐項解讀一下：

• 這個ziplist一共包含33個位元組。位元組編號從byte[0]到byte[32]。圖中每個位元組的值使用16進位表示。
• 頭4個位元組（0x21000000）是按小端（little endian）模式存儲的 欄位。什麼是小端呢？就是指數據的低位元組保存在內存的低地址中（參見維基百科詞條Endianness）。因此，這裡 的值應該解析成0x00000021，用十進位表示正好就是33。
• 接下來4個位元組（byte[4..7]）是 ，用小端存儲模式來解釋，它的值是0x0000001D（值為29），表示最後一個數據項在byte[29]的位置（那個數據項為0x05FE14）。
• 再接下來2個位元組（byte[8..9]），值為0x0004，表示這個ziplist里一共存有4項數據。
• 接下來6個位元組（byte[10..15]）是第1個數據項。其中，prevrawlen=0，因為它前面沒有數據項；len=4，即0x04，相當於前面定義的9種情況中的第1種，表示後面4 個位元組按字符串存儲數據，數據的值為」name」。
• 接下來8個位元組（byte[16..23]）是第2個數據項，與前面數據項存儲格式類似，存儲1個字符串」tielei」。
• 接下來5個位元組（byte[24..28]）是第3個數據項，與前面數據項存儲格式類似，存儲1個字符串」age」。
• 接下來3個位元組（byte[29..31]）是最後一個數據項，它的格式與前面的數據項存儲格式不太一樣。其中，第1個位元組prevrawlen=5，表示前一個數據項占用5個位元組；第2個位元組=0xFE ，相當於前面定義的9種情況中的第8種，所以後面還有1個位元組用來表示真正的數據，並且以整數表示。它的值是20（0x14）。
• 最後1個位元組（byte[32]）表示 ，是固定的值255（0xFF）。

總結一下，這個ziplist里存了4個數據項，分別為：

• 字符串: 「name」
• 字符串: 「tielei」
• 字符串: 「age」
• 整數: 20

注意：這個ziplist是通過兩個 hset 命令創建出來的：

hset myinfo name tielei
hset myinfo age 20

hash與ziplist

hash是Redis中可以用來存儲一個對象結構的比較理想的數據類型。一個對象的各個屬性，正好對應一個hash結構的各個field。

我們在網上很容易找到這樣一些技術文章，它們會說存儲一個對象，使用hash比string要節省內存。實際上這麼說是有前提的，具體取決於對象怎麼來存儲。如果你把對象的多個屬性存儲到多個key上（各個屬性值存成string），當然占的內存要多。但如果你採用一些序列化方法，比如Protocol Buffers，或者Apache Thrift，先把對象序列化為位元組數組，然後再存入到Redis的string中，那麼跟hash相比，哪一種更省內存，就不一定了。

當然，hash比序列化後再存入string的方式，在支持的操作命令上，還是有優勢的：它既支持多個field同時存取（hmset/hmget），也支持按照某個特定的field單獨存取（hset/hget）。

實際上，hash隨著數據的增大，其底層數據結構的實現是會發生變化的，當然存儲效率也就不同。在field比較少，各個value值也比較小的時候，hash採用ziplist來實現；而隨著field增多和value值增大，hash可能會變成dict來實現。當hash底層變成dict來實現的時候，它的存儲效率就沒法跟那些序列化方式相比了。

當我們為某個key第一次執行 hset key field value 命令的時候，Redis會創建一個hash結構，這個新創建的hash底層就是一個ziplist。

當隨著數據的插入，hash底層的這個ziplist就可能會轉成dict。那麼到底插入多少才會轉呢？

hash-max-ziplist-entries 512
hash-max-ziplist-value 64

這個配置的意思是說，在如下兩個條件之一滿足的時候，ziplist會轉成dict：

• 當hash中的數據項（即field-value對）的數目超過512的時候，也就是ziplist數據項超過1024的時候（請參考t_hash.c中的hashTypeSet函數）。
• 當hash中插入的任意一個value的長度超過了64的時候（請參考t_hash.c中的hashTypeTryConversion函數）。

Redis的hash之所以這樣設計，是因為當ziplist變得很大的時候，它有如下幾個缺點：

• 每次插入或修改引發的realloc操作會有更大的機率造成內存拷貝，從而降低性能。
• 一旦發生內存拷貝，內存拷貝的成本也相應增加，因為要拷貝更大的一塊數據。
• 當ziplist數據項過多的時候，在它上面查找指定的數據項就會性能變得很低，因為ziplist上的查找需要進行遍歷。

API和時間複雜度