专栏首页用户7890857的专栏6、Redis数据结构——压缩列表-ziplist
原创

6、Redis数据结构——压缩列表-ziplist

压缩列表

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

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

压缩列表构成

struct ziplist<T>{     
// 整个压缩列表占用字节数    
 int32 zlbytes;     
 // 最后一个节点到压缩列表起始位置的偏移量,可以用来快速的定位到压缩列表中的最后一个元素     
 int32 zltail_offset;    
  // 压缩列表包含的元素个数     
  int16 zllength;    
   // 元素内容列表,用数组存储,内存上紧挨着     
   T[] entries;     
   // 压缩列表的结束标志位,值永远为 0xFF.     
   int8 zlend; 
   } 

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

下图展示了压缩列表的各个组成部分:

各个部分作用:

压缩列表节点的构成

 struct entry{    
 // 前一个 entry 的长度    
  int<var> prevlous_entry_length;     
  // 编码方式    
   int<vat> encoding;     
   // 内容    
    optional bute[] content;
     } 

每个压缩列表节点可以保存一个字节数组或者一个整数值,其中,字节数组可以是一下三种长度的其中一种:

  1. 长度小于等于63(2^6-1)字节的字节数组
  2. 长度小于等于16383(2^14-1)字节的字节数组
  3. 长度小于等于4294967295(2^32-1)字节的字节数组

而整数值则可以是以下六种长度的其中一种

  1. 4位长,介于0至12之间的无符号整数
  2. 1字节长的有符号整数
  3. 3字节长的有符号整数
  4. int16_t类型整数
  5. int32_t类型整数
  6. int64_t类型整数

每个压缩列表节点都由previous_entry_length、encoding、content三个部分组成,如下图:

我们分别介绍这三部分

previous_entry_length

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

  1. 如果前一节点的长度小于254字节,那么previous_entry_length属性的长度为1字节:前一节点的长度就保存在这一字节里面
  2. 如果前一节点的长度大于等于254字节,那么previous_entry_length属性的长度为5字节:其中属性的第一个字节会被设置为0xFE(十进制值254),而之后的四个字接则用于保存前一节点的长度。

因为节点的previous_entry_length属性记录了前一个节点的长度,所以程序可以通过指针运算,根据当前节点的起始地址来计算出前一个节点的起始地址。

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

encoding

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

  1. 一字节、两字节或者五字节长,值的最高位为00、01或者10的是字节数组编码:这种编码表示节点的content属性保存着字节数组,数组的长度由编码除去最高两位之后的其他位记录。
  2. 一字节长,值的最高位以11开头的是整数编码:这种编码表示节点的content属性保存着整数值,整数值的类型和长度由编码出去最高两位之后的其他位记录。

content

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

连锁更新

前面说过,每个节点的previous_entry_length属性都记录了前一个节点的长度:如果前一节点的长度小于254字节,那么previous_entry_length属性的长度为1字节,前一节点的长度就保存在这一字节里面。

现在,考虑这样一种情况:在一个压缩列表中,有多个连续的,长度介于250字节到253字节之间的节点e1至eN。

以为e1至eN的所有节点的长度都小于254字节,所以记录这些节点的长度只需要1字节长的previous_entry_length属性。

这时,如果我们将一个长度大于等于254字节的新节点new 设置为压缩列表的表头节点,如下图

因为e1的previous_entry_length属性仅长1字节,它没办法保存新节点new的长度,所以程序将对压缩列表执行空间重分配操作,并将e1节点的previous_entry_length属性从原来的1字节长扩展为5字节长。

现在,麻烦的事情来了,e1原本的长度介于250字节至253字节之间,在为previous_entry_length属性新增4个字节的空间之后,e1的长度就变成了介于254字节至257字节之间,而这种长度使用1字节长的previous_entry_length属性是没办法保存的。

因为,为了让e2的previous_entry_length属性可以记录下e1的长度,程序需要再次对压缩列表执行空间重分配操作,并将e2节点的previous_entry_length属性从原来的1字节长扩展为5字节长。

如此循环,程序需要不断地对压缩列表执行空间重分配操作,直到eN为止。

redis将这种特殊情况下产生的连续多次空间扩展操作称之为“连锁更新”(cascade update)。除了添加新节点可能会引发连锁更新外,删除节点也可能会引发连锁更新。

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

要注意的是,尽管连锁更新的复杂度较高,但它真正造成性能问题的几率是很低的

  1. 压缩列表要恰好有多个连续的、长度介于250-253字节之间的节点,连锁更新才有可能被引发。
  2. 即使出现连锁更新,只要被更新的节点数量不多,就不会对性能造成影响。

因此,ziplistpush等命令的平均复杂度仅为O(n),实际使用中,我们可以放心地使用这些函数,而不必担心连锁更新会影响压缩列表性能。

