Redis字符串的底层实现SDS

发表于 | 分类于 |
字数统计: 2.3k | 阅读时长 ≈ 8

【引子】

Redis没有直接使用C语言传统的字符串表示，而是自己构建了一种名为简单动态字符串（Simple Dynamic String，SDS）的抽象类型，并将SDS用作Redis的默认字符串表示。

在Redis里面，包含字符串值的键值对在底层都是由SDS实现的，比如：

1
set moremoney programmer

那么Redis将在数据库中创建一个新的键值对，其中：

  • 该键值对的键moremoney是一个字符串对象，底层实现是一个保存了字符串“moremoney”的SDS
  • 该键值对的值programmer也是一个字符串对象，底层实现是一个保存了字符串“programmer”的SDS

除了以上用处，SDS还被用作AOF模块中的AOF缓冲区，以及客户端状态中的输入缓冲区等。

【SDS的定义】

SDS是通过C语言来实现的，我那会儿读大学时，学校最先开始教的是C语言，所以我对C语言也还算有点熟悉。

每个sds.h/sdshdr结构表示一个SDS值（为什么这么设计后续会分析）：

1
2
3
4
5
6
7
8
9
10
11
struct sdshdr {
    //记录buf数组中已使用字节的数量
    //等于SDS所保存字符串的长度
    int len;
    
    //记录buf数组中未使用的字节的数量
    int free;
    
    //字节数组，用于保存字符串
    char buf[];
};

简单来说：

  • 当free属性的值为0，则表示这个SDS没有分配任何未使用的空间；反之，则分配了free个字节的未使用的空间；
  • 字符串的长度为len
  • buf属性是一个char类型的数组，数组的前面保存了该字符串的每个字符，最后一个字节则保存了一个空字符’\0’

SDS遵循了C字符串以空字符结尾的惯例，保存空字符的1字节不会计算在len属性里面（也就是说保存“hello world”的字符串的SDS的len为11），并且为空字符分配的这个额外的1字节的空间，以及添加空字符到字符串末尾等操作，都是由SDS函数自动完成的，也就是说，这个空字符对于SDS的使用者或者Redis的使用者来说是完全透明的，这也体现了封装的思想，对外隐藏实现的细节，简化外部使用者。

SDS的设计者遵循空字符结尾的惯例的一个明显的好处，就是SDS可以直接重用一部分C字符串函数库里面的函数，比如打印字符串。

【SDS与C字符串的区别】

根据传统，C语言使用长度为N+1的字符数组来表示长度为N的字符串，因为最后一个元素是空字符’\0’，表示C字符串的结尾。

C语言使用的这种实现方式，并不能满足Redis对字符串在安全性、效率，以及功能方面的要求。

获取字符串长度

因为C字符串并没有记录字符串的长度信息，所以在获取C字符串长度的时候，必须遍历整个C字符串，遍历到的每个字符都要做计数+1，直到遇到代表字符串结尾的空字符’\0’为止（不计算进去），这个操作的时间复杂度就是O(N)，N为字符串长度。

SDS就不同了，由于SDS直接存储了字符串的长度len，想要获取一个用SDS表示的字符串的长度，只要读取len属性的值就行了，即时间复杂度仅为O(1)。

而且，无需使用者操心的是：设置和更新SDS的len属性的工作，都是由操作SDS的API在执行的时候自动完成的。

通过使用SDS，Redis将获取字符串长度所需的时间，从C字符串的O(N)降低到了O(1)，这确保了获取字符串长度的工作不会成为Redis的瓶颈。

杜绝缓冲区溢出

不记录C字符串的长度，容易造成缓冲区溢出（buffer overflow）。比如通过C函数strcat，将src字符串中的内容拼接到dest字符串的末尾：

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

由于C字符串不记录自身的长度，如果用户在执行strcat函数时，没有给dest分配足够的内容来容纳src，就会产生缓冲区溢出。

SDS的空间分配策略，能够完全杜绝缓冲区溢出的发生：当SDS API需要对SDS进行修改时，API会先检查SDS的空间是否满足修改的需求，若不满足，则API会自动将SDS的空间扩展以至于能够放下src。

修改SDS字符串N次，真的会像C字符串那样，一定做N次内存重分配吗？

我们从前面的文章了解到“C字符串不记录自身的长度”，通过最后一个空字符’\0’来表示字符串结束。所以每次拉长或缩短C字符串，程序总要对保存这个C字符串的数组进行一次内存重分配：

  • 拉长：程序需要先通过内存重分配来扩展底层数组的空间，如果忘了这一步就会产生缓冲区溢出
  • 缩短：程序需要先通过内存重分配来释放字符串不再使用的那部分空间，如果忘了这一步就会产生内存泄漏

由于涉及复杂的算法，且可能需要执行系统调用，所以相对来说，内存重分配是一个比较耗时的操作。Redis作为一个对性能有极致要求的数据库，如果这种操作频繁的发生，可能就会造成一些瓶颈了。

为了避免C字符串的这种缺陷，SDS的设计者相处了一个巧妙的办法：通过未使用空间来解除字符串长度和底层数组长度之间的关联。在SDS中，buf数组的长度不一定就是字符数量+1（+1是最后还是存了空字符’\0’），宿主里面可以包含未使用的字节，这些未使用的字节数量就是free的值。

通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化策略。

  • 空间预分配：当API对一个SDS进行修改，并且需要对SDS空间进行扩展，程序不仅会为SDS分配修改所必须的空间，还会额外分配“未使用空间”，额外分配策略有2种：

    1. 如果对SDS进行修改之后，len小于1MB，那么程序分配和len一样大小的未使用空间
    2. 如果对SDS进行修改之后，len大于1MB，那么程序分配1MB的未使用空间

    空间预分配的好处是，减少连续执行字符串增长操作所需的内存重分配次数：在扩展SDS空间之前，SDS API会先检查未使用空间是否足够，如果足够的话，API就会直接使用未使用空间，而不会执行内存重分配。

  • 惰性空间释放：当需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性来将这些字节记录起来，可供将来扩展使用，相当于优化了将来可能有的增长操作，因为空出来了字节，那么能够容纳增长的字符的话就不需要再内存重分配了。

可能你会担心，惰性空间释放这个特性，会造成内存泄漏，其实SDS提供了相关API，让我们在有需要的时候，真正的释放SDS的未使用空间。

二进制安全

之前有篇文章有提到“二进制安全是什么？”，这里不再详述，简单来说就是C字符串存在二进制安全的问题，它职能保存文本数据，而不能保存像图片、音频、视频压缩文件等二进制数据，因为遇到’\0’就是一个结束了的C字符串。

而SDS的API都是二进制安全的，所有API以处理二进制的方式来处理SDS存放的buf数组里的数据，程序不会对其中的数据做任何限制、过滤、或者转义，数据在写入时是怎么样的，被读取时就是什么样。这也是将SDS的buf数组叫做字节数组的原因——Redis不是用这个数组来保存字符，而使用它来直接保存二进制数据。

所以，Redis不仅可以保存文本，还可以保存任意的二进制数据。非常强大。

兼容部分C字符串函数

前面提到过，SDS遵循了C字符串以空字符’\0’结尾的惯例，并且SDS的API自动维护了这个空字符，所以SDS可以重用一部分<string.h>库定义的函数。这样Redis就不用重复去造轮子了。

------------- 本文结束感谢阅读 -------------
给猫玛尼加个鸡腿~