Chapter 7 - 压缩列表

Created by : Mr Dk.

2020 / 06 / 01 16:45

Nanjing, Jiangsu, China

Ziplist Definition

当列表项中要么是 小整数值，要么是 较短的字符串 时，Redis 使用压缩列表来作为列表键的底层实现。压缩列表由一系列特殊编码的连续内存块组成的顺序结构，其中可以包含任意多个结点，每个结点可以用于保存一个字节数组或整数值。

Attribute	Type	Length	Description
`zlbytes`	`uint32_t`	4B	记录整个压缩列表的字节长度
`zltail`	`uint32_t`	4B	列表中最后一个结点距离列表起始地址的偏移 (不需遍历就能确定表尾结点位置)
`zllen`	`uint16_t`	2B	列表中的结点数量 (当数量超过其能表示的最大范围时，需要遍历整个列表才能得到结果)
`entryX`	列表结点	不一定	各个结点
`zlend`	`uint8_t`	1B	`0xFF`，标记压缩列表末端

如果前一结点的长度小于 254B，previous_entry_length 用一个字节来表示；否则，就使用五个字节 - 第一字节为 0xFE，剩余四个字节表示长度。编码方式也类似，不同的编码方式对应了不同的长度。

当前一结点的长度超过 254B 阈值时，后续结点就需要将 1B 的 previous_entry_length 修改为 5B 的表示形式，从而引发后续结点也变长了。如果比较倒霉，后续结点又会发生连锁的更新。类似地，从列表中删除元素时，也存在这种可能。但是在实际的使用中，发生这种情况的概率很低。

疑问
结点的内容是直接存在列表中，还是只在列表中保存了指向内容的指针？如果结点的内容发生变化，长度发生变化，那么后续结点的内容是不是也会跟着在内存中后移？这样会不会存在性能问题？