Redis在优化性能上做的努力——数据结构篇之SDS

闻道有先后，术业有专攻。可以提供给开发者非常快速读写数据能力的中间件——Redis数据库，它为了保持自己简单高效高速的能力，内部做了非常多的针对性优化手段。这篇文章来记录一下在其内部数据结构方面所下的功夫之一……

简单动态字符串SDS

众所周知Redis是用C语言实现的，但是它并没有使用C语言传统的字符串表示形式(以空字符\0结尾字符数组)，而是自己定义了一个简单动态字符串(Simple Dynamic String)，简称SDS

字符串在Redis中应该是最常见的数据形式了。在Redis中所有的数据都是以Key-Value的形式存在的，而每一个Key都是一个字符串对象，这个字符串对象的底层实现就是SDS

例如我们输入指令

SET msg "hello world"

则在Redis中会建立两个SDS，一个保存着字符串"msg"，另一个保存"hello world"

SDS的定义

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

可见每个SDS都由三部分组成，分别为：

  • len： SDS字符串长度，也是buf数组中已经使用的字节数量
  • free： buf数组中未使用的字节数量
  • buf[]： 用于保存字符串的数组

例如对于字符串"akb48"，它的数据结构可能是下面这个样子的

可以看见，SDS同样遵循C语言中字符串以空字符结尾的惯例，使用了额外的1字节来放置一个空字符作为结尾，这样做的好处就是SDS可以直接重用一部分C语言中字符串函数库里面的函数

而且可以发现free和buf的长度都是5，这并不是巧合，后面会介绍其中“空间预分配”的机制

SDS的优势

从上面的内容我们不禁会想，SDS为什么不采用C语言传统的方式而自己又多定义了这么多空间来保存信息，这样做的好处有哪些呢？

1. 获取字符串长度效率提高

C语言中字符串不记录自身长度信息，因此每当我们要获取一个字符串的长度的之后，就必须遍历整个字符数组，这样做的时间复杂度毫无疑问是O(n)。而SDS使用了额外的空间来记录下len信息，这样我们可以在O(1)的时间复杂度的情况下获取到字符串你的长度。

Redis通过使用额外的一个int空间，从而确保获取字符串长度的工作例如STRLEN指令不会对系统成为性能瓶颈。

2. 不会出现缓冲区溢出的情况

对于C语言中的字符串，我们使用下面的strcat函数时可以将src字符串中的内容拼接到dest字符串你的结尾

char *strcat(char *dest, const char *src);

C语言执行这个方法的时候，都是假定已经为dest字符串分配了足够多的内存的，而本身不会去检查。(如果要检查的话，则需要知道字符串的长度，这样又要去遍历字符数组了，性能开销大)因此当dest分配的内存不够时，则会出现缓冲区溢出的情况，例如：

我们有两个字符串s1和s2，内容分别保存的是"ABC"和"123"，他们恰好在内存空间里成为了邻居

此时我们执行方法strcat(s1, "DE")，则s1的内容将会覆盖掉s2的内容，如下图

而在Redis中，由于我们加入了len变量和free变量，可以很方便的判断拼接之前内存空间是否足够，如果不足够的情况下，Redis先会拓展s1的空间，然后才会执行拼接字符串的操作。

3. 减少修改字符串时重新分配内存的次数

在C语言中，每次增长或者缩短一个字符串，程序都需要保存这个字符串对应的字符数组并进行一次内存重分配的操作：

  • 如果是增长字符串，则需要拓展底层数组空间的大小，不然就会像上面那样产生缓冲区溢出的问题
  • 如果是缩短字符串，则需要通过内存重分配来释放掉不再使用的那一部分空间，不然则会发生内存泄漏问题

内存重分配通常对应着一系列的复杂算法，而且可能需要执行系统调用。熟悉多线程或者操作系统知识的都知道系统调用是内核态中的方法，这会导致发生用户态到内核态的转换，消耗一部分的系统性能开销。因此Redis采取了一些措施来减少修改字符串时重新分配内存的次数。

3.1 空间预分配

每当SDS被修改时，并且需要对SDS进行空间拓展的时候，Redis不仅会为SDS分配必要的空间，还会分配额外的未使用空间，并且用free字段记录下来

  • 如果对SDS修改之后，修改后的len属性值小于1MB，则SDS会被分配双倍的空间，外加一个空字符空间。例如SDS被修改之后为15字节，那么底层buf数组的空间会被分配为15+15+1 = 31字节
  • 如果对SDS修改之后，修改后的len属性值大于1MB，则SDS会被分配原本空间加上额外的1MB的空间，外加一个空字符空间。例如SDS被修改之后为15MB，那么底层buf数组的空间会被分配为15MB+1MB+1B

通过空间预分配策略，Redis可以减少连续执行字符串增长操作所需要的内存重分配次数。连续增长N次字符串所需进行的内存重分配次数从固定为N次降低为最多N次。

3.2 惰性空间释放

当SDS被缩短时，并不会像C语言的字符串那样立即回收那部分多出来的空间，而是使用free字段将其记录下来等待将来的使用。

例如我们有一个SDS，值为"ABCDEFGHIJK"，我们对其进行修改为"ABC"，之后再执行方法

sdscat(s, "1234567");

则其中底层buf数组的变化如下图

通过惰性空间释放策略，SDS避免了缩短字符串时所需的内存重分配操作，并为将来可能的增长操作提供了优化。

另外由于free字段的存在，不用担心未被释放的空间会发生泄漏问题的存在。如果需要释放空间的话，SDS同样提供相应的API来释放空间。

/* Free an sds string. No operation is performed if 's' is NULL. */
void sdsfree(sds s) {
    if (s == NULL) return;
    s_free((char*)s-sdsHdrSize(s[-1]));
}

4. 二进制安全

C语言字符串中的字符必须符合编码，例如Unicode、ANSI等等，并且除了字符串的末尾之外，不能包含空字符\0，不然的话会被当做是字符串的结尾。这种缺陷让C的字符串只能保存文本数据，如果是图片、视频等流数据的话，因为如果里面出现了\0则无法正常读取。

为了确保Redis可以适用于各种不同的场景，所有的SDS API都会以二进制的方式来处理buf数组里面的数据，这样就避免了部分字符数据带来的限制问题。例如下面值为"ABC(\0)123"的SDS可以被正常保存

5. 兼容部分C字符串中的函数

通过遵循C字符串以字符数组保存字符并且以空字符\0结尾的的惯例，SDS可以在有需要的时候重用C语言中<string.h>函数库，从而避免了不必要的代码重复。

小结

Redis通过使用SDS而不是C语言中的字符串，体现了一种以空间换时间的常见思路。因为Redis主要考虑的是自己的性能，使用单线程方式运行的Redis要能够保证自己的性能瓶颈不是CPU处理资源而是内存与网络资源。

比起C字符串，SDS的优点如下：

  • O(1)的时间复杂度获取字符串长度
  • 不会出现缓冲区溢出的现象
  • 可以大幅度减少修改字符串时内存重分配现象
  • 以二进制流的方式处理，字符安全
  • 可以兼容部分C中String函数库中的函数

本文参考资料为：《Redis设计与实现》

Last modification：July 23rd, 2021 at 08:35 pm
© 允许规范转载