0%

redisString

字符串对象

字符串对象的编码方式有int、embstr和raw。

int

使用int编码要求对象是一个整数值,而且可以使用long类型表示

raw

raw编码使用的是sds(simple dynamic string, 简单动态字符串)保存,其数据结构如下:

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
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 {
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[];
};

共有5种sdshdr结构,其中sdshdr5并没有使用。

len

len中存储的是buf中的字符串长度。

buf

buf中存储的是字符串的值,与C中的字符串一样,最后都会又一个额外的字符\0作为结尾。不同的是C中没有存储字符串的长度信息,所以在读取字符串时读到\0便终止,sds中则是直接读取len长度的字符串,所以sds是二进制安全的。

PS:len中不包括\0的长度

alloc

alloc表示的是buf总分配的总长度。出现这个字段是因为redis中的字符串有时会经常进行修改,如果每次都分配len+1的长度,就意味着要经常进行内存分配,所以redis中会对内存空间进行预分配,每次分配alloc的长度。

  • 预分配规则:
    • set的时候不预留空间,alloc=len。总分配hdrlen+alloc+1大小的空间,hdrlen指的是对应sdshdr结构体的大小
    • 其余修改(如append)的时候,先计算已分配未使用的空间大小avail(alloc-len),如果avail够的话,直接添加到buf中,修改len为newlen(二者长度之和)。否则新分配一块(hdrlen+newlen*2+1)大小的内存,alloc改为newlen*2;当newlen>1024*1024(1M)时,每次多分配1M,而非newlen*2

PS:之前的redis版本存的是free,相当于alloc - len。而没有存alloc。

flags

flags表示的是该sds指向的是上述五种sdshdr的哪一种,取值为0-4。

sds

初始化字符串为itlay.top的时候,其结构如下:

redisString

从上图可以看到,ptr指向的是buf位置。实际上在给出sdshdr结构体时,就定义了一个sds指针typedef char *sds,redis中对sdshdr的操作全是通过该指针完成。在创建sdshdr结构后,返回就是指向buf的sds指针,然后将其赋值给ptr

  • 指针指向的是buf字段,如何获取该字符串的len和alloc呢?

    在申明sdshdr时,都使用了__attribute__ ((__packed__)),表示该结构体使用1字节对齐。所以,能使用sds[-1]获取到flags的值,然后获取到对应结构体的大小以获取该结构体头部的指针。以下为获取sds长度的代码,获取alloc的代码类似。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* 根据类型和buf的位置确定sdshdr的位置 */
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))

