摘要：沒有直接使用語言傳統(tǒng)的字符串表示以空字符串結(jié)尾的字符數(shù)組，而是構(gòu)建了一種名為簡單動態(tài)字符串的抽象類型，并將用作的默認字符串表示。對比字符串，有幾大優(yōu)點常數(shù)復(fù)雜度獲取字符串長度杜絕緩沖區(qū)溢出減少修改字符串時所需的內(nèi)存重分配次數(shù)。

Redis 沒有直接使用 C 語言傳統(tǒng)的字符串表示（以空字符串結(jié)尾的字符數(shù)組），而是構(gòu)建了一種名為簡單動態(tài)字符串（simple dynamic string）的抽象類型，并將 SDS 用作 Redis 的默認字符串表示。

在 Redis 中，C 字符串只會作為字符串字面量用在一些無需對字符串進行修改的地方，比如打印日志：

serverLog(LL_WARNING,"SIGTERM received but errors trying to shut down the server, check the logs for more information");

當 Redis 需要的不僅僅是一個字符串字面量，而是一個可以被修改的字符串值時，Redis 就會適應(yīng) SDS 來表示字符串。比如在數(shù)據(jù)庫中，包含字符串值的鍵值對在底層都是由 SDS 實現(xiàn)的。

還是拿簡單的 SET 命令舉例，執(zhí)行以下命令

redis> SET msg "hello world"
ok

那么，Redis 將在數(shù)據(jù)中創(chuàng)建一個新的鍵值對，其中：

鍵值對的鍵是一個字符串對著，對象的底層實現(xiàn)是一個保存著字符串 "msg" 的 SDS。

鍵值對的值也是一個字符串對象，對象的底層實現(xiàn)是一個保存著字符串 "hello world" 的 SDS。

除了用來保存數(shù)據(jù)庫中的字符串值之外， SDS 還被用作緩沖區(qū)。AOF 模塊中的 AOF 緩沖區(qū)，以及客戶端狀態(tài)中的輸入緩沖區(qū)，都是由 SDS 實現(xiàn)的。

接下來，我們就來詳細認識下 SDS。

在 sds.h 中，我們會看到以下結(jié)構(gòu)：

typedef char *sds;

可以看到，SDS 等同于 char 類型。這是因為 SDS 需要和傳統(tǒng)的 C 字符串保存兼容，因此將其類型設(shè)置為 char 。但是要注意的是，SDS 并不等同 char *，它還包括一個 header 結(jié)構(gòu)，共有 5 中類型的 header，源碼如下：

