一 介紹
用途 ziplist壓縮清單底層實作 是 list對象 與 hash對象 的底層實作之一。 當一個list對象隻需要包含少量元素，并且每個元素要麼就是小整數值，要麼就是長度比較短的字元串，那麼Redis就用ziplist來做 list對象 的底層實作。 當一個 hash對象 隻包含少量鍵值對時，并且每個鍵值對的鍵和值要麼就是小整數要麼就是長度比較短的字元串，那麼也用 ziplist 作為底層實作。
例如： rpush lst 1 3 5 'hello' object encoding lst # 是ziplist hmset profile name 'fwy' age 18 object encoding profile #是"ziplist"
ziplist 是一種為節約記憶體而開發的順序型資料結構。 ziplist 是一系列特殊編碼的連續記憶體塊，可以了解成不規則的數組，每個元素的長度是通過元素自身去記錄的。 添加新結點到ziplist，或者删除結點，都可能引起連鎖更新，但機率不高。 壓縮清單可以包含多個結點，每個結點可以儲存一個位元組數組或者整數值。
源碼 ziplist.c ziplist.h
二 資料結構
以下就是 ziplist 的記憶體結構 <zlbytes><zltail><zllen><entry><entry><zlend>
<zlbytes> 是整個ziplist 所占用的位元組數量， 一個無符号整數記錄(uint32_t)。 通過儲存這個值，可以在不周遊整個 ziplist 的前提下，對整個 ziplist 進行記憶體重配置設定。難道一個ziplist可以儲存4GB的内容?
<zltail> 是到清單中最後一個節點的偏移量(同樣為 uint32_t)。 有了這個偏移量，就可以在常數複雜度内對表尾進行操作，用指針加上偏移量，而不必周遊整個清單。
<zllen> 是entry的數量，為 ``uint16_t`` 。 當這個值大于 2**16-2 時，需要周遊整個清單，才能計算出清單的長度。也就是說，當節點數量小于65535時，zllen就是清單結點的數量，當節點數量大于等于65535時，那麼需要周遊才能得知數量。
<zlend> 是一個單位元組的特殊值，等于 255 ，它辨別了清單的末端。
是以我們看到，一個ziplist，不算各個entry，需要11位元組的管理開銷。
ziplist裡面的entry的結構
typedef struct zlentry { unsigned int prevrawlensize, // 儲存前一節點的長度所需的長度,機關位元組 prevrawlen; // 前一節點的長度,主要用于從後往前周遊時使用 unsigned int lensize, // 儲存節點的長度所需的長度 len; // 節點的長度 unsigned int headersize; // header 長度, 是上面的 prevrawlensize + lensize unsigned char encoding; // 編碼方式 unsigned char *p; // 内容 } zlentry;
整個entry占多少位元組呢? prevrawlensize + lensize + len
| prevrawlensize | prevrawlen | lensize | len | headersize | encoding | p |
* 前一個節點的長度的儲存方式如下： * 1) 如果節點的長度 < 254 位元組，那麼直接用一個位元組儲存這個值。 * 2) 如果節點的長度 >= 254 位元組，那麼将第一個位元組設定為 254 ， * 再在之後用 4 個位元組來表示節點的實際長度（共使用 5 個位元組）。
* 目前結點的類型與長度 * * 當節點儲存的是字元串時，第2部分的前 2 位用于訓示儲存内容長度所使用的編碼方式， * 之後跟着的是内容長度的值。 * * 當節點儲存的是整數時，header 的前 2 位都設定為 1 ， * 之後的 2 位用于訓示儲存的整數值的類型（這個類型決定了内容所占用的空間）。
三 連鎖更新
連鎖更新說的是，目前某個 entry 之前的節點 從小于254位元組，變成大于等于254位元組， 那麼目前entry 的 previous_entry_length 從1位元組變成5位元組。如果因為從1位元組變成5位元組，使自己跨越了從小于254位元組，到過了254位元組這條線，就又會引起下一個節點的擴容。 最壞的情況是：所有entry都是剛好處于250-253位元組之間，然後在連結清單頭插入一個大于等于254位元組的entry，此時會觸發全鍊連鎖更新。 除了插入entry會引起連鎖更新，删除也可能會，[big][small][entry1][entry2] ，如果把[small]删除,那麼entry1可能就因為[big]，而需要記憶體重配置設定，繼而影響後面的entry。 連鎖更新最壞情況是執行N次空間重配置設定操作，每次空間重配置設定的最壞複雜度是O(N),是以最壞複雜度是O(N^2)。最壞的情況發生幾率很低，很難全鍊每個entry剛好是250-253位元組，如果隻是引起若幹個結點的連鎖更新，不會對效率産生很大影響。ziplistPush指令的平均複雜度僅為O(N)
四 主要 API
舉例： unsigned char *ziplistNew(void) {
// 分别用于 <zlbytes><zltail><zllen> 和 <zlend> unsigned int bytes = ZIPLIST_HEADER_SIZE+1; // header需要10位元組，2 個 32 bit，一個 16 bit，以及一個 8 bit作為最後一個zlend unsigned char *zl = zmalloc(bytes); // 配置設定11位元組的記憶體
// 設定長度 ZIPLIST_BYTES(zl) = intrev32ifbe(bytes); //intrev32ifbe是轉小端來儲存。ZIPLIST_BYTES是将ziplist的第一部分<zlbytes>(32bit)位置取出，然後把整個ziplist長度(11位元組)存入該位置。
// 設定表尾偏移量 ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE); // 設定在 32-63 位的zltail 為清單header的長度，即10(位元組)，一開始
// 設定清單項數量 ZIPLIST_LENGTH(zl) = 0; //設定zllen,目前還沒有任何entry
// 設定表尾辨別 // 最後已給位元組指派為十進制255 zl[bytes-1] = ZIP_END;
return zl; }
注意：ziplistPush,ziplistInsert,ziplistDelete,ziplistDeleteRange都有可能引起連鎖更新。