SDS(simple dynamic string)是redis提供的字符串的封裝，在redis中也是存在最廣泛的數據結構，它也是很多其他數據結構的基礎，所以才選擇先介紹SDS。 SDS也兼容部分C字符串API(strcmp,strlen)，它如何兼容C字符串我覺得也是有個很sao的操作，等看完我這篇博客你就明白了。在開始正式內容前，我先拋幾個問題(有些也是面試高頻題)，帶著問題去學習也是一種非常好的學習方法。
- C語言中也算是支持String了，為什么Redis還要自己封裝一個？
- SDS中的D(dynamic)到底是什么含義？
- SDS的數據結構是啥樣的？為什么要那么設計？
- SDS是如何兼容C字符串的?
Redis中sds相關的源碼都在src/sds.c 和src/sds.h中（鏈接可以直接跳轉到我中文注釋版redis源碼），其中sds.h中定義了所有SDS的api，當然也實現了部分幾個api，比如sds長度、sds剩余可用空間……，不急著看代碼，我們先看下sds的數據結構，看完后為什么代碼那么寫你就一目了然。
sdshdr數據結構
redis提供了sdshdr5 sdshdr8 sdshdr16 sdshdr32 sdshdr64這幾種sds的實現，其中除了sdshdr5比較特殊外，其他幾種sdshdr差不只在于兩個字段的類型差別。我就拿 sdshdr8和sdshdr16來舉例，其struct定義分別如下。
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* 已使用空間大小 */
uint8_t alloc; /* 總共可用的字符空間大小，應該是實際buf的大小減1(因為c字符串末尾必須是,不計算在內) */
unsigned char flags; /* 標志位，主要是識別這是sdshdr幾，目前只用了3位，還有5位空余 */
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[];
};
sdshdr32 sdshdr64也和上面的結構一致，差別只在于len和alloc的數據類型不一樣而已。相較于c原生的字符串，sds多了len、alloc、flag三個字段來存儲一些額外的信息，redis考慮到了字符串拼接時帶來的巨大損耗，所以每次新建sds的時候會預分配一些空間來應對未來的增長，sds和C string的關系熟悉JAVA的旁友可能會決定就好比java中String和StringBuffer的關系。正是因為預留空間的機制，所以redis需要記錄下來已分配和總空間大小，當然可用空間可用直接算出來。
下一個問題，為什么redis費心費力要提供sdshdr5到sdshdr64這五種SDS呢？我覺著這只能說明Redis作者摳內存摳到機制，犧牲了代碼的簡潔性換取了每個sds省下來的幾個字節的內存空間。從sds初始化方法sdsnew和sdsnewlen中我們就可以看出，redis在新建sds時需要傳如初始化長度，然后根據初始化的長度確定用哪種sdshdr，小于2^8長度的用sdshdr8，這樣len和alloc只占用兩個字節，比較短字符串可能非常多，所以節省下來的內存還是非常可觀的，知道了sds的數據結構和設計原理，sdsnewlen的代碼就非常好懂了，如下：
sds sdsnewlen(const void *init, size_t initlen) {
void *sh; sds s; // 根據初始化的長度確定用哪種sdshdr char type = sdsReqType(initlen);
/* 空字符串大概率之后會Append，但sdshdr5不適合用來append，所以直接替換成sdshdr8 */ 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 (sh == NULL) return NULL;
if (init==SDS_NOINIT)
init = NULL; else if (!init)
memset(sh, 0, hdrlen+initlen+1);
/* 注意：返回的s并不是直接指向sds的指針，而是指向sds中字符串的指針，sds的指針還需要 * 根據s和hdrlen計算出來 */ s = (char*)sh+hdrlen;
fp = ((unsigned char*)s)-1;
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); s[initlen] = '';
return s;
}
SDS的使用
上面代碼中我特意標注了一個注意，sdsnewlen()返回的sds指針并不是直接指向sdshdr的地址，而是直接指向了sdshdr中buf的地址。這樣做有啥好處？好處就是這樣可以兼容c原生字符串。buf其實就是C 原生字符串+部分空余空間，中間是特殊符號''隔開，‘’有是標識C字符串末尾的符號，這樣就實現了和C原生字符串的兼容，部分C字符串的API也就可以直接使用了。 當然這也有壞處，這樣就沒法直接拿到len和alloc的具體值了，但是也不是沒有辦法。
當我們拿到一個sds，假設這個sds就叫s吧，其實一開始我們對這個sds一無所知，連他是sdshdr幾都不知道，這時候可以看下s的前面一個字節，我們已經知道sdshdr的數據結構了，前一個字節就是flag，根據flag具體的值我們就可以推斷出s具體是哪個sdshdr，也可以推斷出sds的真正地址，相應的就知道了它的len和alloc，知道了這點，下面這些有點晦澀的代碼就很好理解了。
oldtype = s[-1] & SDS_TYPE_MASK; // SDS_TYPE_MASK = 7 看下s前面一個字節(flag)推算出sdshdr的類型。
// 這個宏定義直接推算出sdshdr頭部的內存地址#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)// 獲取sds支持的長度 static inline size_t sdslen(const sds s) { unsigned char flags = s[-1]; // -1 相當于獲取到了sdshdr中的flag字段
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
... // 省略 SDS_TYPE_16 SDS_TYPE_32的代碼…… case SDS_TYPE_64: return SDS_HDR(64,s)->len;
} return 0;
}// 獲取sds剩余可用空間大小 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;
} ... // 省略 SDS_TYPE_16 SDS_TYPE_32的代碼…… case SDS_TYPE_64: { SDS_HDR_VAR(64,s);
return sh->alloc - sh->len;
} } return 0;
}/* 返回sds實際的起始位置指針 */void *sdsAllocPtr(sds s) { return (void*) (s-sdsHdrSize(s[-1]));
}
SDS的擴容
在做字符串拼接的時候，sds可能剩余的可用空間不足，這個時候需要擴容，什么時候該擴容，又該怎么擴? 這是不得不考慮的問題。Java中很多數據結構都有動態擴容的機制，比如和sds很類似的StringBuffer，HashMap，他們都會在使用過程中動態判斷是否空間充足，而且基本上都采用了先指數擴容，然后到一定大小限制后才開始線性擴容的方式，Redis也不例外，Redis在10241024以內都是2倍的方式擴容，只要不超出10241024都是先額外申請200%的空間，但一旦總長度超過10241024字節，那每次最多只會擴容10241024字節。 Redis中sds擴容的代碼是在sdsMakeRoomFor()，可以看到很多字符串變更的API開頭都直接或者間接調用這個。 和Java中StringBuffer擴容不同的是，Redis這里還需要考慮不同字符串長度時sdshdr類型的變化，具體代碼如下：
// 擴大sds的實際可用空間，以便后續能拼接更多字符串。
// 注意：這里實際不會改變sds的長度，只是增加了更多可用的空間(buf) 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; // SDS_TYPE_MASK = 7
int hdrlen; /* 如果有足夠的剩余空間，直接返回 */ if (avail >= addlen) return s;
len = sdslen(s);
sh = (char*)s-sdsHdrSize(oldtype);
newlen = (len+addlen);
// 在未超出SDS_MAX_PREALLOC前，擴容都是按2倍的方式擴容，超出后只能遞增
if (newlen < SDS_MAX_PREALLOC) // SDS_MAX_PREALLOC = 1024*1024
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC; type = sdsReqType(newlen);
/* 在真正使用過程中不會用到type5，如果遇到type5直接使用type8*/ 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;
}
常用API
sds.c還有很多源碼我都沒有貼到，其他代碼本質上都是圍繞sdshdr數據結構和各種字符串操作寫的(基本上都是各種字符串新建、拼接、拷貝、擴容……)，只要知道了sds的設計原理，相信你也能輕易寫出來，這里我就列一下所有sds相關的API，對源碼有興趣的旁友可以移步到src/sds.c，中文注釋版的API列表見src/sds.c
sds sdsnewlen(const void *init, size_t initlen); // 新建一個容量為initlen的sds
sds sdsnew(const char *init); // 新建sds，字符串為null，默認長度0
sds sdsempty(void); // 新建空字符“”
sds sdsdup(const sds s); // 根據s的實際長度創建新的sds，目的是降低內存的占用
void sdsfree(sds s); // 釋放sds
sds sdsgrowzero(sds s, size_t len); // 把sds增長到指定的長度，增長出來的新的空間用0填充
sds sdscatlen(sds s, const void *t, size_t len); // 在sds上拼接字符串t的指定長度部分
sds sdscat(sds s, const char *t); // 把字符串t拼接到sds上
sds sdscatsds(sds s, const sds t); // 把兩個sds拼接在一起
sds sdscpylen(sds s, const char *t, size_t len); // 把字符串t指定長度的部分拷貝到sds上
sds sdscpy(sds s, const char *t); // 把字符串t拷貝到sds上
sds sdscatvprintf(sds s, const char *fmt, va_list ap); // 把用printf格式化后的字符拼接到sds上
sds sdscatfmt(sds s, char const *fmt, ...); // 將多個參數格式化成一個字符串后拼接到sds上
sds sdstrim(sds s, const char *cset); // 在sds中移除開頭或者末尾在cset中的字符
void sdsrange(sds s, ssize_t start, ssize_t end); // 截取sds的子串
void sdsupdatelen(sds s); // 更新sds字符串的長度
void sdsclear(sds s); // 清空sds中的內容，但不釋放空間
int sdscmp(const sds s1, const sds s2); // sds字符串比較大小
sds *sdssplitlen(const char *s, ssize_t len, const char *sep, int seplen, int *count);void sdsfreesplitres(sds *tokens, int count);void sdstolower(sds s); // 字符串轉小寫
void sdstoupper(sds s); // 字符串轉大寫
sds sdsfromlonglong(long long value); // 把一個long long型的數轉成sds
sds sdscatrepr(sds s, const char *p, size_t len); sds *sdssplitargs(const char *line, int *argc);sds sdsmapchars(sds s, const char *from, const char *to, size_t setlen);sds sdsjoin(char **argv, int argc, char *sep); // 把字符串數組按指定的分隔符拼接起來
sds sdsjoinsds(sds *argv, int argc, const char *sep, size_t seplen); // 把sds數組按指定的分隔符拼接起來
/* sds底層api */
sds sdsMakeRoomFor(sds s, size_t addlen); // sds擴容
void sdsIncrLen(sds s, ssize_t incr); // 擴容指定長度
sds sdsRemoveFreeSpace(sds s); // 釋放sds占用的多余空間
size_t sdsAllocSize(sds s); // 返回sds總共占用的內存大小
void *sdsAllocPtr(sds s); // 返回sds實際的起始位置指針
void *sds_malloc(size_t size); // 為sds分配空間
void *sds_realloc(void *ptr, size_t size); //
void sds_free(void *ptr); // 釋放sds空間
結語
回到開篇的幾個問題，相信看完上面的內容后你都能回答上來了，如果回答不上來那就再多看兩遍，本博客+源碼搭配服用效果更佳。
為了控制博客篇幅，這里只講解了核心代碼，很多API的源碼我都沒有貼上來(畢竟太多)，有興趣的同學可以再看下源碼 https://github.com/xindoo/redis/。
本文是Redis源碼剖析系列博文，同時也有與之對應的Redis中文注釋版，有想深入學習Redis的同學，歡迎star和關注。 Redis中文注解版倉庫：https://github.com/xindoo/redis
Redis源碼剖析專欄：https://zxs.io/s/1h
本文來自https://blog.csdn.net/xindoo
