精华内容
下载资源
问答
  • ziplist
    2020-05-17 16:40:13

    版本6.0.1
    ziplist.c

    初始化ziplist
    /* Create a new empty ziplist. */
    unsigned char *ziplistNew(void) {
        unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;
        unsigned char *zl = zmalloc(bytes); // 分配11个字节的内存
        ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
        ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
        ZIPLIST_LENGTH(zl) = 0;
        zl[bytes-1] = ZIP_END;
        return zl;
    }
    
    /* The size of a ziplist header: two 32 bit integers for the total
     * bytes count and last item offset. One 16 bit integer for the number
     * of items field. */
    #define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))
    // header占10bytes,其中zlbytes占4bytes,zltail占4bytes,zllen占2bytes
    
    /* Size of the "end of ziplist" entry. Just one byte. */
    #define ZIPLIST_END_SIZE        (sizeof(uint8_t))
    // 最后一个entry占1byte
    

    zmalloc见zmalloc

    /* Return total bytes a ziplist is composed of. */
    #define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl)))
    

    ziplist起始的4bytes表示ziplist占用的字节数
    intrev32ifbe用于大端到小端的转换,详见endianconv.h

    /* Return the offset of the last item inside the ziplist. */
    #define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
    

    ZIPLIST_TAIL_OFFSET用于对zltail进行赋值,表示距离最后一个entry的字节的长度

    /* Return the length of a ziplist, or UINT16_MAX if the length cannot be
     * determined without scanning the whole ziplist. */
    #define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
    

    返回zllen的值。
    ziplist的最后一个字节值为255,表示ziplist的结束。

    ziplist插入元素
    unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where) {
        unsigned char *p;
        p = (where == ZIPLIST_HEAD) ? ZIPLIST_ENTRY_HEAD(zl) : ZIPLIST_ENTRY_END(zl);
        return __ziplistInsert(zl,p,s,slen);
    }
    

    s是插入元素,slen是长度,where表示插入位置,可以为头部或尾部。

    /* Return the pointer to the first entry of a ziplist. */
    #define ZIPLIST_ENTRY_HEAD(zl)  ((zl)+ZIPLIST_HEADER_SIZE)
    
    /* Return the pointer to the last byte of a ziplist, which is, the
     * end of ziplist FF entry. */
    #define ZIPLIST_ENTRY_END(zl)   ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)
    
    /* Return the pointer to the last entry of a ziplist, using the
     * last entry offset inside the ziplist header. */
    #define ZIPLIST_ENTRY_TAIL(zl)  ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))
    

    分别用于返回第一个entry、最后一个字节和最后一个entry的指针

    /* 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; // curlen是当前ziplist的长度
        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) { // p是某个entry的指针,如果不是最后一个用于标志结束的entry,解析prevlen和占用的字节数
            ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
        } else { // 如果是最后一个字节
            unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl); // 最后一个entry的指针
            if (ptail[0] != ZIP_END) { // 如果是空ziplist,最后一个entry为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 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;
        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. */
            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. */
            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 += 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;
    }
    
    

    宏ZIP_DECODE_PREVLEN定义如下

    /* Return the number of bytes used to encode the length of the previous
     * entry. The length is returned by setting the var 'prevlensize'. */
    #define ZIP_DECODE_PREVLENSIZE(ptr, prevlensize) do {                          \
        if ((ptr)[0] < ZIP_BIG_PREVLEN) { // ZIP_BIG_PREVLEN值为254,标志prevlen占1个字节还是5个字节,占5个字节时,第一个字节固定为254                                  \
            (prevlensize) = 1;                                                     \
        } else {                                                                   \
            (prevlensize) = 5;                                                     \
        }                                                                          \
    } while(0);
    
    /* Return the length of the previous element, and the number of bytes that
     * are used in order to encode the previous element length.
     * 'ptr' must point to the prevlen prefix of an entry (that encodes the
     * length of the previous entry in order to navigate the elements backward).
     * The length of the previous entry is stored in 'prevlen', the number of
     * bytes needed to encode the previous entry length are stored in
     * 'prevlensize'. */
    #define ZIP_DECODE_PREVLEN(ptr, prevlensize, prevlen) do {                     \
        ZIP_DECODE_PREVLENSIZE(ptr, prevlensize); // 解析prevlen占用的字节数                                  \
        if ((prevlensize) == 1) {                                                  \
            (prevlen) = (ptr)[0]; //为1个字节时,字节值就是长度                                                 \
        } else if ((prevlensize) == 5) { //为5个字节时,后4个字节的值为占用的字节数                                          \
            assert(sizeof((prevlen)) == 4);                                    \
            memcpy(&(prevlen), ((char*)(ptr)) + 1, 4); // 将后4个字节拷贝到prevlen                            \
            memrev32ifbe(&prevlen); // 字节序转换                                             \
        }                                                                          \
    } while(0);
    

    memrev32ifbe详见endianconv.h

    /* Return the total number of bytes used by the entry pointed to by 'p'. */
    // 用于返回p指向的entry占用的字节数
    unsigned int zipRawEntryLength(unsigned char *p) {
        unsigned int prevlensize, encoding, lensize, len;
        ZIP_DECODE_PREVLENSIZE(p, prevlensize);
        ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
        return prevlensize + lensize + len;
    }
    
    // 解析entry的编码方式和数据长度
    /* Decode the entry encoding type and data length (string length for strings,
     * number of bytes used for the integer for integer entries) encoded in 'ptr'.
     * The 'encoding' variable will hold the entry encoding, the 'lensize'
     * variable will hold the number of bytes required to encode the entry
     * length, and the 'len' variable will hold the entry length. */
    #define ZIP_DECODE_LENGTH(ptr, encoding, lensize, len) do {                    \
        ZIP_ENTRY_ENCODING((ptr), (encoding));                                     \
        if ((encoding) < ZIP_STR_MASK) {                                           \
            if ((encoding) == ZIP_STR_06B) {                                       \
                (lensize) = 1;                                                     \
                (len) = (ptr)[0] & 0x3f;                                           \
            } else if ((encoding) == ZIP_STR_14B) {                                \
                (lensize) = 2;                                                     \
                (len) = (((ptr)[0] & 0x3f) << 8) | (ptr)[1];                       \
            } else if ((encoding) == ZIP_STR_32B) {                                \
                (lensize) = 5;                                                     \
                (len) = ((ptr)[1] << 24) |                                         \
                        ((ptr)[2] << 16) |                                         \
                        ((ptr)[3] <<  8) |                                         \
                        ((ptr)[4]);                                                \
            } else {                                                               \
                panic("Invalid string encoding 0x%02X", (encoding));               \
            }                                                                      \
        } else {                                                                   \
            (lensize) = 1;                                                         \
            (len) = zipIntSize(encoding);                                          \
        }                                                                          \
    } while(0);
    
    
    更多相关内容
  • ziplist结构在redis运用非常广泛,是列表、字典等数据类型的底层结构之一。ziplist的优点在于能够一定程度地节约内存。下面这篇文章主要给大家介绍了关于redis源码分析教程之压缩链表ziplist的相关资料,需要的朋友...
  • 本文来自对Redis内部ziplist结构的内部实现进行了详细深入的分析,ziplist是用一个字符串来实现的双向链表结构。
  • ziplist是一种为节约内存而开发的数据结构,本质是一个字节数组。 ziplist是列表键和哈希键的底层实现之一,也用于quicklist的实现。 问题思考 双向链表结构,在存储数据本身长度远小于链表节点大小的场景下,有严重...

    背景

    ziplist是一种为节约内存而开发的数据结构,本质是一个字节数组。

    ziplist是列表键和哈希键的底层实现之一,也用于quicklist的实现。

    问题思考

    双向链表结构,在存储数据本身长度远小于链表节点大小的场景下,有严重的内存浪费问题。针对这种情况,Redis设计了ziplist这种节约内存的数据结构。以下给出ziplist相关的思考问题,了解ziplist的实现原理和设计思路。

    ziplist的数据结构

    Redis没有专门定义结构体来表示ziplist,因为ziplist本质就是一个空间连续的字节数组。

    ziplist中包含多个节点(entry),每个节点存储一个字符串值或整数值,每个节点通过struct zlentry结构表示。

    ziplist的各组成部分参考如下:
    在这里插入图片描述

    可以看出,ziplist由列表头 + 列表节点 + 列表尾这三部分组成。每个组成部分作用说明如下:

    • zlbytes占4字节,用于记录整个ziplist占用内存的总字节数,对于空表来说,zlbytes等于11,源码参考ziplistNew
    #define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t)) // 8 + 2 = 10字节
    #define ZIPLIST_END_SIZE        (sizeof(uint8_t)) // 1字节
    #define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl)))  // zlbytes
    
    /* Create a new empty ziplist. */
    unsigned char *ziplistNew(void) {
        unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;	// zlbytes = 10 + 1 = 11
        unsigned char *zl = zmalloc(bytes); // 可以看出,空表分配11字节大小空间
        ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
        ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
        ZIPLIST_LENGTH(zl) = 0;
        zl[bytes-1] = ZIP_END;
        return zl;
    }
    

    ziplist为空时的内存空间如下图:
    在这里插入图片描述

    • zltail占4字节,用于记录表尾节点首地址距离ziplist起始地址有多少字节。设计这个字段的目的是为了快速定位表尾节点地址(ZIPLIST_ENTRY_TAIL)。
    • zllen占2字节,用于记录列表节点总数。注意zllen等于65535时,表示这个列表长度太大,必须通过遍历整个ziplist才能得到真实的长度。参考ziplistLen实现:
    #define UINT16_MAX 65535
    unsigned int ziplistLen(unsigned char *zl) {
        unsigned int len = 0;
        if (intrev16ifbe(ZIPLIST_LENGTH(zl)) < UINT16_MAX) {
            len = intrev16ifbe(ZIPLIST_LENGTH(zl)); // zllen < 65535时,O(1)复杂度获取ziplist长度
        } else {
            unsigned char *p = zl+ZIPLIST_HEADER_SIZE;
            while (*p != ZIP_END) {			// zllen = 65535时,O(N)复杂度获取ziplist长度
                p += zipRawEntryLength(p);
                len++;
            }
    
            /* Re-store length if small enough */
            if (len < UINT16_MAX) ZIPLIST_LENGTH(zl) = intrev16ifbe(len);
        }
        return len;
    }
    
    • zlend占1字节,用于标记ziplist的结束,内容固定为0xFF(十进制的255)

    ziplist节点构成

    ziplist中包含多个节点(entry),每个节点存储一个字符串值或整数值,每个节点通过struct zlentry结构表示。

    typedef struct zlentry {
        unsigned int prevrawlensize; /* Bytes used to encode the previous entry len*/
        unsigned int prevrawlen;     /* Previous entry len. */
        unsigned int lensize;        /* Bytes used to encode this entry type/len.
                                        For example strings have a 1, 2 or 5 bytes
                                        header. Integers always use a single byte.*/
        unsigned int len;            /* Bytes used to represent the actual entry.
                                        For strings this is just the string length
                                        while for integers it is 1, 2, 3, 4, 8 or
                                        0 (for 4 bit immediate) depending on the
                                        number range. */
        unsigned int headersize;     /* prevrawlensize + lensize. */
        unsigned char encoding;      /* Set to ZIP_STR_* or ZIP_INT_* depending on
                                        the entry encoding. However for 4 bits
                                        immediate integers this can assume a range
                                        of values and must be range-checked. */
        unsigned char *p;            /* Pointer to the very start of the entry, that
                                        is, this points to prev-entry-len field. */
    } zlentry;
    

    前面提到,ziplist本质是一个字节数组,Redis为了操作方便,才专门定义zlentry结构体,并解析某个entry的信息到zlentry中,注意ziplist字节数组本身并不存储zlentry; ziplist的每个entry结构都由三部分组成:

    • 前一节点长度信息:previous_entry_length
    • 当前节点编码信息:encoding
    • 当前节点内容:content

    ziplist节点的各组成部分示意图:
    在这里插入图片描述

    以下分别介绍这三个组成部分:

    1、前一节点长度信息 previous_entry_length

    previous_entry_length本身占1字节或5字节,用于记录前一个节点的长度,单位为字节:

    • 如果前一个节点长度小于254字节,previous_entry_length就只占1字节,直接保存前一个节点长度。
    • 如果前一个节点长度大于等于254字节,previous_entry_length就占5字节,其中第一个字节固定为0xFE,后4个字节保存前一个节点长度。

    源码参考ZIP_DECODE_PREVLENSIZE,这个宏根据前一个节点长度,返回previous_entry_length占用的字节数:

    #define ZIP_BIG_PREVLEN 254
    #define ZIP_DECODE_PREVLENSIZE(ptr, prevlensize) do {                          \
        if ((ptr)[0] < ZIP_BIG_PREVLEN) {                                          \
            (prevlensize) = 1;                                                     \
        } else {                                                                   \
            (prevlensize) = 5;                                                     \
        }                                                                          \
    } while(0)
    

    Q:为什么要设计previous_entry_length字段,有什么作用?

    A:用于支持从表尾向表头方向遍历。比如我们有指向某个节点起始地址的指针p,用p减去这个节点的previous_entry_length,就能得到前一节点的起始地址。

    访问ziplist当前节点的前一个节点,参考源码ziplistPrev的实现:

    /* Return pointer to previous entry in ziplist. */
    unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p) {
        unsigned int prevlensize, prevlen = 0;
        if (p[0] == ZIP_END) {	// p指向ZIPLIST_ENTRY_END,前一个节点就是最后一个节点,即ZIPLIST_ENTRY_TAIL
            p = ZIPLIST_ENTRY_TAIL(zl);
            return (p[0] == ZIP_END) ? NULL : p;
        } else if (p == ZIPLIST_ENTRY_HEAD(zl)) {	// p为表头,说明前一个节点为NULL
            return NULL;
        } else {
            ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);	// p减去这个节点的previous_entry_length
            assert(prevlen > 0);
            return p-prevlen;
        }
    }
    

    2、当前节点编码信息 encoding,当前节点内容content

    encoding用于记录当前节点内容的实际类型(字符串还是整数),以及长度:

    • encoding长度可以是1字节、2字节、或5字节。其中encoding最高两位为00, 01, 或10时表示存储的值类型为字符串;encoding最高两位为11表示存储的值类型为整数。

    每一种encoding对应的编码长度和content类型,参考如下源码:

    // ziplist.c
    /* Different encoding/length possibilities */
    #define ZIP_STR_MASK 0xc0			// 11000000
    #define ZIP_INT_MASK 0x30			// 00110000
    #define ZIP_STR_06B (0 << 6)		// 00bbbbbb (长度小于等于63)
    #define ZIP_STR_14B (1 << 6)		// 01bbbbbb bbbbbbbb  (长度大于63且小于等于16383)
    #define ZIP_STR_32B (2 << 6)		// 10______ bbbbbbbb bbbbbbbb bbbbbbbb bbbbbbbb(长度大于16384)
    #define ZIP_INT_16B (0xc0 | 0<<4)	// 11000000  16位整数
    #define ZIP_INT_32B (0xc0 | 1<<4)	// 11010000  32位整数
    #define ZIP_INT_64B (0xc0 | 2<<4)	// 11100000  64位整数
    #define ZIP_INT_24B (0xc0 | 3<<4)	// 11110000  24位整数
    #define ZIP_INT_8B 0xfe				// 11111110  8位整数
    
    /* 4 bit integer immediate encoding |1111xxxx| with xxxx between
     * 0001 and 1101. */
    #define ZIP_INT_IMM_MASK 0x0f   /* Mask to extract the 4 bits value. To add
                                       one is needed to reconstruct the value. */
    #define ZIP_INT_IMM_MIN 0xf1    /* 11110001 */
    #define ZIP_INT_IMM_MAX 0xfd    /* 11111101 */
    
    #define INT24_MAX 0x7fffff
    #define INT24_MIN (-INT24_MAX - 1)
    
    /* Macro to determine if the entry is a string. String entries never start
     * with "11" as most significant bits of the first byte. */
    #define ZIP_IS_STR(enc) (((enc) & ZIP_STR_MASK) < ZIP_STR_MASK)  // 判断是否为字节数组编码!!!
    
    /* Extract the encoding from the byte pointed by 'ptr' and set it into
     * 'encoding' field of the zlentry structure. */
    #define ZIP_ENTRY_ENCODING(ptr, encoding) do {  \
        (encoding) = (ptr[0]); \
        if ((encoding) < ZIP_STR_MASK) (encoding) &= ZIP_STR_MASK; \
    } while(0)
    
    /* Decode the entry encoding type and data length (string length for strings,
     * number of bytes used for the integer for integer entries) encoded in 'ptr'.
     * The 'encoding' variable will hold the entry encoding, the 'lensize'
     * variable will hold the number of bytes required to encode the entry
     * length, and the 'len' variable will hold the entry length. */
    #define ZIP_DECODE_LENGTH(ptr, encoding, lensize, len) do {                    \
        ZIP_ENTRY_ENCODING((ptr), (encoding));                                     \
        if ((encoding) < ZIP_STR_MASK) {                                           \
            if ((encoding) == ZIP_STR_06B) {                                       \
                (lensize) = 1;                                                     \
                (len) = (ptr)[0] & 0x3f;                                           \
            } else if ((encoding) == ZIP_STR_14B) {                                \
                (lensize) = 2;                                                     \
                (len) = (((ptr)[0] & 0x3f) << 8) | (ptr)[1];                       \
            } else if ((encoding) == ZIP_STR_32B) {                                \
                (lensize) = 5;                                                     \
                (len) = ((ptr)[1] << 24) |                                         \
                        ((ptr)[2] << 16) |                                         \
                        ((ptr)[3] <<  8) |                                         \
                        ((ptr)[4]);                                                \
            } else {                                                               \
                panic("Invalid string encoding 0x%02X", (encoding));               \
            }                                                                      \
        } else {                                                                   \
            (lensize) = 1;                                                         \
            (len) = zipIntSize(encoding);                                          \
        }                                                                          \
    } while(0)
    

    整数编码:

    encodingencoding长度content长度
    11111110 (ZIP_INT_8B)1字节8位整数
    11000000 (ZIP_INT_16B)1字节16位整数
    11110000(ZIP_INT_24B)1字节24位整数
    11010000(ZIP_INT_32B)1字节32位整数
    11100000(ZIP_INT_64B)1字节64位整数
    1111xxxx1字节0-12之间的整数。此时没有content部分,值存储在encoding的xxxx四个位

    字节数组编码:

    encodingencoding说明encoding长度content长度
    00xxxxxx (ZIP_STR_06B)后6位表示字节数组的长度1字节保存长度小于等于63字节的字节数组
    01xxxxxx xxxxxxxx (ZIP_STR_14B)后14位表示字节数组的长度2字节保存长度大于63, 小于等于16383字节的字节数组
    10______ xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx (ZIP_STR_32B)最后24位表示字节数组的长度,第3-8位留空5字节保存长度大于16384,小于 2^32 - 1字节的字节数组

    总结:Redis根据ziplist节点存储内容的类型和大小,使用不同的编码表示,目的在于最大限度地节省空间。

    思考问题:创建一个ziplist编码的空列表键,并依次添加两个值"hello",“10086”,问此时ziplist的长度是多少,内容是什么样的?

    127.0.0.1:6379> info  # Redis版本必须为3.2之前的,否则列表键的默认编码为quicklist,而非ziplist!
    # Server redis_version:3.0.0 
    127.0.0.1:6379> flushdb
    127.0.0.1:6379> rpush key hello 10086 # 新增列表键,依次插入两个key "hello" "10086"
    (integer) 2
    127.0.0.1:6379> object encoding key   # 确认列表键编码为ziplist
    "ziplist"
    

    如果你真的掌握了ziplist节点构成,那么不需要运行Redis,你也可以得出答案:这个ziplist占用22字节,内存如下图所示:
    在这里插入图片描述
    以下给出GDB的验证方法和验证结果,感兴趣的可以参考:

    // 0、确认ziplist的首地址
    (gdb) p (sds)server.db[0].dict.ht[0].table[3].key
    $1 = (sds) 0x7fc6ac086288 "key" // 键
    (gdb) p *(robj *)server.db[0].dict.ht[0].table[3].v
    $2 = {type = 1, encoding = 5, lru = 13392586, refcount = 1, ptr = 0x7fc6ac035d60} // ptr即为ziplist的首地址!
    
    // 1、打印zlbytes, zltail, zllen
    (gdb) p *(int *)0x7fc6ac035d60
    $3 = 22 // zlbytes = 22
    (gdb) p *(int *)0x7fc6ac035d64
    $4 = 17 // zltail = 17
    (gdb) p *(short *)0x7fc6ac035d68
    $5 = 2  // zlen = 2
        
    // 2、以下开始打印第一个节点
    (gdb) x/xb 0x7fc6ac035d6a
    0x7fc6ac035d6a: 0x00 // previous_entry_length本身占1字节,长度为0
    (gdb) x/xb 0x7fc6ac035d6b		
    0x7fc6ac035d6b: 0x05 // encoding为00000101, 本身占1字节,表示长度为5的字节数组
    (gdb) x/5c 0x7fc6ac035d6c
    0x7fc6ac035d6c: 104 'h' 101 'e' 108 'l' 108 'l' 111 'o'	// content占5字节,存储"hello"
    // 第一个节点总长度为 1 + 1 + 5 = 7 字节
        
    // 3、以下开始打印第二个节点
    (gdb) x/xb 0x7fc6ac035d71
    0x7fc6ac035d71: 0x07 // previous_entry_length本身占1字节,长度为7
    (gdb) x/xb 0x7fc6ac035d72 
    0x7fc6ac035d72: 0xc0 // encoding为11000000, 本身占1字节, 表示16位的整数
    (gdb) p *(short *) 0x7fc6ac035d73
    $6 = 10086	// content本身占2字节,存储内容正是10086
    
    // 4、标志zlend,占1字节
    (gdb) x/xb 0x7fc6ac035d75
    0x7fc6ac035d75: 0xff   
    

    为什么要设计ziplist

    还是考虑这个列表键: "hello" -> "10086"

    • 如果用ziplist编码,仅需22个字节存储。
    • 如果用linkedlist编码,以64位环境为例,光链表节点就需要2 * sizeof(listNode) = 48个字节,这个大小远超过了数据本身的大小,导致严重的内存浪费。

    可以看出,ziplist设计思想是以时间换空间,目的是节省宝贵的内存资源。

    Redis中,ziplist是列表键和哈希键的底层实现之一,也用于quicklist的实现。

    ziplist相关操作

    压缩列表的增、删、改、查API如下:

    API功能时间复杂度
    ziplistPush插入指定节点到表头或表尾平均O(N),连锁更新场景为O(N^2)
    ziplistDelete删除指定节点平均O(N),连续更新场景为O(N^2)
    ziplistFind查找指定节点O(N^2),因为节点值可能是字符串,而字符串比较复杂度为O(N)
    ziplistNext返回给定节点的下一个节点O(1)
    ziplistPrev返回给定节点的前一个节点O(1)

    查找指定节点

    源码参考ziplistFind,时间复杂度为O(N^2),因为节点值可能是字符串,而字符串比较复杂度为O(N)

    // 功能:寻找ziplist中,节点值和vstr相等的节点并返回
    // skip表示跳过的节点数
    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);
            ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
            q = p + prevlensize + lensize;	// 此时q指向节点p的content
    
            if (skipcnt == 0) {
                /* Compare current entry with specified entry */
                if (ZIP_IS_STR(encoding)) {	// 如果是字符串,memcmp比较是否相等,复杂度O(N)
                    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. */
                    // 对于传入的vstr, 解码动作只需做一次, vencoding相当于一个flag
                    if (vencoding == 0) {
                        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) {
                        long long ll = zipLoadInteger(q, encoding);
                        if (ll == vll) {
                            return p;
                        }
                    }
                }
    
                /* Reset skip count */
                skipcnt = skip;
            } else {
                /* Skip entry */
                skipcnt--;
            }
            /* Move to next entry */ 
            // q指向content, len就是content的长度, 所以 q + len即为下一个节点的首地址!!
            p = q + len;	
        }
        return NULL;
    }
    

    连锁更新问题

    前面提到,ziplist中每个节点的previous_entry_length记录了前一个节点的长度,考虑在表头插入节点的场景:

    如果列表所有节点长度都在250-253字节之前,且插入节点大于等于254字节,就会导致所有节点的previous_entry_length都必须从1字节扩展为5字节, 即触发了连锁更新

    以下举例说明这个问题:给定一个长度为3的,每个节点大小均为253字节的ziplist,往表头插入一个300字节大小的节点。
    在这里插入图片描述
    注:除了新增节点会引发连锁更新,删除节点操作也可能引发连锁更新,此处不再赘述。

    思考问题:既然连锁更新的最坏复杂度为O(n^2),为什么Redis还是放心使用ziplist?

    • 因为连锁更新触发条件苛刻,只有满足存在多个连续长度为250-253之间的节点才能触发。
    • ziplist只应用于节点数少且数据小的场景,即使出现了连续更新,需要更新的节点数量也很少,不会出现性能问题。

    参考资料

    【1】《Redis设计与实现》 第7章 压缩列表

    【2】[Redis源码解析-基础数据-ziplist(压缩列表)](

    展开全文
  • ziplist到quicklist,再到listpack的启发 介绍 Redis 优化设计数据结构来提升内存利用率的时候,提到可以使用压缩列表(ziplist)来保存数据。所以现在你应该也知道,ziplist 的最大特点,就是它被设计成一种内存...

    从ziplist到quicklist,再到listpack的启发

    介绍 Redis 优化设计数据结构来提升内存利用率的时候,提到可以使用压缩列表(ziplist)来保存数据。所以现在你应该也知道,ziplist 的最大特点,就是它被设计成一种内存紧凑型的数据结构,占用一块连续的内存空间,以达到节省内存的目的。

    但是,在计算机系统中,任何一个设计都是有利有弊的。对于 ziplist 来说,这个道理同样成立。虽然 ziplist 节省了内存开销,可它也存在两个设计代价:

    • 一是不能保存过多的元素,否则访问性能会降低;
    • 二是不能保存过大的元素,否则容易导致内存重新分配,甚至可能引发连锁更新的问题。所谓的连锁更新,简单来说,就是 ziplist 中的每一项都要被重新分配内存空间,造成 ziplist 的性能降低。

    因此,针对 ziplist 在设计上的不足,Redis 代码在开发演进的过程中,新增设计了两种数据结构:

    • quicklist
    • listpack

    这两种数据结构的设计目标,就是尽可能地保持 ziplist 节省内存的优势,同时避免 ziplist 潜在的性能下降问题。今天这节课,我就来给你详细介绍下 quicklist 和 listpack 的设计思想和实现思路,不过在具体讲解这两种数据结构之前,我想先带你来了解下为什么 ziplist 的设计会存在缺陷。这样一来,你在学习 quicklist 和 listpack 时,可以和 ziplist 的设计进行对比,进一步就能更加容易地掌握 quicklist 和 listpack 的设计考虑了。

    而且,ziplist 和 quicklist 的区别,也是经常被问到的面试题,而 listpack 数据结构因为比较新,你对它的设计实现可能了解得并不多。那在学完了这节课之后,你其实就可以很轻松地应对这三种数据结构的使用问题了。此外,你还可以从这三种数据结构的逐步优化设计中,学习到 Redis 数据结构在内存开销和访问性能之间,采取的设计取舍思想。如果你需要开发高效的数据结构,你就可以把这种设计思想应用起来。

    好,那么接下来,我们就先来了解下 ziplist 在设计与实现上存在的缺陷。

    ziplist 的不足

    你已经知道,一个 ziplist 数据结构在内存中的布局,就是一块连续的内存空间。这块空间的起始部分是大小固定的 10 字节元数据,其中记录了 ziplist 的总字节数、最后一个元素的偏移量以及列表元素的数量,而这 10 字节后面的内存空间则保存了实际的列表数据。在 ziplist 的最后部分,是一个 1 字节的标识(固定为 255),用来表示 ziplist 的结束,如下图所示:

    不过,虽然 ziplist 通过紧凑的内存布局来保存数据,节省了内存空间,但是 ziplist 也面临着随之而来的两个不足:查找复杂度高和潜在的连锁更新风险。那么下面,我们就分别来了解下这两个问题。

    查找复杂度高

    因为 ziplist 头尾元数据的大小是固定的,并且在 ziplist 头部记录了最后一个元素的位置,所以,当在 ziplist 中查找第一个或最后一个元素的时候,就可以很快找到。

    但问题是,当要查找列表中间的元素时,ziplist 就得从列表头或列表尾遍历才行。而当 ziplist 保存的元素过多时,查找中间数据的复杂度就增加了。更糟糕的是,如果 ziplist 里面保存的是字符串,ziplist 在查找某个元素时,还需要逐一判断元素的每个字符,这样又进一步增加了复杂度。

    也正因为如此,我们在使用 ziplist 保存 Hash 或 Sorted Set 数据时,都会在 redis.conf 文件中,通过 hash-max-ziplist-entries 和 zset-max-ziplist-entries 两个参数,来控制保存在 ziplist 中的元素个数。

    不仅如此,除了查找复杂度高以外,ziplist 在插入元素时,如果内存空间不够了,ziplist 还需要重新分配一块连续的内存空间,而这还会进一步引发连锁更新的问题。

    连续更新风险

    我们知道,因为 ziplist 必须使用一块连续的内存空间来保存数据,所以当新插入一个元素时,ziplist 就需要计算其所需的空间大小,并申请相应的内存空间。这一系列操作,我们可以从 ziplist 的元素插入函数 __ziplistInsert 中看到。__ziplistInsert 函数首先会计算获得当前 ziplist 的长度,这个步骤通过 ZIPLIST_BYTES 宏定义就可以完成,如下所示。同时,该函数还声明了 reqlen 变量,用于记录插入元素后所需的新增空间大小。

    源代码的ziplist.c文件中去查看,以下是这个函数的完整代码,先展示完完整代码,然后再去看里面的细节。

    /* Insert item at "p". */
    unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
        // 获取当前ziplist长度curlen;声明reqlen变量,用来记录新插入元素所需的长度
        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;
        // 如果插入的位置不是ziplist末尾,则获取前一项长度
        /* 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;
    }
    

    然后,__ziplistInsert 函数会判断当前要插入的位置是否是列表末尾。如果不是末尾,那么就需要获取位于当前插入位置的元素的 prevlen 和 prevlensize。这部分代码如下所示:

    // 如果插入的位置不是ziplist末尾,则获取前一项长度
        /* 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);
            }
        }
    

    实际上,在 ziplist 中,每一个元素都会记录其前一项的长度,也就是 prevlen。然后,为了节省内存开销,ziplist 会使用不同的空间记录 prevlen,这个 prevlen 空间大小就是 prevlensize。

    举个简单的例子,当在一个元素 A 前插入一个新的元素 B 时,A 的 prevlen 和 prevlensize 都要根据 B 的长度进行相应的变化。那么现在,我们假设 A 的 prevlen 原本只占用 1 字节(也就是 prevlensize 等于 1),而能记录的前一项长度最大为 253 字节。此时,如果 B 的长度超过了 253 字节,A 的 prevlen 就需要使用 5 个字节来记录(prevlen 具体的编码方式,你可以复习回顾下第 4 讲),这样就需要申请额外的 4 字节空间了。不过,如果元素 B 的插入位置是列表末尾,那么插入元素 B 时,我们就不用考虑后面元素的 prevlen 了。

    因此,为了保证 ziplist 有足够的内存空间,来保存插入元素以及插入位置元素的 prevlen 信息,__ziplistInsert 函数在获得插入位置元素的 prevlen 和 prevlensize 后,紧接着就会计算插入元素的长度。

    现在我们已知,一个 ziplist 元素包括了 prevlen、encoding 和实际数据 data 三个部分。所以,在计算插入元素的所需空间时,__ziplistInsert 函数也会分别计算这三个部分的长度。这个计算过程一共可以分成四步来完成。

    • 第一步,计算实际插入元素的长度。

    • 首先你要知道,这个计算过程和插入元素是整数还是字符串有关。__ziplistInsert 函数会先调用 zipTryEncoding 函数,这个函数会判断插入元素是否为整数。

      • 如果是整数,就按照不同的整数大小,计算 encoding 和实际数据 data 各自所需的空间;

      • 如果是字符串,那么就先把字符串长度记录为所需的新增空间大小。这一过程的代码如下所示:

     /* See if the entry can be encoded */
        if (zipTryEncoding(s,slen,&value,&encoding)) {
            // 如果是整数,就按照不同的整数大小,计算 encoding 和实际数据 data 各自所需的空间;
            /* '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;
        }
    
    • 第二步,调用 zipStorePrevEntryLength 函数,将插入位置元素的 prevlen 也计算到所需空间中。

    这是因为在插入元素后,__ziplistInsert 函数可能要为插入位置的元素分配新增空间。这部分代码如下所示:

    /* We need space for both the length of the previous entry and * the length of the payload. */
        reqlen += zipStorePrevEntryLength(NULL,prevlen);
    
    • 第三步,调用 zipStoreEntryEncoding 函数,根据字符串的长度,计算相应 encoding 的大小。

    在刚才的第一步中,__ziplistInsert 函数对于字符串数据,只是记录了字符串本身的长度,所以在第三步中,__ziplistInsert 函数还会调用 zipStoreEntryEncoding 函数,根据字符串的长度来计算相应的 encoding 大小,如下所示:

    reqlen += zipStoreEntryEncoding(NULL,encoding,slen);
    

    好了,到这里,ziplistInsert 函数就已经在 reqlen 变量中,记录了插入元素的 prevlen 长度、encoding 大小,以及实际数据 data 的长度。这样一来,插入元素的整体长度就有了,这也是插入位置元素的 prevlen 所要记录的大小。

    • 第四步,调用 zipPrevLenByteDiff 函数,判断插入位置元素的 prevlen 和实际所需的 prevlen 大小。

    最后,__ziplistInsert 函数会调用 zipPrevLenByteDiff 函数,用来判断插入位置元素的 prevlen 和实际所需的 prevlen,这两者间的大小差别。这部分代码如下所示,prevlen 的大小差别是使用 nextdiff 来记录的:

    nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
    

    那么在这里,如果 nextdiff 大于 0,就表明插入位置元素的空间不够,需要新增 nextdiff 大小的空间,以便能保存新的 prevlen。然后,__ziplistInsert 函数在新增空间时,就会调用 ziplistResize 函数,来重新分配 ziplist 所需的空间。ziplistResize 函数接收的参数分别是待重新分配的 ziplist 和重新分配的空间大小。而 __ziplistInsert 函数传入的重新分配大小的参数,是三个长度之和。那么是哪三个长度之和呢?这三个长度分别是

    • ziplist 现有大小(curlen)
    • 待插入元素自身所需的新增空间(reqlen)
    • 以及插入位置元素 prevlen 所需的新增空间(nextdiff)。

    下面的代码显示了 ziplistResize 函数的调用和参数传递逻辑:

    newlen = curlen+reqlen+nextdiff;
    zl = ziplistResize(zl,newlen);
    

    进一步,那么 ziplistResize 函数在获得三个长度总和之后,具体是如何扩容呢?

    我们可以进一步看下 ziplistResize 函数的实现,这个函数会调用 zrealloc 函数,来完成空间的重新分配,而重新分配的空间大小就是由传入参数 len 决定的。这样,我们就了解到了 ziplistResize 函数涉及到内存分配操作,因此如果我们往 ziplist 频繁插入过多数据的话,就可能引起多次内存分配,从而会对 Redis 性能造成影响。

    下面的代码显示了 ziplistResize 函数的部分实现,你可以看下。

    /* Resize the ziplist. */
    unsigned char *ziplistResize(unsigned char *zl, size_t len) {
        assert(len < UINT32_MAX);
        // 对zl进行重新内存空间分配,重新分配的大小是len
        zl = zrealloc(zl,len);
        ZIPLIST_BYTES(zl) = intrev32ifbe(len);
        zl[len-1] = ZIP_END;
        return zl;
    }
    

    好了,到这里,我们就了解了 ziplist 在新插入元素时,会计算其所需的新增空间,并进行重新分配。而当新插入的元素较大时,就会引起插入位置的元素 prevlensize 增加,进而就会导致插入位置的元素所占空间也增加。

    而如此一来,这种空间新增就会引起连锁更新的问题。

    实际上,所谓的连锁更新,就是指当一个元素插入后,会引起当前位置元素新增 prevlensize 的空间。而当前位置元素的空间增加后,又会进一步引起该元素的后续元素,其 prevlensize 所需空间的增加。

    这样,一旦插入位置后续的所有元素,都会因为前序元素的 prevlenszie 增加,而引起自身空间也要增加,这种每个元素的空间都需要增加的现象,就是连锁更新。我画了下面这张图,你可以看下。

    img

    连锁更新一旦发生,就会导致 ziplist 占用的内存空间要多次重新分配,这就会直接影响到 ziplist 的访问性能。所以说,虽然 ziplist 紧凑型的内存布局能节省内存开销,但是如果保存的元素数量增加了,或是元素变大了,ziplist 就会面临性能问题。那么,有没有什么方法可以避免 ziplist 的问题呢?这就是接下来我要给你介绍的 quicklist 和 listpack,这两种数据结构的设计思想了。

    quicklist 设计与实现

    quicklist 的设计,其实是结合了链表和 ziplist 各自的优势。简单来说,一个 quicklist 就是一个链表,而链表中的每个元素又是一个 ziplist。

    我们来看下 quicklist 的数据结构,这是在quicklist.h文件中定义的,而 quicklist 的具体实现是在quicklist.c文件中。首先,quicklist 元素的定义,也就是 quicklistNode。因为 quicklist 是一个链表,所以每个 quicklistNode 中,都包含了分别指向它前序和后序节点的指针*prev和*next。同时,每个 quicklistNode 又是一个 ziplist,所以,在 quicklistNode 的结构体中,还有指向 ziplist 的指针*zl。

    此外,quicklistNode 结构体中还定义了一些属性,比如 ziplist 的字节大小、包含的元素个数、编码格式、存储方式等。下面的代码显示了 quicklistNode 的结构体定义,你可以看下。

    在quicklist.h中可以查看到

    /* Node, quicklist, and Iterator are the only data structures used currently. */
    
    /* quicklistNode is a 32 byte struct describing a ziplist for a quicklist.
     * We use bit fields keep the quicklistNode at 32 bytes.
     * count: 16 bits, max 65536 (max zl bytes is 65k, so max count actually < 32k).
     * encoding: 2 bits, RAW=1, LZF=2.
     * container: 2 bits, NONE=1, ZIPLIST=2.
     * recompress: 1 bit, bool, true if node is temporary decompressed for usage.
     * attempted_compress: 1 bit, boolean, used for verifying during testing.
     * extra: 10 bits, free for future use; pads out the remainder of 32 bits */
    typedef struct quicklistNode {
        // 前一个quicklistNode
        struct quicklistNode *prev;
        // 后一个quicklistNode
        struct quicklistNode *next;
        // quicklistNode指向的ziplist
        unsigned char *zl;
        // ziplist的字节大小
        unsigned int sz;             /* ziplist size in bytes */
        // ziplist中的元素个数
        unsigned int count : 16;     /* count of items in ziplist */
        // 编码格式,原生字节数组或压缩存储
        unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
        // 存储方式
        unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
        // 数据是否被压缩
        unsigned int recompress : 1; /* was this node previous compressed? */
        // 数据能否被压缩
        unsigned int attempted_compress : 1; /* node can't compress; too small */
        // 预留的bit位
        unsigned int extra : 10; /* more bits to steal for future usage */
    } quicklistNode;
    

    了解了 quicklistNode 的定义,我们再来看下 quicklist 的结构体定义。

    quicklist 作为一个链表结构,在它的数据结构中,是定义了整个 quicklist 的头、尾指针,这样一来,我们就可以通过 quicklist 的数据结构,来快速定位到 quicklist 的链表头和链表尾。

    此外,quicklist 中还定义了 quicklistNode 的个数、所有 ziplist 的总元素个数等属性。quicklist 的结构定义如下所示:

    /* quicklist is a 40 byte struct (on 64-bit systems) describing a quicklist.
     * 'count' is the number of total entries.
     * 'len' is the number of quicklist nodes.
     * 'compress' is: 0 if compression disabled, otherwise it's the number
     *                of quicklistNodes to leave uncompressed at ends of quicklist.
     * 'fill' is the user-requested (or default) fill factor.
     * 'bookmakrs are an optional feature that is used by realloc this struct,
     *      so that they don't consume memory when not used. */
    typedef struct quicklist {
        quicklistNode *head;
        quicklistNode *tail;
        unsigned long count;        /* total count of all entries in all ziplists */
        unsigned long len;          /* number of quicklistNodes */
        int fill : QL_FILL_BITS;              /* fill factor for individual nodes */
        unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
        unsigned int bookmark_count: QL_BM_BITS;
        quicklistBookmark bookmarks[];
    } quicklist;
    

    然后,从 quicklistNode 和 quicklist 的结构体定义中,我们就能画出下面这张 quicklist 的示意图。

    而也正因为 quicklist 采用了链表结构,所以当插入一个新的元素时,quicklist 首先就会检查插入位置的 ziplist 是否能容纳该元素,这是通过 _quicklistNodeAllowInsert 函数来完成判断的。

    _quicklistNodeAllowInsert 函数会计算新插入元素后的大小(new_sz),这个大小等于 quicklistNode 的当前大小(node->sz)、插入元素的大小(sz),以及插入元素后 ziplist 的 prevlen 占用大小。在计算完大小之后,_quicklistNodeAllowInsert 函数会依次判断新插入的数据大小(sz)是否满足要求,即单个 ziplist 是否不超过 8KB,或是单个 ziplist 里的元素个数是否满足要求。只要这里面的一个条件能满足,quicklist 就可以在当前的 quicklistNode 中插入新元素,否则 quicklist 就会新建一个 quicklistNode,以此来保存新插入的元素。下面代码显示了是否允许在当前 quicklistNode 插入数据的判断逻辑,你可以看下。

    在quicklist.c文件中可以查看

    REDIS_STATIC int _quicklistNodeAllowInsert(const quicklistNode *node,
                                               const int fill, const size_t sz) {
        if (unlikely(!node))
            return 0;
    
        int ziplist_overhead;
        /* size of previous offset */
        if (sz < 254)
            ziplist_overhead = 1;
        else
            ziplist_overhead = 5;
    
        /* size of forward offset */
        if (sz < 64)
            ziplist_overhead += 1;
        else if (likely(sz < 16384))
            ziplist_overhead += 2;
        else
            ziplist_overhead += 5;
    
        /* new_sz overestimates if 'sz' encodes to an integer type */
        unsigned int new_sz = node->sz + sz + ziplist_overhead;
        if (likely(_quicklistNodeSizeMeetsOptimizationRequirement(new_sz, fill)))
            return 1;
        /* when we return 1 above we know that the limit is a size limit (which is
         * safe, see comments next to optimization_level and SIZE_SAFETY_LIMIT) */
        else if (!sizeMeetsSafetyLimit(new_sz))
            return 0;
        else if ((int)node->count < fill)
            return 1;
        else
            return 0;
    }
    

    这样一来,quicklist 通过控制每个 quicklistNode 中,ziplist 的大小或是元素个数,就有效减少了在 ziplist 中新增或修改元素后,发生连锁更新的情况,从而提供了更好的访问性能。

    而 Redis 除了设计了 quicklist 结构来应对 ziplist 的问题以外,还在 5.0 版本中新增了 listpack 数据结构,用来彻底避免连锁更新。下面我们就继续来学习下它的设计实现思路。listpack 设计与实现

    listpack 设计与实现

    listpack 也叫紧凑列表,它的特点就是用一块连续的内存空间来紧凑地保存数据,同时为了节省内存空间,listpack 列表项使用了多种编码方式,来表示不同长度的数据,这些数据包括整数和字符串

    和 listpack 相关的实现文件是listpack.c,头文件包括listpack.h和listpack_malloc.h。

    我们先来看下 listpack 的创建函数 lpNew,因为从这个函数的代码逻辑中,我们可以了解到 listpack 的整体结构。lpNew 函数创建了一个空的 listpack,一开始分配的大小是 LP_HDR_SIZE 再加 1 个字节。LP_HDR_SIZE 宏定义是在 listpack.c 中,它默认是 6 个字节,其中 4 个字节是记录 listpack 的总字节数,2 个字节是记录 listpack 的元素数量。此外,listpack 的最后一个字节是用来标识 listpack 的结束,其默认值是宏定义 LP_EOF。和 ziplist 列表项的结束标记一样,LP_EOF 的值也是 255。

    listpack.c文件中查看

    宏定义

    #define LP_HDR_SIZE 6       /* 32 bit total len + 16 bit number of elements. */
    #define LP_EOF 0xFF
    

    函数

    /* Create a new, empty listpack.
     * On success the new listpack is returned, otherwise an error is returned.
     * Pre-allocate at least `capacity` bytes of memory,
     * over-allocated memory can be shrinked by `lpShrinkToFit`.
     * */
    unsigned char *lpNew(size_t capacity) {
        unsigned char *lp = lp_malloc(capacity > LP_HDR_SIZE+1 ? capacity : LP_HDR_SIZE+1);
        if (lp == NULL) return NULL;
        lpSetTotalBytes(lp,LP_HDR_SIZE+1);
        lpSetNumElements(lp,0);
        lp[LP_HDR_SIZE] = LP_EOF;
        return lp;
    }
    

    你可以看看下面这张图,展示的就是大小为 LP_HDR_SIZE 的 listpack 头和值为 255 的 listpack 尾。当有新元素插入时,该元素会被插在 listpack 头和尾之间。

    好了,了解了 listpack 的整体结构后,我们再来看下 listpack 列表项的设计。和 ziplist 列表项类似,listpack 列表项也包含了元数据信息和数据本身。不过,为了避免 ziplist 引起的连锁更新问题,listpack 中的每个列表项不再像 ziplist 列表项那样,保存其前一个列表项的长度,它只会包含三个方面内容,分别是

    • 当前元素的编码类型(entry-encoding)
    • 元素数据 (entry-data)
    • 以及编码类型和元素数据这两部分的长度 (entry-len)

    如下图所示。

    这里,关于 listpack 列表项的设计,你需要重点掌握两方面的要点,分别是列表项元素的编码类型,以及列表项避免连锁更新的方法。下面我就带你具体了解下。listpack 列表项编码方法我们先来看下 listpack 元素的编码类型。如果你看了 listpack.c 文件,你会发现该文件中有大量类似 LP_ENCODING_N_BIT_INT 和 LP_ENCODING_N_BIT_STR 的宏定义,如下所示:

    #define LP_ENCODING_7BIT_UINT 0
    #define LP_ENCODING_7BIT_UINT_MASK 0x80
    #define LP_ENCODING_IS_7BIT_UINT(byte) (((byte)&LP_ENCODING_7BIT_UINT_MASK)==LP_ENCODING_7BIT_UINT)
    
    #define LP_ENCODING_6BIT_STR 0x80
    #define LP_ENCODING_6BIT_STR_MASK 0xC0
    #define LP_ENCODING_IS_6BIT_STR(byte) (((byte)&LP_ENCODING_6BIT_STR_MASK)==LP_ENCODING_6BIT_STR)
    
    #define LP_ENCODING_13BIT_INT 0xC0
    #define LP_ENCODING_13BIT_INT_MASK 0xE0
    #define LP_ENCODING_IS_13BIT_INT(byte) (((byte)&LP_ENCODING_13BIT_INT_MASK)==LP_ENCODING_13BIT_INT)
    
    #define LP_ENCODING_12BIT_STR 0xE0
    #define LP_ENCODING_12BIT_STR_MASK 0xF0
    #define LP_ENCODING_IS_12BIT_STR(byte) (((byte)&LP_ENCODING_12BIT_STR_MASK)==LP_ENCODING_12BIT_STR)
    
    #define LP_ENCODING_16BIT_INT 0xF1
    #define LP_ENCODING_16BIT_INT_MASK 0xFF
    #define LP_ENCODING_IS_16BIT_INT(byte) (((byte)&LP_ENCODING_16BIT_INT_MASK)==LP_ENCODING_16BIT_INT)
    
    #define LP_ENCODING_24BIT_INT 0xF2
    #define LP_ENCODING_24BIT_INT_MASK 0xFF
    #define LP_ENCODING_IS_24BIT_INT(byte) (((byte)&LP_ENCODING_24BIT_INT_MASK)==LP_ENCODING_24BIT_INT)
    
    #define LP_ENCODING_32BIT_INT 0xF3
    #define LP_ENCODING_32BIT_INT_MASK 0xFF
    #define LP_ENCODING_IS_32BIT_INT(byte) (((byte)&LP_ENCODING_32BIT_INT_MASK)==LP_ENCODING_32BIT_INT)
    
    #define LP_ENCODING_64BIT_INT 0xF4
    #define LP_ENCODING_64BIT_INT_MASK 0xFF
    #define LP_ENCODING_IS_64BIT_INT(byte) (((byte)&LP_ENCODING_64BIT_INT_MASK)==LP_ENCODING_64BIT_INT)
    
    #define LP_ENCODING_32BIT_STR 0xF0
    #define LP_ENCODING_32BIT_STR_MASK 0xFF
    #define LP_ENCODING_IS_32BIT_STR(byte) (((byte)&LP_ENCODING_32BIT_STR_MASK)==LP_ENCODING_32BIT_STR)
    

    这些宏定义其实就对应了 listpack 的元素编码类型。具体来说**,listpack 元素会对不同长度的整数和字符串进行编码**,这里我们分别来看下。

    首先,对于整数编码来说,当 listpack 元素的编码类型为 LP_ENCODING_7BIT_UINT 时,表示元素的实际数据是一个 7 bit 的无符号整数。又因为 LP_ENCODING_7BIT_UINT 本身的宏定义值为 0,所以编码类型的值也相应为 0,占 1 个 bit。

    此时,编码类型和元素实际数据共用 1 个字节,这个字节的最高位为 0,表示编码类型,后续的 7 位用来存储 7 bit 的无符号整数,如下图所示:

    而当编码类型为 LP_ENCODING_13BIT_INT 时,这表示元素的实际数据是 13 bit 的整数。同时,因为 LP_ENCODING_13BIT_INT 的宏定义值为 0xC0,转换为二进制值是 1100 0000,所以,这个二进制值中的后 5 位和后续的 1 个字节,共 13 位,会用来保存 13bit 的整数。而该二进制值中的前 3 位 110,则用来表示当前的编码类型。我画了下面这张图,你可以看下。

    好,在了解了 LP_ENCODING_7BIT_UINT 和 LP_ENCODING_13BIT_INT 这两种编码类型后,剩下的 LP_ENCODING_16BIT_INT、LP_ENCODING_24BIT_INT、LP_ENCODING_32BIT_INT 和 LP_ENCODING_64BIT_INT,你应该也就能知道它们的编码方式了。这四种类型是分别用 2 字节(16 bit)、3 字节(24 bit)、4 字节(32 bit)和 8 字节(64 bit)来保存整数数据。同时,它们的编码类型本身占 1 字节,编码类型值分别是它们的宏定义值。

    然后,对于字符串编码来说,一共有三种类型,分别是 LP_ENCODING_6BIT_STR、LP_ENCODING_12BIT_STR 和 LP_ENCODING_32BIT_STR。从刚才的介绍中,你可以看到,整数编码类型名称中 BIT 前面的数字,表示的是整数的长度。因此类似的,字符串编码类型名称中 BIT 前的数字,表示的就是字符串的长度。

    比如,当编码类型为 LP_ENCODING_6BIT_STR 时,编码类型占 1 字节。该类型的宏定义值是 0x80,对应的二进制值是 1000 0000,这其中的前 2 位是用来标识编码类型本身,而后 6 位保存的是字符串长度。然后,列表项中的数据部分保存了实际的字符串。下面的图展示了三种字符串编码类型和数据的布局,你可以看下。

    img

    listpack 避免连锁更新的实现方式

    最后,我们再来了解下 listpack 列表项是如何避免连锁更新的。在 listpack 中,因为每个列表项只记录自己的长度,而不会像 ziplist 中的列表项那样,会记录前一项的长度。所以,当我们在 listpack 中新增或修改元素时,实际上只会涉及每个列表项自己的操作,而不会影响后续列表项的长度变化,这就避免了连锁更新。

    不过,你可能会有疑问:如果 listpack 列表项只记录当前项的长度,那么 listpack 支持从左向右正向查询列表,或是从右向左反向查询列表吗

    其实,listpack 是能支持正、反向查询列表的。

    当应用程序从左向右正向查询 listpack 时,我们可以先调用 lpFirst 函数。该函数的参数是指向 listpack 头的指针,它在执行时,会让指针向右偏移 LP_HDR_SIZE 大小,也就是跳过 listpack 头。你可以看下 lpFirst 函数的代码,如下所示:

    /* Return a pointer to the first element of the listpack, or NULL if the
     * listpack has no elements. */
    unsigned char *lpFirst(unsigned char *lp) {
        // 跳过listpack头部6个字节
        unsigned char *p = lp + LP_HDR_SIZE; /* Skip the header. */
        // 如果已经是listpack的末尾结束字节,则返回NULL
        if (p[0] == LP_EOF) return NULL;
        lpAssertValidEntry(lp, lpBytes(lp), p);
        return p;
    }
    

    然后,再调用 lpNext 函数,该函数的参数包括了指向 listpack 某个列表项的指针。lpNext 函数会进一步调用 lpSkip 函数,并传入当前列表项的指针,如下所示:

    最后,lpSkip 函数会先后调用 lpCurrentEncodedSizelpEncodeBacklen 这两个函数。lpCurrentEncodedSize 函数是根据当前列表项第 1 个字节的取值,来计算当前项的编码类型,并根据编码类型,计算当前项编码类型和实际数据的总长度。然后,lpEncodeBacklen 函数会根据编码类型和实际数据的长度之和,进一步计算列表项最后一部分 entry-len 本身的长度。这样一来,lpSkip 函数就知道当前项的编码类型、实际数据和 entry-len 的总长度了,也就可以将当前项指针向右偏移相应的长度,从而实现查到下一个列表项的目的。

    下面代码展示了 lpEncodeBacklen 函数的基本计算逻辑,你可以看下。

    /* Store a reverse-encoded variable length field, representing the length
     * of the previous element of size 'l', in the target buffer 'buf'.
     * The function returns the number of bytes used to encode it, from
     * 1 to 5. If 'buf' is NULL the function just returns the number of bytes
     * needed in order to encode the backlen. */
    unsigned long lpEncodeBacklen(unsigned char *buf, uint64_t l) {
        // 编码类型和实际数据的总长度小于等于127,entry-len长度为1字节
        if (l <= 127) {
            if (buf) buf[0] = l;
            return 1;
        } else if (l < 16383) {
            // 编码类型和实际数据的总长度大于127但小于16383,entry-len长度为2字节
            if (buf) {
                buf[0] = l>>7;
                buf[1] = (l&127)|128;
            }
            return 2;
        } else if (l < 2097151) {
            // 编码类型和实际数据的总长度大于16383但小于2097151,entry-len长度为3字节
            if (buf) {
                buf[0] = l>>14;
                buf[1] = ((l>>7)&127)|128;
                buf[2] = (l&127)|128;
            }
            return 3;
        } else if (l < 268435455) {
            // 编码类型和实际数据的总长度大于2097151但小于268435455,entry-len长度为4字节
            if (buf) {
                buf[0] = l>>21;
                buf[1] = ((l>>14)&127)|128;
                buf[2] = ((l>>7)&127)|128;
                buf[3] = (l&127)|128;
            }
            return 4;
        } else {
            // 否则,entry-len长度为5字节
            if (buf) {
                buf[0] = l>>28;
                buf[1] = ((l>>21)&127)|128;
                buf[2] = ((l>>14)&127)|128;
                buf[3] = ((l>>7)&127)|128;
                buf[4] = (l&127)|128;
            }
            return 5;
        }
    }
    

    我也画了一张图,展示了从左向右遍历 listpack 的基本过程,你可以再回顾下。

    img

    好,了解了从左向右正向查询 listpack,我们再来看下从右向左反向查询 listpack

    首先,我们根据 listpack 头中记录的 listpack 总长度,就可以直接定位到 listapck 的尾部结束标记。然后,我们可以调用 lpPrev 函数,该函数的参数包括指向某个列表项的指针,并返回指向当前列表项前一项的指针。lpPrev 函数中的关键一步就是调用 lpDecodeBacklen 函数。

    lpDecodeBacklen 函数会从右向左,逐个字节地读取当前列表项的 entry-len。那么,lpDecodeBacklen 函数如何判断 entry-len 是否结束了呢?

    这就依赖于 entry-len 的编码方式了。entry-len 每个字节的最高位,是用来表示当前字节是否为 entry-len 的最后一个字节,这里存在两种情况,分别是:

    • 最高位为 1,表示 entry-len 还没有结束,当前字节的左边字节仍然表示 entry-len 的内容;
    • 最高位为 0,表示当前字节已经是 entry-len 最后一个字节了。

    而 entry-len 每个字节的低 7 位,则记录了实际的长度信息。这里你需要注意的是,entry-len 每个字节的低 7 位采用了大端模式存储,也就是说,entry-len 的低位字节保存在内存高地址上。我画了下面这张图,展示了 entry-len 这种特别的编码方式,你可以看下。

    img

    实际上,正是因为有了 entry-len 的特别编码方式,lpDecodeBacklen 函数就可以从当前列表项起始位置的指针开始,向左逐个字节解析,得到前一项的 entry-len 值。这也是 lpDecodeBacklen 函数的返回值。而从刚才的介绍中,我们知道 entry-len 记录了编码类型和实际数据的长度之和。因此,lpPrev 函数会再调用 lpEncodeBacklen 函数,来计算得到 entry-len 本身长度,这样一来,我们就可以得到前一项的总长度,而 lpPrev 函数也就可以将指针指向前一项的起始位置了。所以按照这个方法,listpack 就实现了从右向左的查询功能。

    你要知道,ziplist 的不足主要在于一旦 ziplist 中元素个数多了,它的查找效率就会降低。而且如果在 ziplist 里新增或修改数据,ziplist 占用的内存空间还需要重新分配;更糟糕的是,ziplist 新增某个元素或修改某个元素时,可能会导致后续元素的 prevlen 占用空间都发生变化,从而引起连锁更新问题,导致每个元素的空间都要重新分配,这就会导致 ziplist 的访问性能下降。

    所以,为了应对 ziplist 的问题,Redis 先是在 3.0 版本中设计实现了 quicklist。quicklist 结构在 ziplist 基础上,使用链表将 ziplist 串联起来,链表的每个元素就是一个 ziplist。这种设计减少了数据插入时内存空间的重新分配,以及内存数据的拷贝。同时,quicklist 限制了每个节点上 ziplist 的大小,一旦一个 ziplist 过大,就会采用新增 quicklist 节点的方法。不过,又因为 quicklist 使用 quicklistNode 结构指向每个 ziplist,无疑增加了内存开销。为了减少内存开销,并进一步避免 ziplist 连锁更新问题,Redis 在 5.0 版本中,就设计实现了 listpack 结构。listpack 结构沿用了 ziplist 紧凑型的内存布局,把每个元素都紧挨着放置。listpack 中每个列表项不再包含前一项的长度了,因此当某个列表项中的数据发生变化,导致列表项长度变化时,其他列表项的长度是不会受影响的,因而这就避免了 ziplist 面临的连锁更新问题。总而言之,Redis 在内存紧凑型列表的设计与实现上,从 ziplist 到 quicklist,再到 listpack,你可以看到 Redis 在内存空间开销和访问性能之间的设计取舍,这一系列的设计变化,是非常值得你学习的。

    展开全文
  • 其中 zlbytes,zltail,zllen 为 ziplist 的 head 部分,entry 为 ziplist 的 entries 部分,每一个 entry 代表一个数据,最后 zlend 表示 ziplist 的 end 部分,如下图所示: ziplist 中每个属性代表的含义如下...

    你知道的越多,不知道的就越多,业余的像一棵小草!

    成功路上并不拥挤,因为坚持的人不多。

    编辑:业余草

    zhouwenxing.github.io

    推荐:https://www.xttblog.com/?p=5188

    前言

    正常情况下我们选择使用 Redis 就是为了提升查询速度,然而让人意外的是,Redis 当中却有一种比较有意思的数据结构,这种数据结构通过牺牲部分读写速度来达到节省内存的目的,这就是 ziplist(压缩列表),Redis 为什么要这么做呢?难道真的是觉得自己的速度太快了,牺牲一点速度也不影响吗?

    什么是压缩列表

    ziplist 是为了节省内存而设计出来的一种数据结构。ziplist 是由一系列特殊编码组成的连续内存块的顺序型数据结构,一个 ziplist 可以包含任意多个 entry,而每一个 entry 又可以保存一个字节数组或者一个整数值。

    ziplist 作为一种列表,其和普通的双端列表,如 linkedlist 的最大区别就是 ziplist 并不存储前后节点的指针,而 linkedlist 一般每个节点都会维护一个指向前置节点和一个指向后置节点的指针。那么 ziplist 不维护前后节点的指针,它又是如何寻找前后节点的呢?

    ziplist 虽然不维护前后节点的指针,但是它却维护了上一个节点的长度和当前节点的长度,然后每次通过长度来计算出前后节点的位置。既然涉及到了计算,那么相对于直接存储指针的方式肯定有性能上的损耗,这就是一种典型的用「时间来换取空间」的做法。因为每次读取前后节点都需要经过计算才能得到前后节点的位置,所以会消耗更多的时间,而在 Redis 中,一个指针是占了 8 个字节,但是大部分情况下,如果直接存储长度是达不到 8 个字节的,所以采用存储长度的设计方式在大部分场景下是可以节省内存空间的。

    ziplist 的存储结构

    ziplist 的组成结构为:

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

    其中 zlbyteszltailzllenziplisthead 部分,entryziplistentries 部分,每一个 entry 代表一个数据,最后 zlend 表示 ziplistend 部分,如下图所示:

    ziplist 中每个属性代表的含义如下表格所示:

    entry 存储结构

    ziplistheadend 存的都是长度和标记,而 entry 存储的是具体元素,这又是经过特殊的设计的一种存储格式,每个 entry 都以包含两段信息的元数据作为前缀,每一个 entry 的组成结构为:

    <prevlen> <encoding> <entry-data>
    

    prevlen

    prevlen 属性存储了前一个 entry 的长度,通过此属性能够从后到前遍历列表。prevlen 属性的长度可能是 1 字节也可能是 5 字节:

    • 当链表的前一个 entry 占用字节数小于 254,此时 prevlen 只用 1 个字节进行表示。

    <prevlen from 0 to 253> <encoding> <entry>
    
    • 当链表的前一个 entry 占用字节数大于等于 254,此时 prevlen5 个字节来表示,其中第 1 个字节的值固定是 254(相当于是一个标记,代表后面跟了一个更大的值),后面 4 个字节才是真正存储前一个 entry 的占用字节数。

    0xFE <4 bytes unsigned little endian prevlen> <encoding> <entry>
    

    注意:「1 个字节完全你能存储 255 的大小,之所以只取到 254 是因为 zlend 就是固定的 255,所以 255 这个数要用来判断是否是 ziplist 的结尾」。

    encoding

    encoding 属性存储了当前 entry 所保存数据的类型以及长度。encoding 长度为 1 字节,2 字节或者 5 字节长。前面我们提到,每一个 entry 中可以保存字节数组和整数,而 encoding 属性的第 1 个字节就是用来确定当前 entry 存储的是整数还是字节数组。当存储整数时,第 1 个字节的前两位总是 11,而存储字节数组时,则可能是 000110 三种中的一种。

    • 当存储整数时,第 1 个字节的前 2 位固定为 11,其他位则用来记录整数值的类型或者整数值(下表所示的编码中前两位均为 11):

    注意:xxxx 四位编码范围是 0000-1111,但是 000011111110 已经被表格中前面表示的数据类型占用了,所以实际上的范围是 0001-1101,此时能保存数据 1-13,再减去 1 之后范围就是 0-12。至于为什么要减去 1 是从使用习惯来说 0 是一个非常常用的数据,所以才会选择统一减去 1 来存储一个 0-12 的区间而不是直接存储 1-13 的区间。

    • 当存储字节数组时,第 1 个字节的前 2 位为 0001 或者 10,其他位则用来记录字节数组的长度:

    entry-data

    entry-data 存储的是具体数据。当存储小整数(0-12)时,因为 encoding 就是数据本身,此时 entry-data 部分会被省略,省略了 entry-data 部分之后的 ziplist 中的 entry 结构如下:

    <prevlen> <encoding>
    

    压缩列表中 entry 的数据结构定义如下(源码 ziplist.c 文件内),当然实际存储并没有直接使用到这个结构定义,这个结构只是用来接收数据,所以大家了解一下就可以了:

    typedef struct zlentry {
        unsigned int prevrawlensize;//存储prevrawlen所占用的字节数
        unsigned int prevrawlen;//存储上一个链表节点需要的字节数
        unsigned int lensize;//存储len所占用的字节数
        unsigned int len;//存储链表当前节点的字节数
        unsigned int headersize;//当前链表节点的头部大小(prevrawlensize + lensize)即非数据域的大小
        unsigned char encoding;//编码方式
        unsigned char *p;//指向当前节点的起始位置(因为列表内的数据也是一个字符串对象)
    } zlentry;

    ziplist 数据示例

    上面讲解了大半天,可能大家都觉得枯燥无味了,也可能会觉得云里雾里,这个没有关系,这些只要心里有个概念,用到的时候再查询对应资料就可以了,并不需要全部记住,接下来让我们一起通过两个例子来体会一下 ziplist 到底是如何来组织存储数据的。

    下面就是一个压缩列表的存储示例,这个压缩列表里面存储了 2 个节点,节点中存储的是整数 25

    1. 第一组 4 个字节为 zlbytes 部分,0f 转成二进制就是 1111 也就是 15,代表整个 ziplist 长度是 15 个字节。

    2. 第二组 4 个字节 zltail 部分,0c 转成二进制就是 1100 也就是 12,这里记录的是压缩列表尾节点距离起始地址有多少个字节,也就是就是说 [02 f6] 这个尾节点距离起始位置有 12 个字节。

    3. 第三组 2 个字节就是记录了当前 ziplistentry 的数量,02 转成二进制就是 10,也就是说当前 ziplist2 个节点。

    4. 第四组 2 个字节 [00 f3] 就是第一个 entry00 表示 0,因为这是第 1 个节点,所以前一个节点长度为 0f3 转成二进制就是 11110011,刚好对应了表格中的编码 1111xxxx,所以后面四位就是存储了一个 0-12位的整数。0011 转成十进制就是 3,减去 1 得到 2,所以第一个 entry 存储的数据就是 2

    5. 第五组 2 个字节 [02 f6] 就是第二个 entry02 即为 2,表示前一个节点的长度为 2,注意,因为这里算出来的结果是小于 254,所以就代表了这里只用到了 1 个字节来存储上一个节点的长度(如果等于 254,这说明接下来 4 个字节才存储的是长度),所以后面的 f6 就是当前节点的数据,转换成二进制为 11110110,对应了表格中的编码 1111xxxx,同样的后四位 0110 存储的是真实数据,计算之后得出是5。

    6. 最后一组1个字节[ff]转成二进制就是 11111111,代表这是整个 ziplist 的结尾。

    假如这时候又添加了一个 Hello World 字符串到列表中,那么就会新增一个 entry,如下所示:

    
    
    1. 第一组的 1 个字节 02 转成十进制就是 2 ,表示前一个节点(即上面示例中的 [02 f6])长度是 2

    2. 第 二组的2 个字节 0b 转成二进制为 00001011,以 00 开头,符合编码 00pppppp,而除掉最开始的两位 00,计算之后得到十进制 11,这就说明后面字节数组的长度是 11

    3. 第三组刚好是 11 个字节,对应了上面的长度,所以这里就是真正存储了 Hello World 的字节数组。

    ziplist 连锁更新问题

    上面提到 entry 中的 prevlen 属性可能是 1 个字节也可能是 5 个字节,那么我们来设想这么一种场景:假设一个 ziplist 中,连续多个 entry 的长度都是一个接近但是又不到 254 的值(介于 250~253 之间),那么这时候 ziplist 中每个节点都只用了 1 个字节来存储上一个节点的长度,假如这时候添加了一个新节点,如 entry1 ,其长度大于 254 个字节,此时 entry1 的下一个节点 entry2prelen 属性就必须要由 1 个字节变为 5 个字节,也就是需要执行空间重分配,而此时 entry2 因为增加了 4 个字节,导致长度又大于 254 个字节了,那么它的下一个节点 entry3prelen 属性也会被改变为 5 个字节。依此类推,这种产生连续多次空间重分配的现象就称之为「连锁更新」。同样的,不仅仅是新增节点,执行删除节点操作同样可能会发生连锁更新现象。

    虽然 ziplist 可能会出现这种连锁更新的场景,但是一般如果只是发生在少数几个节点之间,那么并不会严重影响性能,而且这种场景发生的概率也比较低,所以实际使用时不用过于担心。

    总结

    本文主要讲解了 Redis 当中的 ziplist(压缩列表),一种用时间换取空间的数据结构,在介绍压缩列表存储结构的同时通过一个存储示例来分析了 ziplist 是如何存储数据的,最后介绍了 ziplist 中可能发生的连锁更新问题。

    展开全文
  • ziplist 到 quicklist,再到 listpack 结构;可以看到,初衷都是设计一款数据结构能够高效的使用内存。 ziplist 设计出的紧凑型数据块可以有效利用内存,但在更新上,由于每一个 entry 都保留了前一个 entry 的 ...
  • 前文已经提及了压缩列表ziplist的主要设计初衷是尽量节约空间,因此设计出了一系列的压缩编码,将ziplist设计成了内存地址连续,使用基地址+偏移量的方式来访问压缩列表内节点,并且说明了压缩列表节点结构具有的...
  • 文章目录前言ziplist 中列表项结构解决问题应用场景存在问题总结 前言 ziplist 中列表项结构 ziplist 列表项包括三部分内容,分别是前一项的长度(prevlen)、当前项长度信息的编码结果(encoding),以及当前项的...
  • 详细介绍了Redis的底层数据结构:dict、ziplist、quicklist。
  • ziplist - 压缩列表

    千次阅读 2021-05-29 21:13:06
    一如既往,关于 ziplist 的定义和实现还是放在一对文件中,分别是 ziplist.h 和 ziplist.c。在 ziplist.c 文件的头部一段注释介绍什么是 ziplistziplist 是一个经过特殊编码的双向链表,旨在提高内存效率。
  • Redis基于C语言开发,由于C并未内置链表,因此Redis自己实现了一系列链表,有双端链表linkedlist、压缩列表ziplist、快速链表quicklist等,本篇将从源码角度展现压缩列表ziplist
  • 基于ziplist存在的问题,要避免ziplist列表太大问题,因此将大ziplist分成一系列小的ziplist是一种思路。 quicklist是由链表组成的结构,其中每个链表节点中都存在一个ziplist。是由ziplist改进而来,充分利用链表 ...
  • 02 关于 ziplist

    2021-02-27 11:22:30
    关于 redis 的数据结构 ziplist 相关介绍主要围绕着如下测试用例, 来看看 ziplist 的存储, 以及 相关的 api 本文的 sds 相关代码 拷贝自 redis-6.2.0 代码来自于 https://redis.io/ 测试用例 // // ...
  • 一、ziplist 简介 ziplist,也就是压缩列表,是为了提高存储效率而设计的一种特殊编码的双向链表。它可以存储字符串或者整数,存储整数时是采用整数的二进制而不是字符串形式存储。他能在 O(1) 的时间复杂度下完成 ...
  • 一、Redis 压缩列表(ziplist) 1. 介绍 压缩列表(ziplist)是哈希键的底层实现之一。它是经过特殊编码的双向链表,和整数集合(intset)一样,是为了提高内存的存储效率而设计的。当保存的对象是小整数值,或者是长度...
  • ZipList 食谱插件 WordPress 的配方格式。 此代码源自于发布的 RecipeSEO 1.3.1 版本。 格式化食谱,使它们对 SEO 友好。 现在完全支持 WordPress 4.0.1。 贡献者:ZipList Inc.,codewan 捐赠: : 标签:谷歌...
  • Redis ziplist 原理浅析

    2022-01-16 17:47:39
    文章目录前言ziplist 数据结构增加元素级联更新IntSet 小整数集合 前言 Redis 为了节约内存空间使用,zset 和 hash 容器对象在元素个数较少的时候,采用压缩列表(ziplist) 进行存储。压缩列表是一块连续的内存空间,...
  • zipList 压缩列表 quickList 快链表 链表:LinkedList 数据结构中常用的带头节点的双向链表,并且带有指向头节点的头指针和指向最后一个节点的尾指针,双向链表保证从任意一个位置可以向前或者向后进行遍历,...
  • redis之ziplist

    2021-08-01 14:54:50
    对比双向链表,ziplist是连续的内存,可随机访问,并且减少了next指针空间 缺点: 因为是内存连续的,如果修改中间的entry,可能需要数据拷贝 修改时当数据长度超过当前类型,跨入下一个类型时,因下一个节点保持...
  • Redis列表对象之linkedlist和ziplist实现原理分析前言列表对象linkedlistlinkedlist存储结构ziplistziplist存储结构entry存储结构prevlenencodingentry-dataziplist数据示例ziplist连锁更新问题linkedlist和ziplist...
  • ziplist是Redis中的某些数据类型底层所使用的数据结构 Redis中的hash,List,Sorted List这几种类型的数据在某些情况下会使用ziplist来存储。 Hash类型 当hash类型的数据满足以下条件时,底层使用ziplist存储。 当...
  • redis中ziplist,skiplist

    2021-12-06 21:39:56
    skiplist,ziplist是redis数据结构比较经典的应用,可以参考其中的思想
  • Redis之压缩列表ziplist

    万次阅读 多人点赞 2019-04-30 15:42:38
    ziplist是list键、hash键以及zset键的底层实现之一(3.0之后list键已经不直接用ziplist和linkedlist作为底层实现了,取而代之的是quicklist) 这些键的常规底层实现如下: list键:双向链表 hash键:字典di...
  • 压缩列表-ziplist概述压缩列表压缩列表节点-entryprevious_entry_length属性encoding属性字节数组编码整数编码content压缩列表的连锁更新压缩列表API 概述 压缩列表(ziplist)是 列表键 和 哈希键 的 底层实现之一 ...
  • Redis 数据结构 ziplist

    2021-05-29 16:33:06
    和大家分享 Redis 的数据结构 ziplist(压缩链表),欢迎阅读斧正。
  • 前言 redis是内存操作的对数据的编码也自己的一套...ziplist数据的编码 ziplist数据的插入的分析 ziplist数据的合并的分析 ziplist数据的查找的分析 ziplist数据的删除的分析 正文 一, intset数据结构编码分析 ...
  • Redis底层实现---Ziplist

    2021-07-25 22:06:02
    Redis底层实现—Ziplist 简介 redis 是开源用C语言编写的一个远程的KV词典存储服务,里面有很多经典的设计结构对后续的设计很有启发, 其中最著名的恐怕就是排序链表的底层实现—跳表。 本次要说的是他的另外一个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 16,120
精华内容 6,448
关键字:

ziplist

友情链接: 高傲科技配置.zip