专栏首页charlierororedis 6源码解析之 ziplist

redis 6源码解析之 ziplist

ziplist

ziplist结构

ziplist的布局如下,所有的字符默认使用小端序保存:

+--------+--------+--------+--------+-------+-------+-------+
|zlbytes | zltail |  zllen | entry  |  ...  | entry | zlend |
+--------+--------+--------+--------+-------+-------+-------+
  • uint32_t zlbytes:为一个无符号整数。保存了ziplist占用的字节数,包含zlbytes字段本身占用的4个字节。主要用于调整数据结构的大小。
  • uint32_t zltail:最后一个entry的字节偏移量(非zlend)。用于从list的另一端执行pop操作(即倒序遍历)
  • uint16_t zllen:entry的数目。当保存的entry大于216-2个entry时,则将该值设置为216-1,此时需要遍历整个entry list来计算list中的entry数目
  • uint8_t zlend:表示ziplist中的最后一个entry。字节编码等同于255(即FF)。表示ziplist的结束符

ziplist中的每个entry都使用一个元数据作为前缀,该元数据包含两部分的信息:首先保存了前一个entry的长度,用于倒序查找;再者保存了entry的编码类型,表示entry的类型,如整数或字符串,当编码类型为字符串时,该字段也表示了字符串的长度。字符串的entry-data的长度就等同于该字符串的长度,而整数的entry-data的长度需要根据编码类型进行判断,并不一定等同于其entry-data字符串的长度(见下文encoding)。一个完整的entry为:

+--------+--------+----------+
|prevlen |encoding|entry-data| 
+--------+--------+----------+

有时编码类型即表示entry本身(例如小的整数),这种情况下会忽略entry-data字段,此时entry变为:

+--------+--------+
|prevlen |encoding|
+--------+--------+

prevlen

prevlen表示前一个entry的长度,使用如下方式进行编码:当前一个entry的长度小于254(255是个特殊字符,被zlend使用)字节时,该字段会使用一个字节(即8 bit)表示长度;当长度大于或等于254时,将会使用5个字节,此时第一个字节会被设置为254(FE)来表示一个较大的数值,后续4个字节表示前面一个entry的长度。

因此,prevlen的编码为:

  • 如果前一个entry的长度小于254,编码为: +-------+--------+-----+ |prevlen|encoding|entry| +-------+--------+-----+
  • 如果前一个entry的长度大于254,编码如下: +----+---------------+--------+-----+ |0xFE|4 bytes prevlen|encoding|entry| +----+---------------+--------+-----+

encoding

entryencoding字段取决于entry的内容。当entry为字符串时,encoding的第一个字节的前2bit保存了编码类型,剩余的bit位表示字符串的长度。当entry为整数时,encoding仅占用1个字节,encoding的前2bit都设置为1,后续的2bit用于指定整数的类型,如int16_t,int32_t。encoding中的第一个字节总是用于判定entry的类型。举例如下:

 * |00pppppp| - 1 byte
 *       字符串的长度小于或等于63字节(6 bits).
 *      "pppppp" 表示6bit长度的无符号整数.
 * |01pppppp|qqqqqqqq| - 2 bytes
 *       字符串的长度小于或等于16383字节(14 bits).
 *       IMPORTANT: 14 bit的数字使用大端序保存.
 * |10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 5 bytes
 *      字符串的长度大于或等于16384字节,只使用第1个字节之后的4个字节表示长度,最大为32^2-1,第一个
 *      字节的低6位没有使用,设置为0。因此entry的最大长度为32
 *      IMPORTANT: 32 bit的数字使用大端序保存.
 * |11000000| - 3 bytes
 *      整数编码为int16_t (2 bytes).
 * |11010000| - 5 bytes
 *      整数编码为int32_t (4 bytes).
 * |11100000| - 9 bytes
 *      I整数编码为int64_t (8 bytes).
 * |11110000| - 4 bytes
 *      编码为24 bit的有符号整数 (3 bytes).
 * |11111110| - 2 bytes
 *      编码为8 bit的有符号整数 (1 byte).
 * |1111xxxx| - (xxxx  取值为 0000 到 1101) 表示4bit的整数
 *      无符号整数的取值为0到12,由于无法使用0000(被|11110000|编码占用)和1111(被zlend占用),因此取值
 *      为1到13,因此需要从低4位的整数减去1获得entry的值.
 * |11111111| - 表示ziplist的终止entry,即zlend

