图解+源码角度理解Redis底层原理(二)

2022-10-17 2022-11-17 xiebruce Comments 0 Comment174 Views7 Likes

Table of Contents

双向链表
- 双链表结构体
- 双链表的优缺点
ziplist
quickList
listpack
listpack存字符串示例
Hash类型存储原理
集合(set)存储原理
有序集合(zset)存储原理
key过期和内存淘汰策略
- key过期策略
- 内存淘汰策略
持久化
- RDB快照持久化
- AOF持久化
常见问题
- Redis最多能存几个key？

《图解+源码角度理解Redis底层原理》在本地写的时候是一篇文章，由于总字数差不多13万字，所以分成了两篇文章来发。

本文是接：图解+源码角度理解Redis底层原理(一)的内容的。

双向链表

Redis3.0之前列表(list)使用的就是双向链表结构来存储的，英文为doubly linked list。

双链表结构体

adlist.h第36行，adlist我猜是“A doubly linked list”，ad就是a doubly的意思

// 链表节点
typedef struct listNode {
    // 指向上一个节点的指针
    struct listNode *prev;
    // 指向下一个节点的指针
    struct listNode *next;
    // 当前节点的值
    void *value;
} listNode;

// 链表
typedef struct list {
    // 指向链表的头结点
    listNode *head;
    // 指向链表的尾结点
    listNode *tail;
    // 三个方法：(*dup),(*free),(*match)这种叫函数指针，说明这个函数不是直接定义，而是会调用该指针
    // (*dup)指向的函数，而(*dup)左边还有个*号，则表示它的返回值是一个指针，当然应该是“void *”一起
    // 看，表示返回void型指针(这种类型的指针可指向任意类型的变量)，(*free)没有返回值，(*match)返回int型值
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    // 用于存储链表的长度(即节点数)
    unsigned long len;
} list;

按以上结构体，画出的链表示意图如下所示

注意：对于head节点，因为它是头，没有上一个节点，所以它的prev指针为null，同理，对于tail节点，由于它是尾，没有下一个节点，所以next指针为null。

创建一个链表：先创建链表(即list)，然后创建节点(即listNode)，然后把它添加到list链表中，即一个一个的创建节点，再一个一个的添加到list中，在adlist.c文件中有创建链表，创建节点，插入节点，删除节点等等。

双链表的优缺点

优点：

每个节点都有两个指针和一个值，prev指针指向上一个节点，next指针指向下一个节点，所以获取某个节点的前置节点或后置节点的时间复杂度只需O(1)；
list结构中有head和tail两个属性直接指向链表的头和尾，所以获取链表的表头节点和表尾节点的时间复杂度只需O(1)；
list结构因为提供了链表节点数量len，所以获取链表中的节点数量的时间复杂度只需O(1)，本例的len为3；

缺点：

每个节点之间是通过指针相互指向，但在内存中并不是连续的，无法利用CPU缓存加速访问；
除首尾节点只有一个指针外，其它每个节点都有两个8字节的指针(prev和next)，可是value本身才占4个字节，指针就占了16字节，也就是说指针占的空间远远大于数据本身，这种情况叫“胖指针”。

因此，在Redis 3.0中，在节点少的情况下，改用ziplist作为链表的底层数据结构。

ziplist

ziplist定义

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. 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是一种特殊编码的双链表，旨在提高内存效率。它既存储字符串也存储整体值，其中整数被编码为真正的整数而不是字符串。它允许在列表的任意一边做push和pop操作，时间复杂度为O(1)。然而，因为每个操作都需要重新分配ziplist所使用的内存，所以ziplist的实际复杂度跟它所使用的内存大小有关(使用的越多就越复杂)。

ziplist结构

ziplist(压缩表)的结构如下(在ziplist.c文件中搜索“ZIPLIST OVERALL LAYOUT”)，可以在注释中看到ziplist结构如下所示

/*
* <zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
*/

注意，entry在这里解释成“条目”，而不是“入口/进入”。

我画成示意图如下

并且在ziplist.c文件中有以下详细解释ziplist每个字段都有什么用

* <uint32_t zlbytes> is an unsigned integer to hold the number of bytes that
 * the ziplist occupies, including the four bytes of the zlbytes field itself.
 * This value needs to be stored to be able to resize the entire structure
 * without the need to traverse it first.
 *
 * <uint32_t zltail> is the offset to the last entry in the list. This allows
 * a pop operation on the far side of the list without the need for full
 * traversal.
 *
 * <uint16_t zllen> is the number of entries. When there are more than
 * 2^16-2 entries, this value is set to 2^16-1 and we need to traverse the
 * entire list to know how many items it holds.
 *
 * <uint8_t zlend> is a special entry representing the end of the ziplist.
 * Is encoded as a single byte equal to 255. No other normal entry starts
 * with a byte set to the value of 255.

uint32_t zlbytes: 32位无符号整型(就是4个字节)，用于记录整个ziplist占用的字节数，包括zlbytes自己；
uint32_t zltail: 32位无符号整型(4个字节)，用于表示最后一个entry(条目)的偏移，这样的话，用ziplist的“起始地址+偏移”就能直接定位到最后一个entry(条目)的起始地址，这样做尾部pop操作时就非常方便，否则就要遍历整个ziplist，导致复杂度增加；
uint16_t zllen: entry(条目)的数量，由于使用16位无符号整型存储，所以能存的最大数字为2¹⁶-1=65535，但是在这里最大只能存65534(即2¹⁶-2)，原因是当值为65535(含)以上时，二进制位全部为1，即无论是65535,65536,65537,……，只要是大于等于65535，zllen都是全1，程序无法分辨它到底是65535，还是65536，还是65537，此时只能通过一个一个的遍历(即程序从头到尾数一遍)才能知道具体节点数，所以虽然16位无符号理论上能存的最大数字为2¹⁶-1=65535，但在zplist这里最大只能存65534。当然实际上是不可能发生大于65534这种情况的，因为有这么多条目时，redis早就改用另外的存储结构(quicklist)了，并不会用ziplist存；
uint8_t zlend: ziplist结束标记，它占一个字节，并且该字节全1(即8个1)，即0xFF，10进制的255。由于这个原因，其它entry(条目)中的标记都不能是全1，否则就会被识别为结束标记，造成错误；
顺便提一下，前面所有条目名称都是以zl开头，表示zip list，是这两个单词的首字母。

ziplist条目结构

上面把除entry(条目)以外的所有属性都解释了一遍，但就是没讲条目，因为条目本身又有一个结构，ziplist每个条目结构如下

<prevlen> <encoding> <entry-data>

示意图

prevlen: prev就是前一个，len是长度，prevlen意思就是前一个entry(条目)的长度，这样的话，根据当前条目的地址减去前一个条目的长度，就以定位到前一个条目的地址；
encoding: 用于标示data部分的类型，这个类型只有两种，字符串或整型数字，如果是字符串，还会标示出字符串的长度，具体下边会说；
data: 实际数据。

prevlen(占用1个或5个字节)：
如果prevlen小于254，则占用一个字节，如果等于或大于254，prevlen会占用5个字节，其中第一个字节会设置为254(二进制11111110，就是7个1最后一个0，十六进制是FE)，用于标记prevlen占用了5个字节，剩下的4个字节用于记录前一个entry(条目)的长度。

其实就是1个字节存不下了，就需要扩展到5个字节，但是第一个字节必须标记为254以便于识别已经启用5个字节模式，有人可能会说，8位二进制能表示的最大数是255，那为什么不用255作为标记呢？那是因为255被用于作为结束标记，如果用255来识别，就会被误识别为遇到了结束标记而不是扩展5字节标记。

所以ziplist的entry(条目)实际结构可能是以下两种：

1、当prevlen为0-253时，ziplist entry(条目)如下所示

2、当prevlen为大于253时，第一个字节固定为十六进制0xFE(即十进制254，实际存储的是二进制11111110)，ziplist entry(条目)如下所示

4个字节共32位，能存下的最大数字为2³²-1≈42.9亿多，其实就是3.9999999991GB，(2³²-1)/1024/1024/1024=3.9999999991。由于prevlen就是表示前一个元素的长度，这说明ziplist一个元素的长度最大可达3.99GB的，只不过实际上我们不可能保存这么长的元素而已，如果真的这样，那效率就非常低了。

ziplist条目encoding

encoding比较复杂，分两种情况：

1、实际存储数据为字符串；
2、实际存储数据为整型数字；

当实际存储数据为字符串时，使用encoding第一个字节的前两位来表示三种情况：

1、00xxxxxx: 前两位00，表示encoding占用一个字节，一个字节8位，剩下的6位用于存储后面data的长度，由于6位二进制最大为6个1，即2⁶-1=63，所以这种情况表示data的长度为范围为1-63；
2、01xxxxxx|xxxxxxxx: 前两位为01，表示encoding占用两个字节，两个字节16位，剩下的14位用于存储data部分的长度，由于14位最大数是14个1，即2¹⁴-1=16383，所以这种情况data的长度范围为64-16383，注意这14位是用大端字节序存储的，其它没有说明的都是用小端的；
3、10000000|xxxxxxxx|xxxxxxxx|xxxxxxxx|xxxxxxxx，第一个字节为10000000，表示encoding占用5个字节，剩下的4个字节用于存储data部分的长度，由于4个字节是32，位最大数为，即2³²-1，长度大约为42.9亿，所以这种情况data的长度为16384-42.9亿多，注意这里4个字节也是用大端字节序存储的；

当实际存储数据为整型时，encoding永远占1个字节，但data部分有以下6种情况：

1、当encoding为11000000时，表示data部分为2个字节(16位)，用于存储int16的整数；
2、当encoding为11010000时，表示data部分为4个字节(32位)，用于存储int32的整数；
3、当encoding为11100000时，表示data部分为8个字节(64位)，用于存储int64的整数；
4、当encoding为11110000时，表示data部分为3个字节(24位)，用于存储整数(最大能存16777215)；
5、当encoding为11111110时，表示data部分为1个字节(8位)，用于存储整数(最大能存255)；
6、当encoding为1111xxxx时，xxxx理论上为0000-1111(0-15)，但实际上为0001-1101(1-13)，为什么呢？因为如果它为0000，就变成了11110000时，这样就跟第4点重合了，会被识别为第4点的情况，也不能为1110，否则与第5点重合了，更不能为1111，因为这样就变成8个1，会被识别为ziplist的结束。所以它只能是0001-1101(1-13)，并且此时0001-1101并不是表示data的长度，而是直接表示data本身，这种情况就没有后面的data了，0001-1101分别表示十进制数1-13，但由于数字都是从0开始，所以它实际上应该表示0-12共13个数，所以实际使用的时候，需要把获取到的数字减1才是真正的数字，这个减1也是因为不能从0开始导致的。

zlentry结构体

zlentry结构体在ziplist.c文件第281行，如下所示

/* We use this function to receive information about a ziplist entry.
 * Note that this is not how the data is actually encoded, is just what we
 * get filled by a function in order to operate more easily. */
typedef struct zlentry {
    unsigned int prevrawlensize; /* Bytes used to encode the previous entry len*/
    unsigned int prevrawlen;     /* Previous entry len. */
    unsigned int lensize;        /* Bytes used to encode this entry type/len.
                                    For example strings have a 1, 2 or 5 bytes
                                    header. Integers always use a single byte.*/
    unsigned int len;            /* Bytes used to represent the actual entry.
                                    For strings this is just the string length
                                    while for integers it is 1, 2, 3, 4, 8 or
                                    0 (for 4 bit immediate) depending on the
                                    number range. */
    unsigned int headersize;     /* prevrawlensize + lensize. */
    unsigned char encoding;      /* Set to ZIP_STR_* or ZIP_INT_* depending on
                                    the entry encoding. However for 4 bits
                                    immediate integers this can assume a range
                                    of values and must be range-checked. */
    unsigned char *p;            /* Pointer to the very start of the entry, that
                                    is, this points to prev-entry-len field. */
} zlentry;

