0%

【Redis数据结构】SDS的实现

Redis没有直接使用C语言传统的字符串表示, 而是自己撸了一种名为简单动态字符串(Simple Dynamic String, SDS)的抽象类型作为 Redis 的默认字符串表示。

SDS的特点有

  • 空间预分配, 可动态扩展
    • 对sds修改后, 大小1MB, newlen*=2, 大于1MB, 每次加1MB的可用空间
  • 惰性空间释放
    • 只修改sds长度大小和末尾’\0’, 并不真正释放内存
  • 常数时间内获取字符串长度
    • 直接从sdshdr中获取长度, 不需要遍历
  • 不以 ‘\0’ 结尾, 通过长度来判断是否到达字符串末尾
  • 二进制安全, 能存储任意二进制数据
  • 无缓冲区溢出
  • 兼容部分C语言字符串函数
  • 最多可存储 512MB 数据

SDS数据结构定义

SDS由两部分组成:sds、sdshdr。

sds 是 char * 的别名

sdshdr是sds的头部, 为sds加上一个头部的好处就是为了提高某些地方的效率, 比如获取buf数组中字符串长度, 用 O(1) 的复杂度从头部就能取得.

sds 一共有5种类型的 sdshdr, 除了 sdshdr5 之外,其它4个 sdshdr 的结构都包含 len, alloc, flags, char buf[] 4个字段:

  • len: 字符串的真正长度 (不含结尾的 NULL )
  • alloc: 字符串的最大容量 (不含 heaher 的长度和结尾的 NULL ), 3.0及以前的版本用的是 free 表示剩余可用长度
  • flags: 总是占用一个字节。 其中的低3位用来表示 header 的类型
  • char buf[] 是一个没有指明长度的字符数组,这是C语言中定义字符数组的一种特殊写法,称为柔性数组(flexible array member),只能定义在一个结构体的最后一个字段上。 它在这里只是起到一个标记的作用,表示在 flags 字段后面就是一个字符数组

搞出这么多header类型主要是为了节省 保存字符串长度所花费的空间, 对于一个长度为10的字符串, 使用 uint8_t 保存 len 和 alloc, 比使用 uint64_t 能省14字节, 假如有 100w 个这样的字符串, 就省了 1400w 字节 ≈ 13.3MB 的内存

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
typedef char *sds;

