Redis数据结构详解（1）-redis中的字符串（SDS） redisjava面试后端

前提知识
我们先从百科上摘下Redis的解释：
Redis是一个使用 ANSI C 编写的开源、支持网络、基于内存、分布式、可选持久性的键值对存储数据库。
（不用过多在意ANSI，它只是一个标准，你可以理解为早期民间版本很多，后来统一了标准，大学课程里包括现在在用的都是标准化后的C语言版本）
没错！Redis的底层是由 C语言实现的！大学不管是什么专业应该都有这个课，但是不管大家还有没有它的记忆，都不影响我们接下来的学习哈哈哈~

文章图片

redis第一步，字符串是基础
回想当初学习Java，第一个学习的数据类型应该是基本类型，但redis里最基础的结构其实是字符串，几乎哪里都有它。在mysql定义字段类型时，个别老哥会很中意varchar这个类型，因为万物皆可varchar（不讨论性能的情况下），其实redis就有点这个意思，很多结构的基础都是字符串。
上面提到Redis的底层是由C语言实现的，那岂不是直接拿C语言的字符串（以空字符结尾的字符数组，以下简称C字符串）来用就行？
我先回答了：不行，因为C语言作为早期的编程语言，C字符串是有些“不足”或者说是需要补充的，尤其是像redis这样对速度要求严苛，字符串可能会被频繁修改的服务，于是redis在C字符串的基础上，自己构造了名为简单动态字符串（simple dynamic string，SDS）的抽象类型，用作redis自己的默认字符串。
(redis也不是就不用C字符串了，只会运用在一些无需对字符串值做修改的地方，例如打印日志时)

C字符串简单介绍，嗯，简单。

文章图片

首先上图就是一个值为"yikun"的C字符串。
不了解的小伙伴可能不知道为什么后面多了个'\0'，其实这个字符是空字符，也可以理解为C语言的“字符串终止符”。
长度为N的字符串，会用长度为N+1的字符数组来表示，最后多出来的1长度就是专门用来存储空符'\0'的。
然后没了。
C语言的字符串就是这么简单。

文章图片

不急，我们继续往后说~

那么C字符串有哪些“不足”呢？
俗话说得好：知己知彼，百战百胜。
我们得知道C语言的“不足”，才能知道redis为了弥补这种情况，在SDS中做了什么措施。
1.C字符串并没有记录自身长度。
2.会根据空字符'\0'来判断字符串是否结束。
3.只能根据空字符'\0'来判断字符串是否结束。
2和3好像差不多，但意思其实是有细微差别的。
（果然中华文化博大精深~）

C字符串因为上面的“不足”会引起什么问题?

1.获取字符串长度复杂度高因为不足1 和不足3，所以C字符串只能通过遍历字符来获取长度。

文章图片

我们这里用Java的for循环（只是用Java举例，实际是C语言实现的）简单说明下C语言如何获取字符串长度。
可见字符串越长，这个操作就越耗时，复杂度为O(N)。

2.缓冲区溢出和内存泄露因为不足2，C字符串可能会在修改字符串时出现问题，因为大家知道内存是连续的，假如我要在字符串后面拼接新的内容，我首先要通过内存重分配来扩展底层数组的空间大小。

文章图片

比如我要在字符串'yikun'后拼接'lucky'，但现在后面紧挨存储的是'happy'字符串，所以我首先要扩展数组才能拼接'lucky'，不然就把'happy'给覆盖掉，造成缓存区溢出了。
那如果我要缩短'yikun'，改成'yi'，倒是不用扩展数组。

文章图片

但我空的这部分又造成内存泄漏，所以还是需要进行内存重分配。
而内存重分配是个十分耗时的操作，如果上面的字符串修改频繁发生的话，对于性能的影响就会很大。

3.没办法存储二进制数据因为不足3，假如我们的数据本身就包含空字符串'\0'，而代码逻辑是铁面无私的，会认为是字符串终止的意思；而像图片、音频、视频、压缩文件这样的二进制数据是会包含空字符串'\0'的，所以可想而知，数据会出现问题，可能只能识别到前面的部分数据，而丢失后面的内容。

