Redis中內(nèi)部數(shù)據(jù)結構sds的作用是什么
redis中內(nèi)部數(shù)據(jù)結構sds的作用是什么，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。
專業(yè)從事成都網(wǎng)站建設、做網(wǎng)站,高端網(wǎng)站制作設計,小程序制作,網(wǎng)站推廣的成都做網(wǎng)站的公司。優(yōu)秀技術團隊竭力真誠服務，采用成都h5網(wǎng)站建設+CSS3前端渲染技術，響應式網(wǎng)站設計，讓網(wǎng)站在手機、平板、PC、微信下都能呈現(xiàn)。建站過程建立專項小組，與您實時在線互動，隨時提供解決方案，暢聊想法和感受。
sds的數(shù)據(jù)結構定義
我們知道，在C語言中，字符串是以’\0’字符結尾（NULL結束符）的字符數(shù)組來存儲的，通常表達為字符指針的形式（char *）。它不允許字節(jié)0出現(xiàn)在字符串中間，因此，它不能用來存儲任意的二進制數(shù)據(jù)。
我們可以在sds.h中找到sds的類型定義：
typedef char
sds;
肯定有人感到困惑了，竟然sds就等同于char ？我們前面提到過，sds和傳統(tǒng)的C語言字符串保持類型兼容，因此它們的類型定義是一樣的，都是char
。在有些情況下，需要傳入一個C語言字符串的地方，也確實可以傳入一個sds。但是，sds和char 并不等同。sds是Binary Safe的，它可以存儲任意二進制數(shù)據(jù)，不能像C語言字符串那樣以字符’\0’來標識字符串的結束，因此它必然有個長度字段。但這個長度字段在哪里呢？實際上sds還包含一個header結構：
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[];
};sds一共有5種類型的header。之所以有5種，是為了能讓不同長度的字符串可以使用不同大小的header。這樣，短字符串就能使用較小的header，從而節(jié)省內(nèi)存。
一個sds字符串的完整結構，由在內(nèi)存地址上前后相鄰的兩部分組成：
一個header。通常包含字符串的長度(len)、最大容量(alloc)和flags。sdshdr5有所不同。
一個字符數(shù)組。這個字符數(shù)組的長度等于最大容量+1。真正有效的字符串數(shù)據(jù)，其長度通常小于最大容量。在真正的字符串數(shù)據(jù)之后，是空余未用的字節(jié)（一般以字節(jié)0填充），允許在不重新分配內(nèi)存的前提下讓字符串數(shù)據(jù)向后做有限的擴展。在真正的字符串數(shù)據(jù)之后，還有一個NULL結束符，即ASCII碼為0的’\0’字符。這是為了和傳統(tǒng)C字符串兼容。之所以字符數(shù)組的長度比最大容量多1個字節(jié)，就是為了在字符串長度達到最大容量時仍然有1個字節(jié)存放NULL結束符。
除了sdshdr5之外，其它4個header的結構都包含3個字段：
len: 表示字符串的真正長度（不包含NULL結束符在內(nèi)）。 alloc: 表示字符串的最大容量（不包含最后多余的那個字節(jié)）。 flags: 總是占用一個字節(jié)。其中的最低3個bit用來表示header的類型。header的類型共有5種，在sds.h中有常量定義。 #define SDS_TYPE_5 0 #define SDS_TYPE_8 1 #define SDS_TYPE_16 2 #define SDS_TYPE_32 3 #define SDS_TYPE_64 4
sds的數(shù)據(jù)結構，我們有必要非常仔細地去解析它。
Redis dict結構舉例
上圖是sds的一個內(nèi)部結構的例子。圖中展示了兩個sds字符串s1和s2的內(nèi)存結構，一個使用sdshdr8類型的header，另一個使用sdshdr16類型的header。但它們都表達了同樣的一個長度為6的字符串的值：”tielei”。下面我們結合代碼，來解釋每一部分的組成。
sds的字符指針（s1和s2）就是指向真正的數(shù)據(jù)（字符數(shù)組）開始的位置，而header位于內(nèi)存地址較低的方向。在sds.h中有一些跟解析header有關的宏定義：
#define SDS_TYPE_MASK 7 #define SDS_TYPE_BITS 3 #define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T))); #define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T)))) #define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)
其中SDS_HDR用來從sds字符串獲得header起始位置的指針，比如SDS_HDR(8, s1)表示s1的header指針，SDS_HDR(16, s2)表示s2的header指針。
當然，使用SDS_HDR之前我們必須先知道到底是哪一種header，這樣我們才知道SDS_HDR第1個參數(shù)應該傳什么。由sds字符指針獲得header類型的方法是，先向低地址方向偏移1個字節(jié)的位置，得到flags字段。比如，s1[-1]和s2[-1]分別獲得了s1和s2的flags的值。然后取flags的最低3個bit得到header的類型。
由于s1[-1] == 0x01 == SDS_TYPE_8，因此s1的header類型是sdshdr8。
由于s2[-1] == 0x02 == SDS_TYPE_16，因此s2的header類型是sdshdr16。
有了header指針，就能很快定位到它的len和alloc字段：
s1的header中，len的值為0x06，表示字符串數(shù)據(jù)長度為6；alloc的值為0x80，表示字符數(shù)組最大容量為128。
s2的header中，len的值為0x0006，表示字符串數(shù)據(jù)長度為6；alloc的值為0x03E8，表示字符數(shù)組最大容量為1000。（注意：圖中是按小端地址構成）
在各個header的類型定義中，還有幾個需要我們注意的地方：
在各個header的定義中使用了attribute((packed))，是為了讓編譯器以緊湊模式來分配內(nèi)存。如果沒有這個屬性，編譯器可能會為struct的字段做優(yōu)化對齊，在其中填充空字節(jié)。那樣的話，就不能保證header和sds的數(shù)據(jù)部分緊緊前后相鄰，也不能按照固定向低地址方向偏移1個字節(jié)的方式來獲取flags字段了。
在各個header的定義中最后有一個char buf[]。我們注意到這是一個沒有指明長度的字符數(shù)組，這是C語言中定義字符數(shù)組的一種特殊寫法，稱為柔性數(shù)組（flexible array member），只能定義在一個結構體的最后一個字段上。
它在這里只是起到一個標記的作用，表示在flags字段后面就是一個字符數(shù)組，或者說，它指明了緊跟在flags字段后面的這個字符數(shù)組在結構體中的偏移位置。而程序在為header分配的內(nèi)存的時候，它并不占用內(nèi)存空間。
如果計算sizeof(struct sdshdr16)的值，那么結果是5個字節(jié)，其中沒有buf字段。
sdshdr5與其它幾個header結構不同，它不包含alloc字段，而長度使用flags的高5位來存儲。
因此，它不能為字符串分配空余空間。如果字符串需要動態(tài)增長，那么它就必然要重新分配內(nèi)存才行。所以說，這種類型的sds字符串更適合存儲靜態(tài)的短字符串（長度小于32）。
至此，我們非常清楚地看到了：sds字符串的header，其實隱藏在真正的字符串數(shù)據(jù)的前面（低地址方向）。這樣的一個定義，有如下幾個好處：
header和數(shù)據(jù)相鄰，而不用分成兩塊內(nèi)存空間來單獨分配。這有利于減少內(nèi)存碎片，提高存儲效率（memory efficiency）。
雖然header有多個類型，但sds可以用統(tǒng)一的char *來表達。且它與傳統(tǒng)的C語言字符串保持類型兼容。
如果一個sds里面存儲的是可打印字符串，那么我們可以直接把它傳給C函數(shù)，比如使用strcmp比較字符串大小，或者使用printf進行打印。
弄清了sds的數(shù)據(jù)結構，它的具體操作函數(shù)就比較好理解了。
sds的一些基礎函數(shù) sdslen(const sds s): 獲取sds字符串長度。 sdssetlen(sds s, size_t newlen): 設置sds字符串長度。 sdsinclen(sds s, size_t inc): 增加sds字符串長度。 sdsalloc(const sds s): 獲取sds字符串容量。 sdssetalloc(sds s, size_t newlen): 設置sds字符串容量。 sdsavail(const sds s): 獲取sds字符串空余空間（即alloc - len）。 sdsHdrSize(char type): 根據(jù)header類型得到header大小。 sdsReqType(size_t string_size):
根據(jù)字符串數(shù)據(jù)長度計算所需要的header類型。
這里我們挑選sdslen和sdsReqType的代碼，察看一下。
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;
}
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 (string_size < 1ll<<32)
return SDS_TYPE_32;
return SDS_TYPE_64;
}跟前面的分析類似，sdslen先用s[-1]向低地址方向偏移1個字節(jié)，得到flags；然后與SDS_TYPE_MASK進行按位與，得到header類型；然后根據(jù)不同的header類型，調用SDS_HDR得到header起始指針，進而獲得len字段。
通過sdsReqType的代碼，很容易看到：
長度在0和2^5-1之間，選用SDS_TYPE_5類型的header。
長度在2^5和2^8-1之間，選用SDS_TYPE_8類型的header。
長度在2^8和2^16-1之間，選用SDS_TYPE_16類型的header。
長度在2^16和2^32-1之間，選用SDS_TYPE_32類型的header。
長度大于2^32的，選用SDS_TYPE_64類型的header。能表示的最大長度為2^64-1。
注：sdsReqType的實現(xiàn)代碼，直到3.2.0，它在長度邊界值上都一直存在問題，直到最近3.2 branch上的commit 6032340才修復。
sds的創(chuàng)建和銷毀
sds sdsnewlen(const void *init, size_t initlen) {
void *sh;
sds s;
char type = 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. */
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;
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);
s[initlen] = '\0';
return s;
}
sds sdsempty(void) {
return sdsnewlen("",0);
}
sds sdsnew(const char *init) {
size_t initlen = (init == NULL) ? 0 : strlen(init);
return sdsnewlen(init, initlen);
}
void sdsfree(sds s) {
if (s == NULL) return;
s_free((char*)s-sdsHdrSize(s[-1]));
}sdsnewlen創(chuàng)建一個長度為initlen的sds字符串，并使用init指向的字符數(shù)組（任意二進制數(shù)據(jù)）來初始化數(shù)據(jù)。如果init為NULL，那么使用全0來初始化數(shù)據(jù)。它的實現(xiàn)中，我們需要注意的是：
如果要創(chuàng)建一個長度為0的空字符串，那么不使用SDS_TYPE_5類型的header，而是轉而使用SDS_TYPE_8類型的header。這是因為創(chuàng)建的空字符串一般接下來的操作很可能是追加數(shù)據(jù)，但SDS_TYPE_5類型的sds字符串不適合追加數(shù)據(jù)（會引發(fā)內(nèi)存重新分配）。
需要的內(nèi)存空間一次性進行分配，其中包含三部分：header、數(shù)據(jù)、最后的多余字節(jié)（hdrlen+initlen+1）。
初始化的sds字符串數(shù)據(jù)最后會追加一個NULL結束符（s[initlen] = ‘\0’）。
關于sdsfree，需要注意的是：內(nèi)存要整體釋放，所以要先計算出header起始指針，把它傳給s_free函數(shù)。這個指針也正是在sdsnewlen中調用s_malloc返回的那個地址。
sds的連接（追加）操作
sds sdscatlen(sds s, const void *t, size_t len) {
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 sdscat(sds s, const char *t) {
return sdscatlen(s, t, strlen(t));
}
sds sdscatsds(sds s, const sds t) {
return sdscatlen(s, t, sdslen(t));
}
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;
int hdrlen;
/* Return ASAP if there is enough space left. */
if (avail >= addlen) return s;
len = sdslen(s);
sh = (char*)s-sdsHdrSize(oldtype);
newlen = (len+addlen);
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
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 {
/* 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;
}sdscatlen將t指向的長度為len的任意二進制數(shù)據(jù)追加到sds字符串s的后面。本文開頭演示的string的append命令，內(nèi)部就是調用sdscatlen來實現(xiàn)的。
在sdscatlen的實現(xiàn)中，先調用sdsMakeRoomFor來保證字符串s有足夠的空間來追加長度為len的數(shù)據(jù)。sdsMakeRoomFor可能會分配新的內(nèi)存，也可能不會。
sdsMakeRoomFor是sds實現(xiàn)中很重要的一個函數(shù)。關于它的實現(xiàn)代碼，我們需要注意的是：
如果原來字符串中的空余空間夠用（avail >= addlen），那么它什么也不做，直接返回。
如果需要分配空間，它會比實際請求的要多分配一些，以防備接下來繼續(xù)追加。它在字符串已經(jīng)比較長的情況下要至少多分配SDS_MAX_PREALLOC個字節(jié)，這個常量在sds.h中定義為(1024*1024)=1MB。
按分配后的空間大小，可能需要更換header類型（原來header的alloc字段太短，表達不了增加后的容量）。
如果需要更換header，那么整個字符串空間（包括header）都需要重新分配（s_malloc），并拷貝原來的數(shù)據(jù)到新的位置。
如果不需要更換header（原來的header夠用），那么調用一個比較特殊的s_realloc，試圖在原來的地址上重新分配空間。s_realloc的具體實現(xiàn)得看Redis編譯的時候選用了哪個allocator（在Linux上默認使用jemalloc）。
但不管是哪個realloc的實現(xiàn)，它所表達的含義基本是相同的：它盡量在原來分配好的地址位置重新分配，如果原來的地址位置有足夠的空余空間完成重新分配，那么它返回的新地址與傳入的舊地址相同；否則，它分配新的地址塊，并進行數(shù)據(jù)搬遷。參見 http://man.cx/realloc。
從sdscatlen的函數(shù)接口，我們可以看到一種使用模式：調用它的時候，傳入一個舊的sds變量，然后它返回一個新的sds變量。由于它的內(nèi)部實現(xiàn)可能會造成地址變化，因此調用者在調用完之后，原來舊的變量就失效了，而都應該用新返回的變量來替換。不僅僅是sdscatlen函數(shù)，sds中的其它函數(shù)（比如sdscpy、sdstrim、sdsjoin等），還有Redis中其它一些能自動擴展內(nèi)存的數(shù)據(jù)結構（如ziplist），也都是同樣的使用模式。
淺談sds與string的關系
現(xiàn)在我們回過頭來看看本文開頭給出的string操作的例子。
append操作使用sds的sdscatlen來實現(xiàn)。前面已經(jīng)提到。
setbit和getrange都是先根據(jù)key取到整個sds字符串，然后再從字符串選取或修改指定的部分。由于sds就是一個字符數(shù)組，所以對它的某一部分進行操作似乎都比較簡單。
看完上述內(nèi)容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝您對創(chuàng)新互聯(lián)的支持。
分享題目：Redis中內(nèi)部數(shù)據(jù)結構sds的作用是什么
標題URL：http://bm7419.com/article34/pcogpe.html
成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供域名注冊、企業(yè)建站、云服務器、面包屑導航、手機網(wǎng)站建設、虛擬主機
聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉載內(nèi)容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)
- 云虛擬主機的使用用途有哪些？ 2022-10-07
- 國內(nèi)外虛擬主機對比：站長該如何選擇 2021-10-27
- Windows虛擬主機優(yōu)勢有哪些 2016-11-01
- 免費虛擬主機是在變相的“消費” 2022-05-23
- 企業(yè)網(wǎng)站一般選什么樣的虛擬主機 2014-03-14
- 虛擬主機易被忽視的實用功能 2022-07-17
- 服務器租賃虛擬主機建造網(wǎng)站有哪些便利之處？ 2021-01-25
- 建站是選服務器還是虛擬主機？ 2022-10-03
- 云服務器和虛擬主機的區(qū)別主要有哪些？ 2022-10-06
- 關于服務器，虛擬主機及VPS的解釋! 2019-09-09
- 佛山網(wǎng)站建設如何規(guī)劃?佛山建網(wǎng)站有哪些好的公司? 2022-06-06
- 企業(yè)選擇網(wǎng)站虛擬主機需要重點從哪些方面進行考察？ 2022-06-27