當前位置：首頁 > 运维知识 > 数据库 >内容正文

数据库

Redis之简单动态字符串sds

發(fā)布時間：2023/12/20 数据库 36 豆豆

生活随笔收集整理的這篇文章主要介紹了 Redis之简单动态字符串sds 小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

轉(zhuǎn)載：https://segmentfault.com/a/1190000012262739

redis在處理字符串的時候沒有直接使用以'\0'結(jié)尾的C語言字符串，而是封裝了一下C語言字符串并命名為sds(simple dynamic string)，在sds.h文件里我們可以看到如下類型定義：
typedef char *sds;
也就是說實際上sds類型就是char*類型，那sds和char*有什么區(qū)別呢？
主要區(qū)別就是：sds一定有一個所屬的結(jié)構(gòu)(sdshdr)，這個header結(jié)構(gòu)在每次創(chuàng)建sds時被創(chuàng)建，用來存儲sds以及sds的相關(guān)信息(下文sds的含義僅僅是redis的字符串，sdshdr才表示sds的header)。

那為什么redis不直接使用char*呢？總結(jié)起來理由如下：

<1>、可以常數(shù)復(fù)雜度獲取字符串長度

通過len屬性直接獲取字符串實際長度，不包括結(jié)尾的’\0’.? ??時間復(fù)雜度O(1)

<2>、防止緩沖區(qū)溢出

strcat()函數(shù)不能保證目的內(nèi)存是足夠的。

<3>、減少修改字符串導(dǎo)致內(nèi)存重分配的次數(shù)

空間預(yù)分配策略，Redis可以減少連續(xù)執(zhí)行字符串增長所需的內(nèi)存重分配次數(shù)。

<4>、二進制安全

C語言中的字符串以'\0'結(jié)尾，而Redis由于使用len記錄數(shù)據(jù)長度，而不是使用空字符判斷字符串是否結(jié)束，所以簡單動態(tài)字符串可以存儲包含空字符的數(shù)據(jù).

1.sdshdr定義
sdshdr和sds是一一對應(yīng)的關(guān)系，一個sds一定會有一個sdshdr用來記錄sds的信息。在redis3.2分支出現(xiàn)之前sdshdr只有一個類型，定義如下：

