0%

redis底层之快表QUICKLIST

quicklist是一个ziplist过的linkedlist,它由多个节点Node组成,每个节点都是一个ziplist。

一、定义

  1. 先看源码定义

quicklist.c - A doubly linked list of ziplists.即quicklist是一个ziplist过的linkedlist,它由多个节点Node组成,每个节点都是一个ziplist。

  1. 具体结构(quicklist.h)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
typedef struct quicklist {
quicklistNode *head; #头节点指针
quicklistNode *tail; #尾节点指针
unsigned long count; #所有ziplist数据项entry的个数总和
unsigned long len; #quicklistNode节点总数
int fill : QL_FILL_BITS; #每个节点的最大容量,存放list-max-ziplist-size参数的值
unsigned int compress : QL_COMP_BITS; #quicklist的压缩深度,存放list-compress-depth参数的值
unsigned int bookmark_count: QL_BM_BITS; #bookmarks数组的大小
quicklistBookmark bookmarks[]; #一个可选字段,用来quicklist重新分配内存空间时使用,不使用时不占用空间
} quicklist;

typedef struct quicklistNode {
struct quicklistNode *prev; #前置节点指针
struct quicklistNode *next; #后置节点指针
unsigned char *zl; #不设置压缩数据参数recompress时指向一个ziplist结构
#设置压缩数据参数recompress时指向quicklistLZF结构
unsigned int sz; #ziplist的字节数(ziplist被压缩了,这个sz的值仍然是压缩前的ziplist大小)
unsigned int count : 16; #ziplist中的节点entry数
unsigned int encoding : 2; #编码,只有两个值:1表示未压缩,2表示使用LZF算法进行了压缩
unsigned int container : 2; #quicklistNode节点是否采用ziplist结构保存数据,默认2表示使用ziplist作为数据容器。
unsigned int recompress : 1; #quicklist节点的ziplist之前是否被解压缩过,等于1时需要再次被压缩
unsigned int attempted_compress : 1; #测试时使用
unsigned int extra : 10; #额外扩展位,占10bits长度
} quicklistNode;

typedef struct ziplist{
uint32_t zlbytes; #ziplist分配的内存大小
uint32_t zltail; #达到尾部的偏移量
uint16_t zllen; #存储元素实体个数
unsigned char* entry[]; #存储内容实体元素
unsigned char zlend; #尾部标识,定值十进制255
}ziplist;

typedef struct quicklistLZF {
unsigned int sz; #表示压缩后的ziplist大小
char compressed[]; #存放压缩后的ziplist字节数组
} quicklistLZF;

quicklist

二、相关配置

  1. list-compress-depth val

    • 0: 特殊值,表示都不压缩,默认值。
    • 1~N: 表示quicklist两端各有1~N个节点不压缩,中间的节点压缩,如上图list-compress-depth的值为1
  2. list-max-ziplist-size val

    • 当val大于0时,表示一个quicklistNode结构中zl所指向的ziplist所包含的数据项的最大值,如当这个参数配置成5的时候表示每个quicklistNode的ziplist最多包含5个数据项。
      • val值是由quicklist结构的fill字段来存储的,fill字段是16bit,所以它所能表达的值能够用16bit来表示,即最多可存储2^16个数据项。
    • 当val小于0时,其能够表示的ziplist最大长度是64Kb,具体如下:
      • -5: 每个quicklist节点上的ziplist大小不能超过64Kb。
      • -4: 每个quicklist节点上的ziplist大小不能超过32Kb。
      • -3: 每个quicklist节点上的ziplist大小不能超过16Kb。
      • -2: 每个quicklist节点上的ziplist大小不能超过8Kb,默认值。
      • -1: 每个quicklist节点上的ziplist大小不能超过4Kb。

ziplist中每一个数据项,最少需要2个字节来表示:1个字节的prevlen和1个字节的data(encoding和entry-data合并),所以ziplist中数据项的个数不会超过32K,用16bit来表达足够了。

TODO

超过了会怎样?
16bit怎么就足够了?

三、参考

  1. 参考一
  2. 参考一
  3. 参考一