redis zset,ZipList底层结构
ZipList 压缩列表
Redis是基于内存的nosql，有些场景下为了节省内存redis会用“时间”换“空间”。
ziplist就是很典型的例子。
ziplist是list键,hash键以及zset键的底层实现之一(3.0之后list键已经不直接用ziplist和linkedlist作为底层实现了,取而代之的是quicklist)
ziplist是redis list,hash,zset的底层实现结构之一,当list,hash,zset中节点数量较少,并且存储的大多节点为小整数形,较短的字符串时,Redis就会使用ziplist作为list,hash,zset底层实现
ziplist可以压缩空间
原理
一如既往，关于 ziplist 的定义和实现还是放在一对文件中，分别是 ziplist.h 和 ziplist.c。在 ziplist.c 文件的头部有着这么一段注释介绍什么是 ziplist。
ziplist是一个经过特殊编码的双向链表,旨在提高内存效率.它存储字符串和整数值,其中证书编码为实际整数而不是一系列字符.它允许在O(1)时间内在列表的任一一侧进行推送和弹出操作.但是由于每个操作都需要重新分配ziplist使用的内存,因此实际复杂性与ziplist使用的内存量有关
从这段话得到：对于不同的数据类型有着不同的编码方式，理解为会对数据进行压缩，从而达到减少内存使用的目的。但是随着存储的 value 数据级增加，使用 ziplist 所付出的代价也随之增加。
ziplit是一个特殊的双向链表,不想普通的链表使用前后指针关联在一起,它是存储在连续内存上的.
zlbytes: 32 位无符号整型，记录 ziplist 整个结构体的占用空间大小。当然了也包括 zlbytes 本身。这个结构有个很大的用处，就是当需要修改 ziplist 时候不需要遍历即可知道其本身的大小。 这个 SDS 中记录字符串的长度有相似之处，这些好的设计往往在平时的开发中可以采纳一下。
zltail: 32 位无符号整型, 记录整个 ziplist 中最后一个 entry 的偏移量。所以在尾部进行 POP 操作时候不需要先遍历一次。
zllen: 16 位无符号整型, 记录 entry 的数量， 所以只能表示 2^16。但是 Redis 作了特殊的处理：当实体数超过 2^16 ,该值被固定为 2^16 - 1。 所以这种时候要知道所有实体的数量就必须要遍历整个结构了。
entry: 真正存数据的结构。
zlend: 8 位无符号整型, 固定为 255 (0xFF)。为 ziplist 的结束标识。
entry
每个entry都包含俩条信息的元数据为前缀
第一元数据用来存储前一个entry的长度,以便从后向前遍历列表
第二元数据是entry的编码形式.用来表示entry类型,整数或字符串,在字符串情况下,还表示字符串的有效长度
typedef struct zlentry {
unsigned int prevrawlensize; /* 用于编码前一个节点字节长度*/
unsigned int prevrawlen;
unsigned int lensize; /* 用于编码此节点类型/长度的字节。
例如，字符串有1、2或5个字节标题。
整数总是使用一个字节。
*/
unsigned int len; /* 用于表示节点实际的字节。
对于字符串，这只是字符串长度
而对于整数，它是1、2、3、4、8或
0,具体取决于数字范围。
*/
unsigned int headersize; /* prevrawlensize + lensize. */
unsigned char encoding; /* 设置为ZIP_STR_*或ZIP_INT_*，具体取决于节点编码。*/
unsigned char *p; /* 第一个节点的地址指针，prev-entry-len */
} zlentry;所以一个完整的 ziplist 是这样存储的：
prelen
记录前一个entry的长度.若前一个entry长度小于254,则用一个字节的8位无符号整数来表示
若前一个 entry 长度大于等于 254，则使用 5 个字节来表示。第 1 个字节固定为 254 (FE) 作为标识，剩余 4 字节则用来表示前一个 entry 的实际大小。
1. 前一个 entry 大小不超过 253。
<prevlen from 0 to 253> <encoding> <entry>
2. 前一个 entry 大小超过 253。
0xFE <4 bytes unsigned little endian prevlen> <encoding> <entry>encoding编码
entry 的编码字段取决于具体值的内容，分为字符串、数字两种类型单独处理。
1. 当 entry 是字符串时，有 3 种编码方式。编码第 1 个字节的前 2 位将保存用于存储字符串长度的编码类型，后面是字符串的实际长度。
1. 长度小于或等于 63 字节（6 位）的字符串值。 “pppppp”表示无符号的 6 位数据长度。
|00pppppp| - 1 byte
2. 长度小于或等于 16383 字节（14 位）的字符串值。14 位的数据采用 big endian 存储。
big endian 是一种字节序方式，有Little-Endian、Big-Endian两种。
|01pppppp|qqqqqqqq| - 2 bytes
3. 长度大于或等于 16384 字节的字符串值。
采用 big endian 存储且可表示的字符串长度最大2^32-1，所以第一个字节没有用到，所以低6位没有用，所以都是0。
|10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 5 bytes 当 entry 是整数时，有 6 种编码方式。前 2 位都固定为 1，接下来的 2 位用于指定将在此标头后存储哪种类型的整数。
与 ziplist 标头一样，所有整数都以 Little-Endian 序表示，即使此代码是在 Big-Endian 系统中编译的。
1. 整数编码为 int16_t（2 字节）。
|11000000| - 3 bytes
2. 整数编码为int32_t（4个字节）。
|11010000| - 5 bytes
3. 整数编码为 int64_t（8 字节）。
|11100000| - 9 bytes
4. 整数编码为24位带符号（3个字节）。
|11110000| - 4 bytes
5. 整数编码为 8 位有符号（1 字节）。
|11111110| - 2 bytes
6. 0到12的无符号整数。编码后的值实际上是1到13，因为0000和1111不能用，所以要从编码后的4位值中减去1才能得到正确的值。
|1111xxxx| - (with xxxx between 0001 and 1101) immediate 4 bit integer结尾编码标识
1. 表示 ziplist 结尾的标识。
|11111111|更新
连锁更新是ziplist一个比较大的缺点,也是V7.0倍listpack所替代的重要原因
ziplist 在更新或者新增时候，如空间不够则需要对整个列表进行重新分配。当新插入的元素较大时，可能会导致后续元素的 prevlen 占用空间都发生变化，从而引起「连锁更新」问题，导致每个元素的空间都要重新分配，造成访问压缩列表性能的下降。
ziplist 节点的 prevlen 属性会根据前一个节点的长度进行不同的空间大小分配：
- 如果前一个节点的长度小于 254 字节，那么 prevlen 属性需要用 1 字节的空间来保存这个长度值。
- 如果前一个节点的长度大于等于 254 字节，那么 prevlen 属性需要用 5 字节的空间来保存这个长度值。
假设有这样的一个 ziplist，每个节点都是等于 253 字节的。新增了一个大于等于 254 字节的新节点，由于之前的节点 prevlen 长度是 1 个字节。
为了要记录新增节点的长度所以需要对节点 1 进行扩展，由于节点 1 本身就是 253 字节，再加上扩展为 5 字节的 pervlen 则长度超过了 254 字节，这时候下一个节点又要进行扩展了。噩梦就开始了。
ziplist 为了节省内存，采用了紧凑的连续存储。所以在修改操作下并不能像一般的链表那么容易，需要从新分配新的内存，然后复制到新的空间。
ziplist 是一个双向链表，可以在时间复杂度为 O(1) 从下头部、尾部进行 pop 或 push。
新增或更新元素可能会出现连锁更新现象。
不能保存过多的元素，否则查询效率就会降低。
其实使用中并没有直接指定是否使用这种数据结构，但是可以设置何种情况下使用它。可以在 Redis 的配置文件中进行设置。
hash-max-ziplist-entries：hash 类型元素数量超过指定数据后时候。使用 hash 存储， 否则使用压缩表。
hash-max-ziplist-value： hash 类型元素长度超过指定数据后时候。 使用 hash 存储，否则使用压缩链表。
zset-max-ziplist-entries：zset 类型 压缩列表 ziplist 最大限制元素数。超过指定值将会使用跳表 skiplist + dict 来存储。
zset-max-ziplist-value：set 类型 压缩列表 ziplist 最大限制大小。超过指定将会使用跳表 skiplist+dict 来存储。
list-max-ziplist-value: list 保存的所有字符串元素的长度都小于64字节。
list-max-ziplist-entries：list 保存的元素数量小于512个。
listpack(紧凑列表)
listpack 的出现是用来代替 ziplist 的。
redis在后续版本也采用了quicklist(快速链表),通过控制quicklistNode结构里的压缩列表的大小或者元素个数,来减少连锁更新带来的影响,但并没有完全解决连锁更新的问题,因为quicklistnode还是用了压缩列表来保存元素
所以redis5.0出现了listpack,目的是替代压缩列表,其最大特点是,listpack中每个节点不再包含前一个节点的长度,压缩列表每个节点正因为需要保存前一个节点的长度,就会有连锁的更新隐患
鉴入 Redis7.0 已经将 listpack 完整替代 ziplist,所以本文的源码是 7.0版本。
listpack 最大特点是 listpack 中每个节点不再包含前一个节点的长度，所以直接对比 listpack 和 ziplist 的结构设计。
ziplist entry
typedef struct zlentry {
unsigned int prevrawlensize; /* 用于编码前一个节点字节长度*/
unsigned int prevrawlen;
unsigned int lensize; /* 用于编码此节点类型/长度的字节。
例如，字符串有1、2或5个字节标题。
整数总是使用一个字节。
*/
unsigned int len; /* 用于表示节点实际的字节。
对于字符串，这只是字符串长度
而对于整数，它是1、2、3、4、8或
0,具体取决于数字范围。
*/
unsigned int headersize; /* prevrawlensize + lensize. */
unsigned char encoding; /* 设置为ZIP_STR_*或ZIP_INT_*，具体取决于节点编码。*/
unsigned char *p; /* 第一个节点的地址指针，prev-entry-len */
} zlentry;可以明显看到 prevrawlensize 用于记录前一个节点的大小。
Listpackentry
typedef struct {
/* 当使用string时，它具有长度(slen)。 */
unsigned char *sval;
uint32_t slen;
/* 当使用integer时，“sval”为 NULL，lval 保存该值。*/
long long lval;
} listpackEntry;不同于zipEntry,listpackEnrty中len记录的是当前entry的长度,而非上一个entry长度。listpackEntry 中可存储的为字符串或整型。
- 当存储的为字符串，slen 记录大小。调用函数 lpInsertString() 。
- 当存储的为整形，lval 记录实际值，sval 字段为 NULL。调用函数 lpInsertInteger()。
图文
下面的代码展示了如何创建一个新的 listpack。
unsigned char *lpNew(size_t capacity) {
unsigned char *lp = lp_malloc(capacity > LP_HDR_SIZE+1 ? capacity : LP_HDR_SIZE+1);
if (lp == NULL) return NULL;
lpSetTotalBytes(lp,LP_HDR_SIZE+1);
lpSetNumElements(lp,0);
lp[LP_HDR_SIZE] = LP_EOF;
return lp;
}结合 lpNew() 和 listpackEntry ，不难得到 listpack 的内存结构图。
encoding ：定义该元素的编码类型，会对不同长度的整数和字符串进行编码。
data：实际存放的数据。
len：encoding + data 的总长度，len 代表当前节点的回朔起始地址长度的偏移量。
从上图不难得到这样的结论：listpack 没有记录前一个节点长度，只记录当前节点的长度，从而避免了压缩列表的连锁更新问题。
总结
区别
listpack中每个节点不再包含前一个节点的长度,避免连锁更新的隐患发生
- listpack 相对于 ziplist，没有了指向末尾节点地址的偏移量，解决 ziplist 内存长度限制的问题。但一个 listpack 最大内存使用不能超过 1GB。
参数变动
新增 list-max-listpack-size 代替 list-max-ziplist-size。
新增 hash-max-listpack-entries 代替 hash-max-ziplist-entries。
新增 hash-max-listpack-value 代替 hash-max-ziplist-value。
新增 zset-max-listpack-entries 代替 zset-max-ziplist-entries。
新增 zset-max-listpack-value 代替 zset-max-ziplist-value。
skiplist跳表
概念
skiplist本质上也是一种查找结构，用于解决算法中的查找问题（Searching），即根据给定的key，快速查到它所在的位置（或者对应的value）
一般用于解决查找问题的数据结构分为两个大类：一个是基于各种平衡树，一个是基于哈希表。但skiplist却比较特殊，它没法归属到这两大类里面
在这样一个链表中，如果我们要查找某个数据，那么需要从头开始逐个进行比较，直到找到包含数据的那个节点，或者找到第一个比给定数据大的节点为止（没找到）。也就是说，时间复杂度为O(n)。同样，当我们要插入新数据的时候，也要经历同样的查找过程，从而确定插入位置
假如我们每相邻两个节点增加一个指针，让指针指向下下个节点，如下图：
这样所有新增加的指针连成了一个新的链表，但它包含的节点个数只有原来的一半（上图中是7, 19, 26）。现在当我们想查找数据的时候，可以先沿着这个新链表进行查找。当碰到比待查数据大的节点时，再回到原来的链表中进行查找。比如，我们想查找23，查找的路径是沿着下图中标红的指针所指向的方向进行的：
在这个查找的过程中,由于新增加的指针,我们不需要与每个节点逐个进行比较了.需要比较的节点大概只有原来的一半.利用同样的方式,我们可以在上层新产生的链表上，继续为每相邻的两个节点增加一个指针，从而产生第三层链表。如下图：
在这个新的三层链表结构上，如果我们还是查找23，那么沿着最上层链表首先要比较的是19，发现23比19大，接下来我们就知道只需要到19的后面去继续查找，从而一下子跳过了19前面的所有节点。可以想象，当链表足够长的时候，这种多层链表的查找方式能让我们跳过很多下层节点，大大加快查找的速度
skiplist正是受这种多层链表的想法的启发而设计出来的。实际上，按照上面生成链表的方式，上面每一层链表的节点个数，是下面一层的节点个数的一半，这样查找过程就非常类似于一个二分查找，使得查找的时间复杂度可以降低到O(log n)。但是，这种方法在插入数据的时候有很大的问题。新插入一个节点之后，就会打乱上下相邻两层链表上节点个数严格的2:1的对应关系。*如果要维持这种对应关系，就必须把新插入的节点后面的所有节点（也包括新插入的节点）重新进行调整，这会让时间复杂度重新*退化成O(n)。删除数据也有同样的问题
解决方式
skiplist为了避免这一个问题,它不要求上下相邻之间的节点个数有严格的对应关系,而是为每个节点随机出一个层数(level).比如,一个节点随机出的层数是3,那么久把它链入到第一层和第三层链链表中
上面skiplist的创建和插入过程可以看出,每一个节点的层数(level)是随机出来的,而且新插入一个节点不会影响其它节点的层数.因此插入操作只需要修改插入节点后的指针,而不需要对很多节点都进行调整.这就降低了插入操作的复杂度.实际上,这就是skiplist很重要的特性,折让它哎插入的性能上明显优于平衡树的方案.
根据上图中的skiplist结构，我们很容易理解这种数据结构的名字的由来。skiplist，翻译成中文，可以翻译成“跳表”或“跳跃表”，指的就是除了最下面第1层链表之外，它会产生若干层稀疏的链表，这些链表里面的指针故意跳过了一些节点（而且越高层的链表跳过的节点越多）。这就使得我们在查找数据的时候能够先在高层的链表中进行查找，然后逐层降低，最终降到第1层链表来精确地确定数据位置。在这个过程中，我们跳过了一些节点，从而也就加快了查找速度
刚创建的这个skiplist总共包含4层链表，现在假设我们在它里面依然查找23，下图给出了查找路径：
需要注意的是,前面演示的各个节点的插入过程,实际上在插入之前也要先经历一个类似查找的过程,在确定插入位置后,在完成插入操作
至此，skiplist的查找和插入操作，我们已经很清楚了。而删除操作与插入操作类似，我们也很容易想象出来。这些操作我们也应该能很容易地用代码实现出来
当然,实际应用中的skiplist每个节点应该包含key和value俩部分.前面的描述中我们没有具体区分key和value,实际列表中是按照key进行排序的,查找过程中也是根据key在比较
zset
zset是redis提供的一个非常特别的数据结构,常用作排行榜功能,以用户id为value,关注时间或者分数作为score进行排序.与其他数据结构类似,zset也有俩种不同的实现,分别是ziplist和skiplist .ziplist前面已经介绍过了,具体使用哪种结构进行存储,规则如下
zipList满足以下俩个条件
- 键值对数量少于128个
- 每个元素的长度小于64字节
skipList:不满足以上俩个条件时使用跳表,组合了hash和skipList
- hash用来存储value到score的映射,这样就可以在o(1)时间内找到value对应的分数
- skip按照从小到大的顺序存储分数
- skiplist每个元素都是[score,value]对
使用zipList的示意图如下所示
使用跳表时