举例

整数编码

如下ziplist包含2个元素,表示字符串"2"和"5",长度为15字节,可以看到由于数值小于13,其编码和数值放在了一个字节中。

 [0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]
       |             |          |       |       |     |
    zlbytes        zltail    entries   "2"     "5"   end

前4个字节(zlbytes)表示15,即整个ziplist包含的字节数;第2个4字节(zltail)最后一个entry的字节偏移,即字符串为"5"的entry的位置,偏移量为12字节;接下来的16bit(entries)表示ziplist中的entry的数目,为2;"00 f3"表示list中的第一个entry "2",它包含了前一个entry的长度(prevlen),为0,"f3"对应的编码为"|1111xxxx|","xxxx"的取值为0001到1101,去除前4个bit "1111",并减去1,得到entry的值为2。下一个entry的prevlen为2,表示前一个entry占用了2字节."f6"的编码与前一个相同,去除前4个bit,并减去1,得到entry的值为5;最后的"ff"表示ziplist的结束(zlend)。

字符串编码

在上述ziplist中追加一个"Hello World"的entry的编码。第一个字节表示前面entry的长度,第二个字节表示encoding,二进制为"|00pppppp|",因此"0b"表示一个11字节的字符串。从第3个字节(48)到最后一个字节(64)表示ASCII编码的字符串"Hello World"。

[02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]

源码解析参见:ziplist.c

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • kubernetes实现用户自定义扩缩容

    本文章主要参考walkthrough,aggregation和auth。涉及custom metric API的注册认证以及API server aggrega...

    charlieroro
  • docker storage driver

    使用docker目录创建一个volume,并将该volume挂载到容器的/my_Cvol目录下

    charlieroro
  • openshift 4.3 Istio的搭建(istio 系列一)

    注:不建议使用openshift 1.11(即kubernetes 3.11)安装istio,可能会出现如下兼容性问题,参见此issue

    charlieroro
  • Hanlp分词实例:Java实现TFIDF算法

    关于TFIDF算法的介绍可以参考这篇博客http://www.ruanyifeng.com/blog/2013/03/tf-idf.html。

    IT小白龙
  • 线上IO问题跟踪-剖析MySQL IO路径

    提示:公众号展示代码会自动折行,建议横屏阅读 一、问题描述 某业务CDB实例,每天在特地时间段内( 00:07:00 - 00:08:00左右)机器对应IO监...

    腾讯数据库技术
  • 转载|线上IO问题跟踪-剖析MySQL IO路径

    某业务CDB实例,每天在特地时间段内( 00:07:00 - 00:08:00左右)机器对应IO监控出现写入尖刺,且主从实例都有类似现象,从机器监控可以看到,问...

    用户1278550
  • win10 uwp 右击选择 GridViewItem

    于是我们需要在 GridView 的 SelectionMode 为 Single ,IsRightTapEnabled 为True

    林德熙
  • 对比亚马逊、谷歌和微软,我们发现AI正在模糊他们入局的先发优势

    镁客网
  • 以云计算为名之微软生死战略大逃亡(中)

    以云计算为名之微软生死战略大逃亡(中) ? 题外话:如果你喜欢我的文章,请帮忙多转载,最近粉丝增长匮乏裹足不前两个多月,急需更多的可见度。先表示感谢。 上回我...

    用户1564362
  • win10 uwp 右击选择 GridViewItem

    于是我们需要在 GridView 的 SelectionMode 为 Single ,IsRightTapEnabled 为True

    林德熙

扫码关注云+社区

领取腾讯云代金券