Simple Dynamic Strings(翻译)

sds是antirez从redis中提取出的字符串操作类库

Simple Dynamic Strings

关于version 2的提示:这是一个更新后的版本,目的是同意Redis,Disque,Hiredis,和独立的SDS版本。该版本和version 1的SDS Not binary compatible,但是API是99%兼容的,所以迁移起来不难。
SDS与V1相比在一定工作负荷的场景下稍慢一些,但使用更少的内存,因为header的大小是动态的并且依赖于你需要存储的string的大小。
而且它包含更多的API方法,尤其是sdscatfmt是加速版的sdscatprintf,可以在简单的场景下是使用(避免printf的性能损失)。

How SDS strings work

SDS通过堆上收集的字符串补充有限的libc字符串处理方法:

  • 简单易用
  • 二进制安全
  • 更有效的计算
  • 但... 与native c字符串兼容

通过设计一个C结构体替代native C的string,在结构体中实际存储的string之前放一个前缀,但是返回给用户的是指向string的指针(达到兼容的目的)。

+--------+-------------------------------+-----------+
| Header | Binary safe C alike string... | Null term |
+--------+-------------------------------+-----------+
         |
         `-> Pointer returned to the user.

因为属性数据作为前缀存储在实际返回的指针之前,并且每个SDS string隐式的在每个string之后都添加空字符。所以SDS字符串与C字符串可以一起工作,并且用户在处理只读的字符串时可以随意的互换SDS和C字符串。

SDS是一个C字符串,目的是辅助我过去每天的C编程,之后我将其放在Redis中广泛的使用,并且在Redis中使用的过程中,为了优化性能优化了很多地方。现在我把它从Redis抽离出来性能独立的项目。

因为SDS在Redis在打磨了很多年,SDS即提供在C中方便操作字符串的便利,而且也提供了底层的方法集用于高性能场景(免于高级别字符串库带来的性能损失)。

Advantages and disadvantages of SDS

通常C的动态字符串库会设计一个结构体用于定义string。结构体中会包含一个指针域,在库方法中会操作它。结构体如下:

struct yourAverageStringLibrary {
    char *buf;
    size_t len;
    ... possibly more fields here ...
};

上面提到过,SDS字符串没有跟随上面的模式,替换之的是在返回字符串地址之前防止一个前缀。

与传统的方法区别如下:

**缺点 #1:**很多方法会返回新的string(地址不一样),因为有的时候SDS需要新建string以得到更多空间,因此很多的SDS调用类似下面这样:

s = sdscat(s,"Some more data");

s即作为sdscat的输入,也作为调用的接收方,因为我们不能确定函数内部有没有申请新的字符串作为返回值。在调用与sdscat相似的方法时忘记更新s会导致bug。(这里我尝试理解了比较长时间,之所以作为缺点,是因为SDS的设计有违反了程序员的使用习惯,一般传入s后,可以直接使用s`)

**缺点 #2:**如果SDS字符串在多个地方共享,当你修改字符串时,你需要修改所有引用该字符串的地方,因为一些sds方法很可能会修改字符串的地址。如果你试图共享SDS字符串,最好是把sds嵌入到一个结构体中,并且设置referenct count否则太容易内存泄露。

**优点 #1:**与C字符串兼容,不需要通过访问结构体的成员来调用如下方法:

printf("%s\n", sds_string);

其他的库会像下面这样:

printf("%s\n", string->buf);

或者:

printf("%s\n", getStringPointer(string));

**优点 #2:**可以直接访问字符。C是底层语言所以这是很重要的操作。访问SDS字符串中的字符很自然:

printf("%c %c\n", s[0], s[1]);

使用其他库,你可能需要把string->buf(或者调用方法获得字符串指针)赋值给char指针。无论怎样因为其他的库可能隐式的重新分配字符串地址空间,所以你需要更新buf的地址。

