一、SDS

二、IntSet（整数集合）

三、双向链表

四、压缩列表

五、字典（哈希表）

七、跳表

八、QuickList

九、RedisObject

一、SDS

Redis 是用 C语言实现的，但是它没有直接使用C 语言的 char* 字符数组来实现字符串，而是自己封装了-个名为简单动态字符串(simple dynamic string，SDs) 的数据结构来表示字符串，也就是 Redis 的String 数据类型的底层数据结构是 SDS。

C 语言字符串的缺陷

获取字符串长度的时间复杂度为O(N)
非二进制安全（不能存二进制数据）
不可修改
字符串操作函数不高效且不安全，比如有缓冲区溢出的风险，有可能会造成程序运行终止

SDS 结构

Redis 5.0 的 SDS 的数据结构：

len：记录了字符串长度。这样获取字符串长度的时候，只需要返回这个成员变量值就行，时间复杂度只需要O(1)。
alloc：分配给字符数组的空间长度。这样在修改字符串的时候，可以通过alloc - len计算出剩余的空间大小，可以用来判断空间是否满足修改需求，如果不满足的话，就会自动将SDS的空间扩展至执行修改所需的大小，然后才执行实际的修改操作，所以使用SDS既不需要手动修改SDS的空间大小，也不会出现前面所说的缓冲区溢出的问题。
flags：用来表示不同类型的SDS。一共设计了5种类型，分别是sdshdr5、sdshdr8、sdshdr16、sdshdr32和sdshdr64。
buf[]：字节数组，用来保存实际数据。不仅可以保存字符串，也可以保存二进制数据。总的来说，Redis的SDS结构在原本字符数组之上，增加了三个元数据：len、alloc、flags，用来解决C语言字符串的缺陷。

SDS的扩容原理：

如果所需的sds长度小于1MB，那么最后的扩容是按照翻倍扩容来执行的，即2倍的newlen。
如果所需的sds长度超过1MB，那么最后的扩容长度应该是newlen + 1MB。

在扩容SDS空间之前，SDS API会优先检查未使用空间是否足够，如果不够的话，API不仅会为SDS分配修改所必须要的空间，还会给SDS分配额外的「未使用空间」。

这样的好处是，下次在操作SDS时，如果SDS空间够的话，API就会直接使用「未使用空间」，而无须执行内存分配，有效的减少内存分配次数。

所以，使用SDS即不需要手动修改SDS的空间大小，也不会出现缓冲区溢出的问题。

二、IntSet（整数集合）

IntSet是Redis中set集合的一种实现方式，基于整数数组来实现，并且具备长度可变、有序等特征。结构如下：

typedef struct intset {uint32_t encoding;  // 编码方式，决定每个元素的字节大小uint32_t length;    // 集合包含的元素数量int8_t contents[];  // 保存元素的柔性数组
} intset;

其中的encoding包含三种模式，表示存储的整数大小不同：

为了方便查找，Redis会将intset中所有的整数按照升序依次保存在contents数组中，结构如图：

现在，数组中每个数字都在int16_t的范围内，因此采用的编码方式是INTSET_ENC_INT16，每部分占用的字节大小为：

encoding：4字节
length：4字节
contents：2字节 * 3 = 6字节

我们向该其中添加一个数字：50000，这个数字超出了int16_t的范围，intset会自动升级编码方式到合适的大小。

以当前案例来说流程如下：

升级编码为INTSET_ENC_INT32, 每个整数占4字节，并按照新的编码方式及元素个数扩容数组
倒序依次将数组中的元素拷贝到扩容后的正确位置
将待添加的元素放入数组末尾
最后，将inset的encoding属性改为INTSET_ENC_INT32，将length属性改为4

Intset可以看做是特殊的整数数组，具备一些特点：

Redis会确保Intset中的元素唯一、有序

具备类型升级机制，可以节省内存空间

底层采用二分查找方式来查询

不支持降级操作

三、双向链表

Redis的链表实现优点如下：

listNode链表节点的结构里带有prev和next指针，获取某个节点的前置节点或后置节点的时间复杂度只需O(1)，而且这两个指针都可以指向 NULL，所以链表是无环链表；
list结构因为提供了表头指针 head 和表尾节点tail，所以获取链表的表头节点和表尾节点的时间复杂度只需O(1)；
list结构因为提供了链表节点数量len，所以获取链表中的节点数量的时间复杂度只需O(1)；
listNode链表节使用void* 指针保存节点值，并且可以通过 list结构的 dup、free、match函数指针为节点设置该节点类型特定的函数，因此链表节点可以保存各种不同类型的值；

