写在前面的话
本系列所有代码都基于Redis3.0。
Redis没有直接使用C语言传统的字符串表示，而是自己构建了一种名为简单动态字符串的抽象类型，并将SDS用作Redis的默认字符串表示。
1. 定义
每个sds.h/sdshdr结构表示一个SDS值
struct sdshdr {
// SDS保存字符串的长度
unsigned int len;
// 记录buf数组中未使用字节的数量
unsigned int free;
//字符数组，用以保存字符串
char buf[];
};
该图展示了一个SDS示例：
- free属性值为0，表示这个SDS没有分配任何未使用空间
- len属性的值为5，表示这个SDS保存了一个五字节长的字符串
- buf属性是一个char类型的数组，数组得前五个字节分别保存了'R','e','d','i'和's'五个字符，而最后一个字节则保存了空字符'\0'。
SDS遵循C字符串以空字符结尾得惯例，好处是可以直接重用一部分C字符串函数库里面得函数。
2. SDS与C字符串得区别
主要有以下几点。
- 获取字符串长度的复杂度是O(1)
- 杜绝缓冲区溢出
- 减少修改字符串长度时所需得内存重分配次数
- 二进制安全
- 兼容部分C字符串函数
2.1 获取字符串长度的复杂度是O(1)
C字符串不记录自身的长度，如果需要获取长度的话，必须遍历整个字符串，这个操作的复杂度为O(N)。
而SDS只要访问len属性，就可以立即知道长度。
2.2 杜绝缓冲区溢出
2.2.1 C字符串的问题
由于C字符串不记录自身长度，所以会造成缓冲区溢出。举个例子，<string.h>/strcat函数可以将src字符串中的内容拼接到dest字符串的末尾：
char *stract(char *dest, const char *src);
假定程序里有两个在内存中紧邻着的C字符串s1和s2，其中s1保存了字符串"Redis",而s2保存了字符串"MongoDB",如果一个程序员决定通过执行:
strcat(s1,"Cluster");
将s1的内容修改为"Redis Cluster",但是他忘了在执行strcat之前为s1分配足够的空间，那么该函数执行完之后，s1的数据将溢出到s2所在的空间中，导致s2保存的内容被意外地修改。
2.2.2 SDS的改进
SDS不会出现C字符串的缓冲区溢出问题，做出了如下改良。
- 检查SDS的空间是否满足修改所需的要求
- 不满足的话，将SDS的空间进行扩展
- 执行拼接操作
2.3 减少修改字符串时带来的内存重分配次数
2.3.1 C字符串的问题
对于C字符串来说：
- 如果进行的是拼接操作，程序需要先通过内存重分配来扩展底层数组的空间大小，否则会产生缓冲区溢出
- 如果进行的是截断操作，程序需要先通过内存重分配来释放字符串不再使用的那部分空间，否则会产生内存泄漏。
由于Redis作为数据库，经常被用于速度要求严苛、数据被频繁修改的场合，如果每次修改字符串的长度都需要进行内存重分配的话，会对性能造成影响。
2.3.2 SDS改进
通过空间预分配和惰性空间释放两种优化策略来解决这个问题。
2.3.2.1 空间预分配
用于字符串的增长操作:不仅为SDS分配修改所需要的空间，还会分配额外的未使用空间。
其中，额外分配的未使用空间数量由以下公式决定：
- 如果进行修改之后，SDS的长度将小于1MB, 而SDS的len将变成13个字节，那么程序也会分配13字节的未使用空间(free为13)。
- 如果进行修改之后，SDS的长度将大于1MB,那么会分配1MB的未使用空间
2.3.2.2 惰性空间释放
惰性空间释放用于优化SDS的字符串缩短操作:当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录下来，以后使用。
相关源码如下：
/*
* 将长度为 len 的字符串 t 追加到 sds 的字符串末尾
*
* 返回值
* sds ：追加成功返回新 sds ，失败返回 NULL
*
* 复杂度
* T = O(N)
*/
sds sdscatlen(sds s, const void *t, size_t len) {
struct sdshdr *sh;
//原有字符串长度
size_t curlen = sdslen(s);
//扩展SDS空间
s = sdsMakeRoomFor(s,len);
//没有足够空间扩展，返回NULL
if (s == NULL) return NULL;
//复制T中的内容到字符串后部
sh = (void*) (s-(sizeof(struct sdshdr)));
memcpy(s+curlen, t, len);
//更新属性值
sh->len = curlen+len;
sh->free = sh->free-len;
//添加结尾
s[curlen+len] = '\0';
//返回
return s;
}
/*
* 对 sds 中 buf 的长度进行扩展，确保在函数执行之后，
* buf 至少会有 addlen + 1 长度的空余空间
* （额外的 1 字节是为 \0 准备的）
*
* 返回值
* sds ：扩展成功返回扩展后的 sds
* 扩展失败返回 NULL
*
* 复杂度
* T = O(N)
*/
sds sdsMakeRoomFor(sds s, size_t addlen) {
struct sdshdr *sh, *newsh;
// 获取 s 目前的空余空间长度
size_t free = sdsavail(s);
size_t len, newlen;
// s 目前的空余空间已经足够，无须再进行扩展，直接返回
if (free >= addlen) return s;
// 获取 s 目前已占用空间的长度
len = sdslen(s);
sh = (void*) (s-(sizeof(struct sdshdr)));
// s 最少需要的长度
newlen = (len+addlen);
// 根据新长度，为 s 分配新空间所需的大小
if (newlen < SDS_MAX_PREALLOC)
// 如果新长度小于 SDS_MAX_PREALLOC
// 那么为它分配两倍于所需长度的空间
newlen *= 2;
else
// 否则，分配长度为目前长度加上 SDS_MAX_PREALLOC
newlen += SDS_MAX_PREALLOC;
// T = O(N)
newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);
// 内存不足，分配失败，返回
if (newsh == NULL) return NULL;
// 更新 sds 的空余长度
newsh->free = newlen - len;
// 返回 sds
return newsh->buf;
}
2.4. 二进制安全
2.4.1 C字符串的问题
由于C字符串最后一位必须是'\0',所以只能存储文本数据，不能保存图片、音频、视频、压缩文件这样的二进制数据。
2.4.2 SDS的改进
SDS是靠free的值来判断字符串是否结束，所以可以保存任意格式的二进制数据。
2.5. 兼容部分C字符串函数
通过遵循C字符串以空字符结尾的惯例，SDS可以在有需要时重用<string.h>函数库，从而避免了不必要的代码重复。
3. 相关对象
在Redis里，字符串对象用到的底层数据结构为SDS
3.1 字符串对象
字符串对象的编码可以是int、raw或者embstr。
3.1.1 常用操作命令
3.1.1.1 单值缓存
3.1.1.2 对象缓存
3.1.1.3 分布式锁
3.1.2 使用场景
3.1.2.1 计数器
INCR article:readcount:{文章id}
GET article:readcount:{文章id}
3.1.2.2 Web集群session共享
spring session + redis实现session共享
3.1.2.3 分布式系统全局序列号
INCRBY orderId 1000 //redis批量生成序列号提升性能
参考资料
<<Redis设计与实现>>
