我們知道redis是用C語言開發(fā)的，源代碼開源（小伙伴們可以去網(wǎng)上下載下來進(jìn)行閱讀）今天我們主要看的是SDS(Simple dynamic string) ,它是redis字符串類型的底層實(shí)現(xiàn)。

1. 什么是SDS(源文件sds.h/sds.c)

看下源代碼的定義

typedef char *sds;

從此段代碼可以看出sds是char類型的指針。

我們知道C語言中的字符串是用char[]數(shù)組來表示的，并且數(shù)組的最后一個(gè)是以'\0'結(jié)尾的，那redis里面也保留了這部分的特性，但是redis的字符串是二進(jìn)制安全的，另外字符串的中間可以包含'\0' 字符，（C語言字符必須符合某種編碼 比如ASCII，并且除了字符串的末尾之外，字符串里面不能包含空字符），因?yàn)樵趕ds的頭部保存了字符串的長度，不再是根據(jù)'\0' 這個(gè)符號去判斷字符串是否結(jié)束。
注：二進(jìn)制安全簡單來說就是我們保存的數(shù)據(jù)，比如字符串,不會因?yàn)橐恍┎僮鞒霈F(xiàn)損壞,比如一個(gè)字符串中包含'\0'，那我們的C語言在讀取的時(shí)候就不會讀取'\0'后面的字符，因?yàn)樗谧x取字符串的時(shí)候當(dāng)它讀到''字符時(shí)認(rèn)為字符串已經(jīng)結(jié)束，比如：" hello'\0'world",那最終讀到的會是hello。

2.Redis中的幾種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種sds,這些其實(shí)是字符串的頭（header），真正的字符串是保存在buf中的，那為啥會有5中不同的類型呢？那是因?yàn)閞edis會根據(jù)字符串的長度使用不同的header頭，從而達(dá)到內(nèi)存優(yōu)化的目的,下面列舉下不同的使用場景：
a. 當(dāng)字符串的長度小于 2^5 且不為空的字符串的時(shí)候使用的是sdshdr5 ；
b. 當(dāng)字符串的長度大于等于2^5 小于 2^8 或者字符串為空的時(shí)候使用sdshdr8；
c. 當(dāng)字符串的長度大于等于2^8 小于 2^16時(shí)候使用sdshdr16；
d. 當(dāng)字符串的長度大于等于2^16 小于 2^32并且系統(tǒng)是64位的時(shí)候使用sdshdr32；
f. 其他的情況使用sdshdr64；
接下來我們具體看下sds header 頭里面的字段，我們發(fā)現(xiàn)除了sdshdr5外其他的類型結(jié)構(gòu)是一樣的，那下面我先來簡單介紹下除sdshdr5外的4中類型中的字段

1. len; //sds 字符串的實(shí)際長度.
2. alloc; //分配給字符串的總?cè)萘?，這個(gè)容量是不包含header和'\0'字符的容量，初始化的時(shí)候這個(gè)值和sds長度是一樣的，當(dāng)有修改的時(shí)候往往會分配大于實(shí)際需要用到的長度.
3. flags;// 類型的標(biāo)志，用一個(gè)字節(jié)的低3位保存，主要有 SDS_TYPE_5，SDS_TYPE_8，SDS_TYPE_16，SDS_TYPE_32，SDS_TYPE_64 這幾種類型，它們分別數(shù)字對應(yīng)0,1,2,3,4.
4. buf[];// 字符數(shù)組

那sdshdr5里面的字段又表示什么意思呢？再次貼上源代碼

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

我們發(fā)現(xiàn)它只有flags 和bufs[] 兩個(gè)字段，下面來分別解釋下

1. flags;// 低三位保存類型，高5位保存字符串的長度，也就是相比其他幾種類型sdshdr5把類型和字符串的長度保存在了一個(gè)字段。
2. char buf[] ; //這個(gè)和其他類型是一樣的，這里不再贅敘。
   注：大家不要被Note: sdshdr5 is never used 這句英文給誤導(dǎo)，其實(shí)sdshdr5 是有使用的。

下面我用一張圖來大致展示下sds的結(jié)構(gòu)

sds.png

3. SDS內(nèi)存分配和釋放

當(dāng)字符串發(fā)生修改時(shí)就需要給字符串分配或者釋放一些空間，我們先看下內(nèi)存的分配規(guī)則。

1. 初始的alloc的值和字符串的實(shí)際長度大小是一樣的。
2. 當(dāng)字符串發(fā)生修改的時(shí)候，比如追加字符，這個(gè)時(shí)候有三種情況：
   a. 當(dāng)alloc的空閑空間足夠時(shí)不進(jìn)行操作。
   b. alloc空閑空間不足時(shí)并且新的字符串的長度(newlen)小于1M的時(shí)候，redis會分配2倍新的字符串的長度(2*newlen)給alloc,等于說buf數(shù)組一般時(shí)空閑的。
   c. 當(dāng)新的字符串長度大于1M,那這個(gè)時(shí)候redis會分配newlen+1M的空間給alloc。
   以上具體的源代碼片段如下：

if (avail >= addlen) return s;

len = sdslen(s);
sh = (char*)s-sdsHdrSize(oldtype);
newlen = (len+addlen);
if (newlen < SDS_MAX_PREALLOC)
    newlen *= 2;
else
    newlen += SDS_MAX_PREALLOC;

