带你解析Redis的数据类型及底层原理

曾经终败给现在 2024-03-22 11:49 58阅读 0赞

Redis有丰富的数据类型，但最基本也是最常见的有下面五种：String、List、Set、Hset、Zset

数据类型整体来说会比较杂且枯燥一点，但是其在Redis中作用非常之大，为什么Redis能那么快呢，一方面来说因为其是内存型数据库，另外一方面也是因为其提供丰富的数据结构类型来加速性能。所以可以说这是学习Redis的第一关。

![format_png][]

1.整体结构的了解

首先，我们先来对数据类型有个整体轮廓的了解。Redis是一种key-value的存储结构，在Redis中，key和value都被抽象为了**对象**，key**只能**为string对象，而value则有多个，包括上文提到的五种基础数据类型以及Redis后续追加的四种数据类型。

在Redis这种对象的结构体如下：

![format_png 1][]

*  type：表示哪种对象
 *  encoding：表示底层的编码
 *  lru：记录了对象的访问信息。用于内存淘汰的，内存淘汰有8种策略，一种是lru，以及后面推出的lfu等等
 *  refcount：引用计数，描述多少个指针指向该对象
 *  ptr：内容指针，指向实际的内容

2.五种基本数据类型

① String

String对应的value可以是字符串，也可以是整形或者浮点型的数字，甚至是图片、视频、音频等二进制数据。value能容纳最大的数据长度为512M。 而同时我们也要去了解这些基本类型的底层实现以及编码方式。

String类型底层实现：**int**和**sds**（simple dynamic string）

String类型编码方式：**int**、**embstr**和**raw**

联系为：

![format_png 2][]

> int很好理解，因为上文说了String可以存数字，所以存在这种编码方式与实现。

> sds的引入，主要是c语言的字符串过于简单导致有些方面存在缺陷，而Redis又是C语言实现的。所以Redis又在此基础之上封装出了一个结构sds，正如那句计算机名言：没有什么问题不可以通过添加一层抽象来解决。

具体来说，C中的字符串

*  每次计算字符串长度的复杂度需要O(n)
 *  同时对字符串进行追加，需要重新分配内存
 *  非二进制安全

在Redis内部，字符串的追加以及返回长度是很常见的，而追求高性能的Redis肯定是不容许这些事情发生的，所以进行了结构的封装。sds又分为sds8,sds16,sds32,sds64,字段属性没有区别。结构如下：

![format_png 3][]

首先，记录了len字段，可以O（1）返回字符串的长度，同时alloc表示分配的内存，alloc-len就是预留空间，预留的空间为min(len,1M)。flags代表sds的分类，上面说了sds分为了4种。同时不再以‘\\0’作为结束标识，但内联数组最后会是'\\0'结尾，二进制安全，拼接字符串前也会检查空间是否满足要求，不会导致缓冲区溢出的问题。

而对于三种编码方式，当存储的字符串是整数值，且大小在long范围，则采用int编码方式实现int数据结构，而当字符串长度比较小，采用embstr编码，当超过一定的长度embstr会变为raw编码。这个阈值在3.2版本之前是39字节，3.2版本版本之后是44字节。对于embstr，它的RedisObject和sds是连续的，而raw下面这两个在内存是分开的。同时需要注意的是embstr被设置为了只读，任何写操作embstr都会变为raw，理念就是修改过的字符串通常认为是易变的，计算机的局部性原理。而对于embstr来说，它的RedisObject是连续的，耦合性更强，当需要重新分配embstr的时候，这两个部分需要重新分配，而对于raw来说，它的redisObject不需要重新分配。

> 关于阈值的数值，有兴趣的可以继续往下看： 首先，Redis使用了jemalloc作为内存分配器，jemalloc以64字节为阈值区分大小字符串，所以embstr的阈值其实是受64字节的影响。超过64字节就超过一个内存单元，会用raw编码，反之认为是一个小字符串，用embstr编码。接着分析：我们也知道这两种编码方式由RedisObject和sds两部分组成，分别分析即可。

*  对于RedisObject，其大小没有变过，大小为4+4+24+32+64=128bits=**16B**

![format_png 4][]

*  而对于sds，内存大小为**1B+1B+1B**\+内联数组大小，同时内联大小最后有一个'\\0'占一个字节。所以还剩下能用的大小就为：64-16-3-1=44

![format_png 5][]

而对于之前为什么是39呢？少了5个字节，首先，下图是之前的sds结构图：

![format_png 6][]

当时是通用的sds结构，没有细分为8,16,32,64。3.2之后的版本的embstr用的是sds8，总容量len少了3个字节，容量也减少了3个字节，总共减少了6个字节，但是多了个flag字段占用1个字节，所以相比于没有拆分sds结构来说，embstr的阈值会多5个字节。

② list

List 列表是简单的字符串列表，**按照插入顺序排序**，可以从头部或尾部向 List 列表添加元素。列表能存的元素就非常之多了，每个列表支持超过40亿个元素。

同样的看看其底层实现与编码方式：

其底层实现是通过压缩列表或双向链表实现的， 当为小列表的时候采用压缩列表，判断小的判断有两个维度，一个是列表数量小（512个），一个是列表元素占用字节少（64字节）。当不满足ziplist编码的条件会转为linkedlist编码（linkedlist底层是通过双向链表进行实现的），Redis作为一种内存型数据库，很多时候我感觉是在有限的内存以及性能的追求寻找一个平衡，提供多种数据结构。

