Redis 中 SDS 相比 C 字符串有哪些优势？

SDS 是什么鬼？

其实，SDS 是 Redis 中实现的一种数据结构，主要用来存储字符串。那 SDS 与 C 字符串相比有什么优势呢？那就看看下面小编为大家的分享吧。

1、常数复杂度获取字符串长度

常规 C 字符串并不记录自身的长度信息，所以为了获取一个 C 字符串的长度，程序必须遍历整个字符串，对遇到的每个字符进行计数，直到遇到代表字符串结尾的空字符为止，这个操作的复杂度为 O(N)。

而 SDS 使用结构体实现，结构体中的 len 属性直接记录了该 SDS 结构体中 buf 数组中已使用的长度，因此获取字符串长度时，只需要获取 len 属性的值，这个操作的复杂度为 O(1)。SDS 结构体的实现确保了获取字符串长度的工作不会成为 Redis 的性能瓶颈。

2、杜绝缓冲区溢出

因为，C 字符串不记录自身的长度，所以当进行字符串复制的时候，如果分配内存不够，就有可能产生缓冲区溢出。

而在 Redis 中，当 SDS API 需要对 SDS 进行修改时，API 会先检查 SDS 的空间是否满足修改所需的要求，如果不满足的话，API 会自动将 SDS 的空间扩展至执行修改所需的大小，然后才执行实际的修改操作。所以，使用 SDS 既不需要手动修改 SDS 的空间大小，也不会出现前面所说的缓冲区溢出问题。

Redis 中 strcat 的实现代码：

sds sdscat(sds s, const char *t) {

return sdscatlen(s, t, strlen(t));

}

sds sdscat(sdss,constchar*t){

returnsdscatlen(s,t,strlen(t));

}

Redis 中 sdscatlen 的实现代码:

sds sdscatlen(sds s, const void *t, size_t len) {

struct sdshdr *sh;

// 原有字符串长度 直接获取len属性

size_t curlen = sdslen(s);

// 扩展 sds 空间

// T = O(N)

s = sdsMakeRoomFor(s,len);

// 内存不足？直接返回

if (s == NULL) return NULL;

// 复制 t 中的内容到字符串后部

// T = O(N)

sh = (void*) (s-(sizeof(struct sdshdr)));

memcpy(s+curlen, t, len);

// 更新属性

sh->len = curlen+len;

sh->free = sh->free-len;

// 添加新结尾符号

s[curlen+len] = '\0';

// 返回新 sds

return s;

}

sds sdscatlen(sdss,constvoid*t,size_tlen){

structsdshdr*sh;

// 原有字符串长度 直接获取 len 属性

size_tcurlen=sdslen(s);

// 扩展 sds 空间

// T = O(N)

s=sdsMakeRoomFor(s,len);

// 内存不足？直接返回

if(s==NULL)returnNULL;

// 复制 t 中的内容到字符串后部

// T = O(N)

sh=(void*)(s-(sizeof(structsdshdr)));

memcpy(s+curlen,t,len);

// 更新属性

sh->len=curlen+len;

sh->free=sh->free-len;

// 添加新结尾符号

s[curlen+len]='\0';

// 返回新 sds

returns;

}

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

常规 C 字符串，在执行拼接操作或者截断操作时，通常会对数组进行内存重分配，而内存重分配操作涉及复杂的算法，并且可能执行系统调用，所以它通常是一个比较耗时的操作。

Redis 作为数据库，会对数据进行频繁的修改，并且对速度要求极为严苛，所以每次修改字符串长度都需要进行内存重分配，这会对性能造成极大的影响。

为此，Redis 的 SDS 实现了空间预分配和惰性空间释放两种优化策略。

1. 空间预分配

当 SDS 的 API 对一个 SDS 进行修改时，程序不仅会为 SDS 分配必须要的空间，还会为 SDS 分配额外的未使用空间。

额外分配未使用空间数量的规则：

当 SDS 的 len 属性值小于 1MB，程序分配和 len 属性同样大小的未使用空间。

当 SDS 的 len 属性值大于 1MB，程序将多分配 1M 的未使用空间。

通过这种预分配策略，SDS 将连续增长 N 次字符串所需的内存重分配次数从必定 N 次降低为最多 N 次。

2. 惰性空间释放

当对 SDS 进行字符串缩短操作时，SDS 的 API 不会立即使用内存重分配回收多出来的字节，而是使用 free 属性将这些字节的数量记录起来，等待将来使用。

当然，SDS 也提供了相应的 API，可以用来真正释放 SDS 的未使用空间，所以不用担心惰性空间释放策略会造成内存浪费。

以上就是 redis 中，SDS 简单动态字符串相比 C 字符串的一些好的地方，个人还是比较实用的，希望对大家有帮助吧。

相关文章：《PHP 开发常用的 8 款 Laravel 软件包》 http://www.maiziedu.com/group/article/663/