Redis中内部数据结构sds的作用是什么

53次阅读

共计 9708 个字符，预计需要花费 25 分钟才能阅读完成。

Redis 中内部数据结构 sds 的作用是什么，很多新手对此不是很清楚，为了帮助大家解决这个难题，下面丸趣 TV 小编将为大家详细讲解，有这方面需求的人可以来学习下，希望你能有所收获。

sds 的数据结构定义

我们知道，在 C 语言中，字符串是以’\0’字符结尾（NULL 结束符）的字符数组来存储的，通常表达为字符指针的形式（char *）。它不允许字节 0 出现在字符串中间，因此，它不能用来存储任意的二进制数据。

我们可以在 sds.h 中找到 sds 的类型定义：

typedef char
sds;
肯定有人感到困惑了，竟然 sds 就等同于 char？我们前面提到过，sds 和传统的 C 语言字符串保持类型兼容，因此它们的类型定义是一样的，都是 char
。在有些情况下，需要传入一个 C 语言字符串的地方，也确实可以传入一个 sds。但是，sds 和 char 并不等同。sds 是 Binary Safe 的，它可以存储任意二进制数据，不能像 C 语言字符串那样以字符’\0’来标识字符串的结束，因此它必然有个长度字段。但这个长度字段在哪里呢？实际上 sds 还包含一个 header 结构：

