Redis数据结构

引用：小林coding、JavaGuide、https://juejin.cn/post/7525640395234230326

1. Redis是如何实现键值对数据库的？

Redis是使用了一个哈希表保存所有键值对，哈希表其实就是一个数组，数组中的元素叫哈希桶。哈希桶存放的是指向键值对的指针（dictEntry*），键值对则保存了key和value的指针。

特别说明下，void * key 和 void * value指针指向的是Redis对象，Redis中的每个对象都由redisObject结构表示：

2. Redis的基本数据类型

Redis 共有 5 种基本数据类型：String（字符串）、List（列表）、Set（集合）、Hash（散列）、Zset（有序集合）。

这 5 种数据类型底层实现主要依赖这 8 种数据结构：简单动态字符串（SDS）、LinkedList（双向链表）、Dict（哈希表/字典）、SkipList（跳跃表）、Intset（整数集合）、ZipList（压缩列表）、QuickList（快速列表）。Redis 5 种基本数据类型对应的底层数据结构实现如下表所示：

String	List	Hash	Set	Zset
SDS	LinkedList/ZipList/QuickList	Dict、ZipList	Dict、Intset	ZipList、SkipList

Redis 3.2 之前，List 底层实现是 LinkedList 或者 ZipList。 Redis 3.2 之后，引入了 LinkedList 和 ZipList 的结合 QuickList，List 的底层实现变为 QuickList。从 Redis 7.0 开始， ZipList 被 ListPack 取代。

3. Redis的数据结构

3.1 简单动态字符串SDS

Redis没有直接使用C语言中的字符串，因为C语言字符串存在很多问题：

• 获取字符串长度的需要通过运算
• 非二进制安全(如果字符中出现 ‘\0’，会导致字符串提前结束)
• 不可修改

Redis SDS的5种不同类型

SDS 之所以叫做动态字符串，是因为它具备动态扩容的能力，当给SDS追加一段字符串时：

• 如果新字符串小于 1M，则新空间为扩展后字符串长度的两倍+1（加 1 是因为申请的时候需要预留 ‘\0’ 位，用于兼容C字符串）
• 如果新字符串大于 1M，则新空间为扩展后字符串长度+1M+1。称为内存预分配。申请内存这件事本身是耗时的，所以 Redis 采用的是预分配，减少内存申请的次数

SDS 的优点：

1. 获取字符串的长度的时间复杂度是 O(1)
2. 遍历字符串的时候是根据 len 来运算的，所以是二进制安全的
3. 支持动态扩容
4. 减少内存的分配次数

3.2 整数集合IntSet

IntSet 是 Redis 中 Set 集合的一种实现方式，基于整数数组来实现，并且具备长度可变、有序等特征。为了方便查找，Redis 会将 IntSet 中所有的整数按照升序依次保存在 contents 数组中

其中的 encoding 包含三种模式（INTSET_ENC_INT16：2字节、INTSET_ENC_INT32：4字节、INTSET_ENC_INT64：8字节），表示存储的整数大小不同。

假设当前contents数组中每个元素都在INT16范围内，采用的是INTSET_ENC_INT16编码，此时如果添加一个数字：50000，这个数字超出了INT16的范围，IntSet会自动升级编码方式：

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

IntSet 的优点：

• Redis 会确保 IntSet 中的元素唯一、有序
• 具备类型升级机制，可以节省内存空间
• 底层采用二分查找方式来查询

3.3 字典Dict

当我们向 Dict 添加键值对时，Redis 首先根据 Key 计算出hash 值（h），然后利用 h & sizemask 来计算元素应该存储到数组中的哪个索引位置（因为sizemark = size - 1 且 size为2次幂，所以 h & sizemark == h % size，参考HashMap）

其中dictEntry的key指针指向SDS，next指针通过拉链法解决hash冲突；通过渐进式rehash实现Dict的扩容和缩容（Redis渐进式rehash）

3.4 压缩列表ZipList

