【redis】redis 基本数据结构之String

╰+攻爆jí腚メ 2022-09-16 03:52 156阅读 0赞

> 推荐经典的redis书 《Redis 设计与实现》，讲的非常好！

### 文章目录 ###

*  简单动态字符串
 *   *  SDS 与 C 字符串的区别
     *  获取 SDS 长度时间复杂度为 O（1）
     *  防止缓冲区溢出
     *  减少修改字符串时带来的内存重分配次数
     *   *  增长SDS之空间预分配
         *  缩减SDS之惰性空间释放
     *  二进制安全

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5piv6aaE6aWo5ZGA_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]

# 简单动态字符串 #

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

SDS的定义

每个sds.h/sdshdr结构表示一个SDS值

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5WAlzGGi-1634222389877)(../images/image-20211013180130005.png)\]][img-5WAlzGGi-1634222389877_.._images_image-20211013180130005.png]

> SDS字符串结构体记录了**所用字符的长度len**，**空闲字符的长度**以及**字符数组**

## SDS 与 C 字符串的区别 ##

## 获取 SDS 长度时间复杂度为 O（1） ##

（1）C 语言中没有记录字符串长度，如果获取字符串长度，要从头遍历，时间复杂度为O（N），大大降低了性能的瓶颈，而SDS可以直接获取其len，时间复杂度为O（N）。

## 防止缓冲区溢出 ##

（2）防止缓冲区溢出。在 C 语言中，<String.h>/strcat函数可以将src字符串中的内容拼接到 dest 字符串的末尾；

char *stacat(char *dest,const char *src)

因为 C 字符串不记录自身的长度，所以 strcat 假定用户在执行这个函数时，已经为 dest 分配了足够多的内存，可以容纳 src 字符串中的所有内容，但是一旦内存不够，那么就会产生缓冲区溢出。

例如：程序中有两个内存紧临的字符串 S1 和 S2，S1 为“Redis”，S2为“MongoDB”

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eS76F1rk-1634222389880)(../images/image-20211013183106844.png)\]][img-eS76F1rk-1634222389880_.._images_image-20211013183106844.png]

现在用 strcat （s1，“Cluster”）去拼接，发现s1的内存已经满了，那么在拼接时数据就会溢出到S2的空间中，导致数据的更改。

与 C 字符串不同，SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性：当SDS API需要对 SDS 进行修改的时候，API 会先检查 SDS 的空间是否满足修改所需的要求，如果不满足，则会扩充至执行修改所需要的大小，所以不会出现缓冲区溢出问题。

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

我们知道 C 字符串不记录自身的长度，所以对于一个包含了 N 个字符的 C 字符串来说，这个 C 字符串的底层实现总是一个 N+1 个字符长的数组。因为 C 字符串的长度和底层数组的长度之间存在着这种关联性，所以每次增长或者缩短一个字符串，都需要重新进行内存分配。

>  *  如果执行的是增长操作的话，在操作之前，需要先通过内存分配来扩充数组的空间大小，如果忘了，那么就会出现缓存区溢出。
>  *  如果执行的是缩短操作的话，在操作之后，需要先通过内存分配来释放不在使用的那部分空间，如果忘了，就会引起内存泄漏。
>  *  如果修改字符串长度的情况不经常出现，那么每次修改都执行一次内存分配还是可以接受的，但是我们redis主要是用来做缓存，那么频繁的修改，导致内存分配占用大量时间，还可能对性能造成影响。

SDS 中针对这个问题进行了处理。

### 增长SDS之空间预分配 ###

当对 SDS 进行扩展时，程序不仅会为SDS分配修改所必须的空间，还会为SDS 分配额外的未使用的空间，也就是我们在结构体中看到的 free 的大小。

*  当修改 SDS 之后，SDS 的长度（len）小于 1MB，那么程序分配和 len 属性同样大小的未使用空间，这时 SDS len 属性的值会和 free 属性的值相同。比如 len 为 13，那么free 也为13，那么数组的总长度大小就为 13 + 13 + 1 =27（1 为末尾的空字符‘\\0’）
 *  当修改 SDS 之后，SDS 的长度大于 1 MB，那么程序会分配 1MB的未使用空间。比如 len 的长度为 30 MB，那么会分配 1 MB 的未使用空间，SDS 的 buf 数组的实际长度为 30 MB + 1 MB + 1 byte。

在扩展 SDS 空间之前，SDS API 会先检查未使用空间是否足够，如果足够的话，就会直接使用未使用的空间，不会进行内存重分配。

### 缩减SDS之惰性空间释放 ###

我们在对 SDS 进行删除的时候，并不是立即使用内存重分配来回收缩短后多出来的字节，而是使用 free 属性将这些字节的数量记录起来，并等待将来使用。

比如对于下面 SDS 值来说

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wi2Dacl8-1634222389881)(../images/image-20211014222645613.png)\]][img-wi2Dacl8-1634222389881_.._images_image-20211014222645613.png]

删除SDS 字符串中的所有 X 和 Y。

那么删除以后是这个样子

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DOpXqy7c-1634222389883)(../images/image-20211014222736165.png)\]][img-DOpXqy7c-1634222389883_.._images_image-20211014222736165.png]

会发现我们的剩余空间并没有被删除，而是为将来可能有的增长操作提供了优化。

## 二进制安全 ##

C 字符串中的字符必须符合某种编码（比如 ASCII），并且在字符串的末尾，字符串里面不能包含空字符，否则会认为是结束标识符，这些限制使得 C 字符串只能保存文本数据，而不能保存像图片，音频，视频，压缩文件这样的二进制。

为了确保 Redis 可以适用于各种不同的使用场景，所有 SDS API 都会以处理二进制的方式来处理 SDS 存放在buf 数组中的数据，不会对其中的数据做任何限制，也就是写入时是什么样子，读还是什么样子。

SDS 使用 len 属性的值来判断字符串是否结束，而不是通过空字符串来进行判断，使得 Redis 不仅可以保存文本数据，还可以保存任意格式的二进制数据。

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5piv6aaE6aWo5ZGA_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220828/c3385f8e018e4c6bbfddc36c988da429.png
[img-5WAlzGGi-1634222389877_.._images_image-20211013180130005.png]: /images/20220828/d7eede11e8614a3798a9218468b1ca49.png
[img-eS76F1rk-1634222389880_.._images_image-20211013183106844.png]: /images/20220828/7e984b6ea50449f29a9494256174bc73.png
[img-wi2Dacl8-1634222389881_.._images_image-20211014222645613.png]: /images/20220828/46d0adf128264822ba8af14951aaf319.png
[img-DOpXqy7c-1634222389883_.._images_image-20211014222736165.png]: /images/20220828/0793ed1f419347aca428d089dfd95b3f.png