Redis的字符串是如何實現的
前言
字符串在日常開發中應用得比較普遍，對於Redis來說，鍵值對中的鍵是字符串，值也是字符串。比如在Redis中寫入一條客戶信息記錄姓名、性別、愛好等。
在Redis這種內存數據庫中，由於字符串被廣泛的應用，在設計字符串時基於以下幾點來設計：
1.支持豐富高效的字符串操作，比如追加、拷貝、比較等操作
2.能保存二進制數據
3.能盡可能的節省內存開銷
可能會有人問瞭，既然C語言庫提供瞭char*這樣的字符數組來字符串操作。比如strcmp,strcat。感覺完全可以考慮直接使用C庫提供的啊。C庫字符串運用是很普遍，但是也不是沒有問題的。它需要頻繁的創建和檢查空間，這在實際項目中其實很花時間的。所以，Redis設計瞭簡單字符串（SDS，Simple Data )來表示字符串。同原來的C語言相比提升瞭字符串的操作效率，而且還支持二進制格式。下面我們就來介紹下Redis的字符串是如何實現的。
為什麼不用char*
先來看看char*字符數組的結構，其實很簡單就是開辟一塊連續的內存空間來依次存放每一個字符，最後一個字符是”\0″表示字符串結束。C庫中的字符串操作函數就是通過檢查”\0″來判斷字符串結束。比如strlen函數就是遍歷字符數組中的每一個字符並計數，直到遇到”\0″結束計數，然後返回計數結果。下面我們通過一個代碼來看看”\0″結束字符對字符串長度的影響。
這段代碼的執行結果如下：
表示a1的字符長度是2個字符。這是因為在he後面有瞭”\0″，所以字符串以”\0″表示結束，這就會產生一個問題，如果字符串內部本身就有”\0″,那麼數據就會被”\0″截斷，而這就不能保存任意二進制數據瞭。
傳統設計操作復雜度高
除瞭上面提到的不能保存任意二進制數據以外，操作復雜度也挺大。比如C語言中用得比較普遍的strlen函數，它要遍歷字符數組中的每一個字符才能得到字符串長度。所以，時間復雜度是O(n)。另外再說一個常用函數strcat，它同strlen函數一樣先遍歷字符串才能得到目標字符串的末尾，而且它把源字符串追加到目標字符串末尾的時，還得確認目標字符串是否具有足夠的空間。所以在調用的時候，開發人員還要人為保證目標字符串有足夠的可用空間，不然就需要動態地申請空間。這樣不僅時間復雜度高，操作復雜度也高瞭。
SDS的設計
Redis在設計的時候還是盡量保證復用C標準的字符串操作函數的。Redis在保留瞭使用字符數組來保存實際數據基礎上，專門設計瞭一種SDS數據結構。
首先，SDS結構裡面包含瞭一個字符數組buf[],同時SDS結構裡面還包含瞭三個元數據。分別是字符數組現有長度len，分配給字符數組的空間長度alloc以及SDS類型flags。其中len和alloc這兩個元數據定義瞭不同類型的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本質還是字符數組，隻是在字符數組基礎上增加瞭額外的元數據，Redis在使用字符數組時直接使用sds這個別名。
SDS的高效操作
創建sds
Redis調用sdsnewlen函數創建sds。我們以sedsnewlen舉例，代碼如下：
hisds sdsnewlen(const void *init, size_t initlen) {
//指向SDS結構的指針
void *sh;
//sds類型變量,就是char*的別名
sds s;
//根據大小獲取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. */
//為新創建的sds結構分配內存
sh = s_malloc(hdrlen+initlen+1);
if (sh == NULL) return NULL;
if (!init)
memset(sh, 0, hdrlen+initlen+1);
//指向SDS結構體中的buf數組,sh指向SDS結構的起始位置，hdrlen表示元數據的長度
s = (char*)sh+hdrlen;
fp = ((unsigned char*)s)-1;
//根據類型初始化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"表示字符串結束
s[initlen] = '\0';
return s;
}
該函數主要執行過程如下：
1.根據初始化長度獲取SDS類型。如果初始化長度initlen為0，一般被認為是要執行append操作，設置SDS類型為SDS_TYPE_8
2.為新創建的SDS結構分配內存，內存空間為元數據長度+buf長度+字符串最後的結束符”\0″。
3.根據SDS類型去初始化元數據len和alloc
4.將字符串拷貝給sds
字符數組拼接
由於sds結構中記錄瞭占用的空間和被分配的空間，所以它比傳統C語言的字符串效率更高。下面我們通過Redis的字符串追加函數sdscatlen來看一看。代碼如下：
sds sdscatlen(sds s, const void *t, size_t len) {
//獲取目標字符串的長度
size_t curlen = sdslen(s);
//根據追加長度和目標字符串長度判斷是否需要增加新的空間
s = sdsMakeRoomFor(s,len);
if (s == NULL) return NULL;
//將源字符串t中len長度的數據拷貝到目標字符串尾部
memcpy(s+curlen, t, len);
//設置目標字符串的最新長度
sdssetlen(s, curlen+len);
//拷貝完成後，在字符串結尾加上"\0"
s[curlen+len] = '\0';
return s;
}
這個函數有三個參數分別是目標字符串s,源字符串t和要追加的長度len。這個代碼執行過程如下：
1.首先獲取目標字符串的長度，然後調用sdsMakeRoomFor函數判斷是否要給目標字符串添加新的空間，這樣就可以保證目標字符串有足夠的空間追加字符串
2.在保證瞭有足夠空間可以追加字符串後，將源字符串中指定長度len的數據追加到目標字符串
3.設置目標字符串的最新長度
長度獲取
代碼中，函數sdslen記錄瞭字符數組的使用長度，不用同C庫一樣遍歷字符串瞭，這樣可以大大降低瞭操作使用字符串的開銷。該函數的代碼如下所示：
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;
}
這樣時間復雜度直接降到瞭O(1)。這個函數有一個騷操作，通過s[-1]獲取到flags，然後調用SDS_HDR宏函數。我們來看下這個宏函數定義
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
其中##用來將兩個token連接為一個token，所以加上參數將在預編譯階段將被替換如下
SDS_HDR(8,s); ((struct sdshdr8 *)((s)-(sizeof(struct sdshdr8))))
字符數組地址減去結構體的大小，就能獲取到結構體的首地址，然後直接訪問len屬性。
預分配內存空間
此外，在代碼中還使用瞭sdsMakeRoomFor函數，它在拼接字符串之前會檢查是否需要擴容，如果需要擴容則會預分配空間。這一設計的好處就是避免瞭開發中忘記給目標字符串擴容而導致操作失敗。比如strcpy(char* dst, const char* dst),如果src長度大於瞭dst的長度，又沒有做檢查就會遭成內存溢出。代碼如下所示：
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 */
//如果新的字符數組長度小於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 {
/ /如果頭部大小發生變化隻需要將字符數組向前移，不使用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)
節省內存的設計
前面講SDS結構的時候提到過它有一個元數據flag，表示字符串類型。SDS一共有5中類型，它們分別是sdshdr5,sdshdr8,sdshdr16,sdshdr32和sdshdr64。這五種的主要區別是它們字符數組的現有長度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[];
};
我們可以看到現有長度len和已分配空間alloc都是uint16_t類型，uint16_t是16位無符號整型，會占用2個字節。當字符串類型是sdshdr16的時候它包含的字符數組長度最大為2^16-1字節。而對於其它三種sdshdr8,sdshdr32和sdshdr64，以此類推它們的類型就分別是uin8_t，uin32_t和uint64_t，len和alloc這兩個元數據占用的空間分別是1字節、4字節和8字節。
實際上，設計不同的結構頭的目的是為瞭靈活保存不同大小的字符串，從而有效地節省內存空間。在保存不同大小的字符串時，結構頭占用的內存空間也不一樣，這樣一來保存小字符串時，占用的空間也會比較小。
除瞭設計不同類型的結構頭以外，Redis還使用編譯優化來節省內存空間。比如上面sdshdr16的代碼中就有__attribute__ ((packed))，它的目的是告訴編譯器采用緊湊的方式分配內存，默認情況下編譯器會按照16字節的對齊方式給變量分配內存。也就是說一個變量沒有到16個字節，編譯器也會給它分配16個字節。
我們來舉個例子
#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個字節，int占用4個字節，但是打印出來是8，這樣多出來的3個字節白白浪費掉瞭。現在我們運用__attribute__ ((packed))屬性定義結構體，就可以實際占用多少字節，編譯器就分配多少空間。我們把剛才代碼修改一下加上這個屬性。代碼如下
#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;
}
運行這段代碼，結果就變為5瞭，表示編譯器用瞭緊湊型的內存分配。在開發過程中，為瞭節省內存開銷就可以考慮把__attribute__ ((packed))這個屬性運用起來。
到此這篇關於Redis的字符串是如何實現的的文章就介紹到這瞭,更多相關Redis字符串實現內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！