struct __attribute__ ((__packed__)) sdshdr5 {
 unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
 char buf[];
struct __attribute__ ((__packed__)) sdshdr8 {
 uint8_t len; /* used */
 uint8_t alloc; /* excluding the header and null terminator */
 unsigned char flags; /* 3 lsb of type, 5 unused bits */
 char buf[];
struct __attribute__ ((__packed__)) sdshdr16 {
 uint16_t len; /* used */
 uint16_t alloc; /* excluding the header and null terminator */
 unsigned char flags; /* 3 lsb of type, 5 unused bits */
 char buf[];
struct __attribute__ ((__packed__)) sdshdr32 {
 uint32_t len; /* used */
 uint32_t alloc; /* excluding the header and null terminator */
 unsigned char flags; /* 3 lsb of type, 5 unused bits */
 char buf[];
struct __attribute__ ((__packed__)) sdshdr64 {
 uint64_t len; /* used */
 uint64_t alloc; /* excluding the header and null terminator */
 unsigned char flags; /* 3 lsb of type, 5 unused bits */
 char buf[];};

sds 一共有 5 种类型的 header。之所以有 5 种，是为了能让不同长度的字符串可以使用不同大小的 header。这样，短字符串就能使用较小的 header，从而节省内存。

一个 sds 字符串的完整结构，由在内存地址上前后相邻的两部分组成：

一个 header。通常包含字符串的长度 (len)、最大容量(alloc) 和 flags。sdshdr5 有所不同。
一个字符数组。这个字符数组的长度等于最大容量 +1。真正有效的字符串数据，其长度通常小于最大容量。在真正的字符串数据之后，是空余未用的字节（一般以字节 0 填充），允许在不重新分配内存的前提下让字符串数据向后做有限的扩展。在真正的字符串数据之后，还有一个 NULL 结束符，即 ASCII 码为 0 的’\0’字符。这是为了和传统 C 字符串兼容。之所以字符数组的长度比最大容量多 1 个字节，就是为了在字符串长度达到最大容量时仍然有 1 个字节存放 NULL 结束符。
除了 sdshdr5 之外，其它 4 个 header 的结构都包含 3 个字段：

len:  表示字符串的真正长度（不包含 NULL 结束符在内）。alloc:  表示字符串的最大容量（不包含最后多余的那个字节）。flags:  总是占用一个字节。其中的最低 3 个 bit 用来表示 header 的类型。header 的类型共有 5 种，在 sds.h 中有常量定义。#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

sds 的数据结构，我们有必要非常仔细地去解析它。

Redis dict 结构举例

上图是 sds 的一个内部结构的例子。图中展示了两个 sds 字符串 s1 和 s2 的内存结构，一个使用 sdshdr8 类型的 header，另一个使用 sdshdr16 类型的 header。但它们都表达了同样的一个长度为 6 的字符串的值：”tielei”。下面我们结合代码，来解释每一部分的组成。

sds 的字符指针（s1 和 s2）就是指向真正的数据（字符数组）开始的位置，而 header 位于内存地址较低的方向。在 sds.h 中有一些跟解析 header 有关的宏定义：

#define SDS_TYPE_MASK 7
#define SDS_TYPE_BITS 3
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
#define SDS_TYPE_5_LEN(f) ((f) SDS_TYPE_BITS)

其中 SDS_HDR 用来从 sds 字符串获得 header 起始位置的指针，比如 SDS_HDR(8, s1)表示 s1 的 header 指针，SDS_HDR(16, s2)表示 s2 的 header 指针。

当然，使用 SDS_HDR 之前我们必须先知道到底是哪一种 header，这样我们才知道 SDS_HDR 第 1 个参数应该传什么。由 sds 字符指针获得 header 类型的方法是，先向低地址方向偏移 1 个字节的位置，得到 flags 字段。比如，s1[-1]和 s2[-1]分别获得了 s1 和 s2 的 flags 的值。然后取 flags 的最低 3 个 bit 得到 header 的类型。

由于 s1[-1] == 0x01 == SDS_TYPE_8，因此 s1 的 header 类型是 sdshdr8。
由于 s2[-1] == 0x02 == SDS_TYPE_16，因此 s2 的 header 类型是 sdshdr16。
有了 header 指针，就能很快定位到它的 len 和 alloc 字段：

s1 的 header 中，len 的值为 0x06，表示字符串数据长度为 6；alloc 的值为 0x80，表示字符数组最大容量为 128。
s2 的 header 中，len 的值为 0x0006，表示字符串数据长度为 6；alloc 的值为 0x03E8，表示字符数组最大容量为 1000。（注意：图中是按小端地址构成）
在各个 header 的类型定义中，还有几个需要我们注意的地方：

在各个 header 的定义中使用了 attribute ((packed))，是为了让编译器以紧凑模式来分配内存。如果没有这个属性，编译器可能会为 struct 的字段做优化对齐，在其中填充空字节。那样的话，就不能保证 header 和 sds 的数据部分紧紧前后相邻，也不能按照固定向低地址方向偏移 1 个字节的方式来获取 flags 字段了。

在各个 header 的定义中最后有一个 char buf[]。我们注意到这是一个没有指明长度的字符数组，这是 C 语言中定义字符数组的一种特殊写法，称为柔性数组（flexible array member），只能定义在一个结构体的最后一个字段上。

它在这里只是起到一个标记的作用，表示在 flags 字段后面就是一个字符数组，或者说，它指明了紧跟在 flags 字段后面的这个字符数组在结构体中的偏移位置。而程序在为 header 分配的内存的时候，它并不占用内存空间。

如果计算 sizeof(struct sdshdr16)的值，那么结果是 5 个字节，其中没有 buf 字段。
sdshdr5 与其它几个 header 结构不同，它不包含 alloc 字段，而长度使用 flags 的高 5 位来存储。

因此，它不能为字符串分配空余空间。如果字符串需要动态增长，那么它就必然要重新分配内存才行。所以说，这种类型的 sds 字符串更适合存储静态的短字符串（长度小于 32）。

至此，我们非常清楚地看到了：sds 字符串的 header，其实隐藏在真正的字符串数据的前面（低地址方向）。这样的一个定义，有如下几个好处：

header 和数据相邻，而不用分成两块内存空间来单独分配。这有利于减少内存碎片，提高存储效率（memory efficiency）。

虽然 header 有多个类型，但 sds 可以用统一的 char * 来表达。且它与传统的 C 语言字符串保持类型兼容。

如果一个 sds 里面存储的是可打印字符串，那么我们可以直接把它传给 C 函数，比如使用 strcmp 比较字符串大小，或者使用 printf 进行打印。
弄清了 sds 的数据结构，它的具体操作函数就比较好理解了。

sds 的一些基础函数
sdslen(const sds s):  获取 sds 字符串长度。sdssetlen(sds s, size_t newlen):  设置 sds 字符串长度。sdsinclen(sds s, size_t inc):  增加 sds 字符串长度。sdsalloc(const sds s):  获取 sds 字符串容量。sdssetalloc(sds s, size_t newlen):  设置 sds 字符串容量。sdsavail(const sds s):  获取 sds 字符串空余空间（即 alloc - len）。sdsHdrSize(char type):  根据 header 类型得到 header 大小。sdsReqType(size_t string_size):

根据字符串数据长度计算所需要的 header 类型。
这里我们挑选 sdslen 和 sdsReqType 的代码，察看一下。

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)- 
 case SDS_TYPE_16:
 return SDS_HDR(16,s)- 
 case SDS_TYPE_32:
 return SDS_HDR(32,s)- 
 case SDS_TYPE_64:
 return SDS_HDR(64,s)- 
 }
 return 0;
static inline char sdsReqType(size_t string_size) { if (string_size   1 5)
 return SDS_TYPE_5;
 if (string_size   1 8)
 return SDS_TYPE_8;
 if (string_size   1 16)
 return SDS_TYPE_16;
 if (string_size   1ll 32)
 return SDS_TYPE_32;
 return SDS_TYPE_64;
}

跟前面的分析类似，sdslen 先用 s[-1]向低地址方向偏移 1 个字节，得到 flags；然后与 SDS_TYPE_MASK 进行按位与，得到 header 类型；然后根据不同的 header 类型，调用 SDS_HDR 得到 header 起始指针，进而获得 len 字段。

通过 sdsReqType 的代码，很容易看到：

长度在 0 和 2^5- 1 之间，选用 SDS_TYPE_5 类型的 header。
长度在 2^5 和 2^8- 1 之间，选用 SDS_TYPE_8 类型的 header。
长度在 2^8 和 2^16- 1 之间，选用 SDS_TYPE_16 类型的 header。
长度在 2^16 和 2^32- 1 之间，选用 SDS_TYPE_32 类型的 header。
长度大于 2^32 的，选用 SDS_TYPE_64 类型的 header。能表示的最大长度为 2^64-1。
注：sdsReqType 的实现代码，直到 3.2.0，它在长度边界值上都一直存在问题，直到最近 3.2 branch 上的 commit 6032340 才修复。

sds 的创建和销毁

sds sdsnewlen(const void *init, size_t initlen) {
 void *sh;
 sds s;
 char type = sdsReqType(initlen);
 /* Empty strings are usually created in order to append. Use type 8
 * since type 5 is not good at this. */
 if (type == SDS_TYPE_5   initlen == 0) type = SDS_TYPE_8;
 int hdrlen = sdsHdrSize(type);
 unsigned char *fp; /* flags pointer. */
 sh = s_malloc(hdrlen+initlen+1);
 if (!init)
 memset(sh, 0, hdrlen+initlen+1);
 if (sh == NULL) return NULL;
 s = (char*)sh+hdrlen;
 fp = ((unsigned char*)s)-1;
 switch(type) {
 case SDS_TYPE_5: { *fp = type | (initlen   SDS_TYPE_BITS);
 break;
 }
 case SDS_TYPE_8: { SDS_HDR_VAR(8,s);
 sh- len = initlen;
 sh- alloc = initlen;
 *fp = type;
 break;
 }
 case SDS_TYPE_16: { SDS_HDR_VAR(16,s);
 sh- len = initlen;
 sh- alloc = initlen;
 *fp = type;
 break;
 }
 case SDS_TYPE_32: { SDS_HDR_VAR(32,s);
 sh- len = initlen;
 sh- alloc = initlen;
 *fp = type;
 break;
 }
 case SDS_TYPE_64: { SDS_HDR_VAR(64,s);
 sh- len = initlen;
 sh- alloc = initlen;
 *fp = type;
 break;
 }
 }
 if (initlen   init)
 memcpy(s, init, initlen);
 s[initlen] =  \0 
 return s;
sds sdsempty(void) { return sdsnewlen( ,0);
sds sdsnew(const char *init) { size_t initlen = (init == NULL) ? 0 : strlen(init);
 return sdsnewlen(init, initlen);
void sdsfree(sds s) { if (s == NULL) return;
 s_free((char*)s-sdsHdrSize(s[-1]));
}

sdsnewlen 创建一个长度为 initlen 的 sds 字符串，并使用 init 指向的字符数组（任意二进制数据）来初始化数据。如果 init 为 NULL，那么使用全 0 来初始化数据。它的实现中，我们需要注意的是：

如果要创建一个长度为 0 的空字符串，那么不使用 SDS_TYPE_5 类型的 header，而是转而使用 SDS_TYPE_8 类型的 header。这是因为创建的空字符串一般接下来的操作很可能是追加数据，但 SDS_TYPE_5 类型的 sds 字符串不适合追加数据（会引发内存重新分配）。
需要的内存空间一次性进行分配，其中包含三部分：header、数据、最后的多余字节（hdrlen+initlen+1）。
初始化的 sds 字符串数据最后会追加一个 NULL 结束符（s[initlen] =‘\0’）。
关于 sdsfree，需要注意的是：内存要整体释放，所以要先计算出 header 起始指针，把它传给 s_free 函数。这个指针也正是在 sdsnewlen 中调用 s_malloc 返回的那个地址。

sds 的连接（追加）操作

sds sdscatlen(sds s, const void *t, size_t len) { size_t curlen = sdslen(s);
 s = sdsMakeRoomFor(s,len);
 if (s == NULL) return NULL;
 memcpy(s+curlen, t, len);
 sdssetlen(s, curlen+len);
 s[curlen+len] =  \0 
 return s;
sds sdscat(sds s, const char *t) { return sdscatlen(s, t, strlen(t));
sds sdscatsds(sds s, const sds t) { return sdscatlen(s, t, sdslen(t));
sds sdsMakeRoomFor(sds s, size_t addlen) {
 void *sh, *newsh;
 size_t avail = sdsavail(s);
 size_t len, newlen;
 char type, oldtype = s[-1]   SDS_TYPE_MASK;
 int hdrlen;
 /* Return ASAP if there is enough space left. */
 if (avail  = addlen) return s;
 len = sdslen(s);
 sh = (char*)s-sdsHdrSize(oldtype);
 newlen = (len+addlen);
 if (newlen   SDS_MAX_PREALLOC)
 newlen *= 2;
 else
 newlen += SDS_MAX_PREALLOC;
 type = sdsReqType(newlen);
 /* Don t use type 5: the user is appending to the string and type 5 is
 * not able to remember empty space, so sdsMakeRoomFor() must be called
 * at every appending operation. */
 if (type == SDS_TYPE_5) type = SDS_TYPE_8;
 hdrlen = sdsHdrSize(type);
 if (oldtype==type) { newsh = s_realloc(sh, hdrlen+newlen+1);
 if (newsh == NULL) return NULL;
 s = (char*)newsh+hdrlen;
 } else {
 /* Since the header size changes, need to move the string forward,
 * and can t use realloc */
 newsh = s_malloc(hdrlen+newlen+1);
 if (newsh == NULL) return NULL;
 memcpy((char*)newsh+hdrlen, s, len+1);
 s_free(sh);
 s = (char*)newsh+hdrlen;
 s[-1] = type;
 sdssetlen(s, len);
 }
 sdssetalloc(s, newlen);
 return s;
}

sdscatlen 将 t 指向的长度为 len 的任意二进制数据追加到 sds 字符串 s 的后面。本文开头演示的 string 的 append 命令，内部就是调用 sdscatlen 来实现的。

在 sdscatlen 的实现中，先调用 sdsMakeRoomFor 来保证字符串 s 有足够的空间来追加长度为 len 的数据。sdsMakeRoomFor 可能会分配新的内存，也可能不会。

sdsMakeRoomFor 是 sds 实现中很重要的一个函数。关于它的实现代码，我们需要注意的是：

如果原来字符串中的空余空间够用（avail = addlen），那么它什么也不做，直接返回。

如果需要分配空间，它会比实际请求的要多分配一些，以防备接下来继续追加。它在字符串已经比较长的情况下要至少多分配 SDS_MAX_PREALLOC 个字节，这个常量在 sds.h 中定义为(1024*1024)=1MB。

按分配后的空间大小，可能需要更换 header 类型（原来 header 的 alloc 字段太短，表达不了增加后的容量）。

如果需要更换 header，那么整个字符串空间（包括 header）都需要重新分配（s_malloc），并拷贝原来的数据到新的位置。

如果不需要更换 header（原来的 header 够用），那么调用一个比较特殊的 s_realloc，试图在原来的地址上重新分配空间。s_realloc 的具体实现得看 Redis 编译的时候选用了哪个 allocator（在 Linux 上默认使用 jemalloc）。

但不管是哪个 realloc 的实现，它所表达的含义基本是相同的：它尽量在原来分配好的地址位置重新分配，如果原来的地址位置有足够的空余空间完成重新分配，那么它返回的新地址与传入的旧地址相同；否则，它分配新的地址块，并进行数据搬迁。参见
http://man.cx/realloc。

从 sdscatlen 的函数接口，我们可以看到一种使用模式：调用它的时候，传入一个旧的 sds 变量，然后它返回一个新的 sds 变量。由于它的内部实现可能会造成地址变化，因此调用者在调用完之后，原来旧的变量就失效了，而都应该用新返回的变量来替换。不仅仅是 sdscatlen 函数，sds 中的其它函数（比如 sdscpy、sdstrim、sdsjoin 等），还有 Redis 中其它一些能自动扩展内存的数据结构（如 ziplist），也都是同样的使用模式。

浅谈 sds 与 string 的关系

现在我们回过头来看看本文开头给出的 string 操作的例子。

append 操作使用 sds 的 sdscatlen 来实现。前面已经提到。

setbit 和 getrange 都是先根据 key 取到整个 sds 字符串，然后再从字符串选取或修改指定的部分。由于 sds 就是一个字符数组，所以对它的某一部分进行操作似乎都比较简单。

看完上述内容是否对您有帮助呢？如果还想对相关知识有进一步的了解或阅读更多相关文章，请关注丸趣 TV 行业资讯频道，感谢您对丸趣 TV 的支持。

正文完