Redis之压缩列表

压缩列表的应用场景

压缩列表（ziplist）是hash键的底层实现之一。

当一个hash键只包含少量键值对，并且每个键值对的键和值要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会用压缩列表来做hash键的底层实现。

压缩列表的定义

压缩列表是Redis为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序性数据结构。

单个节点的定义如下：

属性	previous_entry_length	encoding	content
大小	1或者5字节	1字节、2字节或5字节	不定

previous_entry_length：记录了前一个entry的长度。大小可以是1个字节或者5个字节。1个字节就不用说了，5个字节时，第一个字节会被赋值成0xFE，后面4个字节才是真实的大小。

encoding：记录了节点的content属性所保存数据的类型及长度。

• 1字节、2字节或者5字节长，第1个字节的最高位为00、01或10的是字节数组编码，表示content存储的是字节数组。数组的长度由剩下的其他位记录。

编码	编码长度	content属性保存的值
00bbbbbb	1字节	长度小于等于63字节的字节数组(2^6)
01bbbbbb xxxxxxxx	2字节	长度小于等于16383字节的字节数组(2^14)
10xxxxxxx aaaaaaaa bbbbbbbb cccccccc dddddddd	5字节	长度小于等于4294967295字节的字节数组(2^32)，最前面6位不用

• 1字节，值的最高位以11开头的是整数编码，表示content存储的是整数值。整数值的类型和长度由后面6位记录。

编码	编码长度	content属性保存的值
11000000	1字节	int16_t类型的整数
11010000	1字节	int32_t类型的整数
11100000	1字节	int64_t类型的整数
11110000	1字节	24位有符号整数
11111110	1字节	8位有符号整数
1111xxxx	1字节	不存在content，需要保存的值（0-12）已经存放在encoding的后四位xxxx中

content：节点保存的内容，既可以是字符数组，也可以是整数值。

添加节点时，统一传入的都是unsigned char类型的字节数组，添加过程中会根据能否转化为数字进行判断具体的数值类型

/* Check if string pointed to by 'entry' can be encoded as an integer.
 * Stores the integer value in 'v' and its encoding in 'encoding'. */
int zipTryEncoding(unsigned char *entry, unsigned int entrylen, long long *v, unsigned char *encoding) {
    long long value;

    if (entrylen >= 32 || entrylen == 0) return 0;
    // string转换成long long
    if (string2ll((char*)entry,entrylen,&value)) {
        /* Great, the string can be encoded. Check what's the smallest
         * of our encoding types that can hold this value. */
        if (value >= 0 && value <= 12) {
            *encoding = ZIP_INT_IMM_MIN+value;
        } else if (value >= INT8_MIN && value <= INT8_MAX) {
            *encoding = ZIP_INT_8B;
        } else if (value >= INT16_MIN && value <= INT16_MAX) {
            *encoding = ZIP_INT_16B;
        } else if (value >= INT24_MIN && value <= INT24_MAX) {
            *encoding = ZIP_INT_24B;
        } else if (value >= INT32_MIN && value <= INT32_MAX) {
            *encoding = ZIP_INT_32B;
        } else {
            *encoding = ZIP_INT_64B;
        }
        *v = value;
        return 1;
    }
    return 0;
}

压缩列表构成如下：

属性	zlbytes	zltail	zllen	entry0	...	entryX	zlend
类型	uint32_t	uint32_t	uint16_t	ziplistEntry	ziplistEntry	ziplistEntry	uint8_t
长度	4字节	4字节	2字节				1字节
说明	整个压缩列表的大小	压缩列表尾节点距离列表起始地址的偏移量	节点数量，当这个值等于UINT16_MAX时需要遍历统计	压缩列表的节点	压缩列表的节点	压缩列表的节点	特殊值0xFF，用于标记压缩列表的末端

压缩列表的结构图

压缩列表.PNG

连锁更新

如果在头部或者中间插入节点的话，由于新插入的节点与之前节点的大小不一样，会导致后续节点保存的前一节点的大小发生变化，从而需要连锁更新后续节点的内容。不过一般只要不是正好在254字节左右，都不会引发大量的连锁更新。