本文首发于公众号：Hunter后端
原文链接：Redis对象的数据结构及其底层实现原理汇总

当我们被问到 Redis 中有什么数据结构，或者说数据类型，我们可能会说有字符串、列表、哈希、集合、有序集合。

其实这几种数据类型在 Redis 中都由对象构成，而且是两个对象，一个键对象，一个值对象。

在这些数据类型中，它们的键都是字符串对象，而值可以是前面说的字符串对象、列表对象、哈希对象、集合对象、有序集合对象中的一种，这个取决于键值对的数据类型。

而在 Redis 中，这些对象都有其更底层的实现方式，也就是说这一篇笔记我们要介绍的，更底层的数据结构，而且不同的 Redis 版本有不一样的数据结构，最基础的数据结构包括简单动态字符串、字典、跳跃表、整数集合等，

接下来我们先介绍一下 Redis 中对象的构成，然后介绍一下不同 Redis 版本中每个对象所使用的的底层数据结构，之后再逐个介绍这些数据结构的实现原理，以下是本篇笔记的目录：

1. Redis 对象的介绍
2. 不同版本的 Redis 对象的数据结构
3. 数据结构的原理介绍
4. 对象的数据结构选择原理

注意：本篇文章的主体框架内容是基于书籍《Redis设计与实现》进行描述的，部分过时内容都基于网上查询的相应资料与最新版本进行了对齐，如有其他疏漏，还望指正。

1、Redis 对象的介绍

举一个例子，当我们设置一个字符串类型的数据：

set msg "hello world"

这样，我们就创建了两个对象，且两个都是字符串对象，因为键值对的 key 和 value 都是字符串。

如果我们创建了一个列表数据，那么 key 是字符串对象，而值 value 是列表对象。

在 Redis 中，每个对象都由一个 redisObject 结构来表示：

typedef struct redisObject{
    //类型
    unsigned type:4;
    
    //编码
    unsigned encoding:4;
    
    //指向底层实现数据结构的指针
    void *ptr
    
    //...
} robj;

type

在上面的结构中，type 指的是这个对象的类型，比如我们创建了一个列表数据，那么这个数据的 key 就是一个字符串对象，由这个结构里的 type 来指定，这个数据的 value 就是一个列表对象，也是由 type 来进行指定区分。

但是，当我们想要知道一条数据的数据类型是字符串、列表、哈希、集合、有序集合的哪一种时，我们常常是需要知道的这条数据的 value 的类型，一般也是指的 value 的类型，因为数据的 key 的类型总是字符串对象。

一条数据的值对象类型的获取我们可以用 TYPE 命令来操作：

TYPE msg

TYPE 类型的值输出就是我们那五种类型：string、list、hash、set、zset

encoding

encoding 指的是这个对象底层数据结构使用的编码。

一个对象在不同的情况下的编码及底层数据结构可能是不一样的，比如对于字符串对象，它的编码包括 int，embstr，raw 这三种，但后两种的底层结构其实都是简单动态字符串（SDS），不过它们的底层使用方式略有不同，这个我们在下一节再介绍。

获取对象的值的编码使用 OBJECT ENCODING 命令：

OBJECT ENCODING msg

ptr

ptr 则是作为指针指向的是对象的底层数据结构地址。

上面这些查看对象底层编码的命令，我们会在介绍完各个底层数据结构之后根据存储的不同数据类型进行使用。

2、不同版本的 Redis 对象的数据结构

Redis 3.2 版本以前

在 Redis 3.2 版本以前，每个对象对应的编码，及底层数据结构如下：

字符串对象

编码（OBJECT ENCODING输出结果）	底层数据结构
int	整数
embstr	embstr编码的SDS
raw	SDS

列表对象

编码（OBJECT ENCODING输出结果）	底层数据结构
ziplist	压缩列表
linkedlist	双向链表

哈希对象

编码（OBJECT ENCODING输出结果）	底层数据结构
ziplist	压缩列表
hashtable	字典

集合对象

编码（OBJECT ENCODING输出结果）	底层数据结构
intset	整数集合
hashtable	字典

有序集合对象

编码（OBJECT ENCODING输出结果）	底层数据结构
ziplist	压缩列表
skiplist	跳跃表

Redis 3.2 版本

而在 3.2 版本，主要对列表对象的底层实现做了修改，由 quicklist 构成底层实现，quicklist 实际上是 linkedlist 和 ziplist 的混合结构。

列表对象

编码（OBJECT ENCODING输出结果）	底层数据结构
quicklist	快速列表

Redis 5.1 之后版本

在 Redis 5.1 版本，引入了新的数据结构 listpack，6.x 版本作为过渡阶段，并且在 7.0 版本，listpack 已经完全替换了 ziplist，成为了哈希对象、有序集合对象的底层数据结构的原有实现之一，更改如下：

哈希对象

编码（OBJECT ENCODING输出结果）	底层数据结构
listpack	listpack
hashtable	字典

有序集合对象

编码（OBJECT ENCODING输出结果）	底层数据结构
listpack	listpack
skiplist	跳跃表

而且 quicklist 也变成了 linkedlist 和 listpack 的混合结构

3、数据结构的原理介绍

在这一章节将逐步介绍 Redis 中各个数据类型的底层数据结构

1. SDS

SDS，simple dynamic string，即简单动态字符串

SDS 在 Redis 2.9 版本中数据结构如下：

struct sdshdr {
    int len;
    int free;
    char buf[];
};

