ZIPLIST
简介
ziplist是一个经过特殊编码的双向链表，它的设计目标就是为了提高存储效率。ziplist可以用于存储字符串或整数，其中整数是按真正的二进制表示进行编码的，而不是编码成字符串序列。它能以O(1)的时间复杂度在表的两端提供push和pop操作。
实际上，ziplist充分体现了Redis对于存储效率的追求：
- 如果是一个普通的双向链表，链表中每一项都占用独立的一块内存，各项之间用地址指针（或引用）连接起来。这种方式会带来大量的内存碎片，而且两个地址指针需要额外八个字节，也会占用额外的内存。
- ziplist将表中每一项存放在前后连续的地址空间内，一个ziplist整体占用一大块内存。它是一个表（list），但其实不是一个链表（linked list）。
具体实现
概述
ziplist的结构如下图表所示：
| 属性 | 类型 | 长度 | 用途 |
|---|---|---|---|
| zlbytes | uint32_t | 4 字节 | 记录整个压缩列表占用的内存字节数 |
| zltail | uint32_t | 4 字节 | 记录压缩列表表尾节点距离压缩列表的起始地址有多少字节，通过这个偏移量，可以确定表尾节点的地址。 |
| zllen | uint16_t | 2 字节 | 记录了压缩列表包含的节点数量。 最大值为UINT16_MAX （65534），如果超过这个值，此处会记录为65535，但节点的真实数量需要遍历整个压缩列表才能计算得出。（因此需要避免bigKey） |
| entry | 列表节点 | 不定 | 压缩列表包含的各个节点，节点的长度由节点保存的内容决定。 |
| zlend | uint8_t | 1 字节 | 特殊值 0xFF （十进制 255 ），用于标记压缩列表的末端。 |
zlbytes,zltail,zllen占据多个字节，在存储的时候有大端（big endian）和小端（little endian）的区别。ziplist采取的是小端模式来存储；- 列表节点
entry并不像普通链表那样记录前后节点的指针，而是记录了前一个节点的长度； - ZipListEntry中的encoding编码分为字符串和整数两种。
Entry的具体构成
列表节点entry的结构可以表示为下图：
-
previous_entry_length：前一节点的长度，占1个或5个字节。
- 如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值
- 如果前一节点的长度大于254字节，则采用5个字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长度数据
-
encoding：编码属性，记录content的数据类型（字符串还是整数）以及长度，占用1个、2个或5个字节
-
contents：负责保存节点的数据，可以是字符串或整数
当正序访问时，由于可以得知当前节点的头地址和字节数，可以直接通过加上地址偏移量访问到下一个节点；当逆序访问时，由于可以得知上一个节点的字节数，可以通过减去地址偏移量访问上一个节点。
ZipList中所有存储长度的数值也采用小端字节序，即低位字节在前，高位字节在后。例如：数值0x1234，采用小端字节序后实际存储值为：0x3412
Encoding编码
ZipListEntry中的encoding编码分为字符串和整数两种：
字符串：如果encoding是以“00”、“01”或者“10”开头，则证明content是字符串，高两位用来标识编码长度，剩下的位用来表示字符串大小。
| 编码 | 编码长度 | 字符串大小 |
|---|---|---|
| |00pppppp| | 1 bytes | <= 63 bytes |
| |01pppppp|qqqqqqqq| | 2 bytes | <= 16383 bytes |
| |10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| | 5 bytes | <= 4294967295 bytes |
例如：保存字符串：“ab”和 “bc”到Ziplist，结构如下，注意蓝线标识是由于小端字节序，低位字节在前。
整数：如果encoding是以“11”开始，则证明content是整数，且encoding固定只占用1个字节
| 编码 | 编码长度 | 整数类型 |
|---|---|---|
| 11000000 | 1 | int16_t（2 bytes） |
| 11010000 | 1 | int32_t（4 bytes） |
| 11100000 | 1 | int64_t（8 bytes） |
| 11110000 | 1 | 24位有符整数(3 bytes) |
| 11111110 | 1 | 8位有符整数(1 bytes) |
| 1111xxxx | 1 | 直接在xxxx位置保存数值，范围从0001~1101，减1后结果为实际值 |
例如，一个ZipList中包含两个整数值：“2”和“5”
Ziplist连锁更新问题
由上面的介绍可知ZipList的每个Entry都包含previous_entry_length来记录上一个节点的大小，长度是1个或5个字节。
现在，假设我们有N个连续的、长度为250~253字节之间的entry，因此entry的previous_entry_length属性均用1个字节即可表示。
而当我们在ZipList的起始位置插入了一个超出254字节的entry，就会发生以下情况：
- 第二个节点的previous_entry_length变为5个字节；
- 第二个节点的entry总长度超出254字节；
- 第三个节点的previous_entry_length变为5个字节；
- …
ZipList这种特殊情况下产生的连续多次空间扩展操作称之为连锁更新（Cascade Update）。新增、删除都可能导致连锁更新的发生。
Ziplist与Dict的转换
Redis 的 HASH 数据结构可以使用两种底层实现：
ziplist：适用于存储小数据量的哈希表。
dict：适用于存储大数据量的哈希表。
得益于ziplist的紧凑存储，小数据量的Hash结构会使用ziplist实现，节省内存。但在大数据量下，ziplist的操作复杂度（尤其是查询复杂度）增加。此时Redis 会根据以下条件将 ziplist 转换为 dict：
- 元素数量超过阈值：当
HASH中的元素数量超过hash-max-ziplist-entries配置的值时，ziplist会被转换为dict。默认值通常是512。 - 值的大小超过阈值：当
HASH中的某个值的大小超过hash-max-ziplist-value配置的值时，ziplist也会被转换为dict。默认值通常是64字节。
以上两个配置都是可以调整的。
__END__
