【Redis】—— 压缩列表

压缩列表

压缩列表(ziplist)是列表键哈希键的底层实现之一。当一个列表键只包含少量列表项,并且每个列表项要么就是小整数值,要么就是长度比较短的字符串,那么 Redis 就会使用压缩列表来做列表键的底层实现。

压缩列表的构成

压缩列表是 Redis 为了节省内存而开发的,是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个节点(entry),每个节点可以保存一个字节数组或者一个整数值

  • zlbytes :4字节,记录整个压缩列表占用的内存字节数。在对压缩列表进行内存重分配或者计算 zlend 的位置时使用
  • zltail :4字节,记录压缩列表表尾节点距离压缩列表的起始地址有多少个字节。通过这个偏移量,无须便利整个压缩列表就可以确定表尾节点的地址
  • zllen :记录了压缩列表包含的节点数量。当这个属性的值小于 65535 时,这个属性的值就是压缩列表包含节点的数量,当这个值等于 65535 时,节点的真实数量需要便利才能计算得出
  • entryX :压缩列表包含的各个节点,节点的长度由节点保存的内存决定
  • zlend :特殊值 0xFF(十进制 255),用于标记压缩列表的末端

压缩列表节点的构成

每个压缩列表可以保存一个字节数组或者一个整数值

每个压缩列表节点都由 previous_entry_lengthencodingcontent 三个部分组成。

previous_entry_length

previous_entry_length 属性以字节为单位,记录了压缩列表中前一个节点的长度。previous_entry_length 属性的长度可以是 1 字节或者 5 字节。

如果前一节点的长度小于 254 字节,那么 previous_entry_length 属性的长度为 1 字节;否则长度为 5 字节,其中属性的第一个字节设置为 0xFE ,而之后的四个字节则用于保存前一节点的长度。

压缩列表从表尾向表头遍历操作就是使用这一原理实现的,只要拥有了一个指向某个节点起始地址的指针,那么通过这个指针以及这个节点的 previous_entry_length 属性,就可以一直向前一个节点回溯,最终到达压缩列表的表头节点。

encoding

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

content

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

连锁更新

由于每个节点的 previous_entry_length 属性都记录了前一个节点的长度,假如存在一个压缩列表中,又多个连续的、长度介于 250 字节到 253 字节之间的节点,这时将一个长度大于等于 254 字节的新节点设置为压缩列表的表头节点,之前的第一个节点中的 previous_entry_length 属性长度仅为 1,没办法保存新节点的长度,所以会对压缩列表执行空间重分配操作,将当前节点的 previous_entry_length 属性从原来的 1 字节长拓展为 5 字节长。

同理,当前节点发生重分配操作后,可能会影响到后面的下一个节点,最坏情况下,可能会一直影响到最后一个节点。

Redis 将这种在特殊情况下产生的连续多次空间拓展操作称之为”连锁更新“。

除了添加新节点可能会引发连锁更新之外,删除节点也可能会引发连锁更新。

因为连锁更新在最坏情况下需要对压缩列表执行 N 次空间重分配操作,而每次空间重分配的最坏复杂度为 O(N),所以连续更新的最坏复杂度为 O(N2)。

尽管连锁更新的复杂度较高,但真正造成性能问题的几率是很低的。首先,压缩列表里恰好有多个连续的、长度介于 250 字节至 253 字节之间的节点,连锁更新才可能被触发,在实际中,这种情况并不多见。其次,即使出现连锁更新,但只要被更新的节点数量不多,就不会对性能造成任何影响。

你可能感兴趣的