Redis之压缩列表与快速列表

2022-01-10 01:29:00

ziplist

为了节约内存空间，当zset和hash对象在元素较少的时候，使用ziplist(压缩列表)进行存储，压缩列表是一块连续的内存空间，没有任何冗余空隙。

zset

127.0.0.1:6379> zadd program 1 go 2 java 3 python

(integer) 3

127.0.0.1:6379> debug object program

Value at:0xffff9658d2c0 refcount:1 encoding:ziplist serializedlength:36 lru:14930008 lru_seconds_idle:23

可以看到，当创建一个新的zset，元素只有3个的时候，encoding是ziplist，也就说用ziplist在存储这些元素。

hash

127.0.0.1:6379> hmset books go 1 java 2 python 3

OK

127.0.0.1:6379> debug object books

Value at:0xffff9657b820 refcount:1 encoding:ziplist serializedlength:36 lru:14930394 lru_seconds_idle:24

hash也是一样，添加了三个元素，encoding也是ziplist。

ziplist结构

ziplist结构如下：

struct ziplist<T> {
    int32 zlbytes;        // 整个压缩列表占用字节数
    int32 zltail_offset;  // 最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个节点
    int16 zllength;       // 元素个数
    T[] entries;          // 元素内容列表，依次紧凑存储
    int8 zlend;           // 标志压缩列表的结束, 值恒为 0xFF
}

为了支持双向遍历，所以有了ztail_offset这个字段，用来快速定位最后一个元素，就可以倒着遍历了。

ziplist中的entry结构

entry块随着容纳的元素类型不同，也会有不一样的结构。

struct entry {
    int<var> prevlen;         // 前一个entry的字节长度
    int<var> encoding;        // 元素类型编码
    optional byte[] content;  // 元素内容
}

prevlen

prevlen 表示前一个entry的字节长度，当压缩列表倒着遍历时，可以通过这个字段定位到下一个元素的位置，

prevlen 是一个变长整数，当字符串长度小于254(0xFE)时，使用1个字节表示，大于等于254时，则使用5个字节表示，此时第1个字节是固定的 0xFE ，剩余4个字节表示字符串长度。

encoding

encoding字段存储了元素内容的编码类型信息，通过该字段就可以知道entry中的content数组里存储的内容是什么类型。

为了节约内存空间，encoding可以代表多种数据类型，不同的数据类型根据encoding的前缀位进行区分，以下是不同数据类型的前缀位描述：

00xxxxxx，00开头表示最大长度位数为63的短字符串，后面6个位(xxxxxx)用于存储字符串的长度即content数组的长度。
01xxxxxx xxxxxxxx 是中等长度的字符串，后面14个位用于存储content数组的长度。
10000000 xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx 是特大字符串，第一个字节固定为 10000000, 后面 4 个字节表示长度，不过这种encoding基本不会出现在ziplist中，因为ziplist一般只用于存储小数据。
11000000 表示 int16，此时content长度为2，表示int16类型的整数。
11010000 表示 int32, 此时content长度为4。
11100000 表示 int64，此时content长度为8。
11110000 表示 int24，此时content长度为3。
11111110 表示 int8，此时content长度为1。
11111111 表示 ziplist的结束，也就是 zlend 的值 0xFF。
1111xxxx 表示极小整数，xxxx的范围是(0001~1101)，即1~13，因为0000、1110、1111都被上面的类型占用了，读取到的value需要再减去1，即极小整数的值范围是0~12。

content字段在结构体中定义为optional类型，表示该字段是可选的，因为对于极小整数来说，它的内容已经在encoding中定义了，不需要存在content中。

新增元素

ziplist中的元素都是紧凑存储，即entries数组中的每个下标都存储了内容，没有冗余空间(字符串的数组是有冗余空间的)，

此时向ziplist中新增一个元素意为着要为数组再申请一部分内存空间(realloc)，根据当前ziplist占用的内存大小以及内存分配器算法，

realloc可能会重新分配新的内存空间，将原有内容一次性拷贝到新的空间中，也可能在原有地址上拓展空间，此时不需要进行内容拷贝，

如果ziplist占据的内存太大，重新分配内存或者拷贝内存就会有很大的资源消耗，因此ziplist不适合存储大型字符串和过多的元素。

prevlen 级联更新

entry中的prevlen字段存储前一个entry的长度，如果内容小于254字节，prevlen使用1字节存储，否则就是5字节，

这意味着如果某个entry(代号A)经过修改后，长度由253变成了254字节，那么下一个entry(代号B)的prevlen字段就需要进行更新，从1字节拓展为5字节，

如果该entry(代号B)的长度自身恰巧也是253字节，那么prevlen变成5字节后，长度成了258字节，那么再后面的entry(代号C)又要跟着更新，这是一个很耗费计算资源的操作。

