一文帶你快速搞懂動態字元串SDS，面試不再懵逼

2020 年 6 月 8 日
筆記
JAVA, Redis, redis源碼分析, SDS, String, 源碼分析

redis源碼分析系列文章

[Redis源碼系列]在Liunx安裝和常見API

為什麼要從Redis源碼分析

前言

上篇我們已經了解了Redis是什麼，在Linux上如何安裝，常見的數據類型和API使用，如果有不明白的，可以移步到主頁。

Redis是使用C寫的，而C中根本不存在string,list,hash，set和zset這些數據類型，那麼C是如何將這些數據類型實現出來的呢？我們從該篇開始，就要開始分析源碼啦😁。

API使用

我們這篇來學習string的底層實現，首先看下API的簡單應用，設置str1變數為helloworld，然後我們使用debug object +變數名的方式看下，注意標紅的編碼為embstr。

如果我們將str2設置為helloworldhelloworldhelloworldhelloworldhell，字元長度為44，再使用下debug object+變數名的方式看下，注意標紅的編碼為embstr。

但是當我們設置為helloworldhelloworldhelloworldhelloworldhello，字元長度為45，再使用debug object+變數名的方式看下，注意標紅的編碼為raw。

最後我們將str3設置為整數100，再使用debug object+變數名的方式看下，注意標紅的編碼為int。

所以Redis的string類型一共有三種存儲方式，當字元串長度小於等於44，底層採用embstr；當字元串長度大於44，底層採用raw；當設置是整數，底層則採用int。

embstr和raw的區別

所有類型的數據結構最外層都是RedisObject，這部分會說，先這樣大致了解下，因為這篇的重點不在這。如果字元串小於等於44，實際的數據和RedisObject在記憶體中地址相鄰，如下圖。

如果字元串大於44，實際的數據和RedisObject在記憶體中地址不相鄰，如下圖。

再次強調，這些不重要，以後會講，現在提下，只是為了能讓Redis的String類型有個大致了解，先從整體把握。我們今天要說的其實是實際的數據，即上圖指針指向的位置😄。

SDSHdr的定義

其實的數據並不是直接存儲，也有封裝，看下面的程式碼就知道分為五種，分別是sdshdr5，sdshdr8，sdshdr16，sdshdr32，sdshdr64。sdshdr5和另外四種的區別比較明顯，sdshrd5其實對記憶體空間的更加節約。其他四種乍一看都差不多，包括已用長度len，總長度alloc，標記flags（感覺沒啥用，要是有知道的小夥伴，歡迎指教），實際數據buf。

//定義五種不同的結構體，sdshdr5,sdshdr8, sdshdr16,sdshdr32,sdshdr64
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; // 8位的標記 
    char buf[];//實際數據的指針 
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* 已使用長度 */
    uint8_t alloc; /* 總長度*/
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; 
    uint16_t alloc; 
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len;
    uint32_t alloc;
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; 
    uint64_t alloc; 
    unsigned char flags; 
    char buf[];
};

SDS具體邏輯圖

假設我們設置某個字元串為hello，那麼他SDS的可用長度len為8，已用長度len為6，如下圖。注意：Redis會根據具體的字元長度，選擇相應的sdshdr，但是各個類型都差不多，所以下圖加簡單畫了。

SDS的優勢

我們可以看到是對字元數組的再封裝，但是為什麼呢，直接使用字元數組不是更簡單嗎？這要從C和Java語言的根本區別說起。

更快速的獲取字元串長度

我們都知道Java的字元串有提供length方法，列表有提供size方法，我們可以直接獲取大小。但是C卻不一樣，更偏向底層實現，所以沒有直接的方法使用。這樣就帶來一個問題，如果我們想要獲取某個數組的長度，就只能從頭開始遍歷，當遇到第一個’\0’則表示該數組結束。這樣的速度太慢了，不能每次因為要獲取長度就變數數組。所以設計了SDS數據結構，在原來的字元數組外面增加總長度，和已用長度，這樣每次直接獲取已用長度即可。複雜度為O(1)。

數據安全，不會截斷

