Redis的字符串是如何實現(xiàn)的

更新時間：2021年10月22日 08:33:11 作者：神技圈子

本文主要介紹了Redis的字符串是如何實現(xiàn)的，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下

前言

字符串在日常開發(fā)中應(yīng)用得比較普遍，對于Redis來說，鍵值對中的鍵是字符串，值也是字符串。比如在Redis中寫入一條客戶信息記錄姓名、性別、愛好等。

在這里插入圖片描述

在Redis這種內(nèi)存數(shù)據(jù)庫中，由于字符串被廣泛的應(yīng)用，在設(shè)計字符串時基于以下幾點來設(shè)計：
1.支持豐富高效的字符串操作，比如追加、拷貝、比較等操作
2.能保存二進制數(shù)據(jù)
3.能盡可能的節(jié)省內(nèi)存開銷

可能會有人問了，既然C語言庫提供了char*這樣的字符數(shù)組來字符串操作。比如strcmp,strcat。感覺完全可以考慮直接使用C庫提供的啊。C庫字符串運用是很普遍，但是也不是沒有問題的。它需要頻繁的創(chuàng)建和檢查空間，這在實際項目中其實很花時間的。所以，Redis設(shè)計了簡單字符串（SDS，Simple Data )來表示字符串。同原來的C語言相比提升了字符串的操作效率，而且還支持二進制格式。下面我們就來介紹下Redis的字符串是如何實現(xiàn)的。

為什么不用char*

先來看看char*字符數(shù)組的結(jié)構(gòu)，其實很簡單就是開辟一塊連續(xù)的內(nèi)存空間來依次存放每一個字符，最后一個字符是"\0"表示字符串結(jié)束。C庫中的字符串操作函數(shù)就是通過檢查"\0"來判斷字符串結(jié)束。比如strlen函數(shù)就是遍歷字符數(shù)組中的每一個字符并計數(shù)，直到遇到"\0"結(jié)束計數(shù)，然后返回計數(shù)結(jié)果。下面我們通過一個代碼來看看"\0"結(jié)束字符對字符串長度的影響。

在這里插入圖片描述

這段代碼的執(zhí)行結(jié)果如下：

在這里插入圖片描述

表示a1的字符長度是2個字符。這是因為在he后面有了"\0"，所以字符串以"\0"表示結(jié)束，這就會產(chǎn)生一個問題，如果字符串內(nèi)部本身就有"\0",那么數(shù)據(jù)就會被"\0"截斷，而這就不能保存任意二進制數(shù)據(jù)了。

傳統(tǒng)設(shè)計操作復(fù)雜度高

除了上面提到的不能保存任意二進制數(shù)據(jù)以外，操作復(fù)雜度也挺大。比如C語言中用得比較普遍的strlen函數(shù)，它要遍歷字符數(shù)組中的每一個字符才能得到字符串長度。所以，時間復(fù)雜度是O(n)。另外再說一個常用函數(shù)strcat，它同strlen函數(shù)一樣先遍歷字符串才能得到目標(biāo)字符串的末尾，而且它把源字符串追加到目標(biāo)字符串末尾的時，還得確認(rèn)目標(biāo)字符串是否具有足夠的空間。所以在調(diào)用的時候，開發(fā)人員還要人為保證目標(biāo)字符串有足夠的可用空間，不然就需要動態(tài)地申請空間。這樣不僅時間復(fù)雜度高，操作復(fù)雜度也高了。

SDS的設(shè)計

Redis在設(shè)計的時候還是盡量保證復(fù)用C標(biāo)準(zhǔn)的字符串操作函數(shù)的。Redis在保留了使用字符數(shù)組來保存實際數(shù)據(jù)基礎(chǔ)上，專門設(shè)計了一種SDS數(shù)據(jù)結(jié)構(gòu)。
首先，SDS結(jié)構(gòu)里面包含了一個字符數(shù)組buf[],同時SDS結(jié)構(gòu)里面還包含了三個元數(shù)據(jù)。分別是字符數(shù)組現(xiàn)有長度len，分配給字符數(shù)組的空間長度alloc以及SDS類型flags。其中l(wèi)en和alloc這兩個元數(shù)據(jù)定義了不同類型的SDS。SDS定義代碼如下所示：

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

用個圖來表示一下

在這里插入圖片描述

代碼中定義了一個別名

typedef char *sds;

所以SDS本質(zhì)還是字符數(shù)組，只是在字符數(shù)組基礎(chǔ)上增加了額外的元數(shù)據(jù)，Redis在使用字符數(shù)組時直接使用sds這個別名。

SDS的高效操作

