2021-07-04 10:25  阅读(294)
文章分类:死磕 Redis 文章标签:死磕 Java死磕 Redis
© 版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

这篇文章我们来分析 Redis 数据结构的第三个:ziplist。

什么是 ziplist

什么是 ziplist?Redis 官方是这样定义的:

The ziplist is a specially encoded dually linked list that is designed to be very memory efficient. It stores both strings and integer values, where integers are encoded as actual integers instead of a series of characters. It allows push and pop operations on either side of the list in O(1) time.

翻译如下:

ziplist 是一个经过特殊编码的双向链表,它的设计目标就是为了提高存储效率。ziplist 可以用于存储字符串或整数,其中整数是按真正的二进制表示进行编码的,而不是编码成字符串序列。它能以 O(1) 的时间复杂度在表的两端提供 pus h和 pop 操作。

从上我们可以提炼如下几点信息:

  • ziplist 是一个双向链表。事实上 ziplist 由一系列特殊编码的连续内存块组成的顺序型数据结构。
  • 目的是为了提供存储效率。ziplist 是 Redis 为了节约内存而开发的。
  • 用于存储字符串或者整数。当一个列表键或者哈希键值对包含少量的元素项,且每项要么是小整数型,要么就是长度比较短的字符串时,Redis 就会使用 ziplist 来做他们的底层实现。

ziplist 的结构

ziplist 的结构如下图:

结构 类型 长度 说明
zlbytes uint32_t 4 字节 ziplist 总字节数
zltail uint32_t 4 字节 ziplist 中最后一个 entry 元素起始距离的偏移量。通过这个偏移量,程序无须遍历整个列表就可以确定尾节点的地址
zllen uint16_t 2 字节 记录 ziplist 包含的节点数量,也就是 ziplist 里面有多少个 entry。当有该值小于 UINT16_MAX(65535) 时,这个属性值就是压缩列表中包含的 entry 节点数;当这个值等于 UINT16_MAX 时,entry 节点的真实数量需要遍历整个 ziplist 才能计算出来
entry 不定 ziplist 的节点,节点长度由节点保存的内容决定
zlend uint8_t 1 字节 表示 ziplist 结尾的一个特殊值,编码为单字节等于 255

压缩表中的每个 entry 都大体上包含以下 3 个部分:

  • prevlen:上一个 entry 的长度。它主要是为了能够逆序遍历,有了上一个。
  • encoding:记录了节点的 entry-data 属性所保存的数据类型和长度
  • entry-data:负责保存节点的值。0-12 小的整数时没有没有该项

prevlen

prevlen 记录着上一个 entry 节点的长度,即名为 previous_entry_length 。它的属性长度可以是 1 个字节或者 5 个字节:

  • 如果前一个节点的长度小于 254 字节,那么它的长度为 1 字节
  • 如果前一个节点的长度大于等于 254 字节,那么它的长度为 5 字节,其中第一个字节设置为 254 (fe)作为标记,代表后边有一个大的值,其余 4 个字节表示上一个 entry 节点的长度。

正是因为 prevlen 记录着上一个 entry 节点的长度,所以我们可以通过指针运算来获取前一个节点的起始位置,然后依次类推就可以实现 ziplist 从表尾向表头遍历操作:在 ziplist 结构中 zltail 记录着最后一个 entry 节点起始地址,根据该地址减去该节点的 prevlen 值就可以得到倒数第二节点的起始地址,然后根据倒数第二节点的起始值减去该节点的 prevlen 值,就可以得到倒数第三个 entry 节点的起始位置,以此类推,就可以得到第一个 entry 节点的起始位置,实现 ziplist 表尾向表头遍历。