重点回顾

  • ziplist 是 Redis 单独开发,用连续内存空间来存储list的一个数据结构。它的优势是没有链表的前后指针的内存占用,但是在数据量大的时候,性能有压力。因此只用于数据量小的场景。
  • 压缩列表是一种为节约内存开发的顺序型数据结构。
  • 压缩列表被用作列表键和哈希键的底层实现之一。
  • 压缩列表可以包含多个节点,每个节点可以包含一个字节数组或整数值。
  • 添加新节点到压缩列表或者从中删除节点,都可能会引发连锁更新操作,引起性能差异,但这种操作出现几率不高,不用担心。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

关注作者,阅读全部精彩内容

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Redis数据结构-压缩列表

    Redis 为了节约内存空间使用,zset 和 hash 容器对象在元素个数较少的时候,采用压缩列表 (ziplist) 进行存储。

    程序员酷森
  • 面试官:你看过Redis数据结构底层实现吗?

    面试中,redis也是很受面试官亲睐的一部分。我向在这里讲的是redis的底层数据结构,而不是你理解的五大数据结构。你有没有想过redis底层是怎样的数据结构呢...

    用户5224393
  • Redis 内存压缩实战

    Redis的ziplist是用一段连续的内存来存储列表数据的一个数据结构,它的结构示例如下图

    芋道源码
  • 不是吧?为了加快速度,Redis竟做了这么“疯狂”的设计

    列表对象是 Redis 中 5 种基础数据类型之一,在 Redis 3.2 版本之前,列表对象底层存储结构有两种:linkedlist(双端列表)和 zipli...

    Java程序猿阿谷
  • Redis进阶-List底层数据结构精讲

    Redis 有 5 种基础数据结构,分别为:string (字符串)、list (列表)、set (集合)、hash (哈希) 和 zset (有序集合) 。

    小小工匠
  • 你确定不来了解一下Redis中List的原理吗

    在上一章中我们介绍了 Hash的一些内部原理(《你确定不来了解一下Redis中Hash的原理吗》),在这一章中我们再来讨论在五种数据结构中 List 的基本使用...

    大数据真好玩
  • Redis进阶不得不了解的内存优化细节

    Redis所有的数据都在内存中,而内存又是非常宝贵的资源。对于如何优化内存使用一直是Redis用户非常关注的问题。本文让我们深入到Redis细节中,学习内存优化...

    Bug开发工程师
  • Redis源码剖析之压缩列表(ziplist)

    本来打算只用一篇文章来讲解Redis中的list,在实际写作过程中发现Redis中有多种list的实现,所以准备拆成多篇文章,本文主要讲ziplist,zipl...

    xindoo
  • [Redis] redis的设计与实现-对象系统

    1.redis并没有直接使用前面的数据结构实现键值对数据库,而是基于数据结构创建了一个对象系统,字符串对象/列表对象/哈希对象/集合对象/有序集合对象都用到了至...

    陶士涵
  • 降低Redis内存占用

      Redis为列表、集合、散列、有序集合提供了一组配置选项,这些选项可以让redis以更节约的方式存储较短的结构。

    那一叶随风
  • Redis技术知识总结之一——Redis 的数据结构

    Redis 常用的数据类型主要有:String, List, Hash, Set, ZSet 五种,它们分别对应的底层数据结构有:

    剑影啸清寒
  • 《闲扯Redis五》List数据类型底层之quicklist

    Redis 中的 list 是我们经常使用到的一种数据类型,根据使用方式的不同,可以应用到很多场景中。

    大道七哥
  • Redis 中List 及 quicklist实现 1

    quicklist是在Redis 3.2 之后出现的一种Redis底层数据结构用于List结构的具体实现,List在Redis中更像是数据结构中常说的双向链表,...

    邹志全
  • 《闲扯Redis六》Redis五种数据类型之Hash型

    Redis 中的 hash 是我们经常使用到的一种数据类型,根据使用方式的不同,可以应用到很多场景中。

    大道七哥
  • Redis 基本数据结构二:列表

    列表(list)类型是用来存储多个有序的字符串,如下图所示,a、b、c、d、e五个元素从左到右组成了一个有序的列表,列表中的每个字符串称为元素(element)...

    CoderJed
  • Redis系列(八)底层数据结构之紧凑列表

    Redis 已经是大家耳熟能详的东西了,日常工作也都在使用,面试中也是高频的会涉及到,那么我们对它究竟了解有多深刻呢?

    呼延十
  • Redis 内存压缩原理

    Redis 无疑是一个大量消耗内存的数据库,因此 Redis 引入了一些设计巧妙的数据结构进行内存压缩来减轻负担。ziplist、quicklist 以及 in...

    用户1289394
  • 万字长文,38 图爆肝 Redis 基础!

    Redis 在互联网技术存储方面的使用可以说是非常广泛了,只要是接触过 Java 开发的朋友就算你没用过,都会听过它。在面试也是非常高频的一个知识点。

    一个优秀的废人
  • Redis系列(三)底层数据结构之压缩列表

    Redis 已经是大家耳熟能详的东西了,日常工作也都在使用,面试中也是高频的会涉及到,那么我们对它究竟了解有多深刻呢?

    呼延十

扫码关注云+社区

领取腾讯云代金券