您的位置:  首页 > 技术杂谈 > 正文

Redis原理 - 对象的数据结构(SDS、Inset、Dict、ZipList、QuickList、SkipList、RedisObject)

2022-12-06 19:00 https://my.oschina.net/jiagoushi/blog/5605097 博学谷狂野架构师 次阅读 条评论

Redis数据结构

file

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 是一个结构体,源码如下:

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

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

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

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

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

file

1.2 SDS 的优点

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

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

2. Inset

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

2.1 Inset是什么?

结构如下:

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

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

file 现在,数组中每个数字都在 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 类型时,会不会做一个降级操作呢?

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

file 源码如下:

file

file

2.3 总结:

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

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

3. Dict

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

3.1 Dict是什么?

Dict 由三部分组成,分别是:哈希表(DictHashTable)、哈希节点(DictEntry)、字典(Dict)

file

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

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

file

Dict 由三部分组成,分别是:哈希表(DictHashTable)、哈希节点(DictEntry)、字典(Dict) file

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 的 2^n^
  • 收缩大小为第一个大于等于 used 的 2^n^
  • Dict 采用渐进式 rehash,每次访问 Dict 时执行一次 rehash
  • rehash 时 ht [0] 只减不增,新增操作只在 ht [1] 执行,其它操作在两个哈希表

4. ZipList

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

4.1 ZipList 是什么?

file file

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 个字节,浪费内存。而是采用了下面的结构:

file

  • 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 个字节即可表示,如图所示:

file

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

4.4 总结:

ZipList 特性:

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

5. QuickList

5.1 QuickList 是什么?

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

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

file

为了避免 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:

file

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

file

5.2 QuickList 内存布局

file

5.3 总结:

QuickList 的特点:

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

6. SkipList

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

6.1 SkipList 是什么?

SkipList(跳表)首先是链表,但与传统链表相比有几点差异:

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

file

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。

!file

  • 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

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

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

转载请注明出处!

展开阅读全文
  • 0
    感动
  • 0
    路过
  • 0
    高兴
  • 0
    难过
  • 0
    搞笑
  • 0
    无聊
  • 0
    愤怒
  • 0
    同情
热度排行
友情链接