Redis中內(nèi)部數(shù)據(jù)結(jié)構(gòu)ziplist的作用是什么

本篇文章為大家展示了Redis中內(nèi)部數(shù)據(jù)結(jié)構(gòu)ziplist的作用是什么，內(nèi)容簡(jiǎn)明扼要并且容易理解，絕對(duì)能使你眼前一亮，通過這篇文章的詳細(xì)介紹希望你能有所收獲。

什么是ziplist

Redis官方對(duì)于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是一個(gè)經(jīng)過特殊編碼的雙向鏈表，它的設(shè)計(jì)目標(biāo)就是為了提高存儲(chǔ)效率。ziplist可以用于存儲(chǔ)字符串或整數(shù)，其中整數(shù)是按真正的二進(jìn)制表示進(jìn)行編碼的，而不是編碼成字符串序列。它能以O(shè)(1)的時(shí)間復(fù)雜度在表的兩端提供push和pop操作。

實(shí)際上，ziplist充分體現(xiàn)了Redis對(duì)于存儲(chǔ)效率的追求。一個(gè)普通的雙向鏈表，鏈表中每一項(xiàng)都占用獨(dú)立的一塊內(nèi)存，各項(xiàng)之間用地址指針（或引用）連接起來。這種方式會(huì)帶來大量的內(nèi)存碎片，而且地址指針也會(huì)占用額外的內(nèi)存。而ziplist卻是將表中每一項(xiàng)存放在前后連續(xù)的地址空間內(nèi)，一個(gè)ziplist整體占用一大塊內(nèi)存。它是一個(gè)表（list），但其實(shí)不是一個(gè)鏈表（linked list）。

另外，ziplist為了在細(xì)節(jié)上節(jié)省內(nèi)存，對(duì)于值的存儲(chǔ)采用了變長(zhǎng)的編碼方式，大概意思是說，對(duì)于大的整數(shù)，就多用一些字節(jié)來存儲(chǔ)，而對(duì)于小的整數(shù)，就少用一些字節(jié)來存儲(chǔ)。我們接下來很快就會(huì)討論到這些實(shí)現(xiàn)細(xì)節(jié)。

ziplist的數(shù)據(jù)結(jié)構(gòu)定義

ziplist的數(shù)據(jù)結(jié)構(gòu)組成是本文要討論的重點(diǎn)。實(shí)際上，ziplist還是稍微有點(diǎn)復(fù)雜的，它復(fù)雜的地方就在于它的數(shù)據(jù)結(jié)構(gòu)定義。一旦理解了數(shù)據(jù)結(jié)構(gòu)，它的一些操作也就比較容易理解了。

我們接下來先從總體上介紹一下ziplist的數(shù)據(jù)結(jié)構(gòu)定義，然后舉一個(gè)實(shí)際的例子，通過例子來解釋ziplist的構(gòu)成。如果你看懂了這一部分，本文的任務(wù)就算完成了一大半了。

從宏觀上看，ziplist的內(nèi)存結(jié)構(gòu)如下：

<zlbytes><zltail><zllen><entry>...<entry><zlend>

各個(gè)部分在內(nèi)存上是前后相鄰的，它們分別的含義如下：

• <zlbytes>: 32bit，表示ziplist占用的字節(jié)總數(shù)（也包括<zlbytes>本身占用的4個(gè)字節(jié)）。

• <zltail>: 32bit，表示ziplist表中最后一項(xiàng)（entry）在ziplist中的偏移字節(jié)數(shù)。<zltail>的存在，使得我們可以很方便地找到最后一項(xiàng)（不用遍歷整個(gè)ziplist），從而可以在ziplist尾端快速地執(zhí)行push或pop操作。

