2021动工第一天，就有小伙伴私信我，还给我分享了一道他面阿里的redis题（这家伙绝比曾经拿到年终奖了），我看了当前感觉挺有意思，题目很简略，是那种典型的似懂非懂，经常容易被大家疏忽的问题。这里整理出来分享一下，顺便本人坚固一下根底，心愿对正在面试和想要面试的兄弟有点帮忙。

题目大抵是这样的

面试官：理解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 "程序员内点事"

此时键值对的key和value都是一个字符串对象，而对象的底层实现别离是两个保留着字符串xiaofu和程序员内点事的SDS构造。

再比方：我向一个列表中压入数据，redis 又会新建一个键值对。

127.0.0.1:6379> lpush xiaofu "程序员内点事" "程序员小富"

这时候键值对的键和上边一样，还是一个由SDS实现的字符串对象，键值对的值是一个蕴含两个字符串对象的列表对象了，而这两个对象的底层也是由SDS实现。

SDS构造

一个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属性里的，会为他调配额定的空间。

简略理解SDS构造后，下边咱们来看看SDS相比于C字符串有哪些长处。

效率高

举个例子：工作中应用redis，常常会通过STRLEN命令失去一个字符串的长度，在SDS构造中len属性记录了字符串的长度，所以咱们获取一个字符串长度间接取len的值，复杂度是O(1)。

而如果用C字符串，在获取一个字符串长度时，需对整个字符串进行遍历，直至遍历到空格符完结（C中遇到空格符代表一个残缺字符串），此时的复杂度是O(N)。

在高并发场景下频繁遍历字符串，获取字符串的长度很有可能成为redis的性能瓶颈，所以SDS性能更好一些。

数据溢出

上边提到C字符串是不记录本身长度的，相邻的两个字符串存储的形式可能如下图，为字符串调配了适合的内存空间。

如果此时我想把“程序员内点事”改成“程序员内点事123”，可之前调配的内存只有6个字节，批改后的字符串须要9个字节能力放下啊，怎么搞？

没方法只能强占相邻字符串的空间，本身数据溢出导致其余字符串的内容被批改。

而SDS很好的躲避了这点，当咱们须要批改数据时，首先会查看以后SDS空间len是否满足，不满足则主动扩容空间至批改所需的大小，而后再执行批改,如下图所示。

不过有个非凡的中央，在把“程序员内点事”的6个字节扩容到“程序员内点事123”9个字节后，发现free属性的值变成了扩容后字符串的总长度，这就波及到下边要说的内存重调配策略了。

内存重调配策略

C字符串长度是肯定的，所以每次在增长或者缩短字符串时，都要做内存的重调配，而内存重调配算法通常又是一个比拟耗时的操作，如果程序不常常批改字符串还是能够承受的。

但很可怜，redis作为一个数据库，数据必定会被频繁批改，如果每次批改都要执行一次内存重调配，那么就会重大影响性能。

SDS通过两种内存重调配策略，很好的解决了字符串在增长和缩短时的内存调配问题。

1.空间预调配

空间预调配策略用于优化SDS字符串增长操作，当批改字符串并需对SDS的空间进行扩大时，不仅会为SDS调配批改所必要的空间，还会为SDS调配额定的未应用空间free，下次再批改就先查看未应用空间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，有理有据的把为什么这样实现也说进去。

一来能够显得本人基本功扎实，如果表白的在条理清晰，是个很不错的加分项；在一个被动打消面试官问上来的念头，当然就怕不按套路出牌的人！

整顿了几百本各类技术电子书，有须要的同学公号[ 程序员内点事 ]内回复[ 666 ]自取。技术群快满了，想进的同学能够加我好友，和大佬们一起吹吹技术。