Redis 字串研究

Redis 在處理字串資料時，另外實現了一個名為 SDS （Simple Dynamic String）的資料結構。

前置知識

在 C 語言中，字串是由字元陣列構成，並在最後加入 \0（NULL Byte）作為結束標記，這種實作方式存在一些缺點

非 Binary Safe：對於一些 UTF-8 字串可能中間會夾雜 NULL Byte，此時就會被當字串結尾
- 在 CVE-2006-7234 中，因為 PHP 實作上的缺陷導致可以在插入 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 大小相同
- 只需要 realloc 多出來的記憶體空間即可
如果 oldtype 不等於新的 type，表示其 SDS Header 大小不同
- 需要重新建立一個 SDS，並把舊字串的內容複製過去
- 最後再清空原本的 SDS
最後更新 len 及 alloc

他山之石

alcover/stricks

純 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）時，以另外的編碼方式儲存，降低計算與儲存成本