zlentry结构体各属性解释如下：

prevrawlensize：记录用了几个字节来存储下边的prevrawlen值，这个值在ziplist条目中是不存在的，需要通过函数计算获得。其实它只有两个值，1或5，当prevlen<254时，prevlen部分占用1个字节，即prevrawlensize=1，当prevlen>=254时，prevlen部分会占用5个字节，即prevrawlensize=5。这个是使用ziplist.c第470行的宏函数ZIP_DECODE_PREVLENSIZE()来判断的；
prevrawlen：记录上一个条目的长度，这个值在ziplist条目中是存在的(就是上边说的prevlen)；
lensize：记录用了几个字节来存储数据长度，其实就是encoding部分的长度，因为长度是存储在encoding部分的。根据前面ziplist条目encoding所讲的内容，我们可以得知如果存储的是字符串，则encoding可能占用1,2,5个字节，而如果存储的是整型(无论是多大的整型)，encoding都只占用1字节；
len：ziplist条目中实际数据的长度，该值在ziplist条目中虽然存在，但并不是像结构体字段那样能直接获取，而是需要通过读取ziplist。要分两种情况：1、存的是字符串，2、存的是整型数字。如果是字符串，那存储的字符串多长，这个len就是多少字节，比如你存的是字符串“hello”，那么len值就是5字节。但如果存的是整数，就有可能是0,1,2,3,4,8字节，这个前面ziplist条目encoding中有讲，当存储的数据为整数时，data部分的长度有6种情况，即有可能使用1个字节来存储整数，也有可能是2字节，3字节，4字节或8字节，那0字节又是怎么回事呢？0字节表示没有data部分，而是直接把数字存储在encoding剩余的位里面了(只能存0-12这13个数，当然实际存的是1-13，使用时要减1)；
headersize：这个值就等于prevrawlensize + lensize，为什么呢？因为一个ziplist条目除了真正的数据部分，其它辅助用的数据都叫header，根据前面的解释，prevrawlensize就是条目中prevlen的长度，而lensize就是存储“数据部分长度”所占用的字节数，显然这两个值在ziplist条目中并不是直接能获取的一个值，而是需要通过判断或计算获得；
encoding：用于存储编码，对应的宏定义在ziplist.c第206-213行，分别为3种字符串编码ZIP_STR_06B、ZIP_STR_14B、ZIP_STR_32B(这里的B是bit，即位的意思)，以及5种整型编码ZIP_INT_16B、ZIP_INT_32B、ZIP_INT_64B、ZIP_INT_24B、ZIP_INT_8B；
*p：指当前条目(entry)的指针，由于ziplist每个条目的开头都是prevlen，所以实际上这个指针指向的就是当条目的prevlen最左侧的起始地址；

特别注意：zlentry结构体并不是ziplist条目(entry)的实际结构，它只是用来存储实际存储的条目中通过函数计算得到的一些数值，你可以认为zlentry这个结构体里面的属性，是用来存储ziplist条目被解析之后得到的值的。

ziplist存储实例

我们这里讲解一下官方案例，即使用ziplist存储数字2和5，在ziplist.c中搜索“EXAMPLES OF ACTUAL ZIPLISTS”即可找到该案例，这里我把案例图形画，更容易理解。

示意图如下所示

1、0f 00 00 00是zlbytes(占4个字节)，zlbytes用于存储整个ziplist占用的字节数，本例总共占用15个字节，而十六进制0f就是十进制的15。另外，由于Redis在没有特殊说明的情况下都是用小端字节序(低字节存在低内存地址)，并且画图时，一般默认为内存左低右高，所以0f写在左边其实是在内存的低地址中的，这与我们平时写的十六进制数刚好相反，如果我们平时写十六进制数字，那么0f000000应该写成0x0000000f；
2、0c00 0000是ztail(占4个字节)，zltail用于表示最后一个entry(条目)的字节偏移(即offset)，我们假设ziplist起始地址为0，那么entry2的起始地址刚好是12，而十六进制的0c就是十进制的12，所以zltail的数字是对的；
3、02 00是zllen(占两个字节)，zllen用于表示entry(条目)数量，而本例我们存储的是2和5两个数字，即两个条目，所以zllen中02就是2，是对的上的；
4、00 f3是第一个entry(条目)，而条目是由“prevlen+encoding+data”构成的，但是根据前面ziplist条目结构可知，要存储的2和5两个数字由于它们是在1-13之间的整型数字，所以采用的是encoding中的第6种情况，即把data直接存在encoding中，所以没有data部分。00 f3中的00代表的就是prevlen为0，由于它是第一个entry(条目)，并没有前一个entry(条目)，所以它的prelen为0，而f3的格式是1111xxxx前面4个1就是f，而3表示xxxx就是0011，由于这种情况需要把存储的数字减1才是实际数字(ziplist条目结构中encoding的第6点有说明原因)，所以3-1=2，表示存储的是2；
5、同理，entry2存储的是5，由于它前面的entry1是两个字节，所以它的prelen就是2，所以02 f6中的02就是这么来的，而f6的话，也是因为1111xxxx这种格式，f表示前面4个1，6的话就表示实际存储的是5，因为6-1=5(ziplist条目结构中encoding的第6点有说明减1的原因)；
6、最后的ff是ziplist的结束标记符号，即用1个字节8位全为1来表示ziplist结束。

在前面的基础上，添加一个“Hello World”字符串，示意图如下

ziplist存在的问题

ziplist存在的问题有两个：

1、每个entry(条目，或叫“节点”)记录了上一个条目的长度，而根据ziplist条目结构中的“ziplist条目的encoding”可知，当prelen≤253时，prevlen占用一个字段，当prevlen>253时，prevlen部分就会扩展成5个字段；
2、节点之间是在一段连续的内存中的，插入、删除都会导致数据需要在内存中移动，这就需要重新分配内存，导致大量的数据拷贝。

假设有一个ziplist每个条目的长度都在250-253之间，我在它的头部插入一个长度超过253的entry(条目)，那么原头部条目现在就是第二个，它的prevlen就要保存刚刚新插入的条目的长度，由于新插入的条目长度大于253，所以它必须由之前的一个字节扩展到5个字节，即长度增加了4个字节，此时它的总长度至少为250+4=254，这又会导致它的下一个条目中的prevlen要修改，这样就会发生连锁反应，需要不断的修改每个节点的prevlen。当然这个触发条件也比较特殊，就是需要每个节点的长度都在250-253之间，说实话我感觉也不会有这么碰巧吧。

但无论如何，由于这个连锁更新问题的存在，ziplist只会在数据量不大时使用，这样虽然会有连锁更新问题，但因为需要连锁更新的entry(条目)并不多，所以不会对性能造成很大的影响。

对于数据量大的情况，redis 3.2引入了quickList，quicklist并不是用来代替ziplist的，quicklist的本质就是一个双链表，只不过它使用ziplist作为节点的存储格式，而不是直接把值存放在节点里，这样的双链表就叫quicklist，由于每个节点的ziplist长度并不是很长(配置文件可配置)，所以导致的连锁更新prevlen问题以及内存移动问题也没那么严重。后来又在redis又在5.0引入listpack，listpack是用来代替quicklist中的ziplist。

quickList

在t_list.c-3.0.7中，list还是使用的ziplist和linkedlist两种，而到3.0.7的下一个版本t_list.c-3.2-rc1，就已经直接换成了quicklist了，所以quicklist是3.2版本中引入的。

在redis 7.0之前，quicklist的解释是“A doubly linked list of ziplists”，意思就是以ziplist为节点的双链表，在quicklist.c-6.2文件开头的注释中有写。

从redis 7.0开始，quicklist的节点采用listpack作为底层数据结构，在quicklist.c-7.0文件开头的注释中“A doubly linked list of ziplists”已经改为了“A doubly linked list of listpacks”。

但无论是用ziplist还是listpack，它只是节点的格式变了，而宏观上看quicklist，它还是一个双向链表。

quicklist存储结构示意图

使用ziplist作为底层存储结构的quicllist结构示意图(其中ziplist本身又可以使用LZF压缩算法压缩一次以减小空间占用)

使用listpack作为底层存储结构的quicllist结构示意图(其中listpack本身又可以使用LZF压缩算法压缩一次以减小空间占用)

quistList结构体

Redis 7.0之前的quicklist结构体

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all ziplists */
    unsigned long len;          /* number of quicklistNodes */
    int fill : QL_FILL_BITS;              /* fill factor for individual nodes */
    unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

Redis 7.0(含)之后的quicklist结构体

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all listpacks */
    unsigned long len;          /* number of quicklistNodes */
    signed int fill : QL_FILL_BITS;       /* fill factor for individual nodes */
    unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

这两个结构体的区别有两个地方：

1、count的注释，由ziplists变成了listpacks了；
2、fill，7.0之前是int，而7.0(含)之后，变在了signed int，其实这是一样的，都是“有符号整型”，int默认就是signed int(与之对应的是unsigned int)。

所以本质上就是这个quicklist结构体完全没有变化。

quicklist结构体共8个字段40个字节，因为bookmarks[]是quicklistBookmark结构体类型，该类型占5个字节，所以其它的都向5个字节对齐，8×5=40个字节。

quicklist结构体各字段解释：

*head 头部指针，指向快速列表头部节点；
*tail 尾部指针，指向快速列表尾部节点；
count ziplist或listpack总元素个数(因为quicklist底层是用ziplist或listpack存的，7.0以后都用listpack存了)；
len quicklist总节点数；
fill 每个节点的最大容量，在64位系统中是16位，即2个字节，最多可存储2¹⁶=65536，65536/64=64Kb，对应redis.conf中的list-max-ziplist-size(7.0之前)或list-max-listpack-size(7.0之后)配置项，它有正值和负值，具有意思可以看redis.conf中的注释，一般用-2(默认值)比较好；
compress 边缘节点压缩深度。快速列表的ziplist或listpack都是使用quicklistLZF算法压缩过的，但一般会在最左边和最右边留几个不压缩，因为边缘节点访问更频繁(如lpush,rpush,lpop,rpop)，不压缩就避免了来回压缩和解压(压缩和解压都会损耗性能和消耗时间)，compress字段就是用于标注左右两侧留下几个节点不要压缩，如果compress为0，那说明所有节点都不压缩。该字段在64位系统中占16位，即两个字节，对应redis.conf中的list-compress-depth配置项；
bookmark_count 用于标注bookmark数组的长度，在64位系统中占4位，即bookmarks数组最大长度为16；
bookmarks[] 当quicklist结构体重新分配内存时，bookmarks[]数组将会被填充，相当于是一个临时中转的地方，平时该数组是不会占用内存空间的。

关于fill值在配置文件中的配置如下：

以下是7.0之前的redis.conf中list-max-ziplist-size参数值的注释，它有正数和负数，正数你设置多少就表示最大允许有几个ziplist元素，负数从-5到-1，分别代表能设置的最大值如下所示

# Lists are also encoded in a special way to save a lot of space.
# The number of entries allowed per internal list node can be specified
# as a fixed maximum size or a maximum number of elements.
# For a fixed maximum size, use -5 through -1, meaning:
# -5: max size: 64 Kb  <-- not recommended for normal workloads
# -4: max size: 32 Kb  <-- not recommended
# -3: max size: 16 Kb  <-- probably not recommended
# -2: max size: 8 Kb   <-- good
# -1: max size: 4 Kb   <-- good
# Positive numbers mean store up to _exactly_ that number of elements
# per list node.
# The highest performing option is usually -2 (8 Kb size) or -1 (4 Kb size),
# but if your use case is unique, adjust the settings as necessary.
list-max-ziplist-size -2

而7.0开始，就换成了list-max-listpack-size这个参数了，因为它底层已经改成了listpack，但参数的作用还是一样，只不过换成了listpack而已，也是表示它允许设置的元素的多少

