sds，即 Simple Dynamic Strings，是Redis中儲存絕大部分字串所採用的資料結構。
typedef char *sds;
sds的型別包括SDS_TYPE_5, SDS_TYPE_8, SDS_TYPE_16, SDS_TYPE_32, SDS_TYPE_64五種：
#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
建立sds時根據初始字串的長度指定sds型別。原始碼如下：
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;
return SDS_TYPE_64;
#else
return SDS_TYPE_32;
#endif
}
標識SDS_TYPE的數位實際上指定了字串長度能夠由長度為幾位的二進位制數標識。
long long一般是8位元組，只有當long也為8位元組，且字串長度用32位元不足以表示時，才會將sds指定為SDS_TYPE_64型別。
疑問：函數引數
size_t string_size的型別實際為unsigned long long，為什麼要考慮long型的長度？
由於一共有5種型別，需要二進位制數至少三位來標識型別。這可以從下文得到印證。
sds大致的結構為頭部+字串值。對於上述五種不同型別，sds結構大同小異。
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[];
};
__attribute__ ((__packed__))用於指示編譯器以緊湊方式打包結構體，即不對成員進行對齊。
可以看到，公共的成員變數包括buf與flags。
buf用於實際儲存資料flags共有的用途是指明sds的型別，具體儲存在低3位struct sdshdr5相對不復雜，僅在flags中記錄了字串的實際長度。由前文可知，當原字串長度可以用不超過5位表示時，sds採用SDS_TYPE_5型別。於是將長度的5位與用於標識型別的3位組合為flags，很好地利用了空間。
對於其他型別的sds，flags中的高五位已不能滿足長度記錄需要，因此增加了欄位。
len：指的是實際字串的長度，與SDS_TYPE_5型別的sds中flags高五位的含義一致alloc：指的是分配的位元組數，不包含頭部與字串尾部附加的'\0'最簡單的建立sds的函數定義如下所示，該函數接收一個C語言字串作為引數（C語言字串以'\0'為結尾）。
sds sdsnew(const char *init) {
size_t initlen = (init == NULL) ? 0 : strlen(init);
return sdsnewlen(init, initlen);
}
sds sdsnew(const char *init)方法實際呼叫了sdsnewlen方法，將原始字串和字串長度作為引數傳入。sdsnewlen方法定義如下：
sds sdsnewlen(const void *init, size_t initlen) {
return _sdsnewlen(init, initlen, 0);
}
sdsnewlen仍然是一個殼子，呼叫了_sdsnewlen方法，其定義如下。
sds _sdsnewlen(const void *init, size_t initlen, int trymalloc) {
void *sh;
sds s;
char type = sdsReqType(initlen);
/* Empty strings are usually created in order to append. Use type 8
* since type 5 is not good at this. */
if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
int hdrlen = sdsHdrSize(type);
unsigned char *fp; /* flags pointer. */
size_t usable;
assert(initlen + hdrlen + 1 > initlen); /* Catch size_t overflow */
sh = trymalloc?
s_trymalloc_usable(hdrlen+initlen+1, &usable) :
s_malloc_usable(hdrlen+initlen+1, &usable);
if (sh == NULL) return NULL;
if (init==SDS_NOINIT)
init = NULL;
else if (!init)
memset(sh, 0, hdrlen+initlen+1);
s = (char*)sh+hdrlen;
fp = ((unsigned char*)s)-1;
usable = usable-hdrlen-1;
if (usable > sdsTypeMaxSize(type))
usable = sdsTypeMaxSize(type);
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 = usable;
*fp = type;
break;
}
case SDS_TYPE_16: {
SDS_HDR_VAR(16,s);
sh->len = initlen;
sh->alloc = usable;
*fp = type;
break;
}
case SDS_TYPE_32: {
SDS_HDR_VAR(32,s);
sh->len = initlen;
sh->alloc = usable;
*fp = type;
break;
}
case SDS_TYPE_64: {
SDS_HDR_VAR(64,s);
sh->len = initlen;
sh->alloc = usable;
*fp = type;
break;
}
}
if (initlen && init)
memcpy(s, init, initlen);
s[initlen] = '\0';
return s;
}
函數內部首先判定待建立的sds類別，存放在變數type中，所呼叫的sdsReqType我們在前文已經介紹過了。
有一個細節的處理是，如果字串長度是0，手動將其設定為SDS_TYPE_8型別。原因在原始碼的註釋中已經給出：字串長度為0的sds一般是被建立用來拼接字串的，而SDS_TYPE_5型別的sds並不擅長做這個。
接下來，呼叫函數sdsHdrSize根據類別獲取頭部長度，存放在變數hdrlen中。函數定義也很簡單，就是根據type計算對應的頭部結構體大小並返回。需要額外解釋的是，每個sds頭結構體實際用一個柔性陣列存放字串，在sizeof()計算時，柔型陣列欄位對應的size為0。以struct sdshdr8為例，其大小隻有前三個成員的大小決定，為1+1+1位元組。
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[];
};
接下來，為sds分配空間，對應這段程式碼：
sh = trymalloc?
s_trymalloc_usable(hdrlen+initlen+1, &usable) :
s_malloc_usable(hdrlen+initlen+1, &usable);
sdsnewlen呼叫_sdsnewlen時，傳參trymalloc為0。於是我們檢視s_malloc_usable方法。呼叫s_malloc_usable傳入兩個引數，第一個引數值hdrlen+initlen+1恰好指定sds所需的最小空間，包括頭部空間，原始字串，以及字串末尾的\0。第二個引數用於接收分配的可用空間大小。
s_malloc_usable實際通過宏定義指向zmalloc_usable方法。
void *zmalloc_usable(size_t size, size_t *usable) {
size_t usable_size = 0;
void *ptr = ztrymalloc_usable_internal(size, &usable_size);
if (!ptr) zmalloc_oom_handler(size);
#ifdef HAVE_MALLOC_SIZE
ptr = extend_to_usable(ptr, usable_size);
#endif
if (usable) *usable = usable_size;
return ptr;
}
這一方法內部又呼叫了ztrymalloc_usable_internal方法：
static inline void *ztrymalloc_usable_internal(size_t size, size_t *usable) {
/* Possible overflow, return NULL, so that the caller can panic or handle a failed allocation. */
if (size >= SIZE_MAX/2) return NULL;
void *ptr = malloc(MALLOC_MIN_SIZE(size)+PREFIX_SIZE);
if (!ptr) return NULL;
#ifdef HAVE_MALLOC_SIZE
size = zmalloc_size(ptr);
update_zmalloc_stat_alloc(size);
if (usable) *usable = size;
return ptr;
#else
// 分析這裡
*((size_t*)ptr) = size;
update_zmalloc_stat_alloc(size+PREFIX_SIZE);
if (usable) *usable = size;
return (char*)ptr+PREFIX_SIZE;
#endif
}
malloc分配處，將宏定義展開則為如下表示式：
void *ptr = malloc((size > 0 ? size : 0)+(sizeof(size_t)))
size_t實際為unsigned long long，額外分配的PREFIX_SIZE空間用於儲存本次分配空間的大小，不包含PREFIX_SIZE空間大小。
呼叫update_zmalloc_stat_alloc的目的是維護記錄分配空間大小的變數user_memory。
#define update_zmalloc_stat_alloc(__n) atomicIncr(used_memory,(__n))
static redisAtomic size_t used_memory = 0;
ztrymalloc_usable_internal最終返回的是所分配空間向後偏移PREFIX_SIZE的地址。
分配空間的部分我們已經解讀完畢，接下來繼續閱讀_sdsnewlen剩餘程式碼。
s = (char*)sh+hdrlen;，使s指向頭部柔型陣列成員。
fp = ((unsigned char*)s)-1;使fp指向柔型陣列前一個成員，即flags。
switch語句根據type為頭部每個成員賦值。其中SDS_HDR_VAR宏定義如下：
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
這行程式碼讓根據type和柔型陣列首地址找到頭部首地址，並將sh指向這一地址。
兩個與長度相關的欄位賦值如下：
sh->len = initlen;
sh->alloc = usable;
這時，usable與initlen的長度實際上是相等的。
接著複製字串，並在末尾附加'\0'：
if (initlen && init)
memcpy(s, init, initlen);
s[initlen] = '\0';
最後返回的是s而非sh。也就是說，sds建立後，並不存在指向其頭部首地址的指標，sds指標指向柔性陣列欄位。
sds擴充套件空間有兩種方式，不同之處在於是否進行空間預分配，即分配額外的空間以避免每次增加字元都要重新分配記憶體。兩個函數的定義如下：
/* Enlarge the free space at the end of the sds string more than needed,
* This is useful to avoid repeated re-allocations when repeatedly appending to the sds. */
sds sdsMakeRoomFor(sds s, size_t addlen) {
return _sdsMakeRoomFor(s, addlen, 1);
}
/* Unlike sdsMakeRoomFor(), this one just grows to the necessary size. */
sds sdsMakeRoomForNonGreedy(sds s, size_t addlen) {
return _sdsMakeRoomFor(s, addlen, 0);
}
可以看到，兩個函數最終呼叫同一個函數_sdsMakeRoomFor，第三個引數指明是否需要進行預分配。
_sdsMakeRoomFor定義如下：
sds _sdsMakeRoomFor(sds s, size_t addlen, int greedy) {
void *sh, *newsh;
size_t avail = sdsavail(s);
size_t len, newlen, reqlen;
char type, oldtype = s[-1] & SDS_TYPE_MASK;
int hdrlen;
size_t usable;
/* Return ASAP if there is enough space left. */
if (avail >= addlen) return s;
len = sdslen(s);
sh = (char*)s-sdsHdrSize(oldtype);
reqlen = newlen = (len+addlen);
assert(newlen > len); /* Catch size_t overflow */
if (greedy == 1) {
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);
assert(hdrlen + newlen + 1 > reqlen); /* Catch size_t overflow */
if (oldtype==type) {
newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
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_usable(hdrlen+newlen+1, &usable);
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);
}
usable = usable-hdrlen-1;
if (usable > sdsTypeMaxSize(type))
usable = sdsTypeMaxSize(type);
sdssetalloc(s, usable);
return s;
}
首先判斷已有sds尚未使用的空間是否已達到addlen，sdsavail定義如下。
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;
}
若未使用空間已能夠滿足要求，則不額外分配，直接返回。
若繼續分配，要確定新的空間大小：
reqlen = newlen = (len+addlen);
if (greedy == 1) {
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;
}
這裡就是sdsMakeRoomForNonGreedy與sdsMakeRoomFor差異的根源。
if (greedy == 1)內newlen相比於自身原值增加的值就是預分配的空間。預分配空間是有上限的：
#define SDS_MAX_PREALLOC (1024*1024)
若newlen原值達不到預分配空間上限，就分配二倍的newlen空間，否則額外分配SDS_MAX_PREALLOC大小的空間。
接著指定新sds的型別：
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;
這裡更加明確地避免了SDS_TYPE_5的使用。由前面sdsavail函數可以看到，SDS_TYPE_5的未使用空間永遠是0，這也是為什麼SDS_TYPE_5不適合用於字串拼接：每次拼接都要重新分配空間。
後面的處理根據新舊type是否一致而存在差異。若新舊type一致，頭部長度不變，新的空間資料分佈與原空間一致，因此呼叫realloc，當新的空間大小大於原空間大小時，realloc的作用是在堆上開闢一塊新的記憶體空間，將原空間的內容複製到新空間，然後釋放新空間。若新舊type不一致，則新舊sds中buf的位置相對於頭部首地址不同，不能直接利用realloc拷貝，因此呼叫malloc，並需要手動s_free原sds。
redis的sds由頭部和實際字串兩部分組成，並在字串末尾附加一個'\0'，其中字串作為頭部結構體最後一個成員變數存在，且sds實際指向柔型陣列的首地址。這樣的結構有很多好處：
len欄位標識結尾處，而不在'\0'處結尾初始建立sds時不預留空間，這是因為不是所有的sds都會執行拼接操作，預留空間未必有意義。而當對sds執行字串拼接操作時，就要進行空間的預分配了。當存在預分配空間時，進行字串拼接時若預分配空間足夠，則不需要重新分配空間，提高了效率。