摘要：記錄壓縮列表總共占用的字節(jié)數(shù)，在對壓縮列表進行內(nèi)存重分配時使用個字節(jié)。為十六進制值，標(biāo)記一個壓縮列表的末尾具體的數(shù)據(jù)存放在中。占用或字節(jié)表示當(dāng)前存儲數(shù)據(jù)的類型與數(shù)據(jù)的長度。在學(xué)習(xí)的同時，如果沒有經(jīng)過自己的思考，收效甚微。

baiyan
全部視頻：https://segmentfault.com/a/11...

乍一看標(biāo)題，我們可能還不知道ziplist是何許人也。但是如果我說list、hash、zset這幾種數(shù)據(jù)結(jié)構(gòu)，大家就很熟悉了。而ziplist就是這幾種數(shù)據(jù)結(jié)構(gòu)的底層實現(xiàn)之一：

list：3.2.x之前為（ziplist + linkedlist）之后為quicklist
hash：數(shù)據(jù)量小的時候使用ziplist，量大時使用hashtable（dict）
zset：數(shù)據(jù)量小的時候使用ziplist，量大時使用skiplist

我們可以看到，ziplist總是在一種列表、哈希、有序集合這幾種結(jié)構(gòu)在存儲的數(shù)據(jù)量小的時會使用。隨著數(shù)據(jù)量的增長，會轉(zhuǎn)換到相對應(yīng)較復(fù)雜的類型。我們可以猜測，ziplist是一種輕巧、簡單、且占用內(nèi)存小的數(shù)據(jù)結(jié)構(gòu)。它能夠解決在redis數(shù)據(jù)量小時的存儲問題。

在redis的設(shè)計思想中，大多數(shù)情況下，都是以時間換空間。由于redis基于內(nèi)存，且內(nèi)存資源是相當(dāng)寶貴的，所以節(jié)省空間的“性價比”相對于節(jié)省時間，顯然更高一些。在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的過程中，我們常常將數(shù)組和鏈表放在一起比較。由于數(shù)組使用一塊連續(xù)的內(nèi)存，而鏈表分為指針域和數(shù)據(jù)域，數(shù)組在空間利用率上明顯要高于鏈表。參考以上設(shè)計思想，如果讓我們自己去設(shè)計ziplist的結(jié)構(gòu)，我們?nèi)绾嗡伎寄兀?/p>

需要一塊連續(xù)的內(nèi)存空間去存儲真正的數(shù)據(jù)
需要一些額外的信息字段去記錄它的長度、結(jié)束標(biāo)志、還有數(shù)據(jù)的總量等輔助信息

在ziplist中，是按照如下結(jié)構(gòu)進行存儲的，是否符合你的預(yù)期呢？

每個字段的含義如下：

zlbytes：4個字節(jié)。記錄壓縮列表總共占用的字節(jié)數(shù)，在對壓縮列表進行內(nèi)存重分配時使用
zltail：4個字節(jié)。可通過這個字段快速定位到鏈表末尾
zllen：2個字節(jié)。記錄總共有多少個entry
entry：具體數(shù)據(jù)的內(nèi)容就存在這里
zlend：1個字節(jié)。為十六進制值0xFF，標(biāo)記一個壓縮列表的末尾

具體的數(shù)據(jù)存放在entry中。在ziplist中，可以存儲兩種數(shù)據(jù)：

字符串（字節(jié)數(shù)組）
整數(shù)

舉一個例子，一個zset在數(shù)據(jù)量少的情況下，會將元素名和分值按從小到大的順序在ziplist的entry中連續(xù)存儲：

那么問題來了，我們在讀取數(shù)據(jù)的時候，我們怎么知道是應(yīng)該按照讀取字符串還是整數(shù)類型的方式去讀取呢？我們需要知道當(dāng)前entry存儲數(shù)據(jù)的類型，即一個encoding字段，用來標(biāo)識當(dāng)前entry數(shù)據(jù)的類型。
除此之外，我們在查找一個元素的時候，需要對其進行遍歷，在ziplist中是如何遍歷的呢？回想我們在數(shù)組中的遍歷方式：

普通數(shù)組的遍歷是根據(jù)數(shù)組里存儲的數(shù)據(jù)類型來找到下一個元素的，例如int類型的數(shù)組（也是指針）訪問下一個元素時每次只需要加上相應(yīng)類型的指針偏移量即可（如果用下標(biāo)法表示數(shù)組，p[0]到p[1]就等效于p+1*sizeof(int)這個過程；如果用指針法，可以用p+1來表示，它也等效于p+1*sizeof(int)）

那么在ziplist中，我們不知道數(shù)據(jù)類型，也不知道這個數(shù)據(jù)的長度，該如何將遍歷用的指針往后挪呢？這就需要一個字段去完成這個任務(wù)，這里就是previous_entry_length，它記錄前一個entry的長度，可以利用它完成壓縮列表的遍歷
最后，就是最重要的字段，即存儲真正數(shù)據(jù)的字段content
以我們上圖的例子，繼續(xù)我們畫出entry的結(jié)構(gòu)：

previous_entry_length：記錄了壓縮列表中前一個entry的長度。占用1或5字節(jié)

encoding：表示當(dāng)前entry存儲數(shù)據(jù)的類型與數(shù)據(jù)的長度。占用1、2或5字節(jié)

content：真正存儲數(shù)據(jù)的地方