# Lists are also encoded in a special way to save a lot of space.
# The number of entries allowed per internal list node can be specified
# as a fixed maximum size or a maximum number of elements.
# For a fixed maximum size, use -5 through -1, meaning:
# -5: max size: 64 Kb  <-- not recommended for normal workloads
# -4: max size: 32 Kb  <-- not recommended
# -3: max size: 16 Kb  <-- probably not recommended
# -2: max size: 8 Kb   <-- good
# -1: max size: 4 Kb   <-- good
# Positive numbers mean store up to _exactly_ that number of elements
# per list node.
# The highest performing option is usually -2 (8 Kb size) or -1 (4 Kb size),
# but if your use case is unique, adjust the settings as necessary.
list-max-listpack-size -2

quicklistNode结构体

quicklistNode(7.0以前)

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

quicklistNode(7.0以后)

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *entry;
    size_t sz;             /* entry size in bytes */
    unsigned int count : 16;     /* count of items in listpack */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* PLAIN==1 or PACKED==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

以上两个版本的结构体只有*zl和*entry不一样，其实它们两个只是换了个名字，类型还是指针，*zl是指向ziplist结构的指针(7.0之前使用)，*entry是指向listpack结构的指针(7.0之后使用)。

quicklistNode是一个32字节大小的结构体，用于表示一个节点，在64位系统中，指针都是64位(8字节)，所以前面3个指针*prev,*next,*zl(或*entry)加起来就是24字节，剩下8字节，size_t sz占4字节，后面所有的unsigned int占4字节。

其中size_t是sizeof()返回的类型(类型是一种用来表示“size”的类型)，在这里它就是unsigned int，但它又有可能是unsigned long int之类的，反正在这里要凑够32字节，那它肯定就是4字节，这跟具体的实现有关。

quicklistNode结构体各字段解释：

*prev 指向上一个节点，指针占8字节(64位系统)；
*next 指向下一个节点，指针占8字节(64位系统)；
*zl 仅redis版本<7.0时存在，指向真正存储节点数据的ziplist(zl本身就是zip list的两个首字母)，占8字节(64位系统中指针都占8字节)；
*entry 仅redis版本>=7.0时存在，指向真正存储节点数据的listpack，占8字节(64位系统中指针都占8字节)；
sz ziplist或listpack占用的字节数(sz表示size)，size_t在这里占4字节，是unsigned int的别名；
count ziplist(<7.0)或listpack(>=7.0)中的条目(entry)个数；
encoding 只有1和2两个值，1表示未压缩，2表示使用LZF算法压缩过；
container 是否有容器，1表示不使用容器，2表示使用ziplist(<7.0)或listpack(>=7.0)结构作为数据容器；
recompress 当使用lindex之类的命令获取元素的值时，元素本身还在原位，不会被弹出，但是它必须解压才能返回真正的元素值，而解压后就需要把recompress标记为1，等有机会时就会把这个元素重新压缩；
attempted_compress 等于1时表示节点太小，不能压缩(仅用于自动化测试)；
extra 预留字段，暂时不会用到；

quicklistEntry结构体

7.0之前和7.0之后quicklistEntry结构体完全一样，没有修改

typedef struct quicklistEntry {
    const quicklist *quicklist;
    quicklistNode *node;
    unsigned char *zi;
    unsigned char *value;
    long long longval;
    size_t sz;
    int offset;
} quicklistEntry;

quicklistEntry其实就是quicklistNode(快速列表其中一个节点)底层数据结构的其中一个条目(或叫一个元素)，底层数据结构在7.0之前是ziplist，7.0开始改用listpack，所以quicklistEntry这个结构体就是ziplist(或listpack)的其中一个条目(英文叫entry)，也可以说是一个元素，你每往链表中lpush或rpush一个字符串或一个整数，那么这个字符串或整数就是ziplist或listpack的“一个条目(entry)”，或叫一个元素(element)。

*quicklist 快速列表指针，用于标记该条目属于哪个快速列表；
*node 节点指针，用于标记该条目属于快速列表中的哪个节点；
*zi ziplist(或listpack)指针，用于标记该条目属于哪个ziplist(或listpack)；
*value 如果该条目(entry)存储的数据为字符串，则*value就指向这个字符串，由于C中字符串由数组存储，所以这里是指针，而不是字符串本身；
longval 如果该条目为整型，就存储longval中；
sz 用于存储*value的长度(sz是size，就是大小的意思)；
offset 本条目(entry)在ziplist或listpack中的偏移(就是标记它是第几个元素)；

quicklistLZF结构体

为了进一步节省内存，quicklist节点中的ziplist(<7.0)或listpack(>=7.0)会被使用LZF算法压缩，从而占用更少的空间，当然由于quicklist左右两边的数据比较常被访问到，所以一边在左右两边都会留下几个节点的数据不压缩，从而避免重复压缩和解压造成性能损耗及存取速度变慢。

这两边留下的不压缩的节点数，可以在redis.conf中以下两个参数中配置，具体见quistList结构体中fill属性，因为以下两参数配置的值最终其实是被赋值到quicklist结构体的fill属性中的

# <7.0
list-max-ziplist-size

# >=7.0
list-max-listpack-size

以下是quicklistLZF结构体，是用于存储使用LZF算法压缩过的数据的

typedef struct quicklistLZF {
    size_t sz; /* LZF size in bytes*/
    char compressed[];
} quicklistLZF;

sz 压缩后的字符串占用的字节数(sz是size的意思)；
compressed[] 压缩好的数据就存储在这个数组中；

quicklist极端情况

当一个节点中的ziplist或listpack元素非常多时，相当于退化成了ziplist或listpack；
当一个节点中只有一个ziplist或listpack元素时，相当于退化成了普通的双向链表；

所以一个节点中的ziplist或listpack元素数量要合适，这个值可以在配置文件中的以下两个配置文件中配置

list-max-ziplist-size (配置每个quicklistNode中ziplist元素最大允许数量，<7.0)
list-max-listpack-size(配置每个quicklistNode中listpack元素最大允许数量，>=7.0)

listpack

listpack的定义

目前listpack.c的注释中并没有像ziplist.c那样直接给出listpack的结构，因为它还是unstable的，未正式发布，但listpack.c中还是有提到我们可以在这里找到它的定义，但点进去后README.md中并没有，而是有一句话

You can find the specification in the listpack.md file in this repository.
翻译：你可以在该仓库的listpack.md文件中找到说明书。

所以需要我们自己点击源文件中的listpack.md文件来查看listpack的文档，点开后我发现，它最新一个版本是“Version 1.2, 3 Feb 2017”，而我写这个文章的时间是2022-07-15，所以已经是5年半以前写的了，我也不知道为什么还没有完全用在正式版本中。

打开后，基本上就是说listpack是用于解决ziplist存在的问题的

Listpack takes the good ideas of ziplists and reimplement it in order to create a more compact, faster to parse implementation, that maps directly to simple to audit and understand code. Moreover the single entries representation in listpack were redesigned in order to better exploit the kind of data Redis users normally store in lists and hashes.
翻译：为了创建一个更加紧凑，解析更快的实现，listpack吸收了ziplist的优点并重新实现它，让它直接映射到易于审计和理解的代码中。而且，listpack中的单个条目被重新设计，以便更好的利用redis用户通常存储在list和hash中的数据类型。

listpack结构

listpack结构如下所示

tot-bytes: tot就是total的前三个字母，意思是整个listpack总字节数(包括tot-bytes自己以及结尾的listpack-end-byte)。该字段是32位无符号整型，即4个字节，最大可表示的字节数为2³²-1≈3.99GB；
num-elements: listpack元素个数，16位无符号整型，即两个字节，最大可表示2¹⁶-1=65535个元素，
listpack-end-byte: 用一个字节8位全部为1(十六进制为0xFF，十进制为255)表示listpack结束。

listpack每个元素(entry的)结构如下：

encoding-type: 编码类型，有很多值，下边会详细说；
element-data: 元素实际数据(一个整数或一个表示字符串的数组)，与ziplist类似，data为整型数字时，data部分不一定会有，因为有时候data部分直接存储在encoding-type里了；
element-tot-len: 元素总的长度，按需要存储的数字不同，最小1字节，最大可达5字节，tot是total前三个字母。其实它只是encoding-type+element-data的长度，并不包括element-tot-len自己，这个很容易让人误解，而且文档说的不清晰，只有看源码才知道(后面有源码分析)；

encoding-type

0xxxxxxx，第一位为0，剩下7位表示无符号整型数字，最大可表示2⁷-1=127，所以它可以表示0-127范围内的整型数字，也就是说127(含)以内的数字就没有element-data部分了，直接存在encoding-type部分剩余的“位”中了；
10xxxxxx，前两位为10，剩下6位表示element-data中字符串的长度，最大可表示2⁶-1=63，所以element-data最多可存63个字符(可理解为长度是63的字符串)；

1,2位同时为11，3,4位不同时为1:

110xxxxx|xxxxxxxx: 当第3位为0时，无论第4位是0还是1，都不会导致3,4位同时为1，符合规则，剩下的13位x用于表示有符号整型数字
1110xxxx|xxxxxxxx: 固定第3,4位为10，这样剩下的12位用于表示字符串长度，可记录的最长字符串长度为2¹²-1=4095；

第一个字节前四位为1，通过后四位来区分不同类别:

11110000|<4B长度><字符串>: 后四位为0000，表示后面有4字节表示长度，4字节后就是字符串数据(element-data)；
11110001|<16位有符号整型>: 后四位为0001，表示后面有16位(2个字节)表示有符号整型数字；
11110010|<24位有符号整型>: 后四位为0010，表示后面有24位表示有符号整型数字；
11110011|<32位有符号整型>: 后四位为0011，表示后面有32位表示有符号整型数字；
11110100|<64位有符号整型>: 后四位为0100，表示后面有64位表示有符号整型数字；
1111xxxx: 后四位为0101-1110时，没有被使用，应该是预留以后用作其它用途；
11111111: 后四位全为1，因为前四位也是全为1，所以整个字节全1，它就是listpack终止符(0xff)；

element-tot-len

element-tot-len主要是用于反向查找用的(定位当前元素的上一个元素)。element-tot-len中保存的是元素的长度(不包括element-tot-len自己，其实就是encoding-type + lement-data的长)，这个长度是为了可以从右向左获取上一个元素，所以它的存储是用大端字节序的(高位放在内存低地址，低位放在内存高地址)。

按“encoding-type + lement-data”值的大小的不同，element-tot-len最小占1字节，最大可达5字节。但不管是用1个字节还是5字节表示长度，它每个字节的最高位都被用来作为“左侧是否还有更多字节”的标记位，0表示没有了，1表示还有，所以每个字节其实只有7位能真正用来存长度用，并且其实它是多个字节之间的7位拼起来再从右到左重新分8位一组(一个字节)，计算真实数字时，就好像最高位不存在一样。

比如数据部分长度为500，那么它怎么存500这个值呢？500的二进制为111110100，共9位，一个字节存不下，所以要两个字节，如下所示

00000001 11110100

但事实上并不能这么存，因为每个字节的最高位并不会被用来作为数字用，而是用作“左侧还有没有更多字节”的标志位，所以实际上应该写成

[0]0000011          [1]1110100
 |                   |
 `- 左侧没有数据了      `- 左侧还有更多数据

element-tot-len存储500的示意图如下：

这个二进制写成十六进制是：\xF4\x03，也就是说，标记位虽然不用于表示实际数字，但记录的时候也是算上它的，不然怎么知道它是1还是0呢？所以第一个字节前面四个1就是F，后面的0100就是4，所以是F4，而第二个字节前面4位为0，后面是0011也就是3，所以记为03，\x表示它后面的数字为十六进制。而且这里不能写成\x03\xF4，因为平时写数字都是左高位右低位，与内存无关，只有在内存中表示时，才会有大端小端的说法。

listpack存字符串示例

encoding-type

