1、SDS簡介

無論是 Redis 的 Key 還是 Value，其基礎(chǔ)數(shù)據(jù)類型都是字符串。例如，Hash 型 Value 的 field 與 value 的類型、List 型、Set 型、ZSet 型 Value 的元素的類型等都是字符串。雖然 Redis 是使用標準 C 語言開發(fā)的，但并沒有直接使用 C 語言中傳統(tǒng)的字符串表示，而是自定義了一 種字符串。這種字符串本身的結(jié)構(gòu)比較簡單，但功能卻非常強大，稱為簡單動態(tài)字符串， Simple Dynamic String，簡稱 SDS。

注意，Redis 中的所有字符串并不都是 SDS，也會出現(xiàn) C 字符串。C 字符串只會出現(xiàn)在字 符串“字面常量”中，并且該字符串不可能發(fā)生變更。 redisLog(REDIS_WARNNING, “sdfsfsafsafds”);

 2、SDS結(jié)構(gòu)

SDS 不同于 C 字符串。C 字符串本身是一個以雙引號括起來，以空字符’\0’結(jié)尾的字符序列。但SDS是一個結(jié)構(gòu)體，定義在Redis安裝目錄下的src/sds.h中。

struct sdshdr {
// 字節(jié)數(shù)組，用于保存字符串
char buf[];
// buf[]中已使用字節(jié)數(shù)量，稱為 SDS 的長度
int len;
// buf[]中尚未使用的字節(jié)數(shù)量
int free;
}

例如執(zhí)行 SET country “China”命令時，鍵 country 與值”China”都是 SDS 類型的，只不過 一個是 SDS 的變量，一個是 SDS 的字面常量。”China”在內(nèi)存中的結(jié)構(gòu)如下：

通過以上結(jié)構(gòu)可以看出，SDS 的 buf 值實際是一個 C 字符串，包含空字符’\0’共占 6 個字 節(jié)。但 SDS 的 len 是不包含空字符’\0’的。

該結(jié)構(gòu)與前面不同的是，這里有 3 字節(jié)未使用空間。

3、SDS的優(yōu)點

C 字符串使用 Len+1 長度的字符數(shù)組來表示實際長度為 Len 的字符串，字符數(shù)組最后以 空字符’\0’結(jié)尾，表示字符串結(jié)束。這種結(jié)構(gòu)簡單，但不能滿足 Redis 對字符串功能性、安全 性及高效性等的要求。

（1）、防止“字符串長度獲取”性能瓶頸

對于C字符串，若要獲取其長度，則必須要通過遍歷整個字符串才可以獲取到的。對于超常字符串的遍歷，會成為系統(tǒng)的性能瓶頸。

但是，由于SDS結(jié)構(gòu)體中直接就存放著字符串的長度數(shù)據(jù)，所以對于獲取字符串長度需要消耗的系統(tǒng)性能，與字符串本身長度是無關(guān)的，不會成為Redis的性能瓶頸。

（2）保障二進制安全

C 字符串中只能包含符合某種編碼格式的字符，例如 ASCII、UTF-8 等，并且除了字符串 末尾外，其它位置是不能包含空字符’\0’的，否則該字符串就會被程序誤解為提前結(jié)束。而 在圖片、音頻、視頻、壓縮文件、office 文件等二進制數(shù)據(jù)中以空字符’\0’作為分隔符的情況 是很常見的。故而在 C 字符串中是不能保存像圖片、音頻、視頻、壓縮文件、office 文件等 二進制數(shù)據(jù)的。 但 SDS 不是以空字符’\0’作為字符串結(jié)束標志的，其是通過 len 屬性來判斷字符串是否 結(jié)束的。所以，對于程序處理 SDS 中的字符串數(shù)據(jù)，無需對數(shù)據(jù)做任何限制、過濾、假設， 只需讀取即可。數(shù)據(jù)寫入的是什么，讀到的就是什么。

（3）、減少內(nèi)存再分配次數(shù)

SDS采用了空間預分配策略與惰性空間釋放策略來避免內(nèi)存再分配問題。

空間預分配策略是指，每次SDS進行空間擴展時，程序不但為其分配所需的空間，還會為其分配額外的未使用的空間，以減少內(nèi)存再分配次數(shù)。而額外分配的未使用空間大小取決于空間擴展后SDS的len屬性值。

如果 len 屬性值小于 1M，那么分配的未使用空間 free 的大小與 len 屬性值相同。

