Redis的字符串是如何實現(xiàn)的
前言
字符串在日常開發(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)字符串末尾的時，還得確認目標(biāo)字符串是否具有足夠的空間。所以在調(diào)用的時候，開發(fā)人員還要人為保證目標(biāo)字符串有足夠的可用空間，不然就需要動態(tài)地申請空間。這樣不僅時間復(fù)雜度高，操作復(fù)雜度也高了。
SDS的設(shè)計
Redis在設(shè)計的時候還是盡量保證復(fù)用C標(biāo)準的字符串操作函數(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，一般被認為是要執(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)存，默認情況下編譯器會按照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)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Redis實現(xiàn)限流器的三種方法(小結(jié))
本文主要介紹了Redis實現(xiàn)限流器的三種方法，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-05-05
這篇文章主要給大家介紹了關(guān)于redis主從復(fù)制原理的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家學(xué)習(xí)或者使用redis具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-04-04
在 Redis 中,哈希表是一種常見的數(shù)據(jù)結(jié)構(gòu),通常用于存儲對象的屬性,對于哈希表,最常遇到的是哈希沖突,那么,當(dāng) Redis遇到Hash沖突會如何處理？本文我們將詳細介紹Redis如何處理哈希沖突,需要的朋友可以參考下2024-09-09
redis支持五大數(shù)據(jù)類型，只支持第一層，也就說字典的value值，必須是字符串，本文主要介紹了redis中Hash字典操作，感興趣的可以了解一下2021-07-07
這篇文章主要給大家介紹了關(guān)于Redis分布式鎖的使用和實現(xiàn)原理的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11
這篇文章主要介紹了redis服務(wù)如何啟動問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-08-08
本文主要介紹了Redis慢查詢的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-07-07
深入了解Redis連接數(shù)問題的現(xiàn)象和解法
一般情況?Redis?連接數(shù)問題并不常見,但是當(dāng)你業(yè)務(wù)服務(wù)增加、對?Redis?的依賴持續(xù)增強的過程中,可能會遇到很多?Redis?的問題,這個時候,Redis?連接數(shù)可能就成了一個常見的問題,在本章節(jié),希望能夠帶大家了解Redis連接數(shù)問題的現(xiàn)象和解法,需要的朋友可以參考下2023-12-12
Redis中可以設(shè)置鍵的過期時間,并且通過取出過期字典（expires dict）中鍵的過期時間和當(dāng)前時間比較來判斷是否過期,那么一個過期的鍵是怎么被刪除的呢？本文給大家總結(jié)了三種方法,選了其中兩種給大家詳細的介紹一下,需要的朋友可以參考下2024-05-05
redis?Template.opsForValue()中方法實例詳解
這篇文章主要介紹了redis?Template.opsForValue()中方法講解,本文通過實例代碼給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2023-05-05