Redis 压缩列表相关源码阅读笔记，源码文件 ziplist.h & ziplist.c。

1. 小结

  • ziplist 是为了节省内存而设计的压缩双向链表，支持 push 和 pop 操作
  • 由于 ziplist 存储在连续的内存中，因此每次修改都需要 realloc 和 memmove 操作，因此具体的时间复杂度取决于 ziplist 占用内存的大小
  • 执行插入或删除操作时，可能会因为 prevlen 的变化而引发 cascade update

2. ziplist 数据结构

1
2
3
4
5
6

+---------+---------+---------+-------+-------+-----+-------+--------+
| zlbytes | zltail  | zllen   | entry | entry | ... | entry | zlend  |
+---------+---------+---------+-------+-------+-----+-------+--------+
     ^         ^         ^                                       ^
     |         |         |                                       |
  uint32_t  uint32_t  uint16_t                                uint8_t
  • 所有 field 默认按 little endian 存储
  • zlbytes: 存储 ziplist 所占用的字节总数，包含 zlbytes 本身
  • zltail: 存储尾部 entry 的 offset
  • zllen: 存储 entry 个数。当 entry 个数超过 $2^{16}-2$ 时，其值均为 $2^{16}-1$，此时需遍历 ziplist 方可知晓 entry 个数
  • zlend: ziplist 尾部标识，其值为 255(0xFF)，entry 首字节不可为 255(0xFF)

entry 结构

1
2
3
4
5

+---> entry head <---+
|                    |
+---------+----------+------------+
| prevlen | encoding | entry-data |
+---------+----------+------------+

  • prevlen: 存储前一 entry 长度，用于反向遍历

    • 如果长度小于 254，使用 1 字节存储该长度
    • 如果长度大于 254，prevlen 占用 5 字节，首字节为 0xFE 标识，后 4 字节存储该长度

    前一 entry 长度由小于 254 变为大于 254 时，由于 prevlen 长度的变化，导致自身长度也会增长，因此可能会引发 cascade update

  • encoding: 使用首字节表示 entry 中存储的数据类型

    • 首字节前 2 bit 为 00, 01 或 10 时，数据类型为 string，encoding 中剩余 bit 还可用于存储 string 的长度
    • 首字节前 2 bit 为 11 时，数据类型为 integer，如整数较小(0-12)，则会省略 entry-data 部分，直接在 encoding 中存储整数值
encoding encoding size entry-data size entry type
00pppppp 1 byte $\le 63$ bytes String value with length less than or equal to 63 bytes (6 bits)
01pppppp + 1 byte 2 bytes $\le 16383$ bytes String value with length less than or equal to 16383 bytes (14 bits, The 14 bit number is stored in big endian)
10000000 + 4 bytes 5 bytes $\ge 16384$ bytes String value with length greater than or equal to 16384 bytes. Only the 4 bytes following the first byte represents the length up to $2^{32}-1$ (The 32 bit number is stored in big endian)
11000000 1 byte 2 bytes Integer encoded as int16_t (2 bytes)
11010000 1 byte 4 bytes Integer encoded as int32_t (4 bytes)
11100000 1 byte 8 bytes Integer encoded as int64_t (8 bytes)
11110000 1 byte 3 bytes Integer encoded as 24 bit signed (3 bytes)
11111110 1 byte 1 byte Integer encoded as 8 bit signed (1 byte)
1111xxxx 1 byte \ Unsigned integer from 0 to 12 (4 bit)
  • 整型使用 little endian 字节序存储。
  • 在 4 bit 无符号整数中，真实存储的值为 0001 至 1101 (1 至 13)，因为 11110000 表示 24 bit 有符号整型，11111110 表示 8 bit 有符号整型，11111111 表示 zlend，因此这三个值均已被占用

3. ziplist APIs

3.1. ziplistNew

1
2

/* Create a new empty ziplist. */
unsigned char *ziplistNew(void);

3.2. ziplistMerge

1
2

/* Merge ziplists 'first' and 'second' by appending 'second' to 'first'. */
unsigned char *ziplistMerge(unsigned char **first, unsigned char **second);
  • 如果 merge 操作无法执行，返回 NULL
  • 在 first 和 second 中，挑选长度更长的进行 zrealloc，另一个在 join 之后 zfree，函数执行后 first 和 second 指针均不可使用

3.3. ziplistPush

1
2

unsigned char *ziplistPush(unsigned char *zl, unsigned char *s,
                           unsigned int slen, int where);

根据 where 参数将长为 slen 的元素 s 插入压缩列表 zl 的头部或尾部。

3.4. ziplistIndex

1
2
3
4

/* Returns an offset to use for iterating with ziplistNext. When the given
 * index is negative, the list is traversed back to front. When the list
 * doesn't contain an element at the provided index, NULL is returned. */
unsigned char *ziplistIndex(unsigned char *zl, int index);

3.5. ziplistNext

1
2
3
4

/* Return pointer to next entry in ziplist.
 * p is the pointer to the current element
 * The element after 'p' is returned, otherwise NULL if we are at the end. */
unsigned char *ziplistNext(unsigned char *zl, unsigned char *p);

3.6. ziplistPrev

1
2

/* Return pointer to previous entry in ziplist. */
unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p);

3.7. ziplistGet

1
2
3

/* Get entry data pointed to by 'p' */
unsigned int ziplistGet(unsigned char *p, unsigned char **sstr,
                        unsigned int *slen, long long *sval);
  • 如果 p 为 NULL 或 ZIP_END，则返回值为 0，否则为 1
  • 如果 p 所指向的 entry 存储的数据类型为 string，则填充 sstr 和 slen，以获取字符串值
  • 如果 p 所指向的 entry 存储的数据类型为 integer，则填充 sval，以获取整型值，此时 sstr = NULL

3.8. ziplistInsert

1
2
3

/* Insert an entry at "p". */
unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p,
                             unsigned char *s, unsigned int slen);

3.9. ziplistDelete

1
2
3
4

/* Delete a single entry from the ziplist, pointed to by *p.
 * Also update *p in place, to be able to iterate over the
 * ziplist, while deleting entries. */
unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p);

3.10. ziplistDeleteRange

1
2

/* Delete a range of entries from the ziplist. */
unsigned char *ziplistDeleteRange(unsigned char *zl, int index, unsigned int num);

3.11. ziplistCompare

1
2
3

/* Compare entry pointer to by 'p' with 'sstr' of length 'slen'. */
/* Return 1 if equal. */
unsigned int ziplistCompare(unsigned char *p, unsigned char *sstr, unsigned int slen);

3.12. ziplistFind

1
2
3
4

/* Find pointer to the entry equal to the specified entry. Skip 'skip' entries
 * between every comparison. Returns NULL when the field could not be found. */
unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr,
                           unsigned int vlen, unsigned int skip);

3.13. ziplistLen

1
2

/* Return length of ziplist. */
unsigned int ziplistLen(unsigned char *zl);

3.14. ziplistBlobLen

1
2

/* Return ziplist blob size in bytes. */
size_t ziplistBlobLen(unsigned char *zl);

3.15. ziplistRepr

1

void ziplistRepr(unsigned char *zl);

格式化输出 ziplist。