面试题解-Redis的String是如何实现的？

第44题: Redis 的String 是怎么实现的？为什么不直接用c的字符串？

Redis 没有直接使用C 语言的字符串表示，而是自己构建一种简单动态字符串（SDS: simple dynamic string）。

Redis 中的String 都是SDS，例如我们执行这样一条命令:

redis> SET blog angela

那么Redis 在内存中创建了一个键值对，

• 键：键是一个字符串对象，对应底层实现是一个保存字符串“blog” 的SDS;
• 值：值也是一个字符串对象，对应底层实现是一个保存字符串是“angela”的SDS。

如果执行

redis> RPUSH blog "angela" "de" "blog"

那么Redis 将在内存中创建一个键值对，键还是一个SDS，存放“blog”，值是一个列表，存放三个SDS，“angela”、“de”、“blog”

SDS如何实现的呢？

首先SDS被定义为这样一个结构体:

struct sdshdr {
   char buf[];//字节数组,用于保存字符串
   int len;//记录buf数组中已使用字节的数量
   int free;//记录buf数组中未使用字节的数量
}

举个例子:

现有执行redis> SET blog angela 命令后，value值在redis 中存放如下图所示，buf存放字节数组(真实数据)，len表示存放字符串的长度（不包括结束符号'\0'）,free表示剩余空间，可以看到还剩5个字节。

SDS遵循了C语言字符串以空字符结尾的惯例，保存空字符的1个字节空间不在SDS 的len属性里面。这样做有个好处是我们直接可以复用C 提供的库函数，比如打印字符串，直接用C 提供的printf("%s", s->buf);

那又是为什么不直接用C语言提供的字符串呢？

在C语言中，表示一个“angela” 的字符串如下图所示，结束也是通过空字符表示：

C语言的字符串和SDS的区别如下：

• 长度获取效率：C语言如果需要获取字符串长度，需要从头开始遍历，时间复杂度O(n)，SDS提供len属性，访问时间复杂度O(1), Redis的strlen 获取字符串长度函数性能毫无压力；

• 杜绝溢出：C字符串不记录自身长度的另一个问题是容易造成缓冲区溢出，比如要做字符串拼接，char *strcat(char *dest, const char *src), 讲src 字符串拼到desc字符串，如果desc忘记提前扩容，就会溢出，而恰好desc后面正好有数据，则会被覆盖；

• 减少内存重分配：对于Redis这种内存数据库，很多场景会频繁更新value的值，那如果采用C字符串，value长度有变化，就需要频繁分配内存，SDS做了内存的预分配和惰性释放，能有效减少内存分配次数，内存的重分配代价还是很高昂的，对于Redis这种对性能要求非常高的缓存产品，这种性能损耗是不能接受的；

• 二进制安全：C字符串必须符合某种编码（比如ASCII），除了空字符结尾，字符串中间是不能包含空字符的，否则会被误以为是字符串结尾。这就限定了C字符串不能用来存储类型图片、音频、视频、压缩文件这种二进制书数据，但是SDS可以，SDS设计的API都是二进制安全的。

-End-

最近有一些小伙伴，让我帮忙找一些 面试题 资料，于是我翻遍了收藏的 5T 资料后，汇总整理出来，可以说是程序员面试必备！所有资料都整理到网盘了，欢迎下载！