Redis9种数据结构简述

目录

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

参考1：Redis学习（一）简单动态字符串(SDS)

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

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

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

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 &＃8211; 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语言字符串
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 可以重用一部分库定义的函数。

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