在这个结构中，len 表示 buf 数组中已使用字节的数量，free 表示 buf 数组中未使用字节的数量，buf 则表示是一个 char 类型的数组。

Redis 没有复用 C字符串，有以下几个方面的考虑和优点。

1) 常数复杂度获取字符串长度

C字符串并不记录自身的长度信息，如果要获取C字符串的长度，必须遍历整个字符串然后计数。

SDS 结构中有 len 属性记录 SDS 本身的长度，可以直接获取。

2) 杜绝缓冲区溢出

因为 C字符串并不记录自身的长度信息，在执行某些操作，比如拼接字符串的时候，并不会自动查询是否拥有足够内存，那么这个操作可能就会造成缓冲区溢出的问题

而 SDS 执行相应的字符串修改时，其 API 会先检查 SDS 的空间是否需求，不满足则会进行扩展，这个空间分配策略也就是下面要讲的

3) 减少修改字符串带来的内存重分配次数

C字符串每次进行字符串修改时，程序都需要手动进行内存重分配的操作，而 SDS 通过空间预分配和惰性空间释放两种策略对此进行了优化

空间预分配

当 SDS API 对一个 SDS 进行修改并需要对 SDS 进行空间扩展时，程序不仅会为 SDS 分配修改所需要的空间，还会为其分配额外的未使用空间

如果修改之后，SDS 的长度，也就是结构中的 len 属性小于 1MB，那么程序会额外分配同样大小的未使用空间，这个时候，len 属性和 free 属性将相同

如果修改之后，SDS 的长度，也就是结构中的 len 属性大于等于 1MB，那么程序会额外分配 1MB 的未使用空间

惰性空间释放

当需要对SDS保存的字符串进行缩短时，程序并不会重新分配内存来回收多出来的字节，而是会使用 free 属性将这些字节记录下来，以备后面使用

4) 二进制安全

C字符串保存的字符结尾都是以空字符结尾，所以字符串中间不能包含空字符，否则程序读入空字符的时候就会被认为是字符串结尾，因此C字符串只能保存文本数据，不能保存图片、音频等这样的二进制数据

而 SDS 的 API 都是以处理二进制的方式来处理 SDS 中存放在 buf 里的数据，程序不会对数据做任何限制、过滤，所以 SDS 的 API 都是二进制安全的

SDS 使用 len 属性值而不是空字符串来判断字符串是否结束

5) 兼容C字符串函数

虽然SDS的API都是二进制安全的，但是仍然遵循C字符串以空字符结尾的惯例，而且在为 buf 数组分配空间的时候总是会多分配一个字节来容纳这个空字符，所以保存文本数据的 SDS 可以重用一部分C中的函数

以下是 SDS 与 C字符串区别的总结：

C字符串	SDS
获取字符串长度复杂度为 O(N)	获取字符串长度复杂度为O(1)
API是不安全的，可能会造成缓冲区溢出	API是安全的，不会造成缓冲区溢出
修改字符串长度N次必须执行N次内存重分配	修改长度N次最多需要执行N次内存重分配
只能保存文本数据	可以保存文本或者二进制数据
可以使用<string.h>库中函数	可以使用部分

在之后的的 Redis 版本对 SDS 的结构有过更新，将 free 属性换成了 alloc，这个属性表示的意思是分配的空间长度。和之前的 free 属性比较，其关系是 alloc = free + len

2. 双向链表

C 语言没有链表这个结构，所以 Redis 自己设计了一个链表数据结构。

在 Redis 中，链表节点的结构拥有指向前置节点和后置节点的属性。

链表结构则包含链表表头节点、表尾节点、节点长度等属性，便于快速获取链表相关信息。

双向链表是列表对象的底层实现之一，什么情况下使用双向链表作为列表对象的底层实现我们之后再介绍。

以下是链表节点的结构：

typedef struct listNode{
    // 前置节点
    struct listNode *prev;
    
    // 后置节点 
    struct listNode *next;
    
    // 节点值
    struct *value;

}listNode;

在链表节点中，拥有前置节点和后置节点的指针构成双向的链表。

以下是链表的结构：

typedef struct list{
    // 表头节点
    listNode *head;
    
    // 表尾节点
    listNode *tail;
    
    // 链表包含的节点数量
    unsigned long len;
    
    ...
}list;

在链表结构中，有表头节点和表尾节点可快速定位到链表的头部和尾部，以及用有 len 属性表示链表包含的节点数量。

3. 压缩列表

在 Redis 3.2 版本之前，压缩列表是列表对象、哈希对象、有序集合对象的的底层实现之一。

因为压缩列表本身结构上的一些缺陷，压缩列表这个结构被替换了，但是压缩列表结构本身有一些可取之处，并且替换它的新结构 listpack 与之很相似，所以我们这里还是介绍一下压缩列表的结构和存储

压缩列表是 Redis 为了节约内存而开发的，由一个连续内存块组成的顺序型数据结构。

它的组成结构如下：

| zlbytes | zltail | zllen | entry1 | entry2 | ... | entryN | zlend |

压缩列表的英文名是 ziplist，所以它的属性都是 zl 开头。

1) 列表属性介绍

zlbytes

zlbytes 长度为 4 字节，记录整个压缩列表占用的内存字节数

zltail

zltail 长度为 4 字节，记录压缩列表最后一个节点，也就是我们结构示例中的 entryN 到 zlbytes 的地址之间的偏移量。

zllen

