Redis 压缩列表

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

127.0.0.1:6379> RPUSH lst 1 3 5 10086 "hello" "world"
(integer) 6
127.0.0.1:6379> OBJECT ENCODING lst
"ziplist"

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

127.0.0.1:6379> HMSET profile 100 "hello" "world"
OK
127.0.0.1:6379> OBJECT ENCODING profile 
"ziplist"

相关代码在 ziplist.h, ziplist.c。

压缩列表的构成

image.png

属性	类型	长度	用途
zlbytes	uint32_t	4字节	记录整个压缩列表占用的内存字节数量
zltail	uint32_t	4字节	记录压缩列表表尾节点距离压缩列表的起始地址有多少字节
zllen	uint16_t	2字节	记录包含的压缩列表节点数量
entryX	uint32_t	不定
zlend	uint8_t	1字节	特殊值(255)，用于标记压缩列表的末端

/* 创建并返回一个新的 ziplist T = O(1) */
unsigned char *ziplistNew(void) 
{
    // #define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))
    // 1 字节是表末端 ZIP_END 的大小
    unsigned int bytes = ZIPLIST_HEADER_SIZE + 1;

    // 为表头和表末端分配空间
    unsigned char *zl = zmalloc(bytes);

    // 初始化表属性
    ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
    ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
    ZIPLIST_LENGTH(zl) = 0;

    // 设置表末端
    zl[bytes-1] = ZIP_END;

    return zl;
}

image.png

压缩列表节点的构成

每个压缩列表节点可以保存一个字节数组或者一个整数值：
其中字节数组可以是以下3种长度之一：

• 长度小于等于 63(2^6 - 1) 字节的数组
• 长度小于等于 16383(2^14 - 1) 字节的数组
• 长度小于等于 4294967295(2^32 - 1) 字节的数组

而整数值则可以是以下六种长度的其中一种：

• 4位长，介于 0 至 12 之间的无符号整数。
• 1字节长的有符号整数
• 3字节长的有符号整数
• int16_t 类型整数
• int32_t 类型整数
• int64_t 类型整数

压缩列表节点构成：

image.png

• previous_entry_length
  如果前一节点的长度小于 254 字节，那么previous_entry_length属性的长度为1字节，前一节点的长度就保存在这一字节里面。
  如果前一节点的长度大于254字节，那么previous_entry_length 属性的长度为5字节，其中属性的第一字节会被设置为0XFE，而之后的四个字节用于保存前一节点的长度。
  

  image.png

• encoding
  encoding节点的属性记录了节点的content属性所保存数据的类型和长度。
  整数的编码：

  编码	编码长度	content 属性保存的值
  11000000	1字节	int16_t 类型的整数
  11010000	1字节	int32_t 类型的整数
  11100000	1字节	int64_t 类型的整数
  11110000	1字节	24位有符号的整数
  11111110	1字节	8位有符号整数
  1111xxxx	1字节	没有相应的content 属性，xxxx可以保存一个0到12的数

  字节数组的编码：

  编码	编码长度	content 属性保存的值
  00bbbbbb	1字节	长度小于等于 63(2^6 - 1) 字节的数组
  01bbbbbb xxxxxxxx	2字节	长度小于等于 16383(2^14 - 1) 字节的数组
  10_ _ _ _ _ _ aaaaaaaa bbbbbbbb cccccccc dddddddd	5字节	长度小于等于 4294967295(2^32 - 1) 字节的数组

• content
  节点的content属性负责保存节点的值，节点值可以是一个字节数组或者整数。值的类型和长度由节点的encoding属性决定。
  如图所示：
  image.png

连锁更新的问题

每个节点的previous_entry_length属性都记录了前一个节点的长度，要么1字节长度或者5字节长度。
现在考虑这样一种情况：在一个压缩列表中，有多个连续的长度介于250字节到253字节之间的节点e1 至 eN，

假设e1 至 eN 的所有节点的长度都小于254字节，所以记录这些节点的长度只需要1字节长的previous_entry_length，这时我们将一个长度大于等于254字节的新节点new设置为压缩列表的表头节点，那么new 将成为e1的前置节点，

因为e1的previous_entry_length属性仅仅长为1字节，它没办法保存新节点new的长度，所以redis对压缩列表执行空间重分配操作，并将previous_entry_length属性从原来的1字节长度扩展为5字节长。但这时e1 的长度因为的也变为大于，此时e2的previous_entry_length也需要扩容为5字节。如此，有可能程序也许需要不断的对压缩列表进行空间的重分配操作，直到eN为止。

image.png

同样删除节点也可能导致连锁更新。

image.png

压缩列表的API