• <zllen>: 16bit， 表示ziplist中數(shù)據(jù)項(xiàng)（entry）的個(gè)數(shù)。zllen字段因?yàn)橹挥?6bit，所以可以表達(dá)的最大值為2^16-1。這里需要特別注意的是，如果ziplist中數(shù)據(jù)項(xiàng)個(gè)數(shù)超過了16bit能表達(dá)的最大值，ziplist仍然可以來表示。那怎么表示呢？這里做了這樣的規(guī)定：如果<zllen>小于等于2^16-2（也就是不等于2^16-1），那么<zllen>就表示ziplist中數(shù)據(jù)項(xiàng)的個(gè)數(shù)；否則，也就是<zllen>等于16bit全為1的情況，那么<zllen>就不表示數(shù)據(jù)項(xiàng)個(gè)數(shù)了，這時(shí)候要想知道ziplist中數(shù)據(jù)項(xiàng)總數(shù)，那么必須對(duì)ziplist從頭到尾遍歷各個(gè)數(shù)據(jù)項(xiàng)，才能計(jì)數(shù)出來。

• <entry>: 表示真正存放數(shù)據(jù)的數(shù)據(jù)項(xiàng)，長(zhǎng)度不定。一個(gè)數(shù)據(jù)項(xiàng)（entry）也有它自己的內(nèi)部結(jié)構(gòu)，這個(gè)稍后再解釋。

• <zlend>: ziplist最后1個(gè)字節(jié)，是一個(gè)結(jié)束標(biāo)記，值固定等于255。

上面的定義中還值得注意的一點(diǎn)是：<zlbytes>, <zltail>, <zllen>既然占據(jù)多個(gè)字節(jié)，那么在存儲(chǔ)的時(shí)候就有大端（big endian）和小端（little endian）的區(qū)別。ziplist采取的是小端模式來存儲(chǔ)，這在下面我們介紹具體例子的時(shí)候還會(huì)再詳細(xì)解釋。

我們?cè)賮砜匆幌旅恳粋€(gè)數(shù)據(jù)項(xiàng)<entry>的構(gòu)成：

<prevrawlen><len><data>

我們看到在真正的數(shù)據(jù)（<data>）前面，還有兩個(gè)字段：

• <prevrawlen>: 表示前一個(gè)數(shù)據(jù)項(xiàng)占用的總字節(jié)數(shù)。這個(gè)字段的用處是為了讓ziplist能夠從后向前遍歷（從后一項(xiàng)的位置，只需向前偏移prevrawlen個(gè)字節(jié)，就找到了前一項(xiàng)）。這個(gè)字段采用變長(zhǎng)編碼。

• <len>: 表示當(dāng)前數(shù)據(jù)項(xiàng)的數(shù)據(jù)長(zhǎng)度（即<data>部分的長(zhǎng)度）。也采用變長(zhǎng)編碼。

那么<prevrawlen>和<len>是怎么進(jìn)行變長(zhǎng)編碼的呢？各位讀者打起精神了，我們終于講到了ziplist的定義中最繁瑣的地方了。

先說<prevrawlen>。它有兩種可能，或者是1個(gè)字節(jié)，或者是5個(gè)字節(jié)：

1. 如果前一個(gè)數(shù)據(jù)項(xiàng)占用字節(jié)數(shù)小于254，那么<prevrawlen>就只用一個(gè)字節(jié)來表示，這個(gè)字節(jié)的值就是前一個(gè)數(shù)據(jù)項(xiàng)的占用字節(jié)數(shù)。

2. 如果前一個(gè)數(shù)據(jù)項(xiàng)占用字節(jié)數(shù)大于等于254，那么<prevrawlen>就用5個(gè)字節(jié)來表示，其中第1個(gè)字節(jié)的值是254（作為這種情況的一個(gè)標(biāo)記），而后面4個(gè)字節(jié)組成一個(gè)整型值，來真正存儲(chǔ)前一個(gè)數(shù)據(jù)項(xiàng)的占用字節(jié)數(shù)。

有人會(huì)問了，為什么沒有255的情況呢？

這是因?yàn)椋?55已經(jīng)定義為ziplist結(jié)束標(biāo)記<zlend>的值了。在ziplist的很多操作的實(shí)現(xiàn)中，都會(huì)根據(jù)數(shù)據(jù)項(xiàng)的第1個(gè)字節(jié)是不是255來判斷當(dāng)前是不是到達(dá)ziplist的結(jié)尾了，因此一個(gè)正常的數(shù)據(jù)的第1個(gè)字節(jié)（也就是<prevrawlen>的第1個(gè)字節(jié)）是不能夠取255這個(gè)值的，否則就沖突了。

