redis ziplist
ziplist
结构
ziplist是一个压缩的双向链表,由一个特殊编码的连续内存块构成。如果没有特殊指定,所有字段都是以小端序来存储的。
1 | ziplist: |
ziplist: *
uint32_t zlbytes
:ziplist占据的内存大小,包括zlbytes
字段。
*
uint32_t zltail
:最后一个entry(非zlend)的offset,记录了尾节点距离起始地址的字节数,相当于尾指针的作用。
*
uint16_t zllen
:entry的数目,如果元素数目大于2^16-2
,那么值为2^16-1
,只有通过遍历才能得知,有多少个元素。zlen不计入entry数目。
*
uint8_t zlend
:特殊的entry,ziplist的结尾标记,值为0xFF
。
每个entry大小是不固定的: *
prevlen
:前一个entry的长度,用于从后往前遍历时计算prev
entry的起始地址。长度小于254字节和大于等于254字节分别使用两种存储方式。
| value | prevlen | size |
|--------|---------|------|
| < 254 | `0xbb` | 1字节 |
| >=254 | `0xFE xx xx xx xx` | 5字节 |
当长度大于等于254时,`0xFE`代表`prevlen`值的类型,后面的4个字节才是长度。
这样存储方式刚好可以与`zlend`的`0xFF`区分开来,没有一个entry的开头会是`0xFF`。
encoding
:记录了entry-data
数据类型和长度。前两个bit代表存储的是字节数组,还是整型。
encoding size 值的类型 00pppppp
1 byte 长度<=63的字节数组 01pppppp|qqqqqqqq
2 bytes(14 bits使用大端序存储) 长度<=16383的字节数组 10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt
5 bytes(32 bits使用大端序存储) 长度>=16384,且<=2^32 - 1的字节数组 11000000
1 byte int16_t 11010000
1 byte int32_t 11100000
1 byte int64_t 11110000
1 byte 24 bit signed integer 11111110
1 byte 8 bit signed integer 1111xxxx
1 byte 没有 content
属性,4个bit存储[0, 12]的值11111111
1 byte zlend entry-data
:节点的值,字节数组或整形。
插入
ziplist使用了很多宏来实现,主要是进行类型转换和指针运算以便访问相关的字段。
插入分三个情况,
需要分别准备新entry的prevlen
,encoding
,分配空间。
prevlen
先看插入位置是否在zlen
之前,- 如果不在,
p
处的prevlen
就是新entry的prevlen
。 - 如果在,此时无法直接得知
prevlen
,需要看zlend
前是否还有元素。若没有,则zipRawEntryLength(ptail)
计算tail
元素的长度。
p
不是zlend
的时候,新entry的len会作为p
处entry的prevlen
,需要确保p
处prevlen
空间足够。- 如果不在,
encoding
对于encoding
,先会尝试编码为整型zipTryEncoding(s,slen,&value,&encoding)
,- 如果可以编码为整型,那么
zipIntSize(encoding)
得到entry-data的大小。 - 如果无法合法的编码为整型,那么根据
slen
编码为字节数组zipStoreEntryEncoding(NULL,encoding,slen)
,entry-data的大小为slen
。
- 如果可以编码为整型,那么
分配空间, 计算出各字段所需的空间后,
memmove()
来完成空间的调整。要注意对源地址的处理,p-nextdiff
。如果
nextdiff == 0
,说明p
处entry的prevlen
,可以保存新entry的大小。如果
nextdiff == 4
,那么说明空间不够,此时p
处entry的prevlen
原大小为1 byte,从p
往前数4 bytes,加起来的5 bytes作为新prevlen
的存储,因此从p - 4
处开始memmove()
。如果
nextdiff == -4
,说明空间多出4 bytes,从p + 4
的位置开始memmove()
。
1 | unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) { |
连锁更新
插入或删除时,可能导致后面entry存储的prevlen
发生变化。理论上,扩张和缩小都会有,但redis有意忽略了缩小的情况,避免连续的插入导致频繁的扩容和缩小。
1 | if (next.prevrawlensize > rawlensize) { |