Redis内部数据结构详解之简单动态字符串(sds)

痛定思痛。 2023-10-17 15:53 111阅读 0赞

> 本文所引用的源码全部来自Redis2.8.2版本。
> 
> Redis中简单动态字符串sds数据结构与API相关文件是：sds.h, sds.c。

> 转载请注明，本文出自：[http://blog.csdn.net/acceptedxukai/article/details/17482611][http_blog.csdn.net_acceptedxukai_article_details_17482611]

## 预备知识 ##

> 下面介绍有关sizeof计算参数所占字节数的部分实例，方便下面对sds数据结构地址的计算理解

\[cpp\] [view plain][] [copy][view plain]

1. **typedef****struct** Node\{ 
2. **int** len; 
3. **char** str\[5\]; 
4. \}Node; 
5. **typedef****struct** Node2\{ 
6. **int** len; 
7. **char** str\[\]; 
8. \}Node2; 
9. **sizeof**(**char**\*) = 4 
10. **sizeof**(Node\*) = 4 
11. **sizeof**(Node) = 12 
12. **sizeof**(Node2) = 4 
13.

> 简单解释下上述sizeof的结果值，前两个等于4是因为指针；第三个值等于12是因为len占4个字节，char str\[5\]实际应该占5个字节，但是由于计算机内存对齐的原因其实际占8个字节；最后一个等于4，因为char str\[\]没有实际长度，不被分配内存。
> 
> 了解sizeof之后还需要了解stdarg.h中的va\_list, va\_start,va\_end,va\_copy的知识，这个在网上有很多就不多解释了。
> 
>   
>

## 简单动态字符串sds与char\*对比 ##

> sds在Redis中是实现字符串对象的工具，并且完全取代char\*.
> 
> char\*的功能比较单一，不能实现Redis对字符串高效处理的需求，char\*的性能瓶颈主要在：计算字符串长度需要使用strlen函数，该函数的时间复杂度是O(N)，而在Redis中计算字符串长度的操作十分频繁，O(N)的时间复杂度完全不能接受，sds实现能在O(1)时间内得到字符串的长度值；同时，在处理字符串追加append操作时，如果使用char\*则需要多次重新分配内存操作。
> 
>   
>

## 简单动态字符串sds数据结构 ##

\[cpp\] [view plain][] [copy][view plain]

1. **typedef****char** \*sds; 
2. 
3. **struct** sdshdr \{ 
4. **int** len; //buf已占用的长度，即当前字符串长度值
5. **int** free; //buf空余可用的长度，append时使用
6. **char** buf\[\]; //实际保存字符串数据
7. \};

> 通过增加len字段，就可以实现在O(1)时间复杂度内得到字符串的长度，增加free字段，在需要append字符串时，如果free的值大于等于需要append的字符串长度，那么直接追加即可，不需要重新分配内存。sizeof(sdshdr) = 8.

## 简单动态字符串sds中函数API ##

<table style="border-collapse:collapse; border-spacing:0px; max-width:100%; color:rgb(69,69,69); font-family:&quot;PingFang SC&quot;,&quot;Microsoft YaHei&quot;,SimHei,Arial,SimSun; font-size:16px"> 
 <tbody style=""> 
 <tr style=""> 
 <td style=""> 函数名称 </td> 
 <td style=""> 作用 </td> 
 <td style=""> 复杂度 </td> 
 </tr> 
 <tr style=""> 
 <td style=""> sdsnewlen </td> 
 <td style=""> 创建一个指定长度的sds，接受一个指定的C字符串作为初始化值 </td> 
 <td style=""> O(N) </td> 
 </tr> 
 <tr style=""> 
 <td style=""> sdsempty </td> 
 <td style=""> 创建一个只包含空字符串””的sds </td> 
 <td style=""> O(N) </td> 
 </tr> 
 <tr style=""> 
 <td style=""> sdsnew </td> 
 <td style=""> 根据给定的C字符串，创建一个相应的sds </td> 
 <td style=""> O(N) </td> 
 </tr> 
 <tr style=""> 
 <td style=""> sdsdup </td> 
 <td style=""> 复制给定的sds </td> 
 <td style=""> O(N) </td> 
 </tr> 
 <tr style=""> 
 <td style=""> sdsfree </td> 
 <td style=""> 释放给定的sds </td> 
 <td style=""> O(1) </td> 
 </tr> 
 <tr style=""> 
 <td style=""> sdsupdatelen </td> 
 <td style=""> 更新给定sds所对应的sdshdr的free与len值 </td> 
 <td style=""> O(1) </td> 
 </tr> 
 <tr style=""> 
 <td style=""> sdsclear </td> 
 <td style=""> 清除给定sds的buf，将buf初始化为””，同时修改对应sdshdr的free与len值 </td> 
 <td style=""> O(1) </td> 
 </tr> 
 <tr style=""> 
 <td style=""> sdsMakeRoomFor </td> 
 <td style=""> 对给定sds对应sdshdr的buf进行扩展 </td> 
 <td style=""> O(N) </td> 
 </tr> 
 <tr style=""> 
 <td style=""> sdsRemoveFreeSpace </td> 
 <td style=""> 在不改动sds的前提下，将buf的多余空间释放 </td> 
 <td style=""> O(N) </td> 
 </tr> 
 <tr style=""> 
 <td style=""> sdsAllocSize </td> 
 <td style=""> 计算给定的sds所占的内存大小 </td> 
 <td style=""> O(1) </td> 
 </tr> 
 <tr style=""> 
 <td style=""> sdsIncrLen </td> 
 <td style=""> 对给定sds的buf的右端进行扩展或缩小 </td> 
 <td style=""> O(1) </td> 
 </tr> 
 <tr style=""> 
 <td style=""> sdsgrowzero </td> 
 <td style=""> 将给定的sds扩展到指定的长度，空余的部分用\0进行填充 </td> 
 <td style=""> O(N) </td> 
 </tr> 
 <tr style=""> 
 <td style=""> sdscatlen </td> 
 <td style=""> 将一个C字符串追加到给定的sds对应sdshdr的buf </td> 
 <td style=""> O(N) </td> 
 </tr> 
 <tr style=""> 
 <td style=""> sdscpylen </td> 
 <td style=""> 将一个C字符串复制到sds中，需要依据sds的总长度来判断是否需要扩展 </td> 
 <td style=""> O(N) </td> 
 </tr> 
 <tr style=""> 
 <td style=""> sdscatprintf </td> 
 <td style=""> 通过格式化输出形式，来追加到给定的sds </td> 
 <td style=""> O(N) </td> 
 </tr> 
 <tr style=""> 
 <td style=""> sdstrim </td> 
 <td style=""> 对给定sds，删除前端/后端在给定的C字符串中的字符 </td> 
 <td style=""> O(N) </td> 
 </tr> 
 <tr style=""> 
 <td style=""> sdsrange </td> 
 <td style=""> 截取给定sds，[start,end]字符串 </td> 
 <td style=""> O(N) </td> 
 </tr> 
 <tr style=""> 
 <td style=""> sdscmp </td> 
 <td style=""> 比较两个sds的大小 </td> 
 <td style=""> O(N) </td> 
 </tr> 
 <tr style=""> 
 <td style=""> sdssplitlen </td> 
 <td style=""> 对给定的字符串s按照给定的sep分隔字符串来进行切割 </td> 
 <td style=""> O(N) </td> 
 </tr> 
 </tbody> 
</table>

## Redis中sds实现的细节解析 ##

\[cpp\] [view plain][] [copy][view plain]

1. **static****inline****size\_t** sdslen(**const** sds s) \{ 
2. **struct** sdshdr \*sh = (**void**\*)(s-(**sizeof**(**struct** sdshdr))); 
3. **return** sh->len; 
4. \} 
5. 
6. **static****inline****size\_t** sdsavail(**const** sds s) \{ 
7. **struct** sdshdr \*sh = (**void**\*)(s-(**sizeof**(**struct** sdshdr))); 
8. **return** sh->free; 
9. \}

> 上述两个函数sdslen, sdsavail分别用来计算给定的sds的字符串长度和给定的sds空余的字节数。仔细观察会发现函数的参数是sds即char \*，接着通过一行代码就能得到给定sds所对应的sdshdr数据结构，貌似很神奇的样子啊！
> 
> 看Redis中初始化一个sds的代码

\[cpp\] [view plain][] [copy][view plain]

1. /\*init: C字符串，initlen：C字符串的长度\*/
2. sds sdsnewlen(**const****void** \*init, **size\_t** initlen) \{ 
3. **struct** sdshdr \*sh; 
4. 
5. **if** (init) \{ 
6. sh = zmalloc(**sizeof**(**struct** sdshdr)+initlen+1); 
7. \} **else** \{ 
8. sh = zcalloc(**sizeof**(**struct** sdshdr)+initlen+1); 
9. \} 
10. **if** (sh == NULL) **return** NULL; 
11. sh->len = initlen; 
12. sh->free = 0; 
13. **if** (initlen && init) 
14. memcpy(sh->buf, init, initlen); 
15. sh->buf\[initlen\] = '\\0'; 
16. **return** (**char**\*)sh->buf; 
17. \} 
18. 
19. /\* Create a new sds string starting from a null termined C string. \*/
20. sds sdsnew(**const****char** \*init) \{ 
21. **size\_t** initlen = (init == NULL) ? 0 : strlen(init); 
22. **return** sdsnewlen(init, initlen); 
23. \}

> 核心函数是sdsnewlen，sh = zmalloc(sizeof(struct sdshdr)+initlen+1)为sdshdr数据结构分配内存，该段内存分为两个部分：sdshdr数据结构所占的内存数sizeof(sdshdr)，我们知道其值为8；initlen+1为sdshdr数据结构中buf的内存。而sdsnewlen函数的返回值是buf的首地址，这样在看sdslen函数，通过给定的sds首地址减去sizeof(sdshdr)，那么就应该是该sds所对应的sdshdr数据结构首地址，自然就能得到sh->len与sh->free。这种操作真的很神奇，这就是C语言指针的妙用，而且使用这种方式，很好的隐藏了sdshdr数据结构，对外接口全部同C字符串类似，却达到了求取sds字符串长度时间复杂度O(1)与降低append操作频繁申请内存的效果。

## 简单动态字符串sds空间扩展操作解析 ##

sds模块的函数都比较简单，不一一介绍，主要讲解sds如何对空间进行扩展的，扩展操作主要在append操作的时候使用。

\[cpp\] [view plain][] [copy][view plain]

1. /\* Enlarge the free space at the end of the sds string so that the caller
2. \* is sure that after calling this function can overwrite up to addlen
3. \* bytes after the end of the string, plus one more byte for nul term.
4. \*
5. \* Note: this does not change the \*length\* of the sds string as returned
6. \* by sdslen(), but only the free buffer space we have. \*/
7. //对sdshdr的buf进行扩展
8. sds sdsMakeRoomFor(sds s, **size\_t** addlen) \{ 
9. **struct** sdshdr \*sh, \*newsh; 
10. **size\_t** free = sdsavail(s); //查看当前sds空余的长度
11. **size\_t** len, newlen; 
12. 
13. **if** (free >= addlen) **return** s; //不需要扩展
14. len = sdslen(s); //得到当前sds字符串的长度
15. sh = (**void**\*) (s-(**sizeof**(**struct** sdshdr))); //得到sdshdr首地址
16. newlen = (len+addlen); //追加之后sds新的长度
17. **if** (newlen < SDS\_MAX\_PREALLOC) //SDS\_MAX\_PREALLOC (1024\*1024)，扩展的具体方法
18. newlen \*= 2; 
19. **else**
20. newlen += SDS\_MAX\_PREALLOC; 
21. newsh = zrealloc(sh, **sizeof**(**struct** sdshdr)+newlen+1); //重新分配内存
22. **if** (newsh == NULL) **return** NULL;//分配内存失败
23. 
24. newsh->free = newlen - len; //新的sds空余长度
25. **return** newsh->buf; 
26. \}

## 小结 ##

> Redis的简单动态字符串sds对比C语言的字符串char\*，有以下特性：

> > 1) 可以在O(1)的时间复杂度得到字符串的长度
> 
> > 2) 可以高效的执行append追加字符串操作
> 
> > 3) 二进制安全

> sds通过判断当前字符串空余的长度与需要追加的字符串长度，如果空余长度大于等于需要追加的字符串长度，那么直接追加即可，这样就减少了重新分配内存操作；否则，先用sdsMakeRoomFor函数先对sds进行扩展，按照一定的机制来决定扩展的内存大小，然后再执行追加操作，扩展后多余的空间不释放，方便下次再次追加字符串，这样做的代价就是浪费了一些内存，但是在Redis字符串追加操作很频繁的情况下，这种机制能很高效的完成追加字符串的操作。

> 由于sds其他的函数比较简单，如果有问题的可以在回复中提出。
> 
> 指出一点2.8源码中sds作者作出的注释有一处是错误的，具体就不列出了。
> 
> 最后感谢黄健宏（huangz1990）的Redis设计与实现及其他对Redis2.6源码的相关注释对我在研究Redis2.8源码方面的帮助。

来源:http://blog.csdn.net/acceptedxukai/article/details/17482611

[http_blog.csdn.net_acceptedxukai_article_details_17482611]: http://blog.csdn.net/acceptedxukai/article/details/17482611
[view plain]: http://blog.csdn.net/acceptedxukai/article/details/17482611#