Dict 因为大量使用指针（一个指针占 8 字节），会浪费内存空间，并且也会造成内存碎片。进而有了 ZipList，ZipList 是一种特殊的“双端链表” ，由一系列特殊编码的连续内存块组成。可以在任意一端进行压入/弹出操作, 并且该操作的时间复杂度为 O(1)

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

ZipListEntry

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

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

previous_entry_length

• 为什么 zlend 中 0xFF 不会和 previous_entry_length 中的 0xFF 混淆？

1. 因为在 entry 结构体的 previous_entry_length 字段里，只有在用 5 字节编码时才可能出现 0xFF，但它只是“长度数据”的一部分，不会被解析为结束符 ，也就是说 0xFF 出现在previous_entry_length 时不会单独解析 0xFF，而是会用后面 4 字节解码出完整长度。
2. 但是当解析下一个 entry 时，一开始就遇到了 0xFF，那就说明 ZipList 已经到结尾了

• 为什么 previous_entry_length 一个字节时只能表示 254 个字节，而不是 255 个字节？

因为 0xFE（254）被规定为“扩展标志”，一旦前面 entry 超过 253 字节，这 1 字节就写 0xFE，然后后面追加 4 字节来存真正的长度，也就是使用 5 个字节表示长度

Encoding

如果 encoding 以 00、01 或者 10 开头，就表示数据类型是字符串，字符串有三种编码，分别占用 1 个、2 个或 5个字节：

• $contents长度 < 2^6$ 时，以 00 开头，后 6 位表示 contents 的长度
• $2^6 \leq contents长度 < 2^{14}$ 时，以 01 开头，后续 6 位 + 下一个字节的 8 位 = 14 位表示 contents 的长度
• $2^{14} \leq contents长度 < 2^{32}$ 时，以 10 开头，后续 6 位不用，从下一字节起连续 32 位表示 contents 的长度

如果 encoding 以 11开头，表示数据类型是整数，共有6种编码形式，固定只占1个字节：

最后一个类型，为啥没有 11111111 ？因为 11111111 表示 zlend (十进制的 255，十六进制的 0xFF)

Contents

contents 表示真实存的数据，可以是字符串或者整数，从encoding可以得知类型和长度。知道长度，就知道 contents 的起始位置了

比较特殊的是，整数 1 ~ 13 (0001 ~ 1101)，因为比较短，刚好可以塞在 encoding 字段里面，所以就没有 contents

ZipList的连锁更新问题

ZipList 的每个 Entry 都包含 previous_entry_length 来记录上一个节点的大小，长度是 1 个或 5 个字节：

• 如果前一节点的长度小于 254 字节，则采用 1 个字节来保存这个长度值
• 如果前一节点的长度大于等于 254 字节，则采用5个字节来保存这个长度值，第一个字节为 0xfe，后四个字节才是真实长度数据

现在，假设我们有N个连续的、长度为 250~253 字节之间的 entry，因此 entry 的 previous_entry_length 属性用 1 字节即可表示，如图所示：

如果此时在 ZipList 的头部插入一个 Entry，且 Entry 的字节大小为 254 字节，那么整个 ZipList 都需要更新 previous_entry_length 为5字节来表示，也就是说整个 ZipList 都需要做重新申请内存，然后做数据迁移：

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

ZipList特性：

• ZipList可以看做一种连续内存空间的”双向链表”
• 列表的节点之间不是通过指针连接，而是记录上一节点和本节点长度来寻址，内存占用较低
• 如果列表数据过多，导致链表过长，可能影响查询性能
• 增或删较大数据时有可能发生连锁更新问题

3.5 快速列表QuickList

• ZipList 虽然节省内存，但申请内存必须是连续空间，如果内存占用较多，申请内存效率很低 ===> 为了缓解这个问题，我们必须限制 ZipList 的长度和 entry 大小
• 但是我们要存储大量数据，超出了 ZipList 最佳的上限该怎么办？ ===> 分片
• 数据拆分后比较分散，不方便管理和查找，这多个 ZipList 如何建立联系？ ===> QuickList