zllen 长度为 2 字节，记录的是压缩列表包含的节点数量，也就是结构中的 N。

zlend

zlend 长度为 1 字节，它的值为 0xFF（十进制 255），用于标记压缩列表的末端。

2) 压缩列表节点属性介绍

对于每一个 entry 节点，也就是压缩列表中的元素节点，它的结构示意如下：

| previous_entry_length | encoding | content |

previous_entry_length

previous_entry_length 属性记录的是压缩列表中前一个节点的长度

previous_entry_length 属性本身的长度可以是 1 字节或者 5 字节

如果前一节点的长度小于 254 字节，那么 previous_entry_length 属性的长度为 1 字节，前一个节点的长度保存在这个字节里

如果前一节点的长度大于等于 254 字节，那么 previous_entry_length 属性的长度为 5 字节，第一个字节被设置成 0xFE（也就是 254），之后的四个字节用于前一节点的长度。

通过 previous_entry_length 属性，我们可以通过当前节点的地址和 previous_entry_length 属性，计算出前一个节点的起始地址，压缩列表的从表尾道表头的遍历操作就是使用这个原理一个节点一个节点往前回溯实现的。

encoding

encoding 属性记录了节点的 content 属性所保存数据的类型以及长度。

encoding 的值如果是一字节长，且值的最高位以 11 开头，那么表示是整数编码，表示 content 属性保存着整数值。

encoding 的值为 一字节、两字节、五字节长，且值得最高位为 00、01、10 则表示是字节数组编码

content

content 属性保存的是节点的值，可以是一个字节数组或者整数，值的类型和长度由节点的 encoding 属性决定。

3) 连锁更新

在压缩列表的节点属性中，previous_entry_length 属性的长度是根据前一节点的长度来进行赋值的，如果前一节点的长度小于 254 字节，那么下一节点的 previous_entry_length 属性长度为 1 字节，如果前一节点的长度大于等于 254 字节，那么下一节点的 previous_entry_length 属性为 5 字节。

那么在这种情况下，就存在一种较为极端的情况，那就是压缩列表中每个节点的长度都在 250 - 253 字节之间，这时候，如果在表头插入一个长度大于等于 254 字节的节点，那么相对应的第二个节点的 previous_entry_length 的长度就要从 1 字节变为 4 字节，那么该节点的整体长度就大于等于 254 字节。

依此类推，压缩列表的每一个节点的长度都会产生连锁反应，长度都会逐个变成大于等于 254 字节长度，程序就需要不断地对压缩列表执行空间重分配的操作。

Redis 将这种在特殊情况下产生的连续多次空间扩展操作称为连锁更新。

除了新增节点这种情况，还有一种删除节点也可能造成连锁更新的情况，比如有这么几个节点，big 节点的长度大于等于 254 字节，small 节点长度小于254 字节，e1 到 eN 的节点长度都在 250-253 字节之间。

| zlbytes | zltail | zllen | big | small | entry1 | entry2 | ... | entryN | zlend |

这时候，删除 small 节点，entry1 节点的前节点的长度就会从 250-253 变成大于等于 254，因此 entry1 节点的 previous_entry_length 长度就会变成 5 字节，entry1 整体长度就会大于等于 254 字节，依次之后每个节点都会这样产生连锁更新。

尽管连锁更新的复杂度较高，但它真正造成性能问题的几率是很低的：

首先，压缩列表里要恰好有多个连续的、长度介于 250-253 字节之间的节点，连锁反应才有可能被引发

其次，即使出现连锁更新，但只要被更新的节点数量不多，就不会对性能造成任何影响，比如对只拥有三五个节点的压缩列表进行连锁更新。

4）压缩列表缺点

压缩列表虽然能节约内存，但仍然存在一些缺点：

• 需要通过遍历操作来查找节点，元素过多时会造成查询效率低下
• 对压缩列表节点进行新增或者修改时，可能会造成连锁更新的问题

4. 字典

字典在 Redis 中应用相当广泛，在介绍字典之前，先来介绍一下字典、哈希表、哈希表节点的几个概念。

Redis 中，字典是用哈希表及额外的一些属性实现的，而哈希表则由多个哈希表节点构成，我们引用基础命令笔记中介绍的哈希命令中的一个例子来做介绍，一个哈希结构如下：

{
    "student":
        {
            "name": "Hunter",
            "number": "00001",
            "rank": 1
        }
}

其中，student: {} 的底层就是一个哈希表

student 下的 {"name": "Hunter"}、{"number": "00001"}、{"rank": 1} 就是组成哈希表的各个哈希表节点

对于 Redis，哈希表和哈希表节点两个数据结构就可以实现我们对 key-value 数据的操作，但是随着哈希表保存的键值对增加或者减少，我们就需要对哈希表进行扩展或者收缩操作，因此就额外引入了字典结构来做一些额外的辅助操作，具体的实现我们接下来介绍。

1) 哈希表

哈希表结构如下：