**优点 #3:**单次分配内存空间有更好的缓存局部性。很多情况,当你使用字符串库(内部是结构体)创建一个字符串时,你会有两次内存空间分配,第一次是结构体本身,第二次是存储实际字符串的空间这里称buffer。过一段时间,当buffer被重新分配,这时得到的buffer可能是和结构体完全不同的两块内存。因此现代的程序性能经常受缓存不命中影响,SDS也许会提供更好的性能在多数工作负荷的情况下。

SDS basics

SDS字符串的类型是char *。SDS用sds作为char *的别名:你需要使用sds,目的是让你记得你使用的是SDS字符串不是原生C字符串,这不是强制性的。

下面是一个简单的SDS例子:

sds mystring = sdsnew("Hello World!");
printf("%s\n", mystring);
sdsfree(mystring);

output> Hello World!

上面的例子展示了一些关于SDS的重要特征:

  • SDS通过sdsnew()或者其他相似的方法创建,在堆上分配内存。
  • SDS可以像其他C字符串一样被传递给printf().
  • SDS因为是在堆上分配的,所以需要调用sdsfree()回收资源

堆是进程自己的内存空间,需要进程自己控制资源的合理利用

Creating SDS strings
sds sdsnewlen(const void *init, size_t initlen);
sds sdsnew(const char *init);
sds sdsempty(void);
sds sdsdup(const sds s);  

有很多方法创建SDS字符串:

  • sdsnew方法创建一个以空字符串开头的SDS字符串。我们已经在上面例子看到它是怎么工作的。
  • sdsnewlen方法与sdsnew相似,但它不会假定输入字符串以空字符开头,它有一个余外的长度参数。这种方式,你可以用二进制数据创建字符串。
char buf[3];
sds mystring;
buf[0] = 'A';
buf[1] = 'B';
buf[2] = 'C';
mystring = sdsnewlen(buf,3);
printf("%s of len %d\n", mystring, (int) sdslen(mystring));
output> ABC of len 3

注意:sdslen的返回值被转化为int,因为它返回size_t类型。你可以在printf中使用正确的占位符。

  • sdsempty()方法创建一个长度为0的字符串:
sds mystring = sdsempty();
printf("%d\n", (int) sdslen(mystring));

output> 0
  • sdsup()复制一个已经存在的SDS字符串:
sds s1, s2;

s1 = sdsnew("Hello");
s2 = sdsdup(s1);
printf("%s %s\n", s1, s2);

output> Hello Hello
Obtaining the string length
size_t sdslen(const sds s);

上面的例子中,我们已经使用sdslen方法获取字符串的长度。这个方法与libc中的strlen很像,除了以下几点:

  • 时间复杂度是C,因为长度存储在前缀中,所以即便是很大的字符串也不会很花时间。
  • 这个方法是二进制安全的,长度是真实长度,字符串中间有空字符也没有问题。

作为二进制安全的例子,我们看下面的代码:

sds s = sdsnewlen("A\0\0B",4);
printf("%d\n", (int) sdslen(s));

output> 4

注意到SDS字符串都会有空字符在尾部,即便是上面的例子s[4]也是空字符,但是printf只会输出"A",因为libc会把SDS string作为C string。

Destroying strings
void sdsfree(sds s);

销毁一个字符串,只需要传递字符串指针给sdsfree就可以了,注意用sdsempty创建的空字符串也需要调用,否则会导致内存泄露。

NULL传入sdsfree不会触发任何操作,所以你不需要显示检查NULL

if (string) sdsfree(string); /* Not needed. */
sdsfree(string); /* Same effect but simpler. */
Concatenating strings

当用户使用C string库时,连接字符串可能是最常用的操作。SDS提供了不同的连接方法。

sds sdscatlen(sds s, const void *t, size_t len);
sds sdscat(sds s, const char *t);
``

有时候你想让一个SDS string与另一个SDS string连接,你不需要指定长度,同时,字符串不一定需要以空字符结尾。下面是这个特殊的方法。

sds sdscatsds(sds s, const sds t);


用法非常直接:

