Redis 设计与实现之动态字符串

Q: 什么是 SDS

A:

SDS 是 Redis 在实现过程中使用的一种「动态字符串」。由于 Redis 的代码基本都是通过 C 语言来实现的,所以 SDS 在最底层还是依赖于char buf[]来存储数据。SDS 对象的数据结构大致如下图所示

可以看出,SDS 结构体成员中有三个属性:len,free,buf。其中 len 标识一个 SDS 对象管理的字符串有效字符是多少个,而 free 则代表这个 SDS 在不扩充空间的前提下还可以存储多少个有效字符,buf 则是一个char[]类型的指针,它指向一段连续的内存空间,这里才是真正存储字符串的地方(有效字符串是指除\0以外的字符串集合)。

Q: 有了 C 字符串,为什么还需要 SDS?

A:

通过阅读相关数据以及对 Redis 文档的查阅,可以总结出以下几点使用 SDS 而不适用原生 C 字符串的好处

1
2
3
4
5
    * 更高效的获取一个 SDS 对象内保存的字符串的长度
    * 杜绝缓冲区溢出
    * 减少因字符串的修改导致的频繁分配和回收内存空间操作
    * 二进制安全
    * 和 C 语言有关字符串的库函数有一个更高的兼容性

其实看到这里,如果你之前使用其他语言中的「普通数组」实现过一个「动态数组」的话,那么除了「二进制安全」这一条好处可能不太理解之外,其余的应该都比较熟悉。下面我们就来分别说一下这几个好处。

Q: 如何更高效的获取字符串的长度?

A:

这个问题在传统的 C 字符串中算是一个痛点。在一个线性的数据结构中,我们都只能通过遍历这个数据结构中所有的有效元素才能够获取它准确的长度,这个操作的时间复杂度是 O(N) 级别。但是当我们只是把 C 字符串作为 SDS 这个数据结构中的一个成员时,我们就可以通过增加另外一个成员len来实时的计算字符串的准确长度。计算的方式也很简单,就是在字符串做「新增元素」的操作时对len+1,做「减少元素」的操作时对len-1。这样一来,就可以通过访问len来获取 SDS 内存储的字符串的长度。类似于这样的实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void add(char a){
	buf[len++] = a;
}

void sub(char a){
	len--;
}

int length(char a){
	return len;
}

Q: 如何杜绝缓冲区溢出?

A:

缓冲区溢出换成另外一种更加直白的说法:篡改了内存中本不属于你的空间中的数据。这种现象在字符串拼接以及字符串的新增字符的操作中比较常见。处理这种问题的办法也很简单:在内存容量允许的情况下,当一个字符串需要更多的内存空间的时候,重新分配1块「更大」的连续空间,将原来空间中的有效数据 copy 过去。其中,检测是否超出剩余空间,完全可以使用free属性的值,因为它代表了数组中现在还有多少可用的空间。 如果你认真的阅读了上一段的内容,就可以发现,在防止缓冲区溢出的过程中有几个「丑陋」的步骤:

  1. 可能多次在内存中分配一段连续的空间
  2. 可能多次将原来空间中的有效数据 copy 到新的空间中
  3. 分配出去的空间如果没有回收,一直在持续分配,可能会出现内存泄漏

针对于新出现的问题,我们采取了以下办法来解决:

  1. 按照一定的策略分配新的内存空间,尽量减少分配次数
  2. 当空闲空间达到一定阈值的时候,回收多余的内存空间

在 Redis 中,通过两个步骤来确定「预分配」空间的大小:

  1. 如果修改之后的字符串长度(len)小于1MB,除了分配必要的空间之外,还需要分配大小等同于len的空闲空间。例如,修改之后的字符串长度为10(len=10),那么在修改之后,新的内存空间大小为=10+10+1=21。
  2. 如果修改之后的字符串长度(len) 大于1MB,除了分配必要的空间之外,还需要分配大小等同于1MB的空闲空间。

在 SDS 相关的修改操作中,会先对可用空间和实际所需要的空间进行对比,若超出,则会分配新的空间,否则使用旧的空间。通过上面的策略,基本上可以把「重新分配内存空间」和「将原来空间中的有效数据 copy 到新的空间中 」的次数由每次必定发生,降低到最多发生 N 次(N 为修改操作进行的次数)。

这里插入一个笔者小的心得:很多程序员在解决问题的时候都倾向于找到一个完美的解决方案,若是笔者的话,可能在看到这个问题的时候也会想,能否有一个完美的办法来解决上面的问题。但是,我们可以看到,在 Redis 这种工业级的项目中,它采取的方案仍然是很普通的,甚至是我们平时做练习就会用到的「实现」。一个看似「延迟让风险发生」的办法,有的时候就是最「完美」的办法。程序员更多的应该关注如何解决问题,而不是如何「完美」的解决问题。

除了通过分配「预留空间」的方式来减少「分配」操作的次数之外,我们还担心的一点就是,如果一直无限制的进行分配,那么内存终有耗尽的时候。这就是我们常说的内存泄漏问题。想解决它也很简单,就是按照一定的策略回收已经分配的内存空间。比如:当一个 SDS 绑定的内存空间的使用量已经低于25%,那么我们就将它的内存空间缩小为原来的一半。至于为什么只缩小原来的一般而不是全部将空余空间回收,仔细思考一下就知道,如果回收的方式过于极端,那么就将「预分配」空间的优势全部抹杀了(增加内存分配的次数)。

所以,在 SDS 相关的修改(主要是删除元素)操作中,不会立刻对空闲的空间进行回收,而是将它们作为「预留空间」。为了防止「内存泄漏」,Redis 提供了专门的 API,真正的对内存空间进行释放。

Q: 如何保证 SDS 是二进制安全的?

A:

「二进制安全」听起来是个比较陌生的词,但是如果你综合了 C 语言字符串的特点和二进制内容的特点就可以知道,二进制安全主要是防止它的内容中出现像\0这种特殊字符,干扰了对原字符串的正确解释。听起来比较高大上的问题,往往解决它的方案都是比较简单的。在 Redis 中,为了保证「二进制安全」,不在使用 C 语言字符串的\0字符作为其所存储的字符串的边界,而是使用len 这个属性,标识字符串中有效字符的个数。

虽然,为了保证「二进制安全」我们可以无视 C 语言字符串以\0作为字符串结尾的事实。但是,多数情况下大家还是会使用 Redis 储存「文本信息」(符合 C 语言字符串规则的,内容中不含有\0)。此时,对他们的操作可能要依赖于 C 语言和字符串相关的库函数,所以,在 SDS 的实现中会保持这样两个惯例:

  1. 给字符串分配内存空间时会考虑多分配1byte 的空间给\0
  2. 在修改字符串内容的时候,都会在最后追加一个\0字符