【Redis源码】ziplist压缩表（八）
前言：
压缩表是一个连续内存空间的线性结构，元素之间紧挨着存储，没有任何空隙。redis为了节省空间，当使用zset和hash容器对象时再元素个数较少时采取了压缩表（ziplist）进行存储。
1.压缩表结构介绍
压缩表构成如下：
zlbytes :
压缩表字节长度，类型uint32_t占用4个字节，需要存储此值才能调整整个结构的大小。压缩表的大小为2^32 - 1。
zltail:
是列表中最后一个条目的偏移量,类型uint32_t占用4个字节。
zllen：
压缩表个数，类型uint16_t占用2个字节，个数最大数量为2^16-1，也就是65535。必须遍历整个压缩表才能知道它的个数。
entry:
压缩表存储元素，可以是字节数组或者是整数。
zlend:
结束标识，类型uint8_t占用1个字节。该值为255，对应ZIP_END宏,16进制为0xFF。
压缩表各字段间的获取宏如下，ziplist.c中：
//ziplist的zlbytes字段
#define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl)))
//ziplist的zltail字段
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
//ziplist的zllen字段
#define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
//最后一个字节，对应zlend字段
#define ZIPLIST_ENTRY_END(zl) ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)
//ziplist头大小10字节
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
//尾大小1字节
#define ZIPLIST_END_SIZE (sizeof(uint8_t))
//ziplist数据头入口也就是第一个entry结构位置
#define ZIPLIST_ENTRY_HEAD(zl) ((zl)+ZIPLIST_HEADER_SIZE)
//ziplist数据最后一个entry入口,最后一个entry结构位置
#define ZIPLIST_ENTRY_TAIL(zl) ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))
2.压缩表entry介绍
prevlen：
压缩表中前一个entry的长度，占用1个或者5个字节。
1）若前一个entry占用的字节数小于254，则prevlen字段占1个字节。
2）若前一个entry占用字节数大于或等于254，则prevlen字段占用5个字节。注意此时第一个字节固定为254，即0xFE，另外4个字节以uint32_t存储值。
encoding：
entry的编码，表示当前entry存储数据的类型和数据的长度。
字符串编码规则如下：
| 编码示例 | 字节长度 | 备注 |
|---|---|---|
| 00pppppp | 1字节 | 长度小于或等于63字节（6位）的字符串值。“pppppp”表示无符号的6位长度。 |
| 01pppppp qqqqqqqq | 2字节 | 长度小于或等于16383字节（14位）的长度。“pppppp qqqqqqqq”表示长度 |
| 10000000 qqqqqqqq rrrrrrrr ssssssss tttttttt | 5字节 | 特大字符串,长度小于等于 4294967295 （32位）字节的字节数组；“qqqqqqqq rrrrrrrr ssssssss tttttttt” 这4个字节表示长度 |
整型编码规则如下：
| 编码示例 | 字节长度 | 备注 |
|---|---|---|
| 11000000 | 1字节 | 表示 int16_t类型的整数 |
| 11010000 | 1字节 | 表示 int32_t类型的整数 |
| 11100000 | 1字节 | 表示 int64_t类型的整数 |
| 11110000 | 1字节 | 表示 24位类型的整数 |
| 11111110 | 1字节 | 表示8位类型的整数 |
| 1111xxxx | 1字节 | 表示极小整数，xxxx 的范围只能是 (0001~1101), 也就是1~13，因为0000、1110、1111都被占用了。读取到的 value 需要将 xxxx 减 1，也就是整数0~12就是最终的 value。 |
entry-data：
数据存储的值。大小由encode
对应的编码宏如下,ziplist.c中：
#define ZIP_STR_MASK 0xc0
#define ZIP_INT_MASK 0x30
#define ZIP_STR_06B (0 << 6)
#define ZIP_STR_14B (1 << 6)
#define ZIP_STR_32B (2 << 6)
#define ZIP_INT_16B (0xc0 | 0<<4)
#define ZIP_INT_32B (0xc0 | 1<<4)
#define ZIP_INT_64B (0xc0 | 2<<4)
#define ZIP_INT_24B (0xc0 | 3<<4)
#define ZIP_INT_8B 0xfe
根据以上内容，咱们可以看一下如下hash命令的ziplist存储结构
127.0.0.1:6379> hmset name5 a zhaoyu b hello
看上面两张图，解析name5点hash数据存储结构。zl为ziplist的字节数组。
1) 0 ～ 9的10个字节对应zlbytes、zltail、zllen三个字段。
2)然后从zl[10]开始，zl[10]等于prevlen字段当前是0。因为zl[10]是第一个entry没有之前所以为0。然后zl[11]等于十六进制0x1，在二进制下是0000 0001，开头两位是00说明对应1字节的字符数组。其次就是占用一个字节，所以我们zl[12]得到a键。也就是我们命令行中的hmset name5 a中的a。
3)从zl[13]对应prevlen字段，当前是0x3。说明前一个entry是3个字节。确实是 zl[10] ~zl[12]三个字节。然后zl[14]等于十六进制0x6，说明是6个字节的的字符数组。刚好得到zhaoyu 6个字符。
4）zl[31]当前等于10进制255对应0xFF。也就是结尾。
zlentry结构体，ziplist.c中：
typedef struct zlentry {
unsigned int prevrawlensize; /* 前一个元素的内存大小的编码空间 */
unsigned int prevrawlen; /* 前一个元素的内存大小. */
unsigned int lensize; /* 当前元素value部分占用内存大小的编码空间 */
unsigned int len; /* 当前元素value部分占用内存大小 */
unsigned int headersize; /* 当前元素value部分占用内存大小 */
unsigned char encoding; /* 编码类型，标志value的类型和占用的字节数. */
unsigned char *p; /* 内容 */
} zlentry;
zlentry并不是实际的zl中存储的，只是用作解析entry计算使用的结构体。
解码entry函数，ziplist.c中：
void zipEntry(unsigned char *p, zlentry *e) {
ZIP_DECODE_PREVLEN(p, e->prevrawlensize, e->prevrawlen); //解码prevlen字段
ZIP_DECODE_LENGTH(p + e->prevrawlensize, e->encoding, e->lensize, e->len); //解码encoding长度
e->headersize = e->prevrawlensize + e->lensize;
e->p = p;
}
解码prevlen字段宏，ziplist.c中：
#define ZIP_BIG_PREVLEN 254
#define ZIP_DECODE_PREVLEN(ptr, prevlensize, prevlen) do { \
ZIP_DECODE_PREVLENSIZE(ptr, prevlensize); \
if ((prevlensize) == 1) { \
(prevlen) = (ptr)[0]; \
} else if ((prevlensize) == 5) { \
assert(sizeof((prevlensize)) == 4); \
memcpy(&(prevlen), ((char*)(ptr)) + 1, 4); \
memrev32ifbe(&prevlen); \
} \
} while(0);
#define ZIP_DECODE_PREVLENSIZE(ptr, prevlensize) do { \
if ((ptr)[0] < ZIP_BIG_PREVLEN) { \
(prevlensize) = 1; \
} else { \
(prevlensize) = 5; \
} \
} while(0);
该宏其实是解码prevrawlensize字段，是1个字节还是5个字节空间。
解码的长度宏如下ziplist.c中：
#define ZIP_DECODE_LENGTH(ptr, encoding, lensize, len) do { \
ZIP_ENTRY_ENCODING((ptr), (encoding)); \
if ((encoding) < ZIP_STR_MASK) { //判断是否为字节数组 \
if ((encoding) == ZIP_STR_06B) { //63字节的字节数组 \
(lensize) = 1; \
(len) = (ptr)[0] & 0x3f; \
} else if ((encoding) == ZIP_STR_14B) { //16383字节内的字节数组 \
(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);
获得zip的整型大小，可以看一下整型编码规则表，代码ziplist.c中：
unsigned int zipIntSize(unsigned char encoding) {
switch(encoding) {
case ZIP_INT_8B: return 1; //
case ZIP_INT_16B: return 2;
case ZIP_INT_24B: return 3;
case ZIP_INT_32B: return 4;
case ZIP_INT_64B: return 8;
}
if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX)
return 0; /* 4 bit immediate */
panic("Invalid integer encoding 0x%02X", encoding);
return 0;
}
3.压缩表ziplist的API说明
| 函数名称 | 用途 | 复杂度 | 连锁更新 |
|---|---|---|---|
| ziplistNew | 创建一个新的压缩表 | O(1) | 无 |
| ziplistPush | 创建一个包含给定值的新节点， 并将这个新节点添加到压缩列表的表头或者表尾 | 平均 O(N^2) | 使用 |
| ziplistInsert | 将包含给定值的新节点插入到给定节点之后 | 平均 O(N^2) | 使用 |
| ziplistIndex | 返回压缩列表给定索引上的节点 | O(N) | 无 |
| ziplistFind | 在压缩列表中查找并返回包含了给定值的节点 | 因为节点的值可能是一个字节数组， 所以检查节点值和给定值是否相同的复杂度为 O(N^2) | 无 |
| ziplistNext | 返回给定节点的下一个节点 | O(1) | 无 |
| ziplistPrev | 返回给定节点的前一个节点 | O(1) | 无 |
| ziplistGet | 获取给定节点所保存的值 | O(1) | 无 |
| ziplistDelete | 从压缩列表中删除给定的节点 | 平均 O(N^2) | 使用 |
| ziplistDeleteRange | 删除压缩列表在给定索引上的连续多个节点 | 平均 O(N^2) | 使用 |
| ziplistBlobLen | 返回压缩列表目前占用的内存字节数 | O(1) | 无 |
| ziplistLen | 返回压缩列表目前包含的节点数量 | 节点数量小于 65535 时 O(N) | 无 |
总结
1）ziplist在zset和hash中使用到，元素个数较少时用到。
2）压缩表是一个字节数组，比较紧凑的结构。
3）压缩表可以存储存储多个节点，也就是entry。每个节点可以存储字节数组和整型两种数据。
4）压缩表支持最大个数65535个。
5）压缩表插入和删除可能会引起连锁更新。
加V信进群交流