Redis设计与实现-数据结构篇（6）-压缩列表

发表于 | 分类于 |

压缩列表：压缩列表是列表键和哈希键的底层实现之一。为了提高内存存储效率而升级的。
当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么Redis会使用压缩列表来做列表键的底层实现。

注：redis 3.2以后，quicklist作为列表键的底层实现之一，代替了压缩列表。

压缩列表的组成

V73HxI.md.jpg

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
 * 保存 ziplist 节点信息的结构
 */
typedef struct zlentry {

    // prevrawlen ：前置节点的长度
    // prevrawlensize ：编码 prevrawlen 所需的字节大小
    unsigned int prevrawlensize, prevrawlen;

    // len ：当前节点值的长度
    // lensize ：编码 len 所需的字节大小
    unsigned int lensize, len;

    // 当前节点 header 的大小
    // 等于 prevrawlensize + lensize
    unsigned int headersize;

    // 当前节点值所使用的编码类型
    unsigned char encoding;

    // 指向当前节点的指针
    unsigned char *p;

} zlentry;

虽然定义了这个结构体，但是根本就没有使用zlentry结构来作为压缩列表中用来存储数据节点中的结构。
因为这个结构存小整数或短字符是在太浪费空间了。这个结构总共在32位机占用28个字节，64位机占用32个字节。这不符合压缩列表的设计目的。
压缩列表的节点真正结构如下图：
V73TGd.md.jpg

  • prev_entry_len：记录前驱节点的长度
  • encoding：记录当前节点的value成员的数据类型以及长度
  • value：根据encoding保存字节数组或整数

prev_entry_len

prev_entry_len成员实际上就是zlentry结构中prevrawlensize,和prevrawlen这两个成员的压缩版。
这两个成员都是int类型，因此将两者压缩为一个成员prev_entry_len。分别对不同长度的前驱节点使用不同的字节数表示：
1) 如果前置节点的长度小于 254 字节，那么程序将使用 1 个字节来保存这个长度值。
2) 如果前置节点的长度大于等于 254 字节，那么程序将使用 5 个字节来保存这个长度值：
a) 第 1 个字节的值将被设为 254 ，用于标识这是一个 5 字节长的长度值。
b) 之后的 4 个字节则用于保存前置节点的实际长度。

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
/* Encode the length of the previous entry and write it to "p". Return the
 * number of bytes needed to encode this length if "p" is NULL. 
 *
 * 对前置节点的长度 len 进行编码，并将它写入到 p 中，
 * 然后返回编码 len 所需的字节数量。
 *
 * 如果 p 为 NULL ，那么不进行写入，仅返回编码 len 所需的字节数量。
 *
 * T = O(1)
 */
static unsigned int zipPrevEncodeLength(unsigned char *p, unsigned int len) {

    // 仅返回编码 len 所需的字节数量
    if (p == NULL) {
        return (len < ZIP_BIGLEN) ? 1 : sizeof(len)+1;

    // 写入并返回编码 len 所需的字节数量
    } else {

        // 1 字节
        if (len < ZIP_BIGLEN) {
            p[0] = len;
            return 1;

        // 5 字节
        } else {
            // 添加 5 字节长度标识
            p[0] = ZIP_BIGLEN;
            // 写入编码
            memcpy(p+1,&len,sizeof(len));
            // 如果有必要的话，进行大小端转换
            memrev32ifbe(p+1);
            // 返回编码长度
            return 1+sizeof(len);
        }
    }
}

encoding

和prev_entry_len一样，encoding成员同样可以看做成zlentry结构中lensize和len的压缩版。
同样的lensize和len都是占4个字节的，因此将两者压缩为一个成员encoding，只要encoding能够同时具有lensize和len成员的功能，而且对当前节点保存的是字节数组还是整数分别编码。

zlentry中len字段配合encoding字段进行了编码, 尽量压缩字段长度, 减少内存使用。
1）如果节点保存的是字符串，那么使用两个字节来保存编码字符串长度所使用的类型。之后的跟着的内容为字符串的实际长度。

1. |00pppppp| 字符串长度小于等于63字节（6bit)
2. |01pppppp|qqqqqqqq| 字符串长度小于等于16383字节(14bit)
3. |10______|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| 字符串大于等于16384字节；

