关于面试:阿里面试这样问redis-为什么把简单的字符串设计成-SDS

30次阅读

共计 2761 个字符,预计需要花费 7 分钟才能阅读完成。

2021 动工第一天,就有小伙伴私信我,还给我分享了一道他面阿里的 redis 题(这家伙绝比曾经拿到年终奖了),我看了当前感觉挺有意思,题目很简略,是那种典型的似懂非懂,经常容易被大家疏忽的问题。这里整理出来分享一下,顺便本人坚固一下根底,心愿对正在面试和想要面试的兄弟有点帮忙。

题目大抵是这样的

面试官:理解 redisString数据结构底层实现嘛?

铁子:当然晓得,是基于 SDS 实现的

面试官:redis是用 C 语言开发的,那为啥不间接用 C 的字符串,还独自设计 SDS 这样的构造呢?

铁子:·····

其实看得出面试官是想看看,铁子是只停留在 redis 的应用层面,还是对底层数据结构有过更深刻的钻研,面试嘛都爱这样问大家都懂得。

咱们晓得 redis 是用 C 写的,但它却没有齐全间接应用 C 的字符串,而是本人又从新构建了一个叫简略动静字符串SDS(simple dynamic string)的形象类型。

redis也反对应用 C 语言的传统字符串,只不过会用在一些不须要对字符串批改的中央,比方动态的字符输入。

而咱们开发中应用 redis,往往会经常性的批改字符串的值,这个时候就会用SDS 来示意字符串的值了。有一点值得 留神 :在 redis 数据库中,key-value 键值对含有字符串值的,都是由 SDS 来实现的。

比方:在 redis 执行一个最简略的 set 命令,这时 redis 会新建一个键值对。

127.0.0.1:6379> set xiaofu "程序员内点事"

此时键值对的 keyvalue都是一个字符串对象,而对象的底层实现别离是两个保留着字符串 xiaofu程序员内点事 SDS构造。

再比方:我向一个列表中压入数据,redis 又会新建一个键值对。

127.0.0.1:6379> lpush xiaofu "程序员内点事" "程序员小富"

这时候键值对的键和上边一样,还是一个由 SDS 实现的字符串对象,键值对的值是一个蕴含两个字符串对象的列表对象了,而这两个对象的底层也是由 SDS 实现。

SDS 构造

一个 SDS 值的数据结构,次要由 lenfreebuf[] 这三个属性组成。

struct sdshdr{int free; // buf[]数组未应用字节的数量

  int len; // buf[]数组所保留的字符串的长度

  char buf[]; // 保留字符串的数组}

其中 buf[] 为理论保留字符串的 char 类型数组;free示意 buf[]数组未应用字节的数量;len示意 buf[]数组所保留的字符串的长度。

例如上图示意的是 buf[] 保留长度为 6 个字节的字符串,未应用的字节数 free 为 0,然而眼尖的同学会发现这明明是 7 个字符,还有一个 "\0" 啊?

上边提到过 SDS 没有齐全间接应用 C 的字符串,还是沿用了一些 C 个性的,比方遵循 C 的字符串以空格符结尾的规定,这样还能够应用一部分 C 字符串的函数。而对于 SDS 来说,空字符串占用的一字节是不计算在 len 属性里的,会为他调配额定的空间。

简略理解 SDS 构造后,下边咱们来看看 SDS 相比于 C 字符串有哪些长处。

效率高

举个例子:工作中应用 redis,常常会通过STRLEN 命令失去一个字符串的长度,在 SDS 构造中 len 属性记录了字符串的长度,所以咱们获取一个字符串长度间接取 len 的值,复杂度是 O(1)。

而如果用 C 字符串,在获取一个字符串长度时,需对整个字符串进行遍历,直至遍历到空格符完结(C 中遇到空格符代表一个残缺字符串),此时的复杂度是 O(N)。

在高并发场景下频繁遍历字符串,获取字符串的长度很有可能成为 redis 的性能瓶颈,所以 SDS 性能更好一些。

数据溢出

上边提到 C 字符串是不记录本身长度的,相邻的两个字符串存储的形式可能如下图,为字符串调配了适合的内存空间。

如果此时我想把 “程序员内点事” 改成“程序员内点事 123”,可之前调配的内存只有 6 个字节,批改后的字符串须要 9 个字节能力放下啊,怎么搞?

没方法只能 强占 相邻字符串的空间,本身数据溢出导致其余字符串的内容被批改。

而 SDS 很好的躲避了这点,当咱们须要批改数据时,首先会查看以后 SDS 空间 len 是否满足,不满足则主动扩容空间至批改所需的大小,而后再执行批改, 如下图所示。

不过有个非凡的中央 ,在把“程序员内点事” 的 6 个字节扩容到 “程序员内点事 123” 9 个字节后,发现free 属性的值变成了扩容后字符串的总长度,这就波及到下边要说的内存重调配策略了。

内存重调配策略

C 字符串长度是肯定的,所以每次在增长或者缩短字符串时,都要做内存的重调配,而内存重调配算法通常又是一个比拟耗时的操作,如果程序不常常批改字符串还是能够承受的。

但很可怜,redis作为一个数据库,数据必定会被频繁批改,如果每次批改都要执行一次内存重调配,那么就会重大影响性能。

SDS 通过两种内存重调配策略,很好的解决了字符串在增长和缩短时的内存调配问题。

1. 空间预调配

空间预调配策略用于优化 SDS字符串增长 操作,当批改字符串并需对 SDS 的空间进行扩大时,不仅会为 SDS 调配批改所必要的空间,还会为 SDS 调配额定的未应用空间 free,下次再批改就先查看未应用空间free 是否满足,满足则不必在扩大空间。

通过空间预调配策略,redis能够无效的缩小字符串间断增长操作,所产生的内存重调配次数。

额定调配未应用空间 free 的规定:

  • 如果对 SDS 字符串批改后,len 值小于 1M,那么此时额定调配未应用空间 free 的大小与 len 相等。
  • 如果对 SDS 字符串批改后,len 值大于等于 1M,那么此时额定调配未应用空间 free 的大小为1M

2. 惰性空间开释

惰性空间开释策略则用于优化 SDS字符串缩短 操作,当缩短 SDS 字符串后,并不会立刻执行内存重调配来回收多余的空间,而是用 free 属性将这些空间记录下来,如果后续有增长操作,则可间接应用。

数据格式多样性

C 字符串中的字符必须合乎某些特定的编码格局,而且上边咱们也提到,C 字符串以 \0 空字符结尾标识一个字符串完结,所以字符串里边是不能蕴含 \0 的,不然就会被误认是多个。

因为这种限度,使得 C 字符串只能保留文本数据,像音视频、图片等二进制格局的数据是无奈存储的。

redis 会以解决二进制的形式操作 Buf 数组中的数据,所以对存入其中的数据做任何的限度、过滤,只有存进来什么样,取出来还是什么样。

总结

上边只是 redis 数据结构的一点基础知识,没什么难度,但以我的面试教训,如果被问这类问题, 不要只含糊其辞的说出底层是 SDS,有理有据的把为什么这样实现也说进去。

一来能够显得本人基本功扎实,如果表白的在条理清晰,是个很不错的加分项;在一个被动打消面试官问上来的念头,当然就怕不按套路出牌的人!


整顿了几百本各类技术电子书,有须要的同学公号 [ 程序员内点事 ] 内回复 [666 ] 自取。技术群快满了,想进的同学能够加我好友,和大佬们一起吹吹技术。

正文完
 0