typedef struct dictht{
    // 哈希表数组
    dictEntry **table;
    
    // 哈希表大小
    unsigned long size;
    
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;
    
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;

在上面的结构中，table 属性是一个数组，每个元素都是一个指向哈希表节点的指针

size 属性记录了哈希表的大小，也就是 table 数组的大小

used 属性记录了记录了哈希表目前已有节点（键值对）的数量

sizemask 属性总是等于 size - 1，这个属性和哈希值一起决定一个键该被放到 table 数组中的第几个索引上。

现在我们模拟一遍往 student 哈希表里插入一条数据 {"name": "Hunter"} 的过程。

首先，假设我们的哈希表数组的大小为 4（这个大小会随着哈希表里的键值对数量增加或者减少有自动的调整，也就是 rehash 的操作，我们后面再介绍），也就是 size 属性为 4，那么 sizemask = 4 - 1 = 3。

我们要往 table 里插入 {"name": "Hunter"} 这条数据，而哈希表 table 属性有四个长度，应该放在第几个位置呢，就需要使用这个键值对的键，也就是 name 通过哈希函数得到它的哈希值，这个哈希值是一个数值，假设得到的哈希值是 8，那么接下来就需要将 8 与 sizemask 也就是 3 进行 与 操作，得到的结果是 0，那么将这条数据放在 table 数组的索引 0，也就是第一个位置。

至于根据键值对的键获取哈希值使用的哈希函数，Redis 里使用的是 Murmurhash 算法，有兴趣的可以去了解一下。

2) 哈希表节点

哈希表节点的结构如下：

typedef struct dictEntry{
    // 键
    void *key;
    
    // 值
    union{
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    
    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

在这个结构中，key 属性保存着键值对中的键，v 属性则保存着键值对的值，其中值可以是一个指针，或者是一个 uint64_t 整数，也可以是一个 int64_t 整数。

假设我们还是使用 {"name": "Hunter"} 为例，那么这个 key 就是指向的就是 name，val 指向的是 Hunter。

next 属性则是指向另一个哈希表节点的指针，因为不同的键在经过哈希函数处理之后得到的值在跟 sizemask 进行与操作之后得到的索引位置可能相同，所以哈希表节点通过链地址法来解决键冲突的问题。

3) 字典

字典的结构如下：

typedef struct dict{
    // 类型特定函数
    dictType *type;
    
    // 私有数据
    void *privdata;
    
    // 哈希表
    dictht ht[2];
    
    // rehash 索引
    int rehashidx;
}

type 属性和 privdata 属性是针对不同类型的键值对，为创建多态字典而设置的。

ht 属性则是一个包含了两个哈希表的数组，一般情况下只使用 ht[0] 哈希表，ht[1] 只有在 rehash，也就是对哈希表进行进行扩展或者收缩的时候才会使用。

rehashidx 属性记录了 rehash 目前的进度，如果目前没有进行 rehash 操作，那么它的值就是 -1。

4) 哈希算法和键冲突

如何将一个新的键值对插入到哈希表中，这个过程我们在介绍哈希表的属性的时候就已经模拟过这个流程了。

当多个键值对通过哈希算法被分配到哈希表的同一个索引上，我们就称这些键发生了冲突。

为了解决冲突，前面在介绍哈希表节点的结构的时候，介绍了哈希表节点有一个 next 属性，指向的下一个哈希表节点，因此哈希表节点就用使用 next 属性将不同的哈希表节点连接起来。

因为哈希表节点组成的链表没有指向链表表尾的指针，所以为了避免遍历节点到链表尾部，程序会将新节点添加到链表的表头位置，排在其他节点的前面。

5) rehash

前面介绍过，当哈希表保存的键值对数量太多或者太少，会需要对哈希表的大小进行相应的扩展或者收缩。

用于衡量哈希表的大小与键值对的数量之间的关系有一个计算关系，称为哈希表的负载因子（load factor）。

负载因子的计算公式如下：

load_factor = ht[0].used / ht[0].size

即哈希表已保存的节点数量 / 哈希表大小。

哈希表的扩展与收缩

当以下条件任意一个被满足时，程序自动开始对哈希表进行扩展操作：

• 负载因子大于等于1，且服务器没有在执行 BGSAVE 或者 BGREWRITEAOF 命令时
• 负载因子大于等于5，且服务器正在执行 BGSAVE 或者 BGREWRITEAOF 命令时

BGSAVE 和 BGREWRITEAOF 是 Redis 进行持久化操作的两个后台执行的命令。

当哈希表的负载因子小于 0.1 时，程序自动开始对哈希表执行收缩操作。

rehash 步骤

接下来介绍一下 Redis 的字典结构进行 rehash 的步骤。

a. 首先，需要用到字典结构中的 ht 数组的第二个，也就是 ht[1]，需要为其分配空间。

分配的空间大小取决于是扩展还是收缩操作，以及 ht[0] 当前包含的键值对数量，也就是 ht[0].used 属性的值。

如果是扩展操作，我们将需要 ht[1] 的空间大小设置为 x，那么 x 的应该是 2 的 n 次方，且是大于等于 ht[0].used * 2 的第一个 2 的 n 次方。

我们假设当前 ht[0].used 的值为 9，那么大于等于 9 * 2 = 18 的最小的一个 2 的 n 次方的值是 32，也就是 2 的 5 次方，所以我们要将其 ht[1] 的大小设置为 32，也就是哈希表结构里的 size 属性。

如果是收缩操作，我们需要将 ht[1] 的空间大小设置为 x，这个 x 应该是 2 的 n 次方，且是大于等于 ht[0].used 的第一个 2 的 n 次方。

假设 ht[0].used 的值为 9，那么大于等于 9 的最小的 2 的次方的值是 16，也就是 2 的 4 次方。

b. 分配好 ht[1] 的空间之后，将保存在 ht[0] 的所有键值对 rehash 到 ht[1] 上，rehash 的操作就是逐个重新计算哈希表节点的键的哈希值和对应的索引值，然后将键值对放置到 ht[1] 哈希表对应的位置上。

