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


1. 小结

  • ziplist 是为了节省内存而设计的压缩双向链表,支持 pushpop 操作
  • 由于 ziplist 存储在连续的内存中,因此每次修改都需要 reallocmemmove 操作,因此具体的时间复杂度取决于 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, 0110 时,数据类型为 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 无符号整数中,真实存储的值为 00011101 (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
  • firstsecond 中,挑选长度更长的进行 zrealloc,另一个在 join 之后 zfree,函数执行后 firstsecond 指针均不可使用

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);
  • 如果 pNULLZIP_END,则返回值为 0,否则为 1
  • 如果 p 所指向的 entry 存储的数据类型为 string,则填充 sstrslen,以获取字符串值
  • 如果 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