而<len>字段就更加復(fù)雜了，它根據(jù)第1個(gè)字節(jié)的不同，總共分為9種情況（下面的表示法是按二進(jìn)制表示）：

1. |00pppppp| - 1 byte。第1個(gè)字節(jié)最高兩個(gè)bit是00，那么<len>字段只有1個(gè)字節(jié)，剩余的6個(gè)bit用來表示長(zhǎng)度值，最高可以表示63 (2^6-1)。

2. |01pppppp|qqqqqqqq| - 2 bytes。第1個(gè)字節(jié)最高兩個(gè)bit是01，那么<len>字段占2個(gè)字節(jié)，總共有14個(gè)bit用來表示長(zhǎng)度值，最高可以表示16383 (2^14-1)。

3. |10__|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 5 bytes。第1個(gè)字節(jié)最高兩個(gè)bit是10，那么len字段占5個(gè)字節(jié)，總共使用32個(gè)bit來表示長(zhǎng)度值（6個(gè)bit舍棄不用），最高可以表示2^32-1。需要注意的是：在前三種情況下，<data>都是按字符串來存儲(chǔ)的；從下面第4種情況開始，<data>開始變?yōu)榘凑麛?shù)來存儲(chǔ)了。

4. |11000000| - 1 byte。<len>字段占用1個(gè)字節(jié)，值為0xC0，后面的數(shù)據(jù)<data>存儲(chǔ)為2個(gè)字節(jié)的int16_t類型。

5. |11010000| - 1 byte。<len>字段占用1個(gè)字節(jié)，值為0xD0，后面的數(shù)據(jù)<data>存儲(chǔ)為4個(gè)字節(jié)的int32_t類型。

6. |11100000| - 1 byte。<len>字段占用1個(gè)字節(jié)，值為0xE0，后面的數(shù)據(jù)<data>存儲(chǔ)為8個(gè)字節(jié)的int64_t類型。

7. |11110000| - 1 byte。<len>字段占用1個(gè)字節(jié)，值為0xF0，后面的數(shù)據(jù)<data>存儲(chǔ)為3個(gè)字節(jié)長(zhǎng)的整數(shù)。

8. |11111110| - 1 byte。<len>字段占用1個(gè)字節(jié)，值為0xFE，后面的數(shù)據(jù)<data>存儲(chǔ)為1個(gè)字節(jié)的整數(shù)。

9. |1111xxxx| - - (xxxx的值在0001和1101之間)。這是一種特殊情況，xxxx從1到13一共13個(gè)值，這時(shí)就用這13個(gè)值來表示真正的數(shù)據(jù)。注意，這里是表示真正的數(shù)據(jù)，而不是數(shù)據(jù)長(zhǎng)度了。也就是說，在這種情況下，后面不再需要一個(gè)單獨(dú)的<data>字段來表示真正的數(shù)據(jù)了，而是<len>和<data>合二為一了。另外，由于xxxx只能取0001和1101這13個(gè)值了（其它可能的值和其它情況沖突了，比如0000和1110分別同前面第7種第8種情況沖突，1111跟結(jié)束標(biāo)記沖突），而小數(shù)值應(yīng)該從0開始，因此這13個(gè)值分別表示0到12，即xxxx的值減去1才是它所要表示的那個(gè)整數(shù)數(shù)據(jù)的值。

好了，ziplist的數(shù)據(jù)結(jié)構(gòu)定義，我們介紹完了，現(xiàn)在我們看一個(gè)具體的例子。

上圖是一份真實(shí)的ziplist數(shù)據(jù)。我們逐項(xiàng)解讀一下：

• 這個(gè)ziplist一共包含33個(gè)字節(jié)。字節(jié)編號(hào)從byte[0]到byte[32]。圖中每個(gè)字節(jié)的值使用16進(jìn)制表示。

