你好,我是悟空。
“使者大人,前面就是我国的宫殿了,请小心殿堂内的字符串大臣
。”护卫队队长说道。
先生心生疑惑地走进了殿堂中,大家的目光都汇聚到了这位年轻人的身上。他在大殿上给国王行了一个礼。
国王说道:“这是 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 结构是由三部分组成的:
wukong
,最后一个元素是空字符。注意:数组中的空字符是自动加到字符串末尾的,由 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 的实际长度就是 13 + 13 + 1 = 27 字节(额外的字节用于保存空字符)。听完使者说完,国王还是有点懵,但是身边的字符串大臣和内存大臣已经听懂了,不亏是 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 设计与实现