創(chuàng)建sds

Redis調(diào)用sdsnewlen函數(shù)創(chuàng)建sds。我們以sedsnewlen舉例，代碼如下：

hisds sdsnewlen(const void *init, size_t initlen) {
   //指向SDS結(jié)構(gòu)的指針
    void *sh;
    //sds類型變量,就是char*的別名
    sds s;
    //根據(jù)大小獲取SDS的類型
    char type = hi_sdsReqType(initlen);
    /* Empty strings are usually created in order to append. Use type 8
     * since type 5 is not good at this. */
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */

     //為新創(chuàng)建的sds結(jié)構(gòu)分配內(nèi)存
    sh = s_malloc(hdrlen+initlen+1);
    if (sh == NULL) return NULL;
    if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    
    //指向SDS結(jié)構(gòu)體中的buf數(shù)組,sh指向SDS結(jié)構(gòu)的起始位置，hdrlen表示元數(shù)據(jù)的長度    
    s = (char*)sh+hdrlen;
    fp = ((unsigned char*)s)-1;
    //根據(jù)類型初始化len,alloc
    switch(type) {
        case SDS_TYPE_5: {
            *fp = type | (initlen << HI_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)
    //將字符串拷貝給sds變量s
        memcpy(s, init, initlen);
     //字符串變量末尾添加"\0"表示字符串結(jié)束  
    s[initlen] = '\0';
    return s;
}

該函數(shù)主要執(zhí)行過程如下：
1.根據(jù)初始化長度獲取SDS類型。如果初始化長度initlen為0，一般被認(rèn)為是要執(zhí)行append操作，設(shè)置SDS類型為SDS_TYPE_8
2.為新創(chuàng)建的SDS結(jié)構(gòu)分配內(nèi)存，內(nèi)存空間為元數(shù)據(jù)長度+buf長度+字符串最后的結(jié)束符"\0"。
3.根據(jù)SDS類型去初始化元數(shù)據(jù)len和alloc
4.將字符串拷貝給sds

字符數(shù)組拼接

由于sds結(jié)構(gòu)中記錄了占用的空間和被分配的空間，所以它比傳統(tǒng)C語言的字符串效率更高。下面我們通過Redis的字符串追加函數(shù)sdscatlen來看一看。代碼如下：

sds sdscatlen(sds s, const void *t, size_t len) {
//獲取目標(biāo)字符串的長度 
 size_t curlen = sdslen(s);
//根據(jù)追加長度和目標(biāo)字符串長度判斷是否需要增加新的空間
  s = sdsMakeRoomFor(s,len);
  if (s == NULL) return NULL;
  //將源字符串t中l(wèi)en長度的數(shù)據(jù)拷貝到目標(biāo)字符串尾部
  memcpy(s+curlen, t, len);
  //設(shè)置目標(biāo)字符串的最新長度
  sdssetlen(s, curlen+len);
  //拷貝完成后，在字符串結(jié)尾加上"\0"
  s[curlen+len] = '\0';
  return s;
}

這個函數(shù)有三個參數(shù)分別是目標(biāo)字符串s,源字符串t和要追加的長度len。這個代碼執(zhí)行過程如下：
1.首先獲取目標(biāo)字符串的長度，然后調(diào)用sdsMakeRoomFor函數(shù)判斷是否要給目標(biāo)字符串添加新的空間，這樣就可以保證目標(biāo)字符串有足夠的空間追加字符串
2.在保證了有足夠空間可以追加字符串后，將源字符串中指定長度len的數(shù)據(jù)追加到目標(biāo)字符串
3.設(shè)置目標(biāo)字符串的最新長度

長度獲取

代碼中，函數(shù)sdslen記錄了字符數(shù)組的使用長度，不用同C庫一樣遍歷字符串了，這樣可以大大降低了操作使用字符串的開銷。該函數(shù)的代碼如下所示：

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

這樣時間復(fù)雜度直接降到了O(1)。這個函數(shù)有一個騷操作，通過s[-1]獲取到flags，然后調(diào)用SDS_HDR宏函數(shù)。我們來看下這個宏函數(shù)定義

#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))

其中##用來將兩個token連接為一個token，所以加上參數(shù)將在預(yù)編譯階段將被替換如下

SDS_HDR(8,s);
((struct sdshdr8 *)((s)-(sizeof(struct sdshdr8))))

字符數(shù)組地址減去結(jié)構(gòu)體的大小，就能獲取到結(jié)構(gòu)體的首地址，然后直接訪問len屬性。

預(yù)分配內(nèi)存空間

此外，在代碼中還使用了sdsMakeRoomFor函數(shù)，它在拼接字符串之前會檢查是否需要擴容，如果需要擴容則會預(yù)分配空間。這一設(shè)計的好處就是避免了開發(fā)中忘記給目標(biāo)字符串?dāng)U容而導(dǎo)致操作失敗。比如strcpy(char* dst, const char* dst),如果src長度大于了dst的長度，又沒有做檢查就會遭成內(nèi)存溢出。代碼如下所示：

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;
    size_t usable;

    //空余空間足夠，無需擴展
    if (avail >= addlen) return s;

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    assert(newlen > len);   /* Catch size_t overflow */
    //如果新的字符數(shù)組長度小于SDS_MAX_PREALLOC
    //分配2倍所需長度
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    //否則分配新長度加上SDS_MAX_PREALLOC的長度
    else
        newlen += SDS_MAX_PREALLOC;
   
   //重新獲取SDS類型
    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);
    assert(hdrlen + newlen + 1 > len);  /* Catch size_t overflow */
    if (oldtype==type) {
        newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        / /如果頭部大小發(fā)生變化只需要將字符數(shù)組向前移，不使用realloc
        newsh = s_malloc_usable(hdrlen+newlen+1, &usable);
        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);
    }
    usable = usable-hdrlen-1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
     //更新SDS容量  
    sdssetalloc(s, usable);
    return s;
}