struct __attribute__ ((__packed__)) sdshdr5 { // 已棄用
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 { // 長度小于 2^8 的字符串類型
    uint8_t len;         // SDS 所保存的字符串長度
    uint8_t alloc;       // SDS 分配的長度
    unsigned char flags; // 標記位，占 1 字節(jié)，使用低 3 位存儲 SDS 的 type，高 5 位不使用
    char buf[];          // 存儲的真實字符串數(shù)據(jù)
};
struct __attribute__ ((__packed__)) sdshdr16 { // 長度小于 2^16 的字符串類型
    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 { // 長度小于 2^32 的字符串類型
    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 { // 長度小于 2^64 的字符串類型
    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[];
};

之所以會有 5 種類型的 header，是為了能讓不同長度的字符串使用對應(yīng)大小的 header，提高內(nèi)存利用率。

一個 SDS 的完整結(jié)構(gòu)，由內(nèi)存地址上前后相鄰的兩部分組成：

header：包括字符串的長度（len），最大容量（alloc）和 flags（不包含 sdshdr5）。

buf[]：一個字符串數(shù)組。這個數(shù)組的長度等于最大容量加 1，存儲著真正的字符串數(shù)據(jù)。

圖 1-1 展示了一個 SDS 示例：

示例中，各字段說明如下：

alloca：SDS 分配的空間大小。圖中表示分配的空間大小為 10。

len：SDS 保存字符串大小。圖中表示保存了 5 個字節(jié)的字符串。

buf[]：這個數(shù)組的長度等于最大容量加 1，存儲著真正的字符串數(shù)據(jù)。圖中表示數(shù)字的前 5 個字節(jié)分別保存了 "H"、"e"、"l"、"l"、"o" 五個字符，而最后一個字節(jié)則保存了空字符串 "0"。

SDS 遵循 C 字符串以空字符結(jié)尾的慣例，保存空字符的大小不計算在 SDS 的 len 屬性中。此外，添加空字符串到字符串末尾等操作，都是由 SDS 函數(shù)（sds.c 文件中的相關(guān)函數(shù)）自動完成的。

而且，遵循空字符結(jié)尾的慣例，還可以直接重用一部分 C 字符串函數(shù)庫中的函數(shù)。

例如，我們可以直接使用 printf() 函數(shù)打印 s->buf：
printf("%s", s->buf);
這樣，我們可以直接使用 C 函數(shù)來打印字符串 "Redis"，無需為 SDS 編寫轉(zhuǎn)碼的打印函數(shù)。

在 C 語言中，使用長度為 N+1 的字符數(shù)組來表示長度為 N 的字符串，并且字符數(shù)組的最后一個元素總是空字符 "0"。

C 語言使用的這種字符串表示方式，并不能滿足 Redis 對字符串再安全性、效率及功能方面的要求。因此，Redis 設(shè)計出了 SDS，來滿足自己的相關(guān)需求。接下來，我們從以下幾方面來認識 SDS 對比 C 字符串的優(yōu)勢：

獲取字符串長度；

緩沖區(qū)溢出；

修改字符串時的內(nèi)存重分配次數(shù)；

二進制安全；

由于 C 字符串并不記錄自身的長度信息，所以在 C 語言中，為了獲取一個 C 字符串的長度，程序必須遍歷整個字符串，直到遇到代表字符串結(jié)尾的空字符為止，這個操作的復(fù)雜度為 O(N)。

這個復(fù)雜度對于 Redis 而言，一旦碰上非常長的字符串，使用 STRLEN 命令時，很容易對系統(tǒng)性能造成影響。

和 C 字符串不同的是，因為 SDS 在 len 屬性中記錄了 SDS 保存的字符串的長度，所以獲取一個 SDS 長度的復(fù)雜度僅為 O(1)。

而且設(shè)置和更新 SDS 長度的工作都是由 SDS 的 API 在執(zhí)行時自動完成的，所以使用 SDS 無需進行任何手動修改長度的工作。

通過使用 SDS，Redis 將獲取字符串長度所需的復(fù)雜度從 O(N) 降低到了 O(1)，確保了獲取字符串長度的工作不會成為 Redis 的性能瓶頸。

C 字符串不記錄自身長度，不僅使得獲取字符串長度的復(fù)雜度較高，還容易造成緩沖區(qū)溢出（buffer overflow）。

C 語言中的 strcat() 函數(shù)可以將 src 字符串中的內(nèi)容拼接到 dest 字符串的末尾：

char *strcat(char *dest, const char *src);

因為 C 字符串不記錄自身的長度，所以 strcat 函數(shù)執(zhí)行時，假定用戶已經(jīng)為 dest 分配了足夠多的內(nèi)存，可以容納 src 字符串中的所有內(nèi)容。而一旦這個假定不成立，就會產(chǎn)生緩沖區(qū)溢出。

舉個例子，假設(shè)程序里有兩個在內(nèi)存中緊鄰著的 C 字符串 s1 和 s2，其中 s1 保存了字符串 "redis"，s2 保存了字符串 "mysql"，存儲結(jié)構(gòu)如圖 2-1 所示：

如果我們執(zhí)行下面語句：

strcat(s1, " 666");

將 s1 的內(nèi)容修改為 "redis 666"，但卻沒有在執(zhí)行 strcat() 之前為 s1 分配足夠的空間，那么在執(zhí)行 strcat() 之后，s1 的數(shù)據(jù)將移除到 s2 所在的空間，導(dǎo)致 s2 保存的內(nèi)容被意外修改，如圖 2-2 所示：

與 C 字符串不同的是，SDS 的空間分配策略完全杜絕了發(fā)生緩沖區(qū)溢出的可能性：當 SDS 的 API 需要對 SDS 進行修改時，API 會先檢查 SDS 的空間十分滿足修改所需的要求，如果不滿足的話，API 會自動將 SDS 的空間擴展至執(zhí)行修改所需的大小，然后再執(zhí)行實際的修改操作，所以使用 SDS 既不需要手動修改 SDS 的空間大小，也不會出現(xiàn)前面所說的緩沖區(qū)溢出問題。

由于 C 字符串的長度 slen 和底層數(shù)組的長度 salen 總存在著下述關(guān)系：

salen = slen + 1; // 1 是空字符的長度

因此，每次增長或縮短一個 C 字符串，總要對 C 字符串的數(shù)組進行一次內(nèi)存重分配操作：

增長字符串。程序需要通過內(nèi)存重分配來擴展底層數(shù)組的空間的大小，如果漏了這步，就可能會產(chǎn)生緩沖區(qū)溢出。

縮短字符串。程序需要通過內(nèi)存重分配來釋放底層數(shù)組不再使用的空間，如果漏了這步，就可能會產(chǎn)生內(nèi)存泄漏。

而內(nèi)存重分配涉及復(fù)雜的算法，并且可能需要執(zhí)行系統(tǒng)調(diào)用，所以內(nèi)存重分配是一個較為耗時的過程。

對于 Redis 而言，一切耗時的操作都要優(yōu)化?；诖?，SDS 對于字符串的增長和縮短操作，通過空間預(yù)分配和惰性空間釋放兩種方式來優(yōu)化。

2.3.1 空間預(yù)分配

空間預(yù)分配是指：在需要對 SDS 的空間進行擴展時，程序不是僅僅分配所必需的的空間，還會為 SDS 分配額外的未使用空間。

關(guān)于 SDS 的空間擴展，源碼如下：

# sds.c/sdsMakeRoomFor()
...
newlen = (len+addlen); // SDS 最新長度
if (newlen < SDS_MAX_PREALLOC) // 預(yù)分配最大值 SDS_MAX_PREALLOC 在 sds.h 中定義，值為 1024*1024
    newlen *= 2;
else
    newlen += SDS_MAX_PREALLOC;
...

由源碼可以看出，空間擴展分為兩種情況：

新長度小于預(yù)分配最大值。此時，程序?qū)⒅苯訛?SDS 新增最新長度大小的未使用空間。舉個栗子，現(xiàn)有一個長度為 10 字節(jié)的字符串 s1，當給 s1 追加字符串 "redis"，那么，程序?qū)⒊朔峙渥銐?s1 使用的空間，還會為 s1 再分配最新長度大小的預(yù)使用空間。所以，s1 的實際長度就變?yōu)椋?15 + 15 + 1 = 31 個字節(jié)。

