redis底层数据结构之sds

4232342

最近，我想通过redis的源码来学习redis。虽然平时工作中用得不多，不过对redis还是比较感兴趣的，毕竟它的性能是不错的。redis是一个开源的项目，我们可以通过源代码去了解redis。我后面会通过自己的学习，写一些关于redis源码的帖子。帖子的主要内容是分析代码设计，而并不会对源码进行详细解说。如果有不对的地方，请指正。源码是reids 3.0.3版本。

sds

一、redis的字符串 sds：

c语言的字符串是 char *，redis则自己定义了内部的字符串sds，同时也提供了一组sds的相关的操作函数，redis这样做是为了更方便地使用字符串。先看看sds的定义：

1 2 3 4 5 6

typedef char *sds; struct sdshdr {     unsigned int len;    //字符串长度     unsigned int free;    //剩余空间大小     char buf[];        //字符串存储地址 };

先看 struct sdshdr，这是redis字符串的头部信息，各字段意思见注释。这样的字符串设计，是与字符串的相关操作关联的。为更好地了解sds，先举个例子看一下sds是如何的存储“hello world”的。下面一一个例子：

1 2 3

len = 11 free = 5 buf[] = “hello world” + ’\0’ + 5个byte空间

其中 len=11 指的是字符串的长度，free＝5是指sds还剩余的存储空间，buf的实际大小为 len + 1 + free，其中 1 是指 ‘\0’ 的空间大小。

从数据结构的定义和上面例子可以看出：
    1. len是字符串的长度，通过记录下长度，对于求字符串长度的操作是O(1)的，但这样也带来了len的维护问题，在更新字符串长度时，同时需要更新len字段。
    2. free是剩余空间，剩余的空间是用于扩展字符串长度。但是剩余的空间是有限的，为保证字符串长度能自由增长，需要一些方法去增加剩余的空间。
    3. buf字符串存储的地址，把buf声明为0长度的char数组，是常用的内容空间分配设计方法。一般情况下，这样的数据结构都是动态申请空间的。这样就能在动态申请空间时，分配 数据结构本身的大小+buf大小 的空间，做到动申请，现时也能通过重新申请的方法扩展空间。具体可见 sdsnewlen 和 sdsMakeRoomFor 函数的实现。
    4. ’\0’，字符串后面总是以‘\0’结尾，目的是让sds的buf跟c语言的字符串对齐，能够通过printf等函数直接输出。但这里需要注意‘\0’并不能代表sds字符串的结束，因为sds字符串中也可能含有’\0’字符。字符串的结束只能由len指定。这样设计的字符串，不仅可以支持c语言的字符串，还可以扩展到二进制串，就像std::string一样。
    5. 支持二进制存储。由于sds的字符串长度是由len指定的，字符串中的每一个byte，都可以覆盖二进制中的所有值，所以可以支持二进制存储。redis为什么要支持二进制串的存储呢？我想是因为redis需要间接支持复杂数据结构的存储。因为redis本身只提供了string，list，set，zset，hash等通用的数据结构的存储，对于用户自己定义的数据结构，redis并不能直接支持其存储。而redis提供了二进制的存储，可以让用户自己把复杂的数据结构序列化成二进制串再存储。这样虽然在存时需要序列化、取时需要反序列化，消耗了CPU，但却换来的存储的通用性。
    6. typedef char * sds。sds定义为char*而不是sdshdr*。主要的原因是为了使sds看起来更像char*，在使用一些函数时能跟char*无区别，如printf。这样做也是有代价的，那便是sds相关操作的复杂性提高了。几乎每个有关sds的操作，都要通过sds(char*)来定位出sdshdr*。

sds也有一些缺点：

sdshdr占用一定空间
字符串中有剩余空间，虽然可用于扩展，但也可能是一种浪费。
需要代码本身提供一组相关的操作函数，才能更好地使用。
使用sds时，需要比较了解sds的特点和其操作函数的使用规范，对编程者要求比较高。

二、sds的相关操作函数：


为了让使用者更方便地使用sds，redis提供了一系列关于sds的操作函数。如：

1 2 3 4 5 6 7

sdslen 字符串长度 sdsavail 字符串可用空间长度（free） sdsnew 创建字符串 sdsdup 复制字符串 sdsfree 释放字符串 sdscat 字符串拼接 …

这里不一一列举。
sds和其操作函数，一同为redis提供了操作方便的字符串，但同时也增加了字符串操作的复杂性。在使用sds及其操作函数时，必须了解sds的行为特点才能正确使用。

举一个函数来分析，sdsMakeRoomFor：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

/* Enlarge the free space at the end of the sds string so that the caller * is sure that after calling this function can overwrite up to addlen * bytes after the end of the string, plus one more byte for nul term. * * Note: this does not change the *length* of the sds string as returned * by sdslen(), but only the free buffer space we have. */ /* 增在sds的空间，以够字符串长度增加addlen。 * 如果字符串本身的剩余空间大于addlen，则无需增加sds的空间，否则增加空间。 */ sds sdsMakeRoomFor(sds s, size_t addlen) {     struct sdshdr *sh, *newsh;     size_t free = sdsavail(s);     size_t len, newlen;     /* 如果剩余的空间足够存储addlen，无需增加空间 */     if (free >= addlen) return s;     len = sdslen(s);     sh = (void*) (s-(sizeof(struct sdshdr)));    /* 计算sdshdr地址 */     newlen = (len+addlen); /* 字符串增加后的总长度 */     /* 预分配空间的策略，如果新的长度小于 SDS_MAX_PREALLOC(1M)，      则预分配多一倍的长度，否则预分配多SDS_MAX_PREALLOC大小的空间 */     if (newlen < SDS_MAX_PREALLOC)         newlen *= 2;     else         newlen += SDS_MAX_PREALLOC;     /* 申请扩展空间 */     newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);     if (newsh == NULL) return NULL;     newsh->free = newlen - len;     return newsh->buf; }

上面函数 sdsMakeRoomFor 里面会有预分配空间的策略，需要注意的是，预分配空间可以预留空间给字符串增加，但同时也会造成浪费。并不是所有的字符串都会有预分配空间，只有 sdsgrowzero，sdscatlen，sdscpylen，sdscatfmt 等函数会调用 sdsMakeRoomFor。