文章图片

所以针对上面的问题，redis的SDS的结构是怎么设计的？
废话不多说，我们直接来看下SDS的结构：

文章图片

直观来看，SDS多维护了 free 属性和 len 属性。
len 属性用来记录buf数组中已使用字节的数量，同时也等于SDS所保存字符串的长度。

文章图片

而属性 free 是用来记录buf数组中未使用字节的数量。

SDS是如何依靠引入两个属性值len、free来解决具体问题呢？

1.获取字符串长度现在可以直接访问 len 属性来获取字符串长度，就好比Java属性的get方法，复杂度由原来的O(N)一下子降到了O(1)。
而且这个属性是SDS在执行操作时自动完成的，我们无需进行任何维护。

2.空间预分配和惰性空间释放上面我们说内存重分配操作耗时，所以在需要对SDS进行空间扩展的时候，会分配额外的未使用空间。
下面是额外分配空间数量的公式：
1.如果SDS修改之后，SDS的长度(len属性的值)小于1MB，那么就会分配和len属性同样大的未使用空间，也就是free属性会和len属性相同，相当于将原数组长度double。
2.如果SDS修改之后，SDS的长度(len属性的值)大于或等于1MB，那么就会分配固定的1MB未使用空间。

文章图片

而free属性就决定了是不是需要进行额外的内存重分配操作，假如free为7，而你需要拼接的字符串长度只有5，那就不需要进行内存重分配操作，直接存储就可以。
free：太好了，我这空座就是给老弟你留的，快坐快坐~

文章图片

所以针对拼接操作来说，本来N次一定需要N次的内存重分配操作，现在最多只需要N次。
（比如你第一次拼接后，free就大于后续要拼接的字符串长度之和了，那其实就只有1次内存重分配操作，所以说最多N次）
缩短操作也是同理，删掉N个字符后，我free就增加N，我先不做内存重分配操作，就先给你留着呗，万一你后面又做拼接是不是。

文章图片

所以总结：拼接时我们做空间预分配，缩短时我们做惰性空间释放，都是为了减少内存重分配操作。
（SDS其实也提供了响应的方法，在有需要时，可以真正地释放SDS的未使用空间，所以不用担心未使用空间会造成内存浪费。）

3.存储二进制数据 C字符串不能存储二进制数据的原因是只能根据'\0'来判断数据是否结束，不能保证其完整性，但因为SDS的 len 属性，无论你数据里有多少'\0'都没关系，我是根据 len 属性值来判断数据长度的，必定是完整的，所以SDS可以安全地存储二进制数据。

SDS你都有len了，那为啥还要跟C字符串一样在字符串后面加'\0'？
这个很好回答，因为SDS保持和C字符串一样的特性，就不用专门编写多余的函数了，在一定的情况下可以直接用C语言的函数，避免了不必要的重写。

最后的总结
C字符串和SDS之间的区别：

C字符串	SDS
获取字符串长度复杂度为O(N)	获取字符串长度复杂度为O(1)
修改字符串时需要执行N次内存重分配	修改字符串时最多需要执行N次内存重分配
不能保存二进制数据	可以保存二进制数据
可以使用C字符串函数库的所有函数	可以使用C字符串函数库的一部分函数

写在最后的最后
我是苏易困，大家也可以叫我易困，一名Java开发界的小学生，文章可能不是很优质，但一定会很用心。
呜呜呜~ 真是边整理便有收获，自己学习的动力也增长了起来，还真是那句话：你自己明白，才能跟其他人说明白（也不知道是不是说明白了），而且写的时候也会考虑一些取舍，比如有的东西需不需要标注？有的地方是不是过于啰嗦了？是不是写的太入门了一点？可能这些知识在一些人看来都是很基础很入门甚至不用讲的东西。
但怎么说呢，我的初心其实也就是整理和梳理自己的知识，如果能帮到你，我会很开心；如果你觉得不够水平，我也会虚心接受；人嘛，总要有个学习的过程，我也会一直努力的~ 大家一起加油~
【Redis数据结构详解（1）-redis中的字符串（SDS）】