Redis八股文精讲：字符串

Redis八股文精讲：字符串

写在前面

小牛之前出了八股文背诵版系列，不少朋友问我，能不能搞个八股文精讲，把面试问题讲讲透，于是系列就这样诞生了。咱们第一期先聊聊Redis。

字符串

Redis底层是C语言实现的。于是不少朋友想当然的以为，Redis的字符串和C语言字符串实现方式一致。

但事实上，Redis自己定义了一套字符串的实现，名曰SDS(simple dynamic string)。

不少同学在面试时，面试官轻描淡学来一句，来讲一讲Redis的SDS吧。大家一脸懵逼，半天答不上来。最后搞半天，其实面试官就是问的Redis字符串呀。

首先回答一个问题：为什么Redis不采用C语言的字符串直接做具体实现?

这当然是因为这种数据结构有固有缺陷啦。主要有如下几个

缺点1：O(n)复杂度获取长度

我们知道，C语言如何判断一个字符串已经结束，当然是通过标志位'\0'。

C语言Str

所以，对于我们想获得字符串长度，我们需要从头开始遍历，直至遍历到\0，时间复杂度变成了O(n)。

缺点2：没有较好的扩容机制

对于C语言，想要搞个字符串数组，肯定需要预先确定好字符串长度。如果这个字符串经常需要修改，修改前后长度一致还好说，如果不一致，那程序层面就需要重新申请一段新内存，并把字符一个个拷贝到新的地方。

缺点3：特殊字符无法处理

引用《Redis源码剖析与实战》的例子 如果我们想存储字符串"redis\0"

char *a = "redis\0";

到原始C语言，它编译器看到\0，以为还是字符结束的标志呢，如果把它打印下来，它只打出redis。所以特别是对于二进制数据，这种奇奇怪怪的case特别多，因此C语言的字符数组就处理不了这块存储二进制字符的需求了。

为了解决C语言字符数组的不足，redis提出了新的方法。我们先来看看3.0及之前版本的实现。

struct sdshdr {     unsigned int len;     unsigned int free;     char buf[]; }

来解释一下这些字段吧。

len：数组字符串已使用长度

free: 数组未使用的字符串长度

buf：存储字符串

在之后的版本，Redis对SDS进行了改进，但大体思想不变

struct sdshdr {     unsigned int len;     unsigned int alloc;     unsigned char flags;     char buf[]; }

来解释一下这些字段吧。

len：数组字符串已使用长度

alloc: 数组分配的长度

flags: 表示SDS类型

buf：存储字符串

对于SDS类型，我也稍微多啰嗦两句。在新版本redis中，有4种SDS类型(sdshrd5 never used)。其中 sdshrd8 sdshrd16 sdshrd32 sdshrd64 的区别仅仅就在len和alloc上有所区别。

对于sdshrd8 该定义为

struct sdshdr8 {     uint8_t len;     uint8_t alloc;     unsigned char flags;     char buf[]; }

以此类推，sdshrd16就是

struct sdshdr16 {     uint16_t len;     uint16_t alloc;     unsigned char flags;     char buf[]; }

那为啥新版Redis搞这么多结构体?一个结构体不是一法通万法就够了嘛。

当然，事实确实如此，按实现角度看。如果只采用sdshrd64，肯定也够了。

但按抠门角度看呢?如果我们机子很菜，内存很小，想抠抠索索能省一点，是一点，这样做就有好处辣。

好处在哪里?当然是uint8_t、uint16_t、uint32_t、uint64_t占的空间不一样，对于小字符串，用小头sdshdr8，这样len 和alloc占用字段也能省一点，就是这么回事。

所以可以看到，SDS本质上是C语言的字符数组，加上了一点别的标识属性的结构体而已。小伙伴们下次碰见面试官问SDS，就不用慌啦!

最后多啰嗦两句SDS扩容：

对于字符串增加了，如果原始的剩余空间足够，直接返回如果空间不足够，重新申请两倍最小需要长度的空间，再进行挨个赋值。

最后总结一下：Redis提出动态字符串这一数据结构，改进了C语言字符数组的不足。该动态字符串有如下好处：

字符串长度获取时间复杂度从O(n)->O(1)减少字符串扩容引起的数据搬运次数。可以存储更加复杂的二进制数据

参考

《Redis源码剖析与实战》

《Redis的设计与实现》

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。