Redis系列(三)底层数据结构之压缩列表

栏目: IT技术 · 发布时间: 4年前

内容简介:Redis 已经是大家耳熟能详的东西了,日常工作也都在使用,面试中也是高频的会涉及到,那么我们对它究竟了解有多深刻呢?我读了几本 Redis 相关的书籍,尝试去了解它的具体实现,将一些底层的数据结构及实现原理记录下来。本文将介绍 Redis 中底层的

前言

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

我读了几本 Redis 相关的书籍,尝试去了解它的具体实现,将一些底层的数据结构及实现原理记录下来。

本文将介绍 Redis 中底层的 ziplist(压缩列表) 的实现方法。 它是 Redis 中列表键和哈希键的底层实现之一。当符合某些情况(后续文章讲)时,列表键和哈希键会使用它。

Redis系列(三)底层数据结构之压缩列表

可以看到图中,这个键值为 zsetkey 的 zset 内部使用的编码方法就是 ziplist .

定义

列表数据结构,我们已经有了链表,为什么还需要重新搞一个压缩列表呢? 为了节省内存

链表的前后指针是一个非常耗费内存的结构,因此在数据量小的时候,这一部分的空间尤其显得浪费。

压缩列表是一系列特殊编码的连续内存块组成的顺序性数据结构。

这句话有点绕口,其实核心思想就是,在一块连续的内存中,模拟出一个列表的结构。

压缩列表的定义

压缩列表的定义为:

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

Redis系列(三)底层数据结构之压缩列表

每个字段的含义已经注释在代码中了。这里额外解释一下为什么需要 zltail_offset 这个属性,因为压缩列表只能顺序遍历,所以为了提升效率,我们需要可以从首尾双端来遍历,用这个属性可以很快的找到压缩列表的尾部。至于如何反向遍历,请继续向下看。

压缩列表节点的定义

压缩列表的每一个节点的定义为:

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

定义里,prevlous_entry_length 属性,就是为了反向遍历而记录的。想一下,首先拿到尾部节点的偏移量,找到最尾部的节点,然后调用 prevlous_entry_length 属性,就可以拿到前一个节点,然后不断向前遍历了。

这里需要注意的是:这个字段的长度并不是一定的,它可以是 1 个字节,也可以是 5 个字节。

当前一个 entry 的长度在 254 字节以内的时候,这个属性用一个字节来记录。 否则就会用 5 个字节来记录。

这回导致一个问题,见后文。

  • encoding

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

  • content

这个属性用来真正的保存节点的值,可以是一个字节数组或者整数。它的类型和长度由 encoding 来决定。

新增节点

在前言里提到了,在某些情况下列表键会使用压缩列表,就是在列表键的内容比较少时,那么压缩列表为什么不能用于大的列表键呢?

ziplist 是连续存储的数据结构,内存是没有冗余的(前面的文章讲过的 SDS 中就有冗余空间), 也就是说,每一次新增节点,都需要进行内存申请,然后将如果当前内存连续块够用,那么将新节点添加,如果申请到的是另外一块连续内存空间,那么需要将所有的内容拷贝到新的地址。

也就是说,每一次新增节点,都需要内存分配,可能还需要进行内存拷贝。当 ziplist 中存储的值太多,内存拷贝将是一个很大的消耗。

也是因此,Redis 只在一些数据量小的场景下使用 ziplist.

问题:级联更新

在讲 prevlous_entry_length 的时候,我们提到它的长度变化会导致一个问题,那就是级联更新。

当前一个 entry 的长度在 254 字节以内的时候,这个属性用一个字节来记录。否则就会用 5 个字节来记录。

那么我们设想一个极端的场景,在这个 ziplist 内部,所有的节点的长度都是 253 字节,也就意味着所有节点的 prevlous_entry_length 属性都是一个字节。

此时,我们给压缩列表最前端插入一个大于 254 字节的节点,那么此时原来的第一个节点的 prevlous_entry_length 属性会从 1 个字节变成 5 个字节,这个节点的总长度也就来到了 257 字节,大于 254 字节,那么下一个节点(原来的第二个节点)的 prevlous_entry_length 属性也会变成 5 个字节,这又会导致下一个节点的变化。… 引起连锁变化,所有节点的 prevlous_entry_length 值都需要更新一遍。

级联更新的时间复杂度很差,最多需要进行 N 次空间的重分配,每次空间的重分配最差需要 O(N), 所以级联更新的时间复杂度最差是 O(N2).

与新增节点相似,删除节点也有可能会造成级联更新的情况。

但是其实不用怕,因为级联更新造成 Redis 性能压力的概率极其低。

首先,级联更新需要连续的节点大小为 250-253 之间,这本就少见,而大范围的连续就更加少见了。如果运气不好出现了三五个的级联更新,也绝不会对 Redis 的性能有压力。

总结

ziplist 是 Redis 单独开发,用连续的内存空间来存储 list 的一个数据结构。它的优势是没有链表的前后指针的内存占用,但是在数据量大的时候,性能有压力。因此只用于数据量小的场景。

ziplist 是 list 键和 hash 键的底层实现数据结构之一。

ziplist 有一个问题,就是添加节点或者删除节点,有极小的概率会触发级联更新,引起性能差异。但是这个事真的极小概率,不用担心。

参考文章

《Redis 的设计与实现(第二版)》

《Redis 深度历险:核心原理和应用实践》

完。

联系我

最后,欢迎关注我的个人公众号【 呼延十 】,会不定期更新很多后端工程师的学习笔记。 也欢迎直接公众号私信或者邮箱联系我,一定知无不言,言无不尽。 Redis系列(三)底层数据结构之压缩列表

以上皆为个人所思所得,如有错误欢迎评论区指正。

欢迎转载,烦请署名并保留原文链接。

联系邮箱:huyanshi2580@gmail.com

更多学习笔记见个人博客或关注微信公众号 < 呼延十 >——>呼延十


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

并行计算导论

并行计算导论

Ananth Grama、George Karypis、张武、毛国勇、Anshul Gupta、Vipin Kumar、程海英 / 张武、毛国勇、程海英 / 机械工业出版社 / 2005-1-1 / 49.00元

《并行计算导论》(原书第2版)全面介绍并行计算的各个方面,包括体系结构、编程范例、算法与应用和标准等,涉及并行计算的新技术,也覆盖了较传统的算法,如排序、搜索、图和动态编程等。《并行计算导论》(原书第2版)尽可能采用与底层平台无关的体系结构并且针对抽象模型来设计处落地。书中选择MPI、POSIX线程和OpenMP作为编程模型,并在不同例子中反映了并行计算的不断变化的应用组合。一起来看看 《并行计算导论》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

SHA 加密
SHA 加密

SHA 加密工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具