c. 将 ht[0] 上的所有键值对都迁移到 ht[1] 之后，此时 ht[0] 就变成了空表，释放 ht[0]，将 ht[1] 设置为 ht[0]，并在 ht[1] 新创建一个空哈希表，为下一次 rehash 作准备。

6) 渐进式 rehash

上面的 rehash 的操作并不是一次性、集中式完成的，而是分多次、渐进式完成的。

因为当 ht[0] 的键值对数量小的时候可以瞬间完成，但是当键值对数量很大，比如几百万，几千万个键值对，一次性进行迁移操作可能导致 Redis 一段时间内停止服务。

因此 rehash 的操作是分多次、渐进式地将 ht[0] 里面的键值对慢慢地 rehash 到 ht[1]。

以下是其详细步骤：

1. 为 ht[1] 分配空间，让字典同时持有 ht[0] 和 ht[1] 两个哈希表
2. 在字典中维持索引计数器变量 rehashidx，将其设置为 0，表示 rehash 工作正式开始
3. 在 rehash 期间，每次对字典进行添加、删除、查找、或者更新操作时，程序除了执行指定的操作，还会顺带将 ht[0] 上对应索引位置上的哈希表节点都 rehash 到 ht[1]
4. 随着字典操作的不断执行，在某个时间点，ht[0] 的所有键值对都会被 rehash 到 ht[1]，这时候 rehashidx 属性的值设为 -1，表示 rehash 操作已经完成

在进行渐进式 rehash 的过程中，哈希表节点，也就是键值对会在两个哈希表中分布，所以字典的删除、查找、更新操作会在两个哈希表上进行。

比如如果在字典查找一个键，在 ht[0] 里没有查找到，那么会继续在 ht[1] 里查找。

另外，在渐进式 rehash 期间，新添加到字典的键值对一律会被保存到 ht[1] 里面，ht[0] 则不再进行任何添加操作，这个措施保证了 ht[0] 包含的键值对数量只减不增，并随着 rehash 操作的执行最终变成空表。

5. 整数集合

整数集（intset）是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis 就会使用整数集合作为集合键的底层实现。

整数集合可以保存类型为 int16_t，int32_t，int64_t 的整数值，并且保证集合中不会出现重复元素。

以下是整数集合的结构：

typedef struct intset{
    // 编码方式
    uint32_t encoding;
    
    // 集合包含的元素数量
    uint_32_t length;
    
    // 保存元素的数组
    int8_t contents[];
}

其中，encoding 属性的值为 INTSET_ENC_INT16，INTSET_ENC_INT32，INTSET_ENC_INT64，分别表示 contents 数组里存储的整数类型是 int16_t，int32_t，int64_t。

当 encoding 的值为 INTSET_ENC_INT16，contents 数组里每个项都是 int16_t 类型的整数值，范围在 -2**15 ～ 2 ** 15 - 1 之间，也就是 -32768 ～ 32767

当 encoding 的值为 INTSET_ENC_INT32，contents 数组里每个项都是 int32_t 类型的整数值，范围在 -2**31 ～ 2 ** 31 - 1 之间

当 encoding 的值为 INTSET_ENC_INT64，contents 数组里每个项都是 int64_t 类型的整数值，范围在 -2**63 ～ 2 ** 63 - 1 之间

length 属性记录的是整数集合中包含的元素数量，也就是 contents 数组的长度。

contents 数组中的数值按值的大小从小到大有序排列，并且不包含重复项。

contents 数组中包含的元素类型都是一样的，比如当前数组中元素的类型是 int16_t，如果要向其中插入的整数值的类型是 int32_t，那么 contents 数组就要将 contents 数组的元素类型先升级再插入，这个就涉及升级的操作。

升级

当我们要添加到整数集合中的元素的类型比现有所有元素类型都要长时，整数集合需要进行升级（upgrade）操作，然后才能将新元素插入整数集合中。

升级并添加新元素共分为三步进行：

1. 根据新元素类型，扩展整数集合底层数组的空间大小，并为新元素分配空间
2. 将底层数组所有元素转换成与新元素相同的类型，并将类型转换后的元素放在正确的位上，且维持其有序性不变
3. 将新元素添加到底层数组里面

对于整数的三种类型，int16_t，int32_t，int64_t，每种类型的数据占用的位数分别是 16，32，64

假设当前 contents 数组有三个元素：1，2，3。类型是 int16_t，对应的元素和位数展示如下：

位	0-15位	16-31位	32-47位
元素	1	2	3

接下来需要添加一个整数，65535，类型是 int32_t，那么就需要先分配额外的空间，新分配的空间长度等于元素总数 * 新类型的位数 - 原有空间长度 = 4 * 32 - 48 = 80：

位	0-15位	16-31位	32-47位	48-127位
元素	1	2	3	新分配空间

然后分别将元素 3，2，1 移动到对应的空间内，再将新元素 65535 放在对应的空间上：

位	0-31位	32-63位	64-95位	96-127位
元素	1	2	3	65535

然后将整数集合 encoding 属性的值从 INTSET_ENC_INT16 改为 INTSET_ENC_INT32，length 属性的值从 3 改为 4。

升级的好处

为整数集合使用升级策略有两个好处，一个是提升整数集合的灵活性，一个是尽可能的节约内存

因为 C语言是静态类型语言，通常不会将两种不同类型的值放在一个数据结构里，但是整数集合可以通过自动升级底层数组来适应新元素，所以我们可以随意将 int16_t，int32_t，int64_t 类型的整数添加到集合中，而不必担心出现类型错误