链表的缺点：

链表每个节点之间的内存都是不连续的，意味着无法很好利用CPU缓存。能很好利用CPU缓存的数据结构就是数组，因为数组的内存是连续的，这样就可以充分利用 CPU缓存来加速访问。
还有一点，保存一个链表节点的值都需要一个链表节点结构头的分配，内存开销较大。

因此， Redis 3.0的List对象在数据量比较少的情况下，会采用「压缩列表」作为底层数据结构的实现，它的优势是节省内存空间，并且是内存紧凑型的数据结构。

不过，压缩列表存在性能问题（具体什么问题，下面会说），所以 Redis在3.2版本设计了新的数据结构quicklist，并将List对象的底层数据结构改由 quicklist 实现。

然后在 Redis 5.0 设计了新的数据结构 listpack，沿用了压缩列表紧凑型的内存布局，最终在最新的 Redis版本，将 Hash对象和 Zset对象的底层数据结构实现之一的压缩列表，替换成由 listpack实现。

四、压缩列表

ZipList 是一种特殊的“双端链表” ，由一系列特殊编码的连续内存块组成。可以在任意一端进行压入/弹出操作, 并且该操作的时间复杂度为 O(1)。

属性	类型	长度	用途
zlbytes	uint32_t	4 字节	记录整个压缩列表占用的内存字节数
zltail	uint32_t	4 字节	记录压缩列表表尾节点距离压缩列表的起始地址有多少字节，通过这个偏移量，可以确定表尾节点的地址。
zllen	uint16_t	2 字节	记录了压缩列表包含的节点数量。最大值为UINT16_MAX （65534），如果超过这个值，此处会记录为65535，但节点的真实数量需要遍历整个压缩列表才能计算得出。
entry	列表节点	不定	压缩列表包含的各个节点，节点的长度由节点保存的内容决定。
zlend	uint8_t	1 字节	特殊值 0xFF （十进制 255 ），用于标记压缩列表的末端。

ZipListEntry

ZipList 中的Entry并不像普通链表那样记录前后节点的指针，因为记录两个指针要占用16个字节，浪费内存。而是采用了下面的结构：

previous_entry_length：前一节点的长度，占1个或5个字节。
- 如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值
- 如果前一节点的长度大于254字节，则采用5个字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长度数据
encoding：编码属性，记录content的数据类型（字符串还是整数）以及长度，占用1个、2个或5个字节
contents：负责保存节点的数据，可以是字符串或整数

ZipList中所有存储长度的数值均采用小端字节序，即低位字节在前，高位字节在后。例如：数值0x1234，采用小端字节序后实际存储值为：0x3412

Encoding编码

ZipListEntry中的encoding编码分为字符串和整数两种：字符串：如果encoding是以“00”、“01”或者“10”开头，则证明content是字符串

如果当前节点的数据是整数，则encoding会使用1字节的空间进行编码，也就是encoding长度为1字节。通过encoding确认了整数类型，就可以确认整数数据的实际大小了，比如如果encoding编码确认了数据是int16整数，那么data的长度就是int16的大小。
如果当前节点的数据是字符串，根据字符串的长度大小，encoding会使用1字节/2字节/5字节的空间进行编码，encoding编码的前两个bit表示数据的类型，后续的其他bit标识字符串数据的实际长度，即data的长度。

ZipList的每个Entry都包含previous_entry_length来记录上一个节点的大小，长度是1个或5个字节：如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值如果前一节点的长度大于等于254字节，则采用5个字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长度数据现在，假设我们有N个连续的、长度为250~253字节之间的entry，因此entry的previous_entry_length属性用1个字节即可表示，如图所示：

ZipList这种特殊情况下产生的连续多次空间扩展操作称之为连锁更新（Cascade Update）。新增、删除都可能导致连锁更新的发生。

优点：

节省内存开销
能更好地利用 CPU 缓存。

缺点：

插入/删除效率低，修改可能触发连锁更新问题，会导致压缩列表占用的内存空间要多次重新分配，这就会直接影响到压缩列表的访问性能。
仅适合元素少、元素小的小对象存储。

五、字典（哈希表）

Dict由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）

Dict结构图：

Hash冲突

Redis 采用了「链式哈希」的方法来解决哈希冲突（拉链法），（头插法插入节点）

Dict的扩容：

Dict中的HashTable就是数组结合单向链表的实现，当集合中元素较多时，必然导致哈希冲突增多，链表过长，则查询效率会大大降低。

Dict在每次新增键值对时都会检查负载因子（LoadFactor = used/size） ，满足以下两种情况时会触发哈希表扩容（rehash）：

