sds(sds抑郁自測題)

來源：https://www.cnblogs.com/chenchen0618/p/13041715.html

Redis是使用C寫的，而C中根本不存在string,list,hash，t和zt這些數據類型，那么C是如何將這些數據類型實現出來的呢？我們從該篇開始，就要開始分析源碼啦。

我們這篇來學習string的底層實現，首先看下API的簡單應用，設置str1變量為helloworld，然后我們使用debug object +變量名的方式看下，注意標紅的編碼為embstr。

如果我們將str2設置為helloworldhelloworldhelloworldhelloworldhell，字符長度為44，再使用下debug object+變量名的方式看下，注意標紅的編碼為embstr。

?但是當我們設置為helloworldhelloworldhelloworldhelloworldhello，字符長度為45，再使用debug object+變量名的方式看下，注意標紅的編碼為raw。

最后我們將str3設置為整數100，再使用debug object+變量名的方式看下，注意標紅的編碼為int。

所以Redis的string類型一共有三種存儲方式，當字符串長度小于等于44，底層采用embstr；當字符串長度大于44，底層采用raw；當設置是整數，底層則采用int。

所有類型的數據結構最外層都是RedisObject，這部分會說，先這樣大致了解下，因為這篇的重點不在這。如果字符串小于等于44，實際的數據和RedisObject在內存中地址相鄰，如下圖。

如果字符串大于44，實際的數據和RedisObject在內存中地址不相鄰，如下圖。

再次強調，這些不重要，以后會講，現在提下，只是為了能讓Redis的String類型有個大致了解，先從整體把握。我們今天要說的其實是實際的數據，即上圖指針指向的位置。

其實的數據并不是直接存儲，也有封裝，看下面的代碼就知道分為五種，分別是sdshdr5，sdshdr8，sdshdr16，sdshdr32，sdshdr64。sdshdr5和另外四種的區別比較明顯，sdshrd5其實對內存空間的更加節約。其他四種乍一看都差不多，包括已用長度len，總長度alloc，標記flags（感覺沒啥用，要是有知道的小伙伴，歡迎指教），實際數據buf。

//定義五種不同的結構體，sdshdr5,sdshdr8, sdshdr16,sdshdr32,sdshdr64struct __attribute__ ((__packed__)) sdshdr5 { unsigned char flags; // 8位的標記 char buf[];//實際數據的指針 };struct __attribute__ ((__packed__)) sdshdr8 { uint8_t len; /* 已使用長度 */ uint8_t alloc; /* 總長度*/ unsigned char flags; char buf[];};struct __attribute__ ((__packed__)) sdshdr16 { uint16_t len; uint16_t alloc; unsigned char flags; char buf[];};struct __attribute__ ((__packed__)) sdshdr32 { uint32_t len; uint32_t alloc; unsigned char flags; char buf[];};struct __attribute__ ((__packed__)) sdshdr64 { uint64_t len; uint64_t alloc; unsigned char flags; char buf[];};SDS具體邏輯圖

假設我們設置某個字符串為hello，那么他SDS的可用長度len為8，已用長度len為6，如下圖。注意：Redis會根據具體的字符長度，選擇相應的sdshdr，但是各個類型都差不多，所以下圖加簡單畫了。

?

我們可以看到是對字符數組的再封裝，但是為什么呢，直接使用字符數組不是更簡單嗎？這要從C和Java語言的根本區別說起。

我們都知道Java的字符串有提供length方法，列表有提供size方法，我們可以直接獲取大小。但是C卻不一樣，更偏向底層實現，所以沒有直接的方法使用。這樣就帶來一個問題，如果我們想要獲取某個數組的長度，就只能從頭開始遍歷，當遇到第一個''則表示該數組結束。這樣的速度太慢了，不能每次因為要獲取長度就變量數組。所以設計了SDS數據結構，在原來的字符數組外面增加總長度，和已用長度，這樣每次直接獲取已用長度即可。復雜度為O(1)。

如果傳統字符串保存圖片，視頻等二進制文件，中間可能出現''，如果按照原來的邏輯，會造成數據丟失。所以可以用已用長度來表示是否字符數組已結束。

在sds.h中寫了一些常見方法，比如計算sds的長度（即sdshdr的len），計算sds的空閑長度（即sdshdr的可用長度alloc-已用長度len），計算sds的可用長度(即sdshdr的alloc)等等。但是大家有沒有疑問，這不是一行代碼搞定的事嗎，為啥要抽象出方法呢？那么問題在于在上面，我們有將sdshdr分為五種類型，分別是sdshdr5，sdshdr8，sdshdr16，sdshdr32，sdshdr64。那么我們在實際使用的時候，想要區分當前是哪個類型，并取其相應字段或設置相應字段。