我們再接著來看下內(nèi)存釋放的規(guī)則：
比如我們要去掉字符串中的某些字符串，這個(gè)時(shí)候多余的空間并沒有被釋放，redis只是將需要去掉的字符串去掉，修改下len的長度，而不會去修改alloc的長度大小，當(dāng)然與此同時(shí)redis還提供了釋放內(nèi)存的API,可以到真正需要釋放內(nèi)存的時(shí)候再釋放。
比如清空字符串函數(shù)：

void sdsclear(sds s) {
    sdssetlen(s, 0);
    s[0] = '\0';
}

這個(gè)函數(shù)并沒有去修改alloc的值，也就是它不會去釋放一些內(nèi)存。
我們知道redis是用C語言去實(shí)現(xiàn)的，接下來像大家簡單介紹下redis字符串(sds)和C字符串的區(qū)別。

4. SDS與C字符串的區(qū)別

1. C字符串沒有頭信息，不能直接獲取字符串的長度，獲取字符串的長度需要遍歷，時(shí)間復(fù)雜度為O(n)，sds字符串獲取字符串的長度為O(1),速度大大提升。
2. 內(nèi)存分配的方式不一樣，在C語言中它是每次追加或者縮短字符串都會發(fā)生內(nèi)存的分配和釋放，但是redis就不一樣，當(dāng)追加字符串時(shí)它會一次分配大于實(shí)際字符串的長度大小，當(dāng)下次還要追加的時(shí)候就不需要再次分配內(nèi)存了；當(dāng)縮短字符串的時(shí)候不會立馬釋放多余的空間，以防后面再此使用，還有一點(diǎn)就是C中的內(nèi)存分配和釋放都是手動操作的，如果忘記分配或者釋放的話會造成一定的后果，sds內(nèi)存的分配和釋放是自動的，不需要我們自己操作，減少了錯(cuò)誤發(fā)生。
3. 二進(jìn)制安全，redis可以存儲任何形式的字符串，包括二進(jìn)制，但是C對字符串有一定的要求，比如字符串中間不能包含'\0'（空）字符。
4. 還有一點(diǎn)就是sds字符串保留了一些C字符串的特性，比如字符串的末尾的字符是\0,這使得sds 字符串可以使用某些C字符串的API,從而避免的重復(fù)造輪子。
5. 有小伙伴看到這里可能會說怎么都是優(yōu)點(diǎn)訥，難道沒有缺點(diǎn)嗎？目前本人還未發(fā)現(xiàn)，如果要說缺點(diǎn)的話可能就是需要多維護(hù)一個(gè)sds header (頭)，需要一定的維護(hù)成本吧，當(dāng)然這個(gè)是我們r(jià)edis去做的，對用戶來說是透明的。

5. 常用的API

(1) sds sdsnew(const char *init);//創(chuàng)建一個(gè)包含給定C字符串的SDS
/* Create a new sds string starting from a null terminated C string. */
sds sdsnew(const char *init) {
    size_t initlen = (init == NULL) ? 0 : strlen(init);
    return sdsnewlen(init, initlen);
}

(2) sds sdsempty(void);//創(chuàng)建一個(gè)空的字符串
/* Create an empty (zero length) sds string. Even in this case the string
 * always has an implicit null term. */
sds sdsempty(void) {
    return sdsnewlen("",0);
}

(3) sds sdsdup(const sds s);// 創(chuàng)建sds副本
/* Duplicate an sds string. */
sds sdsdup(const sds s) {
    return sdsnewlen(s, sdslen(s));
}

(4) void sdsfree(sds s);//釋放給定的sds
/* 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]));
}
(5) sds sdsgrowzero(sds s, size_t len);//使用空字符將給定的sds擴(kuò)展至給定的長度
/* Grow the sds to have the specified length. Bytes that were not part of
 * the original length of the sds will be set to zero.
 *
 * if the specified length is smaller than the current length, no operation
 * is performed. */
sds sdsgrowzero(sds s, size_t len) {
    size_t curlen = sdslen(s);

    if (len <= curlen) return s;
    s = sdsMakeRoomFor(s,len-curlen);
    if (s == NULL) return NULL;

    /* Make sure added region doesn't contain garbage */
    memset(s+curlen,0,(len-curlen+1)); /* also set trailing \0 byte */
    sdssetlen(s, len);
    return s;
}

(6) sds sdscat(sds s, const char *t);//將指定的C字符串添加到sds 字符串s 的末尾
/* Append the specified null termianted C string to the 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 sdscat(sds s, const char *t) {
    return sdscatlen(s, t, strlen(t));
}

(7) sds sdscatsds(sds s, const sds t);//將一個(gè)sds添加到另外一個(gè)sds的末尾
/* Append the specified sds 't' to the existing sds 's'.
 *
 * After the call, the modified sds string is no longer valid and all the
 * references must be substituted with the new pointer returned by the call. */
sds sdscatsds(sds s, const sds t) {
    return sdscatlen(s, t, sdslen(t));
}
(8)sds sdscpy(sds s, const char *t);//將給定的C字符串復(fù)制到sds里面，覆蓋原來的sds 字符串

/* Like sdscpylen() but 't' must be a null-termined string so that the length
 * of the string is obtained with strlen(). */
sds sdscpy(sds s, const char *t) {
    return sdscpylen(s, t, strlen(t));
}

/* 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) {
    if (sdsalloc(s) < len) {
        s = sdsMakeRoomFor(s,len-sdslen(s));
        if (s == NULL) return NULL;
    }
    memcpy(s, t, len);
    s[len] = '\0';
    sdssetlen(s, len);
    return s;
}

暫時(shí)寫到這里，如有需要補(bǔ)充的地方，歡迎小伙伴在下面留言。