Redis 面试都卷到 C 去了。有个小伙伴在前两天找松哥模面的时候如是说到。

是啊,没办法,自从 Java 八股文这个概念被提出来并且逐步在 Java 程序员中强化之后,现在各种各样的八股文手册,有免费的有付费的,琳琅满目。

单纯的八股文已经区分不出 Java 猿水平的高低了,所以现在面试总会卷出新高度。

这次是小伙伴面试时候被问到一个 SDS 的问题,也就是 Redis 中 String 字符串的底层实现原理。

我来和小伙伴们简单聊一聊这个话题。

一 String 类型

Redis 中有一个 String 类型,使用频率还比较高,我们日常做缓存、分布式锁都会用到。

很多小伙伴也都知道 Redis 是用 C 写的,那么就有一个问题,Redis 中的 String,底层数据结构是什么样的?

是不是就是 C 中的 String 呢?

二 C 中的 String

玩过 C 的小伙伴应该知道,C 语言本身并没有内置的 String 类型,但是 C 语言中可以使用字符数组(char array[])或指向字符的指针(char *pointer)来表示字符串。在 C 语言中,字符串是以空字符 '\0' 结尾的字符序列。例如:

char *str1 = "Hello, World!";

在这个例子中,str1 是一个指向字符串字面量 “Hello, World!” 的指针。

当我们在 Redis 中使用 String 的时候,很多小伙伴可能会想这个 String 可能就是 C 中的 String 吧?并不是!

为什么不直接使用 C 中的 String 呢?主要有以下几种考虑:

  1. char* 这种方式无法直接获取到字符串的长度,只能逐个字符去遍历,很明显效率低。
  2. C 中的字符串使用 \0 去表示字符串结束,这就导致我们没法在字符串中存储二进制数据,因为二进制中的数据可能会和 \0 冲突。
  3. C 中字符串在创建的时候长度和内存大小就都确定下来了,后期如果缩容和扩容都是创建新数组然后拷贝内容,操作方式过于麻烦。

有鉴于此,Redis 自己搞了个 SDS,全称是 Simple Dynamic String。这个 SDS 和 C 中的字符串的关系,有点像我们 Java 中 List 和数组的关系,有点

三 SDS

为了解决上述问题,小伙伴们可以先想想,我们都需要哪些东西呢?

  • 首先得有一个存储字符的 char 数组吧。
  • 数组的总长度得有一个变量记录下来吧。
  • 数组已经使用的长度得记录下来吧。

这是三个最基本的属性。

3.1 SDS 类型

当然在具体实践中还有一个 flags 属性,这个属性用来表示 SDS 的类型,因为 Redis 设计了几种不同的 SDS 类型,这样的设计主要是为了节省内存。

从这里可以看到,一共有五种不同的 SDS 类型,分别是:

  1. sdshdr5
  2. sdshdr8
  3. sdshdr16
  4. sdshdr32
  5. sdshdr64

从注释中可以看到,sdshdr5 其实没有使用,另外四个的区别主要在于数组长度和分配空间长度的差异。

以 sdshdr16 为例,uint16_t 表示 16 位无符号 int 值,能表示的最大值是 2^16-1,所以它的 buf 数组的最大长度就是 2^16。

按照这样的设计,其实 Redis 的字符串能够存储超大的字符串,例如,sdshdr32 类型意味着能够存储的字符长度是 2^32,一个字符占一个字节,就是 4GB。

可是实际上 Redis 的字符串存不了这么长的,Redis 内部会对字符串的长度进行限制,最大是 512MB。

当然实际生产中我们不建议这么搞,一般字符串最好不要超过 1MB。

3.2 编码格式

为了提升效率,SDS 中使用的编码格式也会根据情况来定。

  • 如果是数字类型,且数字长度小于 20,就会使用 int 编码。

  • 长度小于等于 44 字节的字符串,使用 embstr 编码。
  • 长度大于 44 字节的字符串使用 raw 编码。

3.3 其他特点

不同于 C 中的字符串,SDS 可以存储二进制数据,因为 SDS 不再通过 \0 去判断字符串结束,因为有一个 len 变量存储了字符串的长度。

同时,SDS 在字符串扩容的时候也会进行预分配,这些机制类似于咱们 Java 中 ArrayList 扩容、HashMap 扩容,扩容时会预留空间,避免频繁扩容。

同时,缩容的时候并不会立马释放多余空间,防止后续又要扩容。

四 小结

大致就这些东西,其实也不难。

松哥最近也录了一个 Redis 视频课,基于目前最新版的 Redis 来讲解,从用法到原理到经典面试题都有涉及,感兴趣的小伙伴可以看下。

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部