如果傳統字元串保存圖片，影片等二進位文件，中間可能出現’\0’，如果按照原來的邏輯，會造成數據丟失。所以可以用已用長度來表示是否字元數組已結束。

SDS關鍵程式碼分析

獲取常見值（抽象出常見方法）

在sds.h中寫了一些常見方法，比如計算sds的長度（即sdshdr的len），計算sds的空閑長度（即sdshdr的可用長度alloc-已用長度len），計算sds的可用長度(即sdshdr的alloc)等等。但是大家有沒有疑問，這不是一行程式碼搞定的事嗎，為啥要抽象出方法呢？那麼問題在於在上面，我們有將sdshdr分為五種類型，分別是sdshdr5，sdshdr8，sdshdr16，sdshdr32，sdshdr64。那麼我們在實際使用的時候，想要區分當前是哪個類型，並取其相應欄位或設置相應欄位。

//計算sds對應的字元串長度，其實上取得是字元串所對應的哪種sdshdr的len值 
static inline size_t sdslen(const sds s) {
    // 柔性數組不佔空間，所以倒數第二位的是flags 
    unsigned char flags = s[-1];
    //flags與上面定義的宏變數7做位運算 
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5://0 
            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8://1
            return SDS_HDR(8,s)->len;//取上面結構體sdshdr8的len  
        case SDS_TYPE_16://2
            return SDS_HDR(16,s)->len;
        case SDS_TYPE_32://3
            return SDS_HDR(32,s)->len;
        case SDS_TYPE_64://5
            return SDS_HDR(64,s)->len;
    }
    return 0;
}

//計算sds對應的空餘長度，其實上是alloc-len 
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;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            return sh->alloc - sh->len;
        }
    }
    return 0;
}

//設置sdshdr的len 
static inline void sdssetlen(sds s, size_t newlen) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            {
                unsigned char *fp = ((unsigned char*)s)-1;
                *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
            }
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->len = newlen;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->len = newlen;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->len = newlen;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->len = newlen;
            break;
    }
}

//給sdshdr的len添加多少大小 
static inline void sdsinclen(sds s, size_t inc) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            {
                unsigned char *fp = ((unsigned char*)s)-1;
                unsigned char newlen = SDS_TYPE_5_LEN(flags)+inc;
                *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
            }
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->len += inc;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->len += inc;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->len += inc;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->len += inc;
            break;
    }
}

//獲取sdshdr的總長度 
static inline size_t sdsalloc(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8:
            return SDS_HDR(8,s)->alloc;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->alloc;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->alloc;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->alloc;
    }
    return 0;
}

//設置sdshdr的總長度 
static inline void sdssetalloc(sds s, size_t newlen) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            /* Nothing to do, this type has no total allocation info. */
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->alloc = newlen;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->alloc = newlen;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->alloc = newlen;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->alloc = newlen;
            break;
    }
}

創建對象

我們通過sdsnew方法來創建對象，顯示通過判斷init是否為空來確定初始大小，接著調用方法sdsnew（這邊方法名一樣，但是參數不一樣，其為方法的重載），先根據長度確定類型（上面有提過五種類型，不記得的可以往上翻），然後根據類型分配相應的記憶體資源，最後追加C語言的結尾符’\0’。

sds sdsnew(const char *init) {
    size_t initlen = (init == NULL) ? 0 : strlen(init);
    return sdsnewlen(init, initlen);
}


sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    char type = sdsReqType(initlen);//根據長度確定類型 
    /*空字元串，用sdshdr8，這邊是經驗寫法，當想構造空串是為了放入超過32長度的字元串 */
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    int hdrlen = sdsHdrSize(type);//到下一個方法，已經把他們放在一起了
    unsigned char *fp; /* flags pointer. */

    //分配記憶體 
    sh = s_malloc(hdrlen+initlen+1);
    if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    if (sh == NULL) return NULL;
    s = (char*)sh+hdrlen;
    fp = ((unsigned char*)s)-1;
    //根據不同的類型，創建不同結構體，調用SDS_HDR_VAR函數
    //為不同的結構體賦值,如已用長度len,總長度alloc 
    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);
    //最後追加'\0' 
    s[initlen] = '\0';
    return s;
}


