Redis 在處理字串資料時,另外實現了一個名為 SDS (Simple Dynamic String)的資料結構。
前置知識
在 C 語言中,字串是由字元陣列構成,並在最後加入 \0
(NULL Byte)作為結束標記,這種實作方式存在一些缺點
- 非 Binary Safe:對於一些 UTF-8 字串可能中間會夾雜 NULL Byte,此時就會被當字串結尾
- 長度計算為 $O(n)$:在計算字串長度時,需要走訪字元陣列並找到
\0
- 實際上,標準函式庫的
strlen()
在計算字串長度時會利用資料對齊的特性所以執行效率會略高於每個字元比對 - 在比較現代的 CPU 上,還可以利用一些較為現代的指令集去加速比對
SDS
在 Redis 中,為了保證 Binary Safe 及效率問題,其核心實作了 SDS,定義於 sds.h
中
1
2
3
4
5
6
7
8
9
10
11
| struct __attribute__((__packed__)) sdshdr5 {
unsigned char flags;
char buf[];
}
struct __attribute__((__packed__)) sdshdr8 {
uint8_t len;
uint8_t alloc;
unsigned char flags;
char buf[];
}
|
- 另有
sdshdr16
, sdshdr32
, sdshdr64
分別使用 uint16_t
, uint32_t
及 uint64_t
作為 len
及 alloc
的資料型態
len 及 alloc
len
為有效字串長度,這使得 SDS 能夠在 $O(1)$ 複雜度下取得字串長度
alloc
表示記憶體分配時所申請的大小,即整個 SDS 的總大小。alloc - len
即為可使用的空閒空間。
flags
3 LSB(最小的 3 位元)代表型態,表示它是 sdshdr5
, sdshdr8
, sdshdr16
, sdshdr32
或 sdshdr64
在 sdshdr5
中,剩下的 5 MSB(最大的 5 位元)代表長度。因此, sdshdr5
僅能存放 32 bytes($2^5$)長度的字串;在其餘的型態中,剩下的 5 MSB 沒有作用。
沿革
在 2009 年 5 月初時 Redis 的 First Commit 中:
1
2
3
4
5
| struct sdshdr {
long len;
long free;
char buf[0];
}
|
到 2009 年 5 月底時以 Flexible Array Member 改寫 buf
1
2
3
4
5
| struct sdshdr {
long len;
long free;
char buf[];
}
|
直到 Redis 3.2 RC1(2015 年 12 月)才成為當前的型式。
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
| typedef char *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. */
assert(initlen + hdrlen + 1 > initlen); /* Catch size_t overflow */
sh = s_malloc(hdrlen+initlen+1);
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;
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;
}
|
確認 type
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 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 (LONG_MAX == LLONG_MAX)
if (string_size < 1ll<<32)
return SDS_TYPE_32;
return SDS_TYPE_64;
#else
return SDS_TYPE_32;
#endif
}
char type = sdsReqType(initlen);
if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
|
若長度為 0
,表示之後可能會加資料進去,此時就不會使用 SDS_TYPE_5
而應該用 SDS_TYPE_8
。
申請記憶體空間
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #define SDS_TYPE_MASK 7
static inline int sdsHdrSize(char type) {
switch(type&SDS_TYPE_MASK) {
case SDS_TYPE_5:
return sizeof(struct sdshdr5);
case SDS_TYPE_8:
return sizeof(struct sdshdr8);
case SDS_TYPE_16:
return sizeof(struct sdshdr16);
case SDS_TYPE_32:
return sizeof(struct sdshdr32);
case SDS_TYPE_64:
return sizeof(struct sdshdr64);
}
return 0;
}
void *sh;
sh = s_malloc(hdrlen+initlen+1);
if (sh == NULL) return NULL;
|
- 因為不同種類的 SDS 會有不同大小,所以用
sdsHdrSize
預先取得要申請的記憶體空間大小。type&SDS_TYPE_MASK
表示只有 3 LSB 是代表 SDS Header Type
s_malloc
是一個串接 zmalloc
的 macro,而 zmalloc
則是 Redis 包裝記憶體管理機制的實作zmalloc
會依序使用 tcmalloc
, jemalloc
或 ptmalloc
- 總共的記憶體
hdrlen
:給 struct sdshdr
的空間initlen
:因為 buf
是一個 Flexible Array Member,所以其後需要加上額外的大小(字串長度)1
:用於存放 NULL Byte
賦值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
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;
}
// ...
}
|
s
會指向字串的開頭sh
是整個結構的起始,加上 hdrlen
就是結構長度,所以 s
指向 struct sdshdr
的 buf
空間
fp
會指向 struct sdshdr
中的 flag
- 利用
((unsigned char*)s)-1
取得 flag
的位址,因為前面的大小不固定所以依賴 s
的位址去取得 flag
的位址
SDS_TYPE_5 的賦值
因為 SDS_TYPE_5
沒有 len
及 alloc
,其資訊都儲存在 flag
中
|-----------------|-------------------- buf ---------------------------|
| flags: 01011000 | h | e | l | l | o | ' ' | w | o | r | l | d | '\0' |
|-----------------|----------------------------------------------------|
^
01011 代表長度(11)
000 代表類型(SDS_TYPE_5 = 0)
擴充容量
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
| sds sdsMakeRoomFor(sds s, size_t addlen) {
void *sh, *newsh;
size_t avail = sdsavail(s);
size_t len, newlen, reqlen;
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);
reqlen = newlen = (len+addlen);
assert(newlen > len); /* Catch size_t overflow */
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);
assert(hdrlen + newlen + 1 > reqlen); /* Catch size_t overflow */
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;
}
|
取得可用空間
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| static inline size_t sdsavail(const sds s) {
unsigned char flags = s[-1];
switch(flags&SDS_TYPE_MASK) {
case SDS_TYPE_5: {
return 0;
}
case SDS_TYPE_8: {
SDS_HDR_VAR(8,s);
return sh->alloc - sh->len;
}
// ...
}
return 0;
}
size_t avail = sdsavail(s);
if (avail >= addlen) return s;
|
SDS_TYPE_5
是固定空間的字串,不會有可用空間- 其它會用已分配的空間
alloc
減去字串長度 len
- 如果剩餘空間還夠,表示不需要擴充容量則直接回傳
決定新的 type
1
2
3
4
5
6
7
8
9
10
11
| #define SDS_MAX_PREALLOC 1024*1024
reqlen = newlen = (len+addlen);
assert(newlen > len); /* Catch size_t overflow */
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;
type = sdsReqType(newlen);
if (type == SDS_TYPE_5) type = SDS_TYPE_8;
|
為了避免每次擴充容量都要做 memcpy
的成本,預設會分配較多的空間。
- 如果
newlen
小於 2**20
(1 MB),就分配 2 倍的 newlen
的空間 - 如果
newlen
大於等於 1 MB,就分配 newlen + 1MB
的空間
新的 type
將會根據 newlen
的長度計算。
- 如果
newlen
算出來的 type
是 sdshdr5
就改成 sdshdr8
,因為 sdshdr5
不能被擴容
建立新的 SDS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| hdrlen = sdsHdrSize(type);
assert(hdrlen + newlen + 1 > reqlen); /* Catch size_t overflow */
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);
}
|
- 根據新的
type
取得新的 hdrlen
- 如果
oldtype
等於新的 type
,表示其 SDS Header 大小相同 - 如果
oldtype
不等於新的 type
,表示其 SDS Header 大小不同- 需要重新建立一個 SDS,並把舊字串的內容複製過去
- 最後再清空原本的 SDS
- 最後更新
len
及 alloc
他山之石
純 C 語言實作,程式碼較 SDS 來得簡潔。
其原理與 SDS 類似,但因為減少一些判斷與分支導致其效率略高於 SDS,算是很不錯的參考典範。
Rust 與 Golang 中的字串
基於 Rust 中的 RawVector,在實作的思想上與 SDS 相差不遠,只不過會用一個 UniquePtr 去指向資料所在空間,這會產生比較多的記憶體碎片。
註:Rust 的記憶體分配器實作視平台而定,預設 binary 會使用 jemalloc 而 dynamic 及 static library 使用 system 預設。
Golang 字串基於 byte slice,這個與 Rust 的實作思想差不多。
註:Golang 的記憶體分配器預設是使用 golang 版本的 tcmalloc 實作
結論
在大部份情況下,Binary Safe 字串的實作幾乎都大同小異,只不過在一些極端情況下會用各種方法優化實作(例如 SDS 分成多種不同的 type)。
遺珠之憾
在本篇中仍有許多細節沒能完整說明:
- SDS 結構的編碼
- 在字串長度小於 44 bytes 時,與記憶體的對齊
- 在字串為整數(long)時,以另外的編碼方式儲存,降低計算與儲存成本