前言

在官方對(duì)redis的介紹中我們可以看到醒目的一句話：
Redis is not a plain key-value store,it is actually a data structures server
redis訪問速度之所以那么快其一要?dú)w功于他是內(nèi)存型數(shù)據(jù)庫(kù)祝高。其二就要?dú)w功于它對(duì)數(shù)據(jù)存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)济欢，即上面這句所強(qiáng)調(diào)的他更加是數(shù)據(jù)結(jié)構(gòu)服務(wù)器。
關(guān)于redis數(shù)據(jù)結(jié)構(gòu)從使用者角度出發(fā)有:
1.string
2.list
3.hash
4.set
5.sorted set
這也是redis服務(wù)器提供的外部接口
從底層實(shí)現(xiàn)角度出發(fā)有:
1.sds
2.dict
3.skiptlist
4.quicklist
5.ziplist
其中 string類型只由單一的sds實(shí)現(xiàn)

SDS(Simple Dynamic String)

源碼位子:src/sds.c,src/sds.h
在sds.h中 提供了sdshdr5/8/16/32/64這幾種的sds的實(shí)現(xiàn)

/* 以SDS8為例*/
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* 已使用空間大小 */
    uint8_t alloc; /* 總共可用的字符空間大小甸各，應(yīng)該是實(shí)際buf的大小減1(因?yàn)閏字符串末尾必須是\0,不計(jì)算在內(nèi)) */
    unsigned char flags; /* 標(biāo)志位魏保，主要是識(shí)別這是sdshdr幾，目前只用了3位懈词，還有5位空余 */
    char buf[];   /* 真正存儲(chǔ)字符串的地方 */
};

其余大致相同通過(guò)flag來(lái)判斷是sds幾

為什么稱其為簡(jiǎn)單動(dòng)態(tài)字符串慎菲？

1.與C字符串的區(qū)別
C語(yǔ)言采用N+1的字符數(shù)組來(lái)表示字符串，且末尾置'\0'
相較于c原生的字符串课幕，sds多了len厦坛、alloc、flag三個(gè)字段來(lái)存儲(chǔ)一些額外的信息乍惊，redis考慮到了字符串拼接時(shí)帶來(lái)的巨大損耗粪般，所以每次新建sds的時(shí)候會(huì)預(yù)分配一些空間來(lái)應(yīng)對(duì)未來(lái)的增長(zhǎng)
因此C獲取字符串長(zhǎng)度的時(shí)間復(fù)雜度為O(n)，須全部遍歷污桦，SDS只需讀取計(jì)算len字段即可亩歹，且因?yàn)轭A(yù)分配了額外的空間杜絕了緩存溢出和減少了修改字符串時(shí)的內(nèi)存分配次數(shù)匙监，且sds是以len判斷字符串結(jié)尾中間是否出現(xiàn)'\0'與其無(wú)關(guān)，是二進(jìn)制安全的

為啥要設(shè)計(jì)多種sds
閱讀sds.c中的sdsnewlen方法(sds初始化從sdsnew進(jìn)入到sdsnewlen)

// sds在初始化時(shí)需要傳入長(zhǎng)度initlen
sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    //根據(jù)初始化長(zhǎng)度確定使用哪種sds
    char type = sdsReqType(initlen);
    //空字符串處理默認(rèn)類型sds8
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* sds->flag*/
    // redis 自己hock內(nèi)存分配
    sh = s_malloc(hdrlen+initlen+1);
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);
//注意這里返回的sh并不是直接指向sds的指針小作，而是指向sds中字符串的指針
// sds指針需要根據(jù)sh和hdrlen計(jì)算
    if (sh == NULL) return NULL;
    s = (char*)sh+hdrlen;
    fp = ((unsigned char*)s)-1;
//根據(jù)type類型分配內(nèi)存
    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);
//為方便使用C內(nèi)置字符串函數(shù)亭姥，末尾置'\0'
    s[initlen] = '\0';
    return s;
}

閱讀switch分支我們可以看到根據(jù)初始化長(zhǎng)度，小于3的使用sds5(這個(gè)基本不用)顾稀，小于2^8的長(zhǎng)度使用sds8达罗，以此類推，這樣子sds8的len和alloc只占用兩個(gè)字節(jié)静秆，比較短字符串可能非常多粮揉，所以節(jié)省下來(lái)的內(nèi)存還是非常可觀的（基本上是扣額外分配的內(nèi)存）
SDS空間不足要擴(kuò)容怎么辦
常見如字符串拼接抚笔，sds可能空間不足扶认。redis采用指數(shù)級(jí)擴(kuò)容方法

// 擴(kuò)大sds的實(shí)際可用空間，以便后續(xù)能拼接更多字符串殊橙。 
// 注意：這里實(shí)際不會(huì)改變sds的長(zhǎng)度辐宾，只是增加了更多可用的空間(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; // SDS_TYPE_MASK = 7 
    int hdrlen;

    /* 如果有足夠的剩余空間，直接返回 */
    if (avail >= addlen) return s;

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    // 在未超出SDS_MAX_PREALLOC前膨蛮，擴(kuò)容都是按2倍的方式擴(kuò)容叠纹，超出后只能遞增 
    if (newlen < SDS_MAX_PREALLOC)  // SDS_MAX_PREALLOC = 1024*1024
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;

    type = sdsReqType(newlen);

    /*  在真正使用過(guò)程中不會(huì)用到type5，如果遇到type5直接使用type8*/
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    hdrlen = sdsHdrSize(type);
    if (oldtype==type) {
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        // 擴(kuò)容其實(shí)就是申請(qǐng)新的空間敞葛，然后把舊數(shù)據(jù)挪過(guò)去  
        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;
}

對(duì)于SDS_MAX_PREALLOC的宏定義為

#define SDS_MAX_PREALLOC (1024*1024)

在SDS_MAX_PREALLOC范圍內(nèi)以指數(shù)2倍對(duì)buf擴(kuò)容誉察，超出則每次加SDS_MAX_PREALLOC

總結(jié)

sds（簡(jiǎn)單動(dòng)態(tài)字符串）特點(diǎn)，預(yù)先分配內(nèi)存惹谐，記錄字符串長(zhǎng)度持偏，在原字符串?dāng)?shù)組里新增加一串字符串。

新長(zhǎng)度newlen為原len+addlen豺鼻，若newlen小于1M，則為SDS分配新的內(nèi)存大小為2*newlen款慨；若newlen大于等于1M儒飒，則SDS分配新的內(nèi)存大小為newlen + 1M

SDS是以len字段來(lái)判斷是否到達(dá)字符串末尾，而不是以'\0'判斷結(jié)尾檩奠。所以sds存儲(chǔ)的字符串中間可以出現(xiàn)'\0'桩了，即sds字符串是二進(jìn)制安全的。

當(dāng)要清空一個(gè)SDS時(shí)埠戳，并不真正釋放其內(nèi)存井誉，而是設(shè)置len字段為0即可，這樣當(dāng)之后再次使用到該SDS時(shí)整胃，可避免重新分配內(nèi)存颗圣，從而提高效率。

SDS的好處就是通過(guò)預(yù)分配內(nèi)存和維護(hù)字符串長(zhǎng)度，實(shí)現(xiàn)動(dòng)態(tài)字符串在岂。

試試回答以下問題

1.為啥redis要自己封裝一個(gè)string類型
2.什么是動(dòng)態(tài)簡(jiǎn)單
3.如何兼容C字符串

參考

1.redis源碼刨析之SDS
2.如何閱讀redis源碼
3.升入理解redis之簡(jiǎn)單動(dòng)態(tài)字符串