Redis数据结构之——ziplist

基层搬砖的Panda

2705人浏览 · 2022-11-10 23:01:14

基层搬砖的Panda · 2022-11-10 23:01:14 发布

写在前面

以下内容是基于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.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;
}