redis源碼剖析（基礎資料結構篇）——ziplist

    ziplist是什麼東西？它又是幹什麼用的呢？

    簡單的說，ziplist是redis實作的一個連結清單結構體，它的主要特點是極其的節省空間。根據它的特性，我們也能很容易的推斷出，這東西主要是用來節省記憶體空間的。

    我們知道，redis是一個記憶體型資料庫。這樣的定位意味着redis必須盡量減少記憶體的使用量，以增大其處理資料的能力。仔細閱讀源碼，我們也會發現，redis在節省記憶體方面做了很大的工作，ziplist就是redis用于節省記憶體的一種方式。它在redis應用廣泛，redis基礎類型hash、list和zset的實作中都有它的身影，此外redis持久化實作也應用到了該結構體。

一、ziplist的真實記憶體布局

        為了節省記憶體，ziplist沒有直接存儲結構體，因為結構體有對齊的問題，會浪費一部分記憶體空間。另外ziplist的記憶體布局以bit為機關，這一點，用結構體也無法實作。

        1、ziplist整體結構

        ziplist從實質上講，就是一個具有類似雙向連結清單結構的位元組流，它的存儲空間連續，由連結清單頭、連結清單體與結束标志組成。如下圖所示：

圖1 ziplist結構圖

        zlbytes、zltail和zllen字段構成連結清單頭，entry字段表示真正的連結清單節點，entry的集合就是連結清單體，zlend是結束标志，為固定值255。

        zlbytes字段：4位元組，記錄這個ziplist結構的總長度，機關是位元組。

        zltail字段：4位元組，記錄最後一個entry的偏移位址。這個字段有點像連結清單中的尾指針，它可以讓我們迅速的找到連結清單的尾部，在尾部進行插入、删除等操作。

        zllen字段：2位元組，記錄entry的個數。這裡zllen最大為2^16 - 1，但是并不代表ziplist中最多隻能有這麼多個entry。ziplist規定，zllen的數值範圍是0到2^16-2，當zllen為2^16-1時，表示entry的個數大于2^16-2。此時，我們隻能通過周遊的方式獲得entry的個數。這樣做的目的是為了節省記憶體，因為ziplist結構體本身就是為存儲少量資料設計的，其entry個數不太會超過2^16-2。

        zlend字段：1位元組，為常數255。zlend字段标示出了ziplist的結束。255在ziplist中也算是一個特殊的字段，在我們周遊連結清單體時，我們會檢查每個entry的第一個字段，如果為255，就表示我們周遊到了ziplist的結尾處。為了防止混淆，每個真正存儲資料的entry的第一個字段都不會為255，這個我們會在對entry的介紹中看出來。

        entry字段：這個字段比較複雜，我們專門弄個小節來讨論它吧。

        2、entry結構

        entry字段是真正存儲資料的實體，為了節省空間，作者把這個結構體設計的比較複雜，基本上它是由3部分組成的，如下：

        1）prelen字段

        prelen字段指出目前entry的前一個entry字段的長度。這個字段可以使我們逆向周遊ziplist。它可以是1個位元組也可以是5個位元組。目前一個entry的長度小于254時，prelen隻占1個位元組。反之，目前一個entry的長度大于等于254時，prelen由5個位元組組成，第一個位元組設定為254，後4個位元組設定為具體的前一個entry的長度。如下圖所示：

圖2 prenlen的兩種格式

        我們可能會有疑問，1個位元組最大能表示到255，為什麼要拿254作為臨界值？因為255這個數用作了特殊的用途——标示ziplist的結尾，即用作了zlend字段。之前說過，為了防止混淆，每個真正存儲資料的entry的第一個字段都不會為255，而prelen就是entry的第一個字段。

        2）len字段與實體字段

        len字段與實體字段聯系緊密，這裡就一起講了。len字段指出了實體字段的具體長度，機關是位元組，而實體字段就是真正存儲資料的字段了。

        實體字段：對于該字段，首先要清楚一點，為了節省記憶體，ziplist在存儲實體時有一個原則——能用int類型存儲的，絕不用string類型。也就是說，如果存儲實體是一個數，且不超過INT64_MAX，則用int類型存儲，實在存儲不下了才采用string類型。是以實體字段存儲的可能是int，也可能是string。那如何來區分呢？這就需要len字段了。

        len字段：len字段并不是一個單純的數字字段，由于實體字段可以存儲int，還可以存儲string（此處，為了友善，我們把存儲string的entry叫做字元串entry，把存儲int的entry叫做整數entry），而且int可以是int8_t，int16_t，int24_t，int32_t和int64_t，是以len字段必須有一個字段來做标示。是以len字段又分為兩部分——encoding部分和real_len部分。encoding部分用于指明實體字段的存儲類型（是整數entry還是字元串entry），real_len部分用于指明實體字段的長度。多說無益，直接上圖。

