Redis ziplist内部结构分析
来源：nosqlfan
pesiwang
摘要：本文来自对Redis内部ziplist结构的内部实现进行了详细深入的分析，ziplist是用一个字符串来实现的双向链表结构。
Abstract：
Key words :
ziplist是用一个字符串来实现的双向链表结构，顾名思义，使用ziplist可以减少双向链表的存储空间，主要是节省了链表指针的存储，如果存储指向上一个链表结点和指向下一个链表结点的指针需要8个字节，而转化成存储上一个结点长度和当前结点长度在大多数情况下可以节省很多空间(最好的情况下只需2个字节)。但是每次向链表增加元素都需要重新分配内存。
ziplist中的结构体
typedef struct zlentry {
unsigned int prevrawlensize, prevrawlen;
unsigned int lensize, len;
unsigned int headersize;
unsigned char encoding;
unsigned char *p;
} zlentry;
Prevrawlen：上个链表结点占用的长度
Prevrawlensize：上个链表结点长度的存储占用的字节数
Len：当前链表结点占用的长度
Lensize：当前链表结点长度的存储占用的字节数
Headersize：当前链表结点的头部大小， headersize = prevrawlensize + lensize
Encoding：当前链表结点长度(即字段len)使用的编码类型
P：指向当前结点起始位置的指针
Ziplist的存储结构
链表存储结构
Zlbytes：一个4字节的无符号整型，存储的是整个ziplist占用的字节数，用于重分配内存时使用。
Zltail：一个4字节的无符号整型，存储的是链表最后一个结点的偏移值，即链表开头地址+zltail即为最后一个结点的起始地址
Zllen：一个2字节的无符号整型，存储的是链表中存储的结点数，当这个值存储的是2字节无符号整型的最大值时，需要遍历链表获取链表的结点数
Entry：链表结点，链表结点的存储格式见结点存储结构
Zlend：占用1字节的链表的结尾符，值为255
相关的宏定义
Ziplist.c: 89
/* Utility macros */
#define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl)))
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
#define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
#define ZIPLIST_ENTRY_HEAD(zl) ((zl)+ZIPLIST_HEADER_SIZE)
#define ZIPLIST_ENTRY_TAIL(zl) ((zl)+ZIPLIST_TAIL_OFFSET(zl))
#define ZIPLIST_ENTRY_END(zl) ((zl)+ZIPLIST_BYTES(zl)-1)
结点存储结构
<上一个链表结点占用的长度><当前链表结点占用的长度><当前结点数据>
上一个链表结点占用的长度
上一个链表结点占用的长度占用的字节数根据编码类型而定
当长度数据小于254使用一个字节存储，该字节存储的数值就是该长度，
当长度数据大于等于254时，使用5个字节存储，第一个字节的数值为254，表示接下来的4个字节才真正表示长度
当前链表结点用的长度存储和数据存储
第一个字节的前两位用于区分长度存储编码类型和数据编码类型，具体如下
字符串类型编码
|00pppppp|
长度小于等于63(2^6-1)字节的字符串，后6位用于存储字符串长度，长度与类型总共占用了1个字节
|01pppppp|qqqqqqqq|
长度小于等于16383(2^14-1)字节的字符串，后14位用于存储字符串长度，长度与类型总共占用了2个字节
|10______|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt|
长度大于等于16384字节的字符串，后4个字节用于存储字符串长度，长度与类型总共占用了5个字节
整型编码
|1100____|
整型类型，后2个字节存储的值就是该整数
|1101____|
整型类型，后4个字节存储的值就是该整数
|1110____|
整型类型，后8个字节存储的值就是该整数
相关的宏定义
Ziplist.c：77
/* Different encoding/length possibilities */
#define ZIP_STR_06B (0 << 6)
#define ZIP_STR_14B (1 << 6)
#define ZIP_STR_32B (2 << 6)
#define ZIP_INT_16B (0xc0 | 0<<4)
#define ZIP_INT_32B (0xc0 | 1<<4)
#define ZIP_INT_64B (0xc0 | 2<<4)
/* Macro's to determine type */
#define ZIP_IS_STR(enc) (((enc) & 0xc0) < 0xc0)
#define ZIP_IS_INT(enc) (!ZIP_IS_STR(enc) && ((enc) & 0x30) < 0x30)
ziplist提供的接口
unsigned char *ziplistNew(void);
创建一个ziplist
返回创建的ziplist的指针
unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where);
在ziplist的尾端或头部添加一个结点
zl是ziplist的指针
s是待添加结点的值
slen是待添加结点的值长度
返回最新的ziplist的指针
unsigned char *ziplistIndex(unsigned char *zl, int index);
根据索引获取ziplist的结点，封装类似数组接口
zl是ziplist的指针
index是索引，从0开始，0即取链表的第一个结点，index可以是负数，负数表从后往前算，-1就是取链表的最后一个元素
如果index处有结点，则返回指向改结点的指针，否则返回NULL
unsigned char *ziplistNext(unsigned char *zl, unsigned char *p);
获取ziplist的下一个结点
zl是无用参数
p是当前结点指针
如果还有下一个结点，则返回下一个结点的指针，否则返回NULL
unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p);
获取ziplist的上一个结点
zl是ziplist的指针
p是当前结点指针
如果还有上一个结点，则返回上一个结点的指针，否则返回NULL
unsigned int ziplistGet(unsigned char *p, unsigned char **sval, unsigned int *slen, long long *lval);
获取p指向的当前结点的值
p是指向当前结点的指针
sval保存获取到的当前结点的值的指针
slen是获取到的当前结点的值的长度
lval是当值是整型时保存返回的数值
如果p指向的结点是合法结点返回1，否则返回0
unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen);
在指针p指向的位置插入一个结点
zl是ziplist的指针
p是待插入结点的位置
s是待插入结点的值
slen是待插入结点的值的长度
返回最新的ziplist的指针
unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p);
删掉*p指向的结点
zl是ziplist的指针
p是一个value-result参数，传入需删除的结点，返回被删除结点下一个结点的指针
返回最新的ziplist的指针
unsigned char *ziplistDeleteRange(unsigned char *zl, unsigned int index, unsigned int num);
删除连续的一批结点
zl是ziplist的指针
index是开始删除的索引
num是删除的个数
返回最新的ziplist的指针
unsigned int ziplistCompare(unsigned char *p, unsigned char *s, unsigned int slen);
p指向的结点的值和s对应的值做比较
p是ziplist结点的指针
s是呆比较的值
slen是s的长度
相等返回1，否则返回0
unsigned int ziplistLen(unsigned char *zl);
取ziplist链表中元素的个数
zl是ziplist的指针
返回ziplist链表中元素的个数
size_t ziplistBlobLen(unsigned char *zl);
取ziplist链表占用的字节数
zl是ziplist的指针
返回ziplist链表占用的字节数
此内容为AET网站原创，未经授权禁止转载。