Redis內部數據結構SDS詳解
本文轉載自微信公眾號「 學習Java的小姐姐」，作者學習Java的小姐姐0618。轉載本文請聯系學習Java的小姐姐公眾號。
前言
Redis是使用C寫的，而C中根本不存在string,list,hash，set和zset這些數據類型，那么C是如何將這些數據類型實現出來的呢?我們從該篇開始，就要開始分析源碼啦??。
API使用
我們這篇來學習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。
embstr和raw的區別
所有類型的數據結構最外層都是RedisObject，這部分會說，先這樣大致了解下，因為這篇的重點不在這。如果字符串小于等于44，實際的數據和RedisObject在內存中地址相鄰，如下圖。
如果字符串大于44，實際的數據和RedisObject在內存中地址不相鄰，如下圖。
再次強調，這些不重要，以后會講，現在提下，只是為了能讓Redis的String類型有個大致了解，先從整體把握。我們今天要說的其實是實際的數據，即上圖指針指向的位置??。
SDSHdr的定義
其實的數據并不是直接存儲，也有封裝，看下面的代碼就知道分為五種，分別是sdshdr5，sdshdr8，sdshdr16，sdshdr32，sdshdr64。sdshdr5和另外四種的區別比較明顯，sdshrd5其實對內存空間的更加節約。其他四種乍一看都差不多，包括已用長度len，總長度alloc，標記flags(感覺沒啥用，要是有知道的小伙伴，歡迎指教)，實際數據buf。
- //定義五種不同的結構體，sdshdr5,sdshdr8, sdshdr16,sdshdr32,sdshdr64
- struct __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，但是各個類型都差不多，所以下圖加簡單畫了。
SDS的優勢
我們可以看到是對字符數組的再封裝，但是為什么呢，直接使用字符數組不是更簡單嗎?這要從C和Java語言的根本區別說起。
更快速的獲取字符串長度
我們都知道Java的字符串有提供length方法，列表有提供size方法，我們可以直接獲取大小。但是C卻不一樣，更偏向底層實現，所以沒有直接的方法使用。這樣就帶來一個問題，如果我們想要獲取某個數組的長度，就只能從頭開始遍歷，當遇到第一個'\0'則表示該數組結束。這樣的速度太慢了，不能每次因為要獲取長度就變量數組。所以設計了SDS數據結構，在原來的字符數組外面增加總長度，和已用長度，這樣每次直接獲取已用長度即可。復雜度為O(1)。
數據安全，不會截斷
如果傳統字符串保存圖片，視頻等二進制文件，中間可能出現'\0'，如果按照原來的邏輯，會造成數據丟失。所以可以用已用長度來表示是否字符數組已結束。
SDS關鍵代碼分析
獲取常見值(抽象出常見方法)
在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) {
- case SDS_TYPE_5://0
- return SDS_TYPE_5_LEN(flags);
- case SDS_TYPE_8://1
- return SDS_HDR(8,s)->len;//取上面結構體sdshdr8的len
- case SDS_TYPE_16://2
- return SDS_HDR(16,s)->len;
- case SDS_TYPE_32://3
- return SDS_HDR(32,s)->len;
- case 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) {
- case SDS_TYPE_5: {
- return 0;
- }
- case SDS_TYPE_8: {
- SDS_HDR_VAR(8,s);
- return sh->alloc - sh->len;
- }
- case SDS_TYPE_16: {
- SDS_HDR_VAR(16,s);
- return sh->alloc - sh->len;
- }
- case SDS_TYPE_32: {
- SDS_HDR_VAR(32,s);
- return sh->alloc - sh->len;
- }
- case SDS_TYPE_64: {
- SDS_HDR_VAR(64,s);
- return sh->alloc - sh->len;
- }
- }
- return 0;
- }
- //設置sdshdr的len
- static inline void sdssetlen(sds s, size_t newlen) {
- unsigned char flags = s[-1];
- switch(flags&SDS_TYPE_MASK) {
- case SDS_TYPE_5:
- {
- unsigned char *fp = ((unsigned char*)s)-1;
- *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
- }
- break;
- case SDS_TYPE_8:
- SDS_HDR(8,s)->len = newlen;
- break;
- case SDS_TYPE_16:
- SDS_HDR(16,s)->len = newlen;
- break;
- case SDS_TYPE_32:
- SDS_HDR(32,s)->len = newlen;
- break;
- case 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) {
- case 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;
- case SDS_TYPE_8:
- SDS_HDR(8,s)->len += inc;
- break;
- case SDS_TYPE_16:
- SDS_HDR(16,s)->len += inc;
- break;
- case SDS_TYPE_32:
- SDS_HDR(32,s)->len += inc;
- break;
- case 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) {
- case SDS_TYPE_5:
- return SDS_TYPE_5_LEN(flags);
- case SDS_TYPE_8:
- return SDS_HDR(8,s)->alloc;
- case SDS_TYPE_16:
- return SDS_HDR(16,s)->alloc;
- case SDS_TYPE_32:
- return SDS_HDR(32,s)->alloc;
- case SDS_TYPE_64:
- return SDS_HDR(64,s)->alloc;
- }
- return 0;
- }
- //設置sdshdr的總長度
- static inline void sdssetalloc(sds s, size_t newlen) {
- unsigned char flags = s[-1];
- switch(flags&SDS_TYPE_MASK) {
- case SDS_TYPE_5:
- /* Nothing to do, this type has no total allocation info. */
- break;
- case SDS_TYPE_8:
- SDS_HDR(8,s)->alloc = newlen;
- break;
- case SDS_TYPE_16:
- SDS_HDR(16,s)->alloc = newlen;
- break;
- case SDS_TYPE_32:
- SDS_HDR(32,s)->alloc = newlen;
- break;
- case SDS_TYPE_64:
- SDS_HDR(64,s)->alloc = newlen;
- break;
- }
- }
創建對象
我們通過sdsnew方法來創建對象，顯示通過判斷init是否為空來確定初始大小，接著調用方法sdsnew(這邊方法名一樣，但是參數不一樣，其為方法的重載)，先根據長度確定類型(上面有提過五種類型，不記得的可以往上翻)，然后根據類型分配相應的內存資源，最后追加C語言的結尾符'\0'。
- 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)
- memset(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) {
- case SDS_TYPE_5: {
- *fp = type | (initlen << 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)
- memcpy(s, init, initlen);
- //最后追加'\0'
- s[initlen] = '\0';
- 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類型的刪除并不是直接回收內存，而是修改字符，讓其為空字符，這其實是惰性釋放，等待將來使用。在調用sdsempty方法時，再次調用上面的sdsnewlen方法。
- /*修改sds字符串使其為空（零長度）。
- *但是，所有現有緩沖區不會被丟棄，而是設置為可用空間
- *這樣，下一個append操作將不需要分配到
- *當要縮短SDS保存的字符串時，程序并不立即使用內存充分配來回收縮短后多出來的字節，并等待將來使用。*/
- void sdsclear(sds s) {
- sdssetlen(s, 0);
- s[0] = '\0';
- }
- sds sdsempty(void) {
- return sdsnewlen("",0);
- }
添加字符(擴容)重點!!!
添加字符串，sdscat輸入參數為sds和字符串t，首先調用sdsMakeRoomFor擴容方法，再追加新的字符串，最后添加上結尾符'\0'。我們來看下擴容方法里面是如何實現的?第一步先調用常見方法中的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);
- sdssetlen(s, curlen+len);
- s[curlen+len] = '\0';
- 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;
- else //當新長度大于 1024*1024，加2014*1024
- newlen += 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 {//如果類型不一樣，重新開辟內存，把原來的數據復制過去
- 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;
- }
- //計算不同類型的結構體的大小
- static inline int sdsHdrSize(char type) {
- switch(type&SDS_TYPE_MASK) {
- case SDS_TYPE_5:
- return sizeof(struct sdshdr5);
- 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;
- }
總結
該篇主要講了Redis的底層實現SDS，包括SDS是什么，與傳統的C語言相比的優勢，具體的邏輯圖，常見的方法(包括創建，刪除，擴容等)。同時也知道了Redis的embstr和raw的區別。
如果覺得寫得還行，麻煩給個贊??，您的認可才是我寫作的動力!
如果覺得有說的不對的地方，歡迎評論指出。
好了，拜拜咯。
