作者：张仕华
ziplist 简介
Redis 使用 ziplist 是为了节省内存. 以 zset 为例, 当 zset 元素个数少并且每个元素也比较小的时候, 如果直接使用 skiplist(可以理解为多层的双向链表), 每个节点的前后指针这些元数据占用空间的比例可能达到 50% 以上. 而 ziplist 是分配在堆上的一块连续内存, 通过一定的编码格式, 使数据保存更加紧凑. 如下是一个编码为 ziplist 的 zset.
127.0.0.1:6666> zadd zs 100 ‘a’
(integer) 1
127.0.0.1:6666> zadd zs 200 ‘b’
(integer) 1
127.0.0.1:6666> object encoding zs
“ziplist”
ziplist 格式
ziplist 的格式如下图所示:ziplist 各字段解释如下:
zlbytes:ziplist 占用的内存空间大小
zltail:ziplist 最后一个 entry 的偏移量
zllen:ziplist 中 entry 的个数.
entry: 每个元素
0xFF:ziplist 的结束标志
每个 entry 的字段解释如下:
prev_entry_len: 前一个 entry 占用的字节大小, 占用 1 个或者 5 个字节. 当小于 254 时, 占用 1 字节, 当大于等于 254 时, 占用 5 字节
encoding: 当前 entry 内容的编码格式及其长度
content: 当前 entry 保存的内容
注意 ziplist 中有一个 zltail 字段是最后一个 entry 的偏移量, 通过该字段定位到最后一个 entry 后, 读取 prev_entry_len 可以继续向前定位上一个 entry 的起始地址. 也就是说 ziplist 适合于从后往前遍历.
bug 原因及其复现
首先看下代码中是如何修复该 bug 的:
@@ -778,7 +778,12 @@ unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned cha
/* When the insert position is not equal to the tail, we need to
* make sure that the next entry can hold this entry’s length in
* its prevlen field. */
+ int forcelarge = 0;
nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
+ if (nextdiff == -4 && reqlen < 4) {
+ nextdiff = 0;
+ forcelarge = 1;
+ }
/* Store offset because a realloc may change the address of zl. */
offset = p-zl;
@@ -791,7 +796,10 @@ unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned cha
memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);
/* Encode this entry’s raw length in the next entry. */
– zipStorePrevEntryLength(p+reqlen,reqlen);
+ if (forcelarge)
+ zipStorePrevEntryLength(p+reqlen,reqlen);
+ else
+ zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
/* Update offset for tail */
ZIPLIST_TAIL_OFFSET(zl) =
通过把代码反向修改回来, 编译之后执行如下命令可以导致 Redis crash:
0.redis-cli del list
1.redis-cli rpush list one
2.redis-cli rpush list two
3.redis-cli rpush list
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
4.redis-cli rpush list
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
5.redis-cli rpush list three
6.redis-cli rpush list a
7.redis-cli lrem list 1
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
8.redis-cli linsert list after
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA 10
9.redis-cli lrange list 0 -1
我们将以上命令的内存占用情况以图画出来, 表示如下:
每个小矩形框表示占用内存字节数, 大矩形框表示一个个 entry, 每个 entry 有三项, 参见上文 ziplist entry 的格式介绍左列是执行到第 6 条命令之后的内存占用情况接着执行第 7 条命令, 删除了第 3 个 entry, 此时第 4 个 entry 的前一个 entry 长度由 255 字节变为 5 字节, 所以 prev_entry_len 字段由占用 5 个字节变为占用 1 个字节. 参见图中中间列的黄框. 注意此时会发生连锁更新, 因为篮框部分的 prev_entry_len 此时等于 253, 也可以更新为 1 个字节. 但 Redis 中在连锁更新的情况下为了避免频繁的 realloc 操作, 这种情况下不进行缩容. 接着执行第 8 条命令, 插入绿框中的数据, 此时篮筐中的 prev_entry_len 是 5 个字节, 绿框中的数据只占用 2 字节, 当将 prev_entry_len 更新为 1 字节后,prev_entry_len 多余的 4 字节可以完整的容纳绿框中的数据. 即虽然插入了数据, 但 realloc 之后反而缩小了占用的内存, 从而导致 ziplist 中的数据损坏.
修复这个 bug 的代码也就很容易理解了, 即图中右列蓝框的 prev_entry_len 仍然保留为 5 个字节.
Redis 作者对该 bug 的思考
通过上边的分析, 是不是觉着很难理解？Redis 作者也意识到由于连锁更新的存在导致 ziplist 并不是简单易懂. 于是提出了一个优化后的替代结构 listpack.
listpack 主要做了如下两点改进:
头部省去了 4 个字节的 zltail 字段
entry 中不再保存 prev_entry_len 这个字段, 而是改为保存本 entry 自己的长度
整体结构如下:
<tot-bytes> <num-elements> <element-1> … <element-N> <listpack-end-byte>
每个 entry 的结构如下:
<encoding-type><element-data><element-tot-len>
我们知道 ziplist 设计为适合从尾部到头部逐个遍历, 那么 listpack 如何实现该功能呢？首先通过 tot-bytes 偏移到结尾, 然后从右到左读取 element-tot-len(注意该字段设计为从右往左读取), 这样既实现了尾部到头部的遍历, 又没有连锁更新的情况. 是不是很巧妙.
参考文档
https://gist.github.com/antir…
https://raw.githubusercontent…
https://github.com/antirez/re…