/* Note: sdshdr5 is never used, we just access the flags byte directly.
* However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
// 低3位表示header类型, 高5位表示字符串长度
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[];
};

Header 类型宏定义:

1
2
3
4
5
#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

解析header有关的宏定义:

1
2
3
4
5
#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)

## 会将两个字符串连接起来, 如: T为8,则 sdshdr##Tsdshdr8

SDS_HDR_VAR(T,s) 根据T和s, 定义指针sh, 并初始化指向实际 sds 头部的地址 (sdshdr结构体的起始地址)

SDS_HDR(T,s) 返回一个指向实际 sds 的起始地址的指针

SDS_HDRSDS_HDR_VAR 的区别在于 SDS_HDR 只计算sds的 header 的指针,SDS_HDR_VAR 计算后将指针指向一个变量sh

常用的一些API函数

  • sdsnew(const char *init): 创建一个包含给定C字符串的sds
    • return sdsnewlen(init, initlen);
  • sdsempty(void): 创建一个空的sds
    • return sdsnewlen("",0);
  • sdslen(const sds s): 获取sds字符串长度
    • 根据 flags (s的指针-1) 获取type
    • 使用 SDS_HDR(T,s) 获取 sdsheader 结构体的指针, SDS_HDR(T,s)->len 就是s的长度
  • sdssetlen(sds s, size_t newlen): 设置sds字符串的长度
    • SDS_HDR(T,s)->len 设置为 newlen
  • sdsinclen(sds s, size_t inc): 添加sds字符串的长度
    • SDS_HDR(T,s)->len += inc
  • sdsavail(const sds s): 获取sds字符串的可用长度
    • 可用长度就是 alloc - len
  • sdsalloc(const sds s): 获取sds字符串的最大容量
    • 返回 SDS_HDR(T,s)->alloc;
    • 与sdsavail和sdslen的关系: sdsalloc() = sdsavail() + sdslen()
  • sdssetalloc(sds s, size_t newlen): 设置sds字符串的最大容量
    • SDS_HDR(T,s)->alloc = newlen;
  • sdsdup(const sds s) 创建一个sds的内存副本(copy)
    • return sdsnewlen(s, sdslen(s));
  • sdsclear(sds s): 清空sds
    • 只是将sds长度设置为0, 然后将 s[0] 设置为 ‘\0’ (惰性释放)
    • sdssetlen(s, 0);
  • sdscat(sds s, const char *t): 将C字符串t 追加到sds字符串后面
    • return sdscatlen(s, t, sdslen(t));
  • sdscatsds(sds s, const sds t): 将sds字符串 t 追加到 s 后面
    • return sdscatlen(s, t, sdslen(t));
  • sdscpy(sds s, const char *t): 将给定的c字符串复制到 sds 里面, 覆盖 sds 原有的字符串
    • return sdscpylen(s, t, strlen(t));
  • sdsrange(sds s, ssize_t start, ssize_t end): 只保留索引在 [start, end] 的字符串, 干掉其他的
    • startend 都可以是负数, 负数被转化为len+start/end
    • 相当于是 sds 的切片操作, 直接在原字符串上切片
  • sdstrim(sds s, const char *cset): 对 sds 左右两端进行修剪,清除其中 cset 指定的所有字符
    • 只修剪两端, 不修剪中间, 如s和cset分别为”xxabxybayy”,”xy”, 则修剪后的字符串为”abxyba”
  • int sdscmp(const sds s1, const sds s2)
    • 判断2个sds s1 和 s2是否相同
    • 相同返回0, 不同返回1

SDS的一些基础函数

创建一个新的sds (sdsnewlen)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/* Create a new sds string with the content specified by the 'init' pointer and 'initlen'.
* If NULL is used for 'init' the string is initialized with zero bytes.
* If SDS_NOINIT is used, the buffer is left uninitialized;
*
* The string is always null-termined (all the sds strings are, always) so
* even if you create an sds string with:
*
* mystring = sdsnewlen("abc",3);
*
* You can print the string with printf() as there is an implicit \0 at the
* end of the string. However the string is binary safe and can contain
* \0 characters in the middle, as the length is stored in the sds header. */
sds sdsnewlen(const void *init, size_t initlen) {
void *sh;
sds s;

// 根据字符串长度获取字符串的 SDS_TYPE
char type = sdsReqType(initlen);

// 创建空字符串一般是用来追加字符串, 不使用 SDS_TYPE_5, 改为使用 SDS_TYPE_8
// SDS_TYPE_5 类型的sds字符串不适合用来追加数据(很容易引发内存重新分配)
if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;

// 获取header所需要的内存大小
int hdrlen = sdsHdrSize(type);
unsigned char *fp; /* flags pointer. */

// 给sh分配sds内存空间, 空间为 头部长度 + 字符串长度 + 1, sh 为头部首地址
sh = s_malloc(hdrlen+initlen+1);

// SDS_NOINIT表示不初始化, init为NULL直接将sds全部设置为0
if (init==SDS_NOINIT)
init = NULL;
else if (!init)
memset(sh, 0, hdrlen+initlen+1);

// 分配内存失败, 返回NULL
if (sh == NULL) return NULL;

// s的首地址为sdshdr的首地址 + sdshdr的长度
s = (char*)sh+hdrlen;

// 字符串s的首地址-1,即为 flags 字段的指针
fp = ((unsigned char*)s)-1;

// 根据 type 类型初始化sds头部的 len, alloc, flags 字段
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;
}
}

// 拷贝 init 到 s 并将字符串的最后一位设置为`\0`
if (initlen && init)
memcpy(s, init, initlen);
s[initlen] = '\0';

// 返回的是字符串s, 不返回sds头部
return s;
}

释放sds(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]));
}

追加sds(sdscatlen)

追加有2个重要函数 sdscatlen 和 sdsMakeRoomFor

sdsMakeRoomFor 函数保证字符串s有足够的空间来追加长度为len的数据, alloc长度不够保存新的字符串就申请更大的的内存

sdscatlen函数将t追加到s后面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/* Append the specified binary-safe string pointed by 't' of 'len' bytes to the
* end of the specified sds string 's'.
*
* After the call, the passed sds string is no longer valid and all the
* references must be substituted with the new pointer returned by the call. */
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;
}

/* Enlarge the free space at the end of the sds string so that the caller
* is sure that after calling this function can overwrite up to addlen
* bytes after the end of the string, plus one more byte for nul term.
*
* Note: this does not change the *length* of the sds string as returned
* by sdslen(), but only the free buffer space we have. */
sds sdsMakeRoomFor(sds s, size_t addlen) {
void *sh, *newsh;

// 获取目前可用的空间长度 (alloc - len)
size_t avail = sdsavail(s);

size_t len, newlen;
char type, oldtype = s[-1] & SDS_TYPE_MASK;
int hdrlen;

// s 目前的空余空间已经足够,无须再进行扩展,直接返回 s
if (avail >= addlen) return s;

len = sdslen(s);
sh = (char*)s-sdsHdrSize(oldtype);
newlen = (len+addlen);

// 根据新的 sds 长度,为 s 分配新空间所需的大小
// 如果新的长度小于SDS_MAX_PREALLOC (1MB), 新的长度翻倍
// 新的长度>= 1MB, 新的长度 + 1MB
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;

// 获取新的sdshdr的type
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) {
// sdshdr 类型没变, 调用 s_realloc 试图在原来的地址上重新分配空间
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 */

// sdshdr 的类型变了, 调用 s_malloc 分配新的内存空间
newsh = s_malloc(hdrlen+newlen+1);

if (newsh == NULL) return NULL;

// 将s拷贝到新得内存上
memcpy((char*)newsh+hdrlen, s, len+1);

// 释放掉旧的 sdshdr
s_free(sh);

// 新s的地址为新的sdshdr首地 +sdshdr的长度
s = (char*)newsh+hdrlen;

// 设置新的type
s[-1] = type;

// 设置新的字符串长度
sdssetlen(s, len);
}