存hello时的encoding-type：
由于hello长度为5，所以它符合10xxxxxx规则，前两位固定为10，表示这是一个小长度字符串，后6位表示字符串长度，由于字符串长度为5，所以是101，补齐6位就是000101，跟前面的10拼直接就是10000101，转成十六进制是0x85。

存空字符串的encoding-type：
由于空字符串长度为0，所以它符合10xxxxxx规则，前两位固定为10，表示这是一个小长度字符串，后6位表示字符串长度，由于字符串长度为0，补齐6位就是6个0000000，跟前面的10拼直接就是10000000(一个1，七个0)，转成十六进制是0x80。

注：这个在文档中写成了\x45和\x40，是写错了，其实应该是\x85和\x80，见这个issue。

element-tot-len

存“hello”时的element-tot-len：

encoding-type: 1Byte
encoding-data: hello = 5Bytes(注意这里是不存`\0`的，所以长度不是6而是5)
element-tot-len: 1+5 = 6Bytes(encoding-type + element-data, 不包括element-tot-len自己)

存“空字符串”时的element-tot-len：

encoding-type: 1Byte
encoding-data: null 0Bytes(注意这里是不存`\0`的，所以长度不是1而是0)
element-tot-len: 1+5 = 6Bytes(encoding-type + element-data, 不包括element-tot-len自己)

查找上一个元素源码分析

我们从lpLast()函数入手分析(listpack.c-L505)，这也是快速定位到整个listpack最后一个元素的原理，执行lpop操作时就可以用这个方法获取最后一个元素的地址

/* Return a pointer to the last element of the listpack, or NULL if the
 * listpack has no elements. */
unsigned char *lpLast(unsigned char *lp) {
    unsigned char *p = lp+lpGetTotalBytes(lp)-1; /* Seek EOF element. */
    return lpPrev(lp,p); /* Will return NULL if EOF is the only element. */
}

lp指针指向的是整个listpack的起始地址，lpGetTotalBytes(lp)是从listpack中获取tot-bytes的值(即整个listpack的长度)，lp + lpGetTotalBytes(lp)刚好让指针指向listpack末尾，但是又减了1(减掉的是listpack-end-byte这一个字节)，所以它刚好指向最后一个元素末尾

然后它调用了lpPrev(lp,p)，代码如下(listpack.c-L482)，这里p指向的是listpack最后一个元素的结尾，事实上它可以指向任何一个元素的结尾(当在元素之间时，它既是当前元素的起始地址，也是上一个元素的末尾地址)

/* If 'p' points to an element of the listpack, calling lpPrev() will return
 * the pointer to the previous element (the one on the left), or NULL if 'p'
 * already pointed to the first element of the listpack. */
unsigned char *lpPrev(unsigned char *lp, unsigned char *p) {
    assert(p);
    if (p-lp == LP_HDR_SIZE) return NULL;
    p--; /* Seek the first backlen byte of the last element. */
    uint64_t prevlen = lpDecodeBacklen(p);
    prevlen += lpEncodeBacklen(NULL,prevlen);
    p -= prevlen-1; /* Seek the first byte of the previous entry. */
    lpAssertValidEntry(lp, lpBytes(lp), p);
    return p;
}

因为在hello这个例子中，element-tot-len只有一个字节，所以p--其实是指向了element-tot-len头部(也可以认为是指向了element-tot-len的第一个字节)

当element-tot-len有多个字节时，p--其实只是让p指向了上一个元素的element-tot-len中的最后一个字节

然后调用lpDecodeBacklen(p)函数(listpack.c-L384)。特别需要注意的是，当element-tot-len有多个字节时，p最初只是指向它的最后一个字节，然后在lpDecodeBacklen()函数中通过判断该字节的最高位是否为1来决定是否需要继续向左寻找剩下的字节，最终得出整个长度

/* Decode the backlen and returns it. If the encoding looks invalid (more than
 * 5 bytes are used), UINT64_MAX is returned to report the problem. */
static inline uint64_t lpDecodeBacklen(unsigned char *p) {
    uint64_t val = 0;
    uint64_t shift = 0;
    do {
        val |= (uint64_t)(p[0] & 127) << shift;
        if (!(p[0] & 128)) break;
        shift += 7;
        p--;
        if (shift > 28) return UINT64_MAX;
    } while(1);
    return val;
}

lpDecodeBacklen(p)函数运行过程：

00000110 0x06 --- p[0]就是p的第一个字节(当然它也只有一个字节)
01111111 127 (&)
----------------
00000110 0x06   --- shift为0所以不用左移(如果要，则左移比“按位或”优先)
00000000 0  (|) --- 因为val刚开始为0，所以跟0按位与
----------------
00000110 0x06
10000000 128 (&)--- 与128按位与来判断是否break，是因为只有最高位为1
                     时才能不为0，前面说过最高位为1时，表示左侧有数据
----------------
00000000 --- 为0，break，结束循环，最终val的值为00000110,即0x06

然后运行lpEncodeBacklen(NULL,prevlen)，第一个参数为NULL说明不用管buf变量。该函数主要用于计算element-tot-len占用了几个字节，并依此计算出整个元素占用的长度，因为前面得到的prevlen只是“encoding-type + element-data”的长度，想要获取整个entry的长度，还要加上element-tot-len占用的字节数，所以把prevlen传进来，看看要用几个字节才能存下prevlen这个数字

/* Store a reverse-encoded variable length field, representing the length
 * of the previous element of size 'l', in the target buffer 'buf'.
 * The function returns the number of bytes used to encode it, from
 * 1 to 5. If 'buf' is NULL the function just returns the number of bytes
 * needed in order to encode the backlen. */
static inline unsigned long lpEncodeBacklen(unsigned char *buf, uint64_t l) {
    if (l <= 127) {
        if (buf) buf[0] = l;
        return 1;
    } else if (l < 16383) {
        if (buf) {
            buf[0] = l>>7;
            buf[1] = (l&127)|128;
        }
        return 2;
    } else if (l < 2097151) {
        if (buf) {
            buf[0] = l>>14;
            buf[1] = ((l>>7)&127)|128;
            buf[2] = (l&127)|128;
        }
        return 3;
    } else if (l < 268435455) {
        if (buf) {
            buf[0] = l>>21;
            buf[1] = ((l>>14)&127)|128;
            buf[2] = ((l>>7)&127)|128;
            buf[3] = (l&127)|128;
        }
        return 4;
    } else {
        if (buf) {
            buf[0] = l>>28;
            buf[1] = ((l>>21)&127)|128;
            buf[2] = ((l>>14)&127)|128;
            buf[3] = ((l>>7)&127)|128;
            buf[4] = (l&127)|128;
        }
        return 5;
    }
}

return 1,2,3,4,5，分别表示需要用1-5个字节来保存prevlen这个数字，每个if elseif中的数字，分别对应1-5个字节时能表示最大的数字，每个字节只有7位能真正用作记录数字(最高位被用作左侧是否还有数据的标志位)，因此它们能表示的最大数字分别为2⁷-1=127, 2¹⁴-1=16383, 2²¹-1=2097151, 2²⁸-1=268435455, 2³⁵-1=34359738367。

由于0x06用一个字节来保存都绰绰有余，所以element-tot-len占用一个字节，prevlen +=其实就是把前面encoding-type + element-data的长度再加上现在计算得到的element-tot-len长度，以此求得整个元素的总长度。

p -= prevlen-1：

虽然lpDecodeBacklen(p)函数内对p做了循环p--的操作，但是它并不会影响p -= prevlen-1这里的p，这里的p还是最开始传进来做了一次p--;后的值，做了自减操作后，p就指向了上一个元素(entry1)中的倒数第1字节，如下图，很明显，entry1剩下的部分长度就等于prevlen-1，所以p -= prevlen-1就是让p指向entry1的开头了。

Hash类型存储原理

控制参数

Hash底层可由两种结构来存储：

1、使用节省内存的紧凑型格式，叫ziplist(<7.0)或listpack(>=7.0)；
2、使用hashtable(哈希表)格式。

那什么时候会用紧凑型格式，什么时候会用hashtable格式呢？这是由redis.conf中的两个配置来决定。

这两个配置可以从redis.conf-6.2，redis.conf-7.0中搜索到

# Hashes are encoded using a memory efficient data structure when they have a
# small number of entries, and the biggest entry does not exceed a given
# threshold. These thresholds can be configured using the following directives.

翻译：当哈希的条目(entry)比较少，并且其中最大的条目不超过给定的阈值时，哈希会使用一种内存高效数据结构进行编码，这些阈值可以使用以下的指令来配置

# <7.0
hash-max-ziplist-entries 512
hash-max-ziplist-value 64

# >=7.0
hash-max-listpack-entries 512
hash-max-listpack-value 64

也就是说，默认情况下，当ziplist或listpack的条目(entry)数不超过512，并且所有条目(entry)中最大的一个不超过64字节时，就会使用ziplist(<7.0)或listpack(>=7.0)，否则就会使用(或升级到)hashtable。

ziplist/listpack存储

在前面ziplist结构中有讲ziplist的结构，ziplist存储Hash的示意图如下所示：

hset name Jack age 22使用ziplist存储原理图(redis<7.0时使用)

在前面listpack结构中有讲listpack的结构，listpack存储Hash的示意图如下所示：

hset name Jack age 22使用ziplist存储原理图(redis>=7.0时使用，因为从7.0开始全面使用listpack代替ziplist)

由以上两图可以看到，由于ziplist和listpack只是内部的数据结构略有不同，但它们在宏观上还是一个一个的条目(entry)紧挨着存储的，用ziplist或listpack来存储Hash时，是采用相邻两个entry之间一个key一个value的方式来存的。

hashtable存储

下图是执行Redis命令hset user name Jack age 22后的存储结构，此时redisObject的encoding为OBJ_ENCODING_HT(HT即HashTable)

结合前面Redis宏观结构可知，上图中的dictEntry只是整个Redis“键值对”中的一个字典项(一个键值对)，其中它的键是“user”，它的值是一个hash类型，有两对键值对，分别为{"name":"Jack", "age":22}，而哈希类型是用字典(dict)来存的，上图中整个虚线框起来的部分就是“值”，只不过这个值是一个“哈希类型”，它是由“字典结构”来存储的，但Redis的开发者把这种类型叫“OBJ_ENCODING_HT”类型(其中的HT就是HashTable)，而不叫“字典类型”。

注意：事实上按上图的数据量，它会使用ziplist(<7.0)或listpack(>=7.0)来存储，而不是字典来保存，但是数据量大的话图又画不下，所以我就直接这么画了，存储原理是一样的，只不过在数据量大的时候才会换成这种字典结构来保存(官方把这种用字典来保存的类型叫“hashtable”，即哈希表类型)。

源码分析：object.c-6.2第878行或object.c-7.0第1040行，这是objectComputeSize函数的一部分，用于计算一个RedisObject占用的字节数，从以下代码可知，当类型为OBJ_ENCODING_HT类型时，RedisObject的ptr指针指向的就是一个字典(dict)。

6.2版本，编码为ziplisto->encoding == OBJ_ENCODING_ZIPLIST

