redis6.0 源碼學習（五）ziplist

文章目錄

redis6.0 源碼學習（五）ziplist
- 一、資料結構
- 二、代碼解析
- - 1、建立
  - 2、查找
  - 3、插入
- 三、總結

一、資料結構

ziplist是經過特殊編碼的雙向連結清單，該清單具有很高的記憶體效率。它存儲字元串和整數值，其中整數被編碼為實際整數，而不是一系列個字元。它允許對清單的兩側進行push和pop操作且複雜度為O(1)。但是由于每個操作都需要重新配置設定ziplist使用的記憶體，實際複雜度與ziplist使用的記憶體量有關。

下圖是ziplist得示意圖：

redis6.0 源碼學習（五）ziplistredis6.0 源碼學習（五）ziplist

)

各個字段詳細解釋如下：

屬性	類型	長度	用途
zlbytes	uint32_t	4位元組	記錄整個壓縮清單占用的記憶體位元組數，在對壓縮清單進行記憶體重配置設定或者計算zlend的位置時使用。
zltail	uint32_t	4位元組	記錄壓縮清單尾節點距離壓縮清單起始位址有多少個位元組，通過這個偏移量，程式可以直接獲得壓縮清單的表尾節點位址
zllen	uint16_t	2位元組	記錄了壓縮清單的節點數量。當這個屬性的值小于65535時（即：小于UINT16_MAX），這個屬性的值就是壓縮清單的節點數量，但是當這個值等于UINT16_MAX時，需要周遊整個壓縮清單才能獲得其節點數量
entryX	清單節點	不定	壓縮表的各個節點，X代表數量不定
zlend	uint8_t	1位元組	特殊常數值（OxFF,也就是255）。用于标記壓縮清單的末端。

ziplist中的每個entry均包含兩個資訊：prevlen 和 encoding。prevlen 字段：存儲前一個條目的長度，以便能夠從後到前周遊清單。encoding表示entry類型，整數或字元串，對于字元串，還表示字元串有效負載的長度。是以，完整的entry存儲形式如下：

redis6.0 源碼學習（五）ziplistredis6.0 源碼學習（五）ziplist

)

在存儲較小的整數的時候，entry-data字段會不存在，因為也存儲在encoding字段中了。

1、prevlen：針對prevlen的大小不同，prevlen占用的字段長度也不一樣。

prevlen < 254

prevlen占用1個位元組 8位
prevlen > 254

此時prevlen占用5個位元組，第一個位元組為 0xFE,後續四個位元組為真正的長度。 0xFE表示是下一個entry一個大的值。

2、encoding 根據entry-data存入的是字元串還是整數具有不同的格式。具體如下：

a：字元串

redis6.0 源碼學習（五）ziplistredis6.0 源碼學習（五）ziplist

當字元串小于63位元組時(2^6)，節點存為上圖的第一種類型，高2位為00，低6位表示data的長度。

當字元串小于16383位元組時(2^14)，節點存為上圖的第二種類型，高2位為01，後續14位表示data的長度。

當字元串小于4294967296位元組時(2^32)，節點存為上圖的第三種類型，高2位為10，下一位元組起連續32位表示data的長度。

b：整數：整數節點的encoding的長度為8位，其中高2位用來區分整數節點和字元串節點（高2位為11時是整數節點），低6位用來區分整數節點的類型，具體如下：

redis6.0 源碼學習（五）ziplistredis6.0 源碼學習（五）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 int ziplistGet(unsigned char *p, unsigned char **sval, unsigned int *slen, long long *lval);
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 *ziplistDeleteRange(unsigned char *zl, int index, unsigned int num);
unsigned int ziplistCompare(unsigned char *p, unsigned char *s, unsigned int slen);
unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip);
unsigned int ziplistLen(unsigned char *zl);
size_t ziplistBlobLen(unsigned char *zl);

1、建立

可以對照圖1 ziplist結構示意圖看這個建立的過程。

