Redis数据结构
1. SDS
Redis 是用 C 语言写的，但是对于 Redis 的字符串，却不是 C 语言中的字符串（即以空字符’\0’结尾的字符数组），它是自己构建了一种名为 简单动态字符串（simple dynamic string,SDS）的抽象类型，并将 SDS 作为 Redis 的默认字符串表示
因为 C 语言字符串存在很多问题：
- 获取字符串长度的需要通过运算
- 非二进制安全
- 不可修改
例如，我们执行命令：
127.0.0.1:6379> set name zhangsan
ok
那么 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 的优点
- 获取字符串长度的时间复杂度为 O (1)
- 支持动态扩容
- 支持内存预分配，减少用户线程与内核线程交互次数
- 二进制安全
一般来说，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 (重新散列）来对哈希表进行相应的扩展或者收缩。具体步骤：
- 计算新 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 最终为空
-
触发扩容的条件：
- 服务器目前没有执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且负载因子大于等于 1。
- 服务器目前正在执行 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 的 2^n^
- 收缩大小为第一个大于等于 used 的 2^n^
- 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> <encoding> <entry-data>
prevlen：前一个 entry 的大小，编码方式见下文；
encoding：不同的情况下值不同，用于表示当前 entry 的类型和长度；
entry-data：真是用于存储 entry 表示的数据；
**第二种情况：**在 entry 中存储的是 int 类型时，encoding 和 entry-data 会合并在 encoding 中表示，此时没有 entry-data 字段；
redis 中，在存储数据时，会先尝试将 string 转换成 int 存储，节省空间；此时 entry 结构：<prevlen> <encoding>
- prevlen编码
当前一个元素长度小于 254（255 用于 zlend）的时候，prevlen 长度为 1 个字节，值即为前一个 entry 的长度，如果长度大于等于 254 的时候，prevlen 用 5 个字节表示，第一字节设置为 254，后面 4 个字节存储一个小端的无符号整型，表示前一个 entry 的长度；
<prevlen from 0 to 253> <encoding> <entry> //长度小于254结构
0xFE <4 bytes unsigned little endian prevlen> <encoding> <entry> //长度大于等于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. QuickList
5.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. RedisObject
7.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 种不同类型：
| 编号 | 编码方式 | 说明 |
|---|---|---|
| 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 流 |
7.3 五种数据结构
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 |
本文由
传智教育博学谷发布。如果本文对您有帮助，欢迎
关注和点赞；如果您有任何建议也可留言评论或私信，您的支持是我坚持创作的动力。转载请注明出处！