圖3 字元串entry

        圖3顯示的是字元串entry的所有類型，圖中，prelen就是之前說過的prelen字段，有01數字的字段就是len字段的encoding部分，str_len就是len字段的real_len部分，String表示的就是實體字段，表示一個具體的字元串。可以看到，encoding部分為00時，len字段為1個位元組，其中2bit為encoding，6bit為real_len；encoding部分為01時，len字段為2位元組，其中2bit為encoding，14bit為real_len；encoding部分為10時，len字段為5位元組，其中8bit為encoding（後6bit不用），32bit為real_len。我們用表格的形式标明encoding與其實體字段所表示字元串長度的關系。

       表1 encoding對應字元串長度一覽

        可以看出，ziplist真的是使用的是記憶體能省則省的政策，在這裡，它盡量的減少了輔助字段（即real_len字段）的長度。

圖4 整數entry

        圖4顯示的是整數entry的所有類型。與圖3相似，int相當于圖3的string字段，都是實體字段。隻不過這裡沒有real_len字段，因為int的長度是幾個定值（8bit、16bit、24bit、32bit、64bit）。為了與字元串entry區分，整數entry的encoding字段的前兩位是11，後面再以不同的編碼區分int的具體位元組數。這裡要特别題的是圖中的最後一個entry，它的encoding字段範圍是11110001~11111101，它就表示真實的1~13這13個整數。我們用表格的形式标明encoding與其實體字段所表示整數範圍的關系。

表2 encoding對應整數範圍一覽

二、ziplist的具體操作

        其實為了節省記憶體，ziplist結構還可以再進行優化，如，利用設定prelen的思想去設定zlbytes字段或者zltail字段。但是作者為什麼不這麼幹呢？因為太複雜了。我們可以看到僅僅隻是目前的ziplist，要用代碼實作其連結清單式的操作已經非常複雜，其中涉及各種位運算與記憶體遷移。如果再加幾個字段，整體程式的複雜性會大大增加，同時，由于prelen的實作需要realloc的支援，如果ziplist有很多字段都具有prelen這樣的可伸縮特性，ziplist的效率還會變得異常低下與複雜。

        對于ziplist具體操作的實作，我不想講太多，因為确實很複雜，且沒有什麼技巧可以借鑒。其中就有一個東西還有點意思，我稍微提一下——對于prelen字段，ziplist采用隻增大不縮小的政策。

        對于ziplist這種實作，其prelen字段是不宜随意調整大小的，因為他會引起連鎖反應。如圖所示：

圖5 改變prelen引起連鎖反應

       假設entry1的體積增大，entry2中的prelen就要發生變化，假設entry1的大小不能用1個位元組表示，此時entry2的prelen必須從1個位元組變為5個位元組。這個行為也引起了entry2本身的體積增大，緻使entry3中的prelen也有需要擴充的可能。是以，prelen字段的擴充操作是代價很大的。同理，prelen的縮小政策的代價也很大。為此，ziplist不進行prelen的縮減，如果prelen被擴充成了5個位元組，那麼他就一直是5個位元組了。這樣也可以很好的防止某資料在臨界值上下波動造成prelen不斷的擴充與縮減。

       其實這樣的做法在邏輯上也成立——某個entry的值能到達很大的數時，很有可能下次還會到達這個量級。

三、ziplist在redis中的應用

        說了這麼多，那redis到底是怎麼用ziplist的呢？我們來舉個例子吧。就拿redis的基礎類型hash類型的實作來舉例吧。

        當hash中的資料較少時，hash的内部由ziplist實作，當資料過多時則有dict實作。對于這個資料多少的界限，我們可以通過redis.conf配置檔案進行設定。在配置檔案中，關于hash的ziplist配置項主要有“hash-max-ziplist-entries”和“hash-max-ziplist-value”兩個。hash-max-ziplist-entries定義的是ziplist能存儲的最大entry個數，hash-max-ziplist-value定義的是ziplist存儲的字元串的最大長度。隻有當資料個數小于hash-max-ziplist-entries且每個資料的長度都不大于hash-max-ziplist-value時，hash才用ziplist實作。如果上述兩者有一種不符合，hash的内部實作就會從ziplist轉換為dict。其實這兩個配置項主要的作用就是限定ziplist的大小，不讓ziplist太大。

        關于dict結構體，可以參照文章“redis源碼剖析（基礎資料結構篇）——字典”，關于hash的具體實作，以後我還會專門寫文章介紹。

四、小結

        ziplist是一個很節省記憶體且效率不慢的類雙向連結清單實作。它在redis中運用廣泛的結構體，其具體的實作比較複雜，同學們不必深究。但是它的記憶體布局值得我們借鑒。希望同學們能體會到這種設計布局的精髓。