使用过 Redis 的都知道 Redis 用的最多的可能是它的 Key/Value 的缓存，在 Redis 用作 Key/Value 的缓存时，Value 有若干种数据类型，分别是 String、List、Set、Sorted Set 和 Hash。不同的 Value 类型对应了不同的数据结构，我们分别来了解一下 Redis 各种 Value 类型的数据结构。
这次先来了解一下，Redis 的 String 类型所对应的数据结构。我这里要首先感谢《Redis 设计与实现》一书的作者 黄健宏 先生，他写出如此优秀的书籍从而让我们能够学习高性能的 Redis 的内部实现原理。
Redis 是使用 C 语言实现的，C 语言本身就是一种运行时非常高效的程序设计语言。但是 Redis 的字符串结构并没有沿用 C 语言常规的存储字符串的方式。在 C 语言中，字符串是以数组的形式存储在内存中的，并且以 \0 作为字符串的结尾。在 C 语言中，读取字符串、计算字符串长度、连接字符串、拷贝字符串等函数，都是以 \0 来进行判断，而如果在写代码时对缓冲区检查不严格，则会导致缓冲区溢出。缓冲区溢出这种安全问题也是 C 语言一个很严重的问题。C 语言设计的初衷是希望把尽可能多的控制权交给程序员来保证 C 语言的灵活和自由，但是灵活和自由的同时也付出了很多惨痛的代价。
当然了，上面的存储方式是 C 语言的方式，其他的语言就未必了，如果使用过 Delphi 的话，就知道 Delphi 的字符串就不是以 \0 作为结束的，而是在字符串的开头位置放入了字符串长度一个标识。
现在，我们来看看 Redis 的实现，我这里是 Redis 2.6 的实现源码（版本低一些，阅读时会相对容易一些）。
一、SDS 结构体
在 Redis 中的字符串是结合了 C 语言字符串特性（即以 \0 结尾）和一种被称为 SDS 的数据结构共存的字符串结构，其结构的定义在 sds.h 的头文件中，该数据结构的定义如下（所有的中文注释都是我注释的，官方源码中是不可能提供中文注释的，如果注释有误希望可以指出）：
struct sdshdr { /* 已使用缓冲区的长度 */ int len; /* 未使用缓冲区的长度 */ int free; /* 缓冲区 */ char buf[]; };
该结构体中包含三个成员，分别是 len、free 和 buf，其中 len 用来保存已经使用的缓冲区的长度，free 用来保存未使用的缓冲区的长度，buf 是真正的缓冲区的字符数组。buf 中存储的字符串仍然是以 \0 结尾，但是它的长度并不计算在 len 中，这一点和 C 语言是相同的，使用 strlen 计算字符串长度的时候，也没有把 \0 计算在内。
确定了数据结构以后，所有的操作就是围绕数据结构来展开了，就好比我们写代码，确定了表结构，生成了实体类，然后业务处理就是围绕输入和针对实体类的具体操作了。
二、获取字符串的长度
在 C 语言中，求字符串的长度是逐个字符进行遍历统计，直到遇到 \0 就是字符串的结束，这样就能得到字符串的长度了。也就是说，在 C 语言中获取字符串长度的时间复杂度为 O(n)。
在 SDS 结构体中，获取字符串的长度的时间复杂度则为 O(1)，因为在 SDS 结构体中已经有一个成员来保存已使用缓冲区的长度了，它就是实际意义上的字符串的长度，因此在 SDS 字符串长度的时候，可以直接从 SDS 结构体中返回 len 这个成员即可。具体代码在 sds.h 中，代码如下：
/** * 获取已使用缓冲区的长度 * * s：sds字符串 * * 返回值：返回已使用的缓冲区长度，表示获取sds字符串的长度 */ static inline size_t sdslen(const sds s) { struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr))); return sh->len; }
从上面的代码可以看出，对于 Redis 的 SDS 数据结构而言，它获取字符串的长度只是计算一下数据结构的首地址，并返回其数据结构内的一个偏移就可以了，和 C 语言常规字符串计算长度效率的高低也就很明显了。
三、字符串的连接与拷贝
字符串的连接与拷贝在 C 语言当中也是有安全隐患的，因为这些函数的实现本身不对缓冲区进行判断，因此在使用是就可能会导致溢出，覆盖掉相邻内存中的数据，这样的函数有 strcpy 和 strcat 等，不过后来 C 语言有了相对安全的函数版本，比如 strcat_s 和 strcpy_s。关于 C 语言字符串处理的函数而言，不单单只有这两个，但是这两个是相对用的多的，也是比较常见的，我们还是来看看 Redis 的 SDS 是如何处理的吧。
/** * 字符串连接：将t连接到sds字符串s的尾部 * * s：sds字符串 * t：要连接的字符串 * * 返回值：返回字符串追加后的sds的字符串 */ sds sdscat(sds s, const char *t) { return sdscatlen(s, t, strlen(t)); } sds sdscatsds(sds s, const sds t) { return sdscatlen(s, t, sdslen(t)); }
在 Redis 中有两个字符串连接的函数，分别是 sdscat 和 sdscatsds，这两个函数都是用来进行字符串链接的，他们的差别在于参数，它们都有两个参数，第一个参数是目的字符串，目的字符串的类型是 sds，而第二个参数就有区别了，sdscat 的第二个参数是一个 const char * 类型，sdscatsds 的第二个参数是 sds 类型，但是它们其实都是字符串。两个函数都调用了 sdscatlen，也就是说 sdscatlen 是这两个函数的真正实现。
/** * 字符串追加，将c格式的字符串追加至sds字符串的尾部 * * s：sds字符串 * t：要连接的字符串 * len：t的长度 * * 返回值：返回字符串追加后的sds的字符串 */ sds sdscatlen(sds s, const void *t, size_t len) { struct sdshdr *sh; size_t curlen = sdslen(s); /* 检查空间并分配空间 */ s = sdsMakeRoomFor(s,len); if (s == NULL) return NULL; /* 获取sds字符串的头 */ sh = (void*) (s-(sizeof(struct sdshdr))); /* 将追加的字符串拷贝到原sds字符串的尾部 */ memcpy(s+curlen, t, len); /* 修正已使用缓冲区的长度 */ sh->len = curlen+len; /* 修正未使用缓冲区的长度 */ sh->free = sh->free-len; /* 追加NULL字符进行字符串结束 */ s[curlen+len] = '\0'; return s; }
从上面的代码中可以看出，在连接之前会得到当前 sds 字符串 s 的长度，然后通过 sdsMakeRoomFor 函数来检查空间是否能够容纳要连接字符串的长度，如果空间不够会在 sdsMakeRoomFor 函数中申请空间。然后使用 memcpy 来进行一次内存的拷贝，拷贝的开始位置是 sds 字符串 s 的末尾，拷贝的内容是要连接的字符串 t，拷贝的内存长度为 len。memcpy 是 C 语言库中的函数，拷贝完以后会在字符串的末尾增加一个 \0 来表示字符串的结尾。因为 SDS 结构体中除了字符串空间以外，还额外维护着两个值，一个是已经使用的缓冲区的长度，一个是未使用的缓冲区的长度。
我们需要观察一下这段代码 return 之前的四行代码，在代码中进行字符串拷贝以后，先对 SDS 两个额外的成员进行了赋值，最后才追加了 \0 的字符串结束符，对于一般写代码的逻辑而言，我们在调用完 memcpy 进行内存拷贝以后，就会在字符串的末尾追加 \0 字符，然后才去对 len 和 free 两个成员赋值。因为，这样会避免忘记在末尾增加 \0 字符。那么，Redis 为什么这么写呢？我的思考是，Redis 的作者在考虑代码编译后 CPU 流水线的问题，因为这样写代码操作的内存是不一样的，CPU 就可以不用等待当前指令的完成就可以直接执行下一条的指令，充分利用 CPU 的多条流水线从而提高代码的执行效率。当然了，这是我的考虑，如果不正确请指出。
四、二进制安全特性
在上面的 sdscatlen 函数的注释，我其实描述的是不准确的。在 sdscatlen 函数的第二个参数的参数类型是 void*，第三个参数是一个 size_t 的长度。这说明，sdscatlen 能做的并不只是追加以 \0 结尾的字符串，而是可以追加任意的二进制数据，只要数据可以转换为字符数组，都可以存储到 SDS 数据结构中。因为 SDS 结构体本身当中就保存了缓冲区使用的长度，因此 Redis 不会简单的按照 C 语言的 \0 结尾的字符串来处理缓冲区中的数据。
五、兼容 C 字符串
虽然 Redis 对于 SDS 的处理没有按照 C 语言以 \0 的方式处理字符串，但是 Redis 仍然保留了 C 语言字符串结束的 \0 标识，它的作用在于，如果明确缓冲区中保存的是字符串，那么此时对于 C 语言的字符串处理可以直接使用 C 的字符串库，这样 Redis 的开发也省去了很多重新造轮子的工作。
六、SDS 空间的分配与释放
反复的内存分配与释放可能会因为复杂的内存分配算法、系统调用、内存拷贝等原因造成性能上的下降，Redis 通过 “空间预分配” 和 “惰性空间释放” 来解决因为频繁分配和回收内存导致的性能下降的可能性。
1、空间预分配
/** * sds空间预分配函数 * * sds：sds字符串 * addlen：追加字符串的长度 * * 返回值：返回新空间的缓冲区 */ sds sdsMakeRoomFor(sds s, size_t addlen) { struct sdshdr *sh, *newsh; /* 获取未使用缓冲区的长度 */ size_t free = sdsavail(s); size_t len, newlen; /* 未使用的缓冲区长度如果大于追加字符串的长度，则直接返回 */ if (free >= addlen) return s; /* 返回已使用缓冲区的长度 */ len = sdslen(s); /* 获取该sds字符串的头 */ sh = (void*) (s-(sizeof(struct sdshdr))); /** * 首先，将新缓冲区长度设置为已使用缓冲区的长度加上追加字符串的长度 * 其次，判断新缓冲区长度是否大于1M * 如果小于1M则分配2倍的新缓冲区长度 * 如果大于1M则在新分配的缓冲区长度上加1M的长度 */ newlen = (len+addlen); if (newlen < SDS_MAX_PREALLOC) newlen *= 2; else newlen += SDS_MAX_PREALLOC; /* realloc函数会在申请新内存空间的同时，将目前的数据复制到新的缓冲区中 */ newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1); if (newsh == NULL) return NULL; /* 未使用的缓冲区长度未新分配缓冲区长度减去当前已使用缓冲区的长度 */ newsh->free = newlen - len; return newsh->buf; }
该函数会先判断剩余的缓冲区是否能够容纳要写入的字符串，如果空间足够则直接返回。如果空间不足以容纳要写入的字符串，则分配空间，分配空间的策略是，如果需要的空间小于 SDS_MAX_PREALLOC 则直接分配当前已使用空间的长度 + 需要分配空间的长度 的两倍 再 加 1 的空间。如果，需要的空间大于 SDS_MAX_PREALLOC 则分配 已使用空间的长度 + 需要分配空间的长度 + SDS_MAX_PREALLOC + 1，就是上面代码中 if ... else ... 的部分。
SDS_MAX_PREALLOC 的定义如下：
#define SDS_MAX_PREALLOC (1024*1024)
也就是说，SDS_MAXPREALLOC 被定义为了 1 MB 大小。
2、惰性空间释放
/** * 清空sds * * s: sds字符串 */ void sdsclear(sds s) { struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr))); /* 将sds字符串的长度加到未分配长度中 */ sh->free += sh->len; /* 将sds字符串的长度设置为0 */ sh->len = 0; /* 将缓冲区清空 */ sh->buf[0] = '\0'; }
所谓的空间惰性释放，就是指不使用 SDS 时，并不是马上释放，而是将 已经使用的空间 和 未使用的空间 相加后的值 赋值给 未使用的空间，已使用的空间设置为 0，然后在缓冲区的首地址中填充一个 \0 即可。
空间不马上释放，在下次使用时，可能就会有充足的空间用于直接使用，而不用再去分配空间，想想 sdsMakeRoomFor 函数，在使用空间足够的时候就直接返回了。
七、最后
Redis 的 SDS 结构体有诸多的优点，而且也拿它的优点与 C 语言常规的字符串进行了比较。其实我觉得使用 SDS 与 C 语言的常规字符串进行比较其实并不公平，SDS 是 Redis 在性能和安全上设计上的一个考量，而 C 语言的字符串是在语言灵活、高效的上的一个考量。就比如说，UDP 是不可靠的传输，但是通过应用层的处理也可以使它变得可靠，但是 UDP 还是 UDP。Redis 只是使用 C 语言的同时，为了 Redis 的需求做了更多的设计。使用 SDS 和 C 语言的常规字符串进行比较的目的只是以对比的方式来去看待 SDS 的设计，并没有说 C 语言不好的意思。
再次感谢黄老师写的关于 Redis 的书籍，能够让好的技术遍地开花。
