1 Simple Dynamic String (简单动态字符串)

因为 C 语言的字符串存在很多问题：

获取字符串长度需要遍历，效率低
非二进制安全（无法处理 ‘\0’ 等特殊字节）
不支持动态扩容

所以 Redis 没有直接使用 C 语言的字符串，而是构建了一种新的字符串结构：SDS(Simple Dynamic Strings)，简单动态字符串

SDS 的结构

SDS 本质上是一个结构体， char[] 由 SDS 自己来管理

根据字符串长度的不同，SDS 提供多种结构体实现来支持不同大小的字符串（如下图中为 sdsdr8），以节省内存空间

动态扩容——内存预分配

当向 SDS 追加字符串超出当前容量时，会自动申请更大的内存：

新字符串长度 < 1MB：新容量 = 扩展后长度 x 2 + 1
新字符串长度 >= 1MB：新容量 = 扩展后长度 + 1MB + 1（每次固定增长 1MB，防止几何增长造成浪费）

结构就分为这两部分：

Header：记录当前字符串的长度等信息，便于读取
buf[]：真实存储字符串的 char[]

SDS 的优点

O(1) 时间获取字符串长度
支持自动扩容
内存预分配 -> 减少内存分配次数
二进制安全（可安全处理包含 \0 的数据）
-> 正因为 SDS 是字节存储，所以也支持存音频、视频等二进制大对象（但不推荐，毕竟内存贵）

2 IntSet (整数数组)

IntSet 是 Redis 中 Set 集合的一种实现方式，具备有序、元素唯一的、长度可变的特点

是对 C 语言中整数数组的封装和增强，对数组的增删改查都由 IntSet 来维护

在这个数组中，每个元素的大小都是固定的，所以将来查找时就可以通过第一个元素的内存地址，再根据距离和一个元素的大小，通过一个数学表达式快速寻址：startPtr + (sizeof(int16) * index)

IntSet 的编码自动升级机制

当插入的整数超出了当前 encoding 所能表示的范围时，IntSet 会自动升级数组中所有元素的编码格式（不可逆）

比如当前编码为 int16，但插入一个需要 int32 才能表示的值时，整个数组会升级为 int32

为了避免内存重叠时数据被覆盖，IntSet 在迁移数据时采用倒序拷贝（从后往前复制）的方式

有序性

IntSet 内部维护元素有序 -> 使用二分查找来提升查找效率

使用场景

由于 IntSet 依赖连续内存空间，所以适用于元素数量较少的场景

3 Dict (字典)

Dict 的组成

全局哈希表和哈希节点的关系

字典

4 Dict 的扩容

Dict 的结构

Dict 类似 Java 的 HashTable，底层就是数组+单向链表的实现

Dict 包含两个哈希表，ht[0] 平常用，ht[1] 用来 rehash

Dict 的扩容

当集合中元素较多时会出现哈希冲突增多的情况，导致链表过长，大大降低查询效率
-> Dict 在每次新增键值对时，会检查是否需要扩容

什么时候会触发全局哈希表扩容？

（负载因子：LoadFactor = used / size）

哈希表的加载因子 >= 1 并且没有执行 bgsave 或 bgrewriteaof 等后台进程
哈希表的加载因子 > 5

Dict 的缩容

Dict 在每次删除键值对时，会检查是否需要缩容

什么时候会触发全局哈希收缩？

当负载因子 < 0.1 时

Dict 的 rehash

不论是扩容还是收缩，都会创建新的哈希表，导致哈希表的 size 和 sizemask 变化。因此必须对哈希表中的每一个 key 重新计算索引，插入新的哈希表，这个过程称为 rehash。过程如下：

计算新 hash 表的 realSize，值取决于当前要做的是扩容还是收缩：

如果是扩容，则新 size 为第一个大于等于 dict.ht[0].used + 1 的 2^n
如果是缩容，则新 size 为第一个大于等于 dict.ht[0].used 的 2^n（不得小于 4）