/* Create a new empty ziplist. */
unsigned char *ziplistNew(void) {
    unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;  //<zlbytes>4位元組<zltail>4位元組<zllen>2位元組<zlend>1位元組，沒有entry節點
    unsigned char *zl = zmalloc(bytes); //申請記憶體
    ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);//zlbytes指派
    ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);//zltail指派
    ZIPLIST_LENGTH(zl) = 0; //zllen指派
    zl[bytes-1] = ZIP_END; //zlend指派
    return zl;
}

2、查找

/* Find pointer to the entry equal to the specified entry. Skip 'skip' entries
 * between every comparison. Returns NULL when the field could not be found. */
//傳回p節點之後data與vstr(長度是vlen)相等的節點，隻找p節點之後每隔skip的節點
//時間複雜度 O(n)
unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip) {
    int skipcnt = 0;
    unsigned char vencoding = 0;
    long long vll = 0;

    while (p[0] != ZIP_END) {  /* ZIP_END: Special "end of ziplist" entry. */
        unsigned int prevlensize, encoding, lensize, len;
        unsigned char *q;

        ZIP_DECODE_PREVLENSIZE(p, prevlensize); //擷取prevlen的位元組數1還是5
        /* 擷取'ptr'中 entry encoding type 和 data length (字元串長度或者整數使用的bytes ) 。
         * encoding變量： entry的encoding值
         *lensize變量：encode entry所需要的bytes數 
         *len變量：  hold the entry length. */        
        ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
        q = p + prevlensize + lensize; //目前節點的data

        if (skipcnt == 0) {
            /* Compare current entry with specified entry */
            if (ZIP_IS_STR(encoding)) {//判斷目前節點是不是字元串節點
                if (len == vlen && memcmp(q, vstr, vlen) == 0) { //字元串比較
                    return p;
                }
            } else {
                /* Find out if the searched field can be encoded. Note that
                 * we do it only the first time, once done vencoding is set
                 * to non-zero and vll is set to the integer value. */
                if (vencoding == 0) { //這個代碼塊隻會執行一次,判斷vstr能夠用整數表示                  
                    /* 校驗'vstr'指向的内容能否轉換成整數，'vll'存這個整數值 'encoding'存編碼格式 */
                    if (!zipTryEncoding(vstr, vlen, &vll, &vencoding)) {
                        /* If the entry can't be encoded we set it to
                         * UCHAR_MAX so that we don't retry again the next
                         * time. */
                        vencoding = UCHAR_MAX;
                    }
                    /* Must be non-zero by now */
                    assert(vencoding); 
                }

                /* Compare current entry with specified entry, do it only
                 * if vencoding != UCHAR_MAX because if there is no encoding
                 * possible for the field it can't be a valid integer. */
                if (vencoding != UCHAR_MAX) { //entry位址的内容轉換成整數
                    long long ll = zipLoadInteger(q, encoding);
                    if (ll == vll) {
                        return p; //相等的話傳回
                    }
                }
            }

            /* Reset skip count */
            skipcnt = skip;
        } else {
            /* Skip entry */
            skipcnt--;
        }

        /* Move to next entry */
        p = q + len;
    }

    return NULL;
}

3、插入

/* Insert an entry at "p". */
unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
    return __ziplistInsert(zl,p,s,slen);
}

