Redis设计与实现(1) SDS数据结构

SDS 简单动态字符串 Simple dynamic String 属于Redis的一种数据结构

C字符串 以空字符结尾的字符数组
在Redis中仅用于字符串字面量,即用在一些无须对字符串值进行修改的地方,例如:打印日志

Redis > set msg "Hello World"

键:msg ->SDS
值:Hello World ->SDS

Redis > RPUSH fruits "apple" "banana" "cherry"

键:fruits ->SDS
值:apple ->SDS banana->SDS cherry->SDS

这两个例子只是来表明,存在Redis数据库中的话,这些可更改的字符串都是使用SDS这种数据结构。
除保存数据库中的字符串的值,SDS还被用于缓冲区(buffer)区。
AOF模块中的AOF缓冲区 AOF持久化 。
客户端状态中的输入缓冲区 客户端状态。
有一个问题:我还不理解什么是缓冲区。还有这两个东西都不理解是什么鬼。

SDS定义

SDS数据结构

free:未使用空间
len:等于SDS所保存的字符串长度
buf:char buf[] 字节数组,保存字符串。
遵循C字符,空字符串结尾。但不计入len属性中。

使用SDS的好处:
1.将获取字符串长度所需的复杂度从O(n)下降到了O(1)这确保获取字符串长度的工作不会成为Redis性能的瓶颈。
在SDS数据结构中已经标注了长度。
2.杜绝缓冲区异常
C字符串不记录自身长度,容易造成缓冲区溢出。
例如:<string.h> /strcat函数
char strcat(char dest,const char *src)
strcat将src置入dest的内存空间,而dest内存空间不足的时候,将会溢出到src的空间中。造成拼接的时候,dest的没有改变而src中被意外的修改了。
SDS字符串
SDS API对SDS修改
API检查SDS的空间是否满足修改所需的要求
如果不满足API会自动将SDS的空间扩展至执行修改所需大小
自动扩展 杜绝缓冲区溢出

3.减少修改字符串时带来的内存重分配次数
每次增加或缩短一个C字符串,程序总要对保存这个C字符串的数组进行一次内存重分配操作。
增长时先检查是否足够,如果不检查,会造成缓冲区溢出。
缩短时释放字符串不再使用空间,如果不释放,内存泄露。
内存重分配涉及了复杂的算法->系统调用->耗时
SDS的解决方案:
1.空间预分配 free未使用空间
2.惰性空间释放
SDS字符串缩短操作 free是不变的 但是len会变化 释放的是len。

4.二进制安全
C字符串中的字符必须符合某种编码(比如:ASCII),并且除了字符串的末尾之外,字符串里面不能包含空字符。
会被误认为是结尾。
->只能保存二进制数据
SDS是二进制安全的,输入的数据原样输出。(binary safe)数据写入时是啥样,读取时就是啥样。

5.兼容部分C字符函数
处理文本数据的时候 重用C函数中的代码。

总结:

c字符SDS
获取字符长度的复杂度为O(n)获取字符串长度的复杂度为O(1)
可能会造成缓冲区溢出API是安全的,杜绝缓冲区溢出
修改字符串长度n次,必然需要执行N次内存重分配修改字符串长度N次最多会执行N次内存重分配
只能保存文本数据可以保存文本数据和二进制数据
可以使用<string.h>中的全部函数可以使用<string.h>中的部分函数

本文链接:

https://heyzen.club/index.php/Coder/66.html
1 + 7 =
快来做第一个评论的人吧~