sds s1 = sdsnew("aaa");
sds s2 = sdsnew("bbb");
s1 = sdscatsds(s1,s2);
sdsfree(s2);
printf("%s\n", s1);

output> aaabbb


有时候你不想在string的结尾添加什么,但是你试图保证字符串是由指定字节数组成的。

sds sdsgrowzero(sds s, size_t len);


`sdsgrowzero`方法,如果当前字符串长度已经是`len`,该方法没有动作,否则会扩大该string的长度到`len`,用0填充。

sds s = sdsnew("Hello");
s = sdsgrowzero(s,6);
s[5] = '!'; /* We are sure this is safe because of sdsgrowzero() */
printf("%s\n', s);

output> Hello!


##### Formatting strings

这是一个特殊的将string组合的方法,它接受一个类似`printf`中的格式描述字符串。

sds sdscatprintf(sds s, const char *fmt, ...) {


例子:

sds s;
int a = 10, b = 20;
s = sdsnew("The sum is: ");
s = sdscatprintf(s,"%d+%d = %d",a,b,a+b);


很多情况下,你想要从`printf`的格式描述字符串中直接创建SDS string。因为`sdscatprintf`实际上是一个组合字符串的方法,你只需要把你的string与空字符串组合即可:

char *name = "Anna";
int loc = 2500;
sds s;
s = sdscatprintf(sdsempty(), "%s wrote %d lines of LISP\n", name, loc);


你可以使用`sdscatprintf`转化数字为SDS strings:

int some_integer = 100;
sds num = sdscatprintf(sdsempty(),"%d\n", some_integer);


上面的方法速度慢。

##### Fast number to string operations

通过整型数字创建SDS string在很多程序中是比较常见的,如果你使用`sdscatprintf`,性能上的损失会比较大,所以SDS提供了一个具体的方法:

sds sdsfromlonglong(long long value);


使用方法如下:

sds s = sdsfromlonglong(10000);
printf("%d\n", (int) sdslen(s));

output> 5


##### Trimming strings and getting ranges

字符串的修整是比较通用操作(从首尾移除指定字符集),另一个有用的操作是从大字符串中取出部分。

void sdstrim(sds s, const char *cset);
void sdsrange(sds s, int start, int end);


SDS支持上述操作通过`sdstrim`和`sdsrange`方法,注意到这两个方法与之前讨论的都不一样,因为返回值是void:因为不需要申请新的内存空间,只需要在原来内存空间上修改即可。

鉴于以上行为,这两个方法很快且不涉及重新分配内存。

下面是一个例子,展示了将新行和空格从SDS string中移除:

sds s = sdsnew(" my string\n\n ");
sdstrim(s," \n");
printf("-%s-\n",s);

output> -my string-


基本上`sdstrim`把需要trim的字符串作为第一个参数,第二个参数是需要从首尾移除掉的字符集。移除操作遇到第一个不属于字符集中的字符停止:这是为什么`"my"`和`"string"`中间的空格被保留了。

截取字符与trim相似,把字符集替换为坐标,代表需要保留的string的首尾坐标。

sds s = sdsnew("Hello World!");
sdsrange(s,1,4);
printf("-%s-\n");

output> -ello-


负数表示从尾部开始倒数的坐标,`-1`代表最后的字符,`-2`代表倒数第二,例子:

sds s = sdsnew("Hello World!");
sdsrange(s,6,-1);
printf("-%s-\n");
sdsrange(s,0,-2);
printf("-%s-\n");

output> -World!-
output> -World-


当实现网络服务器中的协议处理或者发送消息时`sdsrange`非常有用。例如下面时Redis Cluster中不同节点间写消息总线的方法:

void clusterWriteHandler(..., int fd, void privdata, ...) {
clusterLink link = (clusterLink) privdata;
ssize_t nwritten = write(fd, link->sndbuf, sdslen(link->sndbuf));
if (nwritten <= 0) {
/
Error handling... */
}
sdsrange(link->sndbuf,nwritten,-1);
... more code here ...
}


每当socket准备写,我们都会尽可能的写入字节,这时我们可以用`sdsrange`移除buffer中已经发送的数据。

向集群中其他节点发送消息需要排队,为了发送更多的数据到发送缓存中,我们可以使用`sdscatlen`扩大queue。

注意到Redis Cluster总线使用二进制协议,但是SDS二进制安全,所以这并不是问题,所以SDS的目标不仅是给C程序员提供上层API,也可以动态的申请易于管理的缓存区域。


##### String copying

C库中最危险和臭名昭著的方法是`strcpy`,所以你可以看到上文中关于设计一个好的动态string库时只字未提复制字符串。通常你只需要创建一个存储你数据的string,或者在这个string上连接更多的内容。

无论怎样,SDS为了应对一些性能敏感的代码段,提供了字符串copy方法,但是我想这个方法的实际效用时有限的,因为在Redis的5w行代码中并未用到。

sds sdscpylen(sds s, const char *t, size_t len);
sds sdscpy(sds s, const char *t);


SDS中的字符串copy方法是`sdscpylen`,例子如下:

s = sdsnew("Hello World!");
s = sdscpylen(s,"Hello Superman!",15);


使用方法与之前的sds系方法很相似,不做赘述。

`sdscpylen`简单的替换旧SDS string中的数据。有个相似的方法`sdscpy`,不要求传入长度,但是要求字符串是空字符结尾。

你也许想知道在SDS库中为什么需要字符串copy方法,因为你可以简单的新增一个字符串。原因是效率:`sdsnewlen`总是会新分配空间,而`sdscpylen`会尝试利用已经存在的string,前提是有足够的空间放新string,只在必要时新分配空间。

##### Quoting strings

为程序员提供一致的输出或者处于debug的目的,把包含二进制数据或者特殊字符的string转化为quoted string很重要。这里quoted string的意思是程序源码中的字符串常量。今天这个格式也是json和csv这种序列化格式的一部分,因此它一定会转化程序中的string。

quoted string的一个例子是:

"\x00Hello World\n"


第一个字节是0字节,最后一个字节是新行,所以有两个非字母或者数字的字符在string中。

SDS使用连接方法,把quoted string连接到一个已经存在的string上。

sds sdscatrepr(sds s, const char *p, size_t len);


`scscatrepr`依照通常的SDS string方法的惯例,参数是一个字符指针和一个长度,所以可以传入SDS strings,或者C strings(使用strlen()作为`len`参数),或者二进制数据。例子:

sds s1 = sdsnew("abcd");
sds s2 = sdsempty();
s[1] = 1;
s[2] = 2;
s[3] = '\n';
s2 = sdscatrepr(s2,s1,sdslen(s1));
printf("%s\n", s2);

output> "a\x01\x02\n"


转化的规则:

* `\`和`"`会加上反斜杠
* `'\n'` `'\r'` `'\t'` `'\a'` `'\b'`会加上反斜杠
* 所有其他没有通过`isprint`测试都会转换撑`\x..`的形式,后面的点时两个16进制数字。
* 该方法会在首尾添加双引号字符

有一个方法可以反转化上述规则,会在下面章节介绍。

##### Tokenization

标题意思是把打的字符串分成小的多个strings。具体点说就是,指定另一个string作为分隔符。例如在下面的例子中有两个子字符串是被`|-|`分割出去的:

foo|-|bar|-|zap


一种比较通用的分隔符时逗号:

foo,bar,zap


分割一个字符串的情况在程序中比较常见,所以SDS提供了这种方法,传入string和分隔符,返回string数组。

sds *sdssplitlen(const char *s, int len, const char *sep, int seplen, int *count);
void sdsfreesplitres(sds *tokens, int count)


通常情况下,这个方法既可以传入SDS string,也可以传入C string。`s`和`len`指定了需要被分割的字符串,另外`sep`和`seplen`指定了分隔符。`count`返回子字符串的数量。

返回值是在堆上分配的SDS字符串数组。

sds *tokens;
int count, j;

sds line = sdsnew("Hello World!");
tokens = sdssplitlen(line,sdslen(line)," ",1,&count);

for (j = 0; j < count; j++)
printf("%s\n", tokens[j]);
sdsfreesplitres(tokens,count);

output> Hello
output> World!


`sdsfreesplitres`用于回收。你也可以用`free`释放每个字符串。

一个合法的方法是设置你想重复利用的元素为`NULL`(看了下代码才知道上面的方法也是遍历小字符串挨个释放,遇到NULL的不释放),然后通过`sdsfreesplitres`释放所有。

##### Command line oriented tokenization

通过分隔符分割string是一个比较有用的操作,但是在需要实现**Command Line Interface**时可能有些捉襟见肘。

这就是为什么SDS提供了附加的方法帮助用户分割来自于 键盘,文件,网络,或者其他来源的string。

sds *sdssplitargs(const char *line, int *argc);


`sdssplitargs`和`sdssplitlen`一样返回SDS字符串数组。回收方法也一样。不同的是分割的执行方式。

例如下面时输入:

call "Sabrina" and "Mark Smith\n"


方法会返回下面的tokens:

* "call"
* "Sabrina"
* "and"
* "Mark Smith\n"

token的通过空格划分,每个token内部还会使用`sdscatrepr`进行转义。

##### String joining

有两个方法用于组合strings。

sds sdsjoin(char **argv, int argc, char *sep, size_t seplen);
sds sdsjoinsds(sds *argv, int argc, const char *sep, size_t seplen);


参数是需要组合的字符串数组以及长度加上分隔符字符串和其长度,结果不做赘述。

`sdsjoin`和`sdsjoinsds`的不同在于参数,前者接收C string,后者需要使用sds string。所以只有`sdsjoinsds`能处理二进制数据。

char *tokens[3] = {"foo","bar","zap"};
sds s = sdsjoin(tokens,3,"|",1);
printf("%s\n", s);

output> foo|bar|zap


##### Error handling

所有的SDS方法在内存溢出的情况下会返回`NULL`,这个是唯一一个需要你验证的地方。

现代的许多C程序在内存溢出时直接终止运行,如果你想要达到这个目的,你需要自己封装一下内存管理相关的函数。

#### SDS internals and advanced usage

在文档的最开始解释了SDS字符串时怎么收集的,前缀存储在返回给用户的指针之前。如果想进一步了解,你最好查看SDS的源代码:

struct sdshdr {
int len;
int free;
char buf[];
};


就像你看到的,这个结构体让我们联想到常规的string库,但是`buf`字段不是指针,它是一个还没有初始化的数组,所以`buf`指向`free`之后的第一个字节。所以为了创建SDS string,我们只需要申请`sdshdr`加上我们字符串长度的空间,再加上一个字节用于存储空字符。

`len`是当前字符串的长度,每次字符串操作都会被重新计算。`free`表示当前的空前空间。

所以SDS的布局如下:

+------------+------------------------+-----------+---------------
| Len | Free | H E L L O W O R L D \n | Null term | Free space
+------------+------------------------+-----------+---------------
|
`-> Pointer returned to the user.


你会想知道为什么在string的尾部有空闲空间,这看起来是浪费。实际上在新的SDS string创建后,在尾部是没有空闲空间的:空间分配会正好装下前缀|字符串|空字符。但是一些对字符串的操作会在尾部增加空闲空间,想下面的这个代码:

s = sdsempty();
s = sdscat(s,"foo");
s = sdscat(s,"bar");
s = sdscat(s,"123");


因为SDS的目的是高效,所以它不允许每次字符串连接都去申请内存空间,这样会很低效,所以SDS会在每次扩大字符串时多分配一些空间出来。

预分配的算法如下:每次重新分配,实际申请的空间是连接后字符串大小的2倍。例如如果当前string大小时30bytes,我们想要连接2bytes,这时会申请64bytes。

对于预分配空间的大小有一个限制`SDS_MAX_PREALLOC`。SDS不会超出它,当然你可以修改这个限制。

##### Shrinking strings

sds sdsRemoveFreeSpace(sds s);
size_t sdsAllocSize(sds s);


有的程序可使用内存比较少。在字符串连接,修整,截取后,string会有一些冗余的空闲空间。

把string收缩会最小大小可以通过`sdsRemoveFreeSpace`。

s = sdsRemoveFreeSpace(s);


有个方法可以用于获取当前字符串总的被分配空间`sdsAllocSize`。

sds s = sdsnew("Ladies and gentlemen");
s = sdscat(s,"... welcome to the C language.");
printf("%d\n", (int) sdsAllocSize(s));
s = sdsRemoveFreeSpace(s);
printf("%d\n", (int) sdsAllocSize(s));

output> 109
output> 59


注意:SDS底层的API使用驼峰命名,目的是警告你这些操作非常危险。

##### Manual modifications of SDS strings

void sdsupdatelen(sds s);


有时你想要自己操作SDS string,而不是使用SDS的方法。在下面的例子中我们隐式的改变string的长度,并且我们希望逻辑的长度应该是以空字符结尾的C string的长度。

`sdsupdatelen`更新SDS string内部的长度字段通过`strlen`。

sds s = sdsnew("foobar");
s[2] = '\0';
printf("%d\n", sdslen(s));
sdsupdatelen(s);
printf("%d\n", sdslen(s));

output> 6
output> 2


##### Sharing SDS strings

如果你的程序中需要在多个数据结构中共享SDS string,强力建议你将SDS string封装到一个结构体中,并且增加引用计数字段。

这个方法参考了内存管理中的reference counting,有两个好处:

* 减少因为内存泄露 不释放内存或者释放已经被释放的内存导致的bug。
* 你不需要每次SDS string的修改都更新引用,因为SDS中的方法有时会创建一个新的string出来。

然而这是一个比较通用的编程技巧,这里我列出大体的设计。首先创建下面的结构体:

struct mySharedString {
int refcount;
sds string;
}


当新创建string时,返回成功后设置`refcount`为1。你定义两个方法改变引用计数:

* `incrementStringRefCount`增加`refcount`1。在每次你在新的数据结构种用到SDS string时需要调用。
* `decrementStringRefCount`减少引用计数。有一点特殊的是,需要在`refcount`为0时释放SDS string,还需要释放`mySharedString`。

##### Interactions with heap checkers

因为SDS返回的指针处于通过`malloc`方法收集的内存中间,所以堆checker会有一些问题:

* Valgrind会认为SDS string是possibly lost而不是definitely lost,所以分辨是否内存泄露很容易。我在Redis中使用Valgrind很多年每次真的内存泄露一定会提示"definitely lost"。
* OSX instrumentation tools不能检测到SDS string的泄露,但是可以修正那些指想内存块中间的指针。

##### Zero copy append from syscalls

到这里你已经拥有了所有发掘SDS的工具,这里有一个有趣的模式,在使用底层API时你可以参考,它帮助Redis优化网络相关代码的性能。

使用`sdsIncrLen()`和`sdsMakeRoomFor()`,连接内核中的字节到sds string,不经过intermediate buffer:

oldlen = sdslen(s);
s = sdsMakeRoomFor(s, BUFFER_SIZE);
nread = read(fd, s+oldlen, BUFFER_SIZE);
... check for nread <= 0 and handle it ...
sdsIncrLen(s, nread);


`sdsIncrLen`在sds.c中有描述。

#### Embedding SDS into your project

使用很简单,直接copy如下文件到你的项目:

* sds.c
* sds.h
* sdsalloc.h

任意的C99编译器都可以识别。

#### Using a different allocator for SDS

内部sds.c使用`sdsalloc.h`中的内存收集器。底层使用的是`malloc()` `realloc()` `free()`。可以直接修改这个文件,如果你想。

这里不做赘述,可以根据自己程序运行的环境选择自定义的内存分配方法。

Simple Dynamic Strings(翻译)
Share this