新長度大于預(yù)分配最大值。此時，由于最新字符串較大，程序不會預(yù)分配這么多空間，只會給預(yù)分配最大值的空間。舉個栗子，現(xiàn)有長度為 3M 的字符串 s2，當給 s1 追加一個 2M 大小的字符串，那么程序除了新增 2M 來存儲新增的長度，還會為 s2 再分配 1M（SDS_MAX_PREALLOC）的預(yù)使用空間。所以，s2 的實際長度就變?yōu)椋?b>3M + 2M +1M + 1byte。

正是通過預(yù)分配的策略，Redis 減少了執(zhí)行字符串增長操作所需的內(nèi)存重分配次數(shù)，保證了 Redis 不會因字符串增長操作損耗性能。

2.3.2 惰性空間釋放

預(yù)分配對應(yīng)字符串的增長操作，而空間釋放則對應(yīng)字符串的縮短操作。

惰性空間釋放是指：在對 SDS 進行縮短操作時，程序不立即回收縮短后多出來的字節(jié)，等待將來使用。

舉個栗子，我們使用 sdstrim() 函數(shù)，移除下圖 SDS 中所有指定的字符：

對上圖 SDS，執(zhí)行：
sdstrim(s, "l"); // 移除 SDS 字符串中所有的 "l"

會將 SDS 修改為圖 2-4 所示：

可以看到，執(zhí)行 sdstrim() 之后的 SDS 并沒有釋放多出來的 3 字節(jié)空間，而是將這 3 字節(jié)空間作為未使用空間保留在了 SDS 里面，以待備用。

正是通過惰性空間釋放策略，SDS 避免了縮短字符串時所需的內(nèi)存重分配操作，并為將來可能的增長操作提供了優(yōu)化。

此外，SDS 也提供了相應(yīng)的 API，讓我們在有需要時，真正的釋放 SDS 的未使用空間，避免造成內(nèi)存浪費。

Redis 只會使用 C 字符串作為字面量，大多數(shù)情況下，使用 SDS 作為字符串表示。

SDS 對比 C 字符串，有幾大優(yōu)點：常數(shù)復(fù)雜度獲取字符串長度、杜絕緩沖區(qū)溢出、減少修改字符串時所需的內(nèi)存重分配次數(shù)。