• 頭4個(gè)字節(jié)（0x21000000）是按小端（little endian）模式存儲(chǔ)的<zlbytes>字段。什么是小端呢？就是指數(shù)據(jù)的低字節(jié)保存在內(nèi)存的低地址中（參見維基百科詞條 Endianness）。因此，這里<zlbytes>的值應(yīng)該解析成0x00000021，用十進(jìn)制表示正好就是33。

• 接下來4個(gè)字節(jié)（byte[4..7]）是<zltail>，用小端存儲(chǔ)模式來解釋，它的值是0x0000001D（值為29），表示最后一個(gè)數(shù)據(jù)項(xiàng)在byte[29]的位置（那個(gè)數(shù)據(jù)項(xiàng)為0x05FE14）。

• 再接下來2個(gè)字節(jié)（byte[8..9]），值為0x0004，表示這個(gè)ziplist里一共存有4項(xiàng)數(shù)據(jù)。

• 接下來6個(gè)字節(jié)（byte[10..15]）是第1個(gè)數(shù)據(jù)項(xiàng)。其中，prevrawlen=0，因?yàn)樗懊鏇]有數(shù)據(jù)項(xiàng)；len=4，相當(dāng)于前面定義的9種情況中的第1種，表示后面4個(gè)字節(jié)按字符串存儲(chǔ)數(shù)據(jù)，數(shù)據(jù)的值為”name”。

• 接下來8個(gè)字節(jié)（byte[16..23]）是第2個(gè)數(shù)據(jù)項(xiàng)，與前面數(shù)據(jù)項(xiàng)存儲(chǔ)格式類似，存儲(chǔ)1個(gè)字符串”tielei”。

• 接下來5個(gè)字節(jié)（byte[24..28]）是第3個(gè)數(shù)據(jù)項(xiàng)，與前面數(shù)據(jù)項(xiàng)存儲(chǔ)格式類似，存儲(chǔ)1個(gè)字符串”age”。

• 接下來3個(gè)字節(jié)（byte[29..31]）是最后一個(gè)數(shù)據(jù)項(xiàng)，它的格式與前面的數(shù)據(jù)項(xiàng)存儲(chǔ)格式不太一樣。其中，第1個(gè)字節(jié)prevrawlen=5，表示前一個(gè)數(shù)據(jù)項(xiàng)占用5個(gè)字節(jié)；第2個(gè)字節(jié)=FE，相當(dāng)于前面定義的9種情況中的第8種，所以后面還有1個(gè)字節(jié)用來表示真正的數(shù)據(jù)，并且以整數(shù)表示。它的值是20（0x14）。

• 最后1個(gè)字節(jié)（byte[32]）表示<zlend>，是固定的值255（0xFF）。

總結(jié)一下，這個(gè)ziplist里存了4個(gè)數(shù)據(jù)項(xiàng)，分別為：

• 字符串: “name”

• 字符串: “tielei”

• 字符串: “age”

• 整數(shù): 20

（好吧，被你發(fā)現(xiàn)了~~tielei實(shí)際上當(dāng)然不是20歲，他哪有那么年輕啊……）

實(shí)際上，這個(gè)ziplist是通過兩個(gè)hset命令創(chuàng)建出來的。這個(gè)我們后半部分會(huì)再提到。

好了，既然你已經(jīng)閱讀到這里了，說明你還是很有耐心的（其實(shí)我寫到這里也已經(jīng)累得不行了）?？梢韵劝驯疚氖詹?，休息一下，回頭再看后半部分。

接下來我要貼一些代碼了。

ziplist的接口

我們先不著急看實(shí)現(xiàn)，先來挑幾個(gè)ziplist的重要的接口，看看它們長(zhǎng)什么樣子：

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);

我們從這些接口的名字就可以粗略猜出它們的功能，下面簡(jiǎn)單解釋一下：

• ziplist的數(shù)據(jù)類型，沒有用自定義的struct之類的來表達(dá)，而就是簡(jiǎn)單的unsigned char *。這是因?yàn)閦iplist本質(zhì)上就是一塊連續(xù)內(nèi)存，內(nèi)部組成結(jié)構(gòu)又是一個(gè)高度動(dòng)態(tài)的設(shè)計(jì)（變長(zhǎng)編碼），也沒法用一個(gè)固定的數(shù)據(jù)結(jié)構(gòu)來表達(dá)。

