簡介
在redis內(nèi)部，string數(shù)據(jù)結(jié)構(gòu)的value主要以int诉植、sds作為結(jié)構(gòu)存儲。int用來存放整型昵观，sds用來存放字節(jié)晾腔、字符串、浮點型數(shù)據(jù)啊犬。
sds結(jié)構(gòu)分析
/* 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[];
};
sds一共有5種類型的header（sdshdr5 不再被使用了）灼擂。使得不同長度的字符串可以使用不同大小的header，從而節(jié)省內(nèi)存觉至。
接下來我們定義一個通用的sds結(jié)構(gòu)剔应，如下：
struct sdshdr {
XXX len; /* used */
XXX alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
- len：表示字符串的真正長度（不包含NULL結(jié)束符）；
- alloc：表示字符串的最大容量（不包含頭部和NULL結(jié)束符）语御；
- flags：占用一個字節(jié)峻贮，其中的最低3個bit用來表示header的類型，其余5個bit未使用沃暗。對應(yīng)類型如下：
#define SDS_TYPE_5 0
#define SDS_TYPE_8 1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4
- buf：字符數(shù)組月洛，存儲實際內(nèi)容。SDS 遵循 C 字符串以空字符結(jié)尾的慣例孽锥， 保存NULL字符的 1 字節(jié)空間不計算在SDS的len屬性嚼黔、alloc屬性里面细层， 并且為空字符分配額外的 1 字節(jié)空間。
sds優(yōu)勢
C 語言使用長度為 N+1 的字符數(shù)組來表示長度為 N 的字符串唬涧， 并且字符數(shù)組的最后一個元素總是NULL字符 '\0' 疫赎。這種簡單的字符串表示方式， 并不能滿足 Redis 對字符串在安全性碎节、效率捧搞、以及功能方面的要求。
常數(shù)復(fù)雜度獲取字符串長度
C 字符串并不記錄自身的長度信息狮荔， 所以為了獲取一個 C 字符串的長度胎撇， 程序必須遍歷整個字符串， 對遇到的每個字符進(jìn)行計數(shù)殖氏， 直到遇到代表字符串結(jié)尾的空字符為止晚树， 這個操作的復(fù)雜度為 O(N)；
sds記錄字符串長度雅采，可以直接返回len爵憎，復(fù)雜度為 O(1)；
杜絕緩沖區(qū)溢出
C 字符串不記錄自身長度帶來的另一個問題是容易造成緩沖區(qū)溢出婚瓜。
如上圖所示宝鼓，str1="hello"，str2="world"巴刻，str1與str2存儲在連續(xù)的內(nèi)存空間愚铡，接著對str1拼接“&hello”(c語言提供<string.h>/strcat 函數(shù)可以將 src 字符串中的內(nèi)容拼接到 dest 字符串的末尾：char *strcat(char *dest, const char *src);)，可以看到原先str2="world"被修改了冈涧。
sds的空間分配策略完全杜絕了發(fā)生緩沖區(qū)溢出的可能性： 當(dāng)sds API 需要對sds進(jìn)行修改時茂附， API 會先檢查sds的空間是否滿足修改所需的要求， 如果不滿足的話督弓， API 會自動將sds的空間擴(kuò)展至執(zhí)行修改所需的大小营曼， 然后才執(zhí)行實際的修改操作， 所以使用sds既不需要手動修改sds的空間大小愚隧， 也不會出現(xiàn)前面所說的緩沖區(qū)溢出問題蒂阱。
減少修改字符串時帶來的內(nèi)存重分配次數(shù)
每次增長或者縮短一個 C 字符串， 程序都總要對保存這個 C 字符串的數(shù)組進(jìn)行一次內(nèi)存重分配操作狂塘。內(nèi)存重分配涉及復(fù)雜的算法录煤， 并且可能需要執(zhí)行系統(tǒng)調(diào)用， 所以它通常是一個比較耗時的操作荞胡。
在sds中妈踊， buf 數(shù)組的長度不一定就是字符數(shù)量加一， 數(shù)組里面可以包含未使用的字節(jié)泪漂， 而這些字節(jié)的數(shù)量就由 SDS 的 alloc屬性 - len屬性來決定廊营。
sds通過空間預(yù)分配和惰性空間釋放兩種優(yōu)化策略來減少修改字符串時帶來的內(nèi)存重分配次數(shù)歪泳。
空間預(yù)分配
空間預(yù)分配策略如下：
- 如果對sds進(jìn)行修改之后， len < 1 MB 露筒， 則alloc = 2 * len呐伞，buf長度 = 2*len + 1；
- 如果對sds進(jìn)行修改之后慎式， len >= 1 MB 伶氢， 則alloc = len + 1MB，buf長度 = len + 1MB + 1byte瘪吏；
通過空間預(yù)分配策略癣防， Redis 可以減少連續(xù)執(zhí)行字符串增長操作所需的內(nèi)存重分配次數(shù)。
惰性空間釋放
惰性空間釋放用于優(yōu)化sds的字符串縮短操作： 當(dāng)需要縮短SDS保存的字符串時掌眠，程序并不立即使用內(nèi)存重分配來回收縮短后多出來的字節(jié)劣砍， 而是先預(yù)留著，并等待將來使用扇救。
當(dāng)然， sds也提供了相應(yīng)的API香嗓，讓我們可以在有需要時迅腔，真正地釋放 sds里面的未使用空間， 所以不用擔(dān)心惰性空間釋放策略會造成內(nèi)存浪費靠娱。
二進(jìn)制安全
對于C語言來說沧烈，C 字符串中的字符必須符合某種編碼（比如 ASCII）， 并且除了字符串的末尾之外像云， 字符串里面不能包含NULL字符锌雀， 否則最先被程序讀入的空字符將被誤認(rèn)為是字符串結(jié)尾 —— 這些限制使得 C 字符串只能保存文本數(shù)據(jù)， 而不能保存像圖片迅诬、音頻腋逆、視頻、壓縮文件這樣的二進(jìn)制數(shù)據(jù)侈贷。
sds的 API 都是二進(jìn)制安全的（binary-safe）： 所有sds API 都會以處理二進(jìn)制的方式來處理sds存放在buf數(shù)組里的數(shù)據(jù)惩歉， 程序不會對其中的數(shù)據(jù)做任何額外的處理，數(shù)據(jù)在寫入時是什么樣的俏蛮，它被讀取時就是什么樣撑蚌。也就是說相比C語言字符串，SDS會通過len來限制讀取長度搏屑，而非“\0”争涌，所以保證了二進(jìn)制安全。
因此sds既可以保存文本數(shù)據(jù)辣恋， 又能保存二進(jìn)制數(shù)據(jù)亮垫。
兼容部分 C 字符串函數(shù)
通過遵循C字符串以NULL字符結(jié)尾的慣例模软， sds可以使用部分 <string.h> 庫中的函數(shù)。
