Redis 篇-深入了解 Redis 五种数据类型和底层数据结构（SDS、Intset、Dict、ZipList、SkipList、QuickList）
每次执行新增、查询、修改、删除操作时，都检查一下 dict.rehashidx 是否大于 -1，如果是则将 dict.ht[0].table[rehashidx] 的 entry 链表 rehash 到 dict.ht[1]，并且将 rehashidx++。：如果当前层已经达到目标值或找到了更大的值，改变层级，将 current 指针向下移动到下一层。5）将 dict.ht[1] 赋值给 dict
🔥博客主页： 【小扳_-CSDN博客】
❤感谢大家点赞👍收藏⭐评论✍
文章目录
1.0 Redis 底层数据结构
在 Redis 的底层实现中，除了高层的抽象数据结构（如字符串、哈希、列表、集合等）之外，还有一些更底层的原始数据结构。
1.1 Redis 数据结构 - 动态字符串 SDS
简单动态字符串，简称 SDS 。
Redis 是 c 语言实现的，其中 SDS 是一个结构体，结构如下：
字段解析：
1）uint8_t len：表示 buf 字符数组中已经保存的字符个数，因为一个字符占一个字节，也可以表示已保存的字节数，且不包含结束标识： "\0" 。uint8_t 代表 len 占用了 8 个比特位，也就是一个字节，因此表示 buf 字符数组的最大容量为 2^8 。
2）uint8_t alloc：表示 buf 字符数组申请的总的字节数，同理，且不包含结束标识："\0" 。
3）unsigned char flags：表示不同 SDS 的类型，用来控制 SDS 的头大小，一共有五种类型。不同的 SDS 类型，可以表示 buf 的容量大小不同。
4）char buf[]：字符数组，存放真实数据的容器。
举个例子：
一个包含字符串 "name" 的 SDS 结构体如下：
SDS 之所以叫做动态字符串，是因为它具备动态扩容的能力：
1）如果新字符串小于 1 M，则新空间为扩展后字符串长度的两倍 + 1 。
2）如果新字符串大于 1 M，则新空间为扩展后字符串长度 + 1M + 1，称为内存预分配。
举个例子：
一个原本的字符串数组为 "hi" 的 SDS 结构为：
接着，假如追加一段字符串 ",Amy"，这里首先会申请新的内存空间：
由于 "hi,Amy" 加起来的大小为 6 个字节，小于 1M，因此需要扩展至 13 个字节大小即可。
新的字符数组的 SDS 结构如下：
关于 alloc 为什么不是 13 个字节呢？
这是因为 alloc 表示申请大小不包含结束标识 "\0"，实际上，是扩展至 13 个字节大小。
动态字符串 SDS 的优点：
1）获取字符串长度的时间复杂度为 O(1) 。
2）支持动态扩容。
3）由于支持内存预分配机制，因此减少内存分配次数。
4）由于表示了字符数组的总长度，因此明确结束标识的具体位置，所以二进制安全。
1.2 Redis 数据结构 - Intset
IntSet 是 Redis 中 set 集合的一种实现方式，基于整数数组来实现，并且具备长度可变、有序等特征。
IntSet 结构如下：
字段解析：
1）uint32_t encoding：编码方式，支持存放 16、32、64 位整数。该字段的目的是规定在整数数组中的每一个数据的范围大小。
2）uint32_t length：元素个数，表示的范围由 encoding 编码方式决定。
3）int8_t cotents[]：具体存放的数据，每一个数据的范围大小都是由 encoding 编码方式来决定的。
为了方便查找，Redis 会将 intset 中所有的整数按照升序依次保存在 contents 数组中，结构如下：
现在数组中每个数字都是在两个字节的范围内，因此采用的编码方式是 INTSET_ENC_INT16，每部分占用的字节大小为：
encoding：固定占用 4 个字节。
length：固定占用 4 个字节。
contents：2 字节 * 3 = 6 个字节。
IntSet 升级：
当要插入的数字大小当前整数所表示的范围时，intset 会自动升级编码方式到合适大小。
现在，假设有一个 intset，元素为：{5，10，20}，采用的编码是 INTSET_ENC_INT16，则每个整数占 2 个字节，接着向其中添加一个数字 50000，这个数字超出了 int16_t 的表示范围，intset 会自动升级编码方式到合适的大小，流程如下：
1）升级编码为 INTSET_ENC_INT32，每个整数占 4 个字节，并按照新的的编码方式及元素个数扩容数组。
2）倒叙依次将数组中的元素拷贝到扩容后的正确位置。
3）将待添加的元素放入数组末尾。
4）最后，将 intset 的 encoding 属性改为 INTSET_ENC_INT32，将 length 属性改为 4 。
IntSet 可以看做是特殊的整数数组，具备的特点：
1）Redis 会确保 Intset 中的元素唯一、有序。
2）具备类型升级机制，可以节省内存空间。
3）底层采用二分查找方式来查询。
1.3 Redis 数据结构 - Dict
Redis 是一个键值型的数据库，可以根据键实现快速的增删改查。而键与值的映射关系正是通过 Dict 来实现的。
Dict 由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）。
哈希表和哈希节点的结构体：
哈希表由数组和链表组成，而链表节点则为哈希点。
字段解析：
1）dictEntry **table：表示指针指向哈希表的地址。
2）unsigned long size：哈希表大小，哈希表的大小总是设置为： 2^n 次方，最小的哈希表为 4 。
3）unsigned long sizemask：哈希表大小的掩码，总等于 size - 1，用来计算哈希点具体存放在数组的哪一个索引下的链表中。
当向 Dict 添加键值对时，Redis 首先根据 key 计算出 hash 值，然后利用 hash 值 & sizemask 来计算元素应该存储数组中的哪个索引位置，最后再进行头插链表的方式存储起来。
4）unsigned long used：哈希节点的个数。
5）void *key：指向 key 的地址。
6）union{} value：联合体，表示 value 的类型。
7）struct dictEntry *next：指向下一个节点。
字典的结构体：
字段解析：
1）dictType *type：dict 类型，内置不同的 hash 函数。不用太在意该字段，了解即可。
2）void *privdata：私有数据，在做特殊 hash 运算时用。不用太在意该字段，了解即可。
3）dictht ht[2]：一个 Dict 包含两个哈希表，其中一个是当前数据，另一个一般是空，rehash 时使用。在扩容或者收缩数组大小会使用该字段。
4）long rehashidx：rehash 的进度，-1 表示未进行。
5）int16_t pauserehash：rehash 是否暂停，1 则暂停，0 则继续。
最终的结构：
1.3.1 Dict 的渐进式 rehash
Dict 中的 HashTable 就是数组结合单向链表的实现，当集合中元素较多时，必然导致哈希冲突增多，链表过长，则查询效率会大大降低。
负载因子：LoadFactor = used / size ；
Dict 在每次新增键值对时都会检查负载因子，满足以下两种情况时会触发哈希表扩容：
1）哈希表的 LoadFactor >= 1，并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程。
2）哈希表的 LoadFactor > 5 。
Dict 除了扩容以外，每次删除元素时，也会对负载因子做检查，当 LoadFactor < 0.1 时，会做哈希表收缩。
不管是扩容还是收缩，必定会创建新的哈希表，导致哈希表的 size 和 sizemask 变化，而 key 的查询与 sizemask 有关。因此必须对哈希表中的每一个 key 进行重新计算索引，插入新的哈希表，这个过程为 rehash，过程如下：
1）计算新 hash 表的 realeSize，值取决于当前要做的是扩容还是收缩：
如果是扩容，则新 size 为第一个大于等于 dict.ht[0].used + 1 的 2^n。
如果是收缩，则新 size 为第一个大于等于 dict.ht[1].used 的 2^n（不得小于 4）
2）按照新的 realeSize 申请内存空间，创建 dictht，并赋值给 dict.ht[1]。
3）设置 dict.rehashidx = 0，标示开始 rehash 。
4）每次执行新增、查询、修改、删除操作时，都检查一下 dict.rehashidx 是否大于 -1，如果是则将 dict.ht[0].table[rehashidx] 的 entry 链表 rehash 到 dict.ht[1]，并且将 rehashidx++ 。直至 dict.ht[0] 的所有数据都 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.4 Redis 数据结构 - ZipList
ZipList 是一种特殊的 "双端链表"，由一系列特殊的编码连续内存块组成。可以在任意一端进行压入/弹出操作，并且该操作的时间操作复杂度为：O(1) 。
字段解析：
1）zlbytes：4 个字节，记录整个压缩列表占用的内存字节数。
2）zltail：4 个字节，记录压缩列表表尾节点距离压缩列表的起始地址有多少字节，通过这个偏移量，可以确定表尾节点的地址。
3）zllen：2 个字节，记录了压缩列表包含的节点数量。最大值为 UINT16_MAX(65534)，如果超过这个值，此处会记录为 65535，但节点的真实数量需要遍历整个压缩列表才能计算得出。
4）entry：长度不定，压缩列表包含的各个节点，节点的长度由节点保存的内容决定。
5）zlend：1 个字节，特殊值 0xFF（十进制 255），用于标记压缩列表的末端。
ZipList 中的 entry 并不像普通链表那样记录前后节点的指针，因为记录两个指针要占用 16 个字节，浪费内存。而是采用如下结构：
字段解析：
1）previous_entry_length：前一节点的长度，占 1 个或者 5 个字节：
如果前一节点的长度小于 254 字节，则采用 1 个字节来保存这个长度值。
如果前一节点的长度大于 254 字节，则采用 5 个字节来保存这个长度值，第一个字节为 0xfe，后四个字节才是真实长度数据。
2）encoding：编码属性，记录 content 的数据类型（字符串还是整数）以及长度，占用 1 个、2 个或者 5 个字节。
编码分为字符串和整数两种：
字符串：如果 encoding 是以 "00"、"01" 或者 "10" 开头，则证明 content 是字符串；
举个例子：
整数：如果 encoding 是以 "11" 开始，则证明 content 是整数，且 encoding 固定只占用 1 个字节。
举个例子：
3）contents：负责保存节点的数据，可以是字符串或者整数。
ZipList 特征：
1）压缩列表的可以看做一种连续内存空间的"双向链表"。
2）列表的节点之间不是通过指针连接，而是记录上一个节点和本节点长度来寻址，内存占用较低。
3）如果列表数据过多，导致链表过长，可能影响查询性能。
4）增或删较大数据时有可能发生连续更行问题。
1.5 Redis 数据结构 - QuickList
ZipList 虽然节省内存，但申请内存必须是连续空间，如果内存占用较多，申请内存效率很低，该怎么办呢？
这就不得不引入新的数据结构 QuickList，它是一个双端链表，只不过链表中的每个节点都是一个 ZipList，结构如下：
1）为了避免 QuickList 中的每个 ZipList 中 entry 过多，Redis 提供了一个配置项：list-max-ziplist-size 来限制。
如果值为正，则代表 ZipList 的允许的 entry 个数的最大值。
如果值为负，则代表 ZipList 的最大内存大小，分五种情况：
-1：每个 ZipList 的内存占用不能超过 4 kb；
-2：每个 ZipList 的内存占用不能超过 8 kb；
-3：每个 ZipList 的内存占用不能超过 16 kb；
-4：每个 ZipList 的内存占用不能超过 32 kb；
-5：每个 ZipList 的内存占用不能超过 64 kb；
其默认值为：-2
2）除了控制 ZipList 的大小，QuickList 还可以对节点的 ZipList 做压缩。通过配置项 list-compress-depth 来控制。因为链表一般都是从首尾访问较多，所以首尾是不压缩的。
0：特殊值，代表不压缩。
1：标示 QuickList 的首尾各有 1 个节点不压缩，中间节点压缩。
2：标示 QuickList 的首尾各有 2 个节点不压缩，中间节点压缩。
以此类推......
默认值是 0 ，不压缩节点。
QuickList 与 QuickListNode 的结构源码：
结构如下：
QuickList 的特点：
1）是一个节点为 ZipList 的双端链表
2）节点采用 ZipList，解决了传统链表的内存占用问题。
3）控制了 ZipList 大小，解决连续内存空间申请效率问题。
4）中间节点可以压缩，进一步节省内存。
1.6 Redis 数据结构 - SkipList
首先是链表，但与传统链表相比有以下差异：
1）元素按照升序排序存储。
2）节点可能包含多个指针，指针跨度不同。
在跳表中查找目标数据的步骤：
1）初始化指针：从跳表的最高层的头节点开始，初始化一个指针（通常称为 current）。
2）向右移动：在当前层中，检查 current 节点的下一个节点的值。如果这个值小于目标值，则将 current 指针移动到下一个节点。
3）找到合适的位置：如果下一个节点的值大于或等于目标值，或者已经到达当前层的末尾，则停止此层的移动。
4）向下移动：如果当前层已经达到目标值或找到了更大的值，改变层级，将 current 指针向下移动到下一层。如果目标值小于当前层的下一个节点的值， 则在这一层的当前节点停止查找，进入下一层按步骤 2 进行查找。
5）重复步骤：重复步骤 2 到步骤 4，直到找到目标值或到达底层。如果找到了目标值，则查找成功；
如果到达底层且没有找到目标值：
在底层，检查当前节点的值。
如果当前节点的值等于目标值，则查找成功。
如果当前节点的值小于目标值，继续移动到下一个节点。
如果当前节点的值大于目标值，停止查找。
SkipList 结构源码：
SkipList 结构：
SkipList 的特点：
1）跳跃表是一个双向链表，每一个节点都包含 score 和 ele 值。
2）节点按照 score 值排序，score 值一样则按照 ele 字典排序。
3）每一个节点都快包含多层指针，层数是 1 到 32 之间的随机数。
4）不同层指针到下一个节点的跨度不同，层级越高，跨度越大。
5）增删改查效率与红黑树基本一致，实现却更简单。
1.7 Redis 数据结构 - RedisObject
Redis 中的任意数据类型的键和值都会被封装为一个 RedisObject，也叫做 Redis 对象，源码如下：
字段解析：
1）unsigned type：对象类型，可以是 string、hash、list、set、zset，占用 4 个 bit 位。
2）unsigned encoding：底层编码方式，共有 11 种，占 4 个 bit 位。
3）int refcount：对象引用计数器，计数器为 0 则说明对象无人引用，可以被回收。
4）void *ptr：指针，指向存放实际数据的空间。
5）unsigned lru：lru 表示该对象最后一次被访问的时间，其占用 24 个 bit 位。便于判断空闲时间太久的 key 。
Redis 中会根据存储的数据类型不同，选择不同的编码方式。每种数据类型的使用的编码方式如下：
2.0 数据类型
常见的五种数据类型：String、List、set、zset、hash，以下介绍这五种的数据类型，底层用到的数据结构：
2.1 数据类型 - String
String 是 Redis 中最常见的数据存储类型：
1）其基本编码方式是 RAW，基于简单动态字符串（SDS）实现，存储上限为 512 mb 。
结构如下：
2）如果存储的 SDS 长度小于 44 字节，则会采用 EMBSTR 编码，此时 object head 与 SDS 是一段连续空间。申请内存时只需要调用一次内存分配函数，效率更高。
结构如下：
3）如果存储的字符串是整数值，并且大小在 LONG_MAX 范围内，则会采用 INT 编码：直接将数据保存在 RedisObject 的 ptr 指针位置(刚刚好 8 字节)，不再需要 SDS 了。
结构如下：
2.2 数据类型 - List
Redis 的 List 结构类似一个双端链表，可以从首尾操作列表中的元素：
在 3.2 版本之前，Redis 采用 ZipList 和 LinkedList 来实现 List，当元素数量小于 512 并且元素大小小于 64 字节时采用 ZipList 编码，超过则采用 LinkedList 编码。
在 3.2 版本之后，Redis 统一采用 QuickList 来实现 List：
整体结构：
2.3 数据类型 - Set
Set 是 Redis 中的单列集合，满足下列特点：
1）不保证有序性
2）保证元素唯一（可以判断元素是否存在）
3）求交集、并集、差集
因此：
如果为了查询效率和唯一性，set 采用 HT 编码（Dict）。Dict 中的 key 用来存储元素，value 统一为 null 。
结构如下：
如果存储的所有数据都是整数，并且元素数量不超过 set-max-intset-entries 时，Set 会采用 IntSet 编码，以节省内存。
结构如下：
相关的源码：
2.4 数据类型 - ZSet
ZSet 也就是 SortedSet，其中每一个元素都需要指定一个 score 值和 member 值。
其特点：可以根据 score 值排序、member 必须唯一、可以根据 member 查询分数。
因此：
zset 底层数据结构必须满足键值存储、键必须唯一，可排序：
1）SkipList：可以排序，并且同时存储 score 和 ele 值（member）
2）HT（Dict）：可以键值存储，并且可以根据 key 找 value
源码如下：
整体结构：
当元素数量不多时，HT 和 SkipList 的优势不明显，而且更耗内存。因此 zset 还会采用 ZipList 结构来节省内存，不过需要同时满足两个条件：
1）元素数量小于 zset_max_ziplist_entries，默认值 128
2）每个元素都小于 zset_max_ziplist_value 字节，默认值 64
源码如下：
思考：ziplist 本身没有排序功能，而且没有键值对的概念，因此需要有 zset 通过编码实现：
1）ZipList 是连续内存，因此 score 和 element 是紧挨在一起的两个 entry，element 在前，score 在后。
2）score 越小越接近队首，score 越大越接近队尾，按照 score 值升序排序。
整体结构如下：
2.5 数据类型 - Hash
Hash 结构与 Redis 中的 Zset 非常类似：都是键值存储、都要求根据键获取值、键必须唯一。
因此：
Hash 结构默认采用 ZipList 编码，用以节省内存。ZipList 中相邻的两个 entry 分别保存 field 和 value 。
结构如下：
当数据量较大，Hash 结构会转为 HT 编码，也就是 Dict，触发条件有两个：
1）ZipList 中的元素数量超过了 hash-max-ziplist-entries（默认 512）
2）ZipList 的任意 entry 大小超过了 hash-max-ziplist-value（默认 64 字节）
结构如下：
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
91
0- 0
已为社区贡献14条内容
所有评论(0)