Redis 在 3.2 版本引入了新的数据结构 QuickList，它是一个双端链表LinkedList，只不过链表中的每个节点都是一个 ZipList

compress 参数表示压缩深度，有三种选择方式：

• 0 代表不压缩
• 1 代表不压缩首尾两个节点，下图即为压缩深度为1时的QuickList（为了支持快速的 push/pop 操作）
• 2 代表不压缩首尾四个节点

为了避免 QuickList 中的每个 ZipList 中 entry 过多，Redis 提供了一个配置项：list-max-ziplist-size，超出了这个大小，就会新起一个 ZipList：

• list-max-ziplist-size为正，则代表 ZipList 的允许的 entry 个数的最大值
• list-max-ziplist-size为负，则代表 ZipList 的最大内存大小，分 5 种情况：
  • -1：每个 ZipList 的内存占用不能超过 4kb
  • -2：每个 ZipList 的内存占用不能超过 8kb（默认值🌟）
  • -3：每个 ZipList 的内存占用不能超过 16kb
  • -4：每个 ZipList 的内存占用不能超过 32kb
  • -5：每个 ZipList 的内存占用不能超过 64kb

QuickList 的特点：

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

3.6 紧凑列表Listpack

QuickList 虽然通过控制 QuickListNode结构里的ZipList的大小或者元素个数，来减少连锁更新带来的性能影响，但是并没有完全解决连锁更新的问题
因为QuickListNode还是用了ZipList来保存元素，ZipList连锁更新的问题，来源于它的结构设计，所以要想彻底解决这个问题，需要设计一个新的数据结构

Redis 5.0 引入了listpack并在 7.0 版本完全取代了 ZipList。listpack结构如下：

• encoding：记录data的编码类型及长度，类似ZipList的encoding，会对不同长度的整数和字符串进行编码
• data：实际存放的数据
• len：当前entry的长度，区别于ZipList，不再记录前一个entry的大小previous_entry_length，也就避免了连锁更新问题

3.7 跳表SkipList

ZipList 和 QuickList 查询首尾确实非常快，还节约内存，但是当查询的是中间节点的某一个元素时，查询性能就不是很好了

SkipList也是一个链表结构，但与传统链表相比有几点差异：

• 元素按照Score升序排列存储（根据 Score 值进行排序，节点存放的元素值为 ele）
• 每一个节点可能包含多个指针，指针跨度不同

SkipList查询过程

查找「元素:abcd，权重:4」的节点时:

• 从SkipList头节点最高层L2开始，指向「元素:abc，权重:3」节点，因其权重小于目标权重，访问下一个节点，却发现下一个节点为空
• 跳到「元素:abc，权重:3」节点的下一层level[1]，其forward指针指向「元素:abcde，权重:4」节点，虽权重相
  同，但该节点SDS类型数据大于目标数据，继续跳到下一层level[0]
• 在level[0]层，「元素:abc，权重:3」节点的forward指针指向「元素:abcd，权重:4」节点，找到目标节点，查询
  结束

SkipList的特点：

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

4. Redis的数据类型

4.1 String（SDS / 无需额外内存空间）

String编码类型有三种：

• int编码：如果存储的字符串是整数值且可转成 long long 范围，例如 “255” 可以用整数 255 表示，则会采用 int 编码，此时 value 值由 RedisObject 中的 ptr 指针进行存储，不再需要申请其他内存空间，因为 ptr 为 8 字节，所以 int 表示的范围是 $[-2^{63}, 2^{63} - 1]$

• RAW编码：基于SDS实现，存储上限为 512MB，需要分配两次内存空间（分别为 RedisObject 和 SDS 分配空间）

