0%

redis底层之压缩列表ZIPLIST

Ziplist是由一系列特殊编码的内存块构成的列表,一个Ziplist可以包含多个节点(entry),每个节点可以保存一个长度受限的字符数组(不以\0结尾的char数组)或者整数。

一、定义

  1. 先看源码定义

The ziplist is a specially encoded dually linked list that is designed to be very memory efficient. It stores both strings and integer values, where integers are encoded as actual integers instead of a series of characters. It allows push and pop operations on either side of the list in O(1) time.

百度翻译过来:ziplist是一种特殊编码的双链表,它的设计非常节省内存。它存储字符串和整数值,其中整数被编码为实际整数(按真正的二进制表示进行编码)而不是一系列字符(编码成字符串序列)。它允许在O(1)时间内对列表的任一侧执行push和pop操作。

ziplist特殊之处在于没有维护双向指针prev和next,而是存储上一个entry的长度和当前entry的长度,通过长度推算下一个元素在什么地方,下面会说。

ziplist充分体现了redis对于存储效率的追求:一个普通的双向链表,链表中每一项都独立占用一块内存,各项之间用地址指针(或引用)连接起来,这种方式会带来大量的内存碎片,而且地址指针也会占用额外的内存;而ziplist却是将表中每一项存放在前后连续的地址空间内,一个ziplist整体占用一大块内存。

  1. 具体结构

      redis源码并没有具体的ziplist结构体定义,ziplist.c文件头部有一个简单的描述,即ziplist大体由一下几部分构成<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>

1
2
3
4
5
6
7
typedef struct ziplist{
uint32_t zlbytes; #ziplist分配的内存大小
uint32_t zltail; #达到尾部的偏移量
uint16_t zllen; #存储元素实体个数
unsigned char* entry[]; #存储内容实体元素
unsigned char zlend; #尾部标识
}ziplist;
  • zlbytes:32位无符号整型uint32_t,表示整个压缩列表占用的字节数
    • 在对压缩列表进行内存重分配或计算zlend的位置时使用。
  • zltail:32位无符号整型uint32_t,表示压缩列表表尾节点距离压缩列表的起始地址有多少字节
    • 通过这个偏移量无须遍历整个压缩列表就可以确定表尾节点的地址。
  • zllen:16位无符号整型uint16_t,表示压缩列表包含的节点entry数量(最多2^16 - 1个节点),由ziplist.c文件ziplistLen方法中可知:
    • 当这个属性的值小于UINT16_MAX(65535)时,这个属性的值就是压缩列表包含节点的数量;
    • 当这个值等于UINT16_MAX时,节点的真实数量需要遍历整个压缩列表才能计算得出。
  • entry:压缩列表包含的各个节点,节点的长度由节点保存的内容决定。
  • zlend:8位无符号整型uint8_t,值固定为0xFF(十进制255),用于标记压缩列表的末端。

对于每个节点entry,逻辑结构定义如下:

1
2
3
4
5
6
7
8
9
typedef struct zlentry {
unsigned int prevrawlensize; # 前一个节点所占的字节数(prevrawlen长度确定后,不同的编码会有不同的prevrawlensize)
unsigned int prevrawlen; # 前一个节点长度
unsigned int lensize; # 当前节点所占的字节数(同prevrawlensize)
unsigned int len; # 当前节点长度
unsigned int headersize; # 当前节点header的大小,等于`prevrawlensize + lensize`
unsigned char encoding; # 当前节点编码
unsigned char *p; # 指向当前节点的指针(当前节点内容)
} zlentry;

以上结构体只是为了方便描述每个节点信息,实际在内存中存储信息包含以下信息:

