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

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

在 Redis 中，C 字符串只會(huì)作為字符串字面量用在一些無(wú)需對(duì)字符串進(jìn)行修改的地方，比如打印日志：

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

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

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

redis> SET msg "hello world"
ok

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

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

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

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

接下來(lái)，我們就來(lái)詳細(xì)認(rèn)識(shí)下 SDS。

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

typedef char *sds;

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

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

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

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

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

buf[]：一個(gè)字符串?dāng)?shù)組。這個(gè)數(shù)組的長(zhǎng)度等于最大容量加 1，存儲(chǔ)著真正的字符串?dāng)?shù)據(jù)。

圖 1-1 展示了一個(gè) SDS 示例：

示例中，各字段說(shuō)明如下：

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

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

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

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

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

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

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

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

獲取字符串長(zhǎng)度；

緩沖區(qū)溢出；

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

二進(jìn)制安全；

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

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

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

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

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

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

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

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

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

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

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

strcat(s1, " 666");

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

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

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

salen = slen + 1; // 1 是空字符的長(zhǎng)度

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

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

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

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

對(duì)于 Redis 而言，一切耗時(shí)的操作都要優(yōu)化。基于此，SDS 對(duì)于字符串的增長(zhǎng)和縮短操作，通過(guò)空間預(yù)分配和惰性空間釋放兩種方式來(lái)優(yōu)化。

2.3.1 空間預(yù)分配

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

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

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

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

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

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

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

2.3.2 惰性空間釋放

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

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

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

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

會(huì)將 SDS 修改為圖 2-4 所示：

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

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

此外，SDS 也提供了相應(yīng)的 API，讓我們?cè)谟行枰獣r(shí)，真正的釋放 SDS 的未使用空間，避免造成內(nèi)存浪費(fèi)。

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

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