2）如果节点保存的是征收值，则头两位设置为1，紧跟着的两位用于标识节点所保存的整数类型。

1. |11000000| 节点的值为 int16_t 类型的整数，长度为 2 字节。
2. |11010000| 节点的值为 int32_t 类型的整数，长度为 4 字节。
3. |11100000| 节点的值为 int64_t 类型的整数，长度为 8 字节。
4. |11110000| 节点的值为 24 位（3 字节）长的整数。
5. |11111110| 节点的值为 8 位（1 字节）长的整数。
6. |1111xxxx| 节点的值为介于 0 至 12 之间的无符号整数。取出来的值还得减一。
7. |11111111| ziplist 的结尾标识

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
/*字符串编码标识使用了最高2bit位 */
#define ZIP_STR_06B (0 << 6)  //6bit
#define ZIP_STR_14B (1 << 6)  //14bit
#define ZIP_STR_32B (2 << 6)  //32bit

/*zlentry中len字段进行编码过程*/
static unsigned int zipEncodeLength(unsigned char *p, unsigned char encoding, unsigned int rawlen) {
    unsigned char len = 1, buf[5];

    if (ZIP_IS_STR(encoding)) {
        /*
          *6bit可以存储, 占用空间为1个字节, 值存储在字节后6bit中.
          */
        if (rawlen <= 0x3f) {
            if (!p) return len;
            buf[0] = ZIP_STR_06B | rawlen;
        } else if (rawlen <= 0x3fff) {
            len += 1;
            if (!p) return len;
               /*14bit可以存储, 置前两个bit位为ZIP_STR_14B标志 */
            buf[0] = ZIP_STR_14B | ((rawlen >> 8) & 0x3f);
            buf[1] = rawlen & 0xff;
        } else {
            len += 4;
            if (!p) return len;
            buf[0] = ZIP_STR_32B;
            buf[1] = (rawlen >> 24) & 0xff;
            buf[2] = (rawlen >> 16) & 0xff;
            buf[3] = (rawlen >> 8) & 0xff;
            buf[4] = rawlen & 0xff;
        }
    } else {
        /* 内容编码为整型, 长度默认为1*/
        if (!p) return len;
        buf[0] = encoding;
    }

    /* Store this length at p */
    memcpy(p,buf,len);
    return len;
}
2.3 zlentry之encoding和p编码
zlentry中encoding和p表示元素编码和内容, 下面分析下具体编码规则, 可以看到这里对内存节省真是到了魔性的地步. encoding是保存在len字段第一个字节中, 第一个字节最高2bit标识字符串编码, 5和6bit位标识是整数编码, 解码时直接从第一个字节中获取编码信息.

/* 整数编码标识使用了5和6bit位 */
#define ZIP_INT_16B (0xc0 | 0<<4)  //16bit整数
#define ZIP_INT_32B (0xc0 | 1<<4)  //32bit整数
#define ZIP_INT_64B (0xc0 | 2<<4)  //64bit整数
#define ZIP_INT_24B (0xc0 | 3<<4)  //24bit整数
#define ZIP_INT_8B 0xfe            //8bit整数

#define ZIP_INT_IMM_MASK 0x0f
#define ZIP_INT_IMM_MIN 0xf1    /* 11110001 */
#define ZIP_INT_IMM_MAX 0xfd    /* 11111101 */

static int zipTryEncoding(unsigned char *entry, unsigned int entrylen, long long *v, unsigned char *encoding) {
    long long value;
    if (entrylen >= 32 || entrylen == 0) return 0;
   
    if (string2ll((char*)entry,entrylen,&value)) {
        /* 0-12之间的值, 直接在保存在了encoding字段中, 其他根据值大小, 直接设置为相应的编码*/
        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;
}

连锁更新

当将一个新节点添加到某个节点之前时，如果原节点的header空间不足以保存新节点的长度，那么就需要对原节点的header空间进行扩展（从1字节扩展到5字节）。但是当对这个节点进行扩展后，可能又会引起后续节点的扩展，这就会引起连锁更新。这种情况在多个连续节点的长度都接近 ZIP_BIGLEN 时可能发生。

反过来说，因为节点的长度变小而引起的连续缩小也是可能出现的，为了避免扩展-缩小-扩展-缩小这样的情况反复出现（flapping，抖动），我们不处理这种情况，而是任由 prevlen 比所需的长度更长。