2021年第一天，有个小伙伴给我发了私信，给我参考了阿里的另一个redis问题(这家伙肯定比已经拿了年终奖的强)。看完之后觉得挺有意思的。题目很简单，是一个典型的看似无法理解，又经常被大家忽略的问题。 这里整理一下供参考，自己巩固基础。希望对正在面试和想面试的兄弟们有帮助。 题目大致是这样的:你了解redis的字符串数据结构的底层实现吗？铁:当然是基于SDS。面试官:redis是用C语言开发的，为什么不直接用C的字符串，像SDS一样单独设计结构呢？铁子:图片“其实我看得出面试官是想看看铁子是仅仅停留在redis的使用层面，还是对底层数据结构做了更深层次的研究。面试的时候大家都知道这个问题。 我们知道redis是用C写的，但是它没有直接使用C字符串，而是重构了一个通用类型，叫做简单动态字符串SDS(simple dynamic string)。 Redis也支持C语言中的传统字符串，但是会用在少数不需要修改字符串的地方，比如静态字符输出。 我们在开发中使用redis时，经常会频繁修改字符串的值，然后会用SDS来表示字符串的值。 值得注意的是，在redis数据库中，包含字符串值的键值对都是由SDS实现的。 比如在redis中执行最简单的set命令，然后redis会创建一个新的键值对。 127.0.0.1:6379 >此时设置符晓“程序员内部事务”，键-值对的键和值都是一个字符串对象，对象的底层实现是分别存放字符串符晓和程序员内部事务的两个SDS结构。 例如，如果我将数据推入一个列表，redis将创建一个新的键-值对。 127.0.0.1:6379 >Lpush符晓《程序员的工作》《程序员符晓》此时的key-value对的key同上，是SDS实现的string对象。key-value对的值是一个包含两个string对象的list对象，这两个对象的底层也是由SDS实现的。 SDS structure SDS值的一种数据结构，主要由len、free和buf[]组成 struct sdshdr { int free//buf[]数组int len未使用的字节数；//存储在buf []数组中的字符串的长度char buf[]；//保存的字符串数组}其中buf[]是实际保存字符串的char类型数组；指示freebuf []数组中未使用的字节数；指示存储在lenbuf []数组中的字符串的长度。 比如上图显示buf[]保存了一个长度为6字节的字符串，未使用的字节数free为0，但是眼尖的同学会发现这明明是7个字符，还有一个“\0”？如上所述，SDS并没有直接使用C字符串，而是仍然使用了少量的C特性，比如遵循C字符串以空格结尾的规则，这样就可以使用C字符串的一些功能。 对于SDS，空字符串占用的一个字节不计入len属性，会为其分配额外的空间。 了解了SDS的简单结构之后，我们再来看看SDS相对于C字符串的优势。 高效例子:在工作中使用redis时，我们经常通过STRlen命令得到一个字符串的长度。在SDS结构中，len属性记录了字符串的长度，所以我们直接得到LEN的值，复杂度为O(1) 但如果图片使用C字符串，在获取一个字符串的长度时，需要遍历整个字符串，直到遍历结束(C中的空格字符代表一个完整的字符串)。此时，复杂度为O(N) 在高并发场景下，频繁遍历字符串，获取字符串的长度很可能成为redis的性能瓶颈，所以SDS具有更好的性能。 上面提到的数据溢出中的C字符串不记录自己的长度，可能会存储两个相邻的字符串，如下图所示，并为字符串分配适当的内存空间。 图片如果此时我想把“程序员的工作”改成“程序员的工作123”，之前分配的内存只有6个字节，修改后的字符串需要9个字节才能放下。怎么会？图像只能占用相邻字符串的空间，自身数据溢出导致其他字符串的内容被修改。 SDS很好地规避了这一点。当我们需要修改数据时，会先检查当前的SDS space len是否能满足要求，如果不能，会自动将空间扩展到需要的大小进行修改，然后进行修改，如下图所示。 但是，图中有一个特别的地方。将“程序员内务”的6个字节扩展为“程序员内务123”的9个字节后，发现free属性的值变成了扩展字符串的总长度，这就涉及到下面要介绍的内存再分配策略。 内存再分配策略C字符串长度是一定的，所以每次增加或缩短字符串都需要进行内存再分配，而内存再分配算法通常是一个比较耗时的操作，如果程序不经常修改字符串的话是可以接受的。 遗憾的是，redis作为一个数据库，数据会被频繁修改，如果每次修改都进行内存重新分配，性能会受到严重影响。 通过SDS的两种内存再分配策略，很好地处理了字符串增长和缩短时的内存分配问题。 1.空间预分配空间预分配策略用于优化SDS字符串增长操作。当字符串被修改并且SDS的空间需要被扩展时，不仅修改所需的空间将被分配给SDS，而且额外的未使用的空闲空间也将被分配给SDS。接下来的修改会先检查未使用的空间free是否可以满足，如果满足，则不会用来扩展空间。 通过空间预分配的策略，redis可以有效减少字符串持续增长导致的内存重分配次数。 为图片额外分配未使用空间free的规则:如果修改SDS字符串后len的值小于1M，则额外分配的未使用空间free的大小等于len的大小。 如果修改SDS字符串后len的值大于或等于1M，则额外分配的未用空闲空间的大小为1M。 2.空闲空间释放。空闲空间释放策略用于优化SDS字符串缩短操作。当SDS字符串被缩短时，不会立即执行内存重新分配来回收多余的空间，而是使用free属性来记录空间，如果有后续的增长操作，可以直接使用。 数据格式的多样性C字符串中的字符必须符合一些特定的编码格式，而我们上面提到过，C字符串以\0空字符结尾来标识一个字符串的结尾，所以字符串不能包含\0，否则会被误认为是多个字符。 由于这个限制，C字符串只能存储文本数据，而不能存储音频、视频、图片等二进制格式的数据。 Redis会对Buf数组中的数据进行二进制的操作，所以对存储在其中的数据没有任何限制和过滤，只有存储在其中的和取出的。 总结以上只是redis数据结构的一点基础知识，不难。但是以我的面试经验，如果被问到这种问题，不要只是含糊的说底层是SDS，要说出为什么是这样实现的。 第一，你可以看起来基本功扎实。如果你表达清楚了，就是一个非常好的加分。在一次主动打消面试官问的念头，当然是怕不按套路出牌的人！