• ziplistNew: 創(chuàng)建一個(gè)空的ziplist（只包含<zlbytes><zltail><zllen><zlend>）。

• ziplistMerge: 將兩個(gè)ziplist合并成一個(gè)新的ziplist。

• ziplistPush: 在ziplist的頭部或尾端插入一段數(shù)據(jù)（產(chǎn)生一個(gè)新的數(shù)據(jù)項(xiàng)）。注意一下這個(gè)接口的返回值，是一個(gè)新的ziplist。調(diào)用方必須用這里返回的新的ziplist，替換之前傳進(jìn)來的舊的ziplist變量，而經(jīng)過這個(gè)函數(shù)處理之后，原來舊的ziplist變量就失效了。為什么一個(gè)簡(jiǎn)單的插入操作會(huì)導(dǎo)致產(chǎn)生一個(gè)新的ziplist呢？這是因?yàn)閦iplist是一塊連續(xù)空間，對(duì)它的追加操作，會(huì)引發(fā)內(nèi)存的realloc，因此ziplist的內(nèi)存位置可能會(huì)發(fā)生變化。實(shí)際上，我們?cè)谥敖榻Bsds的文章中提到過類似這種接口使用模式（參見sdscatlen函數(shù)的說明）。

• ziplistIndex: 返回index參數(shù)指定的數(shù)據(jù)項(xiàng)的內(nèi)存位置。index可以是負(fù)數(shù)，表示從尾端向前進(jìn)行索引。

• ziplistNext和ziplistPrev分別返回一個(gè)ziplist中指定數(shù)據(jù)項(xiàng)p的后一項(xiàng)和前一項(xiàng)。

• ziplistInsert: 在ziplist的任意數(shù)據(jù)項(xiàng)前面插入一個(gè)新的數(shù)據(jù)項(xiàng)。

• ziplistDelete: 刪除指定的數(shù)據(jù)項(xiàng)。

• ziplistFind: 查找給定的數(shù)據(jù)（由vstr和vlen指定）。注意它有一個(gè)skip參數(shù)，表示查找的時(shí)候每次比較之間要跳過幾個(gè)數(shù)據(jù)項(xiàng)。為什么會(huì)有這么一個(gè)參數(shù)呢？其實(shí)這個(gè)參數(shù)的主要用途是當(dāng)用ziplist表示hash結(jié)構(gòu)的時(shí)候，是按照一個(gè)field，一個(gè)value來依次存入ziplist的。也就是說，偶數(shù)索引的數(shù)據(jù)項(xiàng)存field，奇數(shù)索引的數(shù)據(jù)項(xiàng)存value。當(dāng)按照field的值進(jìn)行查找的時(shí)候，就需要把奇數(shù)項(xiàng)跳過去。

• ziplistLen: 計(jì)算ziplist的長(zhǎng)度（即包含數(shù)據(jù)項(xiàng)的個(gè)數(shù)）。

ziplist的插入邏輯解析

ziplist的相關(guān)接口的具體實(shí)現(xiàn)，還是有些復(fù)雜的，限于篇幅的原因，我們這里只結(jié)合代碼來講解插入的邏輯。插入是很有代表性的操作，通過這部分來一窺ziplist內(nèi)部的實(shí)現(xiàn)，其它部分的實(shí)現(xiàn)我們也就會(huì)很容易理解了。

ziplistPush和ziplistInsert都是插入，只是對(duì)于插入位置的限定不同。它們?cè)趦?nèi)部實(shí)現(xiàn)都依賴一個(gè)名為__ziplistInsert的內(nèi)部函數(shù)，其代碼如下（出自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;
}

我們來簡(jiǎn)單解析一下這段代碼：

