你好，我是悟空。
旁边的字符串大臣按捺不住地问道：“你这样做，我看不到什么好处呢？反而增加了空间来保存 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 分配额外的未使用空间。”
“快给我们讲讲吧。”国王急不可待的说道。
空间预分配
“我这个功能叫做空间预分配。分配的规则如下。”使者义正言辞地解释道。
听完使者说完，国王还是有点懵，但是身边的字符串大臣和内存大臣已经听懂了，不亏是 C 语言帝国的两大支柱，这点扩容知识还是很容易理解的。
“可否举个例子呀，寡人实在无法理解。”国王摇摇头的说道。
“好的，国王。我还是用悟空取经来说明。”使者答应道。
“首先 SDS 存放的是悟空的英文 WuKong，然后追加一个取经的英文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源创计划”，欢迎正在阅读的你也加入，一起分享。