【Redis 系列 02】Redis 简单动态字符串

01、SDS 数据结构

Redis 底层是基于 C 语言来开发的,但是它没有采用 C 语言传统的字符串表示方式,而是自定义了一种叫做 SDS(Sample Dynamic String,简单动态字符串)的数据结构来表示字符串。传统的 C 语言的字符串是采用空字符(\0)作为结尾的字符数组,SDS 的数据结构稍微复杂一点,整个结构包含三个部分,是 Redis 的基础。

1.1、数据结构

在 sds.h/sdshdr 结构体中定于了 SDS 的数据结构,包括三个部分,free,len,buf[],依次含义如下

  1. buf[]:字节数组,用于存放实际的字符串;
  2. len:记录 buf 数组中已经使用的字节数量,等同于 SDS 所保存的字符串的长度;
  3. free:记录 buf 数组中未使用的字节的数量。

image-20191015000650127

说明

上图中的 SDS 表示一个存放了 ‘RED’ 字符串,已经使用的长度为 3,未使用的长度为 2(这里用空白格表示未使用),其中的 ‘\0’ 表示的是字符串的结束,不计算在 SDS 的 len 中,并且由 SDS 底层函数自动添加,对使用者来说是透明。这里统一采用空字符(\0)结尾是为了复用 C 语言的相关函数。

02、为什么采用 SDS

2.1、SDS 与 C语言字符串的区别

在说明 Redis 为什么要自定义 SDS 之前我们先看一下 SDS 与传统的 C 语言的字符串有什么区别,知道了具体的区别我们才能知道这样实现的原因是什么。

2.1.1、O(1) 获取字符串的长度

传统的 C 语言字符串如果要获取字符串的长度,则需要遍历整个字符串,直到遇到 ‘\0’ 字符,才知道整个字符串的长度是多少,操作复杂度是 O(n) 的。但是在 SDS 中,由于我们记录了字符串的长度,所以在获取字符串长度的时候是可以直接获取的,整个操作为 O(1)。

如上面的示例,我们可以直接获取字符串的长度是 3,而不需要遍历,另外字符串 Key 在 Redis 的底层实现就是采用 SDS 的,所以这个特性就保证了我们在计算 Key 的长度的时候不会出现任何瓶颈,对系统的性能不会有任何影响。

2.1.2、动态扩容

由于 SDS 中记录了未使用的空间大小,所以如果出现对已有字符串进行修改或者赋值时,SDS 底层函数会自动检测剩余空间是否能满足此次修改,如果 free 空间足够则直接修改;如果 free 空间不够则会先进行动态扩容达到能满足的空间大小,然后再执行修改动作。整个扩容的动作是 SDS 底层函数自动完成,对使用者无感。

而对于传统的 C 语言字符串,如果在修改前忘记手动扩容则会导致字符串后面的数据被覆盖。

2.1.3、减少内存分配次数

在传统的 C 语言的字符串,我们每次对字符串的修改都会涉及到字符串内存的重新分配,不管是增加还是减少字符串的长度。这种情况下,如果我们多次对字符串的长度进行调整的时候就会导致多次的内存重新分配。

而在 SDS 中我们在对一个 SDS 初始化的时候会根据实际 buf[] 字符串的长度进行预先空间分配,并且标记为 free。这种方式叫做空间预分配,在很大程度上可以减少增加字符串长度导致内存重新分配的情况。free 的空间分配的策略是根据 buf[] 大小来决定的,如果 buf[] 大小小于 1MB,则 len 多大 free 就多大;如果 buf[] 大小大于 1MB,则 free 固定设置为 1MB。

上面说的是SDS 字符串的长度增加,另外如果 SDS 的字符串长度减少,那么 SDS 会将减少的长度存放到 free 中,而不是直接回收,这样可以方便下次如果再次使用,减少内存重新分配。这种策略叫做惰性空间释放

同样的上面两种操作对使用者是完全无感的。

2.1.4、二进制安全

我们都知道 Redis 是可以存储各种类型数据的,不仅是字符串也可以存储图片,视频等二进制数据流。这是由于 Redis 不依赖一 ‘\0’ 空字符作为结束字符。C 语言之所以不支持就是因为二进制流中会携带 ‘\0’ 字符,导致无法知道字符串真实的结束位置。这就带来了另一个 Redis 特性,就是二进制的安全性。

2.2 为什么使用 SDS

通过上面的内容我们知道了 SDS 比传统的 C 语言的字符串有很多优势,也正是这些必不可少的优势才促成了 SDS的存在。Redis 是一个高性能的内存数据库,所以在性能方面要求特别高,这种设计方式虽然浪费了一定的空间,但是为了达到性能的要求也是值得的。有空间换时间的这种方式,在软件设计的领域还是很多的。

2.3 SDS 常用 API

在 2.1 中提到有获取长度 len 和释放空间 free 的动作,那么对应在 SDS 底层必定会有提供支持的 API,下面我们通过源码来看几个常用的 API。

  1. 在源码 sds.c 文件中 sdsfree 函数定义如下
1
2
3
4
5
/* 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]));
}
  1. 在源码 sds.h 文件中 sdslen 函数定义如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static inline size_t sdslen(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8:
            return SDS_HDR(8,s)->len;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->len;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->len;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->len;
    }
    return 0;
}
  1. 在源码 sds.c 文件中创建 sds 的函数定义如下
1
2
3
4
5
6
7
8
9
10
11
/* Create an empty (zero length) sds string. Even in this case the string
 * always has an implicit null term. */
sds sdsempty(void) {
    return sdsnewlen("",0);
}

/* Create a new sds string starting from a null terminated C string. */
sds sdsnew(const char *init) {
    size_t initlen = (init == NULL) ? 0 : strlen(init);
    return sdsnewlen(init, initlen);
}

03、总结

这篇文章跟大家介绍了一下 Redis 的 SDS 和 SDS 底层的组成结构,并且与 C 语言传统字符串进行的详细的对比,阐述了 SDS 出现解决了哪些问题,最后带大家从源码中简单的看了几个底层的函数实现。这篇文章就到这里,下篇文章我们会介绍 Redis 常用的一些基础数据结构和常用命令,敬请期待。

04、参考文档

  1. https://github.com/antirez/redis
  2. https://redis.io/
  3. 《Redis 设计与实现(第二版)》——黄建宏
Java Geek Tech wechat
欢迎订阅 Java 极客技术,这里分享关于 Java 的一切。