// 将 s 的 alloc 设置为 newlen
sdssetalloc(s, newlen);

// 返回s的地址
return s;
}

覆盖sds

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* Destructively modify the sds string 's' to hold the specified binary
* safe string pointed by 't' of length 'len' bytes. */
sds sdscpylen(sds s, const char *t, size_t len) {
// 如果s的最大容量比t的长度小, 需要调用 sdsMakeRoomFor 重新分配内存空间
if (sdsalloc(s) < len) {
s = sdsMakeRoomFor(s,len-sdslen(s));
if (s == NULL) return NULL;
}
// 将t拷贝到s上, 设置新的长度和末尾的\0
memcpy(s, t, len);
s[len] = '\0';
sdssetlen(s, len);
return s;
}

sds的切片

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/* Turn the string into a smaller (or equal) string containing only the
* substring specified by the 'start' and 'end' indexes.
*
* start and end can be negative, where -1 means the last character of the
* string, -2 the penultimate character, and so forth.
*
* The interval is inclusive, so the start and end characters will be part
* of the resulting string.
*
* The string is modified in-place.
*
* Example:
*
* s = sdsnew("Hello World");
* sdsrange(s,1,-1); => "ello World"
*/

void sdsrange(sds s, ssize_t start, ssize_t end) {
size_t newlen, len = sdslen(s);

if (len == 0) return;
// start 或者 end 是负数的话, 先转化为正数
if (start < 0) {
start = len+start;
if (start < 0) start = 0;
}
if (end < 0) {
end = len+end;
if (end < 0) end = 0;
}

// 设置新的字符串长度, start 比 end大的情况将字符串长度设置为0,不判错
newlen = (start > end) ? 0 : (end-start)+1;

if (newlen != 0) {
if (start >= (ssize_t)len) {
// start比sds长度还大, newlen设置为0
newlen = 0;
} else if (end >= (ssize_t)len) {
// end比sds长度大, end 改为 newlen - 1
end = len-1;
newlen = (start > end) ? 0 : (end-start)+1;
}
} else {
start = 0;
}

// 内存拷贝

if (start && newlen) memmove(s, s+start, newlen);

// 设置新的sds长度以及末尾的0
s[newlen] = 0;
sdssetlen(s,newlen);
}

memmove与memcpy区别:

当内存发生局部重叠的时候,memmove保证拷贝的结果是正确的, memcpy不保证拷贝的结果的正确

sds比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int sdscmp(const sds s1, const sds s2) {
size_t l1, l2, minlen;
int cmp;

l1 = sdslen(s1);
l2 = sdslen(s2);
minlen = (l1 < l2) ? l1 : l2;
cmp = memcmp(s1,s2,minlen);

// memcpy比较较小长度的值, 前minlen个字符相等,但是长度不相等, 返回s1的长度-s2的长度
// s1比s2长说明s1比s2大
if (cmp == 0) return l1-l2;

return cmp;
}

memcmp (const void s1, const void s2, size_t n):

  • s1 > s2 返回正数
  • s1 < s2 返回负数
  • s1 = s2 返回0

修剪sds两端的字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
sds sdstrim(sds s, const char *cset) {
char *start, *end, *sp, *ep;
size_t len;
// 开始指针与结束指针
sp = start = s;
ep = end = s+sdslen(s)-1;

// 修剪左右两端中在cset中的字符, 如果字符在cset中,指针往前或者后移动
while(sp <= end && strchr(cset, *sp)) sp++;
while(ep > sp && strchr(cset, *ep)) ep--;

// 都在cset里面, sds长度设置为0
len = (sp > ep) ? 0 : ((ep-sp)+1);

// 左边被修剪了,将sp拷贝到左边的s的起始地址
if (s != sp) memmove(s, sp, len);
s[len] = '\0';
sdssetlen(s,len);
return s;
}

char *strchr(const char *str, int c): 判断 字符c 是不是在 字符串str 中, 在的话返回地址, 不在返回null

char *strstr(char* str, const char* s): 判断 字符串s 是不是在 字符串str 中, 在的话返回首地址, 不在返回null

参考: