【Redis 面试题】Redis 的字符串是怎么实现的？
Redis 字符串的实现
Redis 虽然是用 C 语言写的，但却没有直接用 C 语言的字符串，而是自己实现了一套字符串。目的就是为了提升速度，提升性能，可以看出 Redis 为了高性能也是煞费苦心。
Redis 构建了一个叫做简单动态字符串（Simple Dynamic String），简称 SDS
1.SDS 代码结构
struct sdshdr{
// 记录已使用长度
int len;
// 记录空闲未使用的长度
int free;
// 字符数组
char[] buf;
};
SDS ？什么鬼？可能对此陌生的朋友对这个名称有疑惑。只是个名次 2 而已不必在意，我们要重点欣赏借鉴 Redis 的设计思路。 下面画个图来说明，一目了然。
image.png
Redis 的字符串也会遵守 C 语言的字符串的实现规则，即最后一个字符为空字符。然而这个空字符不会被计算在 len 里头。
2.SDS 动态扩展特点
SDS 的最厉害最奇妙之处在于它的 Dynamic。动态变化长度。举个例子
image.png
如上图所示刚开始 s1 只有 5 个空闲位子，后面需要追加' world' 6 个字符，很明显是不够的。那咋办？Redis 会做一下三个操作：
1.计算出大小是否足够
2.开辟空间至满足所需大小
3.开辟与已使用大小 len 相同长度的空闲 free 空间（如果 len < 1M）开辟 1M 长度的空闲 free 空间（如果 len >= 1M）
看到这儿为止有没有朋友觉得这个实现跟 Java 的列表 List 实现有点类似呢？看完后面的会觉得更像了。
Redis 字符串的性能优势
快速获取字符串长度
避免缓冲区溢出
降低空间分配次数提升内存使用效率
1.快速获取字符串长度
在看下上面的 SDS 结构体：
struct sdshdr{
// 记录已使用长度
int len;
// 记录空闲未使用的长度
int free;
// 字符数组
char[] buf;
};
由于在 SDS 里存了已使用字符长度 len，所以当想获取字符串长度时直接返回 len 即可，时间复杂度为 O(1)。如果使用 C 语言的字符串的话它的字符串长度获取函数时间复杂度为 O(n),n 为字符个数，因为他是从头到尾（到空字符'\0'）遍历相加。
2.避免缓冲区溢出
对一个 C 语言字符串进行 strcat 追加字符串的时候需要提前开辟需要的空间，如果不开辟空间的话可能会造成缓冲区溢出，而影响程序其他代码。如下图，有一个字符串 s1="hello" 和 字符串 s2="baby",现在要执行 s
trcat(s1,"world"),并且执行前未给 s1 开辟空间，所以造成了缓冲区溢出。
image.png
而对于 Redis 而言由于每次追加字符串时都会检查空间是否够用，所以不会存在缓冲区溢出问题。每次追加操作前都会做如下操作：
1.计算出大小是否足够
2.开辟空间至满足所需大小
3.降低空间分配次数提升内存使用效率
字符串的追加操作会涉及到内存分配问题，然而内存分配问题会牵扯内存划分算法以及系统调用所以如果频繁发生的话影响性能，所以对于性能至上的 Redis 来说这是万万不能忍受的。所以采取了一下两种优化措施
评论