写点什么

牺牲速度来节省内存,Redis 是觉得自己太快了吗?,mysql 破解版百度网盘

用户头像
极客good
关注
发布于: 刚刚

0xFE <4 bytes unsigned little endian prevlen> <encoding> <entry>


注意:1 个字节完全你能存储 255 的大小,之所以只取到 254 是因为 zlend 就是固定的 255,所以 255 这个数要用来判断是否是 ziplist 的结尾

encoding

encoding 属性存储了当前 entry 所保存数据的类型以及长度。encoding 长度为 1 字节,2 字节或者 5 字节长。前面我们提到,每一个 entry 中可以保存字节数组和整数,而 encoding 属性的第 1 个字节就是用来确定当前 entry 存储的是整数还是字节数组。当存储整数时,第 1 个字节的前两位总是 11,而存储字节数组时,则可能是 000110 三种中的一种。


  • 当存储整数时,第 1 个字节的前 2 位固定为 11,其他位则用来记录整数值的类型或者整数值(下表所示的编码中前两位均为 11):



注意:xxxx 四位编码范围是 0000-1111,但是 000011111110 已经被表格中前面表示的数据类型占用了,所以实际上的范围是 0001-1101,此时能保存数据 1-13,再减去 1 之后范围就是 0-12。至于为什么要减去 1 是从使用习惯来说 0 是一个非常常用的数据,所以才会选择统一减去 1 来存储一个 0-12 的区间而不是直接存储 1-13 的区间。


  • 当存储字节数组时,第 1 个字节的前 2 位为 0001 或者 10,其他位则用来记录字节数组的长度:


entry-data

entry-data 存储的是具体数据。当存储小整数(0-12)时,因为 encoding 就是数据本身,此时 entry-data 部分会被省略,省略了 entry-data 部分之后的 ziplist 中的 entry 结构如下:


<prevlen> <encoding>


压缩列表中 entry 的数据结构定义如下(源码 ziplist.c 文件内),当然实际存储并没有直接使用到这个结构定义,这个结构只是用来接收数据,所以大家了解一下就可以了:


typedef struct zlentry {unsigned int prevrawlensize;//存储 prevrawlen 所占用的字节数 unsigned int prevrawlen;//存储上一个链表节点需要的字节数 unsigned int lensize;//存储 len 所占用的字节数 unsigned int len;//存储链表当前节点的字节数 unsigned int headersize;//当前链表节点的头部大小(prevrawlensize + lensize)即非数据域的大小 unsigned char encoding;//编码方式 unsigned char *p;//指向当前节点的起始位置(因为列表内的数据也是一个字符串对象)} zlentry;

ziplist 数据示例

上面讲解了大半天,可能大家都觉得枯燥无味了,也可能会觉得云里雾里,这个没有关系,这些只要心里有个概念,用到的时候再查询对应资料就可以了,并不需要全部记住,接下来让我们一起通过两个例子来体会一下 ziplist 到底是如何来组织存储数据的。


下面就是一个压缩列表的存储示例,这个压缩列表里面存储了 2 个节点,节点中存储的是整数 25


[0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]| | | | | |zlbytes zltail zllen "2" "5" end


  1. 第一组 4 个字节为 zlbytes 部分,0f 转成二进制就是 1111 也就是 15,代表整个 ziplist 长度是 15 个字节。

  2. 第二组 4 个字节 zltail 部分,0c 转成二进制就是 1100 也就是 12,这里记录的是压缩列表尾节点距离起始地址有多少个字节,也就是就是说 [02 f6] 这个尾节点距离起始位置有 12


【一线大厂Java面试题解析+核心总结学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开:qq.cn.hn/FTf 免费领取
复制代码


字节。3. 第三组 2 个字节就是记录了当前 ziplistentry 的数量,02 转成二进制就是 10,也就是说当前 ziplist2 个节点。4. 第四组 2 个字节 [00 f3] 就是第一个 entry00 表示 0,因为这是第 1 个节点,所以前一个节点长度为 0f3 转成二进制就是 11110011,刚好对应了表格中的编码 1111xxxx,所以后面四位就是存储了一个 0-12位的整数。0011 转成十进制就是 3,减去 1 得到 2,所以第一个 entry 存储的数据就是 2。5. 第五组 2 个字节 [02 f6] 就是第二个 entry02 即为 2,表示前一个节点的长度为 2,注意,因为这里算出来的结果是小于 254,所以就代表了这里只用到了 1 个字节来存储上一个节点的长度(如果等于 254,这说明接下来 4 个字节才存储的是长度),所以后面的 f6 就是当前节点的数据,转换成二进制为 11110110,对应了表格中的编码 1111xxxx,同样的后四位 0110 存储的是真实数据,计算之后得出是 5。6. 最后一组 1 个字节[ff]转成二进制就是 11111111,代表这是整个 ziplist 的结尾。


假如这时候又添加了一个 Hello World 字符串到列表中,那么就会新增一个 entry,如下所示:


[02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]


  1. 第一组的 1 个字节 02 转成十进制就是 2 ,表示前一个节点(即上面示例中的 [02 f6])长度是 2

  2. 第 二组的2 个字节 0b 转成二进制为 00001011,以 00 开头,符合编码 00pppppp,而除掉最开始的两位 00,计算之后得到十进制 11,这就说明后面字节数组的长度是 11

  3. 第三组刚好是 11 个字节,对应了上面的长度,所以这里就是真正存储了 Hello World 的字节数组。

ziplist 连锁更新问题

上面提到 entry 中的 prevlen 属性可能是 1 个字节也可能是 5 个字节,那么我们来设想这么一种场景:假设一个 ziplist 中,连续多个 entry 的长度都是一个接近但是又不到 254 的值(介于 250~253 之间),那么这时候 ziplist 中每个节点都只用了 1 个字节来存储上一个节点的长度,假如这时候添加了一个新节点,如 entry1 ,其长度大于 254 个字节,此时 entry1 的下一个节点 entry2prelen 属性就必须要由 1 个字节变为 5 个字节,也就是需要执行空间重分配,而此时 entry2 因为增加了 4 个字节,导致长度又大于 254 个字节了,那么它的下一个节点 entry3prelen 属性也会被改变为 5 个字节。依此类推,这种产生连续多次空间重分配的现象就称之为连锁更新。同样的,不仅仅是新增节点,执行删除节点操作同样可能会发生连锁更新现象。


虽然 ziplist 可能会出现这种连锁更新的场景,但是一般如果只是发生在少数几个节点之间,那么并不会严重影响性能,而且这种场景发生的概率也比较低,所以实际使用时不用过于担心。

总结

本文主要讲解了 Redis 当中的 ziplist(压缩列表),一种用时间换取空间的数据结构,在介绍压缩列表存储结构的同时通过一个存储示例来分析了 ziplist 是如何存储数据的,最后介绍了 ziplist 中可能发生的连锁更新问题。

用户头像

极客good

关注

还未添加个人签名 2021.03.18 加入

还未添加个人简介

评论

发布
暂无评论
牺牲速度来节省内存,Redis是觉得自己太快了吗?,mysql破解版百度网盘