遍歷是查找操作的基礎(chǔ)，學(xué)習(xí)任意一種數(shù)據(jù)結(jié)構(gòu)，遍歷都是關(guān)鍵。

正向遍歷ziplist：首先指針p在第一個entry的起始位置，即previous_entry_length字段的位置。由于previous_entry_length可能占用1個字節(jié)、也可能占用5個字節(jié)，所以我們需要知道如何區(qū)分這個字段占用了1還是5字節(jié)。表示方法如下：

如果前一個entry的長度小于254字節(jié)時，previous_entry_length用1字節(jié)表示
如果前一個entry的長度大于等于254字節(jié)時，previous_entry_length用5字節(jié)表示。注意此時第一個字節(jié)是固定的標(biāo)志0xFE（254），后面4個字節(jié)用來表示前一個entry的長度

這樣一來，我們就能夠知道：由于我們當(dāng)前的指針為unsigned char *類型（見源碼），指針運算p+1就等于往后偏移1個字節(jié)（即8位）。所以只需要讀取當(dāng)前指針的第一個字節(jié)的內(nèi)容，即p[0]的值是否在二進制的00000000 ~ 11111110（即0~254）之間。如果在這個區(qū)間內(nèi)，就說明previous_entry_length只占用1個字節(jié)，使用p+1就能夠得到encoding的首地址了；如果p[0]的值為11111111（255），說明previous_entry_length占用了5個字節(jié)，使用p+5也能夠得到encoding的首地址。

現(xiàn)在我們的指針來到了encoding字段起始地址的位置。那么，encoding字段是如何存儲數(shù)據(jù)類型和長度的呢？為了節(jié)省encoding字段所占用的內(nèi)存空間，將所有字符數(shù)組（字符串）類型以及整數(shù)類型按照如下編碼方式區(qū)分：

觀察上圖encoding的編碼方式，我們發(fā)現(xiàn)，只需要讀取當(dāng)前指針位置往后偏移兩位的內(nèi)容，就能夠得到encoding字段的長度。（00、11占用1字節(jié)；01占用2字節(jié)；10占用5字節(jié)）。那么我們相應(yīng)的p+1、p+2、p+5即可將指針偏移到content的位置。

由于我們在encoding字段中知道content字段的數(shù)據(jù)類型的長度（如int16等）再將指針往后偏移之前encoding字段中存儲的的相應(yīng)數(shù)據(jù)類型長度，就可以偏移到content字段的末尾了。后面如果有多個同樣的entry結(jié)構(gòu)，也同理，這樣就成功實現(xiàn)了ziplist的正序遍歷。

由于previous_entry_length字段的存在，我們首先取出外部zltail字段，也就是指向ziplist結(jié)構(gòu)末尾的指針，然后一次又一次地將指針減去entry中previous_entry_length字段的值，就能夠?qū)⒅羔樒频絲iplist的頭部，原理很簡單，相信大家都能夠理解，不再贅述。所以我們能夠發(fā)現(xiàn)，ziplist更適合從后往前遍歷。

其實ziplist就是借鑒了數(shù)組的思想，skiplist借鑒了鏈表的思想。不管是正向還是反向遍歷，還是在ziplist的插入或者刪除中需要將后面的元素往后挪或者往前挪，所有操作的復(fù)雜度均為O(n)。比起zset的另一種實現(xiàn)dict+skiplist中查詢O(1)的時間復(fù)雜度，還有插入以及刪除的O(logn)復(fù)雜度，ziplist在效率方面并沒有優(yōu)勢。但是我們之前講過，redis的設(shè)計思想一般都是以時間換空間，所以，相比skiplist需要維護大量的指針、在多層上面重復(fù)的數(shù)據(jù)（skiplist占用的空間為2n，詳情請看上一篇筆記），ziplist在空間復(fù)雜度上優(yōu)勢盡顯。

但是我們不得不說，ziplist在時間復(fù)雜度上面的劣勢依然存在，所以我們不能把劣勢無限放大開來，而是要揚長避短。所以，redis開發(fā)者也反復(fù)權(quán)衡，考慮到了這一點。就拿zset來說，只有符合如下兩個條件，才會使用ziplist編碼，否則使用skiplist進行編碼：

zset中的對象保存的元素數(shù)量不超過128個
zset中保存的所有元素成員的長度小于64字節(jié)

這樣一來，由于ziplist只處理少量、且規(guī)模很小的數(shù)據(jù)，這使得時間復(fù)雜度O(n)在ziplist處理少量數(shù)據(jù)的時候，這個n是非常小的。所以，這樣就能夠?qū)⑵鋾r間復(fù)雜度的影響降到了最低，將其空間復(fù)雜度的優(yōu)勢發(fā)揮到最大，這就是為什么需要進行編碼轉(zhuǎn)換的根本原因。

至于ziplist的關(guān)鍵之處就講完了。至于其增刪改查的具體源碼，有興趣的讀者可以去ziplist.c中深入查看，筆者在這篇文章里再復(fù)制粘貼一次意義也不大。學(xué)習(xí)的過程中，我閱讀了大量的資料，但是內(nèi)容質(zhì)量參差不齊。這里我想說，我們在學(xué)習(xí)一種新知識的時候，不僅僅要知道它是什么樣子，也要知道它為什么是這樣的、為什么這么做而不采用其它的替代方案？它的比較優(yōu)勢在哪里？而不要簡單的堆砌概念。在學(xué)習(xí)的同時，如果沒有經(jīng)過自己的思考，收效甚微。