// 压缩列表级联更新
unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) {
    size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), rawlen, rawlensize;
    size_t offset, noffset, extra;
    unsigned char *np;
    zlentry cur, next;

    while (p[0] != ZIP_END) {
        zipEntry(p, &cur);
        rawlen = cur.headersize + cur.len;
        rawlensize = zipStorePrevEntryLength(NULL,rawlen);

        /* Abort if there is no next entry. */
        if (p[rawlen] == ZIP_END) break;
        zipEntry(p+rawlen, &next);

        /* Abort when "prevlen" has not changed. */
        // prev 长度没有变，中断级联更新
        if (next.prevrawlen == rawlen) break;
        
        if (next.prevrawlensize < rawlensize) {
            /* The "prevlen" field of "next" needs more bytes to hold
             * the raw length of "cur". */
            // 级联拓展
            offset = p-zl;
            extra = rawlensize-next.prevrawlensize;
            // 拓大内存
            zl = ziplistResize(zl,curlen+extra);
            p = zl+offset;

            /* Current pointer and offset for next element. */
            np = p+rawlen;
            noffset = np-zl;

            /* Update tail offset when next element is not the tail element. */
            // 更新 zltail_offset指针
            if ((zl+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) != np) {
                ZIPLIST_TAIL_OFFSET(zl) =
                    intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra);
            }

            /* Move the tail to the back. */
            // 移动内存
            memmove(np+rawlensize,
                np+next.prevrawlensize,
                curlen-noffset-next.prevrawlensize-1);
            zipStorePrevEntryLength(np,rawlen);

            /* Advance the cursor */
            p += rawlen;
            curlen += extra;
        } else {
            if (next.prevrawlensize > rawlensize) {
                /* This would result in shrinking, which we want to avoid.
                 * So, set "rawlen" in the available bytes. */
                // 级联收缩
                zipStorePrevEntryLengthLarge(p+rawlen,rawlen);
            } else {
                // 大小没有变化，更改长度值
                zipStorePrevEntryLength(p+rawlen,rawlen);
            }

            /* Stop here, as the raw length of "next" has not changed. */
            break;
        }
    }
    return zl;
}

intset

当set集合存储的元素都是整数，并且元素比较少的时候，那么redis将采用intset进行存储，intset是一个紧凑的数组结构，支持16、32、64位整数。

intset结构：

struct intset<T> {
    int32 encoding; // 决定整数位宽是16位、32位还是64位
    int32 length;   // 元素个数 
    int<T> contents;// 整数数组，可以是16、32或64位
}

添加一个set结构，只有三个元素，debug可以看到encoding是intset。

127.0.0.1:6379> sadd intset-demo 1 2 3

(integer) 3

127.0.0.1:6379> debug object intset-demo

Value at:0xffff9658d2b0 refcount:1 encoding:intset serializedlength:15 lru:14949108 lru_seconds_idle:7

向set中添加一个字符串，encoding即变为hash结构。

127.0.0.1:6379> sadd intset-demo java

(integer) 1

127.0.0.1:6379> debug object intset-demo

Value at:0xffff9658d2b0 refcount:1 encoding:hashtable serializedlength:12 lru:14949166 lru_seconds_idle:2

quicklist

redis中的list在早期版本中，如果数据量比较小，使用的是ziplist，如果数据量较多，使用的是linkedlist。

// 链表节点
struct listNode<T> {
    listNode* prev;
    listNode* next;
    T value;
}
// 链表
struct list {
    listNode *head;
    listNode *tail;
    long length;
}

由于链表的每个节点都需要一个prev和next指针，两个指针需要占据16字节(64位操作系统的指针占用8个字节)的空间，

每个节点的内存都是单独分配，又加剧了内存的碎片化，影响内存管理效率，后来Redis使用了quicklist替代了ziplist和linkedlist。

127.0.0.1:6379> rpush quicklist-demo go java python

(integer) 3

127.0.0.1:6379> debug object quicklist-demo

Value at:0xffff9658d320 refcount:1 encoding:quicklist serializedlength:31 lru:14949574 lru_seconds_idle:17 ql_nodes:1 ql_avg_node:3.00 ql_ziplist_max:-2 ql_compressed:0 ql_uncompressed_size:29

可以看到，新建一个list结构，debug看到的encoding是quicklist。

quicklist是ziplist和linkedlist的混合体，其将linkedlist进行切分，每一段数据使用ziplist紧凑存储，多个ziplist之间使用指针串联。

为了进一步节约空间，redis还会使用LZF算法对ziplist进行压缩，可以选择压缩深度。

quicklist结构如下：

struct ziplist {
    ....上面有这里不写了
}

struct ziplist_compressed {
    int32 size;
    byte[] compressed_data;
}


struct quicklistNode {
    quicklistNode* prev;
    quicklistNode* next;
    ziplist* zl;        //指向压缩列表
    int32 size;         //ziplist的字节总数
    int16 count;        //ziplist中的元素数量
    int2 encoding;      //存储形式，原生字节数组还是LZF压缩存储
}

struct quicklist {
    quicklistNode* head;
    quicklistNode* tail;
    long count;          //元素总数
    int nodes;           //ziplist节点的个数
    int compressDepth;   //LZF算法压缩深度
}

ziplist容量

quicklist内部默认单个ziplist长度为8KB，超出这个字节数，就会另起一个ziplist，ziplist的长度由配置参数 list-max-ziplist-size 决定。

压缩深度

quicklist默认压缩深度为0，即不压缩，实际深度由配置参数list-compress-depth决定，为了支持快速的push/pop操作，quicklist首位两个ziplist不压缩，此时压缩深度就是1，

如果压缩深度是2，表示quicklist首尾第一、第二个ziplist都不压缩，下图的压缩深度即为1，因为首尾第一个ziplist没有压缩，第二个压缩了。

码农公寓