// 当RedisObject的类型o->type为OBJ_HASH，即hash类型时
} else if (o->type == OBJ_HASH) {
    // 判断encoding，如果是ziplist
    if (o->encoding == OBJ_ENCODING_ZIPLIST) {
        // 则使用ziplist的方式计算size
        asize = sizeof(*o)+(ziplistBlobLen(o->ptr));
        // 如果是hashtable类型OBJ_ENCODING_HT
    } else if (o->encoding == OBJ_ENCODING_HT) {
        // 则把o->prt赋值给d，这个d就是dict，就是字典，所以说
        // 当它是哈希类型时，RedisObject的ptr指针是指向字典的
        // 后面对变量“d”的操作，其实都是对字典的操作，说明“d”就是字典
        d = o->ptr;
        di = dictGetIterator(d);
        // sizeof(*o)就是RedisObject结构体的大小，sizeof(dict)是字典结构体大小
        // dictSlots(d)是ht[0]+ht[1]的**table指向的数组的元素个数，元素个数*每个元素一个
        // dictEntry，得出一个基本数字，但每个元素(这里一般叫bucket)中基本上都不可能只有一个
        // dictEntry，所以需要循环判断有没有下一个元素，如果有，还加上计算下一个dictEntry的
        // 大小(包括它自己占用的大小加上它指向的key和value占用的大小)
        // 按上图的结构，好像少计算了dictht的大小？其实并不是，因为dictht就是dict里的数组，所以
        // 计算dict的大小时，已经包含dictht的大小了，只不过dictht结构太多，直接画在dict里面不方便
        // 所以才分开画，但它们其实不是分开的
        asize = sizeof(*o)+sizeof(dict)+(sizeof(struct dictEntry*)*dictSlots(d));
        while((de = dictNext(di)) != NULL && samples < sample_size) {
            ele = dictGetKey(de);
            ele2 = dictGetVal(de);
            elesize += sdsZmallocSize(ele) + sdsZmallocSize(ele2);
            elesize += sizeof(struct dictEntry);
            samples++;
        }
        dictReleaseIterator(di);
        if (samples) asize += (double)elesize/samples*dictSize(d);
    } else {
        serverPanic("Unknown hash encoding");
    }
}

7.0版本，编码换成listpack了o->encoding == OBJ_ENCODING_LISTPACK

} else if (o->type == OBJ_HASH) {
    // 7.0的也一样，只不过这边改成了判断是listpack，其它代码都一样
    if (o->encoding == OBJ_ENCODING_LISTPACK) {
        asize = sizeof(*o)+zmalloc_size(o->ptr);
    } else if (o->encoding == OBJ_ENCODING_HT) {
        d = o->ptr;
        di = dictGetIterator(d);
        asize = sizeof(*o)+sizeof(dict)+(sizeof(struct dictEntry*)*dictSlots(d));
        while((de = dictNext(di)) != NULL && samples < sample_size) {
            ele = dictGetKey(de);
            ele2 = dictGetVal(de);
            elesize += sdsZmallocSize(ele) + sdsZmallocSize(ele2);
            elesize += sizeof(struct dictEntry);
            samples++;
        }
        dictReleaseIterator(di);
        if (samples) asize += (double)elesize/samples*dictSize(d);
    } else {
        serverPanic("Unknown hash encoding");
    }
}

集合(set)存储原理

集合底层用两个结构来存储：

1、当整个集合都是整数，并且集合元素个数少于512时，使用intset类型来存储；
2、当整个集合中有一个不是整数，或者虽然都是整数，但整个集合元素个数超过512个时，就会使用hashtable来存储。其实就是用字典结构来存，前面的内容已经说过，整个redis的键值对，是用字典结构来存储的，hash类型的value也是用字典结构来存储的，现在set类型也是用字典结构来存储，说明字典结构用的地方非常多。

这个512其实是可以配置的，在redid.conf-6.2或redid.conf-7.0中有set-max-intset-entries这个选项，它默认是512，但你可以改成其它值，不过建议还是别改。

sadd命令源码分析

在6.2版本的源码文件t_set.c中，有以下函数

void saddCommand(client *c) {
    robj *set;
    int j, added = 0;

    // 添加集合元素命令：sadd key1 ele1 ele2 ele3
    // argv就是从终端传过来的数组，该数组中的每个元素就是上边命令，从0开始，即argv[0]
    // 就是sadd,argv[1]就是key1,argv[2]就是ele1,argv[2]就是ele1argv[4]就是ele3
    // 所以这里查找argv[1]，其实就是找这个key之前是否存在
    set = lookupKeyWrite(c->db,c->argv[1]);
    // 如果找到了key，但是key中的类型不是集合类型，说明我们无法住这个key添加元素，直接return
    if (checkType(c,set,OBJ_SET)) return;

    // 如果set为NULL，说明我们设置的key不存在
    if (set == NULL) {
        // setTypeCreate，根据第一个元素的类型来判断要用什么底层结构来存储
        // 这个命令(c->argv[2]->ptr就是第一个元素的值)，返回一个redisObject
        set = setTypeCreate(c->argv[2]->ptr);
        // 向db中添加一个键值对，key就是argv[1]，value就是一个redisObject，就是前面的set变量
        dbAdd(c->db,c->argv[1],set);
    }

    // 循环添加元素，j=2是因为argv中下标2开始才是元素(下标0是sadd命令，下标1是key)
    for (j = 2; j < c->argc; j++) {
        // 然后一个一个往刚刚创建的set集合里添加元素，这个setTypeAdd函数会判断元素的类型，如果
        // 刚开始是intset，但是后来又遇到字符串，那么它会setTypeConvert转换成OBJ_ENCODING_HT
        // 类型(即hashtable类型，其实就是用字典结构来存储)
        if (setTypeAdd(set,c->argv[j]->ptr)) added++;
    }
    if (added) {
        signalModifiedKey(c,c->db,c->argv[1]);
        notifyKeyspaceEvent(NOTIFY_SET,"sadd",c->argv[1],c->db->id);
    }
    server.dirty += added;
    addReplyLongLong(c,added);
}

从以上函数注释可知，sadd添加一个元素，它会按第一个元素的类型创建一个底层结构，如果第一个元素类型是整数，那么它会创建intset类型的集合，否则会创建hashtable类型的集合，这个需要跟踪到setTypeCreate函数里才能知道

/* Factory method to return a set that *can* hold "value". When the object has
 * an integer-encodable value, an intset will be returned. Otherwise a regular
 * hash table. */
robj *setTypeCreate(sds value) {
    if (isSdsRepresentableAsLongLong(value,NULL) == C_OK)
        return createIntsetObject();
    return createSetObject();
}

另外一个就是初始元素类型是intset，并且，在添加元素的过程中又有字符串(或者虽然没有字符串，但元素数量已经超过set-max-intset-entries，默认是512)，那么就会执行setTypeConvert，把它转换为hashtable类型。

setTypeConvert函数是在setTypeAdd函数体中被调用的，以下是setTypeAdd函数中当原始集合为intset类型时的部分代码

else if (subject->encoding == OBJ_ENCODING_INTSET) {
    if (isSdsRepresentableAsLongLong(value,&llval) == C_OK) {
        uint8_t success = 0;
        subject->ptr = intsetAdd(subject->ptr,llval,&success);
        if (success) {
            /* Convert to regular set when the intset contains
             * too many entries. */
            size_t max_entries = server.set_max_intset_entries;
            /* limit to 1G entries due to intset internals. */
            if (max_entries >= 1<<30) max_entries = 1<<30;
            // 虽然存储的都是整型元素，但由于元素数量已经超过了配置文件中
            // “set-max-intset-entries”配置项设置的值，集合底层类型需要由intset转换为hashtable
            if (intsetLen(subject->ptr) > max_entries)
                setTypeConvert(subject,OBJ_ENCODING_HT);
            return 1;
        }
    } else {
        /* Failed to get integer from object, convert to regular set. */
        // 遇到了非整型元素(其实就是字符串)，需要把集合底层类型由intset转换为hashtable
        setTypeConvert(subject,OBJ_ENCODING_HT);

        /* The set *was* an intset and this value is not integer
         * encodable, so dictAdd should always work. */
        serverAssert(dictAdd(subject->ptr,sdsdup(value),NULL) == DICT_OK);
        return 1;
    }
}

intset存储集合

在intset.h文件第35行有intset结构体如下(6.2和7.0版本都一样，没有修改)

typedef struct intset {
    // 编码(其实就是数组元素类型)
    uint32_t encoding;
    // 数组长度
    uint32_t length;
    // 用于存储集合元素的数组，它的初始类型是int8_t，但后期会
    // 根据存储的数字的大小不同，会升级转换为能容纳更大数值的类型
    int8_t contents[];
} intset;

intset故名思义，int是整型，set是集合，intset就是整型集合的意思，所以它只能存储整型数字。

intset存储整数1,2,3,4的示意图

在6.2或7.0版本中，intset.c第45行有一个_intsetValueEncoding函数，用于根据当前需要存储的整数判断intset中的contents[]数组应该升级为什么类型

/* Return the required encoding for the provided value. */
static uint8_t _intsetValueEncoding(int64_t v) {
    // 如果值小于INT32的最小值或大于INT32的最大值，用INT32已经无法存储下，所以需要INT64来存
    if (v < INT32_MIN || v > INT32_MAX)
        return INTSET_ENC_INT64;
    // 如果值小于INT16_MIN的最小值或大于INT16_MIN的最大值，用INT16_MIN已经无法存储下，所以需要INT32来存
    else if (v < INT16_MIN || v > INT16_MAX)
        return INTSET_ENC_INT32;
    else
        // 否则就用INT16来存，这里的16,32,64都表示二进制位数
        return INTSET_ENC_INT16;
}

整数集合(intset)升级操作
如果原数组类型无法存储下新添加的元素，那么数组的类型就得升级为能容纳更大存储范围的类型，具体需要什么类型，前面所说的_intsetValueEncoding函数会根据要存储的值的大小来判断。注意，数组类型升级，代表它的每个元素都升级了，因为数组中的元素类型都是一样的。

比如刚开始集合中存储的是1,2,3三个整数，它们使用的是int16_t来存储(最低是int16_t，不会使用int8_t，见_intsetValueEncoding函数，那为什么结构体里不直接写int16_t呢？我觉得是在刚创建结构体变量的时候让它少占用内存吧)

现在我们向集合中加入一个65536，这个数16位已经存不下，必须升级为32位的，即int32_t类型，它会调用intsetUpgradeAndAdd函数，我们来看看这个函数

/* Upgrades the intset to a larger encoding and inserts the given integer. */
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    // 判断原函数的encoding(encoding就是contents[]数组的元素类型)
    uint8_t curenc = intrev32ifbe(is->encoding);
    // 根据要添加的value判断要用什么新的encoding
    uint8_t newenc = _intsetValueEncoding(value);
    // 获取原数组的长度intrev32ifbe()函数是用于判断是否要
    // 进行大端转小端，如果在小端系统中该函数是空的(条件编译)
    int length = intrev32ifbe(is->length);
    // 这个用于做排序，从小到大排(负数排在前面)
    int prepend = value < 0 ? 1 : 0;

    /* First set new encoding and resize */
    // 设置新的encoding
    is->encoding = intrev32ifbe(newenc);
    // 做resize操作，把数组的长度加1，它的本质，就是创建一个新的数组，数组元素类型是新的encoding
    // 类型，并且原数组的值会原封不动的拷贝到新数组中，最后释放原数组，这是realloc()函数的功劳，
    // 不需要手动做这个事情，反正最终就相当于是在原数组的基础上新增了一个元素(即数组长度+1)，并且
    // 把数组元素类型改为新的类型，当然数组的指针会变，毕竟它本质上是创建了新数组
    is = intsetResize(is,intrev32ifbe(is->length)+1);

    /* Upgrade back-to-front so we don't overwrite values.
     * Note that the "prepend" variable is used to make sure we have an empty
     * space at either the beginning or the end of the intset. */
    // 由于原数组元素已经原样拷贝到了新数组，所以需要把原数组中的元素升级为新数组的元素类型
    // 为了避免覆盖数据，它是从后往前一个一个来升级类型的，这个length+prepend是因为后面的
    // 代码时，负数是需要放在最前面的，所以这里必须+1(值为负数时，prepend=1)，最终的效果
    // 就是把所有原来元素转换为新类型后，数组的头部预留了一个空间，用来存储新增的负数
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));

    /* Set the value at the beginning or the end. */
    // 在这里判断，如果是负数就从前面插入，如果是正数就从后面插入
    if (prepend)
        _intsetSet(is,0,value);
    else
        _intsetSet(is,intrev32ifbe(is->length),value);
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    // 最终返回指针
    return is;
}

