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 数组的实际长度等于 10 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 设计与实现
500 人 Java、架构交流群
扫码加入，一起进阶。
本文分享自微信公众号 - 悟空聊架构（PassJava666）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
