Redis 帝国的神秘使者到访 C 语言帝国

迎接使者大人

“吁····”

这声音从一辆豪华马车中传出，拉车的两匹马儿听到后，立马停在了路边。

“先生，可有什么不对劲？”车夫谨慎地问道。

车中的一位年轻帅小伙拉开了车门前的帘布，说道：“前方有一只百人军队正在赶来，想必是 C 语言帝国的皇家护卫军。”

一小会的功夫，前方百人军队正骑着马来到了马车前。

一名身材魁梧，八尺高，手持一柄长枪的士兵从马背上下来了。

“我是 C 语言帝国的皇家护卫队队长，恭闻使者大人远道而来出使我国，国王特派我前来迎接。” 这位队长笑盈盈说道。

C 语言帝国大殿

“使者大人，前面就是我国的宫殿了，请小心殿堂内的字符串大臣。”护卫队队长说道。

先生心生疑惑地走进了殿堂中，大家的目光都汇聚到了这位年轻人的身上。他在大殿上给国王行了一个礼。

国王说道：“这是 Redis 帝国派来的使者，他给我们带了一个新的数据结构，叫做简单动态字符串，他还有个英文名字，叫做 SDS，全称 Simple Dynamic String”。

在大殿一旁的字符串大臣，脸色显得略微有点难看。

国王继续说道：“SDS 先生，你一路辛苦了，可以介绍下贵国的 SDS 数据结构吗？”

SDS 使者说：“我和 C 语言大国的字符串不一样，我们先来回顾下贵国的字符串表示方式。C 语言字符串是由字符数组组成的，最后一个元素总是空字符 \0。” 使者向殿内大臣展示了一张示意图：

“比如现在中文悟空的拼音 wukong 被放到数组一个长度为 7 的字符数组中，最后一个元素是空字符'\0'。” 使者继续解释道。

旁边的数组大臣和字符串大臣专注地聆听着，好像随时准备发问似的。

SDS 使者说：“我们 Redis 帝国的字符串是用 SDS 表示的，这是在字符数组上进行了增强，是一种新的结构体”

随后使者拿出了一卷羊皮纸，上面写着一份代码：

 struct sdshdr {
    // 字符数组，用于保存字符串
    // 和 C 语言中保存字符串的字符数组一样。
    char buf[];
     
    // 记录 buf 数组中已使用字节的数量，等于 SDS 锁保存字符串的长度。 
     int len;
     
    // 记录 buf 数组中未使用字节的数量
     int free;
 }

随后 SDS 使者拿出来了一张准备好的示例图解释道：

简单动态字符串 SDS 结构是由三部分组成的：

• buf 数组属性和 C 语言帝国一样，都用了 7 个字节来保存 wukong，最后一个元素是空字符。
• len 属性这个值为 6，代表这个 SDS 保存了一个 6 字节长的字符串（最后一个空字符不计算 len 属性中）。
• free 属性的值为 0，代表这个 SDS 没有其他剩余空间来存放字符了。

注意：数组中的空字符是自动加到字符串末尾的，由 SDS 的函数自动完成。为什么要和 C 语言的字符串的空字符结尾保持一致呢？是因为这样可以重用一部分 C 字符串函数库里面的函数。

旁边的字符串大臣按捺不住地问道：“你这样做，我看不到什么好处呢？反而增加了空间来保存 free 和 len 属性。”

众人听完字符串大臣的话，都若有所思。

“大家不要着急，且听使者解释。”国王看着众人疑惑的脸说道。

“因为我用 len 属性记录了字符串的总长度，所以要是有程序想要访问 SDS 的 len 属性，就可以立即知道保存的字符串长度，简单来说就是复杂度为 O(1)。比如我刚刚举的例子，可以立即知道 SDS 的长度为 6 字节。” 使者不紧不慢地说道。

国王将目光投向了字符串大臣，然后说道：“字符串爱卿，我们的 C 字符串计算长度需要多久？”

“尊敬的国王大人，我们计算 C 字符串的长度需要遍历整个字符串，对遇到的每个字符进行计数，直到遇到代表字符串结尾的空字符为止。上面的例子，我们要记 6 次，也就是复杂度为 O(N)。” 字符串大臣连忙回答。

“那我们也太慢了吧...” 国王小声嘀咕着。

内存分配的天赋

杜绝缓冲区溢出

“听说 SDS 在内存分配上有很大的天赋，可以给我们说说看吗？”C 语言帝国的内存大臣提到。

“首先我可以杜绝缓冲区溢出。” SDS 使者自豪地说道。

提示：缓冲区是对原始磁盘块的临时存储，用来缓存将要写入磁盘的数据。这样，内核就可以把分散的写集中起来，统一优化磁盘写入。

“快给我说说，我发现总是有缓冲区溢出的异常出现，就是因为 C 字符串的一些不正规操作导致的。”内存大臣说完瞥了一眼字符串大臣。

“这可不管我的事，都是那些程序员不正规操作造成的。”字符串赶紧向内存大臣解释。

“这还跟程序员有关？”国王追问着。

“国王大人，情况是这样的，假设内存中有紧邻的 C 字符串 S1 和 S2，S1 保存了字符串 WuKong（悟空），而 S2 字符串保存了字符串ZiXia（紫霞），给您看个示意图。”SDS 使者拿出了一张早已准备好的原理图：

“如果某个程序员执行了如下拼接字符串命令，又没有提前为 S1 分配足够的空间，那就悲剧了。”字符串大臣继续说道。