哈希表的 LoadFactor >= 1，并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程；
哈希表的 LoadFactor > 5 ；

Dict的rehash：

不管是扩容还是收缩，必定会创建新的哈希表，导致哈希表的size和sizemask变化，而key的查询与sizemask有关。因此必须对哈希表中的每一个key重新计算索引，插入新的哈希表，这个过程称为rehash。过程是这样的：

计算新hash表的realeSize，值取决于当前要做的是扩容还是收缩：
- 如果是扩容，则新size为第一个大于等于dict.ht[0].used + 1的2^n
- 如果是收缩，则新size为第一个大于等于dict.ht[0].used的2^n （不得小于4）
按照新的realeSize申请内存空间，创建dictht，并赋值给dict.ht[1]
设置dict.rehashidx = 0，标示开始rehash
将dict.ht[0]中的每一个dictEntry都rehash到dict.ht[1]
将dict.ht[1]赋值给dict.ht[0]，给dict.ht[1]初始化为空哈希表，释放原来的dict.ht[0]的内存
将rehashidx赋值为-1，代表rehash结束
在rehash过程中，新增操作，则直接写入ht[1]，查询、修改和删除则会在dict.ht[0]和dict.ht[1]依次查找并执行。这样可以确保ht[0]的数据只减不增，随着rehash最终为空

存在的问题：

如果「哈希表1」的数据量非常大，那么在迁移至「哈希表2」的时候，因为会涉及大量的数据拷贝，此时可能会对 Redis 造成阻塞，无法服务其他请求。

渐进式 rehash

为了避免 rehash 在数据迁移过程中，因拷贝数据的耗时，影响 Redis 性能的情况，所以 Redis 采用了渐进式 rehash，也就是将数据的迁移的工作不再是一次性迁移完成，而是分多次迁移。

渐进式 rehash 步骤如下：

给「哈希表 2」分配空间；
在 rehash 进行期间，每次哈希表元素进行新增、删除、查找或者更新操作时，Redis 除了会执行对应的操作之外，还会顺序将「哈希表 1」中索引位置上的所有 key-value 迁移到「哈希表 2」上；
随着处理客户端发起的哈希表操作请求数量越多，最终在某个时间点会把「哈希表 1」的所有 key-value 迁移到「哈希表 2」，从而完成 rehash 操作。

这样就巧妙地把一次性大量数据迁移工作的开销，分摊到了多次处理请求的过程中，避免了一次性 rehash 的耗时操作。

在进行渐进式 rehash 的过程中，会有两个哈希表，所以在渐进式 rehash 进行期间，哈希表元素的删除、查找、更新等操作都会在这两个哈希表进行。

比如，查找一个 key 的值的话，先会在「哈希表 1」里面进行查找，如果没找到，就会继续到哈希表 2 里面进行找到。

另外，在渐进式 rehash 进行期间，新增一个 key-value 时，会被保存到「哈希表 2」里面，而「哈希表 1」则不再进行任何添加操作，这样保证了「哈希表 1」的 key-value 数量只会减少，随着 rehash 操作的完成，最终「哈希表 1」就会变成空表。

七、跳表

跳表结构设计：

链表在查找元素的时候，因为需要逐一查找，所以查询效率非常低，时间复杂度是O(N)，于是就出现了跳表。跳表是在链表基础上改进过来的，实现了一种「多层」的有序链表，这样的好处是能快速定位数据。

下图展示了一个层级为3的跳表

图中头节点有 L0~L2 三个头指针，分别指向了不同层级的节点，然后每个层级的节点都通过指针连接起来：

L0 层级共有 5 个节点，分别是节点1、2、3、4、5；
L1 层级共有 3 个节点，分别是节点 2、3、5；
L2 层级只有 1 个节点，也就是节点 3。

如果我们要在链表中查找节点 4 这个元素，只能从头开始遍历链表，需要查找 4 次，而使用了跳表后，只需要查找 2 次就能定位到节点 4，因为可以在头节点直接从 L2 层级跳到节点 3，然后再往前遍历找到节点 4。

可以看到，这个查找过程就是在多个层级上跳来跳去，最后定位到元素。当数据量很大时，跳表的查找复杂度就是 O(logN)。

那跳表节点是怎么实现多层级的呢？这就需要看「跳表节点」的数据结构了，如下：

typedef struct zskiplistNode {//Zset 对象的元素值sds ele;//元素权重值double score;//后向指针struct zskiplistNode *backward;//节点的 level 数组，保存每层上的前向指针和跨度struct zskiplistLevel {struct zskiplistNode *forward;unsigned long span;} level[];
} zskiplistNode;

