sds 的用途
Sds 在 Redis 中的主要作用有以下兩個：
實現字符串對象（StringObject）；
在 Redis 程序內部用作 char* 類型的替代品；
以下兩個小節分別對這兩種用途進行介紹。
實現字符串對象
Redis 是一個鍵值對數據庫（key-value DB）， 數據庫的值可以是字符串、集合、列表等多種類型的對象， 而數據庫的鍵則總是字符串對象。
對於那些包含字符串值的字符串對象來說， 每個字符串對象都包含一個 sds 值。
“包含字符串值的字符串對象”，這種說法初聽上去可能會有點奇怪， 但是在 Redis 中， 一個字符串對象除了可以保存字符串值之外， 還可以保存 long 類型的值， 所以為了嚴謹起見， 這裡需要強調一下： 當字符串對象保存的是字符串時， 它包含的才是 sds 值， 否則的話， 它就是一個 long 類型的值。
舉個例子， 以下命令創建了一個新的數據庫鍵值對， 這個鍵值對的鍵和值都是字符串對象， 它們都包含一個 sds 值：
redis> SET book "Mastering C++ in 21 days" OK redis> GET book "Mastering C++ in 21 days"
以下命令創建了另一個鍵值對， 它的鍵是字符串對象， 而值則是一個集合對象：
redis> SADD nosql "Redis" "MongoDB" "Neo4j" (integer) 3 redis> SMEMBERS nosql 1) "Neo4j" 2) "Redis" 3) "MongoDB"
用 sds 取代 C 默認的 char* 類型
因為 char* 類型的功能單一， 抽象層次低， 並且不能高效地支持一些 Redis 常用的操作（比如追加操作和長度計算操作）， 所以在 Redis 程序內部， 絕大部分情況下都會使用 sds 而不是 char* 來表示字符串。
性能問題在稍後介紹 sds 定義的時候就會說到， 因為我們還沒有了解過 Redis 的其他功能模塊， 所以也沒辦法詳細地舉例說那裡用到了 sds ， 不過在後面的章節中， 我們會經常看到其他模塊（幾乎每一個）都用到了 sds 類型值。
目前來說， 只要記住這個事實即可： 在 Redis 中， 客戶端傳入服務器的協議內容、 aof 緩存、 返回給客戶端的回復， 等等， 這些重要的內容都是由 sds 類型來保存的。
redis 中的字符串
在 C 語言中，字符串可以用一個 \0 結尾的 char 數組來表示。
比如說， hello world 在 C 語言中就可以表示為 "hello world\0" 。
這種簡單的字符串表示，在大多數情況下都能滿足要求，但是，它並不能高效地支持長度計算和追加（append）這兩種操作：
每次計算字符串長度（strlen(s)）的復雜度為 θ(N) 。
對字符串進行 N 次追加，必定需要對字符串進行 N 次內存重分配（realloc）。
在 Redis 內部， 字符串的追加和長度計算很常見， 而 APPEND 和 STRLEN 更是這兩種操作，在 Redis 命令中的直接映射， 這兩個簡單的操作不應該成為性能的瓶頸。
另外， Redis 除了處理 C 字符串之外， 還需要處理單純的字節數組， 以及服務器協議等內容， 所以為了方便起見， Redis 的字符串表示還應該是二進制安全的： 程序不應對字符串裡面保存的數據做任何假設， 數據可以是以 \0 結尾的 C 字符串， 也可以是單純的字節數組， 或者其他格式的數據。
考慮到這兩個原因， Redis 使用 sds 類型替換了 C 語言的默認字符串表示： sds 既可高效地實現追加和長度計算， 同時是二進制安全的。
sds 的實現
在前面的內容中， 我們一直將 sds 作為一種抽象數據結構來說明， 實際上， 它的實現由以下兩部分組成：
typedef char *sds;
struct sdshdr {
// buf 已占用長度
int len;
// buf 剩余可用長度
int free;
// 實際保存字符串數據的地方
char buf[];
};
其中，類型 sds 是 char * 的別名（alias），而結構 sdshdr 則保存了 len 、 free 和 buf 三個屬性。
作為例子，以下是新創建的，同樣保存 hello world 字符串的 sdshdr 結構：
struct sdshdr {
len = 11;
free = 0;
buf = "hello world\0"; // buf 的實際長度為 len + 1
};
通過 len 屬性， sdshdr 可以實現復雜度為 θ(1) 的長度計算操作。
另一方面， 通過對 buf 分配一些額外的空間， 並使用 free 記錄未使用空間的大小， sdshdr 可以讓執行追加操作所需的內存重分配次數大大減少， 下一節我們就會來詳細討論這一點。
當然， sds 也對操作的正確實現提出了要求 —— 所有處理 sdshdr 的函數，都必須正確地更新 len 和 free 屬性，否則就會造成 bug 。
數據類型定義
與sds實現有關的數據類型有兩個，一個是 sds：
// 字符串類型的別名 typedef char *sds;
另一個是 sdshdr：
// 持有sds的結構
struct sdshdr {
// buf中已經被使用的字符串空間數量
int len;
// buf中預留字符串的空間數量
int free;
// 實際存儲字符串的地方
char buf[];
};
其中，sds只是字符串數組類型char*的別名，而sdshdr用於持有和保存sds的信息
比如，sdshdr.len可以用於在O（1）的復雜度下獲取sdshdr.buf中存儲的字符串的實際長度，而sdshdr.free則用於保存sdshdr.buf中還有多少預留空間
（這裡sdshdr應該是sds handler的縮寫）
將sdshdr用作sds
sds模塊對sdshdr結構使用了一點小技巧：通過指針運算，它使得sdshdr結構可以像sds類型一樣被傳值和處理，並在需要的時候恢復成sdshdr類型
通過下面的函數定義來理解這個技巧
sdsnewlen 函數返回一個新的sds值，實際上，它創建的卻是一個sdshdr結構：
sds sdsnewlen(const void *init, size_t initlen)
{
struct sdshdr *sh;
if (init) {
// 創建
sh = malloc(sizeof(struct sdshdr) + initlen + 1);
} else {
// 重分配
sh = calloc(1, sizeof(struct sdshdr) + initlen + 1);
}
if (sh == NULL) return NULL;
sh->len = initlen;
sh->free = 0; // 剛開始free為0
if (initlen && init) {
memcpy(sh->buf, init, initlen);
}
sh->buf[initlen] = '\0';
// 只返回sh->buf這個字符串部分
return (char *)sh->buf;
}
通過使用變量持有一個sds的值，在遇到那些只處理sds值本身的函數時，可以直接將sds傳給它們。比如說，sdstoupper 函數就是其中的一個例子：
static inline size_t sdslen(const sds s)
{
// 從sds中計算出相應的sdshdr結構
struct sdshdr *sh = (void *)(s - (sizeof(struct sdshdr)));
return sh->len;
}
void sdstoupper(sds s)
{
int len = sdslen(s), j;
for (j = 0; j < len; j ++)
s[j] = toupper(s[j]);
}
這裡有一個技巧，通過指針運算，可以從sds值中計算出相應的sdshdr結構：
sds雖然是指向char *的buf（ps：並且空數組不占用內存空間，數組名即為內存地址），但是分配的時候是分配sizeof(struct sdshdr) + initlen + 1的，通過sds - sizeof(struct sdshdr)可以計算出struct sdshdr的首地址，從而可以得到len和free的信息
sdsavail 函數就是使用這中技巧的一個例子：
static inline size_t sdsavail(const sds s)
{
struct sdshdr *sh = (void *)(s - (sizeof(struct sdshdr)));
return sh->free;
}
內存分配函數實現
和Reids 的實現決策相關的函數是 sdsMakeRoomFor ：
sds sdsMakeRoomFor(sds s, size_t addlen)
{
struct sdshdr *sh, *newsh;
size_t free = sdsavail(s);
size_t len, newlen;
// 預留空間可以滿足本地拼接
if (free >= addlen) return s;
len = sdslen(s);
sh = (void *)(s - (sizeof(struct sdshdr)));
// 設置新sds的字符串長度
// 這個長度比完成本次拼接實際所需的長度要大
// 通過預留空間優化下次拼接操作
newlen = (len + addlen);
if (newlen < 1024 * 1024)
newlen *= 2;
else
newlen += 1024;
// 重新分配sdshdr
newsh = realloc(sh, sizeof(struct sdshdr) + newlen + 1);
if (newsh == NULL) return NULL;
newsh->free = newlen - len;
// 只返回字符串部分
return newsh->buf;
}
這種內存分配策略表明，在對sds 值進行擴展（expand）時，總會預留額外的空間，通過花費更多的內存，減少了對內存進行重分配(reallocate)的次數，並優化下次擴展操作的處理速度
再把redis的如果實現對sds字符串擴展的方法貼一下，很不錯的思路：
/**
* 按長度len擴展sds，並將t拼接到sds的末尾
*/
sds sdscatlen(sds s, const void *t, size_t len)
{
struct sdshdr *sh;
size_t curlen = sdslen(s);
// O(N)
s = sdsMakeRoomFor(s, len);
if (s == NULL) return NULL;
// 復制
memcpy(s + curlen, t, len);
// 更新len和free屬性
sh = (void *)(s - (sizeof(struct sdshdr)));
sh->len = curlen + len;
sh->free = sh->free - len;
// 終結符
s[curlen + len] = '\0';
return s;
}
/**
* 將一個char數組拼接到sds 末尾
*/
sds sdscat(sds s, const char *t)
{
return sdscatlen(s, t, strlen(t));
}
