redis 系列3 简单动态字符串 SDS
一. sds概述
redis 没有直接使用c语言传统的字符串表示，而是自己构建了一种名为简单动态字符串(simple dynamic string, sds)的抽象类型，并将sds用作redis的默认字符串表示。redis只会使用c字符串作为字面量。在redis里，使用sds来表示字符串值，是一个可以被修改的字符串，字符串“键值对”底层都是由sds实现的。
-- 例1：客户端执行如下命令： 127.0.0.1:6379> set msg "hello world" ok 127.0.0.1:6379> get msg "hello world"
上面例1中就在数据库里创建一个新的键值对。 其中“键”是一个字符串对象，对象的底层实现是一个保存着字符串"msg" 的sds。 "键值" 也是一个字符串对象，对象的底层实现是一个保存着字符串" hello world " 的sds。
-- 例2: 客户端执行如下命令： 127.0.0.1:6379> rpush fruits "apple" "banana" "cherry" (integer) 3 127.0.0.1:6379> lrange fruits 0 -1 1) "apple" 2) "banana" 3) "cherry"
上面例2中也在数据库里创建一个新的键值对。其中“键”是一个字符串对象，对象的底层实现是一个保存着字符串" fruits " 的sds。"键值"是一个列表对象，列表包含了三个字符串对象，分别由三个sds实现。
sds除了用来保存数据库中的字符串值之外，还用作缓冲区(buffer): aof模块中的aof缓冲区，以及客户端状态中的输入缓冲区。
二. sds 定义
每个sds.h文件下的sdshdr结构表示一个sds值, 下面是redis源码，在github的地址是
struct sdshdr{
//记录buf数组中已使用字节的数量，也就是字符串的长度
int len ;
// 记录buf数组中未使用字节的数量
int free;
//字节数组，用于保存字符串
char buf[];
}
在c语言中使用长度为n+1的字符数组来表示长度为n的字符串，并且字符数组最后一个元素总是空字符'\0'。 假设sds的值为 "redis"，那么free属性值为0, len 属性值为5, buf数组为r,e,d,i,s五个字符，最后一个字节则保存空字符'\0' 。
三. sds与c字符串的区别
c语言使用简单的字符串表示方式，并不能满足redis对字符串在安全性，效率以及功能方面的要求，从几个方面说明：
1. 常数复杂度获取字符串长度
因为c字符串并不记录自身的长度信息，所以为了获取一个c字符串的长度，程序必须遍历整个字符串。与c 字符串不同，因为sds在len属性中记录了sds本身的长度，对于sds的值为"redis"的字节长度就是5。
2. 杜绝缓冲区溢出
在c中, 假设紧邻的字符串s1 和 s2， s1保存为"redis", s2保存为"mongodb", 如果修改s1的值为 redis cluster, 但修改之前没了空间，那么s1的数据将溢出到s2所在空间中。
在sds中，会先检查给定的sds空间是否足够，会自动扩展修改所需的大小空间。然后在执行实际的修改操作。
3. 减少修改字符串时带来的内存重分配次数
在c 中，字符串的底层实现总是一个n+1个字符长的数组，因为字符串的长度和底层数组的长度之间存在着这种关联，所以每次增长或者缩短一个c字符串，程序都要对保存这个c字符串的数组进行一次内存重分配操作。
在sds中通过未使用空间解除了字符串长度和底层数组长度之间的关联，buf数组的长度不一定就是字符数量加1， 数组里机可以包含未使用的字节，这些由free属性记录。
3.1 空间预分配
当sds的api对一个sds进行操作，并且需要对sds进行空间扩展的时候，程序不仅会为sds 分配修改所必须要的空间，还会为sds分配额外的未使用空间。额外分配的未使用空间数量由以下公式决定：
如果对sds进行修改之后，sds的长度(也即是len属性的值) 将小于1mb，那么程序分配和len属性同样大小的未使用空间。这时sds len属性的值将和fee属性的值相同，例如：修改之后,sds的len将变成13字节， 那么程序也会分配13字节的未使用空间，sds的buf数组的实际长度将变成13+13+1=27字节。
如果对sds进行修改之后，sds的len大于等于1mb, 那么程序会分配1mb的未使用空间，如果对sds进行修改之后, sds的len变成30mb,那么程序会分配1mb的未使用空间，sds的buf数组的实际长度为30mb + 1mb +1byte。
通过空间预分配策略，redis可以减少连续执行字符串增长操作所需的内存重分配次数。
3.2 惰性空间释放
惰性空间释放用于优化sds的字符串缩短操作。当sds的api需要缩短sds保存的字符串时，程序并不立即使用内存重分配来回收缩短多出来的字节，而是使用free属性将这些字节的数据记录起来，并等待将来使用(缩短后未使用的空间不会释放，而是将来增长操作时，再使用这些未使用空间)。
4. 二进制安全
在c字符串的字符必须符合某种编码(如ascii), 并且除了字符串的末尾之处，字符串里面不能包含空字符，否则最先被程序读入的空字符将被误以为是字符串的结尾，这使得c字符串只能保存文本数据，不能保存图片，音频，视频，压缩文件之类的二进制数据。
为了保证redis 可以适用各种不同的使用场景，sds的api 都是二进制安全的，程序不会对其中的数据做任何限制，过滤，数据写入是什么，读取时就是什么。
5. 兼容部分c字符串函数
在sds中会遵循c字符串以空字符结尾的惯例，总会为buf数组分配空间时多分配一个字节来容纳这个空字符，这是为了让sds的字符串可以重用一部分(string.h>库定入的函数。
四 总结
4.1 c字符串与sds之间的区别总结
|
c字符串 |
sds |
|
获取字符串长度的复杂度为0(n) |
获取字符串长度的复杂度为0(1) |
|
api是不安全的，可能会造成缓冲区溢出 |
api是安全的，不会造成缓冲区溢出 |
|
修改字符串长度n次必然需要执行n次内存重分配 |
修改字符串长度n次最多需要执行n次内存重分配 |
|
只能保存文本数据 |
可以保存文本或者二进制数据 |
|
可以使用所有<string.h>库中函数 |
可以使用一部分<string.h>库中函数 |
4.2 sds api(主要的一些api)
|
函数 |
作用 |
|
sdsnew |
创建一个sds字符串 |
|
sdsempty |
创建一个不包含内容的空sds 字符串 |
|
sdsfree |
释放给定的sds字符串未使用空间 |
|
sdslen |
返回sds字符串已使用空间字节数 |
|
sdsavail |
返回sds字符串未使用空间字节数 |
|
sdsdup |
创建一个给定sds的副本 |
|
sdsclear |
清空sds字符串内容 |
|
sdscat |
将给定c字符拼接到sds字符串的末尾 |
|
sdscatsds |
将给定的sds字符串拼接到另一个sds字符串的末尾 |
|
sdscpy |
将给定的c字符拼复制到sds里机，覆盖sds原有字符串 |
|
sdsgrowzero |
用空字符将sds扩展至指定长度 |
|
sdsrange |
保留sds指定区间内的数据，不在区间内的数据会被覆盖或清除 |
|
sdstrim |
接受一个sds和一个c字符串作为参数，从sds中移除所有在c字符串中出现过的字符 |
|
sdscmp |
对比两个sds字符串是否相同 |