Redis数据结构之——ziplist

写在前面

以下内容是基于Redis 6.2.6 版本整理总结

一、压缩列表（ziplist）

当一个哈希键只包含少量键值对，并且每个键值对的键和值要么是小整数，要么是短字符串，Redis就会采用压缩列表作为哈希键的底层实现。

1.1 压缩列表的构成

压缩列表是Redis为节约内存而开发的，是由一系列特殊编码的连续内存组成。一个压缩列表可以包含任意多个节点，每个节点可以保存一个小整数或者一个短的字符串。

ziplist 的结构如下：

各字段说明：

• zlbytes（4 字节）： ziplist占用总的字节数
• zltail（4 字节）: ziplist 最后一个 entry 距离起始位置偏移的字节数
• zllen（2 字节）: ziplist 中 entry 的个数
• zlend（1 字节）：结束符（ziplist 以0xFF作为结束）

举个栗子：

说明：ziplist 的总长度为96字节（0x60的十进制），最后一个entry距离ziplist起始位置偏移了75字节（0x4B的十进制），ziplist中此时有3（0x03的十进制）个entry。

entry的结构如下:

各字段说明：
pre_entry_len：上一个entry的长度。占用的字节数取决于上一个节点的长度，如果上一个节点的长度小于254字节，pre_entry_len就占1个字节；如果大于等于254，pre_entry_len就占5个字节，而且，第一个字节会被设置为0xFE（十进制的254）。
encoding：记录该节点content属性保存数据的类型及长度。开头说了 ziplist 用来存储小整数或者短的字符串。encoding规则如下：
存储字符串：
encoding的长度有1字节、2字节、和5字节：主要根据高位的00/01/10来区分不同的编码。

存储小整数：

1.2 ziplist源码分析

1.2.1 创建ziplist

redis用ziplistNew() 函数来创建ziplist。采用zmalloc分配空间，初始化ziplist的 header 和 end，共 11 个字节。

#define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))
#define ZIPLIST_END_SIZE        (sizeof(uint8_t))

/* Create a new empty ziplist. */
unsigned char *ziplistNew(void) {
    // bytes = 4 + 4 + 2 + 1 = 11 字节
    unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;
    unsigned char *zl = zmalloc(bytes);

    // 初始化 zlbytes = 11
    ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
    // 初始化 zltail = 10，此时还没有entry
    ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
    // 初始化 zllen = 10
    ZIPLIST_LENGTH(zl) = 0;
    // 初始化 zlend = 255
    zl[bytes-1] = ZIP_END;
    
    return zl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1.2.2 ziplist的插入

__ziplistInsert() 函数，将新节点查到给定节点之后。

/* 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, newlen;
    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 = zipRawEntryLengthSafe(zl, curlen, 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 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. */
    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;
    newlen = curlen+reqlen+nextdiff;
    zl = ziplistResize(zl,newlen);
    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. */
        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. */
        assert(zipEntrySafe(zl, newlen, p+reqlen, &tail, 1));
        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 += zipStorePrevEntryLength(p,prevlen);
    p += zipStoreEntryEncoding(p,encoding,slen);
    if (ZIP_IS_STR(encoding)) {
        memcpy(p,s,slen);
    } else {
        zipSaveInteger(p,value,encoding);
    }
    ZIPLIST_INCR_LENGTH(zl,1);
    return zl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

二、总结

1. ziplist是Redis为了节约内存而实现的一种顺序型数据结构
2. 压缩列表中的节点用来存储较短的字符串或小整数
3. 添加和删除节点可能会引发连锁更新，但这种概率很低

文章参考与<零声教育>的C/C++linux服务期高级架构系统教程学习