一聚教程网:一个值得你收藏的教程网站

最新下载

热门教程

Redis ziplist压缩列表代码解析

时间:2022-07-01 编辑:袖梨 来源:一聚教程网

本篇文章小编给大家分享一下Redis ziplist压缩列表代码解析,文章代码介绍的很详细,小编觉得挺不错的,现在分享给大家供大家参考,有需要的小伙伴们可以来看看。

源码解读

一如既往,关于 ziplist 的定义和实现还是放在一对文件中,分别是 ziplist.h 和 ziplist.c。在 ziplist.c 文件的头部有着这么一段注释介绍什么是 ziplist。

ziplist 是一个经过特殊编码的双向链表,旨在提高内存效率。 它存储字符串和整数值,其中整数被编码为实际整数而不是一系列字符。 它允许在 O(1) 时间内在列表的任一侧进行推送和弹出操作。 但是,由于每个操作都需要重新分配 ziplist 使用的内存,因此实际复杂性与 ziplist 使用的内存量有关。

从这段话得到:对于不同的数据类型有着不同的编码方式,理解为会对数据进行压缩,从而达到减少内存使用的目的。但是随着存储的 value 数据级增加,使用 ziplist 所付出的代价也随之增加。

ziplist 布局

ziplist 是一个特殊双向链表,不像普通的链表使用前后指针关联在一起,它是存储在连续内存上的。整体的结构布局如下图:

zlbytes: 32 位无符号整型,记录 ziplist 整个结构体的占用空间大小。当然了也包括 zlbytes 本身。这个结构有个很大的用处,就是当需要修改 ziplist 时候不需要遍历即可知道其本身的大小。 这个 SDS 中记录字符串的长度有相似之处,这些好的设计往往在平时的开发中可以采纳一下。

zltail: 32 位无符号整型, 记录整个 ziplist 中最后一个 entry 的偏移量。所以在尾部进行 POP 操作时候不需要先遍历一次。

zllen: 16 位无符号整型, 记录 entry 的数量, 所以只能表示 2^16。但是 Redis 作了特殊的处理:当实体数超过 2^16 ,该值被固定为 2^16 - 1。 所以这种时候要知道所有实体的数量就必须要遍历整个结构了。

entry: 真正存数据的结构。

zlend: 8 位无符号整型, 固定为 255 。为 ziplist 的结束标识。

entry 节点

每个 entry 都包含两条信息的元数据为前缀。 第一元数据用来存储前一个 entry 的长度,以便能够从后向前遍历列表。 第二元数据是表示 entry 的编码形式。 用来表示 entry 类型,整数或字符串,在字符串的情况下,它还表示字符串有效的长度。

所以一个完整的 ziplist 是这样存储的:

prelen

记录前一个 entry 的长度。若前一个 entry 的长度小于 254 , 则使用 1 个字节的 8 位无符号整数来表示。

若前一个 entry 长度大于等于 254,则使用 5 个字节来表示。第 1 个字节固定为 254 (FE) 作为标识,剩余 4 字节则用来表示前一个 entry 的实际大小。

所以两种情况下的 entry 结构如下所示:

1. 前一个 entry 大小不超过 253。
  
2. 前一个 entry 大小超过 253。
0xFE <4 bytes unsigned little endian prevlen>  

encoding 编码

entry 的编码字段取决于具体值的内容,分为字符串、数字两种类型单独处理。

一、当 entry 是字符串时,有 3 种编码方式。编码第 1 个字节的前 2 位将保存用于存储字符串长度的编码类型,后面是字符串的实际长度。

1. 长度小于或等于 63 字节(6 位)的字符串值。 “pppppp”表示无符号的 6 位数据长度。
|00pppppp| - 1 byte
2. 长度小于或等于 16383 字节(14 位)的字符串值。14 位的数据采用  big endian 存储。
big endian 是一种字节序方式,有Little-Endian、Big-Endian两种。
|01pppppp|qqqqqqqq| - 2 bytes
3. 长度大于或等于 16384 字节的字符串值。
采用 big endian 存储且可表示的字符串长度最大2^32-1,所以第一个字节没有用到,所以低6位没有用,所以都是0。
|10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 5 bytes 

二、当 entry 是整数时,有 6 种编码方式。前 2 位都固定为 1,接下来的 2 位用于指定将在此标头后存储哪种类型的整数。

与 ziplist 标头一样,所有整数都以 Little-Endian 序表示,即使此代码是在 Big-Endian 系统中编译的。

1. 整数编码为 int16_t(2 字节)。
|11000000| - 3 bytes
2. 整数编码为int32_t(4个字节)。
|11010000| - 5 bytes
3. 整数编码为 int64_t(8 字节)。
|11100000| - 9 bytes
4. 整数编码为24位带符号(3个字节)。
|11110000| - 4 bytes
5. 整数编码为 8 位有符号(1 字节)。
|11111110| - 2 bytes
6. 0到12的无符号整数。编码后的值实际上是1到13,因为0000和1111不能用,所以要从编码后的4位值中减去1才能得到正确的值。
|1111xxxx| - (with xxxx between 0001 and 1101) immediate 4 bit integer

三、结尾编码标识

1. 表示 ziplist 结尾的标识。
|11111111|

热门栏目