面试官：你知道redis的String数据结构的底层实现吗？铁子：当然是基于SDS的。面试官：Redis是用C语言开发的，为什么不直接用C语言的字符串呢？单独设计一个像SDS这样的结构怎么样？铁子：“其实看得出来，面试官是想看看铁子是仅仅停留在redis的使用层面，还是对底层数据结构做了更深入的研究，大家都喜欢在面试中问这样的问题。我们知道redis是用C写的，但是它并没有完全直接使用C的字符串，而是重新构建了一个简单的动态字符串，叫做SDS（simpledynamicstring））抽象类型，Redis也支持C语言的传统字符串，但是它会用在一些不需要修改字符串的地方，比如静态字符输出，我们在开发中使用redis的时候，经常会频繁修改字符串的值，这时候就会用SDS来表示字符串的值。值得注意的一点：在redis数据库中，包含字符串值的key-value键值对都是由SDS实现的。例如：在redis中执行最简单的set命令，然后redis会创建一个新的键值对。127.0.0.1:6379>setxiaofu"AAA"此时键值对的key和value都是一个字符串对象，对象的底层实现是两个存储字符串xiaofu和AAA的SDS结构。再举个例子：我把数据push到一个list里面，redis会新建一个key-valuepair。127.0.0.1:6379>lpushxiaofu"AAA""BBB"此时键值对的key同上，仍然是SDS实现的字符串对象。键值对的值是一个包含两个字符串对象的列表对象，这两个对象的底层也是由SDS实现的。执行。SDS结构SDS值的数据结构，主要由三个属性组成：len,free,buf[].structsdshdr{intfree;//buf[]数组中未使用的字节数intlen;//buf[]数组中的lengthofthesavedstringcharbuf[];//Arrayofsavedstrings}其中buf[]是实际保存字符串的char类型的数组；free表示buf[]数组中未使用的字节数；len表示buf[]数组中存储的字符串的长度。比如上图，buf[]保存了一个长度为6字节的字符串，free未使用的字节数为0，但是眼尖的同学会发现这明明是7个字符，而且有个“\0”啊？如前所述，SDS并没有完全直接使用C字符串，而是使用了一些C的特性，比如遵循C字符串以空格字符结尾的规则，这样也可以使用C字符串的一些功能。对于SDS，空字符串占用的1个字节不计入len属性，会额外分配空间。在简单了解了SDS的结构之后，我们再来看看SDS相对于C字符串的优势。效率高举个例子：在工作中使用redis时，经常会通过STRLEN命令来获取字符串的长度。在SDS结构中，len属性记录了字符串的长度，所以我们获取一个字符串的长度，直接取len的值。复杂度为O(1)。如果使用C字符串，在获取字符串长度时，需要遍历整个字符串，直到到达空格字符的末尾（C中一个空格字符代表一个完整的字符串），复杂度为这次的度数是O(N)。高并发场景下频繁遍历字符串，获取字符串长度很可能成为redis的性能瓶颈，所以SDS的性能更好。上面提到的数据溢出就是C字符串没有记录自己的长度。相邻的两个字符串的存储方式可能如下图所示，为字符串分配合适的内存空间。如果此时我想把“AAA”改成“AAA123”，之前分配的内存只有6个字节，修改后的字符串需要9个字节才能放下，怎么办？没办法只能占用相邻字符串的空间，自身数据的溢出会导致其他字符串的内容被修改。SDS很好地避免了这种情况。当我们需要修改数据时，首先会检查当前SDS空间len是否满足。如果没有，空间会自动扩展到需要修改的大小，然后进行修改，如下图。不过，有一个特别的地方。将“AAA”的6字节扩展为“AAA123”的9字节后，发现free属性的值变成了扩展字符串的总长度，这就涉及到下面的内存重分配策略。内存重分配策略C字符串的长度是固定的，因此每次增加或缩短字符串时，都必须重新分配内存，而内存重分配算法通常是一个耗时的操作。如果程序不经常修改字符串还是可以接受的。但遗憾的是，作为数据库，redis的数据肯定会被频繁修改。如果每次修改都要重新分配内存，会严重影响性能。SDS通过两种内存重分配策略很好地解决了字符串增长和缩短时的内存分配问题。1.空间预分配空间预分配策略用于优化SDS字符串增长操作。当字符串被修改，需要扩展SDS的空间时，不仅会为SDS分配修改所需要的空间，还会为SDS分配额外的空间。未使用的空间空闲，下次修改时，先检查未使用的空间free是否满足，满足则无需扩容。通过空间预分配策略，redis可以有效减少字符串连续增长操作产生的内存重新分配次数。追加分配未使用空间free的规则：如果修改SDS字符串后len的值小于1M，则追加分配未使用空间free的大小等于len。如果修改SDS字符串后len的值大于等于1M，那么此时额外分配的未使用空间free的大小为1M。2.惰性空间释放惰性空间释放策略用于优化SDS字符串缩短操作。当SDS字符串被缩短时，不会立即进行内存重分配回收多余的空间，而是使用free属性记录这些空间，如果有后续的增长操作，可以直接使用。数据格式多样性C字符串中的字符必须符合某些特定的编码格式，而我们在上面也提到了C字符串以\0空字符结尾来标记字符串的结束，所以字符串不能包含\0，否则会被误认为是多个。由于这个限制，C字符串只能存储文本数据，不能存储音频、视频、图片等二进制格式的数据。Redis会对Buf数组中的数据进行二进制处理，所以对里面存放的数据没有任何限制和过滤，只要存放进去，就取出来。综上所述，以上只是redis数据结构的一点基础知识，难度不大，但是根据我的面试经验，如果被问到这种问题，不要只含糊地说底层是SDS，还要解释为什么要这样执行出来。一方面可以说明你的基本功扎实。如果表达清楚，是很好的bonusitem；主动打消面试官提问的念头，当然怕不按套路走的人！
