在 Redis 中，list 有兩種存儲(chǔ)方式：雙鏈表（LinkedList）和壓縮雙鏈表（ziplist）。雙鏈表即普通數(shù)據(jù)結(jié)構(gòu)中遇到的，在 adlist.h 和 adlist.c 中實(shí)現(xiàn)。壓縮雙鏈表以連續(xù)的內(nèi)存空間來表示雙鏈表，壓縮雙鏈表節(jié)省前驅(qū)和后驅(qū)指針的空間（8b），這在小的list 上，壓縮效率是非常明顯的，因?yàn)橐粋€(gè)普通的雙鏈表中，前驅(qū)后驅(qū)指針在 64 位機(jī)器上需分別占用 8B；壓縮雙鏈表在 ziplist.h 和 ziplist.c 中實(shí)現(xiàn)。這篇主要詳述壓縮雙鏈表，普通雙鏈表可以參看其他。

壓縮雙鏈表的具體實(shí)現(xiàn)

在壓縮雙鏈表中，節(jié)省了前驅(qū)和后驅(qū)指針的空間，在 64 位機(jī)器上共節(jié)省了 8 個(gè)字節(jié)，這讓數(shù)據(jù)在內(nèi)存中更為緊湊。只要清晰的描述每個(gè)數(shù)據(jù)項(xiàng)的邊界，就可以輕易得到前驅(qū)后驅(qū)數(shù)據(jù)項(xiàng)的位置，ziplist 就是這么做的。

ziplist 的格式可以表示為：

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

zlbytes 是 ziplist 占用的空間；zltail 是最后一個(gè)數(shù)據(jù)項(xiàng)的偏移位置，這方便逆向遍歷鏈表，也是雙鏈表的特性；zllen 是數(shù)據(jù)項(xiàng)entry 的個(gè)數(shù)；zlend 就是 255，占 1B。

下面詳細(xì)展開 entry 的結(jié)構(gòu)。entry 的格式即為典型的 type-lenght-value，即 TLV，表述如下：

|<prelen><<encoding+lensize><len>><data>|
|---1----------------2--------------3---|

域 1）是前驅(qū)數(shù)據(jù)項(xiàng)的大小。因?yàn)椴挥妹枋銮膀?qū)的數(shù)據(jù)類型，描述較為簡單。

域 2）是此數(shù)據(jù)項(xiàng)的的類型和數(shù)據(jù)大小。為了節(jié)省空間，redis 預(yù)設(shè)定了多種長度的字符串和整數(shù)。

3 種長度的字符串：

#define ZIP_STR_06B (0 << 6)
#define ZIP_STR_14B (1 << 6)
#define ZIP_STR_32B (2 << 6)

5 種長度的整數(shù)：

#define ZIP_INT_16B (0xc0 | 0<<4)
#define ZIP_INT_32B (0xc0 | 1<<4)
#define ZIP_INT_64B (0xc0 | 2<<4)
#define ZIP_INT_24B (0xc0 | 3<<4)
#define ZIP_INT_8B 0xfe

域3）為真正的數(shù)據(jù)。透過 ziplist 查找函數(shù) ziplistFind()，來熟悉 ziplist entry 的數(shù)據(jù)格式：

// 在ziplist 中查找數(shù)據(jù)項(xiàng)
/* 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. */
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) {
    unsigned int prevlensize, encoding, lensize, len;
    unsigned char *q;
    ZIP_DECODE_PREVLENSIZE(p, prevlensize);

    // 跳過前驅(qū)數(shù)據(jù)項(xiàng)大小，解析數(shù)據(jù)項(xiàng)大小
    // len 為data 大小
    // lensize 為len 所占內(nèi)存大小
    ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
    // q 指向data
    q = p + prevlensize + lensize;
    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 {
        // 整數(shù)比較
        /* 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 解析為整數(shù)
                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. */
                    // 不能編碼為數(shù)字?。?！會(huì)導(dǎo)致當(dāng)前查找的數(shù)據(jù)項(xiàng)被跳過
                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) {
        // 讀取整數(shù)
            long long ll = zipLoadInteger(q, encoding);
        if (ll == vll) {
            return p;
            }
        }
    }
        /* Reset skip count */
        skipcnt = skip;
    } else {
        /* Skip entry */
        skipcnt--;
        }
        // 移動(dòng)到ziplist 的下一個(gè)數(shù)據(jù)項(xiàng)
        /* Move to next entry */
        p = q + len;
    }
  // 沒有找到
  return NULL;
}

注意，ziplist 每次插入新的數(shù)據(jù)都要 realloc。

為什么要用 ziplist

redis HSET 命令官網(wǎng)的描述是： Sets field in the hash stored at key to value. If key does not exist, a new key holding a hash is created. If field already exists in the hash, it is overwritten.

實(shí)際上，HSET 底層所使用的數(shù)據(jù)結(jié)構(gòu)正是上面所說的 ziplist，而不是平時(shí)所說的 hashtable. 那為什么要使用ziplist，反對(duì)的理由是查找來說，（ziplist O(N)）VS（hashtable O(1)）？ redis 可是為內(nèi)存節(jié)省想破了頭。首先 ziplist 比 hashtable 更節(jié)省內(nèi)存，再者，redis 考慮到如果數(shù)據(jù)緊湊的 ziplist 能夠放入 CPU 緩存（hashtable 很難，因?yàn)樗欠蔷€性的），那么查找算法甚至?xí)?hashtable 要快！。ziplist 由此有性能和內(nèi)存空間的優(yōu)勢。

上一篇：Redis 與 Memcache下一篇：Redis 數(shù)據(jù)淘汰機(jī)制