牺牲速度来节省内存,Redis 是觉得自己太快了吗?,mysql 破解版百度网盘
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
,而存储字节数组时,则可能是 00
、01
和 10
三种中的一种。
当存储整数时,第
1
个字节的前2
位固定为11
,其他位则用来记录整数值的类型或者整数值(下表所示的编码中前两位均为11
):
注意:xxxx
四位编码范围是 0000-1111
,但是 0000
,1111
和 1110
已经被表格中前面表示的数据类型占用了,所以实际上的范围是 0001-1101
,此时能保存数据 1-13
,再减去 1
之后范围就是 0-12
。至于为什么要减去 1
是从使用习惯来说 0
是一个非常常用的数据,所以才会选择统一减去 1
来存储一个 0-12
的区间而不是直接存储 1-13
的区间。
当存储字节数组时,第
1
个字节的前2
位为00
、01
或者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
个节点,节点中存储的是整数 2
和 5
:
[0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]| | | | | |zlbytes zltail zllen "2" "5" end
第一组
4
个字节为zlbytes
部分,0f
转成二进制就是1111
也就是15
,代表整个ziplist
长度是15
个字节。第二组
4
个字节zltail
部分,0c
转成二进制就是1100
也就是12
,这里记录的是压缩列表尾节点距离起始地址有多少个字节,也就是就是说[02 f6]
这个尾节点距离起始位置有12
个
字节。3. 第三组 2
个字节就是记录了当前 ziplist
中 entry
的数量,02
转成二进制就是 10
,也就是说当前 ziplist
有 2
个节点。4. 第四组 2
个字节 [00 f3]
就是第一个 entry
,00
表示 0
,因为这是第 1
个节点,所以前一个节点长度为 0
,f3
转成二进制就是 11110011
,刚好对应了表格中的编码 1111xxxx
,所以后面四位就是存储了一个 0-12
位的整数。0011
转成十进制就是 3
,减去 1
得到 2
,所以第一个 entry
存储的数据就是 2
。5. 第五组 2
个字节 [02 f6]
就是第二个 entry
,02
即为 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
个字节02
转成十进制就是2
,表示前一个节点(即上面示例中的[02 f6]
)长度是2
。第 二组的
2
个字节0b
转成二进制为00001011
,以00
开头,符合编码00pppppp
,而除掉最开始的两位00
,计算之后得到十进制11
,这就说明后面字节数组的长度是11
。第三组刚好是
11
个字节,对应了上面的长度,所以这里就是真正存储了Hello World
的字节数组。
ziplist 连锁更新问题
上面提到 entry
中的 prevlen
属性可能是 1
个字节也可能是 5
个字节,那么我们来设想这么一种场景:假设一个 ziplist
中,连续多个 entry
的长度都是一个接近但是又不到 254
的值(介于 250~253
之间),那么这时候 ziplist
中每个节点都只用了 1
个字节来存储上一个节点的长度,假如这时候添加了一个新节点,如 entry1
,其长度大于 254
个字节,此时 entry1
的下一个节点 entry2
的 prelen
属性就必须要由 1
个字节变为 5
个字节,也就是需要执行空间重分配,而此时 entry2
因为增加了 4
个字节,导致长度又大于 254
个字节了,那么它的下一个节点 entry3
的 prelen
属性也会被改变为 5
个字节。依此类推,这种产生连续多次空间重分配的现象就称之为连锁更新。同样的,不仅仅是新增节点,执行删除节点操作同样可能会发生连锁更新现象。
虽然 ziplist
可能会出现这种连锁更新的场景,但是一般如果只是发生在少数几个节点之间,那么并不会严重影响性能,而且这种场景发生的概率也比较低,所以实际使用时不用过于担心。
总结
本文主要讲解了 Redis
当中的 ziplist
(压缩列表),一种用时间换取空间的数据结构,在介绍压缩列表存储结构的同时通过一个存储示例来分析了 ziplist
是如何存储数据的,最后介绍了 ziplist
中可能发生的连锁更新问题。
评论