• embstr编码：如果存储的字符串长度小于 44 字节，则会采用 embstr 编码，此时 RedisObject 的头信息与 SDS 是一段连续空间，只分配一次内存空间（但它是只读的，任何修改都会导致它升级为 raw，因为原地修改embstr成本很高）

  Redis字符串的embstr编码和raw编码之间的界限为什么是44字节

4.2 List（LinkedList / ZipList / QuickList / listpack）

哪一个数据结构能满足LPUSH RPUSH LRANGE LPOP RPOP等操作？

• LinkedList ：普通链表，可以从双端访问，内存占用较高，内存碎片较多
• ZipList ：压缩列表，可以从双端访问，内存占用低，存储上限低
• QuickList：LinkedList + ZipList，可以从双端访问，内存占用较低，包含多个ZipList，存储上限高
• listpack：Redis7.0后推出的用于替代ZipList的数据结构，大体上和ZipList类似，但避免了连锁更新问题

Redis 的 List 结构类似一个双端链表，可以从首、尾操作列表中的元素。

• 在3.2版本之前，Redis 采用 ZipList 和 LinkedList 来实现 List，当列表元素数量小于 512 并且每个元素大小小于 64 字节时采用 ZipList 编码，超过则采用LinkedList 编码
• 在3.2版本之后，Redis 统一采用 QuickList 来实现 List
• 在7.0版本之后，Redis统一采用 listpack来实现List

4.3 Set（Dict / IntSet）

Set 常用命令为SADD，SISMENMBER，SINTER，可以看出，Set 对查询元素的效率要求非常高

• HashTable，也就是 Redis 中的 Dict，不过 Dict 是双列集合（可以存键、值对），Java 中 HashSet 底层是通过 HashMap 实现的，只利用了 HashMap 的 Key，而 Value 为 null，所以我们也可以参考 Java 的实现思路。所以 Redis 的 Set 数据类型的实现方式之一就是通过 Dict 实现的，同时也保证了查询效率和唯一性。Dict 中的 Key 用来存储元素，Value 统一为 null。最终 Set集合不一定确保元素有序，但可以满足元素唯一、查询效率也高
• 当存储的所有数据都是整数，并且元素数量不超过set-max-intset-entries时，Set 会采用 IntSet 编码，IntSet由于内部有序，使用二分查找加快查询效率，同时还能节省内存。当采用 IntSet 编码的时候，能够满足元素的有序性，但是 Set 集合对外还是要说明是不保证元素的有序性的

4.4 ZSet（ZipList / listpack / SkipList）

ZSet 常用命令为ZADD，ZRANK，ZSCORE，ZSet 底层数据结构必须满足键值存储、键必须唯一、可排序这几个需求

ZSet 类型的底层数据结构是由ZipList或SkipList实现的:

• 如果 ZSet 的元素个数小于 128个 （默认值，可由 zset_max_ziplist_entries 配置），并且每个元素的值小于64字节（默认值，可由  zset_max_ziplist_value 配置）时，Redis会使用 ZipList 作为 ZSet 类型的底层数据结构，使用Score值在 ZipList 中进行排序；（在 Redis7.0中，ZipList 数据结构已经废弃了，交由 listpack 数据结构来实现了）
• 如果 ZSet 的元素不满足上面的条件，Redis会使用 SkipList 作为 ZSet 类型的底层数据结构

4.5 Hash（ZipList / listpack / Dict）

Hash 结构与 Redis 中的 ZSet 非常类似：都是键值存储、都需求根据键获取值、键必须唯一

Hash类型的底层数据结构是由 ZipList 或 Dict 实现的:

• 如果Hash类型元素个数小于 512 个（默认值，可由 hash-max-ziplist-entries 配置），并且每个元素小于 64 字节（默认值，可由 hash-max-ziplist-value 配置）的话，Redis会使用 ZipList 作为 Hash 类型的底层数据结构；（在Redis 7.0中， ZipList 数据结构已经废弃了，交由 listpack 数据结构来实现了）
• 如果 Hash 类型元素不满足上面条件，Redis会使用 Dict 作为 Hash类型的底层数据结构