另外，要让数组可以同时保存 int16_t，int32_t，int64_t 这三种类型的整数，最简单的方式是直接使用 int64_t 类型的数组去保存数据，但这样的话如果元素都是 int16_t，int32_t 类型的值，那么会出现浪费内存的情况。

因此现在升级策略可以尽量节约内存。

降级

整数集合不支持降低操作，一旦对数组进行了升级，编码就会一直保持升级后的状态。

比如前面的数组 1，2，3，65535，如果我们删除了 65535，整数集合还是会维持原有 INTSET_ENC_INT64 的编码，底层数组也还是 int64_t 类型的。

6. 跳跃表

跳跃表结构是有序集合的底层实现之一，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。

当有序集合包含的元素数量较多，又或者有序集合中的元素的成员是比较长的字符串时，Redis 就会使用跳跃表来作为有序集合的底层实现。

接下来介绍一下跳跃表和跳跃表节点结构。

跳跃表结构：

typedef struct zskiplist{
    // 表头节点和表尾节点
    struct skiplistNode *header, *tail;
    
    // 表中节点的数量
    unsigned long length;
    
    // 表中层数最大的节点的层数
    int level;
} zskiplist;

跳跃表结构中包含指向表头和表尾的指针，以及 length 字段表示表中节点的数量，level 字段则是表示所有跳跃表节点中最大的节点层数，层数的概念在跳跃表节点结构中再详细说明。

跳跃表节点结构：

typedef struct zskiplistNode{
    // 后退指针
    struct zskiplistNode *backward;
    
    // 分值
    double score;
    
    // 成员对象
    robj *obj;
    
    // 层
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        
        // 跨度
        unsigned int span;
    } level [];
    
} zskiplistNode;

我们可以将跳跃表理解成链表，不过链表上的每个节点都有指向前面一个节点的指针和多个指向后面某些节点的指针，指向后面的指针以数组的形式存在。

接下来我们以一张图来示意一下跳跃表及其节点之间的关系。

1) 跳跃表结构

在上面的伪代码示例和上图结构中，可以看到一个跳跃表结构如下几个属性：

a) header

header 是跳跃表的头节点指针，可以快速定位跳跃表的头节点

b) tail

tail 是跳跃表的尾部节点指针，可以快速定位跳跃表的尾部节点

c) level

level 表示的是跳跃表节点中层数最高的数值，比如在图中第三个跳跃表节点的层数最高，数值是 5，所以跳跃表的这个值是 5。

d) length

length 属性表示的是跳跃表节点的个数，也就是跳跃表的长度。

2) 跳跃表节点结构

跳跃表节点的各个属性如下：

a) obj

节点的成员对象，见图中的，o1，o2，o3，是一个指针，指向一个字符串对象，字符串对象保存着一个 SDS 值，就是有序集合中存储的数值。

b) score

有序集合用来进行排序的分值，有序集合通过这个属性用来对集合的元素进行排序，保存的是 double 类型的浮点数，在跳跃表中，所有节点按照分值从小到大来排序。

c) backward

后退指针，跳跃表的每个节点通过这个属性指向前一个节点，用于从表尾向表头方向访问节点。

图中展示了如何从表尾向跳跃表的头节点遍历的过程：通过 tail 指针指向跳跃表的尾部节点，然后通过 backward 后退指针逐个往前遍历，直到第一个节点的 backward 为 NULL 表示遍历结束。

d) skiplistLevel

skiplistLevel 是跳跃表节点的层，层数介于 1 到 32 之间，每个层的都包含两个属性，前进指针和跨度。

前进指针：forward，指向同一层级的下一个跳跃表节点

跨度：span，用于记录到同层级的下一个节点之间的距离，比如第一个节点的第四层级，下一个节点的第四层级是第三个节点，因此，o1 的第四层级的的跨度是 2。

3) 跳跃表节点层(level)介绍

前面介绍跳跃表节点的层属性是一个数组，包含多个指向下一个同一层级的指针，而每个节点层的大小则是根据幂次定律(power law) 来生成的。

在创建一个跳跃表节点的时候，程序都会根据幂次定律随机生成一个介于 1 到 32 之间的值作为 level 数组的大小，这个规则是越大的数出现的概率越小，它有一种计算方式，层数每加 1，出现的概率都是前一个数字的 0.25。

比如 level = 1 的概率是 0.75，那么 level = 2 的概率是 0.75 * 0.25，level = 3 的概率则是 0.75 * 0.25 * 0.25，直到最高层数

所以每个跳跃表节点的层数都是随机的，跟这个节点在跳跃表的前后位置无关。

4) 跳跃表的查询过程

以上面的图为例，比如我们想查询 score 为 2.0 的 o2 节点，那么查询的过程是这样的：

1. 首先根据头节点的最高一层节点，在图中是 L5，L5 指向的是 o3 节点，o3 节点的分值比目标分值 2.0 大，舍弃
2. 头节点往下降一层，到 L4，L4 指向下个节点 o1，o1的 score 比 2.0 小，跳到 o1 节点，继续查询
3. o1 节点的 L4 指向的下一节点是 o3，o3 的 score 比 2.0 大，舍弃，o1 的 L4 继续下降一层
4. o1 节点的 L3 节点指向的 o3 还是不符合条件，继续下降一层
5. o1 节点的 L2 节点指向的 o2 节点，其分值满足条件，而从 o1 到 o2 的跨度为 1 + 1 = 2