如下图，从int16_t升级到int32_t，总共新增了80位空间

先把原数据中的“3”升级为新类型(新类型一个元素占32位)，注意，如果新增的数是负数，它会被排在最前面，为了给它预留一个元素位置，这个“3”会被放到最后一个元素，而不是下图这个“倒数第二个元素”　

然后把原数据中的“2”升级为新类型(新类型一个元素占32位)

最后把元素“1”升级为新类型

类型升级完之后，再把新元素添加到数组中(看)

hashtable存储集合

由前面的sadd命令源码分析可知，Redis添加一个集合元素，是通过saddCommand函数来添加的，而saddCommand中真正添加集合元素的是setTypeAdd函数，如下所示

/* Add the specified value into a set.
 *
 * If the value was already member of the set, nothing is done and 0 is
 * returned, otherwise the new element is added and 1 is returned. */
int setTypeAdd(robj *subject, sds value) {
    long long llval;
    // subject就是传进来的redisObject
    if (subject->encoding == OBJ_ENCODING_HT) {
        // 由于encoding是OBJ_ENCODING_HT(即hashtable)，所以redisObject的ptr指向的
        // 就是字典(dict)，这里定义变量的时候，写成了“*ht”，容易让会误解为redisObject的
        // ptr指针指向的是dictht，但其实并不是，它指向的就是dict(字典)，而不是dictht(字典中的属性)
        dict *ht = subject->ptr;
        // 添加一个字典项(dictEntry)，注意dictAddRaw()第二个参数是key，但是这里为什么传value进去呢？
        // 因为它就是要把value作为key，存储到dictEntry的key中，当然dictAddRaw()函数并不会设置
        // key，传key进去只是为了通过key计算哈希槽位置。为什么要把value作为key呢？因为集合元素不
        // 像哈希，它是只有元素值，没有key，所以用哈希结构存储集合元素时，只会使用dictEntry的key，value为空
        dictEntry *de = dictAddRaw(ht,value,NULL);
        // 创建dictEntry成功(de就是dict Entry的两个首字母)
        if (de) {
            // 给刚刚创建的dictEntry设置key，可以看到，传进去的是value，说明是把value存到dictEntry的key中的，sdsdup()函数用于复制一份value(深拷贝)
            dictSetKey(ht,de,sdsdup(value));
            // 给刚刚创建的dictEntry设置value，可以看到，value被设置为NULL
            dictSetVal(ht,de,NULL);
            return 1;
        }
    }
// 后面部分由于与hashtable无关，我就没粘贴到这边，大家可以自己去看

通过上面的setTypeAdd函数可知，当编码为OBJ_ENCODING_HT(hashtable)时，它会使用字典结构来存储集合的元素(当然Redis中一般称为hashtable)，并且会把集合元素的值存到字典项的key位置，而值位置则为空，原因是集合元素都是整数或者字符串，而dictEntry的key刚好就是字符串或整数，所以存储起来非常方便。

hashtable存储集合元素示意图，可以看到，hashtable就是字典结构，它是使用字典项(dictEntry)的key来存储集合的元素的，而value则指向空

有序集合(zset)存储原理

有序集合是在无序集合的基础上添加了一个score值(有人叫它“分值”或“分数”)，然后根据score值的大小来排序。有序集合底层数据结构有两种：

当数据量比较少时，是使用ziplist(<7.0)或listpack(>=7.0)来存储的；
当数据量比较大时，是使用dict+skiplist来存储的(其中dict就是字典，前面Redis的字典讲过)，而skiplist是有序集合中非常重要的一个结构，后面会着重讲；

那么它是根据什么条件来判断是使用ziplist/listpack存储还是使用dict+skiplist来存储的呢？其实是根据redis.conf-6.2或redis.conf-7.0文件中的配置来确定的，配置如下所示

# 6.2
// 最大允许条目数128个
zset-max-ziplist-entries 128
// 单个条目最大字节数64
zset-max-ziplist-value 64

# 7.0
// 最大允许条目数128个
zset-max-listpack-entries 128
// 单个条目最大字节数64
zset-max-listpack-value 64

只要两个条件都满足，比如刚开始创建的时候，要存储的集合元素小于64字节，肯定就会使用ziplist或listpack。而随着ziplist或listpack中节点数的增加，当增加到128个时(其实只有64个元素，因为一个元素其实是一对值“score”和“ele”，它们会占用两个ziplist或listpack节点)，再继续增加，就会转换成dict+skiplist来存储，当然，就算没有达到128个元素，但如果其中一个元素大于64字节，它也会转换成dict+skiplist来存储。

zset结构体及创建obj

在6.2版本中，zset结构体在server.h的1017行

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

可以看到，zset结构体只有两个属性，一个dict(字典)，一个skiplist(跳跃表)，为什么呢？因为字典是用于根据值查分数的，此时元素值作为字典的“键”，score作为“值”，而skiplist是用于根据score来查找元素值的(可范围查找)，并且根据score进行排序。

当我们使用zadd命令添加一个有序集合时，它是调用zaddCommand()函数的

void zaddCommand(client *c) {
    zaddGenericCommand(c,ZADD_IN_NONE);
}

如上所示，zaddCommand()函数又调用了zaddGenericCommand()函数，在zaddGenericCommand()函数中我们可以找到以下这段代码

/* Lookup the key and create the sorted set if does not exist. */
// 查看要设置的key是否存在
zobj = lookupKeyWrite(c->db,key);
// 假设这个key存在，则能查找key对应的redisObject，然后查看它的encoding，
// 看是不是OBJ_ZSET(有序集合)，如果不是，那就goto cleanup，代表这个key
// 已经存在，无法设置，然后去清除之前所做的工作
if (checkType(c,zobj,OBJ_ZSET)) goto cleanup;
// 如果redisObject为空，说明这个key是不存在的，那就说明可以设置
if (zobj == NULL) {
    // 由于xx表示只更新存在的key，所以key不存在不符合条件，
    // 它会goto reply_to_client，其实就是返回0(表示设置了0个)
    if (xx) goto reply_to_client; /* No key + XX option: nothing to do. */

    // 一切都符合之后，如果发现redis.conf中的zset-max-ziplist-entries等于0或者
    // zset-max-ziplist-value小于第一个值的长度，则创建一个zset，这里为什么要拿第一
    // 个值的长度来判断呢？其实这里是大概判断，就是拿第一个元素来“碰运气”，万一第一个元素
    // 都大于配置文件中的zset-max-ziplist-value值，那么它直接就创建zset结构了，万一
    // 第一个元素小于zset-max-ziplist-value值，它创建了zsetZiplist，那也没关系，
    // 因为在后面添加的时候(代码没粘贴到这里)，它是会判断的，如果后面有其它元素不符合这条件
    // 它还是会转换成zset的
    if (server.zset_max_ziplist_entries == 0 ||
        server.zset_max_ziplist_value < sdslen(c->argv[scoreidx+1]->ptr))
    {
        // 创建一个OBJ_ZSET类型的redisObject对象来保存zset
        zobj = createZsetObject();
    } else {
        // 否则创建一个OBJ_ENCODING_ZIPLIST类型的redisObject对象来保存zset
        zobj = createZsetZiplistObject();
    }
    // 最后把这个key和redisObject加入到db中
    dbAdd(c->db,key,zobj);
}

以上这段代码主要描述了redis是怎样创建用来存储有序集合元素的redisObject对象的。

ziplist或listpack存储

根据前面zset结构体及创建obj可知，它会创建一个zset结构体类型的obj或ziplist类型的obj(当然如果是7.0以上版本，ziplist会被listpack代替)，这里我们就来讲讲当使用ziplist或listpack类型来存储有序集合元素时，是怎么存的！

以下为ziplist存储有序集合结构图，它就是一个val和一个score为一组，注意score是位于val之后的

以下为listpack存储有序集合结构图，它跟ziplist没什么区别，也是一个val跟着一个score，score位于val之后

以下是向集合中插入一个元素的源码，6.2版本的是在t_zset.c第1034行

unsigned char *zzlInsertAt(unsigned char *zl, unsigned char *eptr, sds ele, double score) {
    unsigned char *sptr;
    char scorebuf[128];
    int scorelen;
    size_t offset;

    scorelen = d2string(scorebuf,sizeof(scorebuf),score);
    // 如果指针为空，那就直接push，因为这是个空ziplist，还没有添加任何元素
    if (eptr == NULL) {
        // 先push集合元素
        zl = ziplistPush(zl,(unsigned char*)ele,sdslen(ele),ZIPLIST_TAIL);
        // 再push该元素对应的score值
        zl = ziplistPush(zl,(unsigned char*)scorebuf,scorelen,ZIPLIST_TAIL);
    } else {
        // 否则，如果eptr不为空，则插入到eptr指定的位置中，这个
        // eptr指定的位置是调用该函数的上级函数计算好排序的位置
        /* Keep offset relative to zl, as it might be re-allocated. */
        offset = eptr-zl;
        // 先插入集合元素
        zl = ziplistInsert(zl,eptr,(unsigned char*)ele,sdslen(ele));
        eptr = zl+offset;

        /* Insert score after the element. */
        serverAssert((sptr = ziplistNext(zl,eptr)) != NULL);
        // 再插入该元素对应的score值
        zl = ziplistInsert(zl,sptr,(unsigned char*)scorebuf,scorelen);
    }
    return zl;
}

eptr是element ptr，元素指针，从上面的代码可知，score是存储在元素(ele)之后的。对于listpack，存储结构也是一样的，都是把score放在ele之后，这里就不讲listpack的代码了。

skiplist(跳跃表)原理

由前面zset结构体及创建obj可知，一个zset结构是由一个dict(词典)和一个skiplist(跳跃表)构成的，dict在前面Redis的字典已经说过了，所以这里来说一下skiplist。

skiplist，中文叫跳跃表(简称跳表)是一个多层的有序链表，“跳跃”的意思是，本来正常链表是一个一个往前查找的，但跳跃表可以“跳过n个节点”往前找，因为跳跃表有多层指针。

正常的双向链表

我们知道，这样的链表查找数据都是需要从头开始，一个一个往后遍历，直到找到需要的数据为止(或者遍历到最后还是没找到，说明没有这个数据)，所以双向链表的时间复杂度是O(n)，同样，在插入、删除、修改数据时，也是要用同样的方法查找(就算是插入，也是要查找到合适的插入位置，因为需要根据数字的大小排序)，所以时间复杂度也是O(n)。

双层链表

如下图所示，我们增加了一层指针，这层指针都跳过一个节点，直接指向下一个节点。

比如我想找37，如果按前面正常的双向链表，需要查7次，即分别对比3,7,11,19,22,26,37共7个数，直到第7次才找到37；
但是如果用上图所示的双层链表，我们可以先从上层查找，直接找7，不是37且比37小，继续下一个节点19，不是37且比37小,继续下一个节点26，不是37且比37小，然后降层(降到下一层，即第一层)查找，然后由于在上一层的时候，知道26比37小，所以降层后的方向就是往前找(而不是往回找)，然后就直接找到37了，整个过程查了4次，比前面的7次少了三次。

三层链表

还是要找37，从最上层(第三层)开始，直接找到19，发现19比37小，且本层没有节点了，降到第二层继续往前找，找到26小于37，且本层没有节点了，降层继续往前找，于是找到了37，这样只用了3次就找到了37；
那如果找11呢？直接找到19，发现19大于11，降层往回找，找到7，发现7小于11，所以需要往前找，可是刚刚就是从19那儿回来的，如果往前找就是19了，所以需要降层，然后再往前找，于是找到了11，这个过程用了3次，虽然直接在第一层找也是3次，但只是碰巧而已，大多数时候还是能节省次数的，特别是数据量大的时候，因为画图画不下太多节点，所以大家只能发挥想象力；
如果找26，那么只需要19找一次，然后降层往前找(因为前面知道19小于26，所以降层后需要往前找，而不是往回找)，然后就直接找到26，整个过程查找了2次，如果直接查需要6次，可见多层链表查找速度比单层双向链表效率高很多；

上面的多层链表，其实就是“跳跃表(skiplist)”，当然以上多层链表存在一个问题：每两层之间，上层的节点数刚好是下层的一半，拿三层的来说：

第三层有1个节点：19；
第二层有2个节点：7,26;
第一层有4个节点：3,11,22,37。

由于这个规律，查找的时候其实就相当于二分查找，但这个规律也造成了另外的问题：如果新插入或删除一个节点，那么必然会“打乱”这种上下层之间节点数1:2的关系，要维持这个关系，就必须把新插入的节点及其后面的所有节点重新调整，这样会造成插入和删除效率低下。

跳跃表(skiplist)为了避免这个问题，它不要求上下两层之间的节点数有严格的对应关系，而是为每个节点随机出一个层数，当然这个随机是有概率的，就是越高的层级出现的概率越小。

以下是创建一个链表的模拟过程，由于全部图放在一起太长了，所以我每两个一起放一张图

插入19和7

插入3和37

插入11和26

为什么不按从小到大的顺序插入呢？因为实际数据是随机的，不可能每次需要插入的数据刚好比前一个大。

skiplist代码解析

对于6.2版本，在server.h文件的第1000行到1015行中有两个结构体，分别是zskiplistNode,zskiplist

/* ZSETs use a specialized version of Skiplists */
// 跳跃表节点结构体
typedef struct zskiplistNode {
    // 集合元素
    sds ele;
    // 集合score值
    double score;
    // 后退指针
    struct zskiplistNode *backward;
    // 层结构体
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 前进的跨度，跳跃就是这里在跳，就是说一个链表，本来我要查找下个元素，是要挨个往下查找的，
        // 但是现在它可以跳过n-1个元素，直接查找第n个，当span=1时，就是查找下一个，span=2表示
        // 查找它下边第二个(中间跳过了一个)，span=3表示查找它下边第3个(跳过了2个)
        unsigned long span;
    } level[];
} zskiplistNode;