//計算sds對應的字符串長度，其實上取得是字符串所對應的哪種sdshdr的len值 static inline size_t sdslen(const sds s) { // 柔性數組不占空間，所以倒數第二位的是flags unsigned char flags = s[-1]; //flags與上面定義的宏變量7做位運算 switch(flags&SDS_TYPE_MASK) { ca SDS_TYPE_5://0 return SDS_TYPE_5_LEN(flags); ca SDS_TYPE_8://1 return SDS_HDR(8,s)->len;//取上面結構體sdshdr8的len ca SDS_TYPE_16://2 return SDS_HDR(16,s)->len; ca SDS_TYPE_32://3 return SDS_HDR(32,s)->len; ca SDS_TYPE_64://5 return SDS_HDR(64,s)->len; } return 0;}//計算sds對應的空余長度，其實上是alloc-len static inline size_t sdsavail(const sds s) { unsigned char flags = s[-1]; switch(flags&SDS_TYPE_MASK) { ca SDS_TYPE_5: { return 0; } ca SDS_TYPE_8: { SDS_HDR_VAR(8,s); return sh->alloc - sh->len; } ca SDS_TYPE_16: { SDS_HDR_VAR(16,s); return sh->alloc - sh->len; } ca SDS_TYPE_32: { SDS_HDR_VAR(32,s); return sh->alloc - sh->len; } ca SDS_TYPE_64: { SDS_HDR_VAR(64,s); return sh->alloc - sh->len; } } return 0;}//設置sdshdr的len static inline void sdstlen(sds s, size_t newlen) { unsigned char flags = s[-1]; switch(flags&SDS_TYPE_MASK) { ca SDS_TYPE_5: { unsigned char *fp = ((unsigned char*)s)-1; *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS); } break; ca SDS_TYPE_8: SDS_HDR(8,s)->len = newlen; break; ca SDS_TYPE_16: SDS_HDR(16,s)->len = newlen; break; ca SDS_TYPE_32: SDS_HDR(32,s)->len = newlen; break; ca SDS_TYPE_64: SDS_HDR(64,s)->len = newlen; break; }}//給sdshdr的len添加多少大小 static inline void sdsinclen(sds s, size_t inc) { unsigned char flags = s[-1]; switch(flags&SDS_TYPE_MASK) { ca SDS_TYPE_5: { unsigned char *fp = ((unsigned char*)s)-1; unsigned char newlen = SDS_TYPE_5_LEN(flags)+inc; *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS); } break; ca SDS_TYPE_8: SDS_HDR(8,s)->len += inc; break; ca SDS_TYPE_16: SDS_HDR(16,s)->len += inc; break; ca SDS_TYPE_32: SDS_HDR(32,s)->len += inc; break; ca SDS_TYPE_64: SDS_HDR(64,s)->len += inc; break; }}//獲取sdshdr的總長度 static inline size_t sdsalloc(const sds s) { unsigned char flags = s[-1]; switch(flags&SDS_TYPE_MASK) { ca SDS_TYPE_5: return SDS_TYPE_5_LEN(flags); ca SDS_TYPE_8: return SDS_HDR(8,s)->alloc; ca SDS_TYPE_16: return SDS_HDR(16,s)->alloc; ca SDS_TYPE_32: return SDS_HDR(32,s)->alloc; ca SDS_TYPE_64: return SDS_HDR(64,s)->alloc; } return 0;}//設置sdshdr的總長度 static inline void sdstalloc(sds s, size_t newlen) { unsigned char flags = s[-1]; switch(flags&SDS_TYPE_MASK) { ca SDS_TYPE_5: /* Nothing to do, this type has no total allocation info. */ break; ca SDS_TYPE_8: SDS_HDR(8,s)->alloc = newlen; break; ca SDS_TYPE_16: SDS_HDR(16,s)->alloc = newlen; break; ca SDS_TYPE_32: SDS_HDR(32,s)->alloc = newlen; break; ca SDS_TYPE_64: SDS_HDR(64,s)->alloc = newlen; break; }}創建對象

我們通過sdsnew方法來創建對象，顯示通過判斷init是否為空來確定初始大小，接著調用方法sdsnew（這邊方法名一樣，但是參數不一樣，其為方法的重載），先根據長度確定類型（上面有提過五種類型，不記得的可以往上翻），然后根據類型分配相應的內存資源，最后追加C語言的結尾符''。