/* Insert item at "p". */
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. */
    // 找出待插入節點的前置節點長度
    // 如果p[0]不指向清單末端，說明清單非空，并且p指向其中一個節點
    if (p[0] != ZIP_END) {
         // 擷取前置節點p的長度和編碼該長度需要的位元組
        ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
    } else {        
        unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
        if (ptail[0] != ZIP_END) {// 如果p指向清單末端，表示清單為空
            prevlen = zipRawEntryLength(ptail);
        }
    }

    /* See if the entry can be encoded */
    if (zipTryEncoding(s,slen,&value,&encoding)) {//嘗試encoding成整數
        /* 'encoding' is set to the appropriate integer encoding */
        reqlen = zipIntSize(encoding); //擷取編碼長度
    } else {
        /* 'encoding' is untouched, however zipStoreEntryEncoding 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 += zipStorePrevEntryLength(NULL,prevlen); // 擷取前置節點的編碼長度
    reqlen += zipStoreEntryEncoding(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. */
    // 隻要不是清單的末端插入，需要計算出下一個元素儲存本元素prevlen字段空間是否足夠, 不夠時計算出欠缺的內插補點 
    // nextdiff大于0，那就說明需要對目前p指向的節點的header進行擴充
    int forcelarge = 0;
    nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
    if (nextdiff == -4 && reqlen < 4) {
        nextdiff = 0;
        forcelarge = 1;
    }

    /* Store offset because a realloc may change the address of zl. */
    offset = p-zl;// 存儲p相對于清單zl的偏移位址
    zl = ziplistResize(zl,curlen+reqlen+nextdiff); // 重新配置設定空間，curlen目前清單的長度
    p = zl+offset; // 重新擷取p的值

    /* 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);/* 移動p原有位置和後面的内容到新的位置 */      

        /* Encode this entry's raw length in the next entry. */   
        if (forcelarge)
            zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
        else
            zipStorePrevEntryLength(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. */
        // 如果新節點後面有多個節點，那麼表尾的偏移量需要算上nextdiff的值
        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 */
     // 當nextdiff不為0時，表示需要新節點的後繼節點對頭部進行擴充
    //說明下一個元素需要擴充空間存放prevlen字段, 由于下一個元素空間變大, 有可能引起下下一個元素空間需要擴充, 下面函數檢測後面元素, 并在需要時重置元素prevlen長度
    if (nextdiff != 0) {
        // 需要對p所指向的header進行擴充更新
        // 有可能會引起連鎖更新
        offset = p-zl;
        zl = __ziplistCascadeUpdate(zl,p+reqlen);
        p = zl+offset;
    }

    /* Write the entry */
    p += zipStorePrevEntryLength(p,prevlen); // 将新節點前置節點的長度寫入新節點的header
    p += zipStoreEntryEncoding(p,encoding,slen); // 将新節點的值長度寫入新節點的header
    if (ZIP_IS_STR(encoding)) { // 寫入節點值
        memcpy(p,s,slen);
    } else {
        zipSaveInteger(p,value,encoding);
    }
    ZIPLIST_INCR_LENGTH(zl,1);  // 更新清單節點計數
    return zl;
}

三、總結

ziplist是為節省記憶體空間而生的。
ziplist是一個為Redis專門提供的底層資料結構之一，本身可以有序也可以無序。當作hash的底層實作時，節點之間沒有順序；當作為zset的底層實作時，節點之間會按照大小順序排列。

redis6.0 源碼學習（五）ziplistredis6.0 源碼學習（五）ziplist

redis6.0 源碼學習（五）ziplist

文章目錄

一、資料結構

二、代碼解析

1、建立

2、查找

3、插入

三、總結

繼續閱讀

秒懂JVM的三大參數類型，就靠這十個小實驗了初級—中級—進階三個級别的大廠面試真題阿裡雲——Java 實習生/初級美團——Java 中級螞蟻金服——Java 進階基礎篇JVM 篇MySQL 篇Redis 篇

CentOs7 安裝redis4.0 遇到的坑一、CentOs7連接配接網絡二、make檔案的時候出錯三、安裝ruby的redis插件時候報錯最後

docker 搭建Redis 問題解決

如何解決Redis緩存擊穿、雪崩、穿透問題

java 版本的redis-stat不能運作在背景和daemon

redis管理常用指令

django短信驗證碼的後端實作

Redis訂閱了一段時間後訂閱失效了（ redisTemplate.convertAndSend）

2022秋招面試總結（cpp+java+測開）百度測開一面位元組後端一面蝦皮後端一面蝦皮後端二面

資料遷移方法資料遷移原則資料遷移之雙寫方案資料遷移之級聯同步方案

微服務-性能壓測\緩存redis和分布式鎖redisson和SpringCache

Nacos 2.0 更新前後性能對比壓測

Spring資料和Redis

redis叢集資料一緻性_RedisRaft為Redis叢集帶來強大的資料一緻性

supervisor 管理redis 和httpd 環境centos7

Redis簡介一(單機版)發展曆程Redis