//根據實際字元長度確定類型 
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;
#endif
    return SDS_TYPE_64;
}


刪除
String類型的刪除並不是直接回收記憶體，而是修改字元，讓其為空字元，這其實是惰性釋放，等待將來使用。在調用sdsempty方法時，再次調用上面的sdsnewlen方法。

/*修改sds字元串使其為空（零長度）。

*但是，所有現有緩衝區不會被丟棄，而是設置為可用空間

*這樣，下一個append操作將不需要分配到

*當要縮短SDS保存的字元串時，程式並不立即使用記憶體充分配來回收縮短後多出來的位元組，並等待將來使用。
void sdsclear(sds s) {
    sdssetlen(s, 0);
    s[0] = '\0';
}

sds sdsempty(void) {
    return sdsnewlen("",0);
}

添加字元（擴容）重點！！！

添加字元串，sdscat輸入參數為sds和字元串t，首先調用sdsMakeRoomFor擴容方法，再追加新的字元串，最後添加上結尾符’\0’。我們來看下擴容方法裡面是如何實現的？第一步先調用常見方法中的sdsavail方法，獲取還剩多少空閑空間。如果空閑空間大於要添加的字元串t的長度，則直接返回，不想要擴容。如果空閑空間不夠，則想要擴容。第二步判斷想要擴容多大，這邊有分情況，如果目前的字元串小於1M，則直接擴容雙倍，如果目前的字元串大於1M，則直接添加1M。第三個判斷添加字元串之後的數據類型還是否和原來的一致，如果一致，則沒啥事。如果不一致，則想要新建一個sdshdr，把現有的數據都挪過去。

這樣是不是有點抽象，舉個例子，現在str的字元串為hello，目前是sdshdr8，總長度50，已用6，空閑44。現在想要添加長度為50的字元t，第一步想要看下是否要擴容，50明顯大於44，需要擴容。第二步擴容多少，str的長度小於1M，所以擴容雙倍，新的長度為50*2=100。第三步50+50所對應sdshdr類型還是sdshdr8嗎？明顯還是sdshdr8，所以不要數據遷移，還在原來的基礎上添加t即可。

sds sdscat(sds s, const char *t) {
    return sdscatlen(s, t, strlen(t));
}

sds sdscatlen(sds s, const void *t, size_t len) {
    //調用sds.h裡面的sdslen，即取已用長度 
    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';
    return s;
}

sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    //調用sds.h，獲取空閑長度alloc 
    size_t avail = sdsavail(s);
    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;

   //空閑長度大於需要增加的，不需要擴容，直接返回 
    if (avail >= addlen) return s;

//調用sds.h裡面的sdslen，即取可用長度 
    len = sdslen(s);
    
    sh = (char*)s-sdsHdrSize(oldtype);
    //len加上要添加的大小 
    newlen = (len+addlen);
    
    //#define SDS_MAX_PREALLOC (1024*1024) 
    //當新長度小於 1024*1024，直接擴容兩倍 
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else //當新長度大於 1024*1024，加2014*1024 
        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);
    //如果類型一樣，直接使用原地址，長度加上就行 
    if (oldtype==type) {
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {//如果類型不一樣，重新開闢記憶體，把原來的數據複製過去 
        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;
}

//計算不同類型的結構體的大小 
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;
}

總結

該篇主要講了Redis的底層實現SDS，包括SDS是什麼，與傳統的C語言相比的優勢，具體的邏輯圖，常見的方法（包括創建，刪除，擴容等）。同時也知道了Redis的embstr和raw的區別。如果覺得寫得還行，麻煩給個贊👍，您的認可才是我寫作的動力！

如果覺得有說的不對的地方，歡迎評論指出。

好了，拜拜咯。

參考資料

【Redis源碼分析】一個對SDSHDR5是否使用的疑問

如何閱讀 Redis 源碼？

Tags: JAVA Redis redis源碼分析 SDS String 源碼分析