如果 len 屬性值大于等于 1M ，那么分配的未使用空間 free 的大小固定是 1M。

SDS對于空間釋放采用的是惰性空間釋放策略。該策略是指，SDS字符串長度如果縮短，那么多出的未使用空間將暫時不釋放，而是增加到free中。以使后期擴展SDS時減少內(nèi)存再分配次數(shù)。

如果要釋放 SDS 的未使用空間，則可通過 sdsRemoveFreeSpace()函數(shù)來釋放。

（4）兼容C函數(shù)

Redis 中提供了很多的 SDS 的 API，以方便用戶對 Redis 進行二次開發(fā)。為了能夠兼容 C 函數(shù)，SDS 的底層數(shù)組 buf[]中的字符串仍以空字符’\0’結(jié)尾。 現(xiàn)在要比較的雙方，一個是 SDS，一個是 C 字符串，此時可以通過 C 語言函數(shù) strcmp(sds_str->buf，c_str）

4、基本操作

數(shù)據(jù)結(jié)構(gòu)的基本操作不外乎增、刪、改、查，SDS也不例外。由于Redis 3.2后的SDS涉及多種類型，修改字符串內(nèi)容帶來的長度變化可能會影響SDS的類型而引發(fā)擴容。

4.1、創(chuàng)建字符串

Redis通過sdsnewlen函數(shù)創(chuàng)建SDS。在函數(shù)中會根據(jù)字符串長度選擇合適的類型，初始化完相應的統(tǒng)計值后，返回指向字符串內(nèi)容的指針，根據(jù)字符串長度選擇不同的類型：

    sds sdsnewlen(const void ＊init, size_t initlen) {
        void ＊sh;
        sds s;
        char type = sdsReqType(initlen); //根據(jù)字符串長度選擇不同的類型
        if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8; //SDS_TYPE_5強制轉(zhuǎn)化
            為SDS_TYPE_8
        int hdrlen = sdsHdrSize(type); //計算不同頭部所需的長度
        unsigned char ＊fp; /＊ 指向flags的指針 ＊/
        sh = s_malloc(hdrlen+initlen+1); //"+1"是為了結(jié)束符'\0'
        ...
        s = (char＊)sh+hdrlen; //s是指向buf的指針
        fp = ((unsigned char＊)s)-1; //s是柔性數(shù)組buf的指針，-1即指向flags
        ...
        s[initlen] = '\0'; //添加末尾的結(jié)束符
        return s;
    }

注意： Redis 3.2后的SDS結(jié)構(gòu)由1種增至5種，且對于sdshdr5類型，在創(chuàng)建空字符串時會強制轉(zhuǎn)換為sdshdr8。原因可能是創(chuàng)建空字符串后，其內(nèi)容可能會頻繁更新而引發(fā)擴容，故創(chuàng)建時直接創(chuàng)建為sdshdr8。

創(chuàng)建SDS的大致流程：首先計算好不同類型的頭部和初始長度，然后動態(tài)分配內(nèi)存。需要注意以下3點：

• 創(chuàng)建空字符串時，SDS_TYPE_5被強制轉(zhuǎn)換為SDS_TYPE_8。
• 長度計算時有“+1”操作，是為了算上結(jié)束符“\0”。
• 返回值是指向sds結(jié)構(gòu)buf字段的指針。

返回值sds的類型定義如下：

typedef char ＊sds;

從源碼中我們可以看到，其實s就是一個字符數(shù)組的指針，即結(jié)構(gòu)中的buf。這樣設計的好處在于直接對上層提供了字符串內(nèi)容指針，兼容了部分C函數(shù)，且通過偏移能迅速定位到SDS結(jié)構(gòu)體的各處成員變量。

4.2、釋放字符串

SDS提供了直接釋放內(nèi)存的方法——sdsfree，該方法通過對s的偏移，可定位到SDS結(jié)構(gòu)體的首部，然后調(diào)用s_free釋放內(nèi)存：

    void sdsfree(sds s) {
        if (s == NULL) return;
        s_free((char＊)s-sdsHdrSize(s[-1])); //此處直接釋放內(nèi)存
    }

為了優(yōu)化性能（減少申請內(nèi)存的開銷）, SDS提供了不直接釋放內(nèi)存，而是通過重置統(tǒng)計值達到清空目的的方法——sdsclear。該方法僅將SDS的len歸零，此處已存在的buf并沒有真正被清除，新的數(shù)據(jù)可以覆蓋寫，而不用重新申請內(nèi)存：

    void sdsclear(sds s) {
        sdssetlen(s, 0); //統(tǒng)計值len歸零
        s[0] = '\0'; //清空buf
    }

4.3、拼接字符串

拼接字符串操作本身不復雜，可用sdscatsds來實現(xiàn)，代碼如下：

    sds sdscatsds(sds s, const sds t) {
        return sdscatlen(s, t, sdslen(t));
    }

sdscatsds是暴露給上層的方法，其最終調(diào)用的是sdscatlen。由于其中可能涉及SDS的擴容，sdscatlen中調(diào)用sdsMakeRoomFor對帶拼接的字符串s容量做檢查，若無須擴容則直接返回s；若需要擴容，則返回擴容好的新字符串s。函數(shù)中的len、curlen等長度值是不含結(jié)束符的，而拼接時用memcpy將兩個字符串拼接在一起，指定了相關(guān)長度，故該過程保證了二進制安全。最后需要加上結(jié)束符。

    /＊ 將指針t的內(nèi)容和指針s的內(nèi)容拼接在一起，該操作是二進制安全的＊/
    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'; //加上結(jié)束符
        return s;
    }

