Redis ziplist内部结构分析

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 + lensizeEncoding：当前链表结点长度(即字段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处有结点，则返回指向改结点的指针，否则返回NULLunsigned char *ziplistNext(unsigned char *zl, unsigned char *p);获取ziplist的下一个结点zl是无用参数p是当前结点指针如果还有下一个结点，则返回下一个结点的指针，否则返回NULLunsigned char *ziplistPrev(unsigned char *zl, unsigned char *p);获取ziplist的上一个结点zl是ziplist的指针p是当前结点指针如果还有上一个结点，则返回上一个结点的指针，否则返回NULLunsigned int ziplistGet(unsigned char *p, unsigned char **sval, unsigned int *slen, long long *lval);获取p指向的当前结点的值p是指向当前结点的指针sval保存获取到的当前结点的值的指针slen是获取到的当前结点的值的长度lval是当值是整型时保存返回的数值如果p指向的结点是合法结点返回1，否则返回0unsigned 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，否则返回0unsigned int ziplistLen(unsigned char *zl);取ziplist链表中元素的个数zl是ziplist的指针返回ziplist链表中元素的个数size_t ziplistBlobLen(unsigned char *zl);取ziplist链表占用的字节数zl是ziplist的指针返回ziplist链表占用的字节数