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

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

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

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

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

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

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

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

每個(gè)字段的含義如下：

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

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

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

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

那么問(wèn)題來(lái)了，我們?cè)谧x取數(shù)據(jù)的時(shí)候，我們?cè)趺粗朗菓?yīng)該按照讀取字符串還是整數(shù)類型的方式去讀取呢？我們需要知道當(dāng)前entry存儲(chǔ)數(shù)據(jù)的類型，即一個(gè)encoding字段，用來(lái)標(biāo)識(shí)當(dāng)前entry數(shù)據(jù)的類型。
除此之外，我們?cè)诓檎乙粋€(gè)元素的時(shí)候，需要對(duì)其進(jìn)行遍歷，在ziplist中是如何遍歷的呢？回想我們?cè)跀?shù)組中的遍歷方式：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

zset中的對(duì)象保存的元素?cái)?shù)量不超過(guò)128個(gè)
zset中保存的所有元素成員的長(zhǎng)度小于64字節(jié)

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

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