阿里面试这样问：redis 为什么把简单的字符串设计成 SDS？
Hollis
共 2849字，需浏览 6分钟
·
2021-04-28 13:49
面试官：了解redis的String数据结构底层实现嘛?
铁子：当然知道，是基于SDS实现的
面试官：redis是用C语言开发的，那为啥不直接用C的字符串，还单独设计SDS这样的结构呢?
铁子：·····
“其实看得出面试官是想看看，铁子是只停留在redis的使用层面，还是对底层数据结构有过更深入的研究，面试嘛都爱这样问大家都懂得。
redis是用C写的，但它却没有完全直接使用C的字符串，而是自己又重新构建了一个叫简单动态字符串SDS（simple dynamic string）的抽象类型。redis也支持使用C语言的传统字符串，只不过会用在一些不需要对字符串修改的地方，比如静态的字符输出。redis，往往会经常性的修改字符串的值，这个时候就会用SDS来表示字符串的值了。有一点值得注意：在redis数据库中，key-value键值对含有字符串值的，都是由SDS来实现的。redis执行一个最简单的set命令，这时redis会新建一个键值对。127.0.0.1:6379> set xiaofu "AAA"
key和value都是一个字符串对象，而对象的底层实现分别是两个保存着字符串xiaofu和AAA的SDS结构。127.0.0.1:6379> lpush xiaofu "AAA" "BBB"
SDS结构
len、free、buf[]这三个属性组成。struct sdshdr{
int free; // buf[]数组未使用字节的数量
int len; // buf[]数组所保存的字符串的长度
char buf[]; // 保存字符串的数组
}
buf[]为实际保存字符串的char类型数组；free表示buf[]数组未使用字节的数量；len表示buf[]数组所保存的字符串的长度。
buf[]保存长度为6个字节的字符串，未使用的字节数free为0，但是眼尖的同学会发现这明明是7个字符，还有一个"\0"啊？SDS没有完全直接使用C的字符串，还是沿用了一些C特性的，比如遵循C的字符串以空格符结尾的规则，这样还可以使用一部分C字符串的函数。而对于SDS来说，空字符串占用的一字节是不计算在len属性里的，会为他分配额外的空间。效率高
redis，经常会通过STRLEN命令得到一个字符串的长度，在SDS结构中len属性记录了字符串的长度，所以我们获取一个字符串长度直接取len的值，复杂度是O(1)。
redis的性能瓶颈，所以SDS性能更好一些。数据溢出
“AAA”改成“AAA123”，可之前分配的内存只有6个字节，修改后的字符串需要9个字节才能放下啊，怎么搞？
侵占相邻字符串的空间，自身数据溢出导致其他字符串的内容被修改。len是否满足，不满足则自动扩容空间至修改所需的大小，然后再执行修改,如下图所示。
“AAA”的6个字节扩容到“AAA123”9个字节后，发现free属性的值变成了扩容后字符串的总长度，这就涉及到下边要说的内存重分配策略了。内存重分配策略
redis作为一个数据库，数据肯定会被频繁修改，如果每次修改都要执行一次内存重分配，那么就会严重影响性能。1.空间预分配
free，下次再修改就先检查未使用空间free是否满足，满足则不用在扩展空间。redis可以有效的减少字符串连续增长操作，所产生的内存重分配次数。
free的规则：如果对 SDS 字符串修改后， len值小于1M，那么此时额外分配未使用空间free的大小与len相等。如果对 SDS 字符串修改后， len值大于等于1M，那么此时额外分配未使用空间free的大小为1M。
2.惰性空间释放
free属性将这些空间记录下来，如果后续有增长操作，则可直接使用。
数据格式多样性
\0空字符结尾标识一个字符串结束，所以字符串里边是不能包含\0的，不然就会被误认是多个。Buf数组中的数据，所以对存入其中的数据未做任何的限制、过滤，只要存进来什么样，取出来还是什么样。总结
有道无术，术可成；有术无道，止于术
欢迎大家关注Java之道公众号
好文章，我在看❤️
评论