// 跳跃表结构体
typedef struct zskiplist {
    // 跳跃表的头节点和尾节点指针
    struct zskiplistNode *header, *tail;
    // 跳跃表长度，就是表中节点(zskiplistNode)数量
    unsigned long length;
    // 跳跃表中层数最大的的节点的层数
    int level;
} zskiplist;

创建一个跳跃表(skiplist)：跳跃表有4个属性，分别为头尾指针(header和tail)，以及length(节点数，不包括头节点)和level(所有节点中的最高层级数，不包括头节点)

zskiplist *zslCreate(void) {
    int j;
    zskiplist *zsl;
    // 分配内存，并让zsl指针指向它，这块内存就用于存储跳跃表的属性
    zsl = zmalloc(sizeof(*zsl));
    // 层级先设置为1
    zsl->level = 1;
    // 长度初始化为0，因为一个节点都没有，而length是用于表示跳跃表节点数的(头节点是不算在内的，因为它不存储实际数据)
    zsl->length = 0;
    // 创建一个header节点，跳跃表中的header节点是不存储实际数据的，所以它的第二个参数“score”为0，
    // 第三个参数“ele”为NULL，header节点的层数都是最大层数(redis6.2中ZSKIPLIST_MAXLEVEL是32，
    // 可在server.h文件中搜索ZSKIPLIST_MAXLEVEL查看它的值)
    zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
    for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
        // 循环把每层的forward指针初始化为NULL
        // 把每层的span值初始化为0
        zsl->header->level[j].forward = NULL;
        zsl->header->level[j].span = 0;
    }
    // 把header的backward指针初始化为NULL(事实上该值一直为NULL，因为头节点没有前一个节点)
    zsl->header->backward = NULL;
    // 把跳跃表的尾节点指针置为NULL，因为还没有创建尾节点
    zsl->tail = NULL;
    // 返回这个跳跃表
    return zsl;
}

注意：跳跃表的头结点不存储实际节点数据(即集合元素)，它只是用于维护节点关系，它永远具有最高层级(Redis6.2中最高层级是32级)。由于它不存储具体数据，所以它不能被算入length(跳跃表节点数)中，又由于它永远具有最高层级，所以跳跃表的level值不能把它算在内，因为level值是所有节点中的最高层级，而头节点的层级永远比其它层级高(或者与其它层级相等)，所以如果把它算在内，那么level值就会永远等于最高层级(即32)，如果这样的话，这个level属性就没什么意义了。

创建一个跳跃表(skiplist)节点：

zskiplistNode *zslCreateNode(int level, double score, sds ele) {
    // 使用zmalloc分配一块内存用来存储zskiplistNode类型的数据(即存储一个跳跃表节点)
    // 注意：sizeof(*zn)是不包括它最后一个数组的大小的。当结构体有2个或2个以上属性，并且
    // 有一个是数组，并且数组放在最后时，这个数组就叫“柔性数组”，它只是一个占位符，sizeof
    // 计算结构体占用的空间时，是不会计算这个数组的，因为它根本没有占用任何空间，它是空的。
    // 所以才需要level*sizeof(struct zskiplistLevel)来计算
    zskiplistNode *zn =
        zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
    // 把score值和ele值都赋值给对应的属性
    zn->score = score;
    zn->ele = ele;
    return zn;
}

跳跃表插入一个节点：是使用zslInsert函数来插入的

// zsl就是zSkipList，意思是向*zsl这个跳跃表中插入一个集合元素ele以及它的score
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
    // 需要更新指针的节点(假设新节点刚好插入到几个节点的中间，而它的层级又比较高，那么它前面的所有节点本
    // 来是指向原来的节点的，现在被它插入了，就变成全部指向它，然后再由它来指向之前前面那些节点指向的节
    // 点)，现在这个update数组就是用来保存这些需要更新forward指针的节点
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    // rank数组用于保存排位(也叫“等级”)
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    int i, level;

    // 断言score不是NaN(NaN就是not a number，不是一个数字，熟悉js的应该知道)
    serverAssert(!isnan(score));

    // 从header节点开始遍历
    x = zsl->header;
    // 从最高层往下开始遍历(level数组下标从0开始，最高层数组下标就是“层数-1”)
    for (i = zsl->level-1; i >= 0; i--) {
        /* store rank that is crossed to reach the insert position */
        // 设置当前层rank的初始值，如果i等于最高层(zsl->level-1表示最高层数组下标)，
        // 则rank为0，因为i等于最高层肯定是第一次循环，第一次循环初始值肯定就是0。而
        // 后续的循环中，当前层rank的初始值就必须等于上一层循环到最后的rank值，因为这
        // 个rank值其实是把逐层符合插入的节点的span值全部加起来的一个值
        rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];

        // 上边的for循环是用于在“层”之间循环的，它是从上到下的方向，
        // 而这个while是遍历当前层的节点(未必是所有)，是从左到右的方向
        // 由于节点一开始是header，而header是不存实际值的，所以需要检查forward(下一个节点)
        // 1. 如果当前节点forward指针不为NULL(即存在下一个节点)
        while (x->level[i].forward &&
                // 2. 下一个节点的score值小于要插入的score值
                (x->level[i].forward->score < score ||
                    // 3. 如果两个score值相等但下一个节点的ele元
                    // 素小于要插入的ele(ele可以是整数或字符串)
                    // 如果是字符串，则根据它们的编码排序，比如a排在b前面
                    (x->level[i].forward->score == score &&
                    sdscmp(x->level[i].forward->ele,ele) < 0)))
        {
            // 上边while循环里的条件都在确认一个问题：新节点是否能插入
            // 到forward节点的下一个节点，如果能插入，那就进入到这里

            // 该层排位就要叠加当前节点当前层的span值，每个节点每层都有一个span值，用于表示它指向
            // 下一个节点跨越了多少节点，被指向的节点也算在内，也就是说跨越1个节点，其实就是span=2，
            // 跨越2个节点span=3，因为指向的那个节点虽然没有被“跨越”，但也是计算在内的
            rank[i] += x->level[i].span;
            // 节点移动到该层的下一个节点，然后继续循环，最终rank[i]就是该层所有符合插入的位置的span之和
            x = x->level[i].forward;
        }
        // 当while循环结束时，就会执行这句，while循环为什么会结束？可能是当前层已经没有节点了，
        // 也可能是当前层已经遍历到某个节点，它的分值大你要插入的分值大，它的元素(字符串)也比你
        // 要插入的元素(字符串)大，使得需要插入的节点不能插入到该节点后面，所以需要结束循环，降
        // 到下一层，而这个update[i] = x是在降层之前执行的，它保存的就是降层之前，上一层遍历到
        // 的最后一个符合插入条件的节点(注意未必是上一层最后一个，而是最后一个符合插入条件的节点)
        update[i] = x;
    }
    /* we assume the element is not already inside, since we allow duplicated
     * scores, reinserting the same element should never happen since the
     * caller of zslInsert() should test in the hash table if the element is
     * already inside or not. */
    // 随机生成一个level层级，它一定会在1-32之间，并且越高的层级生成的概率越低
    level = zslRandomLevel();
    // 如果随机生成的层级(level)比当前的最高层级(zsl->level)大
    if (level > zsl->level) {
        // 则从之前的最高层级(即zsl->level-1)的上一层(即zsl->level)开始往上循环，
        // 一直循环到新的最高层(level层)，这是因为节点插入后，需要把原来所有的节点各
        // 层的指针指向这个新插入进来的节点，而他们之前指向的节点则由新插入的节点来指向
        // 不过对于之前的最高层往上，其实只有header的各层指针要更新，因为其它层都没那么高
        for (i = zsl->level; i < level; i++) {
            rank[i] = 0;
            // 需要更新的节点为header节点从“旧最高层”到“新最高层”的每一层
            update[i] = zsl->header;
            // 由于前提条件是插入的层级高于之前任何层级，所以从之前最高层级的上一层(zsl->level)
            // 到level之间，它们的中间都不会有任何节点，header中这些层级会直接指向NULL，相当于
            // 跨过了所有节点，所以它们的length就等于zsl->length
            update[i]->level[i].span = zsl->length;
        }
        // 最终把当前跳跃表的level值(当前跳跃表中具有最多层的节点的层数)更新为新的level值
        zsl->level = level;
    }
    // 创建一个节点，用于保存集合元素分值(score)及集合元素本身(ele)
    x = zslCreateNode(level,score,ele);
    // 从该节点的第0层开始
    for (i = 0; i < level; i++) {
        // 循环，让每一层的forward指针都指向前面保存的需要更新的节点(update数组)对应
        // 层级的forward指针，为什么呢？因为update数组中的节点的forward指针即将要指
        // 向这个新插入的节点，所以需要让这个新插入的节点指向它们之前指向的节点
        x->level[i].forward = update[i]->level[i].forward;
        // 然后把“要更新的节点”每层的forward指针都指向新节点
        update[i]->level[i].forward = x;

        /* update span covered by update[i] as x is inserted here */
        // 这两句是用于调整新节点插入后，新节点本身每一层的span和由于被新节点插入了，
        // 新节点前面那些要更新的节点的span也改变了，所以要更新，至于具体为什么是
        // 这样计算，需要结合画图才能理解了
        x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
        update[i]->level[i].span = (rank[0] - rank[i]) + 1;
    }

    /* increment span for untouched levels */
    // 循环，把level层到最高层之间的所有需要update的节点的span都加1(因为新
    // 增了一个节点)，因为这些层都比新插入的层高，所以它们的span值直接加1就行
    for (i = level; i < zsl->level; i++) {
        update[i]->level[i].span++;
    }

    // 处理backward指针，如果update[0]是头节点，那么说明新节点是插入到头节点后面，
    // 理论上它的backward指针就是头节点，但实际上，因为头节点只用于维持数据结构，
    // 并不存实际元素值，所以这个backward指针就是null
    x->backward = (update[0] == zsl->header) ? NULL : update[0];

    // 判断第0层是否有forward指针，如果有，说明前面一定有节点，那么新节点的下一个节点的backward指针就是新节点自己
    if (x->level[0].forward)
        x->level[0].forward->backward = x;
    else // 否则，如果新节点没有下一个节点，那说明新节点自己就是尾结点，于是把zsl的tail指针指向它
        zsl->tail = x;
    // 由于添加了一个节点，所以zsl的长度加1
    zsl->length++;
    // 最终返回新节点的指针
    return x;
}