• 這個(gè)函數(shù)是在指定的位置p插入一段新的數(shù)據(jù)，待插入數(shù)據(jù)的地址指針是s，長(zhǎng)度為slen。插入后形成一個(gè)新的數(shù)據(jù)項(xiàng)，占據(jù)原來p的配置，原來位于p位置的數(shù)據(jù)項(xiàng)以及后面的所有數(shù)據(jù)項(xiàng)，需要統(tǒng)一向后移動(dòng)，給新插入的數(shù)據(jù)項(xiàng)留出空間。參數(shù)p指向的是ziplist中某一個(gè)數(shù)據(jù)項(xiàng)的起始位置，或者在向尾端插入的時(shí)候，它指向ziplist的結(jié)束標(biāo)記<zlend>。

• 函數(shù)開始先計(jì)算出待插入位置前一個(gè)數(shù)據(jù)項(xiàng)的長(zhǎng)度prevlen。這個(gè)長(zhǎng)度要存入新插入的數(shù)據(jù)項(xiàng)的<prevrawlen>字段。

• 然后計(jì)算當(dāng)前數(shù)據(jù)項(xiàng)占用的總字節(jié)數(shù)reqlen，它包含三部分：<prevrawlen>, <len>和真正的數(shù)據(jù)。其中的數(shù)據(jù)部分會(huì)通過調(diào)用zipTryEncoding先來嘗試轉(zhuǎn)成整數(shù)。

• 由于插入導(dǎo)致的ziplist對(duì)于內(nèi)存的新增需求，除了待插入數(shù)據(jù)項(xiàng)占用的reqlen之外，還要考慮原來p位置的數(shù)據(jù)項(xiàng)（現(xiàn)在要排在待插入數(shù)據(jù)項(xiàng)之后）的<prevrawlen>字段的變化。本來它保存的是前一項(xiàng)的總長(zhǎng)度，現(xiàn)在變成了保存當(dāng)前插入的數(shù)據(jù)項(xiàng)的總長(zhǎng)度。這樣它的<prevrawlen>字段本身需要的存儲(chǔ)空間也可能發(fā)生變化，這個(gè)變化可能是變大也可能是變小。這個(gè)變化了多少的值nextdiff，是調(diào)用zipPrevLenByteDiff計(jì)算出來的。如果變大了，nextdiff是正值，否則是負(fù)值。

• 現(xiàn)在很容易算出來插入后新的ziplist需要多少字節(jié)了，然后調(diào)用ziplistResize來重新調(diào)整大小。ziplistResize的實(shí)現(xiàn)里會(huì)調(diào)用allocator的zrealloc，它有可能會(huì)造成數(shù)據(jù)拷貝。

• 現(xiàn)在額外的空間有了，接下來就是將原來p位置的數(shù)據(jù)項(xiàng)以及后面的所有數(shù)據(jù)都向后挪動(dòng)，并為它設(shè)置新的<prevrawlen>字段。此外，還可能需要調(diào)整ziplist的<zltail>字段。

• 最后，組裝新的待插入數(shù)據(jù)項(xiàng)，放在位置p。

hash與ziplist

hash是Redis中可以用來存儲(chǔ)一個(gè)對(duì)象結(jié)構(gòu)的比較理想的數(shù)據(jù)類型。一個(gè)對(duì)象的各個(gè)屬性，正好對(duì)應(yīng)一個(gè)hash結(jié)構(gòu)的各個(gè)field。

我們?cè)诰W(wǎng)上很容易找到這樣一些技術(shù)文章，它們會(huì)說存儲(chǔ)一個(gè)對(duì)象，使用hash比string要節(jié)省內(nèi)存。實(shí)際上這么說是有前提的，具體取決于對(duì)象怎么來存儲(chǔ)。如果你把對(duì)象的多個(gè)屬性存儲(chǔ)到多個(gè)key上（各個(gè)屬性值存成string），當(dāng)然占的內(nèi)存要多。但如果你采用一些序列化方法，比如 Protocol Buffers，或者 Apache Thrift，先把對(duì)象序列化為字節(jié)數(shù)組，然后再存入到Redis的string中，那么跟hash相比，哪一種更省內(nèi)存，就不一定了。

當(dāng)然，hash比序列化后再存入string的方式，在支持的操作命令上，還是有優(yōu)勢(shì)的：它既支持多個(gè)field同時(shí)存取（hmset/hmget），也支持按照某個(gè)特定的field單獨(dú)存取（hset/hget）。