Zset 对象要同时保存「元素」和「元素的权重」，对应到跳表节点结构里就是 sds 类型的 ele 变量和 double 类型的 score 变量。每个跳表节点都有一个后向指针（struct zskiplistNode *backward），指向前一个节点，目的是为了方便从跳表的尾节点开始访问节点，这样倒序查找时很方便。

跳表是一个带有层级关系的链表，而且每一层级可以包含多个节点，每一个节点通过指针连接起来，实现这一特性就是靠跳表节点结构体中的zskiplistLevel 结构体类型的 level 数组。

level 数组中的每一个元素代表跳表的一层，也就是由 zskiplistLevel 结构体表示，比如 leve 就表示第一层，leve 就表示第二层。zskiplistLevel 结构体里定义了「指向下一个跳表节点的指针」和「跨度」，跨度时用来记录两个节点之间的距离。

比如，下面这张图，展示了各个节点的跨度。

跨度实际上是为了计算这个节点在跳表中的排位。

具体怎么做的呢？

因为跳表中的节点都是按序排列的，那么计算某个节点排位的时候，从头节点到该结点的查询路径上，将沿途访问过的所有层的跨度累加起来，得到的结果就是目标节点在跳表中的排位。

举个例子，查找图中节点3在跳表中的排位，从头节点开始查找节点3，查找的过程只经过了一个层（L2），并且层的跨度是3，所以节点3在跳表中的排位是3。

另外，图中的头节点其实也是zskiplistNode跳表节点，只不过头节点的后向指针、权重、元素值都没有用到，所以图中省略了这部分。

问题来了，由谁定义哪个跳表节点是头节点呢？这就介绍「跳表」结构体了，如下所示：

typedef struct zskiplist {struct zskiplistNode *header, *tail;unsigned long length;int level;
} zskiplist;

跳表结构里包含了：

跳表的头尾节点，便于在O(1)时间复杂度内访问跳表的头节点和尾节点；
跳表的长度，便于在O(1)时间复杂度获取跳表节点的数量；
跳表的最大层数，便于在O(1)时间复杂度获取跳表中层高最大的那个节点的层数量；

跳表节点查询过程

查找一个跳表节点的过程时，跳表会从头节点的最高层开始，逐一遍历每一层。在遍历某一层的跳表节点时，会用跳表节点中的 SDS 类型的元素和元素的权重来进行判断，共有两个判断条件：

如果当前节点的权重『小于』要查找的权重时，跳表就会访问该层上的下一个节点。
如果当前节点的权重『等于』要查找的权重时，并且当前节点的 SDS 类型数据『小于』要查找的数据时，跳表就会访问该层上的下一个节点。

如果上面两个条件都不满足，或者下一个节点为空时，跳表就会使用目前遍历到的节点的 level 数组里的下一层指针，然后沿着下一层指针继续查找，这就相当于跳到了下一层接着查找。

举个例子，下图有个 3 层级的跳表。

如果要查找『元素：abcd，权重：4』的节点，查找的过程是这样的：

先从头节点的最高层开始，L2 指向了『元素：abc，权重：3』节点，这个节点的权重比要查找节点的小，所以要访问该层上的下一个节点；
但是该层的下一个节点是空节点（leve指向的是空节点），于是就会跳到『元素：abc，权重：3』节点的下一层去找，也就是 leve;
『元素：abc，权重：3』节点的 leve 的下一个指针指向了『元素：abcde，权重：4』的节点，然后将其和要查找的节点比较。虽然『元素：abcde，权重：4』的节点的权重和要查找的权重相同，但是当前节点的 SDS 类型数据『大于』要查找的数据，所以会继续跳到『元素：abc，权重：3』节点的下一层去找，也就是 leve;
『元素：abc，权重：3』节点的 leve 的下一个指针指向了『元素：abcd，权重：4』的节点，该节点正是要查找的节点，查询结束。

跳表节点层数设置

跳表的相邻两层的节点数量的比例会影响跳表的查询性能、举个例子，下图的跳表，第二层的节点数量只有1个，而第一层的节点数量有6个

这时，如果想要查询节点 6，那基本就跟链表的查询复杂度一样，就需要在第一层的节点中依次顺序查找，复杂度就是 O(N) 了。所以，为了降低查询复杂度，我们就需要维持相邻层结点数间的关系。

跳表的相邻两层的节点数量最理想的比例是 2:1，查找复杂度可以降低到 O(logN)。

下图的跳表就是，相邻两层的节点数量的比例是 2:1。