下圖描述了sdsMakeRoomFor的實現(xiàn)過程。

Redis的sds中有如下擴容策略：

1）若sds中剩余空閑長度avail大于新增內(nèi)容的長度addlen，直接在柔性數(shù)組buf末尾追加即可，無須擴容。代碼如下：

    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; //s[-1]即flags
        int hdrlen;
        if (avail >= addlen) return s; //無須擴容，直接返回
        ...
    }

2）若sds中剩余空閑長度avail小于或等于新增內(nèi)容的長度addlen，則分情況討論：新增后總長度len+addlen<1MB的，按新長度的2倍擴容；新增后總長度len+addlen>1MB的，按新長度加上1MB擴容。代碼如下：

    sds sdsMakeRoomFor(sds s, size_t addlen)
    {
        ...
        newlen = (len+addlen);
        if (newlen < SDS_MAX_PREALLOC)// SDS_MAX_PREALLOC這個宏的值是1MB
            newlen ＊= 2;
        else
            newlen += SDS_MAX_PREALLOC;
        ...
    }

3）最后根據(jù)新長度重新選取存儲類型，并分配空間。此處若無須更改類型，通過realloc擴大柔性數(shù)組即可；否則需要重新開辟內(nèi)存，并將原字符串的buf內(nèi)容移動到新位置。具體代碼如下：

    sds sdsMakeRoomFor(sds s, size_t addlen)
    {
        ...
        type = sdsReqType(newlen);
        /＊ type5的結(jié)構(gòu)不支持擴容，所以這里需要強制轉(zhuǎn)成type8＊/
        if (type == SDS_TYPE_5) type = SDS_TYPE_8;
        hdrlen = sdsHdrSize(type);
        if (oldtype==type) {
        /＊無須更改類型，通過realloc擴大柔性數(shù)組即可，注意這里指向buf的指針s被更新了＊/
                    newsh = s_realloc(sh, hdrlen+newlen+1);
            if (newsh == NULL) return NULL;
            s = (char＊)newsh+hdrlen;
        } else {
            /＊ 擴容后數(shù)據(jù)類型和頭部長度發(fā)生了變化，此時不再進行realloc操作，而是直接重新開辟內(nèi)存，
              拼接完內(nèi)容后，釋放舊指針＊/
            newsh = s_malloc(hdrlen+newlen+1); //按新長度重新開辟內(nèi)存
            if (newsh == NULL) return NULL;
            memcpy((char＊)newsh+hdrlen, s, len+1); //將原buf內(nèi)容移動到新位置
            s_free(sh); //釋放舊指針
            s = (char＊)newsh+hdrlen; //偏移sds結(jié)構(gòu)的起始地址，得到字符串起始地址
            s[-1] = type; //為falgs賦值
            sdssetlen(s, len); //為len屬性賦值
        }
        sdssetalloc(s, newlen); //為alloc屬性賦值
        return s;
    }

4.4、其余API

下表列出了其他常用的API：

學習時把握以下兩點：

• SDS暴露給上層的是指向柔性數(shù)組buf的指針。
• 讀操作的復雜度多為O(1)，直接讀取成員變量；涉及修改的寫操作，則可能會觸發(fā)擴容。

到此這篇關(guān)于redis實現(xiàn)動態(tài)字符串SDS的文章就介紹到這了,更多相關(guān)redis 動態(tài)字符串SDS內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論