Redis 9 种数据结构简述

目录一、简介二、Redis 内部编码三、5种最基本数据结构1. String（字符串）1.1 内部编码1.2 应用1.3 数据结构1.3.1 什么是简单动态字符串(SDS)1.3.2 SDS 的数据结构1.3.3SDS 与 C语言字符串的区别1.3.3.1 获取字符串长度1.3.3.2 杜绝缓冲区溢出1.3.3.3 减少修改字符串时带来的内存重分配次数1.3.3.3.1 空间预分配1.3.3.3.

武大志

13072人浏览 · 2021-08-05 13:24:06

武大志 · 2021-08-05 13:24:06 发布

一、简介

redis 9种数据结构由5种最基本的数据结构（String、List、Hash、Set、Sorted Set（zset）） 加 bitmap、geohash、hyperloglog、streams 组成。

二、Redis 内部编码

我们常说的 String、List、Hash、Set、Sorted Set（zset）只是对外的编码，实际上每种数据结构都有自己底层的内部编码，而且不止一种，这样就可以在合适的场景下选择合适的内部编码。

内部编码如图（图片纠正：intset编码，而不是inset编码）：

在这里插入图片描述

三、5种最基本数据结构

Redis有5种数据结构，分别为：string(字符串)、list(列表)、set(集合)、hash(哈希)、zset(有序集合)。

Redis 所有的数据结构都是以唯一的 key 字符串作为名称，然后通过这个唯一 key 值来获取相应的 value 数据。不同类型的数据结构的差异就在于 value 的结构不一样。

1. String（字符串）

1.1 内部编码

String 3种内部编码：int、embstr、raw：

int编码：当一个key的value是整型时，Redis就将其编码为int类型（另外还有一个条件：把这个value当作字符串来看，它的长度不能超过20，保存的是可以用 long 类型表示的整数值）。这种编码类型为了节省内存。Redis默认会缓存10000个整型值（#define OBJ_SHARED_INTEGERS 10000），这就意味着，如果有10个不同的KEY，其value都是10000以内的值，事实上全部都是共享同一个对象。
embstr编码：保存长度小于44字节的字符串（redis3.2版本之前是39字节，之后是44字节）。
raw编码：保存长度大于44字节的字符串（redis3.2版本之前是39字节，之后是44字节）。

int 编码是用来保存整数值，raw 编码是用来保存长字符串，而embstr是用来保存短字符串。其实 embstr 编码是专门用来保存短字符串的一种优化编码，raw 和 embstr 的区别如下图：
在这里插入图片描述
embstr与raw都使用redisObject和sds保存数据，区别在于，embstr的使用只分配一次内存空间（因此redisObject和sds是连续的），而raw需要分配两次内存空间（分别为redisObject和sds分配空间）。因此与raw相比，embstr的好处在于创建时少分配一次空间，删除时少释放一次空间，以及对象的所有数据连在一起，寻找方便。而embstr的坏处也很明显，如果字符串的长度增加需要重新分配内存时，整个redisObject和sds都需要重新分配空间，因此redis中的embstr实现为只读。

PS：Redis中对于浮点数类型也是作为字符串保存的，在需要的时候再将其转换成浮点数类型。

编码的转换：

当 int 编码保存的值不再是整数，或大小超过了long的范围时，自动转化为raw。
对于 embstr 编码，由于 Redis 没有对其编写任何的修改程序（embstr 是只读的），在对embstr对象进行修改时，都会先转化为raw再进行修改，因此，只要是修改embstr对象，修改后的对象一定是raw的，无论是否达到了44个字节。

1.2 应用

string 结构使用非常广泛，最常见的就是缓存用户信息。将用户信息结构体使用JSON序列化成字符串，存入 redis 中。获取时再将 value 反序列化成目标对象。

因为string 类型是二进制安全的，可以用来存放图片，视频等内容，另外由于Redis的高性能读写功能，而string类型的value也可以是数字，可以用作计数器（INCR,DECR），比如分布式环境中统计系统的在线人数，秒杀等。

1.3 数据结构

string 是 redis 最简单的数据结构，由一个 key - value 组成。

Redis 的字符串是简单动态字符串(SDS)，是可以修改的字符串，内部结构实现上类似与 java 的 ArrayList，采用预分配冗余空间的方式来减少内存的频繁分配。当字符串长度小于 1M 时，扩容都是加倍现有的空间，如果超过 1M，扩容时一次只会多扩 1M 的空间。需要注意的是字符串最大长度为 512M。

1.3.1 什么是简单动态字符串(SDS)

简单动态字符串(SDS)，即：simple dynamic string。
Redis 没有直接使用 C 语言传统的字符串表示，而是自己构建了一种简单动态字符串的抽象类型，并将 SDS 用作 Redis 的默认字符串表示。

1.3.2 SDS 的数据结构

struct sdshdr {
    // 记录buf数组中已使用字节的数量
    // 等于SDS所保存字符串的长度
    int len;
    
    // 记录buf数组中未使用字节的数量
    int free;
    
    // 字节数组，用于保存字符串
    char buf[];
};

SDS 内存块结构

free = 0：表示这个 SDS 没有分配任何未使用空间；
len = 4：表示这个 SDS 保存了一个四字节长的字符串；
buf：是一个 char 类型的数组，最后一个字节和C语言字符串一样，保存了空字符 ‘\0’。

SDS 遵循 C 语言字符串以空字符结尾的惯例，保存空字符的 1 字节不计算在 SDS 的 len 属性里面，并且为空字符分配额外的 1 字节空间，以及添加空字符到字符串末尾等操作，都是由 SDS 函数自动完成的。