其中SDS_MAX_PREALLOC的長度為1024*1024

#define SDS_MAX_PREALLOC (1024*1024)

節(jié)省內(nèi)存的設(shè)計

前面講SDS結(jié)構(gòu)的時候提到過它有一個元數(shù)據(jù)flag，表示字符串類型。SDS一共有5中類型，它們分別是sdshdr5,sdshdr8,sdshdr16,sdshdr32和sdshdr64。這五種的主要區(qū)別是它們字符數(shù)組的現(xiàn)有長度len和分配空間alloc的不同。
那么我們就以sdshdr16為例，它的定義如下

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

我們可以看到現(xiàn)有長度len和已分配空間alloc都是uint16_t類型，uint16_t是16位無符號整型，會占用2個字節(jié)。當(dāng)字符串類型是sdshdr16的時候它包含的字符數(shù)組長度最大為2^16-1字節(jié)。而對于其它三種sdshdr8,sdshdr32和sdshdr64，以此類推它們的類型就分別是uin8_t，uin32_t和uint64_t，len和alloc這兩個元數(shù)據(jù)占用的空間分別是1字節(jié)、4字節(jié)和8字節(jié)。
實際上，設(shè)計不同的結(jié)構(gòu)頭的目的是為了靈活保存不同大小的字符串，從而有效地節(jié)省內(nèi)存空間。在保存不同大小的字符串時，結(jié)構(gòu)頭占用的內(nèi)存空間也不一樣，這樣一來保存小字符串時，占用的空間也會比較小。
除了設(shè)計不同類型的結(jié)構(gòu)頭以外，Redis還使用編譯優(yōu)化來節(jié)省內(nèi)存空間。比如上面sdshdr16的代碼中就有__attribute__ ((packed))，它的目的是告訴編譯器采用緊湊的方式分配內(nèi)存，默認(rèn)情況下編譯器會按照16字節(jié)的對齊方式給變量分配內(nèi)存。也就是說一個變量沒有到16個字節(jié)，編譯器也會給它分配16個字節(jié)。
我們來舉個例子

#include <string.h>
#include <iostream>

using namespace std;

typedef struct MyStruct
{
 char  a;
 int b;   
} MyStruct;


int
main()
{
    cout << sizeof(MyStruct) << endl;
    
    return 0;
}

雖然char占用1個字節(jié)，int占用4個字節(jié)，但是打印出來是8，這樣多出來的3個字節(jié)白白浪費掉了?，F(xiàn)在我們運用__attribute__ ((packed))屬性定義結(jié)構(gòu)體，就可以實際占用多少字節(jié)，編譯器就分配多少空間。我們把剛才代碼修改一下加上這個屬性。代碼如下

#include <string.h>
#include <iostream>

using namespace std;

typedef struct MyStruct
{
 char  a;
 int b;   
} __attribute__ ((__packed__))MyStruct;


int
main()
{
    cout << sizeof(MyStruct) << endl;
    
    return 0;
}

運行這段代碼，結(jié)果就變?yōu)?了，表示編譯器用了緊湊型的內(nèi)存分配。在開發(fā)過程中，為了節(jié)省內(nèi)存開銷就可以考慮把__attribute__ ((packed))這個屬性運用起來。

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

您可能感興趣的文章: