原本打算只用一篇文章来解说 Redis 中的 list，在理论写作过程中发现 Redis 中有多种 list 的实现，所以筹备拆成多篇文章，本文次要讲 ziplist，ziplist 也是 quicklist 的根底。另外还有 skiplist，skiplist 尽管是 list，当次要和 set 命令相干，所以会放到前面。
本文次要波及到的源码在 ziplist.c
何为 ziplist？咱们能够在 ziplist.c 源码头部找到一段 Redis 作者的一段介绍。
The ziplist is a specially encoded dually linked list that is designed to be very memory efficient. It stores both strings and integer values, where integers are encoded as actual integers instead of a series of characters. It allows push and pop operations on either side of the list in O(1) time.However, because every operation requires a reallocation of the memory used by the ziplist, the actual complexity is related to the amount of memory used by the ziplist.
ziplist 是为了进步存储效率而设计的一种非凡编码的双向链表。它能够存储字符串或者整数，存储整数时是采纳整数的二进制而不是字符串模式存储。他能在 O(1)的工夫复杂度下实现 list 两端的 push 和 pop 操作。然而因为每次操作都须要重新分配 ziplist 的内存，所以理论复杂度和 ziplist 的内存使用量相干。
前半句还好了解，但每次 操作都须要从新分配内存…… 就有点回味无穷了。别急，你看完 ziplist 的具体实现就懂了。
ziplist 在逻辑上是个双向链表，但它是存储在一大块间断的内存空间上的。与其说 ziplist 是个数据结构，倒不如说他是 Redis 中双向链表的序列化存储形式。
ziplist 构造
整个 ziplist 在内存中的存储格局如下：
ziplist 次要有这么几个局部：
- zlbytes: 32 位无符号整型，示意整个 ziplist 所占的空间大小，蕴含了 zlbytes 所占的 4 个字节。
- 这个字段能够在重置整个 ziplist 大小时不须要遍历整个 list 来确定大小，空间换工夫。
- zltail: 32 位无符号整型，示意整个 list 中最初一项所在的偏移量，不便在尾部做 pop 操作。
- zllen: 16 位，示意 ziplist 中所存储的 entry 数量，然而留神，这里最多示意 $2^{16} -2$ 个 entry，如果是 $2^{16}-1$ 有非凡含意，$2^{16}-1$ 示意存储数量超过了 $2^{16}-2$ 个，但具体是多少个得遍历一次能力晓得。
- zlend: 8 位，ziplist 的开端示意，值固定是 255.
- entry: 不定长，可能有多个，list 中具体的数据项，上面会具体介绍。
entry
这里最外围的就是 entry 的数据格式，entry 还真有些简单，从上图中能够看出它次要有三个局部。
- prelen: 前一个 entry 的存储大小，次要是为了不便从后往前遍历。
- encoding: 数据的编码模式（字符串还是数字，长度是多少）
- data: 理论存储的数据
比较复杂的是 Redis 为了节俭内存空间，对下面三个字段设计了一套比较复杂的编码方式，实质上就是一套变长的编码协定，具体规定如下：
prelen
如果 prelen 数值小于 254，那就只用一个字节来示意长度，如果长度大于等于 254 就用 5 个字节，第一个字节是固定值 254(FE)来标识这是个非凡的数据，剩下的 4 个字节来示意理论的长度。
encoding
encoding 的具体值取决于 entry 中具体的内容，当 entry 是个 string 时，encoding 的前两字节存储了字符串的长度。当 entry 是一个整数的时候，前两字节默认都是 1，前面两字节标识出前面存的是哪种类型的整数，第一个字节就足够判断出 entry 是什么类型了。不同的 encoding 类型示例如下:
- |00pppppp| – 1 字节
长度小于或者等于 63 的 String 类型，’pppppp’ 无符号 6 位数标识 string 长度。
- |01pppppp|qqqqqqqq| – 2 字节
长度小于或者等于 16383 的 String 类型(14 位)，留神：14 位 ’pppppp’ 采纳大端的形式存储
- |10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| – 5 字节
长度大于等于 16384 的 String 类型，第二字节开始的 qqrrsstt 都是用来存储字符串长度的二进制位，可示意的字符串长度最大 2^32-1，第一字节的低 6 位没有用，所以都是 0。
留神: 32 位数采纳大端的形式存储
- |11000000| – 3 字节
存储 int16_t (2 字节).
- |11010000| – 5 字节
存储 int32_t (4 字节).
- |11100000| – 9 字节
存储 int64_t (8 字节).
- |11110000| – 4 字节
24 位有符号类型整数 (3 字节).
- |11111110| – 2 字节
8 位有符号类型整数 (1 字节).
- |1111xxxx| – (xxxx 在 0001 和 1101 之间) 4 位无符号整数.
0 到 12 的无符号整数. 编码值实际上是从 1 到 13，因为 0000 和 1111 不能应用，要留出一位示意 0，所以应该从编码值中减去 1 才是精确值
在某些比拟小的数值下，具体值能够间接存储到 encoding 字段里。
ziplist 的 API
ziplist.c 代码也较多，双链表操作很多代码在 ziplist 中比拟多，其实实质上都是它这简单的存储格局导致的，实际上了解了它的编码格局，具体代码不难理解。这里我只列出几个我认为比拟重要的 API，其余能够参考源码 ziplist.c。
ziplist 其实只是一种双向队列的序列化形式，是在内存中的存储格局，实际上并不能间接拿过去用，用户看到的 ziplist 只是一个 char * 指针，其中每个 entry 在理论应用中还须要反序列化成 zlentry 不便调用。
typedef struct zlentry {
unsigned int prevrawlensize; /* 内存中编码后的 prevrawlen 用了多少字节 */
unsigned int prevrawlen; /* 前一个 entry 占用的长度，次要是为了 entry 之间跳转 */
unsigned int lensize; /* 内存中编码后的 len 用了多少字节 */
unsigned int len; /* 以后 entry 的长度，如果是 string 则示意 string 的长度，如果是整数，则 len 依赖于具体数值大小。*/
unsigned int headersize; /* prevrawlensize + lensize. entry 的 head 局部用了多少字节 */
unsigned char encoding; /* 以后 entry 的编码格局 */
unsigned char *p; /* 指向数据域的指针 */
} zlentry;另外有一点，ziplist 在内存中是高度紧凑的间断存储，这意味着它起始对批改并不敌对，如果要对 ziplist 做批改类的操作，那就需重新分配新的内存来存储新的 ziplist，代价很大，具体插入和删除的代码如下。
/* 在 p 地位插入数据 *s. */
unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen;
unsigned int prevlensize, prevlen = 0;
size_t offset;
int nextdiff = 0;
unsigned char encoding = 0;
long long value = 123456789; /* initialized to avoid warning. Using a value
that is easy to see if for some reason
we use it uninitialized. */
zlentry tail;
/* 找到前一个节点计算出 prevlensize 和 prevlen */
if (p[0] != ZIP_END) {ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
} else {unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
if (ptail[0] != ZIP_END) {prevlen = zipRawEntryLength(ptail);
}
}
/* See if the entry can be encoded */
if (zipTryEncoding(s,slen,&value,&encoding)) {
/* 'encoding' is set to the appropriate integer encoding */
reqlen = zipIntSize(encoding);
} else {
/* 'encoding' is untouched, however zipStoreEntryEncoding will use the
* string length to figure out how to encode it. */
reqlen = slen;
}
/* We need space for both the length of the previous entry and
* the length of the payload. */
reqlen += zipStorePrevEntryLength(NULL,prevlen);
reqlen += zipStoreEntryEncoding(NULL,encoding,slen);
/* When the insert position is not equal to the tail, we need to
* make sure that the next entry can hold this entry's length in
* its prevlen field. */
int forcelarge = 0;
nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
if (nextdiff == -4 && reqlen < 4) {
nextdiff = 0;
forcelarge = 1;
}
/* Store offset because a realloc may change the address of zl. */
offset = p-zl;
// 计算出须要的内存容量，而后从新生成一个新大小的 zl 替换掉原来的 zl。zl = ziplistResize(zl,curlen+reqlen+nextdiff);
p = zl+offset;
/* 迁徙数据，而后更新 tail 的 offset */
if (p[0] != ZIP_END) {
/* Subtract one because of the ZIP_END bytes */
memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);
/* Encode this entry's raw length in the next entry. */
if (forcelarge)
zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
else
zipStorePrevEntryLength(p+reqlen,reqlen);
/* Update offset for tail */
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);
/* When the tail contains more than one entry, we need to take
* "nextdiff" in account as well. Otherwise, a change in the
* size of prevlen doesn't have an effect on the *tail* offset. */
zipEntry(p+reqlen, &tail);
if (p[reqlen+tail.headersize+tail.len] != ZIP_END) {ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}
} else {
/* This element will be the new tail. */
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
}
/* When nextdiff != 0, the raw length of the next entry has changed, so
* we need to cascade the update throughout the ziplist */
if (nextdiff != 0) {
offset = p-zl;
zl = __ziplistCascadeUpdate(zl,p+reqlen);
p = zl+offset;
}
/* 写入数据 */
p += zipStorePrevEntryLength(p,prevlen);
p += zipStoreEntryEncoding(p,encoding,slen);
if (ZIP_IS_STR(encoding)) {memcpy(p,s,slen);
} else {zipSaveInteger(p,value,encoding);
}
ZIPLIST_INCR_LENGTH(zl,1);
return zl;
}ziplist 节点删除
unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned int num) {
unsigned int i, totlen, deleted = 0;
size_t offset;
int nextdiff = 0;
zlentry first, tail;
zipEntry(p, &first);
for (i = 0; p[0] != ZIP_END && i < num; i++) {p += zipRawEntryLength(p);
deleted++;
}
totlen = p-first.p; /* 删除元素后缩小的内存空间(字节) */
if (totlen > 0) {if (p[0] != ZIP_END) {
/* Storing `prevrawlen` in this entry may increase or decrease the
* number of bytes required compare to the current `prevrawlen`.
* There always is room to store this, because it was previously
* stored by an entry that is now being deleted. */
nextdiff = zipPrevLenByteDiff(p,first.prevrawlen);
/* Note that there is always space when p jumps backward: if
* the new previous entry is large, one of the deleted elements
* had a 5 bytes prevlen header, so there is for sure at least
* 5 bytes free and we need just 4. */
p -= nextdiff;
zipStorePrevEntryLength(p,first.prevrawlen);
/* Update offset for tail */
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen);
/* When the tail contains more than one entry, we need to take
* "nextdiff" in account as well. Otherwise, a change in the
* size of prevlen doesn't have an effect on the *tail* offset. */
zipEntry(p, &tail);
if (p[tail.headersize+tail.len] != ZIP_END) {ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}
/* 把 tail 挪动到 ziplist 的后面 */
memmove(first.p,p,
intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)-1);
} else {
/* The entire tail was deleted. No need to move memory. */
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe((first.p-zl)-first.prevrawlen);
}
/* 更新 ziplist 大小 */
offset = first.p-zl;
zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff);
ZIPLIST_INCR_LENGTH(zl,-deleted); // 更新 zllen
p = zl+offset;
/* When nextdiff != 0, the raw length of the next entry has changed, so
* we need to cascade the update throughout the ziplist */
if (nextdiff != 0)
zl = __ziplistCascadeUpdate(zl,p);
}
return zl;
}插入删除的根本逻辑都是相似，先定位，而后算插入 / 删除后所需的内存空间变动，依据计算出来新的空间大小对 zl 做 ziplistResize()，而后更新 zl 的元信息。
除了插入删除外，像 ziplistPush ziplistMerge，这这种带改变的 API，最初都调用了 ziplistResize，ziplistResize 代码如下：
unsigned char *ziplistResize(unsigned char *zl, unsigned int len) {zl = zrealloc(zl,len);
ZIPLIST_BYTES(zl) = intrev32ifbe(len);
zl[len-1] = ZIP_END;
return zl;
}看起来很简短，其实大量的逻辑都在 zrealloc 中，zrealloc是个宏定义(忽然感觉 c 的宏定义很骚)，其实次要逻辑就是申请一块长度为 len 的空间，而后开释原来 zl 所指向的空间。这里能够看出 ziplist 批改的代价是很高的，如果在应用中有频繁更新 list 的操作，倡议对 list 相干的配置做些优化。
其余 API
具体 API 定义列表见源码 ziplist.h
unsigned char *ziplistNew(void); // 新建 ziplist
unsigned char *ziplistMerge(unsigned char **first, unsigned char **second); // 合并两个 ziplist
unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where); // 在 ziplist 头部或者尾部 push 一个节点
unsigned char *ziplistIndex(unsigned char *zl, int index); // 找到某个下标的节点
unsigned char *ziplistNext(unsigned char *zl, unsigned char *p); // 找到 p 节点的下一个节点
unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p); // 找到 p 节点的前一个节点
unsigned int ziplistGet(unsigned char *p, unsigned char **sval, unsigned int *slen, long long *lval); // 获取 entry 中存储的具体内容
unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen); // 插入
unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p); // 删除
unsigned char *ziplistDeleteRange(unsigned char *zl, int index, unsigned int num); // 删除某个下标区间内的节点
unsigned int ziplistCompare(unsigned char *p, unsigned char *s, unsigned int slen); // 比拟两个节点的大小
unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip); // 找到某个特定值的节点
unsigned int ziplistLen(unsigned char *zl); // ziplist 的长度
size_t ziplistBlobLen(unsigned char *zl); // ziplist 的存储空间大小
void ziplistRepr(unsigned char *zl); // 结语
ziplist 其实是一个逻辑上的双向链表，能够疾速找到头节点和尾节点，而后每个节点 (entry) 中也蕴含指向前 / 后节点的 ” 指针 ”，但作者为了将内存节俭到极致，摒弃了传统的链表设计(前后指针须要 16 字节的空间，而且会导致内存碎片化重大)，设计出了内存十分紧凑的存储格局。内存是省下来了，但操作复杂性也更新的复杂度上来了，当然 Redis 作者也思考了这点，所以也设计出了 ziplist 和传统双向链表的折中——quicklist，咱们将在下一篇博文中具体介绍 quicklist。
本文是 Redis 源码分析系列博文，同时也有与之对应的 Redis 中文正文版，有想深刻学习 Redis 的同学，欢送 star 和关注。
Redis 中文注解版仓库：https://github.com/xindoo/Redis
Redis 源码分析专栏：https://zxs.io/s/1h