Redis—简单动态字符串(SDS)

作者: 博客园精华区  更新时间:2021-05-08 16:59:00  原文链接


目录

  • Redis—简单动态字符串(SDS)

Redis—简单动态字符串(SDS)

这两天我原本打算学习一下 若依 这个老生常谈的开源的后端管理系统(如果你没听过,在将来的某一天也会听说甚至用到),拿到这个系统的前后端分离版后, 若依码云项目地址 ,一启动发现需要Redis服务,遂转战学习Redis(Redis也是老生常谈了~)

白泽预计将花费一个月的时间去学习Redis的设计与实现,并尽量保证文章的输出,我们共勉~

本次介绍一个Redis的数据类型,简单动态字符串,SDS(simple dynamic string),因为Redis是用C语言写的,而且C语言本身就有字符串这个数据类型,那就要提出疑问: 为啥不直接用C语言的字符串,而要新发明一种新的字符串类型呢?

事实上,即使我没学过Redis,也听闻过它可以以键值对的形式存储数据,它很快。但它的快绝不仅仅是键值对的存储形式带来的,SDS的存在就是帮助Redis更快,更安全~

SDS的定义

//sds的存储结构
struct sdshdr {
	int len;	//记录buf数组中已经使用的字节的数量
	int free;	//记录buf数组中还未使用的字节的数量
	char buf[]; //字节数组,用于保存字符串
};

很明显,SDS内部就是一个C语言的字符串(字节数组),只是多了两个变量存放当前的长度和剩余的长度,下面这张图模拟了当sds存放了 'Redis' 字符串后的情况

SDS遵循C字符串以空字符结尾的惯例,保存空字符的1字节空间不计算在SDS的len属性中,好处是SDS可以直接重用一部分的C字符串函数库中的函数(只要SDS内部的buf也是以'\0'结尾,那就是一个C语言的字符串啊,有啥不能用的~)

当然还可以像下面这张图这样,5为已使用的buf数组的长度,5为未使用的数组的长度,而下面这种场景才是更多的出现在Redis中的。接下来就讲讲通过 free,len和C语言字符串buf的配合 ,如何使Redis比单纯使用C语言的字符串更快,更安全吧

SDS与C字符串的区别

1. 常数复杂度获取字符串长度:

因为SDS的free直接就记录了buf数组的使用长度,因此如果要获取buf的长度,SDS只需要O(1)的时间复杂度,而C的字符串需要O(N), 因此更快!

2. 杜绝缓冲区溢出:

如上图:因为C语言字符串不记录本身的长度,如果原本连续的内存中存放了str1 = 'Redis',str2 = 'MySQL'两个字符串,此时执行某个操作将str1替换为下方的str1 = 'Hello BaiZe',那么str1的内容将会溢出到原本str2的空间中

如果使用SDS的API修改SDS内容时,如果buf剩余空间不足,API将先扩容SDS的空间,然后再修改buf数组的内容。 因此更安全!

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

C语言的字符串无论是增长还是缩短,每次都需要程序重新分配内存(因为可能会影响到内存已经存在的数据),这就意味着每次都将消耗一定资源去完成这个任务。

而Redis作为数据库,数据可能会频繁修改,每次都去内存重分配就慢了。而在SDS中,len、free和buf数组相配合,就能从两个角度去优化频繁修改时时间的消耗

  • 空间预分配:

    当SDS需要扩容的时候(进行一次内存重新分配),扩容后len小于1MB,那么程序分配和len属性相同大小的free空间,则本次扩容后SDS的free会等于此时SDS的len, 当然空字符'\0'依旧会占额外的一字节的空间 ,本次扩容结束后SDS所占空间为:len + free + 1byte

    如果扩容后len大于1MB,那么程序会分配1MB的未使用free空间(所以最多就是给你分配1MB的free),此时SDS所占用空间为:len + free(1MB) + 1byte

    说到底 空间预分配 的目的就是每次扩容时多申请一些空间(每次扩容也是一次内存的重新分配),以备下次buf数组长度增长时 或许可以不去 申请内存的重新分配,但 最差的情况下 每次多申请的空间都不够下次用的,那依旧退化为C语言字符串扩容时每次都需要重新分配内存的情况

  • 惰性空间释放

    有扩容就有缩短,当SDS的buf变短时,程序并不直接进行内存的重新分配,而是只是增加free的值, 这比进行一次内存重新分配缩短buf快很多! buf数组多余的5个空间依旧保留,如果将来要对SDS进行增长操作还能用上。 当然如果有需要SDS也提供了API对这些空间进行真正的释放

4. 二进制安全

C语言字符串以空字符'\0'判断字符串是否结束,那么下面这种含有两个空字符的字符串就无法完整地存入C语言的字符串,因此也无法存储二进制数据(图片、视频、音频等),但是SDS的长度是由len定义的,因此内部也可以存放空字符'\0',也可以用于保存二进制数据( 啥都能存

小结

C字符串和SDS的区别