redis没有直接使用c语言传统的字符串表示（以空字符结尾的字符数组），而是自己构建了一种“简单动态字符串”（simple dynamic string ，SDS）用作Redis的默认字符串表示。
作用
- 保存数据库中字符串值
- 用作缓冲区：AOF模块中的AOF缓冲区，以及客户端状态中的输入缓冲区
2.1 SDS的定义
数据结构
struct sdshdr{
//记录buf数组已使用字节的数量，等于SDS所保存的字符串长度
int len;
//记录buf数组中未使用的字节数量
int free;
//字节数组，用于保存字符串
char buf[]
}
实例图
WechatIMG48.jpeg
- free属性值为0，表示sds没有分配任何未使用空间
- len属性值为5，表示sds保存了一个5字节长的字符串
- buf属性是一个char类型的数组，分别保存了'R','e',...'s' 五个字符，最后一个字节保存空字符 '\0';
SDS遵循C字符串以空字符结尾的惯例，保存空字符的1字节空间不计算在SDS的len属性里面；为空字符分配额外的1字节空间，以及添加空字符到字符串末尾操作，都是由SDS函数自动完成的；遵循空字符串结尾好处是，可以直接重用一部分c字符串函数库里的函数。例：printf() 函数等
2.2 SDS 与 C 字符串的区别
C语言使用长度为N+1的字符数组，表示长度为N的字符串，并且最后一位元素总是空字符'\0'，这种表达方式不能满足Redis对字符串在安全性，效率，以及功能上面的要求
| C字符串 | SDS |
|---|---|
| 获取字符串长度的复杂度为O(n) | 获取字符串长度的复杂度为O(1) |
| API是不安全的，会造成缓冲区溢出 | API是安全的，不会造成缓冲区溢出 |
| 修改字符串长度N次必然需要执行N次内存重分配 | 修改字符串长度N次最多修改执行N次内存重分配 |
| 只能保存文本数据 | 可以保存文本或者二进制数据 |
| 可以使用所有<string.h>库中的函数 | 可以使用一部分<string.h>库中的函数� |
2.2.1 常数复杂度获取字符串长度
c字符串不记录自身的长度信息，获取一个c字符串的长度必须遍历整个字符串，遇到结尾的空字符串为止，复杂度为O(N)。
SDS在len属性中记录了SDS本身的长度，复杂度为O(1)。（�设置和更新SDS长度是由SDS的API执行时自动完成的）
2.2.2 杜绝缓冲区溢出
假设有两个在内存中相邻的两个c字符串s1和s2，其中s1 保存了“Redis” ，s2保存了“MongoDB”，通过执行strcat(s1, "Cluster")(拼接函数) ，若忘记在执行strcat之前为s1分配足够的内存空间，在执行完strcat函数后，s1的数据将溢出到s2所在的空间中，导致s2保存的内容被意外的修改
SDS的内存空间完全的杜绝了缓冲区溢出的可能性：当SDS api 需要对SDS进行操作的时候，会先检查SDS的空间是否满足修改所需的要求；如果不满足的话，API会自动将SDS的空间扩大至所需要的大小，然后才执行修改操作。所有，SDS不需要手动的修改SDS空间大小，也不会出现c语言的缓冲区溢出问题。
修改前
WechatIMG50.jpeg
修改后
WechatIMG49.jpeg
2.2.3 减少修改字符串时带来的内存重分配次数
c字符串的底层实现总是一个N+1个字符长的数组，所以每次增长或缩短一个c字符串，程序都总要对保存这个c字符串的数组进行一次内存重分配操作：
- 增长字符串操作，比如拼接，执行这个操作之前，需要通过内存重新分配来扩展底层数组的空间大小，如果忘了会产生缓冲区溢出。
- 缩短字符串操作，比如截断，执行这个操作之后，需要通过内存重分配释放不再使用的那部分空间，如果忘了就会产生内存泄漏。
c字符串内存重新分配涉及复杂的算法，需要执行系统的调用，通常是一个比较耗时的操作：
- 一般程序中，修改字符串长度不太常出现，每次修改都执行一次内存重分配是可以接受的。
- Redis作为数据库，用于速度要求严格，数据频繁修改的场合，每次修改字符串的长度都需要执行一次内存分配的话，光是执行内存重分配的时间就会占去修改字符串所用时间的一大部分，修改频繁的话，还会对性能造成影响、
sds为了避免c字符串的这种缺陷，通过未使用空间解除了字符串长度和底层数组长度的之间的关联；在sds中buf数组的长度不一定就是字符数量加一，数组里面包含了未使用的字节，由free属性记录；
通过未使用空间，实现了 空间预分配 和 惰性空间释放 两种优化政策：
2.2.3.1 空间预分配
用于优化sds字符串增长操作，当进行空间扩展的时候，不仅会为sds分配修改所需要的空间，还会分配额外的未使用空间。
其中，额外分配未使用空间数量，由一下公式决定：
- sds len属性 < 1MB,程序分配和len属性同样大小的未使用空间；
- sds len属性 >= 1MB，程序分配1MB的未使用空间；
通过空间预分配策略，Redis可以减少连续执行字符串增长操作所需的内存重分配次数。
在扩展sds空间之前，api会先检查未使用的空间是否足够，足够的话，直接使用未使用空间，无须执行内存重分配。
通过这种预分配策略，将内存分配次数从必定N次降低为最多N次
2.2.3.2 惰性空间释放
用于优化sds字符串缩短操作：通过api缩短sds保存的字符串时，并不立即使用内存重分配来回收缩短后多出来的字节，而是通过free属性将这些字节的数量记录下来，等待将来使用；
WechatIMG52.jpeg
执行 sdstrim(s, "XY"); //移除sds字符串中所有'X' 和 'Y'
WechatIMG51.jpeg
执行sdstrim之后的sds并没有释放多出来的8个字节空间，而是将这8个字节空间作为未使用空间保留在了sds里面，将来要执行增长操作的话，未使用空间就能派上用场。
通过惰性空间释放策略，sds避免了缩短字符串所需的内存重分配操作，并为将来可能有的增长操作提供了优化。
sds也提供了相应的api，在我们需要的时候，真正的释放sds未使用空间，不用担心惰性空间释放策略会造成内存的浪费
2.2.4 二进制安全
c字符串中的字符必须符合某种编码（ASCII） ，并且除了字符串末尾之外，其他地方不能包含空字符，否则最先被程序读入的空字符将被误以为是字符串结尾，也限制了c字符串只能保存文本数据，不能保存图片，音频，视频，压缩文件这样的二进制数据。
为了确保Redis适用于不同的使用场景，SDS api 都是二进制安全的，所有api都会以处理二进制方式来处理sds存放在buf数组里的数据，并且不会对其中的数据做任何限制，过滤；sds使用的len属性的值，而不是空字符来判断字符串是否结束。
2.2.5兼容部分C字符串函数
虽然sds的api都是二进制安全的，但一样遵循c字符串以空字符结尾的惯例，为保证保存文本数据可以重用一部分<string.h>定义的函数
2.3 SDS API
| 函数:作用 | 时间复杂度 |
|---|---|
| sdsnew: 创建一个包含给定c字符串的SDS | O(n) |
| sdsempty: 创建一个不包含任何内容的空SDS | O(1) |
| sdsfree: 释放给定的sds | O(n) |
| sdslen: 返回sds的已使用空间字节数 | 通过读取len属性 O(1) |
| sdsavail: 返回sds未使用的空间字节数 | 通过读取free属性 O(1) |
| sdsdup: 创建一个给定sds的副本 | O(n) |
| sdsclear: 清空sds保存的字符串内容 | 惰性空间释放策略 O(1) |
| sdscat: 将给定的c字符串拼接到sds字符串末尾 | O(n) |
| sdscatsds: 将给定的sds字符串拼接到另一个sds字符串的末尾 | O(n) |
| sdscpy: 给定的c字符串复制到sds里面，覆盖sds原有的字符串 | O(n) |
| sdsgrowzero: 用空字符串将sds扩展至给定长度 | O(n) |
| sdsrange: 保留给定区间内的数据，不在区间内数据会被覆盖或清除 | O(n) |
| sdstrim: 接受一个sds 和一个c字符串作为参数，从sds左右两端分别移除所有在c字符串中出现过的字符 | O(m*n) m为sds的长度，n为给定c字符串长度 |
| sdscmp: 对比两个字符串是否相同 | O(n) |
网友评论