当前位置: 代码迷 >> 综合 >> redis6:ziplist
  详细解决方案

redis6:ziplist

热度:100   发布时间:2023-11-30 17:32:25.0

1、介绍

  • ziplist体现了redis对于存储效率的追求,一个普通的双向链表,其中每一项都占用独立的一块内存,各项之间使用地址指针连接起来,这种方式会带来大量的内存碎片,而且地址指针也会占用额外的内存。而ziplist将表中每一项放在连续地址空间内,一个ziplist占用一大块内存,他是一个list而非linked list。
  • ziplist在细节上节省内存,对于值的存储采用了变长的编码方式,对于大的整数就多用一些字节来存储,对于小的整数就少用一些字节来存储。

2、ziplist的构成

??压缩列表是redis为了节约内存而开发的,是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个ziplist可包含任意多个节点(entry),每个节点可以保存一个字节数组或者一个整数值。
在这里插入图片描述

属性 类型 用途
zlbytes uint32_t 记录整个压缩列表所占用的内存字节数:在对压缩列表进行内存重分配或者计算zlend位置时使用
zltail uint32_t 记录压缩列表表尾节点距离起始地址多少字节:无需遍历整个列表就可以确定表尾节点的地址
zllen uint16_t ziplist包含的节点数量:当小于UINT16_MAX表示包含结点的数量,等于UINT16_MAX时节点的真是数量需要遍历才能计算得到
entryX 列表节点 各个节点,节点的长度由节点保存的内容决定
zlend uint8_t 特殊值0xFF,用于标记ziplist的末端

在这里插入图片描述

3、ziplist节点的构成

在这里插入图片描述
previous_entry_length
以字节为单位,记录了ziplist中前一个节点的长度。占用1字节或5字节。

  • 若是前一个节点的长度小于254字节,那么previous_entry_length属性的长度1字节
  • 若是前一个节点的长度大于等于254,那么previous_entry_length属性的长度是5字节:属性的第一字节会被设置为0xFE,之后的四个字节用于保存前一节点的长度。

根据当前节点的起始地址和previous_entry_length可以计算前一个节点的起始地址。
ziplist的从表尾向表头遍历就是使用这个原理实现的。

encoding
记录了content属性所保存数据的类型以及长度。

  • 1字节、2字节、5字节,值的最高位是00、01、10的是字节数组编码:表示节点的content属性保存着字节数组,数组的长度由除去最高两位之后的其他位表示。
  • 1字节长,值得最高位以11开头的是整数编码:节点的content保存着整数值,整数值的类型和长度由除去最高两位之后的其他位记录;

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

4、连锁更新

考虑这样一种情况:一个压缩列表中,多个连续的、长度介于250字节~253字节之间的节点e1到eN,
如果将一个长度大于等于254字节的新节点new设置为压缩列表的表头节点,那么new将成为e1的前置节点。
在这里插入图片描述

  1. 因为e1的previous_entry_length属性仅为1个字节,没办法保存新节点new的长度,所以程序对ziplist执行空间重分配操作,将e1的previous_entry_length属性从原来的1字节扩展为5字节长。
  2. e1原来的长度介于250~253字节之间,在为previous_entry_length属性新增四个字节的空间之后,e1长度变成了介于254-257之间,就这样每个节点都要空间重分配。
  3. 除了添加新节点会引发连锁更新之外,删除节点也可能会引发连锁更新;

连锁更新在最坏情况下需要对列表执行N次空间重分配操作,每次分配的最坏复杂度是O(N),所以连锁更新的最坏时间复杂度是O(N*N)。
尽管连锁更新的复杂度高,但是真正造成性能问题的几率是很低的:

  • ziplist要恰好有多个连续的、长度符合要求的节点,连锁更新才可能被引发,实际中并不多见;
  • 即使出现连锁更新,只要被更新的节点数不多,就不会对性能造成影响。
  • 因此push的平均复杂度仅为O(N),实际中可以放心使用。

5、总结

  • ziplist是一种为节约内存而开发的顺序性数据结构
  • ziplist被用作list和hash的底层实现之一
  • 可以包含多个节点,每个节点可以保存一个字节数组或者整数值;
  • 连锁更新相关。