static inline size_t sdslen(const sds s) {
unsigned char flags = s[-1];
/* SDS_TYPE_MASK=7,因为flags只使用了3位*/
switch(flags&SDS_TYPE_MASK) {
case SDS_TYPE_5:
/* sdshdr5的长度存在flags的前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;
}

接下来看下几个主要函数的代码

创建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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
sds _sdsnewlen(const void *init, size_t initlen, int trymalloc) {
void *sh;
sds s;
/* sdsReqType 获取需要使用的sdshdr类型*/
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;
/* sdsHdrSize 获取该类型的结构体大小*/
int hdrlen = sdsHdrSize(type);
unsigned char *fp; /* flags pointer. */
size_t usable;

assert(initlen + hdrlen + 1 > initlen); /* Catch size_t overflow */
/* s_trymalloc_usable:返回分配的结果或者空
* s_malloc_usable:返回分配的结果或者异常
* 申请分配的大小为 结构体大小 + 字符串大小 + '\0', usable为实际分配的值*/
sh = trymalloc?
s_trymalloc_usable(hdrlen+initlen+1, &usable) :
s_malloc_usable(hdrlen+initlen+1, &usable);
if (sh == NULL) return NULL;
if (init==SDS_NOINIT)
init = NULL;
else if (!init)
memset(sh, 0, hdrlen+initlen+1);
s = (char*)sh+hdrlen;
fp = ((unsigned char*)s)-1;
/* 获取alloc,若大于该类型的最大值,则设其为该类型最大值 */
usable = usable-hdrlen-1;
if (usable > sdsTypeMaxSize(type))
usable = sdsTypeMaxSize(type);
switch(type) {
case SDS_TYPE_5: {
*fp = type | (initlen << SDS_TYPE_BITS);
break;
}
case SDS_TYPE_8: {
/* 根据s获取指向该结构体头部的指针sh*/
SDS_HDR_VAR(8,s);
sh->len = initlen;
sh->alloc = usable;
*fp = type;
break;
}
case SDS_TYPE_16: {
SDS_HDR_VAR(16,s);
sh->len = initlen;
sh->alloc = usable;
*fp = type;
break;
}
case SDS_TYPE_32: {
SDS_HDR_VAR(32,s);
sh->len = initlen;
sh->alloc = usable;
*fp = type;
break;
}
case SDS_TYPE_64: {
SDS_HDR_VAR(64,s);
sh->len = initlen;
sh->alloc = usable;
*fp = type;
break;
}
}
if (initlen && init)
memcpy(s, init, initlen);
/* 将最后一位设为\0 */
s[initlen] = '\0';
return 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
#define SDS_MAX_PREALLOC (1024*1024)

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;
size_t usable;

/* Return ASAP if there is enough space left. */
if (avail >= addlen) return s;

len = sdslen(s);
sh = (char*)s-sdsHdrSize(oldtype);
newlen = (len+addlen);
assert(newlen > len); /* Catch size_t overflow */
/* SDS_MAX_PREALLOC为1024*1024 */
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;
/* 获取新长度的sdshdr类型 */
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);
assert(hdrlen + newlen + 1 > len); /* Catch size_t overflow */
/* 同样申请hdrlen+newlen+1大小的空间,但根据类型是否更改进行不同操作*/
if (oldtype==type) {
newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
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_usable(hdrlen+newlen+1, &usable);
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);
}
usable = usable-hdrlen-1;
if (usable > sdsTypeMaxSize(type))
usable = sdsTypeMaxSize(type);
sdssetalloc(s, usable);
return s;
}

embstr

当字符串长度小于等于44字节时,使用的是embstr编码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
redis> set a aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
OK

redis> strlen a
(integer) 44

redis> object encoding a
"embstr"

redis> set a aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
OK

redis> strlen a
(integer) 45

redis> object encoding a
"raw"

embstr编码的字符串对象,在内存分配的时候会直接分配一整块连续空间,依次包含redisObject和sdshdr。这样内存分配和释放的时候都只需一次,而且对象和数据放在同一内存能更好的访问。

其对象创建代码如下:

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
robj *createEmbeddedStringObject(const char *ptr, size_t len) {
/* 一次性分配对象和数据的空间 */
robj *o = zmalloc(sizeof(robj)+sizeof(struct sdshdr8)+len+1);
/* 获取sdshdr8的首地址 */
struct sdshdr8 *sh = (void*)(o+1);
/* 设置对象的字段 */
o->type = OBJ_STRING;
o->encoding = OBJ_ENCODING_EMBSTR;
/* 指向的是buf字段 */
o->ptr = sh+1;
o->refcount = 1;
if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
} else {
o->lru = LRU_CLOCK();
}
/* 设置sdshdr8的字段 */
sh->len = len;
sh->alloc = len;
sh->flags = SDS_TYPE_8;
if (ptr == SDS_NOINIT)
sh->buf[len] = '\0';
else if (ptr) {
memcpy(sh->buf,ptr,len);
sh->buf[len] = '\0';
} else {
memset(sh->buf,0,len+1);
}
return o;
}
  • 为啥是44字节?

    因为redis使用jemalloc分配内存,可以以8、16、32、64等字节为单位分配内存。在embstr中使用的都是sdshdr8,包含3个固定字节(uint8_t*2+char = 1*2 + 1),而redisObject占16字节,再加上最后一个\0,于是64-16-3-1 = 44。

redis中没有对embstr编写任何的修改方法,所以embstr是只读的,对其进行修改会将编码方式改为raw。

补充一些sds的函数

最后有一个问题:

为啥sds指向的是buf?

目前看到的稍微靠谱的解答:为了更好的使用C语言中字符串的特性,所以直接指向字符串