按照新的 realSize 申请内存空间，创建 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] 的内存

以上的过程存在什么问题呢？试想一下，如果 Dict 中包含数百万的 entry，要在一次 rehash 中完成，极有可能导致主线程阻塞。
-> 因此 Dict 的 rehash 并不是一次性完成的，而是分多次、渐进式完成的（每次访问 Dict 时执行一次 rehash），称为渐进式 rehash。过程如下：

计算新 hash 表的 realSize，值取决于当前要做的是扩容还是收缩：

如果是扩容，则新 size 为第一个大于等于 dict.ht[0].used + 1 的 2^n
如果是缩容，则新 size 为第一个大于等于 dict.ht[0].used 的 2^n（不得小于 4）

按照新的 realSize 申请内存空间，创建 dictht，并赋值给 dict.ht[1]
设置 dict.rehashidx = 0，标示开始 rehash
~~将 dict.ht[0] 中的每一个 dictEntry 都 rehash 到 dict.ht[1]~~
每次执行新增、查询、修改、删除操作时，都检查一下 dict.rehashidx 是否大于 -1，如果是则将 dict.ht[0].table[rehashidx] 的 entry 链表 rehash 到 dict.ht[1]，并且 rehashidx++，直至 dict.ht[0] 的所有数据都 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 的进行最终为空

5 ZipList (压缩列表)

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

当然它不是真正意义上的链表，因为列表的节点之间不是通过指针连接的，而是通过记录上一节点和本节点的长度来寻址 -> 省内存 + 访问速度快！

ZipList 的结构

这是一片连续的内存空间，前三部分（zlbytes、zltail、zllen）是头信息。

zlbytes（uint32_t, 4 bytes）：压缩列表的总字节数
zltail（uint32_t, 4 bytes）：尾节点的偏移量（尾节点的起始地址、起始节点之间的字节数）-> 所以能快速定位 -> 所以能快速压入/弹出
zllen（uint16_t, 2 bytes）：entry 节点的个数

第一个 entry 称为头节点 head，最后一个 entry 称为尾节点 tail。每个 entry 节点的长度是不固定的，由节点保存的内容决定。

最后的 zlend 是整个压缩列表的结束标识（uint8_t, 1 byte, 值是固定的——0xff）。

ZipList 中的 Entry 的结构

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

previous_entry_length（1 byte / 5 bytes）：前一个节点的长度。如果：

前一个节点的长度 < 254 bytes：采用 1 byte 来保存这个长度值
前一个节点的长度 >= 254 bytes：采用 5 bytes 来保存这个长度值，第一个字节固定为 0xfe，后四个字节才是真实长度数据（四个字节挺大的，所以不推荐让单个数据占用过多内存）
encoding：编码属性，记录 content 的数据类型（字符串 / 整数）以及长度，占用 1 byte / 2 bytes / 5 bytes
contentss：负责保存节点的数据，可以是字符串或整数

补充

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

ZipList 中的 Entry 中的 Encoding 的结构

ZipList 中的 Entry 中的 encoding 编码分为字符串和整数两种：

字符串：如果 encoding 是以 00 / 01 / 10 开头，则说明 content 是字符串，

| 00pppppp |
编码长度为 1 bytes，字符串大小 <= 63(2^6-1) bytes
| 01pppppp | qqqqqqqq |
编码长度为 2 bytes，字符串大小 <= 16383(2^14-1) bytes
| 10000000 | qqqqqqqq | rrrrrrrr | ssssssss | tttttttt |
编码长度为 5 bytes，字符串大小 <= 4294967295 bytes

整数：如果 encoding 是以 11 开头，则说明 content 是整数，且 encoding 固定只占用 1 个字节

（编码格式和具体整数类型之间的对应关系省略，感觉学习意义不大）

ZipList 的缺点

和双向链表类似，只能从前往后 / 从后往前遍历，那如果列表数据过多，就可能影响查询性能。

ZipList 的连锁更新问题（Cascade Update）

如前所述，ZipList 中的每个 Entry 都包含 previous_entry_length 字段，用于记录上一个节点的长度。这个字段的长度可能是：1 byte（当长度 <= 253 bytes）；也可能是 5 bytes（当长度 > 253 字节）。假设现在有 N 个连续的长度为 250~253 bytes的 Entry，此时每个 Entry 的 previous_entry_length 只需要 1 byte 就可以表示。

但是，如果我们在中间插入一个长度超过 253 bytes的新 Entry，那么它后面的那个 Entry 的 previous_entry_length 字段就必须从 1 byte 扩展为 5 bytes！这会使这个 Entry 的空间发生变化，进而影响下一个 Entry 的偏移计算，从而引发一连串的结构更新（推动后续每个节点向后移动）——这就是“连锁更新”。

新增、删除都可能导致连锁更新，只要影响了 previous_entry_length 的编码方式，就有可能引发这种“向后传染”的更新行为。虽然发生的概率极低，但是一旦触发会造成频繁的内存申请、销毁、迁移，以及用户态与内核态之间频繁的内存拷贝，影响性能。

6 QuickList (快速列表)

QuickList 简介

可以理解为：LinkedList + ZipList

特殊的双端链表，每一个节点都关联了一个 ZipList

针对 ZipList 存在的问题：

虽然节省内存，但是申请内存必须是连续空间，如果内存占用较多，申请内存效率会很低
-> 为了缓解这个问题，我们必须限制 ZipList 的长度和 Entry 大小

但是我们要存储大量数据，超出了 ZipList 最佳的上限怎么办
-> 创建多个 ZipList，分片存储数据

压缩 ZipList

QuickList 除了能控制 ZipList 的大小，还可以对节点的 ZipList 进行压缩

QuickList 的结构

QuickList 的特点

是一个节点为 ZipList 的双端链表
节点内部采用 ZipList，解决了传统链表的内存占用问题
控制了 ZipList 的大小，解决连续内存空间的申请效率问题
中间节点可以压缩，进一步节省了内存

总而言之：QuickList 兼具了链表和 ZipList 的优点！

7 SkipList (跳表)

空间换时间，操作的时间复杂度是 **O(logN)**，证明略

特点总结

跳表是一个双向链表，每个节点都包含 score 和 ele 值
节点优先按照 score 值排序，score 值一样则按照 ele 字典排序
每个节点都可以包含多层指针，层数范围是 [1, 32]
不同层指针到下一个节点的跨度不同，层级越高，跨度越大
增删改查效率与红黑树基本一致，实现却更简单

8 RedisObject (Redis 对象)

简介

value 底层的 6 种数据机构：

SDS (简单动态字符串)
IntSet (整型数组)
Dict (字典/哈希表)
ZipList (压缩列表)
SkipList (跳表)

这些数据结构最终作为 value 底层存储的数据形式，并且会被封装在一个 RedisObject 中

Redis 的编码方式

Redis 会根据存储数据的类型不同，选择不同的编码方式

RedisObject 、Redis 所有数据类型、Redis 所有编码方式（底层实现）三者之间的关系

9 数据类型：String

String 是 Redis 中最常见的数据存储类型

会根据 SDS 的长度来决定采用什么编码方式/实现方式，有 3 种：

基本的编码格式：RAW，基于 SDS 实现，存储上限为 512 MB（可以自己配置）

如果存储的 SDS 长度小于等于 44 bytes -> 采用 EMBSTR 编码，此时 object head 与 SDS 是一段连续内存空间，申请内存时只需要调用一次内存分配函数，效率更高

如果存储的字符串是整数值，并且大小在 LONG_MAX 范围内 -> 采用 INT 编码：直接将数据保存在 RedisObject 的 ptr 指针位置（刚好是 8 bytes），不再需要 SDS 了

确切来说，String 在 Redis 中是用一个 robj 来表示的

10 数据类型：List

Redis 的 List 结构类似一个双端链表

特点

有序
可以重复
可以双端操作

版本区别

在 3.2 版本之前，Redis 采用 ZipList 和 LinkedList 来实现 List，当元素数量不超过 512 并且元素大小不超过 64 bytes 时采用 ZipList 编码，有其中一项超过则采用 LinkedList 编码
在 3.2 版本之后，Redis 统一采用 QuickList 来实现 List

结构如下：

11 数据类型：Set

特点

无序
元素唯一
可以求交集、并集、差集

底层实现

Set 对随机查询效率要求极高

（默认）为了查询效率和唯一性，采用 HT 编码，Dict 中的 key 用来存储元素，value 统一为 null
当存储的所有数据都是整数，并且元素数量不超过 set-max-intset-entries 时，Set 会采用 IntSet 编码，以节省内存

每次插入都会检查是否满足：都是整数 && 数量不超过set-max-intset-entries，如果不满足，就会将 IntSet 编码转换为 HT 编码

结构如下：

12 数据类型：ZSet

Zset = SortedSet，有序集合

特点 & 底层实现

ZSet 必须满足以下特点：

键值存储（member -> score）
键（member）必须唯一
有序性（根据 score 值排序）

底层采用了两种方式：SkipList + Dict、ZipList

方式一：SkipList + Dict

利用 Dict 实现 -> 键唯一、键值存储
利用 SkipList 实现 -> 有序性

所以，上面两种方式 ZSet 全都要，结构如下（注：o->encoding 只写了 SKIPLIST，但是其实是 Dict 和 SkipList 两种）：

缺点：内存占用太高！

方式二：当元素数量不多时，会采用 ZipList 来存储 -> 节省空间

当元素数量不多时，HT 和 SkipList 的优势不明显，而且更占内存
-> 因此 ZSet 还会采用 ZipList 结构来节省内存，不过需要同时满足两个条件时：

元素个数不超过 zset_max_ziplist_entries(默认值 128)
元素大小不超过 zset_max_ziplist_value(默认值 64 字节)

结构如下：

ZipList 本身没有排序功能，也没有键值对的概念，因此需要用 ZSet 结合业务逻辑来实现：键值存储、键唯一、有序性，具体思路：

ZipList 是连续内存，因此 score 和 element 是紧挨在一起的两个 entry，element 在前，score 在后
score 越小越接近队首，score 越大越接近队尾，按照 score 值升序排列

总结

初始化过程中会判断采用哪种方式，初始方案：ZipList，最终方案：SkipList + Dict(哈希表)

13 数据类型：Hash

特点 & 底层实现

Hash 结构和 ZSet 非常相似

Hash 必须满足以下特点：

键值存储
键必须唯一

区别：

ZSet 的 key(member) 是字符串，value(score) 是数值；而 Hash 的 key(field) 和 value 都是任意值
ZSet 需要根据 score 排序；而 Hash 无需排序

因此，Hash 底层采用的编码与 ZSet 基本一致，只是去掉了排序相关的 SkipList
-> 两种方式：ZipList、Dict：

数据量较少时 -> 采用 ZipList 编码（默认）

节省内存，ZipList 中相邻的两个 entry 分别存储 field 和 value

数据量较大时 -> 采用 HT 编码（Dict）

触发条件有两个（满足其中之一）：

ZipList 中的元素个数 > hash_max_ziplist_entries(默认值 512)
ZipList 中的元素大小 > hash_max_ziplist_value(默认值 64 bytes)

为什么需要从 ZipList 升级？

Redis 的 Hash 之所以这样设计，是因为当 ZipList 变得很大的时候有以下性能问题：

每次插入/修改会引发 realloc 操作，有更大的概率造成内存拷贝
内存拷贝的成本也相应增加，因为要拷贝更大的一块内存
当 ZipList 数据项过多时，查找指定的数据项性能很差，因为 ZipList 需要线性便利所有项