skiplist结构图

上面skiplist(跳跃表)原理中的图并没有画出redis的完整结构，看过前面skiplist代码解析后，我们再来看一下真正的skiplist结构图。

skiplist结构图

zskiplist的header和tail指针分别指向跳跃表的头尾节点；
zskiplist的length为整个跳跃表节点数(头节点不计算在内，因为头节点不存储实际数据，只用于维护节点指针)；
zskiplist的level为所有节点中最高层级数(头节点不计算在内，因为头节点总是具有最高层级，在server.h文件中查找ZSKIPLIST_MAXLEVEL，在redis6.2中它的值为32)；
所有节点都有且只有一个backward指针，该指针用于指向上一个节点；
头节点的backward指针为NULL，因为它前面没有节点了；
第一个节点的backward指针也为NULL，因为头节点不存储实际信息，所以相当于第一个节点前面也没有节点了；
所有节点的每一层都有一个forward指针，用于指向下一个节点的相同层(如果下一个节点没有相同层，则会跨过它一下往下找具有相同层的节点)，尾节点的foward指针都指向NULL，因为尾节点已经是最后一个，它下边已经没有节点可以指向了；
每一层的跨度(span值)计算方式为：从该层的下一个节点到forward指向的节点(包含被指向的节点)一共有几个节点，则跨度就是几；
所有节点(除头节点外)的score值都是直接存储在该节点的score属性中的；
所有节点(除头节点外)的元素值(即ele)都是一个指针，都指向一个sds字符串(也就是说，集合的元素只能是字符串，数字属于特殊字符串，sds存储的时候会做相应特殊处理)；
所有节点都按score值由小到大排序，如果score值相同，则比较元素(ele)本身，就算元素是字符串也是可以比较的，比如a会在排在b前面(比较它们的ASCII码大小)。

为什么不用B树？

There are a few reasons:

1) They are not very memory intensive. It’s up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.
1) 它们(skiplist)不是很占用内存。这基本上取决于你。改变节点的概率参数(p)来让节点获得给定数量的层级，可以让skiplist的内存占用小于B树。
2) A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.
2) 一个有序列表经常被使用ZRANGE和ZREVRANGE来获取一个范围的元素(rev是reverse的意思)，即将跳跃表作为链表遍历，性能不亚于其它平衡树。
3) They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.
3) 跳跃表的实现和调试更加简单，比如说多亏了skiplist够简单，我(redis作者)收到了一个补丁，该补丁可让skiplist的zrank命令的时间复杂度达到O(logN)。

总结：

1、skiplist不是很占用内存，通过调节层级概率参数，可让它的内存占用小于B树；
2、有序集合可能面对大量的范围查询操作，skiplist易于做范围查找，性能不亚于B树；
3、代码实现起来比B树更简单，这样更多人可参与到redis的开发，给redis贡献代码。

zset结构图

前面zset结构体及创建obj中说过，当有序集合使用zset结构体来存储时，它是由一个dict(字典)+一个skiplist(跳跃表)来存的。

下图是一个相对比较完整的zset存储结构图(点击图片可放大)

以上结构为执行zadd test 0.1 red 0.4 blue 0.5 green后的zset存储结构(当然实际上它会使用ziplist存储，因为数据量少，但为了说明结构，我们画成了zset)；
由Redis宏观结构可知，上图中的dictEntry，其实只是整个redis键值对字典中某个字典条目(dictEntry)，它的key为“test”，value为一个redisObject(zset类型)；
redisObject的ptr指针指向一个zset结构体，zset再指向一个skiplist和一个dict；
dict(字典)使用集合元素(red,blue,green)作为key，使用它们的score值作为value(图中score值我直接写在dictEntry里了，但大家要明白，事实上它也是指向sds字符串结构的，但是空间不太够我就没画)；
skiplist使用集合元素(red,blue,green)作为节点元素值，而score值则用于排序；
skiplist和dict共用一份sds字符串；

key过期和内存淘汰策略

key过期策略

定时过期：每个设置过期时间的key都需要创建一个定时器，到过期时间就会立即清除。该策略可以立即清除过期的数据，对内存很友好；但是会占用大量的CPU资源去处理过期的数据，从而影响缓存的响应时间和吞吐量；
惰性过期：只有当访问一个key时，才会判断该key是否已过期，过期则清除。该策略可以最大化地节省CPU资源，却对内存非常不友好。极端情况可能出现大量的过期key没有再次被访问，从而不会被清除，占用大量内存。
定期过期：每隔一定的时间，会扫描一定数量的数据库的expires字典中一定数量的key，并清除其中已过期的key。该策略是前两者的一个折中方案。通过调整定时扫描的时间间隔和每次扫描的限定耗时，可以在不同情况下使得CPU和内存资源达到最优的平衡效果。

Redis实际上选用了选用惰性过期+定期过期两种方式。

内存淘汰策略

Redis的内存淘汰策略是指在Redis的用于缓存的内存不足时，怎么处理新写入的且需要申请额外空间的数据。

redis中有以下内存淘汰策略，在6.2版本中，是在redis.conf文件的第996行中

volatile-lru -> 当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，移除最近最少使用的key；
allkeys-lru -> 当内存不足以容纳新写入数据时，在整个键空间中，移除最近最少使用的key；
volatile-lfu -> 当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，移除最不常使用的key；
allkeys-lfu -> 当内存不足以容纳新写入数据时，在键空间中，移除最近最不经常使用的key；
volatile-random -> 当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，随机移除某个key；
allkeys-random -> 当内存不足以容纳新写入数据时，在整个键空间中，随机移除某个key；
volatile-ttl -> 当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，移除最接近过期时间的key； (即TTL生存时间比较小的key)；
noeviction -> (这是默认值)，不移除任何数据，直接返回内存已满，无法写入的错误。

持久化

Redis持久化有两种方式：RDB快照持久化和AOF持久化，这两种方式可以同时使用。

RDB快照持久化

快照(snapshot)持久化，在6.2版本中是在redis.conf和362行开始

比如如下配置

# 每900秒内至少有1个key有变化，触发bgsave，执行一次快照备份
save 900 1
# 每300秒内至少有10个key有变化，触发bgsave，执行一次快照备份
save 300 10
# 每60秒内至少有1万个key有变化，触发bgsave，执行一次快照备份
save 60 10000

bgsave就是background save，它会fork一个子进程来做快照备份工作，备份期间的设置值的指令不会被执行，而是会被放到缓存中，等bgsave完成后，才会把缓存中的指令逐个执行。

快照持久化方式，如果遇到突然宕机，丢失的数据会比较多，当然具体参数也得靠你调，比如60秒1w个key有变化，那如果60秒内只变化了9999个key，然后宕机了，那你就丢了这9999次改变，当然你也可以调成60秒有1000个key变化，这样如果60秒内有999个key变化然后宕机，那么你丢失的就是999个key的改变，频率太低万一出现问题丢的数据就多，频率太高会对性能有影响。

另外，如果总数据量大，备份会比较耗时。

AOF持久化

aof是append only file的缩写，意思是只往一个文件中添加(追加，不会覆盖)。相关配置在6.2版本中是在redis.conf的第1234行。

它有三种模式

# 每次都追加，这个会影响性能，一般不会用这种方式
# appendfsync always

# 每秒钟追加一次，如果突然宕机，会丢失1秒钟的数据(这一秒钟)
appendfsync everysec

# 让系统来决定什么时候追加(缓冲区满了就会flush到文件中)，如果突然宕机，不知道确定会丢失多少数据
# appendfsync no

常见问题

Redis最多能存几个key？

理论上可以处理最多达2³²=4,294,967,296(约42.9亿个key)，但应该没有人测试过，官方测试过的数据是2.5亿个key(只是测试了这么多，但不代表不能继续添加)。

对于hash, list, set, zset，每个key内部最多可存2³²个元素，所以总体来说，基本上可以认为是无限制的，因为在到达限制之前，你的服务器内存已经不够用了。

这个答案可以在官方的faq中找到：What is the maximum number of keys a single Redis instance can hold? What is the maximum number of elements in a Hash, List, Set, and Sorted Set?。

参考：
github-redis6.2-源码, github-redis7.0-源码
 redis内部数据结构详解(推荐)
Redis内部数据结构详解(1)——dict
Redis设计原理
 Redis数据结构之字典（dict）-推荐
 Redis底层是怎样保存一个key和value的？
Redis设计与实现
 把Redis当作队列来用，真的合适吗？
Redis几种数据类型及应用场景
 Redis只能做缓存？太out了！
分布式面试【Redis】
一文带你快速搞懂动态字符串SDS，面试不再懵逼
 深入了解一下Redis的内存模型
 为了拿捏 Redis 数据结构，我画了 40 张图（完整版）
Redis7.0代码分析总结之：底层数据结构 listpack 实现原理
 Redis Quicklist: Do you even list?
二.Redis 数据结构(下) quicklist、listpack 。 by TEnth丶
 Redis内部数据结构详解(4)——ziplist
Redis常用数据类型及其存储结构(源码篇)
redis-02 五种类型底层数据结构
 redis quicklist剖析
 Redis数据结构（一）SDS
Redis 源码解析 7：五大数据类型之列表
 【Redis系列2】Redis字符串对象之SDS(简单动态字符串)实现原理分析
 Redis数据结构详解（2）-redis中的字典dict
The underlying implementation of the Redis data structure
redis 一组kv实际内存占用计算
 Redis源码分析之key过期
 深入分析redis之listpack，取代ziplist?
Redis 7内存优化–1.简化dict数据结构-推荐
 美团针对Redis Rehash机制的探索和实践
 懵了~ 面试官Redis夺命连环20问！
面试准备 — Redis 跳跃表
 跳表
 redis zset底层数据结构
 《我们一起进大厂》系列-Redis哨兵、持久化、主从、手撕LRU
Redis位图(bitmap)介绍和在签到场景的应用
 Redis 核心剖析：为什么这么“快”的秘密

打赏

IMOOWI	起航天空
萌新	一冉再
凹凸实验室	风雪之隅
Mengkang's land	ChenShuai
歪麦博客	烂泥行天下
朱双印个人日志	Docker系列教程
骏马金龙

双向链表

双链表结构体

双链表的优缺点

ziplist

ziplist定义

ziplist结构

ziplist条目结构

ziplist条目encoding

zlentry结构体

ziplist存储实例

ziplist存在的问题

quickList

quicklist存储结构示意图

quistList结构体

quicklistNode结构体

quicklistEntry结构体

quicklistLZF结构体

quicklist极端情况

listpack

listpack的定义

listpack结构

encoding-type

element-tot-len

listpack存字符串示例

encoding-type

element-tot-len

查找上一个元素源码分析

Hash类型存储原理

控制参数

ziplist/listpack存储

hashtable存储

集合(set)存储原理

sadd命令源码分析

intset存储集合

hashtable存储集合

有序集合(zset)存储原理

zset结构体及创建obj

ziplist或listpack存储

skiplist(跳跃表)原理

skiplist代码解析

skiplist结构图

为什么不用B树？

zset结构图

key过期和内存淘汰策略

key过期策略

内存淘汰策略

持久化

RDB快照持久化

AOF持久化

常见问题

Redis最多能存几个key？

©版权声明

扫码在手机查看 iPhone请用自带相机扫 安卓用UC/QQ浏览器扫

扫码在手机查看

iPhone请用自带相机扫

安卓用UC/QQ浏览器扫