Redis基础数据结构——简单动态字符串(SDS)

2021年9月7日 136点热度 2人点赞 0条评论

Redis中的字符串的底层实现并没有简单的使用C语言传统的字符串表示,而是自己构建了一种名为简单动态字符串的数据结构来表示字符串。

SDS的作用主要有两个:其一是用来保存数据库中的字符串值;其二是被用作缓冲区,比如AOF模块中的AOF缓冲区以及客户端状态中的输入缓冲区。

SDS的定义

SDS结构的定义如下:

struct sdshdr{
    //记录buf数组中已经使用字节的数量
    //等于SDS所保存字符串的长度
    int len;

    //记录buf数组中未使用字节的数量
    int free;

    //字节数组,用于保存字符串
    char buf[];
};

值得一提的是,SDS遵循C字符串以空字符结尾的惯例,保存空字符的1字节空间不计算在SDS的len属性里面,并且为空字符分配额外的1字节空间,以及添加空字符到字符串末尾等操作,都是SDS函数自动完成的,所以这个空字符对于SDS的使用者来说是完全透明的。

SDS相较于C字符串的优势

SDS可以看作是在C字符串的基础上封装而成的,增加了几个字段,可以更好的适应Redis的需求。相比较C字符串,SDS有以下优势。

常数复杂度获取字符串长度

C字符串并没有记录自身的长度信息,如果要获取一个C字符串的长度就必须进行一次遍历,时间复杂度为$O(n)$。而SDS的len字段记录了字符串的长度,所以可以以$O(1)$的复杂度获取字符串的长度。

杜绝缓冲区溢出

C字符串并不记录自身的长度,因而容易造成缓冲区溢出的问题。比如,在进行字符串拼接的时候,默认用户已经为最终的字符串分配了足够的空间,如果程序员不当操作,就会造成缓冲区溢出。

与C字符串不同,SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能性:当对SDS进行修改的时候,首先会检查SDS的空间是否满足修改所需要的要求,如果不满足的话,会自动将SDS的空间扩展至执行修改所需的大小,然后才执行实际的修改操作,因而不会出现缓冲区溢出的问题。

减少修改字符串时带来的内存重分配次数

由于C字符串不记录自身的长度,所以每次增长或者缩短一个C字符串的长度的时候,程序都总要对这个C字符串的数组进行一次内存重分配操作。

因为内存重分配涉及复杂的算法,并且可能需要执行系统调用,所以它通常是一个比较耗时的操作。

而SDS可以通过空间预分配和惰性空间释放两种优化策略减少修改字符串时带来的内存重分配次数。

空间预分配:当需要对SDS进行空间扩展的时候,程序不仅会为SDS分配修改所必须的空间,还会为SDS分配额外的未使用空间。额外分配的未使用空间大小由以下规则决定:如果对SDS进行修改之后,SDS的长度将小于1MB,那么程序分配和len属性同样大小的未使用空间,这时候SDS的len属性的值将和free属性的值相同;如果对SDS进行修改之后,SDS的长度将大于等于1MB,那么程序就会分配1MB的未使用空间。在扩展SDS空间之前,程序会先检查未使用空间是否足够,如果足够的话,程序就会直接使用未使用空间,从而减少了内存重分配的次数。空间预分配用于优化SDS的字符串增长操作。

惰性空间释放:当需要缩短SDS保存的字符串时,程序并不立即使用内存重分配来回收缩短后多出来的字节,而是使用free属性将这些字节的数量记录下来,并等待将来使用。通过惰性空间释放策略,SDS避免了缩短字符串时所需的内存重分配操作,并且为将来可能有的增长操作提供了优化。惰性空间释放用于优化SDS的字符串缩短策略

二进制安全

C字符串中的字符必须符合某种编码,并且除了字符串的末尾之外,字符串里面不能包含空字符,否则最先被程序读入的空字符将被误认为是字符串结尾,这些限制使得C字符串只能保存文本数据,而不能保存像图片、音频、视频、压缩文件这样的二进制数据。而SDS解决了这个问题,并且确保了 Redis可以适用于各种不同的使用场景。SDS使得Redis不仅可以保存文本数据,还可以保存任意格式的二进制数据。也就是说,SDS是二进制安全的。

兼容部分C字符串函数

SDS遵循了C字符串以空字符结尾的惯例,这可以让那些保存文本数据的SDS重用一部分库定义的函数。

SDS与C字符串的区别

C字符串 SDS
获取字符串长度的复杂度为$O(N)$ 获取字符串长度的复杂度为$O(1)$
API是不安全的,可能会造成缓冲区溢出 API是安全的,不会造成缓冲区溢出
修改字符串长度N次必然需要执行N次内存重分配 修改字符串长度N次最多需要执行N次内存重分配
只能保存文本数据 可以保存文本或者二进制数据
可以使用所有库中的函数 可以使用一部分库中的函数

agedcat_xuanzai

这个人很懒,什么都没留下

文章评论