溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇文章為大家展示了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為了在細節上節省內存，對于值的存儲采用了變長的編碼方式，大概意思是說，對于大的整數，就多用一些字節來存儲，而對于小的整數，就少用一些字節來存儲。我們接下來很快就會討論到這些實現細節。
ziplist的數據結構組成是本文要討論的重點。實際上，ziplist還是稍微有點復雜的，它復雜的地方就在于它的數據結構定義。一旦理解了數據結構，它的一些操作也就比較容易理解了。
我們接下來先從總體上介紹一下ziplist的數據結構定義，然后舉一個實際的例子，通過例子來解釋ziplist的構成。如果你看懂了這一部分，本文的任務就算完成了一大半了。
從宏觀上看，ziplist的內存結構如下：
<zlbytes><zltail><zllen><entry>...<entry><zlend>
各個部分在內存上是前后相鄰的，它們分別的含義如下：
<zlbytes>: 32bit，表示ziplist占用的字節總數（也包括<zlbytes>本身占用的4個字節）。
<zltail>: 32bit，表示ziplist表中最后一項（entry）在ziplist中的偏移字節數。<zltail>的存在，使得我們可以很方便地找到最后一項（不用遍歷整個ziplist），從而可以在ziplist尾端快速地執行push或pop操作。
<zllen>: 16bit， 表示ziplist中數據項（entry）的個數。zllen字段因為只有16bit，所以可以表達的最大值為2^16-1。這里需要特別注意的是，如果ziplist中數據項個數超過了16bit能表達的最大值，ziplist仍然可以來表示。那怎么表示呢？這里做了這樣的規定：如果<zllen>小于等于2^16-2（也就是不等于2^16-1），那么<zllen>就表示ziplist中數據項的個數；否則，也就是<zllen>等于16bit全為1的情況，那么<zllen>就不表示數據項個數了，這時候要想知道ziplist中數據項總數，那么必須對ziplist從頭到尾遍歷各個數據項，才能計數出來。
<entry>: 表示真正存放數據的數據項，長度不定。一個數據項（entry）也有它自己的內部結構，這個稍后再解釋。
<zlend>: ziplist最后1個字節，是一個結束標記，值固定等于255。
上面的定義中還值得注意的一點是：<zlbytes>,
<zltail>,
<zllen>既然占據多個字節，那么在存儲的時候就有大端（big endian）和小端（little endian）的區別。ziplist采取的是小端模式來存儲，這在下面我們介紹具體例子的時候還會再詳細解釋。
我們再來看一下每一個數據項<entry>的構成：
<prevrawlen><len><data>
我們看到在真正的數據（<data>）前面，還有兩個字段：
<prevrawlen>: 表示前一個數據項占用的總字節數。這個字段的用處是為了讓ziplist能夠從后向前遍歷（從后一項的位置，只需向前偏移prevrawlen個字節，就找到了前一項）。這個字段采用變長編碼。
<len>: 表示當前數據項的數據長度（即<data>部分的長度）。也采用變長編碼。
那么<prevrawlen>和<len>是怎么進行變長編碼的呢？各位讀者打起精神了，我們終于講到了ziplist的定義中最繁瑣的地方了。
先說<prevrawlen>。它有兩種可能，或者是1個字節，或者是5個字節：
如果前一個數據項占用字節數小于254，那么<prevrawlen>就只用一個字節來表示，這個字節的值就是前一個數據項的占用字節數。
如果前一個數據項占用字節數大于等于254，那么<prevrawlen>就用5個字節來表示，其中第1個字節的值是254（作為這種情況的一個標記），而后面4個字節組成一個整型值，來真正存儲前一個數據項的占用字節數。
有人會問了，為什么沒有255的情況呢？
這是因為：255已經定義為ziplist結束標記<zlend>的值了。在ziplist的很多操作的實現中，都會根據數據項的第1個字節是不是255來判斷當前是不是到達ziplist的結尾了，因此一個正常的數據的第1個字節（也就是<prevrawlen>的第1個字節）是不能夠取255這個值的，否則就沖突了。
而<len>字段就更加復雜了，它根據第1個字節的不同，總共分為9種情況（下面的表示法是按二進制表示）：
|00pppppp| - 1 byte。第1個字節最高兩個bit是00，那么<len>字段只有1個字節，剩余的6個bit用來表示長度值，最高可以表示63 (2^6-1)。
|01pppppp|qqqqqqqq| - 2 bytes。第1個字節最高兩個bit是01，那么<len>字段占2個字節，總共有14個bit用來表示長度值，最高可以表示16383 (2^14-1)。
|10__|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 5 bytes。第1個字節最高兩個bit是10，那么len字段占5個字節，總共使用32個bit來表示長度值（6個bit舍棄不用），最高可以表示2^32-1。需要注意的是：在前三種情況下，<data>都是按字符串來存儲的；從下面第4種情況開始，<data>開始變為按整數來存儲了。
|11000000| - 1 byte。<len>字段占用1個字節，值為0xC0，后面的數據<data>存儲為2個字節的int16_t類型。
|11010000| - 1 byte。<len>字段占用1個字節，值為0xD0，后面的數據<data>存儲為4個字節的int32_t類型。
|11100000| - 1 byte。<len>字段占用1個字節，值為0xE0，后面的數據<data>存儲為8個字節的int64_t類型。
|11110000| - 1 byte。<len>字段占用1個字節，值為0xF0，后面的數據<data>存儲為3個字節長的整數。
|11111110| - 1 byte。<len>字段占用1個字節，值為0xFE，后面的數據<data>存儲為1個字節的整數。
|1111xxxx| - - (xxxx的值在0001和1101之間)。這是一種特殊情況，xxxx從1到13一共13個值，這時就用這13個值來表示真正的數據。注意，這里是表示真正的數據，而不是數據長度了。也就是說，在這種情況下，后面不再需要一個單獨的<data>字段來表示真正的數據了，而是<len>和<data>合二為一了。另外，由于xxxx只能取0001和1101這13個值了（其它可能的值和其它情況沖突了，比如0000和1110分別同前面第7種第8種情況沖突，1111跟結束標記沖突），而小數值應該從0開始，因此這13個值分別表示0到12，即xxxx的值減去1才是它所要表示的那個整數數據的值。
好了，ziplist的數據結構定義，我們介紹完了，現在我們看一個具體的例子。
上圖是一份真實的ziplist數據。我們逐項解讀一下：
這個ziplist一共包含33個字節。字節編號從byte[0]到byte[32]。圖中每個字節的值使用16進制表示。
頭4個字節（0x21000000）是按小端（little endian）模式存儲的<zlbytes>字段。什么是小端呢？就是指數據的低字節保存在內存的低地址中（參見維基百科詞條
Endianness）。因此，這里<zlbytes>的值應該解析成0x00000021，用十進制表示正好就是33。
接下來4個字節（byte[4..7]）是<zltail>，用小端存儲模式來解釋，它的值是0x0000001D（值為29），表示最后一個數據項在byte[29]的位置（那個數據項為0x05FE14）。
再接下來2個字節（byte[8..9]），值為0x0004，表示這個ziplist里一共存有4項數據。
接下來6個字節（byte[10..15]）是第1個數據項。其中，prevrawlen=0，因為它前面沒有數據項；len=4，相當于前面定義的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個字節=FE，相當于前面定義的9種情況中的第8種，所以后面還有1個字節用來表示真正的數據，并且以整數表示。它的值是20（0x14）。
最后1個字節（byte[32]）表示<zlend>，是固定的值255（0xFF）。
總結一下，這個ziplist里存了4個數據項，分別為：
字符串: “name”
字符串: “tielei”
字符串: “age”
整數: 20
（好吧，被你發現了~~tielei實際上當然不是20歲，他哪有那么年輕啊……）
實際上，這個ziplist是通過兩個hset命令創建出來的。這個我們后半部分會再提到。
好了，既然你已經閱讀到這里了，說明你還是很有耐心的（其實我寫到這里也已經累得不行了）。可以先把本文收藏，休息一下，回頭再看后半部分。
接下來我要貼一些代碼了。
我們先不著急看實現，先來挑幾個ziplist的重要的接口，看看它們長什么樣子：
unsigned char *ziplistNew(void); unsigned char *ziplistMerge(unsigned char **first, unsigned char **second); unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where); unsigned char *ziplistIndex(unsigned char *zl, int index); unsigned char *ziplistNext(unsigned char *zl, unsigned char *p); unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p); unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen); unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p); unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip); unsigned int ziplistLen(unsigned char *zl);
我們從這些接口的名字就可以粗略猜出它們的功能，下面簡單解釋一下：
ziplist的數據類型，沒有用自定義的struct之類的來表達，而就是簡單的unsigned char *。這是因為ziplist本質上就是一塊連續內存，內部組成結構又是一個高度動態的設計（變長編碼），也沒法用一個固定的數據結構來表達。
ziplistNew: 創建一個空的ziplist（只包含<zlbytes><zltail><zllen><zlend>）。
ziplistMerge: 將兩個ziplist合并成一個新的ziplist。
ziplistPush: 在ziplist的頭部或尾端插入一段數據（產生一個新的數據項）。注意一下這個接口的返回值，是一個新的ziplist。調用方必須用這里返回的新的ziplist，替換之前傳進來的舊的ziplist變量，而經過這個函數處理之后，原來舊的ziplist變量就失效了。為什么一個簡單的插入操作會導致產生一個新的ziplist呢？這是因為ziplist是一塊連續空間，對它的追加操作，會引發內存的realloc，因此ziplist的內存位置可能會發生變化。實際上，我們在之前介紹sds的文章中提到過類似這種接口使用模式（參見sdscatlen函數的說明）。
ziplistIndex: 返回index參數指定的數據項的內存位置。index可以是負數，表示從尾端向前進行索引。
ziplistNext和ziplistPrev分別返回一個ziplist中指定數據項p的后一項和前一項。
ziplistInsert: 在ziplist的任意數據項前面插入一個新的數據項。
ziplistDelete: 刪除指定的數據項。
ziplistFind: 查找給定的數據（由vstr和vlen指定）。注意它有一個skip參數，表示查找的時候每次比較之間要跳過幾個數據項。為什么會有這么一個參數呢？其實這個參數的主要用途是當用ziplist表示hash結構的時候，是按照一個field，一個value來依次存入ziplist的。也就是說，偶數索引的數據項存field，奇數索引的數據項存value。當按照field的值進行查找的時候，就需要把奇數項跳過去。
ziplistLen: 計算ziplist的長度（即包含數據項的個數）。
ziplist的相關接口的具體實現，還是有些復雜的，限于篇幅的原因，我們這里只結合代碼來講解插入的邏輯。插入是很有代表性的操作，通過這部分來一窺ziplist內部的實現，其它部分的實現我們也就會很容易理解了。
ziplistPush和ziplistInsert都是插入，只是對于插入位置的限定不同。它們在內部實現都依賴一個名為__ziplistInsert的內部函數，其代碼如下（出自ziplist.c）:
static unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen;
unsigned int prevlensize, prevlen = 0;
size_t offset;
int nextdiff = 0;
unsigned char encoding = 0;
long long value = 123456789; /* initialized to avoid warning. Using a value
that is easy to see if for some reason
we use it uninitialized. */
zlentry tail;
/* Find out prevlen for the entry that is inserted. */
if (p[0] != ZIP_END) {
ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
} else {
unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
if (ptail[0] != ZIP_END) {
prevlen = zipRawEntryLength(ptail);
}
}
/* See if the entry can be encoded */
if (zipTryEncoding(s,slen,&value,&encoding)) {
/* 'encoding' is set to the appropriate integer encoding */
reqlen = zipIntSize(encoding);
} else {
/* 'encoding' is untouched, however zipEncodeLength will use the
* string length to figure out how to encode it. */
reqlen = slen;
}
/* We need space for both the length of the previous entry and
* the length of the payload. */
reqlen += zipPrevEncodeLength(NULL,prevlen);
reqlen += zipEncodeLength(NULL,encoding,slen);
/* When the insert position is not equal to the tail, we need to
* make sure that the next entry can hold this entry's length in
* its prevlen field. */
nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
/* Store offset because a realloc may change the address of zl. */
offset = p-zl;
zl = ziplistResize(zl,curlen+reqlen+nextdiff);
p = zl+offset;
/* Apply memory move when necessary and update tail offset. */
if (p[0] != ZIP_END) {
/* Subtract one because of the ZIP_END bytes */
memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);
/* Encode this entry's raw length in the next entry. */
zipPrevEncodeLength(p+reqlen,reqlen);
/* Update offset for tail */
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);
/* When the tail contains more than one entry, we need to take
* "nextdiff" in account as well. Otherwise, a change in the
* size of prevlen doesn't have an effect on the *tail* offset. */
zipEntry(p+reqlen, &tail);
if (p[reqlen+tail.headersize+tail.len] != ZIP_END) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}
} else {
/* This element will be the new tail. */
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
}
/* When nextdiff != 0, the raw length of the next entry has changed, so
* we need to cascade the update throughout the ziplist */
if (nextdiff != 0) {
offset = p-zl;
zl = __ziplistCascadeUpdate(zl,p+reqlen);
p = zl+offset;
}
/* Write the entry */
p += zipPrevEncodeLength(p,prevlen);
p += zipEncodeLength(p,encoding,slen);
if (ZIP_IS_STR(encoding)) {
memcpy(p,s,slen);
} else {
zipSaveInteger(p,value,encoding);
}
ZIPLIST_INCR_LENGTH(zl,1);
return zl;
}我們來簡單解析一下這段代碼：
這個函數是在指定的位置p插入一段新的數據，待插入數據的地址指針是s，長度為slen。插入后形成一個新的數據項，占據原來p的配置，原來位于p位置的數據項以及后面的所有數據項，需要統一向后移動，給新插入的數據項留出空間。參數p指向的是ziplist中某一個數據項的起始位置，或者在向尾端插入的時候，它指向ziplist的結束標記<zlend>。
函數開始先計算出待插入位置前一個數據項的長度prevlen。這個長度要存入新插入的數據項的<prevrawlen>字段。
然后計算當前數據項占用的總字節數reqlen，它包含三部分：<prevrawlen>,
<len>和真正的數據。其中的數據部分會通過調用zipTryEncoding先來嘗試轉成整數。
由于插入導致的ziplist對于內存的新增需求，除了待插入數據項占用的reqlen之外，還要考慮原來p位置的數據項（現在要排在待插入數據項之后）的<prevrawlen>字段的變化。本來它保存的是前一項的總長度，現在變成了保存當前插入的數據項的總長度。這樣它的<prevrawlen>字段本身需要的存儲空間也可能發生變化，這個變化可能是變大也可能是變小。這個變化了多少的值nextdiff，是調用zipPrevLenByteDiff計算出來的。如果變大了，nextdiff是正值，否則是負值。
現在很容易算出來插入后新的ziplist需要多少字節了，然后調用ziplistResize來重新調整大小。ziplistResize的實現里會調用allocator的zrealloc，它有可能會造成數據拷貝。
現在額外的空間有了，接下來就是將原來p位置的數據項以及后面的所有數據都向后挪動，并為它設置新的<prevrawlen>字段。此外，還可能需要調整ziplist的<zltail>字段。
最后，組裝新的待插入數據項，放在位置p。
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。
robj *createHashObject(void) {
unsigned char *zl = ziplistNew();
robj *o = createObject(OBJ_HASH, zl);
o->encoding = OBJ_ENCODING_ZIPLIST;
return o;
}上面的createHashObject函數，出自object.c，它負責的任務就是創建一個新的hash結構。可以看出，它創建了一個type = OBJ_HASH但encoding = OBJ_ENCODING_ZIPLIST的robj對象。
實際上，本文前面給出的那個ziplist實例，就是由如下兩個命令構建出來的。
hset user:100 name tielei hset user:100 age 20
每執行一次hset命令，插入的field和value分別作為一個新的數據項插入到ziplist中（即每次hset產生兩個數據項）。
當隨著數據的插入，hash底層的這個ziplist就可能會轉成dict。那么到底插入多少才會轉呢？
還記得本文開頭提到的兩個Redis配置嗎？
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上的查找需要進行遍歷。
上述內容就是Redis中內部數據結構ziplist的作用是什么，你們學到知識或技能了嗎？如果還想學到更多技能或者豐富自己的知識儲備，歡迎關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
