Redis的字符串是如何實(shí)現(xiàn)的
字符串在日常開發(fā)中應(yīng)用得比較普遍，對于Redis來說，鍵值對中的鍵是字符串，值也是字符串。比如在Redis中寫入一條客戶信息記錄姓名、性別、愛好等。
在Redis這種內(nèi)存數(shù)據(jù)庫中，由于字符串被廣泛的應(yīng)用，在設(shè)計(jì)字符串時(shí)基于以下幾點(diǎn)來設(shè)計(jì)：
1.支持豐富高效的字符串操作，比如追加、拷貝、比較等操作
2.能保存二進(jìn)制數(shù)據(jù)
3.能盡可能的節(jié)省內(nèi)存開銷
可能會有人問了，既然C語言庫提供了char*這樣的字符數(shù)組來字符串操作。比如strcmp,strcat。感覺完全可以考慮直接使用C庫提供的啊。C庫字符串運(yùn)用是很普遍，但是也不是沒有問題的。它需要頻繁的創(chuàng)建和檢查空間，這在實(shí)際項(xiàng)目中其實(shí)很花時(shí)間的。所以，Redis設(shè)計(jì)了簡單字符串（SDS，Simple Data )來表示字符串。同原來的C語言相比提升了字符串的操作效率，而且還支持二進(jìn)制格式。下面我們就來介紹下Redis的字符串是如何實(shí)現(xiàn)的。
為什么不用char*
先來看看char*字符數(shù)組的結(jié)構(gòu)，其實(shí)很簡單就是開辟一塊連續(xù)的內(nèi)存空間來依次存放每一個(gè)字符，最后一個(gè)字符是"\0"表示字符串結(jié)束。C庫中的字符串操作函數(shù)就是通過檢查"\0"來判斷字符串結(jié)束。比如strlen函數(shù)就是遍歷字符數(shù)組中的每一個(gè)字符并計(jì)數(shù)，直到遇到"\0"結(jié)束計(jì)數(shù)，然后返回計(jì)數(shù)結(jié)果。下面我們通過一個(gè)代碼來看看"\0"結(jié)束字符對字符串長度的影響。
這段代碼的執(zhí)行結(jié)果如下：
表示a1的字符長度是2個(gè)字符。這是因?yàn)樵趆e后面有了"\0"，所以字符串以"\0"表示結(jié)束，這就會產(chǎn)生一個(gè)問題，如果字符串內(nèi)部本身就有"\0",那么數(shù)據(jù)就會被"\0"截?cái)啵@就不能保存任意二進(jìn)制數(shù)據(jù)了。
傳統(tǒng)設(shè)計(jì)操作復(fù)雜度高
除了上面提到的不能保存任意二進(jìn)制數(shù)據(jù)以外，操作復(fù)雜度也挺大。比如C語言中用得比較普遍的strlen函數(shù)，它要遍歷字符數(shù)組中的每一個(gè)字符才能得到字符串長度。所以，時(shí)間復(fù)雜度是O(n)。另外再說一個(gè)常用函數(shù)strcat，它同strlen函數(shù)一樣先遍歷字符串才能得到目標(biāo)字符串的末尾，而且它把源字符串追加到目標(biāo)字符串末尾的時(shí)，還得確認(rèn)目標(biāo)字符串是否具有足夠的空間。所以在調(diào)用的時(shí)候，開發(fā)人員還要人為保證目標(biāo)字符串有足夠的可用空間，不然就需要動態(tài)地申請空間。這樣不僅時(shí)間復(fù)雜度高，操作復(fù)雜度也高了。
SDS的設(shè)計(jì)
Redis在設(shè)計(jì)的時(shí)候還是盡量保證復(fù)用C標(biāo)準(zhǔn)的字符串操作函數(shù)的。Redis在保留了使用字符數(shù)組來保存實(shí)際數(shù)據(jù)基礎(chǔ)上，專門設(shè)計(jì)了一種SDS數(shù)據(jù)結(jié)構(gòu)。
首先，SDS結(jié)構(gòu)里面包含了一個(gè)字符數(shù)組buf[],同時(shí)SDS結(jié)構(gòu)里面還包含了三個(gè)元數(shù)據(jù)。分別是字符數(shù)組現(xiàn)有長度len，分配給字符數(shù)組的空間長度alloc以及SDS類型flags。其中l(wèi)en和alloc這兩個(gè)元數(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[];
};
用個(gè)圖來表示一下
代碼中定義了一個(gè)別名
typedef char *sds;
所以SDS本質(zhì)還是字符數(shù)組，只是在字符數(shù)組基礎(chǔ)上增加了額外的元數(shù)據(jù)，Redis在使用字符數(shù)組時(shí)直接使用sds這個(gè)別名。
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;
}
這個(gè)函數(shù)有三個(gè)參數(shù)分別是目標(biāo)字符串s,源字符串t和要追加的長度len。這個(gè)代碼執(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;
}
這樣時(shí)間復(fù)雜度直接降到了O(1)。這個(gè)函數(shù)有一個(gè)騷操作，通過s[-1]獲取到flags，然后調(diào)用SDS_HDR宏函數(shù)。我們來看下這個(gè)宏函數(shù)定義
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
其中##用來將兩個(gè)token連接為一個(gè)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ù)，它在拼接字符串之前會檢查是否需要擴(kuò)容，如果需要擴(kuò)容則會預(yù)分配空間。這一設(shè)計(jì)的好處就是避免了開發(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;
//空余空間足夠，無需擴(kuò)展
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è)計(jì)
前面講SDS結(jié)構(gòu)的時(shí)候提到過它有一個(gè)元數(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個(gè)字節(jié)。當(dāng)字符串類型是sdshdr16的時(shí)候它包含的字符數(shù)組長度最大為2^16-1字節(jié)。而對于其它三種sdshdr8,sdshdr32和sdshdr64，以此類推它們的類型就分別是uin8_t，uin32_t和uint64_t，len和alloc這兩個(gè)元數(shù)據(jù)占用的空間分別是1字節(jié)、4字節(jié)和8字節(jié)。
實(shí)際上，設(shè)計(jì)不同的結(jié)構(gòu)頭的目的是為了靈活保存不同大小的字符串，從而有效地節(jié)省內(nèi)存空間。在保存不同大小的字符串時(shí)，結(jié)構(gòu)頭占用的內(nèi)存空間也不一樣，這樣一來保存小字符串時(shí)，占用的空間也會比較小。
除了設(shè)計(jì)不同類型的結(jié)構(gòu)頭以外，Redis還使用編譯優(yōu)化來節(jié)省內(nèi)存空間。比如上面sdshdr16的代碼中就有__attribute__ ((packed))，它的目的是告訴編譯器采用緊湊的方式分配內(nèi)存，默認(rèn)情況下編譯器會按照16字節(jié)的對齊方式給變量分配內(nèi)存。也就是說一個(gè)變量沒有到16個(gè)字節(jié)，編譯器也會給它分配16個(gè)字節(jié)。
我們來舉個(gè)例子
#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個(gè)字節(jié)，int占用4個(gè)字節(jié)，但是打印出來是8，這樣多出來的3個(gè)字節(jié)白白浪費(fèi)掉了。現(xiàn)在我們運(yùn)用__attribute__ ((packed))屬性定義結(jié)構(gòu)體，就可以實(shí)際占用多少字節(jié)，編譯器就分配多少空間。我們把剛才代碼修改一下加上這個(gè)屬性。代碼如下
#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;
}
運(yùn)行這段代碼，結(jié)果就變?yōu)?了，表示編譯器用了緊湊型的內(nèi)存分配。在開發(fā)過程中，為了節(jié)省內(nèi)存開銷就可以考慮把__attribute__ ((packed))這個(gè)屬性運(yùn)用起來。
到此這篇關(guān)于Redis的字符串是如何實(shí)現(xiàn)的的文章就介紹到這了,更多相關(guān)Redis字符串實(shí)現(xiàn)內(nèi)容請搜索本站以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持本站！
版權(quán)聲明：本站文章來源標(biāo)注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請保持原文完整并注明來源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站，禁止在非www.sddonglingsh.com所屬的服務(wù)器上建立鏡像，否則將依法追究法律責(zé)任。本站部分內(nèi)容來源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來，僅供學(xué)習(xí)參考，不代表本站立場，如有內(nèi)容涉嫌侵權(quán)，請聯(lián)系alex-e#qq.com處理。
關(guān)注官方微信