凌云的博客

行胜于言

Redis 5 数据结构(一)SDS

分类:Redis| 发布时间:2019-04-13 23:43:00


概述

本文是 Redis 5 数据结构系列的第一篇,本系列主要讲解 Redis 5 底层数据结构的相关原理和实现细节。 本文主要讲的是 SDS(简单动态字符串)的结构和实现细节。

SDS 的定义

SDS 的源代码在 src/sds.h 和 src/sds.c 文件中。

和早期版本(Redis 3.0 以及更早版本)的 SDS 定义不同,Redis 5 中的 SDS 结构有如下几个版本:

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 最低位的 3 个比特表示类型,最高位的 5 个比特表示字符串的长度 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* 已用大小 */
    uint8_t alloc; /* 分配的内存大小,不包括 sdshdr8 本身的大小,以及 NULL 结束符 */
    unsigned char flags; /* 最低位的 3 个比特表示类型,最高位的 5 个比特未用 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* 已用大小 */
    uint16_t alloc; /* 分配的内存大小,不包括 sdshdr16 本身的大小,以及 NULL 结束符 */
    unsigned char flags; /* 最低位的 3 个比特表示类型,最高位的 5 个比特未用 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* 已用大小 */
    uint32_t alloc; /* 分配的内存大小,不包括 sdshdr16 本身的大小,以及 NULL 结束符 */
    unsigned char flags; /* 最低位的 3 个比特表示类型,最高位的 5 个比特未用 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* 已用大小 */
    uint64_t alloc; /* 分配的内存大小,不包括 sdshdr16 本身的大小,以及 NULL 结束符 */
    unsigned char flags; /* 最低位的 3 个比特表示类型,最高位的 5 个比特未用 */
    char buf[];
};

#define SDS_TYPE_5  0
#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4
#define SDS_TYPE_MASK 7
#define SDS_TYPE_BITS 3

SDS 提供的接口会根据要保存的内容的大小自动选择合适的结构类型。 以上结构中,除了 sdshdr5 外其他结构都是类似的,都有一个 len 成员表示已用的空间,alloc 表示分配的 buf 的大小, 而 sdshdr5 直接将 len 信息放在了 flags 字段的高 5 位中,而且没有 alloc 字段,这意味着 sdshdr5 在分配空间的时候只会按照实际使用空间大小进行分配,不会出现还有未使用的空间的情况(除非使用了 sdsclear 等操作)。

以上结构中都有一个没有指定大小的 chr buf[] 数组成员,这其实就是 C99 标准的柔性数组 ,这个成员在结构中 本身并不占用内存空间,只是用于指定结构后面的内存。

SDS 有几个特性是我们需要注意的: * 由于 sdshdrxx 有一个 len 的成员,因此可以直接通过此成员获取 sds 的大小,其复杂度为 O(1) * 所有的 SDS 接口在处理 SDS 时都会在 SDS 字符串的末尾加上 ‘\0’ 字符,因此 SDS 字符串可以用于所有需要 C 字符串的地方。 * 由于 sdshdrxx 有一个 len 的成员,因此 SDS 不单可以用于保存字符串数据,还可以保持任意的二进制数据,只要使用指定数据长度的接口即可 * 在对 SDS 使用如 sdscat 等会改变 SDS 大小的操作的时候,接口本身会检查 SDS 是否有足够空间保存改动后的数据,若不够则会申请更大的内存保存处理后的数据,这些接口一般都会返回处理后的 SDS ,调用这些接口后应该使用这些接口返回的 SDS,比如:

sds s = sdsnew("hello");
sds t = sdscat(s, " world");

在调用完 sdscat 后,应该使用 t 来进行后面的操作,并且所有原先对 s 的引用都应该改为 t,因为调用完 sdscat 后,s 原先的内存地址有可能已经被释放掉了。 * SDS 的接口在需要分配更大的内存空间的时候采用如下策略,如果修改后的 len 属性小于 1MB,则分配和 len 属性同样大小的未使用空间给 SDS,这种情况下修改后的 SDS 的 alloc 等于两倍大小的 len,如果修改后的 len 属性大于等于 1MB,则多分配 1MB 未使用空间给 SDS,这种情况下修改后的 SDS 的 alloc 等于 len + 1MB

SDS API

在这部分我们将对 SDS 提供所有的 API 进行详细讲解。

