Redis数据结构

1. SDS

Redis 是用 C 语言写的，但是对于 Redis 的字符串，却不是 C 语言中的字符串（即以空字符’\0’结尾的字符数组），它是自己构建了一种名为 简单动态字符串（simple dynamic string,SDS）的抽象类型，并将 SDS 作为 Redis 的默认字符串表示

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

  • 获取字符串长度的需要通过运算
  • 非二进制安全
  • 不可修改

例如，我们执行命令：

127.0.0.1:6379> set name zhangsanok

那么 Redis 将在底层创建两个 SDS，其中一个是包含 “name” 的 SDS，另一个是包含 “zhangsan” 的 SDS。

1.1 SDS 是什么

Redis 是 C 语言实现的，其中 SDS 是一个结构体，源码如下：


例如，一个包含字符串 “name” 的 sds 结构如下：第一次分配时并不会分配多余空间


SDS 之所以叫做动态字符串，是因为它具备动态扩容的能力，例如一个内容为 “hi” 的 SDS：


假如我们要给 SDS 追加一段字符串 “,Amy”，这里首先会申请新内存空间：

如果新字符串小于 1M，则新空间为扩展后字符串长度的两倍 + 1；

如果新字符串大于 1M，则新空间为扩展后字符串长度 + 1M+1。称为内存预分配。

1.2 SDS 的优点

  1. 获取字符串长度的时间复杂度为 O (1)
  2. 支持动态扩容
  3. 支持内存预分配，减少用户线程与内核线程交互次数
  4. 二进制安全

一般来说，SDS 除了保存数据库中的字符串值以外，SDS 还可以作为缓冲区（buffer）：包括 AOF 模块中的 AOF 缓冲区以及客户端状态中的输入缓冲区

2. Inset

intset 是 set 集合的一种实现方式，基于整数数组来实现，并且具备长度可变、有序等特征。

2.1 Inset是什么？

结构如下：


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


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


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

  • encoding：4 字节 （可以理解为标识每个元素的类型）
  • length：4 字节
  • contents：2 字节 * 3 = 6 字节

2.2 inset自动升级

我们向该其中添加一个数字：50000，这个数字超出了 int16_t 的范围，intset 会自动升级编码方式到合适的大小。
以当前案例来说流程如下：

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

那么如果我们删除掉刚加入的 int32 类型时，会不会做一个降级操作呢？

不会。主要还是减少开销的权衡


源码如下：

2.3 总结：

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

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

3. Dict

我们知道 Redis 是一个键值型（Key-Value Pair）的数据库，我们可以根据键实现快速的增删改查。而键与值的映射关系正是通过 Dict 来实现的。是 set 和 hash 的实现方式之一

3.1 Dict是什么？

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

当我们向 Dict 添加键值对时，Redis 首先根据 key 计算出 hash 值（h），然后利用 h & sizemask 来计算元素应该存储到数组中的哪个索引位置。我们存储 k1=v1，假设 k1 的哈希值 h =1，则 1&3 =1，因此 k1=v1 要存储到数组角标 1 位置。

注意这里还有一个指向下一个哈希表节点的指针，我们知道哈希表最大的问题是存在哈希冲突，如何解决哈希冲突，有开放地址法和链地址法。这里采用的便是链地址法，通过 next 这个指针可以将多个哈希值相同的键值对连接在一起，用来解决哈希冲突。

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

3.2 深入理解

  • 哈希算法：Redis 计算哈希值和索引值方法如下：