Redis在3.2版本引进了一种新的数据结构quicklist，为什么呢，ziplist是为了在数据较少时节约内存，当数据稍多时插入数据会导致很多内存复制，而当linkedlist链表节点很多的话，又会占用很多内存，并不能很好的解决问题。quicklist是这两者的结合体。单个quicklist节点存的是ziplist，即多个数据，如下图：

![format_png 7][]

当数据较少的时候，quicklist的节点只有一个，此时相当于就是一个ziplist

当数据很多的时候，则同时利用了ziplist和linkedlist的优势。

ziplist本身存在一个连锁更新的问题，在Redis7.0之后，使用listpack的编码方式取代了ziplist，但本质都是一种压缩的列表，可以统称为压缩列表，主要是用来解决**连锁更新**的问题。

> 连锁更新的问题大家可以去了解一下ziplist中entry它的结构，这个结构里面有个prevlen属性导致了连锁更新的问题，它用来表示上一个节点的数据长度，通过它可以定位到上一个数据，也因此压缩列表才可以从后向前遍历，如果前一个节点的长度小于254字节（255是特殊字符，被zlend占用，表示ziplist的结束），这个属性占用一个字节，否则使用5个字节去保存长度值。连锁更新指的是后移操作不止发生了一次，而是发生了多次。比如说当插入一个节点，导致后面的数据进行了一次后移操作，同时，因为它的插入，原本后面结点的prevlen属性本来只占用一个属性，而现在变成了五个字节，结点膨胀之后又要逐步迭代更新。实际业务中，很少碰到需要迭代更新超过2个结点的情况，但这种情况的存在会使性能不稳定。当然也是从结点的结构定义下手，有一个element-tot-len属性表示存储整个结点除它自身之外的长度。规则如下：每个字节第一个bit标识是否结束，0是结束，省下7个bit存储数据大小。那么，我们如何从当前结点找到上一个结点的首位置呢，该结点首部即上个结点的element-tot-len属性（该属性在结点结构尾部），假如为（00000010 10000101）占用大小的字节为 0000010 0000101 —--十进制—> 261字节

③ set

Set是一个无序且不重复的字符串集合

同样的看看其底层实现与编码方式：

其底层实现是通过哈希表或整数集合实现的，出于性能与内存的综合考虑，set也支持两种编码方式，当元素都是整数且元素个数不超过512个，就用INTSET编码，否则用哈希表。哈希表能O（1）时间进行快速查询，而INTSET编码只能进行二分查询。

④ HSet/Hash

HSet是一个键值对集合，很适合拿来存储对象。比如任务信息对象，field可以设置为任务类型，value设置为任务配置参数。先来直观了解一下其结构，首先，它是一种**key-value集合**，但需要**注意**的是它的value形式是这样子的：`value=[{field1，value1}，...{fieldN，valueN}]`，比如说我们的购物车，永无id作为key，商品id作为field, 商品数量作为value

同样的HSet也有两种底层实现与编码方式：压缩列表和哈希表（压缩列表在较高的版本7.0已经完全是listpack了）

*  当哈希类型元素个数小于 `512` 个，field和value小于 `64` 字节，Redis 会使用**压缩列表**作为 Hash 类型的底层数据结构；
 *  如果哈希类型元素不满足上面条件，Redis 会使用**哈希表**作为 Hash 类型的 底层数据结构。

⑤ ZSet/SortedSet

ZSet比Set多了一个排序属性score，同样的value有两个值组成，一个是排序值，一个是元素值。当我们使用ZADD为集合添加元素，也是排序值在前，元素值在后。

![format_png 8][]

同样的ZSet也有两种底层实现与编码方式：**压缩列表**或**跳表+哈希表**

*  如果有序集合的元素个数小于 `128` 个，并且每个**元素值**小于 `64` 字节时，Redis 会使用**压缩列表**作为 Zset 类型的底层数据结构；（是不包括分数值占用的字节的，score入参的时候还是double,还不知道转换成字符串会占用多少字节）
 *  如果有序集合的元素不满足上面的条件，Redis 会使用**跳表+哈希表**作为 ZSet 类型的底层数据结构；

3.关系总结图

下面是针对Redis对外提供的五种基本类型与底层实现的数据结构的关系，图来源于网络。最后ZSet对应的跳表最好再加个哈希表。使得可以O（1）时间复杂度查询到成员的分数值。

![format_png 9][]

[format_png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/dca150b8826542e8bc76053a71b90cfd.png
[format_png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/209d60b2747840d5ab4e4b42f7957425.png
[format_png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/2d592b84ceb144e7bbd74d753e325ec0.png
[format_png 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/7db59d1f101f46d7b82aff3eb432bebe.png
[format_png 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/a341843fda5f43469f46ccad5e3fc8e9.png
[format_png 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/b6e4525e4e9d4e989f047d18727d6b48.png
[format_png 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/80ffd7bb6f61495c9f78636f5d8ca8b9.png
[format_png 7]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/a1fe406185234eb995228c2e53d6cfc7.png
[format_png 8]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/a2d0c12be3db492ea6c10da873055af1.png
[format_png 9]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/00a3f0842fe243518095e275fbe68462.png