创建 SDS

typedef char *sds;
sds sdsnewlen(const void *init, size_t initlen);
sds sdsnew(const char *init);
sds sdsempty(void);
sds sdsdup(const sds s);
sds sdsnewlen(const void *init, size_t initlen)

创建内容为 init 和 initlen 指定的 SDS 字符串,如果 init 为 NULL,则字符串会被初始化为长度为 initlen 的以 ‘\0’ 填充的字符串,如果 init 为 SDS_NOINIT 则字符串为长度为 initlen 的未初始化的字符串。

可以看到 sds 实际就是字符串指针,实际上 sds 就是指向 sdshdrx 的 buf 位置,因此,SDS API 可以通过 sds[-1] 获取这个 sds header 的实际类型,从而根据类型获取 len,alloc 等信息。

而如果 sds 保存的是 C 函数兼容的字符串,则可以直接将 sds 传给 printf() 等 C 库函数。 字符串会以 ‘\0’ 结尾(所有的 SDS 字符串都是这样),因此即使你通过如下方式创建 SDS:

mystring = sdsnewlen("abc",3);

你可以安全的将 mystring 传给 printf(),因为 mystring[3] 总是等于 ‘\0’。 SDS 是二进制安全的,即使在字符串中间保存 ‘\0’ 字符也是没问题,这时你可以通过保存在 SDS header 的 length 获取 SDS 的真正长度(可以直接使用 sdslen 函数)。

sds sdsnew(const char *init);

创建一个内容为以 NULL 结尾的字符串,这个函数会通过 strlen 获取 init 的长度,然后调用带长度版本的 sdsnew。

sds sdsnew(const char *init) {
    size_t initlen = (init == NULL) ? 0 : strlen(init);
    return sdsnewlen(init, initlen);
}
sds sdsempty(void);

创建空的 SDS,通过如下方式创建:

sds sdsempty(void) {
    return sdsnewlen("",0);
}
sds sdsdup(const sds s);

复制一个 SDS

sds sdsdup(const sds s) {
    return sdsnewlen(s, sdslen(s));
}
````

#### 释放 SDS 的空间
```c
void sdsfree(sds s);

当 s 为 NULL 时,不作任何操作

扩大 SDS 的长度,扩大的部分以 0 填充

sds sdsgrowzero(sds s, size_t len);

如果指定的长度比 SDS 本身的长度要小,则这个函数不会进行任何操作

追加数据

sds sdscatlen(sds s, const void *t, size_t len);
sds sdscat(sds s, const char *t);
sds sdscatsds(sds s, const sds t);
sds sdscatlen(sds s, const void *t, size_t len);

追加长度为 len 的数据到 s 中,此函数执行完后,s 有可能不再有效,因此所有对 s 的引用必须替换为函数返回的指针。

sds sdscat(sds s, const char *t);
sds sdscat(sds s, const char *t) {
    return sdscatlen(s, t, strlen(t));
}
sds sdscatsds(sds s, const sds t);

将 t 的数据追加到 s 中,内部调用 sdscatlen 实现。

复制数据到 SDS

sds sdscpylen(sds s, const char *t, size_t len);
sds sdscpy(sds s, const char *t);

调用完这两个函数后,s 可能就无效了,所有对 s 的引用都应该用函数的返回值替代。

格式化字符串

sds sdscatvprintf(sds s, const char *fmt, va_list ap);
sds sdscatprintf(sds s, const char *fmt, ...);
sds sdscatfmt(sds s, char const *fmt, ...);
sds sdscatvprintf(sds s, const char *fmt, va_list ap);

先用 vsnprintf 格式化数据,然后将格式化后的数据使用 sdscat 追加到 s 中。

sds sdscatprintf(sds s, const char *fmt, …);

内部调用 sdscatvprintf。比较有意思的是这个函数在头文件的声明:

#ifdef __GNUC__
sds sdscatprintf(sds s, const char *fmt, ...)
    __attribute__((format(printf, 2, 3)));
#else
sds sdscatprintf(sds s, const char *fmt, ...);
#endif

如果使用的是 GNUC 则添加了 __attribute__((format(printf, 2, 3))) 声明。这个属性声明的详细作用可以查看: https://gcc.gnu.org/onlinedocs/gcc-8.3.0/gcc/Common-Function-Attributes.html#Common-Function-Attributes 这里简单讲解下这个属性声明的作用,对 sdscatprintf 函数参数进行类型检查,其中第二个参数为格式化参数,格式与 printf 的格式字符串一样, 从这个函数的第三个参数开始检查,添加此属性后,如果发现后面的参数格式与格式化字符串需要的格式不一致编译器会报 Warning。

sds sdscatfmt(sds s, char const *fmt, …);

前面两个格式化函数都使用了 C 函数的 vsnprintf,而这个函数通常很慢, 因此 SDS 自己实现了一个类似 sdscatvprintf 的高效的格式化函数。

但是这个函数只能处理部分与 printf 不兼容的格式说明符: * %s - C 字符串 * %S - SDS 字符串 * %i - 有符号整数 * %I - 64 位有符号整数 (long long, int64_t) * %u - 无符号整数 * %U - 64 位无符号整数 (unsigned long long, uint64_t) * %% - 一个 “%” 字符

更新 SDS 的数据

sds sdstrim(sds s, const char *cset);
void sdsrange(sds s, ssize_t start, ssize_t end);
void sdsupdatelen(sds s);
void sdsclear(sds s);
void sdstolower(sds s);
void sdstoupper(sds s);
sds sdstrim(sds s, const char *cset);

去掉字符串两边的由 ‘cset’ 里的字符组成的连续子串。

注意:无论从函数的声明还是源码的注释来看,在调用完这个函数后,都应该假设传进去的 SDS 已经无效。 但是从 Redis 5.0.4 版本的 sdstrim 的实现来看,传进去的 SDS 总是等于返回的 SDS。

假设有如下代码:

 s = sdsnew("AA...AA.a.aa.aHelloWorld     :::");
 s = sdstrim(s,"Aa. :");
 printf("%s\n", s);

结果应该为:”HelloWorld”

void sdsrange(sds s, ssize_t start, ssize_t end);

将 SDS 变为一个只包含由 start 和 end 指定的范围的子字符串。

start 和 end 可以是负数,当为负数时,-1 表示最后一个字符,-2 表示倒数第二个字符,依次类推。 指定的区间是个闭区间,修改后的结果原地修改到字符串中。

比如有如下代码:

 s = sdsnew("Hello World");
 sdsrange(s,1,-1); => "ello World"

结果为: “ello World”

void sdsupdatelen(sds s);

将 SDS 字符串的长度设置为 strlen() 所获得的长度,就是说当遇到第一个空字符串时就认为字符串已经结束了。

通常可以在手动修改字符串后,使用 sdsupdatelen 更新字符串的长度,比如:

 s = sdsnew("foobar");
 s[2] = '\0';
 sdsupdatelen(s);
 printf("%d\n", sdslen(s));

结果为 2,如果不调用 sdsupdatelen 结果应该为 6。

void sdsclear(sds s);

原地清除 SDS 的数据,这个函数只会将 SDS 的 len 设置为 0,以及将 buf[0] 设置为 ‘\0’。

void sdstolower(sds s);

对里面的每个字符调用 tolower(),将结果写回原地。

void sdstoupper(sds s);

对里面的每个字符调用 toupper(),将结果写回原地。

比较函数

int sdscmp(const sds s1, const sds s2);

用 memcmp() 比较两个 SDS 字符串。 返回值: * 当 s1 > s2,返回正数 * 当 s1 < s2,返回负数 * s1 和 s2,二进制相等,返回 0

当两个 SDS 有相同前缀时,认为长的字符串比短的字符串要大。

split

sds *sdssplitlen(const char *s, ssize_t len, const char *sep, int seplen, int *count);
void sdsfreesplitres(sds *tokens, int count);
sds *sdssplitargs(const char *line, int *argc);
sds *sdssplitlen(const char *s, ssize_t len, const char *sep, int seplen, int *count);

用 ‘sep’ 分割 ’s’,返回一组 SDS 字符串,*count 为返回的字符串的大小。

当出现内存不足时,返回 NULL,sep 可以为多个字符,函数内部使用 memcmp 来判断 ’s’ 里面是否有和 ‘sep’ 一样的子串。

void sdsfreesplitres(sds *tokens, int count);

释放 sdssplitlen 返回的 SDS 数组。

sds *sdssplitargs(const char *line, int *argc);

将 line 分割为多个参数,每个参数都可能是如下的 “programming-language REPL-alike” 形式:

foo bar "newline are supported\n" and "\xff\x00otherstuff"

argc 保存了返回的 sds 数组的数量。

调用者需要使用 sdsfreesplitres() 释放返回的 SDS 数组。

需要注意的是 sdssplitargs() 可以解析 sdscatrepr() 返回的结果回原来的格式。

这个函数会在解析成功后返回 SDS 数组,如果传进来的是空字符串,返回的结果也不为 NULL(此时 argc 为 0)。 如果发现传进来的字符串是非法的(比如,双引号或者单引号不匹配)则会返回 NULL。

join

sds sdsjoin(char **argv, int argc, char *sep);
sds sdsjoinsds(sds *argv, int argc, const char *sep, size_t seplen);

低层函数

sds sdsMakeRoomFor(sds s, size_t addlen);
void sdsIncrLen(sds s, ssize_t incr);
sds sdsRemoveFreeSpace(sds s);
size_t sdsAllocSize(sds s);
void *sdsAllocPtr(sds s);
sds sdsMakeRoomFor(sds s, size_t addlen);

扩大 SDS 的可用空间,使得返回的 SDS 至少有长度为 addlen 的可用空间。 这个函数不会改变 SDS 的 len 大小。

void sdsIncrLen(sds s, ssize_t incr);

增加 SDS 的长度,并减少可用空间,同样会在字符串末尾添加空字符串。

这个函数的一个使用场景为使用 sdsMakeRoomFor() 为 SDS 创建了一部分可用空间, 然后直接追加了部分数据到 SDS,最后调用这个函数来设置 SDS 的长度。

当 incr 为负数时表示要缩短字符串。

例子:

oldlen = sdslen(s);
s = sdsMakeRoomFor(s, BUFFER_SIZE);
nread = read(fd, s+oldlen, BUFFER_SIZE);
// ... check for nread <= 0 and handle it ...
sdsIncrLen(s, nread);
sds sdsRemoveFreeSpace(sds s);

重新创建 SDS 字符串,使得 SDS 不会有可用空间(就是 alloc == len)。

size_t sdsAllocSize(sds s);

返回 SDS 所占用的内存大小,包括: * SDS 数据前的 SDS header 大小 * SDS 数据大小 * 可能有的空闲空间 * 隐式的 NULL 字符串

size_t sdsAllocSize(sds s) {
    size_t alloc = sdsalloc(s);
    return sdsHdrSize(s[-1])+alloc+1;
}
void *sdsAllocPtr(sds s);

返回创建 SDS 时所申请的内存空间的指针 (通常来说返回的 SDS 都是指向数据部分)

void *sdsAllocPtr(sds s) {
    return (void*) (s-sdsHdrSize(s[-1]));
}

allocator 相关函数

void *sds_malloc(size_t size);
void *sds_realloc(void *ptr, size_t size);
void sds_free(void *ptr);

这几个函数主要用于外部程序使用,当外部需要自己创建 SDS 或者是否 SDS 时,需要使用这几个函数。

其他

sds sdsfromlonglong(long long value);
sds sdscatrepr(sds s, const char *p, size_t len);
sds sdsmapchars(sds s, const char *from, const char *to, size_t setlen);
sds sdsfromlonglong(long long value);

将一个 long long 保存为 SDS 字符串形式。比

sdscatprintf(sdsempty(),"%lld\n", value);

要快得多。

sds sdscatrepr(sds s, const char *p, size_t len);

将 p 追加到 s 中,其中 s 为 escaped 字符串,这表示 p 中所有无法打印的字符都会被 escaped,如: * ‘\n’ -> “\n” * ‘\r’ -> “\r” * ‘\t’ -> “\t” * ‘\a’ -> “\a” * ‘\b’ -> “\b” * 其他不可打印的字符(通过 isprint() 函数判断)-> “\x

通过这个函数追加的字符串总是以双引号包含起来。

所有对 s 的引用必须替换为函数返回的指针。

sds sdsmapchars(sds s, const char *from, const char *to, size_t setlen);

将 s 中所有出现在 from 的字符替换为 to 中对应的字符。

比如:

sdsmapchars(mystring, "ho", "01", 2)

结果为 “0ell1”