7. listpack

按照顺序，本来应该先介绍 quicklist 的结构，quicklist 在 7.0 之前的版本是由双向链表和压缩列表构成的，但是在 7.0 版本已经变成了由双向链表和 listpack 实现，所以在这里我们先介绍一下 listpack 的结构。

listpack 是替换 zippiest 的数据结构，所以在结构上两者是有些相似的，listpack 的结构如下：

| 总字节长度 | entry个数 | entry1 | entry2 | ... | entryN | end |

相比 ziplist，listpack 去除了到尾部节点，也就是到 entryN 的偏移量，但保留了其他属性。

对于单个 entry 元素，其结构如下：

| encoding | content | length |

encoding 表示 content 的编码，endocing 表示实际存储的内容，length 表示该 entry 的长度

避免连锁更新

使用 listpack 替代 ziplist 的一个好处是避免了连续更新的问题。

因为 ziplist 的每个元素都有一个属性用于保存前一个节点元素的长度，因此前一个节点修改后会可能需要修改后一个节点的属性，但是 listpack 没有这个关联关系，从而避免了影响后续元素的长度，也因此避免了连锁更新的问题。

获取最后一个节点

虽然 listpack 没有了指向尾部节点的偏移量，但是同样可以快速找到 listpack 的尾部节点，方式是通过 总字节长度属性的值，可以直接获取到 listpack 的尾部，然后根据 entry 元素尾部的 length 属性，就可以找到尾部 entry 的起始地址了。

8. quicklist

在 Redis 3.2 版本，列表对象的底层实现变成了由 quicklist 实现，quicklist 实际上是压缩列表和双向链表的组合结构，因为 quicklist 就是一个链表，而链表中每一个元素就是压缩列表。

而在 Redis 7.0 版本，quicklst 变成了由双向链表和 listpack 构成的结构。

这里直接介绍 quicklist 由双向链表和 listpack 构成的结构。

quicklist 的结构和双向链表的结构类似：

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count; 
    unsigned long len; 
    ...
} quicklist;

对于一个 quicklist，它也有指向 quicklist 的头节点和尾节点的指针，如结构中的 head 和 tail。

count 属性统计每个 quicklist 节点的 listpack 总数量的属性

len 则是统计 quicklist 中 quicklistNode 的数量的属性。

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *entry;
    size_t sz;             
    unsigned int count : 16; 
    ...
} quicklistNode;

对于一个 quicklistNode，拥有指向前置节点和后置节点的指针，还有指向其下 listpack 的 entry，以及 sz 表示该 listpack 的总字节长度，count 属性则表示该 listpack 中包含的元素个数。

4、对象的数据结构选择

一个对象的结构如下：

typedef struct redisObject{
    //类型
    unsigned type:4;
    
    //编码
    unsigned encoding:4;
    
    //指向底层实现数据结构的指针
    void *ptr
    
    //...
} robj;

type 属性用于表示这个对象的类型，比如 string，list，hash，set，zset 分别表示字符串对象，列表对象，哈希对象，集合对象和有序集合对象。

encoding 属性则表示该对象使用的编码

ptr 则是指向底层的指针

1. 字符串对象

字符串对象的编码有三种，int、embstr 和 raw

1) int

如果字符串对象保存的是整数值，并且这个整数值可以用 long 类型来表示，那么字符串对象会将整数值保存到对象的 ptr 属性里，且将编码设置为 int。

例如我们执行：

set number 123

object encoding number
# "int"

执行下面的命令返回的就是 number 的编码，为 int

2) embstr

在 Redis 3.2 版本之前，如果字符串保存的是一个字符串值，且这个字符串值的长度小于等于 39 字节，那么字符串对象会使用 embstr 编码的方式来保存。

但是我使用 Redis 7.0.11 版本测试的时候，这个值已经变成了 44，也就是说字符串值的长度小于等于 44 字节时，会使用 embstr 来编码，否则使用 raw 编码。

set embstr_str "this is a long long long long long story"

object encoding embstr_str
# "embstr"

3) raw

当我们设置的字符串值的长度大于 44 字节时，字符串对象会使用 raw 编码保存

set raw_str "this is a long long long long long long story"
object encoding raw_str

# "raw"

4) embstr 编码的好处

embstr 编码是专门用于保存短字符串的一种优化编码方式，这种编码和 raw 编码一样都使用 redisObject 结构和 sdshdr 结构来表示字符串对象。

但 raw 编码会调用两次内存分配来分别创建 redisObject 和 sdshdr 结构，而 embstr 编码则调用一次内存分配函数来分配一块连续的空间，依次包含 redisObject 和 sdshdr 两个结构。

使用 embstr 编码的好处如下：

• 创建字符串对象的时候内存分配次数从 raw 编码的两次降低为一次
• 释放 embstr 编码的字符串对象只需要调用一次内存释放函数，而 raw 编码的字符串对象需要调用两次内存释放函数
• embstr 编码的字符串对象的所有数据都保存在一块连续的内存里，所以比 raw 编码的字符串对象能更好地利用缓存带来的优势

5) 各类型值的编码方式

如果保存的是一个浮点数，在 Redis 中也是以字符串值来保存的，比如：

set pi 3.14
object encodng pi
# "embstr"

在有需要的时候，比如对 pi 进行运算的时候，程序会将这个字符串值转换回浮点数值，执行运算之后，再将其转换回字符串值保存，比如：