1
2
3
4
5
typedef struct entry {
unsigned int prevlen;
unsigned char encoding;
unsigned char *entyr-data;
}zlentry;
  • prevlen:记录了前一个节点的长度(字节为单位)。

    • 如果前一节点的长度小于254字节,那么prevlen的长度为1字节,用于保存前一节点的长度;
    • 如果前一节点的长度大于等于254字节, 那么prevlen属性的长度为5字节,其中:
      • 第一个字节会被设置为0xFE(十进制值254);
      • 后面四个字节则用于保存前一节点的长度。
  • encoding:记录了当前节点的entry-data属性所保存数据的类型(字符串还是数字)及长度,其依赖entry-data具体内容,一般可根据encoding第一个字节的前2位内容进行区分:

    • 前2位都是1的时候表示存储的是数字,其余则是字节数组,共分为以下9种情况:

      序号 encoding编码 encoding长度 entry-data长度 entry-data类型
      1 00xxxxxx 1字节 6位 最大长度63(2^6 - 1)的字节数组
      2 01xxxxxx xxxxxxxx 2字节 14位 最大长度16383(2^14)-1的字节数组
      3 10______ xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx 5字节 32位 最大长度(2^32)-1的字节数组
      4 1100 0000 1字节 2字节 int16整数
      5 1101 0000 1字节 4字节 int32整数
      6 1110 0000 1字节 8字节 int64整数
      7 1111 0000 1字节 3字节 24位整数
      8 1111 1110 1字节 1字节 8位整数
      9 1111 xxxx 1字节 特殊0 没有entry-data字段,xxxx表示0~12之间的整数

针对以上第9中情况,xxxx的值在0001和1101之间(其中0000和1110已被占用,1111被zlend占用),可表示的真实数据为1~13。另外,小数值应该从0开始,因此这13个值分别表示0到12,即xxxx的值减去1才是它所要表示的那个整数数据的值。

  • entry-data:记录了实际存储的数据。

为了方便理解,可以记为<prevlen> <<encoding+lensize><len>> <data>

二、官方例子

假设存储数字2和5,那么压缩表的结构如下(16进制表示,redis采用的是小端模式存取数据):

1
2
3
*  [0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]
* | | | | | |
* zlbytes zltail zllen "2" "5" zlend

解析

  • 对于zlbytes对应的数据0f 00 00 00,由于使用的小端模式,实际数据为00 00 00 0f,转为十进制为15,即整个ziplist占用15字节的内存;
  • 同理,由zltail可得到偏移量为12;
  • 同理,由zllen可知整个压缩列表包含2个节点;
  • 对于内容为2的节点,由于其没有前置节点,prevlen等于0并占用1个字节,encoding部分由于其满足第9种情况,占用1个字节,2的2进制为0010加1则为0011,拼接前缀后为11110011,转为16进制即为f3,没有entry-data部分;
  • 对于内容为5的节点,前置节点2占用2个字节,小于254仍占用1字节,encoding部分同样满足第9种情况最终可得f6,没有entry-data部分;
  • zlend固定值为ff(十进制的255)

    此时新加入一个节点,其内容为”hello world”,则ziplist则应为如下结构:

  • “hello world”字符串长度为11,满足第1种1情况00xxxxxx,转为16进制就是0b,及entry-data部分68656c6c6f20776f726c640a
1
2
3
*  [0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [02 0b 68656c6c6f20776f726c640a] [ff]
* | | | | | | |
* zlbytes zltail zllen "2" "5" "hello world" zlend

三、大小端

      在计算机系统中,数据是以字节为单位存放的,每个地址单元都对应着一个字节,一个字节为8bit。C语言中存在不同的数据类型,每个数据类型占用的字节数各不相同,如int型在32位系统中占4个字节。以C语言开发的各种应用,在存放数据时就存在怎样存放多个字节的问题,因此就出现了大端存储模式和小端存储模式。

大端模式,是指数据的高字节保存在内存的低地址中,而数据的低字节保存在内存的高地址中,这样的存储模式有点儿类似于把数据当作字符串顺序处理:地址由小向大增加,而数据从高位往低位放,这和我们的阅读习惯一致。

小端模式,是指数据的高字节保存在内存的高地址中,而数据的低字节保存在内存的低地址中,这种存储模式将地址的高低和数据位权有效地结合起来,高地址部分权值高,低地址部分权值低。

下面以unsigned int val = 0x12345678为例,分别看看在两种字节序下其存储情况,我们可以用unsigned char buf[4]来存储val

对于大端模式:

1
2
3
4
5
6
         ---------------
高地址 -- buf[3] (0x78) -- 数据低位
buf[2] (0x56)
buf[1] (0x34)
低地址 -- buf[0] (0x12) -- 数据高位
---------------

对于小端模式

1
2
3
4
5
6
         ---------------
高地址 -- buf[3] (0x12) -- 数据高位
buf[2] (0x34)
buf[1] (0x56)
低地址 -- buf[0] (0x78) -- 数据低位
---------------
内存地址 小端模式存放内容 大端模式存放内容
0x4000 0x78 0x12
0x4001 0x56 0x34
0x4002 0x34 0x56
0x4003 0x12 0x78

四、参考

  1. 参考一
  2. 参考二