List（版本3.2之前）、Hash 和 Sorted Set 这三种数据类型，都可以使用压缩列表（ziplist）来保存数据。

新版本Redis的quickList底层也是采用zipList支持，Redis版本更新频繁，本文不保证时效性。

 

一、ziplist结构

ziplist 是一个特殊双向链表，不像普通的链表使用前后指针关联在一起，它是存储在连续内存上的，设计主要是为了节省内存。

 

Redis官方对于ziplist的定义是（出自ziplist.c的文件头部注释）：

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.

 

翻译一下：ziplist是一个经过特殊编码的双向链表，它的设计目标就是为了提高存储效率。ziplist可以用于存储字符串或整数，其中整数是按真正的二进制表示进行编码的，而不是编码成字符串序列。它能以O(1)的时间复杂度在表的两端提供push和pop操作。

1、代码定义

压缩列表的函数定义和实现代码分别在 ziplist.h 和 ziplist.c 中。

不过，我们在 ziplist.h 文件中其实根本看不到压缩列表的结构体定义。这是因为压缩列表本身就是一块连续的内存空间，它通过使用不同的编码来保存数据。

 

 

这里为了方便理解压缩列表的设计与实现，我们先来看看它的创建函数 ziplistNew，如下所示：

unsigned char *ziplistNew(void) {
    //初始分配的大小
    unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;
    unsigned char *zl = zmalloc(bytes);
    …
   //将列表尾设置为ZIP_END
    zl[bytes-1] = ZIP_END;
    return zl;
}

实际上，ziplistNew 函数的逻辑很简单，就是创建一块连续的内存空间，大小为 ZIPLIST_HEADER_SIZE 和 ZIPLIST_END_SIZE 的总和，然后再把该连续空间的最后一个字节赋值为 ZIP_END，表示列表结束。

 

另外你要注意的是，在上面代码中定义的三个宏 ZIPLIST_HEADER_SIZE、ZIPLIST_END_SIZE 和 ZIP_END，在 ziplist.c 中也分别有定义，分别表示 ziplist 的列表头大小、列表尾大小和列表尾字节内容，如下所示。

 

//ziplist的列表头大小，包括2个32 bits整数和1个16bits整数，分别表示压缩列表的总字节数，列表最后一个元素的离列表头的偏移，以及列表中的元素个数
//ziplist的列表头大小，包括2个32 bits整数和1个16bits整数，分别表示压缩列表的总字节数，列表最后一个元素的离列表头的偏移，以及列表中的元素个数
#define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))
//ziplist的列表尾大小，包括1个8 bits整数，表示列表结束。
#define ZIPLIST_END_SIZE        (sizeof(uint8_t))
//ziplist的列表尾字节内容
#define ZIP_END 255

 

那么，在创建一个新的 ziplist 后，该列表的内存布局就如下图所示。注意，此时列表中还没有实际的数据。

 

 

然后，当我们往 ziplist 中插入数据时，ziplist 就会根据数据是字符串还是整数，以及它们的大小进行不同的编码。这种根据数据大小进行相应编码的设计思想，正是 Redis 为了节省内存而采用的。

 

2、存储结构

 

 

ziplist 列表项包括三部分内容，分别是前一项的长度（prevlen）、当前项长度信息的编码结果（encoding），以及当前项的实际数据（data）。下面的图展示了列表项的结构（图中除列表项之外的内容分别是 ziplist 内存空间的起始和尾部）。

 

 

3、节点结构及编码

 

结点结构：<prevlen> <encoding> <entry-data>，但有时候数值很小，用 <encoding> 也能保存数据，不需要 <entry-data>， 即 <prevlen> <encoding>。

 

4、encoding 编码

entry 的编码字段取决于具体值的内容，分为字符串、数字两种类型单独处理。

 