strcat(s1, " QuJing") // 取经

“因为 S1 没有分配足够的空间，所以在 strcat 函数执行之后，S1 d的数据将会溢出到 S2 所在的空间中，导致 S2 保存的内容被意外地修改，这就是缓冲区溢出。但这个跟我无关啊，是程序员干的。”字符串大臣一脸无辜地说道。

“对对对，就是这样，害得我好惨。”内存大臣嘀咕道。

“请问使者有什么高见？”国王大人毕恭毕敬地说道。

“和 C 字符串相比，SDS 的空间分配策略就杜绝了这种情况发生。”SDS 使者平静地说道。

“当 SDS API，比如拼接的 API，需要对 SDS 进行修改时，API 会先检查 SDS 的空间是否满足修改所需的要求，不满足的话，则会自动扩容。” SDS 解释道。

“妙啊！对于 C 字符串来说，每次修改字符串长度都要进行内存重分配的操作，涉及到了复杂的算法，还可能需要执行系统调用，非常耗时。” 内存大臣大声感叹道。

“那你们的自动扩容是每次修改字符串时都需要么？” 字符串大臣疑惑道。

“当然不是，我们扩容的时候不仅会为 SDS 分配修改所必须要的空间，而且还会为 SDS 分配额外的未使用空间。”

“快给我们讲讲吧。”国王急不可待的说道。

空间预分配

“我这个功能叫做空间预分配。分配的规则如下。”使者义正言辞地解释道。

• 如果对 SDS 进行修改之后，SDS 的长度（len 属性决定），还是小于 1 MB 的话，那么将会分配和 len 属性相同大小的未使用空间，那么 SDS len 属性的值将 free 属性的值相同。比如说当前 SDS 的 len = 6，加上 7 个字符后，len 的值变为了 13，还是小于 1 MB 的，然后 SDS 会被分配 13 字节的未使用空间。那么 SDS 的实际长度就是 13 + 13 + 1 = 27 字节（额外的字节用于保存空字符）。
• 如果对 SDS 进行修改之后，SDS 的长度大于等于 1 MB，那么会分配 1 MB 的额外空间。也就是说 SDS 长度等于必须存放的空间的长度 + 1MB 的未使用空间的长度。比如说 SDS 修改之后，变成了 10 MB，那么会分配 1 MB 的未使用空间，最后 buf 数组的实际长度等于 30 MB + 1 MB + 1 byte。

听完使者说完，国王还是有点懵，但是身边的字符串大臣和内存大臣已经听懂了，不亏是 C 语言帝国的两大支柱，这点扩容知识还是很容易理解的。

“可否举个例子呀，寡人实在无法理解。”国王摇摇头的说道。

“好的，国王。我还是用悟空取经来说明。”使者答应道。

“首先 SDS 存放的是悟空的英文 WuKong，然后追加一个取经的英文 QuJing，我们来看看怎么扩容的。”使者继续说道。

提示：SDS 的 API 中其实也有一个用于执行拼接操作的 sdscat 函数，他可以将一个 C 字符串拼接到 SDS 所保存的字符串后面，但是在执行拼接操作之前，sdscat API 会先检查给定 SDS 的空间是否足够，如果不够的话， sdscat 会先扩展 SDS 的空间，然后才执行拼接操作。

s = "WuKong";
sdscat("s", " QuJing");

WuKong总共占了 6 个字符， QuJing 占了 7 个字符（包含前面的空格）。最后拼接的结果就是：WuKong Qujing。我还是来画个图给大家看下吧。”

最开始 SDS 长这样：

后来拼接了 " QuJing" 的时候，free = 0，不足以存放，所以开始扩容，首先会增加 7 个字符的空间，len = 6 + 7 = 13，然后再分配额外的未使用空间，空间大小等于 len 的值，也是 13，所以 free = len = 13。

拼接后 SDS 长下面这样：

如果还想再拼接一个字符串在后面，比如字符串 GuiLai（中文：归来，占 6 个字符），那是不用再扩容，因为未使用的 13 个字符串空间足以容纳这 6 个字符。通过简单的计算也可以得出这个结果：Total = 13 + 13 = 26，6 + 7 + 7 = 20 < 26。

众人听完使者的解释后，都赞叹不已。

突然大殿之中传来一个声音：“那假设每次拼接的字符串都超过了未分配空间，是不是每次都得扩容？”众人将目光转向了声音的方向，字符串大臣那里。

“的确如此，不过通过这种预分配的扩容方式，SDS 将必定 N 次扩容降低为最多 N 次。”使者微笑道。

“那缩短字符串的时候，会立即回收多余的空间吗？”字符串大臣追问道。

“我们有惰性空间释放的功能，不会立即释放多出来的字节，而是等待将来使用。而且当有需要的时候，会有专门的 API 来真正地释放 SDS 的空间。”使者解释道。

众人纷纷点头，国王总结道：“通过 SDS 的预分配和惰性空间释放的方式，确实减少了分配空间的次数，难怪 Redis 会这么快的。”

字符串大臣静静地听着国王的总结，生怕国王一声令下要改造 C 语言帝国的字符串形式。

“你去公众号回复下 SDS 吧，听说那里可以下载 Redis SDS 的源码。研究下，后面可能改造下我们的字符串。”国王对着字符串大臣说道。

巨人的肩膀：

Redis 设计与实现