實(shí)際上，hash隨著數(shù)據(jù)的增大，其底層數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)是會(huì)發(fā)生變化的，當(dāng)然存儲(chǔ)效率也就不同。在field比較少，各個(gè)value值也比較小的時(shí)候，hash采用ziplist來實(shí)現(xiàn)；而隨著field增多和value值增大，hash可能會(huì)變成dict來實(shí)現(xiàn)。當(dāng)hash底層變成dict來實(shí)現(xiàn)的時(shí)候，它的存儲(chǔ)效率就沒法跟那些序列化方式相比了。

當(dāng)我們?yōu)槟硞€(gè)key第一次執(zhí)行 hset key field value 命令的時(shí)候，Redis會(huì)創(chuàng)建一個(gè)hash結(jié)構(gòu)，這個(gè)新創(chuàng)建的hash底層就是一個(gè)ziplist。

robj *createHashObject(void) {
    unsigned char *zl = ziplistNew();
    robj *o = createObject(OBJ_HASH, zl);
    o->encoding = OBJ_ENCODING_ZIPLIST;
    return o;
}

上面的createHashObject函數(shù)，出自object.c，它負(fù)責(zé)的任務(wù)就是創(chuàng)建一個(gè)新的hash結(jié)構(gòu)?？梢钥闯?，它創(chuàng)建了一個(gè)type = OBJ_HASH但encoding = OBJ_ENCODING_ZIPLIST的robj對(duì)象。

實(shí)際上，本文前面給出的那個(gè)ziplist實(shí)例，就是由如下兩個(gè)命令構(gòu)建出來的。

hset user:100 name tielei
hset user:100 age 20

每執(zhí)行一次hset命令，插入的field和value分別作為一個(gè)新的數(shù)據(jù)項(xiàng)插入到ziplist中（即每次hset產(chǎn)生兩個(gè)數(shù)據(jù)項(xiàng)）。

當(dāng)隨著數(shù)據(jù)的插入，hash底層的這個(gè)ziplist就可能會(huì)轉(zhuǎn)成dict。那么到底插入多少才會(huì)轉(zhuǎn)呢？

還記得本文開頭提到的兩個(gè)Redis配置嗎？

hash-max-ziplist-entries 512
hash-max-ziplist-value 64

這個(gè)配置的意思是說，在如下兩個(gè)條件之一滿足的時(shí)候，ziplist會(huì)轉(zhuǎn)成dict：

• 當(dāng)hash中的數(shù)據(jù)項(xiàng)（即field-value對(duì)）的數(shù)目超過512的時(shí)候，也就是ziplist數(shù)據(jù)項(xiàng)超過1024的時(shí)候（請(qǐng)參考t_hash.c中的hashTypeSet函數(shù)）。

• 當(dāng)hash中插入的任意一個(gè)value的長(zhǎng)度超過了64的時(shí)候（請(qǐng)參考t_hash.c中的hashTypeTryConversion函數(shù)）。

Redis的hash之所以這樣設(shè)計(jì)，是因?yàn)楫?dāng)ziplist變得很大的時(shí)候，它有如下幾個(gè)缺點(diǎn)：

• 每次插入或修改引發(fā)的realloc操作會(huì)有更大的概率造成內(nèi)存拷貝，從而降低性能。

• 一旦發(fā)生內(nèi)存拷貝，內(nèi)存拷貝的成本也相應(yīng)增加，因?yàn)橐截惛蟮囊粔K數(shù)據(jù)。

• 當(dāng)ziplist數(shù)據(jù)項(xiàng)過多的時(shí)候，在它上面查找指定的數(shù)據(jù)項(xiàng)就會(huì)性能變得很低，因?yàn)閦iplist上的查找需要進(jìn)行遍歷。

上述內(nèi)容就是Redis中內(nèi)部數(shù)據(jù)結(jié)構(gòu)ziplist的作用是什么，你們學(xué)到知識(shí)或技能了嗎？如果還想學(xué)到更多技能或者豐富自己的知識(shí)儲(chǔ)備，歡迎關(guān)注億速云行業(yè)資訊頻道。