由于 prevlen 长度可以是 1 字节或者 5 字节,这样就会产生一个问题:连锁更新。如果已有的 ziplist 中有多个连续的 entry 节点(e1 ~ en)的长度都是介于 250 ~ 253 字节,现在在表头添加一个元素,该元素的长度大于 254,因为 e1 的 prevlen 长度仅为 1 字节,它是没有办法保存新节点的长度,所以程序需要对 ziplist 执行空间重分配操作,将 e1 的 prevlen 属性从原来的 1 字节扩展到 5 字节。当 e1 的 prevlen 属性长度扩展到 5 字节,那么其长度变为了 254 ~ 257,这时 e2 的 prevlen 属性就没法保存了,也需要执行空间重分配,将 prevlen 属性扩展到 5 字节,这时 e3 就没法保存了也需要执行,就这样 e1 引发 e2 扩展,e2 引发 e3 扩展 ... 依次到 en,就这样程序需要不断地对 ziplist 执行空间重分配,这个连续执行多次空间扩展的操作就称之为 ”连锁更新“。

可能有小伙伴认为这种连续分配存储空间的过程很消耗性能,其实不然,首先 ziplist 这种数据结构本身存储的数据就不是很多,而且还需要存在很多连续的元素其长度都介于 250 ~ 253 之间,这种概率本身就很小。

encoding

encoding 记录了节点的 entry-data 属性所保存数据的类型及长度:

  • 1 字节(00)、2 字节(01)或者 5 字节长(10), 值的最高位为 00 、 01 或者 10 的是字节数组编码: 这种编码表示节点的 entry-data 属性保存着字节数组, 数组的长度由编码除去最高两位之后的其他位记录

  • 1 字节长, 值的最高位以 11 开头的是整数编码: 这种编码表示节点的 entry-data 属性保存着整数值, 整数值的类型和长度由编码除去最高两位之后的其他位记录

  • 字节数组编码

字节数组编码 编码长度 entry-data 属性保存的值
00bbbbbb 1 字节 长度小于等于63 字节的字节数组
01bbbbbb xxxxxxxx 2 字节 长度小于等于16 383 字节的字节数组
10______ aaaaaaaa bbbbbbbb cccccccc dddddddd 5 字节 长度小于等于 4 294 967 295 的字节数组
  • 整数编码
字节数组编码 编码长度 entry-data 属性保存的值
11000000 1 字节 int16_t 类型的整数
11010000 1 字节 int32_t 类型的整数
11100000 1 字节 int64_t 类型的整数
11110000 1 字节 24 位有符号整数
11111110 1 字节 8 位有符号整数
1111xxxx 1 字节 使用这一编码的节点没有相应的 entry-data 属性,因为编码本身的xxxx 四个位已经保存了一个介于0 和12 之间的值,所以它无须 entry-data 属性

entry-data

entry-data 负责保存节点的值, 节点值可以是一个字节数组或者整数, 值的类型和长度由节点的 encoding 属性决定。

下面我们将演示如何将 "sike",”redis“,10086、9这四个元素插入到 ziplist 中。

  • 插入第一个节点 ”sike“

”sike“ 4 字节数组,那么 encoding 就是 00000100,prevlen 为空,zllen = 1,zltail = 0x000a (4 字节的 zlbytes、4 字节 的 zltail、2 字节的 zllen),zlbytes = 0x0011。如下:

  • 插入第二个节点 ”redis“

"redis" 5 字节数组,所以 encoding 为 00000101,prevlen 为 ”sike“ 节点的起始地址,所以为 10 即(0x0a),zllen = 2 即 0x02,ztail 为当前节点的起始位置 16 即 0x10,zlbytes 为 ”sike“ 的长度 + ”redis“ 的长度为 24 ,即 0x18,所以如下:

  • 插入第三个节点 10086

10086 为 int16_t 类型的证书,所以 encoding = 11000000,得到下图:

  • 插入第四个节点 9

因为 9 < 13 ,所以没有 entry-data 这个属性,按照上面的规律计算得到下图:

参考

点赞(0)
版权归原创作者所有,任何形式转载请联系作者; Java 技术驿站 >> 【死磕 Redis】----- Redis 数据结构:ziplist
上一篇
【死磕 Redis】----- Redis 数据结构:sds
下一篇
【死磕 Redis】----- Redis 数据结构: skiplist