struct sdshdr {unsigned int len;//表示sds當前的長度unsigned int free;//已為sds分配的長度-sds當前的長度char buf[];//sds實際存放的位置 };

這些版本的redis每次創(chuàng)建一個sds 不管sds實際有多長，都會分配一個大小固定的sdshdr。根據(jù)成員len的類型可知，sds最多能存長度為2^(8*sizeof(unsigned int))的字符串。
而3.2分支引入了五種sdshdr類型，每次在創(chuàng)建一個sds時根據(jù)sds的實際長度判斷應(yīng)該選擇什么類型的sdshdr，不同類型的sdshdr占用的內(nèi)存空間不同。這樣細分一下可以省去很多不必要的內(nèi)存開銷，下面是3.2的sdshdr定義：

struct __attribute__ ((__packed__)) sdshdr5 {//實際上這個類型redis不會被使用。他的內(nèi)部結(jié)構(gòu)也與其他sdshdr不同，直接看sdshdr8就好。unsigned char flags; //一共8位，低3位用來存放真實的flags(類型),高5位用來存放len(長度)。char buf[];//sds實際存放的位置 }; struct __attribute__ ((__packed__)) sdshdr8 {uint8_t len;//表示當前sds的長度(單位是字節(jié))uint8_t alloc; //表示已為sds分配的內(nèi)存大小(單位是字節(jié))unsigned char flags; //用一個字節(jié)表示當前sdshdr的類型，因為有sdshdr有五種類型，所以至少需要3位來表示000:sdshdr5，001:sdshdr8，010:sdshdr16，011:sdshdr32，100:sdshdr64。高5位用不到所以都為0。char buf[];//sds實際存放的位置 }; 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[]; };

首先要說明之所以sizeof(struct sdshdr8)的大小是len+alloc+flags 是因為這個struct擁有一個柔性數(shù)組成員?buf，柔性數(shù)組成員是C99之后引入的一個新feature，這里可以通過sizeof整個struct給出buf變量的偏移量，從而確定buf的位置

其次需要說明的是定義sdshdr的這部分代碼用了__attribute__ ((__packed__))，這個語法不存在于任何C語言標準，是GCC的一個extension，用來告訴編譯器使用最小的內(nèi)存來存儲sdshdr。

引用里"minimize the memory required"其實就是讓編譯器盡量不使用內(nèi)存對齊(alignment)，以避免不必要的空間浪費，但其實這么做會有時間上的開銷，假設(shè)CPU總是從存儲器中讀取8個字節(jié)，則變量地址必須為8的倍數(shù)，為了獲取一個沒對齊的8字節(jié)的uint8_t數(shù)據(jù)，CPU需要執(zhí)行兩次內(nèi)存訪問從兩個8字節(jié)的內(nèi)存塊中取出完整的8字節(jié)數(shù)據(jù)。關(guān)于內(nèi)存對齊的更多信息，《深入理解計算機系統(tǒng)》第三章和《程序員的自我修養(yǎng)》都有非常詳細的描述。但這里我們只需要知道禁用(準確地說是盡量不使用)內(nèi)存對齊是redis為了節(jié)省內(nèi)存開支的一種手段。

接下來分析每個成員：

len表示sds當前sds的長度(單位是字節(jié))，不包括'0'終止符，通過len直接獲取字符串長度，不需要掃一遍string，這就是上文說的封裝sds的理由之一；
alloc表示當前為sds分配的大小(單位是字節(jié))(3.2以前的版本用的free是表示還剩free字節(jié)可用空間)，不包括'0'終止符；
flags表示當前sdshdr的類型，聲明為char 一共有1個字節(jié)(8位)，僅用低三位就可以表示所有5種sdshdr類型(詳見上文代碼注釋):

要判斷一個sds屬于什么類型的sdshdr，只需?flags&SDS_TYPE_MASK和SDS_TYPE_n比較即可(之所以需要SDS_TYPE_MASK是因為有sdshdr5這個特例，它的高5位不一定為0，參考上面sdshdr5定義里的代碼注釋）

sds.h里所有給出定義的內(nèi)聯(lián)函數(shù)都是通過sds作為參數(shù)，通過比較flags&SDS_TYPE_MASK和SDS_TYPE_n來判斷該sds屬于哪種類型sdshdr，再按照指定的sdshdr類型取出sds的相關(guān)信息。
例如sdslen函數(shù):

#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T)))) //返回一個類型為T包含s字符串的sdshdr的指針 #define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS) //用sdshdr5的flags成員變量做參數(shù)返回sds的長度，這其實是一個沒辦法的hack #define SDS_TYPE_BITS 3 static inline size_t sdslen(const sds s) {unsigned char flags = s[-1]; //sdshdr的flags成員變量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;//取出sdshdr的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; }

第一行里的雙井號##的意思是在一個宏(macro)定義里連接兩個子串(token)，連接之后這##號兩邊的子串就被編譯器識別為一個。
sdslen函數(shù)里第一行出現(xiàn)了s[-1]，看起來感覺會是一個undefined behavior，其實不是，這是一種正常又正確的使用方式，它就等同于*(s-1)。The de?nition of the subscript operator [] is that E1[E2] is identical to (*((E1)+(E2))). --C99。又因為s是一個sds(char*)所以s指向的類型是char，-1就是-1*sizeof(char)，由于sdshdr結(jié)構(gòu)體內(nèi)禁用了內(nèi)存對齊，所以這也剛好是一個flags(unsigned char)的地址，所以通過s[-1]我們可以獲得sds所屬的sdshdr的成員變量flags。
類似sdslen這樣利用sds找到sdshdr類型的還有如下幾個函數(shù)，就不一一分析了：

static inline size_t sdsavail(const sds s) static inline void sdssetlen(sds s, size_t newlen) static inline void sdsinclen(sds s, size_t inc) static inline size_t sdsalloc(const sds s) static inline void sdssetalloc(sds s, size_t newlen)

2.創(chuàng)建一個sds

?前面說的是在已有結(jié)果的情況下，根據(jù)一個sds通過flags變量來判斷它的sdshdr類型。那么最開始創(chuàng)建一個sds時應(yīng)該選用什么類型的sdshdr來存放它的信息呢？這就得根據(jù)要存儲的sds的長度決定了，redis在創(chuàng)建一個sds之前會調(diào)用sdsReqType(size_t string_size)來判斷用哪個sdshdr。該函數(shù)傳遞一個sds的長度作為參數(shù)，返回應(yīng)該選用的sdshdr類型

static inline char sdsReqType(size_t string_size) {if (string_size < 1<<5) //小于2^5，flags成員的高5位即可表示return SDS_TYPE_5;if (string_size < 1<<8) //小于2^8，8位整數(shù)(sdshdr8里的uint8_t)即可表示string_sizereturn SDS_TYPE_8;if (string_size < 1<<16) //小于2^16，16位整數(shù)(sdshdr16里的uint16_t)即可表示string_sizereturn SDS_TYPE_16;if (string_size < 1ll<<32) /小于2^32，32位整數(shù)(sdshrd32里的uint32_t)即可表示string_size，1ll是指1long long(至少64位)的意思，如果沒有l(wèi)l，1就是一個int，假設(shè)int為4字節(jié)32位，1<<32就會導(dǎo)致undefined behavior.return SDS_TYPE_32;return SDS_TYPE_64; //若sds的長度超過2^64，則所有類型都不法表示這個sds的len }

?知道了創(chuàng)建一個sds時應(yīng)選用什么類型的sdshdr后我們就可以看看創(chuàng)建sds的函數(shù)了:

//用init指針指向的內(nèi)存的內(nèi)容截取initlen長度來new一個sds，這個函數(shù)是二進制安全的 sds sdsnewlen(const void *init, size_t initlen) {void *sh;//sdshdr的指針sds s; //char * s;char type = sdsReqType(initlen);//根據(jù)需要的長度決定sdshdr的類型/* 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;//如果initlen為空并且sdshdr的類型為sdshdr5，則將類型設(shè)置為sdshdr8int hdrlen = sdsHdrSize(type);//每個sdshdr類型的大小都不一樣，根據(jù)類型返回sdshdr的大小以計算需要分配的空間unsigned char *fp; /* flags pointer. */sh = s_malloc(hdrlen+initlen+1);//在heap里申請一段連續(xù)的空間給sdshdr和屬于它的sds，+1是因為要在尾部放置'\0'if (!init)memset(sh, 0, hdrlen+initlen+1);//如果init為空，則整個sdshdr都用0即字符'\0'初始化if (sh == NULL) return NULL;s = (char*)sh+hdrlen;//通過sdshdr指針找到sds的位置fp = ((unsigned char*)s)-1;//找到flags的位置，等同于&s[-1]switch(type) {case SDS_TYPE_5: {*fp = type | (initlen << SDS_TYPE_BITS);//initlen左移3位到高5位，給type騰出位置，和type做或運算break;}case SDS_TYPE_8: {SDS_HDR_VAR(8,s);//#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T))); 可以理解為在switch作用域下申明了一個新的局部變量sh，類型是struct sdshdr##T，跟外面的sh值一樣，變量名一樣，但不是一個東西。sh->len = initlen;sh->alloc = initlen;*fp = type;//設(shè)置flagsbreak;}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); //memcpy不會因為'\0'而停下，支持二進制數(shù)據(jù)的拷貝s[initlen] = '\0'; //不管是不是二進制數(shù)據(jù)，尾部都會加上'\0'return s; } static inline int sdsHdrSize(char type) {switch(type&SDS_TYPE_MASK) {case SDS_TYPE_5:return sizeof(struct sdshdr5);//之前說的柔性數(shù)組成員不會計入struct的大小，所以這個hdrsize沒有包括sds的長度case SDS_TYPE_8:return sizeof(struct sdshdr8);case SDS_TYPE_16:return sizeof(struct sdshdr16);case SDS_TYPE_32:return sizeof(struct sdshdr32);case SDS_TYPE_64:return sizeof(struct sdshdr64);}return 0; }

流程如下:

根據(jù)sds的長度判斷需要選用sdshdr的類型
根據(jù)sdshdr的類型用sdsHdrSize函數(shù)得到hdrlen(其實就是sizeof(struct sdshdr))
為sdshdr分配一個hdrlen+initlen+1大小的堆內(nèi)存(+1是為了放置'\0'，這個'\0'不計入alloc或len)
按參數(shù)填充成員變量len、alloc和type
用memcpy給sds賦值，并在尾部加上'\0'

下面是sdsMakeRoomFor的源碼:

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;elsenewlen += 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的代碼:?

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; }

2.sds縮減

我粗略地在源碼里找了找，縮短sds字符串的有三個函數(shù):sdsclear、sdstrim、sdsrange，他們都不會改變alloc的大小即不會釋放任何內(nèi)存，這就是sds字符串內(nèi)存管理的一種方式:惰性釋放。額外調(diào)用sdsRemoveFreeSpace釋放內(nèi)存，這樣就節(jié)省了每次sds縮減長度而導(dǎo)致的內(nèi)存釋放開銷。
三個縮短sds的函數(shù)就不一一介紹了，有興趣直接去代碼里看就好，需要注意的這些函數(shù)里移動字符串用的memmove()是允許內(nèi)存重疊的，這點跟memcpy()不一樣。
下面介紹一下sdsRemoveFreeSpace，先放源碼:

//這個函數(shù)壓縮內(nèi)存，讓alloc=len。如果type變小了，則另開一片內(nèi)存復(fù)制，如果type不變，則realloc sds sdsRemoveFreeSpace(sds s) {void *sh, *newsh;char type, oldtype = s[-1] & SDS_TYPE_MASK;int hdrlen;size_t len = sdslen(s);sh = (char*)s-sdsHdrSize(oldtype);type = sdsReqType(len);hdrlen = sdsHdrSize(type);//這之后的代碼就跟sdsMakeRoomFor后面的代碼差不多了，釋放掉多余內(nèi)存并重置alloc。if (oldtype==type) {newsh = s_realloc(sh, hdrlen+len+1);if (newsh == NULL) return NULL;s = (char*)newsh+hdrlen;} else {newsh = s_malloc(hdrlen+len+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, len);return s; }

?總之：sds簡單動態(tài)字符串的優(yōu)點(重復(fù)下上面的一段提示)