那怎样才能维持相邻两层的节点数量的比例为 2 : 1 呢?

如果采用新增节点或者删除节点时，来调整跳表节点以维持比例的方法的话，会带来额外的开销。

Redis 则采用一种巧妙的方法是，跳表在创建节点的时候，随机生成每个节点的层数，并没有严格维持相邻两层的节点数量比例为 2 : 1 的情况。

具体的做法是，跳表在创建节点时候，会生成范围为[0-1]的一个随机数，如果这个随机数小于 0.25（相当于概率 25%），那么层数就增加 1 层，然后继续生成下一个随机数，直到随机数的结果大于 0.25 结束，最终确定该节点的层数。

这样的做法，相当于每增加一层的概率不超过 25%，层数越高，概率越低，层高最大限制是 64。

虽然我前面讲解跳表的时候，图中的跳表的「头节点」都是 3 层高，但是其实如果层高最大限制是 64，那么在创建跳表「头节点」的时候，就会直接创建 64 层高的头节点。

八、QuickList

其实 quicklist 就是「双向链表+压缩列表」组合，因为一个 quicklist 就是一个链表，而链表中的每个元素又是一个压缩列表。

虽然压缩列表是通过紧凑型的内存布局节省了内存开销，但是因为它的结构设计，如果保存的元素数量增加，或者元素变大了，压缩列表会有「连锁更新」的风险，一旦发生，会造成性能下降。

quicklist 解决办法，通过控制每个链表节点中的压缩列表的大小或者元素个数，来规避连锁更新的问题,因为压缩列表元素越少或越小，连锁更新带来的影响就越小，从而提供了更好的访问性能。

quicklist 结构设计

在向 quicklist 添加一个元素的时候，不会像普通的链表那样，直接新建一个链表节点。而是会检查插入位置的压缩列表是否能容纳该元素，如果能容纳就直接保存到 quicklistNode 结构里的压缩列表，如果不能容纳，才会新建一个新的 quicklistNode 结构。

quicklist 会控制 quicklistNode 结构里的压缩列表的大小或者元素个数，来规避潜在的连锁更新的风险，但是这并没有完全解决连锁更新的问题。

QuickList的特点：

是一个节点为ZipList的双端链表

节点采用ZipList，解决了传统链表的内存占用问题

控制了ZipList大小，解决连续内存空间申请效率问题

中间节点可以压缩，进一步节省了内存

九、RedisObject

Redis中的任意数据类型的键和值都会被封装为一个RedisObject，也叫做Redis对象

从Redis的使用者的角度来看，⼀个Redis节点包含多个database（非cluster模式下默认是16个，cluster模式下只能是1个），而一个database维护了从key space到object space的映射关系。这个映射关系的key是string类型，⽽value可以是多种数据类型，比如： string, list, hash、set、sorted set等。

我们可以看到，key的类型固定是string，而value可能的类型是多个。

⽽从Redis内部实现的⾓度来看，database内的这个映射关系是用⼀个dict来维护的。dict的key固定用⼀种数据结构来表达就够了，这就是动态字符串sds。而value则比较复杂，为了在同⼀个dict内能够存储不同类型的value，这就需要⼀个通⽤的数据结构，这个通用的数据结构就是robj，全名是redisObject。

Redis的编码方式

Redis中会根据存储的数据类型不同，选择不同的编码方式，共包含11种不同类型：

编号	编码方式	说明
0	OBJ_ENCODING_RAW	raw编码动态字符串
1	OBJ_ENCODING_INT	long类型的整数的字符串
2	OBJ_ENCODING_HT	hash表（字典dict）
3	OBJ_ENCODING_ZIPMAP	已废弃
4	OBJ_ENCODING_LINKEDLIST	双端链表
5	OBJ_ENCODING_ZIPLIST	压缩列表
6	OBJ_ENCODING_INTSET	整数集合
7	OBJ_ENCODING_SKIPLIST	跳表
8	OBJ_ENCODING_EMBSTR	embstr的动态字符串
9	OBJ_ENCODING_QUICKLIST	快速列表
10	OBJ_ENCODING_STREAM	Stream流

五种数据结构

Redis中会根据存储的数据类型不同，选择不同的编码方式。每种数据类型的使用的编码方式如下：

数据类型	编码方式
OBJ_STRING	int、embstr、raw
OBJ_LIST	LinkedList和ZipList(3.2以前)、QuickList（3.2以后）
OBJ_SET	intset、HT
OBJ_ZSET	ZipList、HT、SkipList
OBJ_HASH	ZipList、HT