redis5.0.7源码阅读——压缩列表ziplist
redis中压缩列表ziplist相关的文件为:ziplist.h与ziplist.c
压缩列表是redis专门开发出来为了节约内存的内存编码数据结构。源码中关于压缩列表介绍的注释也写得比较详细。
一、数据结构
压缩列表的整体结构如下(借用redis源码注释):
1/*2<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
3*/
各个部分的含义:
项
类型
长度
用途
zlbytes
uint32_t
4B
ziplist总字节数,包括zlbytes
zltail
uint32_t
4B
最后一个entry的偏移量
zllen
uint16_t
2B
entry数量
zlend
uint8_t
1B
ziplist固定结尾,值固定为0xFF
entry
不定
不定
ziplist的各节点,具体结构不定
关于entry,借用redis源码注释的结构改造一下:
1/*2<prevlen> <encoding> [<entry-data>]
3*/
prevlen表示的是前一个entry的长度,用于反向遍历,即从最后一个元素遍历到第一个元素。因每个entry的长度是不确定的,所以要记录一下前一个entry的长度。prevlen本身的长度也是不定的,与前一entry的实际长度有关。若长度小于254,只需要1B就可以了。若实际长度大于等于254,则需要5B,第1B固定为254,后面4B存储实际长度。
encoding则与entry存储的data有关。
encoding前两位
encoding内容
encoding长度
entry-data类型
entry-data长度
00
|00pppppp|
1B
string
6b能表示的数字,0~63,encoding中存储的长度为大端字节序
01
|01pppppp|qqqqqqqq|
2B
string
14b能表示的数字,64~16383,encoding中存储的长度为大端字节序
10
|10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt|
5B
string
int32能表示的数字,16384~2^32-1,encoding中存储的长度为大端字节序
11
|11000000|
1B
int16
2B
11
|11010000|
1B
int32
4B
11
|11100000|
1B
int64
8B
11
|11110000|
1B
int24
3B
11
|11111110|
1B
int8
1B
11
|1111xxxx|
1B
无
xxxx在[0001,1101]之间,表示0~12的数字,存储时进行+1操作
11
|11111111|
1B
无
End of ziplist special entry(源码注释)
如一个具体的ziplist,有两个成员“2”与“5”:
/*[0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]
| | | | | |
zlbytes zltail zllen "2" "5" end
*/
zlbytes值为15,表示这个ziplist总长为15B
zltail的值为12,表示最后一个entry的偏移量为12
zllen的值为2,表示一共有两个entry
第一个entry的prevlen为0。因为第一个成员之前没有其它成员了,所以是0,占1B。值为“2”,可以用数字表示,且是介于[0,12]之间,故使用1111xxxx的encoding方式,无entry-data。2的二进制编码为0010,+1后为0011,实际为11110011,即0xF3。同理,5的encoding为0xF6。做为第二个entry,其前一个entry的总长为2,故其prevlen值为2。
zlend固定是0xFF。
二、基本操作
redis中使用了大量的宏定义与函数配合操作ziplist。
1、创建
1#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))2#define ZIPLIST_END_SIZE (sizeof(uint8_t))
3#define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl)))
4#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
5#define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
6#define ZIP_END 255
7
8
9 unsigned char *ziplistNew(void) {
10 unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;
11 unsigned char *zl = zmalloc(bytes);
12 ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
13 ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
14 ZIPLIST_LENGTH(zl) = 0;
15 zl[bytes-1] = ZIP_END;
16return zl;
17 }
新创建的ziplist,没有entry,只有zlbytes、zltail、zllen与zlend:
1/*2[0b 00 00 00] [0a 00 00 00] [00 00] [ff]
3 | | | |
4 zlbytes zltail zllen end
5*/
2、插入
假设有以下ziplist:
1/*2[0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]
3 | | | | | |
4 zlbytes zltail zllen "2" "5" end
5*/
要在"2"与"5"之间插入节点“3”,则:
a.获取所要插入位置当前节点“5”的prevlen=2,prevlen_size=1
若要插入的位置是end处,则取出zltail进行偏移,取到“5”节点,直接进行计算。而如果当前是个空ziplist,直接就是0了。
b.获取节点“3”的实际长度,若其为纯数字,则可以使用数字存储,节约内存。否则直接使用外部传入的,string的长度。
这里有一点:
1int zipTryEncoding(unsigned char *entry, unsigned int entrylen, longlong *v, unsigned char *encoding) { 2longlong value; 34if (entrylen >= 32 || entrylen == 0) return0;
5if (string2ll((char*)entry,entrylen,&value)) {
6/* Great, the string can be encoded. Check what"s the smallest
7 * of our encoding types that can hold this value. */
8if (value >= 0 && value <= 12) {
9 *encoding = ZIP_INT_IMM_MIN+value;
10 } elseif (value >= INT8_MIN && value <= INT8_MAX) {
11 *encoding = ZIP_INT_8B;
12 } elseif (value >= INT16_MIN && value <= INT16_MAX) {
13 *encoding = ZIP_INT_16B;
14 } elseif (value >= INT24_MIN && value <= INT24_MAX) {
15 *encoding = ZIP_INT_24B;
16 } elseif (value >= INT32_MIN && value <= INT32_MAX) {
17 *encoding = ZIP_INT_32B;
18 } else {
19 *encoding = ZIP_INT_64B;
20 }
21 *v = value;
22return1;
23 }
24return0;
25 }
在尝试使用数字编码的时候,如果len >= 32,则直接不尝试,并不清楚这个32是怎么来的。
本例中,“3”可以直接使用数字编码,且在[0,12]之间,故没有entry-data
c.获得本entry的总长度,即prevlen、encoding、entry-data长度和。本处为1+1=2
d.判断一下插入后,后一个entry的prevlen是否足够存储新entry的长度。新长度为2,原entry的prevlen只有1B,足够。
此处需要注意,如果原本是5B的prevlen,当前1B就足够存储,则不做任何处理,强制使用5B来存储1B能存储的数字。而如果原来是1B,当前要5B,则还需要4B空间。
e.重新分配ziplist空间。新增加的字节数,为c、d两步之和。此处只需要额外2B的空间。
分配空间后:
1/*2[11 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff] [00 ff]
3 | | | | | |
4 zlbytes zltail zllen "2" "5" end
5*/
重新分配空间会自动设置zlend与zlbytes
f.将“5”及之后的节点(不包括zlend)往后移:
1/*2[11 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [02 f6] [ff]
3 | | | | | |
4 zlbytes zltail zllen "2" "5" "5"
5*/
g.修正当前“5”所在位置的prevlen=2:
1/*2[11 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [02 f6] [ff]
3 | | | | | |
4 zlbytes zltail zllen "2" "5" "5"
5*/
h.修改zltail:
1/*2[11 00 00 00] [0e 00 00 00] [02 00] [00 f3] [02 f6] [02 f6] [ff]
3 | | | | | |
4 zlbytes zltail zllen "2" "5" "5"
5*/
i.填写新entry:
1/*2[11 00 00 00] [0e 00 00 00] [02 00] [00 f3] [02 f4] [02 f6] [ff]
3 | | | | | |
4 zlbytes zltail zllen "2" "3" "5"
5*/
j.更新zllen:
1/*2[11 00 00 00] [0e 00 00 00] [03 00] [00 f3] [02 f4] [02 f6] [ff]
3 | | | | | |
4 zlbytes zltail zllen "2" "3" "5"
5*/
若在此基础上,在“3”前,插入的是一个长度为256的string X,则:
a.获取“3”的prevlen与prevlen_size
prevlen=2,prevlen_size=1
b.长度大于32,使用string进行存储,实际长度data_len=256
c.获取entry总长度
此处prevlen长度为1B,encoding长度为2B ,entry-data长度为256B,共1+2+256=259
d.判断一下插入后,后一个entry的prevlen是否足够存储新entry的长度。新长度为259,超过了254,需要5B,而原本只有1B,还差了4B。即,nextdiff=4
e.分配空间。新增加字节数为259+4=263,共280B,即0x118
分配空间后:
1/*2[0x118] [0xe] [03 00] [00 f3] [02 f4] [02 f6] [...] [ff]
3 | | | | | | |
4zlbytes zltail zllen "2" "3" "5" 263B
5 4B 4B
6*/
f.memmove操作
ziplist中的memmove操作:
1 memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);
操作完之后:
1/*2[...] [00 f3] [02 f4] [02 f6] [...] [03 00] [00 f3] [02 f4] [02 f6] [ff]
3 | | | | | | | |
4header "2" "3" "5" 255B "2" "3" "5"
5 10B
6*/
其中header为zlbytes、zltail与tllen
其实与以下写法相同效果:
1 memmove(p+reqlen+nextdiff,p,curlen-offset-1+nextdiff);
这种写法操作完之后:
1/*2[0x118] [0xe] [03 00] [00 f3] [02 f4] [02 f6] [...] [02 f4] [02 f6] [ff]
3 | | | | | | | | |
4zlbytes zltail zllen "2" "3" "5" 259B "3" "5"
5 4B 4B
6*/
目的是一样的,把原来的节点移至正确的位置上。
g.修正当前“3”所在位置的prevlen=259,即0X103:
1/*2[0x118] [0xe] [03 00] [00 f3] [...] [FE 03 01 00 00 f4] [02 f6] [ff]
3 | | | | | | |
4zlbytes zltail zllen "2" 259B "3" "5"
5 4B 4B
6*/
h.此时节点"3"的长度发生变化,需要更新其后一个节点"5"的prevlen:
1/*2[0x118] [0xe] [03 00] [00 f3] [...] [FE 03 01 00 00 f4] [06 f6] [ff]
3 | | | | | | |
4zlbytes zltail zllen "2" 259B "3" "5"
5 4B 4B
6*/
i.修改zltail:
1/*2[0x118] [0x115] [03 00] [00 f3] [...] [FE 00 00 01 03 f4] [06 f6] [ff]
3 | | | | | | |
4zlbytes zltail zllen "2" 259B "3" "5"
5 4B 4B
6*/
j.填写新entry:
encoding值为:01000001 00000000 即0x4100,大端字节序
填写后:
1/*2[0x118] [0x115] [03 00] [00 f3] [02 41 00 ...] [FE 00 00 01 03 f4] [06 f6] [ff]
3 | | | | | | |
4zlbytes zltail zllen "2" X "3" "5"
5 4B 4B 259B
6*/
k.更新zllen:
1/*2[0x118] [0x115] [04 00] [00 f3] [02 41 00 ...] [FE 00 00 01 03 f4] [06 f6] [ff]
3 | | | | | | |
4zlbytes zltail zllen "2" X "3" "5"
5 4B 4B 259B
6*/
若有连续几个entry的长度在[250,253]B之间,在插入新节点后可能存在连锁更新的情况。
如以下ziplist(只保留部分entry,其余节点省略):
1/*2... [FD 40 FA ...] [FD 40 FA ...] ...
3 | |
4 E1 253B E2 253B
5*/
E1的prevlen为FD,即长度为253。此时在E1之前插入一个长度为256的节点,E1需要增加prevlen的长度,从而导致E1整体长度增加。
E2的prevlen为FD,即E1的长度为253。增加4个节点之后为257,E2也需要增加prevlen的长度。
之后还可能会有E3,E4等entry需要处理,产生了连锁反应,直到到了以下情况才会停止:
i.到了zlend
ii.不需要继续扩展
iii.需要减少prevlen字节数时
连锁更新时需要多次重新分配空间,最坏情况下有n个节点的ziplist,需要分配n次空间,而每次分配的最坏情况时间复杂度为O(n),故连锁更新的最坏情况时间复杂度为O(n^2)。
3、查找
ziplist的查找过程其实是一次遍历,依次解析出prevlen、encoding与entry-data,然后根据encoding类型,决定是要用strcmp,还是直接使用数字的比较。在首次进行数字比较的时候,会把传入要查找的串,尝试一次转换成数字的操作。如果无法转换,就会跳过数字比较操作。
查找操作支持每隔几个entry才做一次比较操作。如,查找每5个entry中,值为“1”的entry。
4、删除
如有以下ziplist:
1/*2[0x118] [0x115] [04 00] [00 f3] [02 41 00 ...] [FE 00 00 01 03 f4] [06 f6] [ff]
3 | | | | | | |
4zlbytes zltail zllen "2" X "3" "5"
5 4B 4B 259B
6*/
删除的是节点“5”,因是最后一个节点,则只要先修改zltail:
1/*2[0x118] [0x10F] [04 00] [00 f3] [02 41 00 ...] [FE 00 00 01 03 f4] [06 f6] [ff]
3 | | | | | | |
4zlbytes zltail zllen "2" X "3" "5"
5 4B 4B 259B
6*/
然后resize:
1/*2[0x116] [0x10F] [04 00] [00 f3] [02 41 00 ...] [FE 00 00 01 03 f4] [ff]
3 | | | | | |
4zlbytes zltail zllen "2" X "3"
5 4B 4B 259B
6*/
最后修改zllen即可:
1/*2[0x116] [0x10F] [03 00] [00 f3] [02 41 00 ...] [FE 00 00 01 03 f4] [ff]
3 | | | | | |
4zlbytes zltail zllen "2" X "3"
5 4B 4B 259B
6*/
如果是这个ziplist:
1/*2[0x118] [0x115] [04 00] [00 41 00 ...] [FE 00 00 01 03 f4] [06 f3] [02 f6] [ff]
3 | | | | | | |
4zlbytes zltail zllen X "3" "2" "5"
5 4B 4B 259B
6*/
如果删除是的节点"3",则先要计算删除后,"3"节点后的"2"节点的prevlen长度是否足够,然后直接写入。此时长度不够,并不会直接重新分配空间,而是直接使用之前"3"节的最后4B空间:
1/*2[0x118] [0x115] [04 00] [00 41 00 ...] [FE 00] [FE 00 00 01 03 f3] [02 f6] [ff]
3 | | | | | | |
4zlbytes zltail zllen X 2B "2" "5"
5 4B 4B 259B
6*/
然后修改zltail:
1/*2[0x118] [0x113] [04 00] [00 41 00 ...] [FE 00] [FE 00 00 01 03 f3] [02 f6] [ff]
3 | | | | | | |
4zlbytes zltail zllen X 2B "2" "5"
5 4B 4B 259B
6*/
接着进行memmove操作:
1/*2[0x118] [0x113] [04 00] [00 41 00 ...] [FE 00 00 01 03 f3] [02 f6] [02 f6] [ff]
3 | | | | | | |
4zlbytes zltail zllen X "2" "5" "5"
5 4B 4B 259B
6*/
resize操作:
1/*2[0x116] [0x113] [04 00] [00 41 00 ...] [FE 00 00 01 03 f3] [02 f6] [ff]
3 | | | | | |
4zlbytes zltail zllen X "2" "5"
5 4B 4B 259B
6*/
最后要更新节点"2"及其之后entry的prevlen:
1/*2[0x116] [0x113] [04 00] [00 41 00 ...] [FE 00 00 01 03 f3] [06 f6] [ff]
3 | | | | | |
4zlbytes zltail zllen X "2" "5"
5 4B 4B 259B
6*/
注意此时更新也是有可能产生连锁反应。
删除操作支持删除从指定位置开始,连续n个entry,操作类似。
以上是 redis5.0.7源码阅读——压缩列表ziplist 的全部内容, 来源链接: utcz.com/z/532193.html