incrbyfloat pi 2

以下是字符串对象保存各类型值的编码方式：

值	编码
可以用 long 类型保存的整数	int
可以用 long double 类型保存的浮点数	embstr 或者 raw
字符串值，或者因为长度太大而没办法用 long 类型表示的整数，又或者因为长度太大而没办法用 long double 类型表示的浮点数	embstr 或者 raw

6) 编码的转换

对于 int 编码的整数来说，如果我们对其进行了数值上的操作，比如 incr 等，它仍然是一个 int 编码。

但是如果对其操作之后使其变成了字符串值，那么它的编码会变成 raw，比如通过 append 命令向其追加字符串：

set a 1
object encoding a
# "int"

append a " hello"
object encoding a
# "raw"

程序执行逻辑是先将其转换成字符串值，然后进行追加操作。

虽然追加字符串值之后，它的长度并没有超过 44 字节，但是 Redis 没有为 embstr 编码的字符串对象编写任何修改程序（只有 int 和 raw 编码的字符串对象有），所以对 int 或者 embstr 执行 append 这种修改逻辑之后，它的编码总是会变成 raw。

2. 列表对象

Redis 3.2 版本之前，列表对象的底层实现是由 ziplist 或者 双向链表实现的。

当以下两个条件被满足时，列表对象使用 ziplist 编码：

• 列表对象保存的所有字符串元素长度都小于 64 字节
• 列表对象保存的元素数量小于 512 个

以上两个条件任一不被满足，列表对象就会使用双向链表的方式存储列表数据。

而在 Redis 3.2 版本之后，列表对象的底层实现就变成了 quicklist。

Redis 7.0 版本中，quicklist 的结构是双向链表和 listpack 的混合结构，quicklist 拥有多个 quicklistNode 节点，其节点下是 listpack 结构保存多个元素。

3. 哈希对象

Redis 7.0 版本之前，哈希对象的底层实现用的是 ziplist 和 字典。

以下两个条件同时被满足时，哈希对象使用的是 ziplist 编码：

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

当上面两个条件任一不被满足，哈希对象就会使用字典作为编码。

接下来我们测试一下：

hset book name "this is short name"
object encoding book
# "ziplist"

hset book name "this is a long long long long long long long long long long long long"
object encoding book
# "hashtable"

注意：这里我们测试的是将 name 的 value 值设置长度大于 64 字节，如果我们将 name 替换成一个大于 64 字节的 key，同样会引起底层结构变成字典。

Redis 7.0 版本已经正式对 ziplist 进行了替换，所以哈希对象的底层实现变成了 listpack 和字典

4. 集合对象

集合对象的编码可以是 intset 或者 hashtable，由整数集合或者字典构成。

当集合对象同时满足下面两个条件时，对象使用 intset 编码：

• 集合对象中保存的所有元素都是整数值
• 集合对象中保存的元素数量不超过 512 个

接下来我们进行一个测试：

sadd set_test 1 2 3
object encoding set_test
# "intset"

sadd set_test "Python"
object encoding set_test
# "hashtable"

因为哈希表节点是 key-value 结构，所以当使用字典结构保存集合的时候，字典的 value 全部被设为 NULL。

5. 有序集合对象

Redis 7.0 版本以前，有序集合的编码是 ziplist 或 skiplist。

底层实现是压缩列表或者跳跃表。

但是底层实现是跳跃表的时候，为了查询更方便，并不仅仅使用跳跃表结构，还是用了字典进行辅助查询，这个我们后面细讲。

当有序集合满足以下两个条件时，对象使用 ziplist 编码：

• 有序集合保存的元素成员长度小于 128 个
• 有序集合保存的所有元素成员的长度都小于 64 字节

我们来测试一下长度的变化引起编码的改变：

zadd zset_test 1.2 name
object encoding zset_test
# "ziplist"

zadd zset_test 2.1 long_long_long_long_long_long_long_long_long_long_long_long_long_name 
# "skiplist"

当有序集合对象使用的是压缩列表作为底层实现时，每个集合元素使用两个紧挨在一起的压缩列表节点保存，第一个节点保存元素的成员（member），第二个元素保存元素的分值（score），且按照分值从小到大进行排序，分值较小的元素被放置在靠近表头的位置，分值较大的被放置在靠近表尾的位置。

假设我们创建的下面这个数据：

zadd price 8.5 apple 5.0 banana 6.0 cherry

那么在 ziplist 中保存的结构如下所示：

| zlbytes | zltail | zllen | "banana" | 5.0 | "cherry" | 6.0 | "apple" | 8.5 | zlend |

当有序集合对象的的编码是 skiplist 时，它的底层实现是 zset，一个 zset 结构同时包含一个字典和一个跳跃表，如下：

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

其中，dict 字典创建了一个从成员到分值的映射，zskiplist 跳跃表则按照分值从小到大保存了所有集合元素，示意图如下：

为什么会用两个结构来保存有序集合对象呢？

因为方便，如果需要对有序集合进行范围查找，比如ZRANK、ZRANGE，可以基于跳跃表 API 进行查询，如果要查询给定成员的分值，可以用 dict 结构。

上图中，为了展示方便，字典和跳跃表重复展示了各个元素的成员和分值，但在实际中，字典和跳跃表会共享元素的成员和分值，所以并不会任何数据的重复，也不会因此而浪费任何内存。

Redis 7.0 版本之后，有序集合底层的 ziplist 也被替换成了 listpack。