sds sdsnew(const char *init) { size_t initlen = (init == NULL) ? 0 : strlen(init); return sdsnewlen(init, initlen);}sds sdsnewlen(const void *init, size_t initlen) { void *sh; sds s; char type = sdsReqType(initlen);//根據長度確定類型 /*空字符串，用sdshdr8，這邊是經驗寫法，當想構造空串是為了放入超過32長度的字符串 */ 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) memt(sh, 0, hdrlen+initlen+1); if (sh == NULL) return NULL; s = (char*)sh+hdrlen; fp = ((unsigned char*)s)-1; //根據不同的類型，創建不同結構體，調用SDS_HDR_VAR函數 //為不同的結構體賦值,如已用長度len,總長度alloc switch(type) { ca SDS_TYPE_5: { *fp = type | (initlen << SDS_TYPE_BITS); break; } ca SDS_TYPE_8: { SDS_HDR_VAR(8,s); sh->len = initlen; sh->alloc = initlen; *fp = type; break; } ca SDS_TYPE_16: { SDS_HDR_VAR(16,s); sh->len = initlen; sh->alloc = initlen; *fp = type; break; } ca SDS_TYPE_32: { SDS_HDR_VAR(32,s); sh->len = initlen; sh->alloc = initlen; *fp = type; break; } ca 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] = ''; return s;}//根據實際字符長度確定類型 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 (LONG_MAX == LLONG_MAX) if (string_size < 1ll<<32) return SDS_TYPE_32;#endif return SDS_TYPE_64;}

刪除String類型的刪除并不是直接回收內存，而是修改字符，讓其為空字符，這其實是惰性釋放，等待將來使用。在調用sdmpty方法時，再次調用上面的sdsnewlen方法。

/*修改sds字符串使其為空（零長度）。*但是，所有現有緩沖區不會被丟棄，而是設置為可用空間*這樣，下一個append操作將不需要分配到*當要縮短SDS保存的字符串時，程序并不立即使用內存充分配來回收縮短后多出來的字節，并等待將來使用。void sdsclear(sds s) { sdstlen(s, 0); s[0] = '';}sds sdmpty(void) { return sdsnewlen("",0);}添加字符（擴容）重點！！！

添加字符串，sdscat輸入參數為sds和字符串t，首先調用sdsMakeRoomFor擴容方法，再追加新的字符串，最后添加上結尾符''。我們來看下擴容方法里面是如何實現的？第一步先調用常見方法中的sdsavail方法，獲取還剩多少空閑空間。如果空閑空間大于要添加的字符串t的長度，則直接返回，不想要擴容。如果空閑空間不夠，則想要擴容。第二步判斷想要擴容多大，這邊有分情況，如果目前的字符串小于1M，則直接擴容雙倍，如果目前的字符串大于1M，則直接添加1M。第三個判斷添加字符串之后的數據類型還是否和原來的一致，如果一致，則沒啥事。如果不一致，則想要新建一個sdshdr，把現有的數據都挪過去。

這樣是不是有點抽象，舉個例子，現在str的字符串為hello，目前是sdshdr8，總長度50，已用6，空閑44。現在想要添加長度為50的字符t，第一步想要看下是否要擴容，50明顯大于44，需要擴容。第二步擴容多少，str的長度小于1M，所以擴容雙倍，新的長度為50*2=100。第三步50+50所對應sdshdr類型還是sdshdr8嗎？明顯還是sdshdr8，所以不要數據遷移，還在原來的基礎上添加t即可。

sds sdscat(sds s, const char *t) { return sdscatlen(s, t, strlen(t));}sds sdscatlen(sds s, const void *t, size_t len) { //調用sds.h里面的sdslen，即取已用長度 size_t curlen = sdslen(s); //擴容方法 s = sdsMakeRoomFor(s,len); if (s == NULL) return NULL; memcpy(s+curlen, t, len); sdstlen(s, curlen+len); s[curlen+len] = ''; return s;}sds sdsMakeRoomFor(sds s, size_t addlen) { void *sh, *newsh; //調用sds.h，獲取空閑長度alloc size_t avail = sdsavail(s); size_t len, newlen; char type, oldtype = s[-1] & SDS_TYPE_MASK; int hdrlen; //空閑長度大于需要增加的，不需要擴容，直接返回 if (avail >= addlen) return s;//調用sds.h里面的sdslen，即取可用長度 len = sdslen(s); sh = (char*)s-sdsHdrSize(oldtype); //len加上要添加的大小 newlen = (len+addlen); //#define SDS_MAX_PREALLOC (1024*1024) //當新長度小于 1024*1024，直接擴容兩倍 if (newlen < SDS_MAX_PREALLOC) newlen *= 2; el //當新長度大于 1024*1024，加2014*1024 newlen += SDS_MAX_PREALLOC;//根據長度計算新的類型 type = sdsReqType(newlen); /* Don't u type 5: the ur 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; } el {//如果類型不一樣，重新開辟內存，把原來的數據復制過去 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; sdstlen(s, len); } //設置新的總長度 sdstalloc(s, newlen); return s;}//計算不同類型的結構體的大小 static inline int sdsHdrSize(char type) { switch(type&SDS_TYPE_MASK) { ca SDS_TYPE_5: return sizeof(struct sdshdr5); ca SDS_TYPE_8: return sizeof(struct sdshdr8); ca SDS_TYPE_16: return sizeof(struct sdshdr16); ca SDS_TYPE_32: return sizeof(struct sdshdr32); ca SDS_TYPE_64: return sizeof(struct sdshdr64); } return 0;}總結

該篇主要講了Redis的底層實現SDS，包括SDS是什么，與傳統的C語言相比的優勢，具體的邏輯圖，常見的方法（包括創建，刪除，擴容等）。同時也知道了Redis的embstr和raw的區別。如果覺得寫得還行，麻煩給個贊，您的認可才是我寫作的動力！

如果覺得有說的不對的地方，歡迎評論指出。