Redis源码学习：ziplist的数据结构和连锁更新问题

ziplist

ziplist 是 Redis 中一种紧凑型的列表结构，专门用来存储元素数量少且每个元素较小的数据。它是一个双端链表，可以在任意一端进行压入/弹出操作，并且该操作的时间复杂度为O(1)。

ziplist数据结构

<zlbytes><zltail><zllen><entry1>...<entryX><zlend>

字段	字节数	描述
zlbytes	4 字节	记录整个 ziplist 所占用的字节数
zltail	4 字节	记录 ziplist 最后一个元素的偏移量
zllen	2 字节	记录 ziplist 中包含的元素个数（最大为 65535）
entryX	不定长	每个元素的数据，包括 prevlen、encoding 和 content
zlend	1 字节	特殊值 0xFF，标志 ziplist 的结束

每个元素的结构

<prevlen><encoding><content>

字段	字节数	描述
prevlen	1 或 5 字节	记录前一个元素的长度，为了方便反向遍历ziplist
encoding	1-5 字节	记录当前元素的类型和长度信息
content	不定长	具体的数据内容，长度由 encoding 部分决定

ziplist的不足

1、查找复杂度高

虽然ziplist对头尾的操作可以很快，但是，当要查找列表中间的元素时，ziplist 就得从列表头或列表尾遍历才行。而当 ziplist 保存的元素过多时，查找中间数据的复杂度就会增加。因此，ziplist的最大存储元素数量和每个元素的大小直接影响其性能。

hash-max-ziplist-entries：hash 类型元素数量超过指定数据后时候。使用 hash 存储，否则使用压缩表。
hash-max-ziplist-value： hash 类型元素长度超过指定数据后时候。使用 hash 存储，否则使用压缩链表。
zset-max-ziplist-entries：zset 类型压缩列表 ziplist 最大限制元素数。超过指定值将会使用跳表 skiplist + dict 来存储。
zset-max-ziplist-value：set 类型压缩列表 ziplist 最大限制大小。超过指定将会使用跳表 skiplist+dict 来存储。

在Redis.conf文件中有默认配置：

# 最大元素个数
hash-max-ziplist-entries 512
# 元素最大字节数
hash-max-ziplist-value 64

zset-max-ziplist-entries 128
zset-max-ziplist-value 64

2、连锁更新问题

由于ziplist 必须使用一块连续的内存空间来保存数据，所以当新插入一个元素时，ziplist 就需要计算其所需的空间大小，并申请相应的内存空间，假设有N个小于255字节的Entry，每一个Entry的pre_entry_len都可以用1个字节存储，现在要在中间插入新的Entry，长度大于254，此时pre_entry_len就需要5字节来存，后续的元素的prevlen字段也需要扩展，就会引起连锁更新的问题。这一系列操作，可以从 ziplist 的元素插入函数__ziplistInsert中看到。