实际上，所谓的编码技术，就是指用不同数量的字节来表示保存的信息。在 ziplist 中，编码技术主要应用在列表项中的 prevlen 和 encoding 这两个元数据上。而当前项的实际数据 data，则正常用整数或是字符串来表示。

 

 

二、ziplist 的不足

一个 ziplist 数据结构在内存中的布局，就是一块连续的内存空间。这块空间的起始部分是大小固定的 10 字节元数据，其中记录了 ziplist 的总字节数、最后一个元素的偏移量以及列表元素的数量，而这 10 字节后面的内存空间则保存了实际的列表数据。在 ziplist 的最后部分，是一个 1 字节的标识（固定为 255），用来表示 ziplist 的结束，如下图所示：

虽然 ziplist 通过紧凑的内存布局来保存数据，节省了内存空间，但是 ziplist 也面临着随之而来的两个不足：

  • 查找复杂度高
  • 连锁更新风险

1、查找复杂度高

因为 ziplist 头尾元数据的大小是固定的，并且在 ziplist 头部记录了最后一个元素的位置，所以，当在 ziplist 中查找第一个或最后一个元素的时候，就可以很快找到。

 

但问题是，当要查找列表中间的元素时，ziplist 就得从列表头或列表尾遍历才行。而当 ziplist 保存的元素过多时，查找中间数据的复杂度就增加了。更糟糕的是，如果 ziplist 里面保存的是字符串，ziplist 在查找某个元素时，还需要逐一判断元素的每个字符，这样又进一步增加了复杂度。

 

也正因为如此，我们在使用 ziplist 保存 Hash 或 Sorted Set 数据时，都会在 redis.conf 文件中，通过 hash-max-ziplist-entries 和 zset-max-ziplist-entries 两个参数，来控制保存在 ziplist 中的元素个数。

 

不仅如此，除了查找复杂度高以外，ziplist 在插入元素时，如果内存空间不够了，ziplist 还需要重新分配一块连续的内存空间，而这还会进一步引发连锁更新的问题。

 

2、级联更新问题

 

当一个entry前边的entry的长度发生变化时，会导致需要增大entry 的prevlen字段的size 来存储前一个entry的长度,如果有连续多个entry的容量接近254时，就会发生多个entry的prevlen的size需要扩容，这时就发生所谓的级联更新。

 

级联更新发生在何种情形下：

ziplist插入元素或者删除元素时都可能发生级联更新。

 

 

三、何时使用zipList

 

1、hash时什么情况才用ziplist

同时满足以下条件：

  • 哈希对象保存的所有键值的字符串长度小于64字节；
  • 哈希对象保存的键值对数量小于512个；

 

  • 为什么不直接用hastable：

相比hashtable，ziplist结构少了指针，大大的减少了内存的使用，而内存对于redis来说弥足珍贵。

 

  • 为什么不用 linklist？

ziplist存储时内存分配是连续的，查询更快，这里的快只是相对双端队列。

 

  • ziplist如何实现hash存储？

 

将同一键值对的两个节点紧挨着保存，保存键的节点在前，保存值的节点在后，新加入的键值对，放在压缩列表表尾。

 

 

2、ZSet何时使用zipList

 

在redis.conf中，有如下两个参数：

zset-max-ziplist-entries 128
zset-max-ziplist-value 64

这两个条件均不满足，使用ziplist压缩表来实现sorted set

满足这两个条件之一，sorted set的内部实现会由ziplist转换为zset

 

3、List何时使用zipList

 

在版本3.2之前，Redis 列表list使用两种数据结构作为底层实现：

 

 

quicklist是 Redis 3.2 引入的数据类型，早期的列表类型使用的是ziplist (压缩列表) 和双向链表组成的，Redis 3.2 改为用 quicklist 来存储列表元素。

 

 

 

参考资料：

https://redis.com/ebook/part-2-core-concepts/01chapter-9-reducing-memory-use/9-1-short-structures/9-1-1-the-ziplist-representation/