Redis之SDS數據結構的使用

Posted on by

序言

Redis的幾種基本數據結構有字符串（String）、哈希（Hash）、列表（List）、集合（Set）、有序集合（Sorted Set），這些是最常見的，也能在官網上查看到。

官網鏈接：Redis 教程_redis教程

字符串

前面也提到過字符串是設計瞭簡單動態字符串SDS（Simple Dynamic String）結構來表示字符串。這種數據結構可以提升字符串的操作效率，並可以保存二進制數據。

先思考一個問題：

Redis是用C語言實現的，那麼為什麼沒有復用C語言的字符串實現方法，而選用瞭SDS呢？

char*字符串數組

C語言實現字符串使用的是char*字符串數組，它是一塊連續的內存空間，一次存放瞭字符串的每一個字符，並且最後一個字符是“\0”，用來標識字符串的結尾位置，如下圖，

連續的內存空間的所有字符串沒有分隔符計算機就沒辦法區分字符串與字符串之間的位置。在C語言標準庫中字符串的操作函數就會通過檢查字符串數組中是否有“\0”來判斷字符串是否結束。例如字符串操作函數strlen函數，它就是在遍歷字符串數組中的每一個字符，並進行計數，直到檢查到“\0”，它的時間復雜度是O(n)。流程如下，

簡單動態字符串SDS

SDS的數據結構裡包含：字符串實際長度，字符串分配空間長度，SDS類型，字符數組，其中字符數組buf[]用來保存實際數據，如下圖，

再來看看類似的字符操作函數sdslen函數的源碼（在sds.h文件中），直接根據SDS類型返回對應的字符串現有長度，避免瞭對字符串的遍歷，時間復雜度變成瞭O(1)，當然也會付出一點代價增加瞭空間復雜度。這都是設計人員讓數據操作更加高效。源碼如下，

static inline size_t sdslen(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)->len;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->len;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->len;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->len;
    }
    return 0;
}

再來看一下字符串的拷貝源碼，操作都使用瞭字符串的現有長度，拷貝後進行更新。

sds sdscpylen(sds s, const char *t, size_t len) {
    // 判斷字符串數組分配的空間長度是不是小於字符串數組當前長度
    if (sdsalloc(s) < len) {
        // 根據要追加的長度len-sdslen(s)和現有長度，判斷是否增加新的空間
        s = sdsMakeRoomFor(s,len-sdslen(s));
        if (s == NULL) return NULL;
    }
    // 將源字符串t中len長度的數據拷貝到目標字符串結尾
    memcpy(s, t, len);
    // 拷貝完後，在目標字符串結尾加上\0
    s[len] = '\0';
    // 設置字符串數組最新當前長度
    sdssetlen(s, len);
    return s;
}

SDS把目標字符串的空間檢查和擴容封裝在瞭sdsMakeRoomFor函數中，追加、打印、復制等操作都會調用該函數。可以看到該函數根據sds的信息進行動態擴容，源碼如下，

sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    // 獲取sds可用空間
    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長度
    len = sdslen(s);
    // sds指針
    sh = (char*)s-sdsHdrSize(oldtype);
    // 新字符串長度
    newlen = (len+addlen);
    // 如果新長度小於最大預分配長度，則進行兩倍擴容
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;
    type = sdsReqType(newlen);
    // SDS類型5轉換為類型8
    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 {
        /* 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;
}

 可以看到sdsMakeRoomFor函數中sdshdr5類型不再使用直接轉換成瞭sdshdr8類型，它們是SDS設計的5種類型，分別表示sdshdr5、sdshdr8、sdshdr16、sdshdr32和sdshdr64，下面就看一下這幾種類型的結構源碼，如下圖，

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

sdshdr5已不再使用，所以在函數中做瞭處理，把sdshdr5類型轉換為sdshdr8類型。前面也提到過SDS是緊湊型字符串數據結構，以sdshdr8為例，它是用的是uint8_t即8位無符號整型，會占用1字節的內存空間。SDS之所以設計不同的結構是為瞭能靈活保存不同大小的字符串，從而有效節省內存空間。

另外，__attribute__ ((__packed__))標志可以告訴編譯器在編譯以上數據結構時，不實用字節對齊的方式（不滿8字節的整數倍，則會自動補齊），而是采用緊湊的方式分配內存。

到此這篇關於Redis之SDS數據結構的使用的文章就介紹到這瞭,更多相關Redis SDS數據結構內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：