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

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

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

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

SDS的定义

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

比如对于下面 SDS 值来说

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

那么删除以后是这个样子

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

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

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

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