【死磕 Redis】----- Redis 數(shù)據(jù)結(jié)構(gòu)：sds
字符串使我們在編程過程中使用最為廣泛的對象了，在 Redis 中同樣如此。我們知道 Redis 是 C 語言實現(xiàn)的，但是 Redis 放棄了 C 語言傳統(tǒng)的字符串而是自己創(chuàng)建了一種名為簡單動態(tài)字符串 SDS（Simple Dynamic String）的抽象類型，并將 SDS 用作 Redis 的默認(rèn)字符串表示，其主要原因就是傳統(tǒng)的字符串表示方式并不能滿足 Redis 對字符串在安全性、效率、以及功能方面的要求。所以這篇文章就來說說 SDS。
在 Redis 里面，只會將 C 語言字符串當(dāng)做字符串字面量，用于一些無須對字符串進行修改的地方，比如打印日志。在大多數(shù)場景下，Redis 都是使用 SDS 來作為字符串的表示。
對比 C 語言字符串，SDS 具有如下優(yōu)點：
常數(shù)復(fù)雜度獲取字符串長度。
杜絕緩沖區(qū)溢出。
減少修改字符串長度時所需的內(nèi)存重分配次數(shù)。
二進制安全。
兼容部分 C 字符串函數(shù)。
SDS 的定義
SDS 的源碼主要實現(xiàn)在 sds.c 和 sds.h 兩個文件中。其定義為：
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[];
};
從上述代碼可以看出，每一個 sdshdr 都是由以下幾個部分組成（sdshdr5除外）：
len：SDS 字符串已使用的空間
alloc：申請的空間，減去len就是未使用的空間，初始時和len一致。
flag：只使用了低三位表示類型，細(xì)化了SDS的分類，根據(jù)字符串的長度的不同選擇不同的 SDS 結(jié)構(gòu)體，而結(jié)構(gòu)體的主要區(qū)別是 len 和 alloc 的類型，這樣做可以節(jié)省一部分空間大小，畢竟在 Redis 字符串非常多，進一步的可以節(jié)省空間。
buf：char 類型數(shù)組，表示不定長字符串。
SDS 采用一段連續(xù)的內(nèi)存空間來存儲字符串，下圖是字符串 “Redis” 在內(nèi)存中的示例圖：
SDS 與 C 字符串的區(qū)別
SDS相比C字符串，在安全性、性能、功能性具有優(yōu)勢：
安全性：防止緩沖區(qū)溢出、二進制安全
性能：獲取字符串長度、空間預(yù)分配、惰性釋放
功能性：二進制安全、兼容部分C字符串函數(shù)
緩沖區(qū)溢出
緩沖區(qū)溢出（buffer overflow）：是這樣的一種異常，當(dāng)程序?qū)?shù)據(jù)寫入緩沖區(qū)時，會超過緩沖區(qū)的邊界，并覆蓋相鄰的內(nèi)存位置。
C 字符串不記錄自身長度，不會自動進行邊界檢查，所以會增加溢出的風(fēng)險。如下面函數(shù)
char* strcat(char* dest, const char* src);
該函數(shù)是將 src 字符串內(nèi)容拼接到 dest 字符串的末尾。假如有 s1 = “Redis”，s2 = "MongoDB"，如下：
當(dāng)執(zhí)行 strcat(s1,'Cluster') 時，未給 s1 分配足夠的內(nèi)存空間，s1 的數(shù)據(jù)將會溢出到 s2 所在的內(nèi)存空間，導(dǎo)致 s2 保存的內(nèi)容被修改，如下：
與 C 字符串不同，SDS 杜絕了發(fā)生緩存溢出的可能性，他會按照如下步驟進行：
先檢查 SDS 的空間是否滿足修改所需的要求
如果不滿足要求的話，API 會自動將 SDS 的空間擴展到執(zhí)行修改所需的大小
最后才是執(zhí)行實際的修改操作
例子可見：sds.c/sdscat：
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;
}
常數(shù)復(fù)雜度獲取字符串長度
我們知道 C 字符串是不會記錄自身的長度信息，因此我們要獲取一個 C 字符串的長度，需要變臉整個字符串，直到遇到第一個 '\0'，復(fù)雜度為 O(n)。但是 SDS 記錄了自身長度 len，因此其復(fù)雜度降為 O(1) 就能獲取字符串的長度。
空間預(yù)分配
當(dāng) SDS 的 API 要對一個 SDS 進行修改，并且需要對 SDS 進行空間擴展的時候，程序不僅會為 SDS 分配修改所必須要的空間，還會為 SDS 分配額外的未使用的空間，具體策略見 sds.c/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;
else
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 {
/* 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;
}
如果對 SDS 進行修改后，SDS 的長度小于 1MB，那么則擴大兩倍，若 SDS 的長度大于等于 1MB，那么則會增加 1MB。
通過空間預(yù)分配策略，Redis 可以減少聯(lián)系執(zhí)行字符串增長操作所需的內(nèi)存分配次數(shù)。
惰性釋放
預(yù)分配空間用于優(yōu)化 SDS 字符串增長操作，惰性釋放則用于優(yōu)化字符串縮短的操作：當(dāng) SDS 的 API 需要縮短 SDS 保存的字符串時，程序并不立即使用內(nèi)存重分配來回收縮短后多出來的字節(jié)，而是回歸到 alloc 屬性中，并等待將來使用。
通過惰性釋放策略，SDS 避免了縮短字符串時所需的內(nèi)存重分配操作，并為將來可能有的增長操作提供了優(yōu)化。
二進制安全
二進制安全（binary-safe）：指能處理任意的二進制數(shù)據(jù)，包括非ASCII和null字節(jié)。
我們知道 C 字符串是以空字符（\0）結(jié)尾，所以除了字符串的末尾之外，字符串里面不能包含任何的空字符，否則最先被程序讀入的空字符會被誤認(rèn)為是字符串的結(jié)尾。這些限制使得 C 字符串只能保存文本數(shù)據(jù)，不能保存圖像、視頻、音頻等二進制數(shù)據(jù)。
而 SDS 不會對數(shù)據(jù)做任何限制、過濾、假設(shè)，數(shù)據(jù)在寫入時是什么樣子的，它被讀取時就是什么樣的。因此 Redis 不僅可以保存文本數(shù)據(jù)，還可以保存任意格式的二進制數(shù)據(jù)。
參考
《Redis 設(shè)計與實現(xiàn)》
Redis源碼分析之sds
redis源碼分析（二）、redis源碼分析之sds字符串
【死磕 Redis】----- Redis 通信協(xié)議 RESP
【死磕 Redis】----- 理解 pipeline 管道
【死磕 Redis】-----如何排查 Redis 中的慢查詢
【死磕 Redis】----- 主從復(fù)制（一）：概述
【死磕 Redis】----- 主從復(fù)制（二）:全量復(fù)制和部分復(fù)制
【死磕 Redis】----- 主從復(fù)制（三）：注意的問題
【死磕 Redis】----- 哨兵（一）：部署哨兵架構(gòu)