Redis的字符串是如何實現的
前言
字符串在日常開發(fā)中應用得比較普遍，對于Redis來說，鍵值對中的鍵是字符串，值也是字符串。比如在Redis中寫入一條客戶信息記錄姓名、性別、愛好等。
在Redis這種內存數據庫中，由于字符串被廣泛的應用，在設計字符串時基于以下幾點來設計：
1.支持豐富高效的字符串操作，比如追加、拷貝、比較等操作
2.能保存二進制數據
3.能盡可能的節(jié)省內存開銷
可能會有人問了，既然C語言庫提供了char*這樣的字符數組來字符串操作。比如strcmp,strcat。感覺完全可以考慮直接使用C庫提供的啊。C庫字符串運用是很普遍，但是也不是沒有問題的。它需要頻繁的創(chuàng)建和檢查空間，這在實際項目中其實很花時間的。所以，Redis設計了簡單字符串（SDS，Simple Data )來表示字符串。同原來的C語言相比提升了字符串的操作效率，而且還支持二進制格式。下面我們就來介紹下Redis的字符串是如何實現的。
為什么不用char*
先來看看char*字符數組的結構，其實很簡單就是開辟一塊連續(xù)的內存空間來依次存放每一個字符，最后一個字符是"\0"表示字符串結束。C庫中的字符串操作函數就是通過檢查"\0"來判斷字符串結束。比如strlen函數就是遍歷字符數組中的每一個字符并計數，直到遇到"\0"結束計數，然后返回計數結果。下面我們通過一個代碼來看看"\0"結束字符對字符串長度的影響。
這段代碼的執(zhí)行結果如下：
表示a1的字符長度是2個字符。這是因為在he后面有了"\0"，所以字符串以"\0"表示結束，這就會產生一個問題，如果字符串內部本身就有"\0",那么數據就會被"\0"截斷，而這就不能保存任意二進制數據了。
傳統設計操作復雜度高
除了上面提到的不能保存任意二進制數據以外，操作復雜度也挺大。比如C語言中用得比較普遍的strlen函數，它要遍歷字符數組中的每一個字符才能得到字符串長度。所以，時間復雜度是O(n)。另外再說一個常用函數strcat，它同strlen函數一樣先遍歷字符串才能得到目標字符串的末尾，而且它把源字符串追加到目標字符串末尾的時，還得確認目標字符串是否具有足夠的空間。所以在調用的時候，開發(fā)人員還要人為保證目標字符串有足夠的可用空間，不然就需要動態(tài)地申請空間。這樣不僅時間復雜度高，操作復雜度也高了。
SDS的設計
Redis在設計的時候還是盡量保證復用C標準的字符串操作函數的。Redis在保留了使用字符數組來保存實際數據基礎上，專門設計了一種SDS數據結構。
首先，SDS結構里面包含了一個字符數組buf[],同時SDS結構里面還包含了三個元數據。分別是字符數組現有長度len，分配給字符數組的空間長度alloc以及SDS類型flags。其中l(wèi)en和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的高效操作
創(chuàng)建sds
Redis調用sdsnewlen函數創(chuàng)建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. */
//為新創(chuàng)建的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;
}
該函數主要執(zhí)行過程如下：
1.根據初始化長度獲取SDS類型。如果初始化長度initlen為0，一般被認為是要執(zhí)行append操作，設置SDS類型為SDS_TYPE_8
2.為新創(chuàng)建的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中l(wèi)en長度的數據拷貝到目標字符串尾部
memcpy(s+curlen, t, len);
//設置目標字符串的最新長度
sdssetlen(s, curlen+len);
//拷貝完成后，在字符串結尾加上"\0"
s[curlen+len] = '\0';
return s;
}
這個函數有三個參數分別是目標字符串s,源字符串t和要追加的長度len。這個代碼執(zhí)行過程如下：
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函數，它在拼接字符串之前會檢查是否需要擴容，如果需要擴容則會預分配空間。這一設計的好處就是避免了開發(fā)中忘記給目標字符串擴容而導致操作失敗。比如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 {
/ /如果頭部大小發(fā)生變化只需要將字符數組向前移，不使用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é)省內存的設計
前面講SDS結構的時候提到過它有一個元數據flag，表示字符串類型。SDS一共有5中類型，它們分別是sdshdr5,sdshdr8,sdshdr16,sdshdr32和sdshdr64。這五種的主要區(qū)別是它們字符數組的現有長度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個字節(jié)。當字符串類型是sdshdr16的時候它包含的字符數組長度最大為2^16-1字節(jié)。而對于其它三種sdshdr8,sdshdr32和sdshdr64，以此類推它們的類型就分別是uin8_t，uin32_t和uint64_t，len和alloc這兩個元數據占用的空間分別是1字節(jié)、4字節(jié)和8字節(jié)。
實際上，設計不同的結構頭的目的是為了靈活保存不同大小的字符串，從而有效地節(jié)省內存空間。在保存不同大小的字符串時，結構頭占用的內存空間也不一樣，這樣一來保存小字符串時，占用的空間也會比較小。
除了設計不同類型的結構頭以外，Redis還使用編譯優(yōu)化來節(jié)省內存空間。比如上面sdshdr16的代碼中就有__attribute__ ((packed))，它的目的是告訴編譯器采用緊湊的方式分配內存，默認情況下編譯器會按照16字節(jié)的對齊方式給變量分配內存。也就是說一個變量沒有到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é)白白浪費掉了。現在我們運用__attribute__ ((packed))屬性定義結構體，就可以實際占用多少字節(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;
}
運行這段代碼，結果就變?yōu)?了，表示編譯器用了緊湊型的內存分配。在開發(fā)過程中，為了節(jié)省內存開銷就可以考慮把__attribute__ ((packed))這個屬性運用起來。
到此這篇關于Redis的字符串是如何實現的的文章就介紹到這了,更多相關Redis字符串實現內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要為大家介紹了Redis拓展之定時消息通知實現詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-07-07
這篇文章主要給大家介紹了關于Redis Cluster添加、刪除的完整操作步驟，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習下吧。2017-09-09
這篇文章主要介紹了Redis中實現查找某個值的范圍,本文的題引來了Redis作者Salvatore Sanfilippo（@antirez）的回答,比較經典,需要的朋友可以參考下2015-06-06
這篇文章主要介紹了Redis 常見使用場景的相關資料,需要的朋友可以參考下文2021-08-08
這篇文章主要介紹了YII2框架手動安裝Redis擴展的過程，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2022-06-06
BitMap是通過一個bit位來表示某個元素對應的值或者狀態(tài),其中的key就是對應元素本身。我們知道8個bit可以組成一個Byte，所以bitmap本身會極大的節(jié)省儲存空間，下面通過本文給大家介紹Redis中的bitmap知識，感興趣的朋友一起看看吧2021-10-10
這篇文章主要為大家介紹了Redis使用Lua腳本命令詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-12-12
這篇文章主要介紹了redis配置認證密碼的方法,需要的朋友可以參考下2016-08-08
這篇文章主要介紹了Redis刪除策略的三種方法及逐出算法，文章圍繞主題展開詳細的內容介紹，具有一定的參考價值，需要的小伙伴可以參考一下2022-08-08
為了保證我們線上服務的并發(fā)性和安全性，目前我們的服務一般拋棄了單體應用，采用的都是擴展性很強的分布式架構，這篇文章主要介紹了使用Redis實現分布式鎖的方法,需要的朋友可以參考下2022-06-06