#1、使用字典设置的哈希函数，计算键 key 的哈希值hash = dict->type->hashFunction(key);#2、使用哈希表的sizemask属性和第一步得到的哈希值，计算索引值index = hash & dict->ht[x].sizemask;

  • 解决哈希冲突：这个问题上面我们介绍了，方法是链地址法。通过字典里面的 *next 指针指向下一个具有相同索引值的哈希表节点。

  • 扩容和收缩：当哈希表保存的键值对太多或者太少时，就要通过 rerehash (重新散列）来对哈希表进行相应的扩展或者收缩。具体步骤：

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

ps：负载因子 = 哈希表已保存节点数量 / 哈希表大小。

  • 渐进式rehash

什么叫渐进式 rehash？也就是说扩容和收缩操作不是一次性、集中式完成的，而是分多次、渐进式完成的。如果保存在 Redis 中的键值对只有几个几十个，那么 rehash 操作可以瞬间完成，但是如果键值对有几百万，几千万甚至几亿，那么要一次性的进行 rehash，势必会造成 Redis 一段时间内不能进行别的操作。所以 Redis 采用渐进式 rehash, 这样在进行渐进式 rehash 期间，字典的删除查找更新等操作可能会在两个哈希表上进行，第一个哈希表没有找到，就会去第二个哈希表上进行查找。但是进行 增加操作，一定是在新的哈希表上进行的。

3.3 总结：

Dict 的结构：

  • 类似 java 的 HashTable，底层是数组加链表来解决哈希冲突
  • Dict 包含两个哈希表，ht [0] 平常用，ht [1] 用来 rehash

Dict 的伸缩：

  • 当 LoadFactor 大于 5 或者 LoadFactor 大于 1 并且没有子进程任务时，Dict 扩容
  • 当 LoadFactor 小于 0.1 时，Dict 收缩
  • 扩容大小为第一个大于等于 used + 1 的 2n
  • 收缩大小为第一个大于等于 used 的 2n
  • Dict 采用渐进式 rehash，每次访问 Dict 时执行一次 rehash
  • rehash 时 ht [0] 只减不增，新增操作只在 ht [1] 执行，其它操作在两个哈希表

4. ZipList

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

4.1 ZipList 是什么？


zlbytes : 字段的类型是 uint32_t , 这个字段中存储的是整个 ziplist 所占用的内存的字节数

zltail : 字段的类型是 uint32_t , 它指的是 ziplist 中最后一个 entry 的偏移量。用于快速定位最后一个 entry, 以快速完成 pop 等操作

zllen : 字段的类型是 uint16_t , 它指的是整个 ziplit 中 entry 的数量。这个值只占 2bytes（16 位）: 如果 ziplist 中 entry 的数目小于 65535 (2 的 16 次方), 那么该字段中存储的就是实际 entry 的值。若等于或超过 65535, 那么该字段的值固定为 65535, 但实际数量需要一个个 entry 的去遍历所有 entry 才能得到。

zlend 是一个终止字节，其值为全 F, 即 0xff. ziplist 保证任何情况下，一个 entry 的首字节都不会是 255

4.2 ZipListEntry

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

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

第一种情况：一般结构

​prevlen：前一个 entry 的大小，编码方式见下文；

​encoding：不同的情况下值不同，用于表示当前 entry 的类型和长度；

​entry-data：真是用于存储 entry 表示的数据；

第二种情况：在 entry 中存储的是 int 类型时，encoding 和 entry-data 会合并在 encoding 中表示，此时没有 entry-data 字段；

redis 中，在存储数据时，会先尝试将 string 转换成 int 存储，节省空间；此时 entry 结构：

  • prevlen编码

当前一个元素长度小于 254（255 用于 zlend）的时候，prevlen 长度为 1 个字节，值即为前一个 entry 的长度，如果长度大于等于 254 的时候，prevlen 用 5 个字节表示，第一字节设置为 254，后面 4 个字节存储一个小端的无符号整型，表示前一个 entry 的长度；

        //长度小于254结构0xFE      //长度大于等于254
  • encoding 编码

encoding 的长度和值根据保存的是 int 还是 string，还有数据的长度而定；

前两位用来表示类型，当为 “11” 时，表示 entry 存储的是 int 类型，其它表示存储的是 string；

存储string时：

|00xxxxxx| ：此时 encoding 长度为 1 个字节，该字节的后六位表示 entry 中存储的 string 长度，因为是 6 位，所以 entry 中存储的 string 长度不能超过 63；

|01xxxxxx|xxxxxxxx| 此时 encoding 长度为两个字节；此时 encoding 的后 14 位用来存储 string 长度，长度不能超过 16383；

|10000000|xxxxxxxx|xxxxxxxx|xxxxxxxx|xxxxxxxx| 此时 encoding 长度为 5 个字节，后面的 4 个字节用来表示 encoding 中存储的字符串长度，长度不能超过 2^32 – 1;

存储int时：

|11000000| encoding 为 3 个字节，后 2 个字节表示一个 int16；

|11010000| encoding 为 5 个字节，后 4 个字节表示一个 int32;

|11100000| encoding 为 9 个字节，后 8 字节表示一个 int64;

|11110000| encoding 为 4 个字节，后 3 个字节表示一个有符号整型；

|11111110| encoding 为 2 字节，后 1 个字节表示一个有符号整型；

|1111xxxx| encoding 长度就只有 1 个字节，xxxx 表示一个 0 – 12 的整数值；

|11111111| zlend

4.3 ZipList 的连锁更新问题

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

ZipList 这种特殊情况下产生的连续多次空间扩展操作称之为连锁更新（Cascade Update）。新增、删除都可能导致连锁更新的发生。虽然发生的条件非常苛刻，但不代表不会发生

4.4 总结：

ZipList 特性：

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

5. QuickList5.1 QuickList 是什么？

ZipList 虽然节省内存，但申请内存必须是连续空间，但是我们要存储大量数据，内存中碎片比较多，很难找到一块大的连续空间。于是 ，大数据量下，内存申请效率低成了 ziplist 的最大问题，而 quickList 就是为了帮助 zipList 摆脱困境的。

  • 为了缓解内存申请效率低的问题，QuickList 提供了可限制 ZipList 的最大节点数 和 每个 entry 的大小的方式。
  • 那么对于大数据量 ，我们可以采用分片的思想，存储在多个 ZipList 中 ，而 QuickList 可以将这些 ZipList 作为节点连接起来。

为了避免 QuickList 中的每个 ZipList 中 entry 过多，Redis 提供了一个配置项：list-max-ziplist-size 来限制。

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

其默认值为 -2：

以下是 QuickList 的和 QuickListNode 的结构源码：

5.2 QuickList 内存布局

5.3 总结：

QuickList 的特点：

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

6. SkipList

跳跃表结构在 Redis 中的运用场景只有一个，那就是作为有序列表 (Zset) 的使用。跳跃表的性能可以保证在查找，删除，添加等操作的时候在对数期望时间内完成，这个性能是可以和平衡树来相比较的，而且在实现方面比平衡树要优雅，这就是跳跃表的长处。跳跃表的缺点就是需要的存储空间比较大，属于利用空间来换取时间的数据结构

6.1 SkipList 是什么？

SkipList（跳表）首先是链表，但与传统链表相比有几点差异：

  • 元素按照升序排列存储
  • 节点可能包含多个指针，指针跨度不同。

6.2 SkipListNode 结构

  • ele 字段，持有数据，是 sds 类型
  • score 字段，其标示着结点的得分，结点之间凭借得分来判断先后顺序，跳跃表中的结点按结点的得分升序排列.
  • backward 指针，这是原版跳跃表中所没有的。该指针指向结点的前一个紧邻结点.
  • level 字段，用以记录所有结点 (除过头节点外)；每个结点中最多持有 32 个 zskiplistLevel 结构。实际数量在结点创建时，按幂次定律随机生成 (不超过 32). 每个 zskiplistLevel 中有两个字段
  • forward 字段指向比自己得分高的某个结点 (不一定是紧邻的), 并且，若当前 zskiplistLevel 实例在 level [] 中的索引为 X, 则其 forward 字段指向的结点，其 level [] 字段的容量至少是 X+1. 这也是上图中，为什么 forward 指针总是画的水平的原因.
  • span 字段代表 forward 字段指向的结点，距离当前结点的距离。紧邻的两个结点之间的距离定义为 1.

6.3 skiplist 与平衡树、哈希表的比较

skiplist 和各种平衡树（如 AVL、红黑树等）的元素是有序排列的，而哈希表不是有序的。因此，在哈希表上只能做单个 key 的查找，不适宜做范围查找。所谓范围查找，指的是查找那些大小在指定的两个值之间的所有节点。

在做范围查找的时候，平衡树比 skiplist 操作要复杂。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在 skiplist 上进行范围查找就非常简单，只需要在找到小值之后，对第 1 层链表进行若干步的遍历就可以实现。

平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而 skiplist 的插入和删除只需要修改相邻节点的指针，操作简单又快速。

从内存占用上来说，skiplist 比平衡树更灵活一些。一般来说，平衡树每个节点包含 2 个指针（分别指向左右子树），而 skiplist 每个节点包含的指针数目平均为 1/(1-p)，具体取决于参数 p 的大小。如果像 Redis 里的实现一样，取 p=1/4，那么平均每个节点包含 1.33 个指针，比平衡树更有优势。

查找单个 key，skiplist 和 平衡树 的时间复杂度都为 O (log n)，大体相当；而哈希表在保持较低的哈希值冲突概率的前提下，查找时间复杂度接近 O (1)，性能更高一些。所以我们平常使用的各 Map 或 dictionary 结构，大都是基于哈希表实现的。

从算法实现难度上来比较，skiplist 比平衡树要简单得多。

6.4 总结：

SkipList 的特点：

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

7. RedisObject7.1 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。

!

  • type : 占 4bit , 五个取值类型，表示对象类型 String , Hash , List , set , zset。
  • encoding : 占 4bit ，十一种编码方式
  • lru : 占用 3 字节，记录最后一次被访问的时间，主要用于 lru 算法，最近最少使用
  • refcount ：占用 4 字节，引用计数器，无人用就回收
  • *ptr：占用 8 字节 ，只想存放实际数据的空间

redis 的头部占用 16 字节

7.2 encoding 取值：

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

编号编码方式说明
0OBJ_ENCODING_RAWraw 编码动态字符串
1OBJ_ENCODING_INTlong 类型的整数的字符串
2OBJ_ENCODING_HThash 表（字典 dict）
3OBJ_ENCODING_ZIPMAP已废弃
4OBJ_ENCODING_LINKEDLIST双端链表
5OBJ_ENCODING_ZIPLIST压缩列表
6OBJ_ENCODING_INTSET整数集合
7OBJ_ENCODING_SKIPLIST跳表
8OBJ_ENCODING_EMBSTRembstr 的动态字符串
9OBJ_ENCODING_QUICKLIST快速列表
10OBJ_ENCODING_STREAMStream 流

7.3 五种数据结构

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

数据类型编码方式
OBJ_STRINGint、embstr、raw
OBJ_LISTLinkedList 和 ZipList (3.2 以前)、QuickList（3.2 以后）
OBJ_SETintset、HT
OBJ_ZSETZipList、HT、SkipList
OBJ_HASHZipList、HT

本文由传智教育博学谷教研团队发布。

如果本文对您有帮助，欢迎关注和点赞；如果您有任何建议也可留言评论或私信，您的支持是我坚持创作的动力。

转载请注明出处！