1.3.3 SDS 与 C语言字符串的区别

1.3.3.1 获取字符串长度

C语言字符串
因为C 语言字符串本身不记录长度信息，所以为了获取字符串长度，程序必须遍历整个字符串，直到遇到 \0 结束符为止，所以它获取长度的复杂度为：O(N)。

SDS
从 SDS 的数据结构中可知道，它用 len 字段保存了字符串的长度，所以获取一个 SDS 长度的复杂度为：O(1)。

1.3.3.2 杜绝缓冲区溢出

C语言字符串
<string.h>strcat 函数可以将 src 字符串中的内容拼接到 dest 字符串的末尾：
char *strcat(char *dest, const char *src)

假设某个程序中有两个在内存中紧邻着的 C字符串 s1 和 s2，其中 s1 保存了字符串 Redis，而 s2 则保存了字符串 MongoDB，如图所示：
在这里插入图片描述
那么在执行 strcat(s1, ‘Cluster’) 时，如果没有为 s1 分配足够的空间，那么在执行 strcat 方法后，s1 的数据将溢出到 s2 所在的空间中，导致 s2 保存的内容被意外地修改。如图：

在这里插入图片描述

SDS
当 SDS API 需要对 SDS 进行修改时，API 会先检查 SDS 的空间是否满足修改所需的要求，如果不满足的话，API 会自动将 SDS 的空间扩展至执行修改所需的大小，然后才执行实际的修改操作，所以不会出现C语言字符串中的缓冲区溢出问题。

1.3.3.3 减少修改字符串时带来的内存重分配次数

C语言字符串
因为 C 字符串并不记录自身长度，且末尾总是包含 \0 的结束符。所以，每次增长或者缩短一个 C 字符串，程序都要对保存这个 C 字符串的数组进行一次内存重分配操作。

如果程序执行的是增长字符串的操作，那么在执行之前，需要先通过内存重分配来扩展底层数组的大小，不然会产生缓冲区溢出的问题。
如果程序执行的是缩短字符串的操作，那么在执行之后，需要通过内存重分配来释放字符串的空闲空间，不然会产生内存泄漏的问题。

SDS
为了避免 C 字符串存在的问题，SDS 通过未使用空间解除了字符串长度和底层数组长度之间的关联：在 SDS 中，buf 数组的长度不一定就是字符数量加一，数组里面可以包含未使用的字节，而这些字节的数量就由 free 属性记录。
通过未使用空间，SDS 实现了空间预分配与惰性空间释放两种优化策略。

1.3.3.3.1 空间预分配

空间预分配用于优化 SDS 的字符串增长操作：当 SDS API 对一个 SDS 进行修改，并且需要对 SDS 进行空间扩展的时候，程序不仅会为 SDS 分配修改所必须的空间，还会为 SDS 分配额外的未使用空间。
预分配的空间大小由以下公式决定：

如果对 SDS 进行修改之后，SDS 的长度小于 1MB。那么程序会分配和 len 属性同样大小的未使用空间。如：修改后，SDS len = 10 字节 < 1 MB，那么程序会额外分配多 10 字节。所以最终结果为：10 + 10 + 1 = 21 字节。
如果对 SDS 进行修改之后，SDS 的长度大于 1MB，那么程序将分配 1MB 的未使用空间。

通过空间预分配策略，Redis 可以减少连续执行字符串增长操作所需要的的内存重分配次数。

1.3.3.3.2 惰性空间释放

惰性空间释放用于优化 SDS 的字符串缩短操作：当 SDS API 需要缩短 SDS 保存的字符串时，程序不会立即使用内存重分配来回收缩短后多出来的字节，而是使用 free 属性将这个字节的数量记录起来，并等待将来使用。

1.3.3.4 获取字符串长度

C语言字符串
C 字符串中的字符必须符合某种编码（比如：ASCII），并且除了字符串的末尾之外，字符串里面不能包含空字符，否则最先被程序读入的空字符将被误认为是字符串的结尾。有着这个限制，使得 C 字符串只能保存文本数据，而不能保存像图片、音频、视频、压缩文件这样的二进制数据。

SDS
SDS API 都是二进制安全的，所有的 SDS API 都会以处理二进制的方式来处理 SDS 存在在 buf 数组里的数据。

1.3.3.5 兼容部分 C 字符串函数

虽然 SDS API 都是二进制安全的，但它们一样遵循 C 字符串以空字符结尾的惯例：这些 API 总会将 SDS 保存的数据的末尾设置为空字符，并且总会在为 buf 数组分配空间时多分配一个字节来容纳这个空字符，为的就是让 SDS 可以重用一部分<string.h>库定义的函数。

1.3.3.5 总结

在这里插入图片描述

1.4 命令使用

如果 value 值是一个整数，还可以对它进行自增操作。自增是有范围的，它的范围是 signed long 的最大最小值，超过了这个值，Redis 会报错。

> set name code  # 设置，成功返回 ok
> get name       # 获取，不存在返回 nil
> mset name1 code1 name2 code2 # 批量设置
> mget name1 name2 # 批量获取
> exists name    # 是否存在，1:存在；0:不存在
> del name       # 删除，1:成功
> expire name 5  # 设置过期时间
> setex name 5 code # 等价于 set + expire
> setnx name code   # 如果name不存在，则创建，存在，则创建失败返回 0
> incr name # 对name++
> incrby name 5 # 对name + n