根據(jù)傳統(tǒng)， C 語言使用長度為?N+1?的字符數(shù)組來表示長度為?N?的字符串， 并且字符數(shù)組的最后一個元素總是空字符?'\0'?。

比如說， 圖 2-3 就展示了一個值為?"Redis"?的 C 字符串：

C 語言使用的這種簡單的字符串表示方式， 并不能滿足 Redis 對字符串在安全性、效率、以及功能方面的要求， 本節(jié)接下來的內(nèi)容將詳細(xì)對比 C 字符串和 SDS 之間的區(qū)別， 并說明 SDS 比 C 字符串更適用于 Redis 的原因。

常數(shù)復(fù)雜度獲取字符串長度

因為 C 字符串并不記錄自身的長度信息， 所以為了獲取一個 C 字符串的長度， 程序必須遍歷整個字符串， 對遇到的每個字符進(jìn)行計數(shù)， 直到遇到代表字符串結(jié)尾的空字符為止， 這個操作的復(fù)雜度為??。

舉個例子， 圖 2-4 展示了程序計算一個 C 字符串長度的過程。

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

舉個例子， 對于圖 2-5 所示的 SDS 來說， 程序只要訪問 SDS 的?len?屬性， 就可以立即知道 SDS 的長度為?5?字節(jié)：

又比如說， 對于圖 2-6 展示的 SDS 來說， 程序只要訪問 SDS 的?len?屬性， 就可以立即知道 SDS 的長度為?11?字節(jié)。

設(shè)置和更新 SDS 長度的工作是由 SDS 的 API 在執(zhí)行時自動完成的， 使用 SDS 無須進(jìn)行任何手動修改長度的工作。

通過使用 SDS 而不是 C 字符串， Redis 將獲取字符串長度所需的復(fù)雜度從??， 這確保了獲取字符串長度的工作不會成為 Redis 的性能瓶頸。

比如說， 因為字符串鍵在底層使用 SDS 來實(shí)現(xiàn)， 所以即使我們對一個非常長的字符串鍵反復(fù)執(zhí)行?STRLEN?命令， 也不會對系統(tǒng)性能造成任何影響， 因為?STRLEN?命令的復(fù)雜度僅為??。

杜絕緩沖區(qū)溢出

除了獲取字符串長度的復(fù)雜度高之外， C 字符串不記錄自身長度帶來的另一個問題是容易造成緩沖區(qū)溢出（buffer overflow）。

舉個例子，?<string.h>/strcat?函數(shù)可以將?src?字符串中的內(nèi)容拼接到?dest?字符串的末尾：

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

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

舉個例子， 假設(shè)程序里有兩個在內(nèi)存中緊鄰著的 C 字符串?s1?和?s2?， 其中?s1?保存了字符串?"Redis"?， 而?s2?則保存了字符串?"MongoDB"， 如圖 2-7 所示。

如果一個程序員決定通過執(zhí)行：

strcat(s1, " Cluster");

將?s1?的內(nèi)容修改為?"Redis?Cluster"?， 但粗心的他卻忘了在執(zhí)行?strcat?之前為?s1?分配足夠的空間， 那么在?strcat?函數(shù)執(zhí)行之后，?s1?的數(shù)據(jù)將溢出到?s2?所在的空間中， 導(dǎo)致?s2?保存的內(nèi)容被意外地修改， 如圖 2-8 所示。

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

舉個例子， SDS 的 API 里面也有一個用于執(zhí)行拼接操作的?sdscat?函數(shù)， 它可以將一個 C 字符串拼接到給定 SDS 所保存的字符串的后面， 但是在執(zhí)行拼接操作之前，?sdscat?會先檢查給定 SDS 的空間是否足夠， 如果不夠的話，?sdscat?就會先擴(kuò)展 SDS 的空間， 然后才執(zhí)行拼接操作。

比如說， 如果我們執(zhí)行：

sdscat(s, " Cluster");

其中 SDS 值?s?如圖 2-9 所示， 那么?sdscat?將在執(zhí)行拼接操作之前檢查?s?的長度是否足夠， 在發(fā)現(xiàn)?s?目前的空間不足以拼接?"?Cluster"之后，?sdscat?就會先擴(kuò)展?s?的空間， 然后才執(zhí)行拼接?"?Cluster"?的操作， 拼接操作完成之后的 SDS 如圖 2-10 所示。

注意圖 2-10 所示的 SDS ：?sdscat?不僅對這個 SDS 進(jìn)行了拼接操作， 它還為 SDS 分配了?13?字節(jié)的未使用空間， 并且拼接之后的字符串也正好是?13?字節(jié)長， 這種現(xiàn)象既不是 bug 也不是巧合， 它和 SDS 的空間分配策略有關(guān)， 接下來的小節(jié)將對這一策略進(jìn)行說明。

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

正如前兩個小節(jié)所說， 因為 C 字符串并不記錄自身的長度， 所以對于一個包含了?N?個字符的 C 字符串來說， 這個 C 字符串的底層實(shí)現(xiàn)總是一個?N+1?個字符長的數(shù)組（額外的一個字符空間用于保存空字符）。

因為 C 字符串的長度和底層數(shù)組的長度之間存在著這種關(guān)聯(lián)性， 所以每次增長或者縮短一個 C 字符串， 程序都總要對保存這個 C 字符串的數(shù)組進(jìn)行一次內(nèi)存重分配操作：

• 如果程序執(zhí)行的是增長字符串的操作， 比如拼接操作（append）， 那么在執(zhí)行這個操作之前， 程序需要先通過內(nèi)存重分配來擴(kuò)展底層數(shù)組的空間大小 —— 如果忘了這一步就會產(chǎn)生緩沖區(qū)溢出。
• 如果程序執(zhí)行的是縮短字符串的操作， 比如截斷操作（trim）， 那么在執(zhí)行這個操作之后， 程序需要通過內(nèi)存重分配來釋放字符串不再使用的那部分空間 —— 如果忘了這一步就會產(chǎn)生內(nèi)存泄漏。

舉個例子， 如果我們持有一個值為?"Redis"?的 C 字符串?s?， 那么為了將?s?的值改為?"Redis?Cluster"?， 在執(zhí)行：

strcat(s, " Cluster");

之前， 我們需要先使用內(nèi)存重分配操作， 擴(kuò)展?s?的空間。

之后， 如果我們又打算將?s?的值從?"Redis?Cluster"?改為?"Redis?Cluster?Tutorial"?， 那么在執(zhí)行：

strcat(s, " Tutorial");

之前， 我們需要再次使用內(nèi)存重分配擴(kuò)展?s?的空間， 諸如此類。

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

• 在一般程序中， 如果修改字符串長度的情況不太常出現(xiàn)， 那么每次修改都執(zhí)行一次內(nèi)存重分配是可以接受的。
• 但是 Redis 作為數(shù)據(jù)庫， 經(jīng)常被用于速度要求嚴(yán)苛、數(shù)據(jù)被頻繁修改的場合， 如果每次修改字符串的長度都需要執(zhí)行一次內(nèi)存重分配的話， 那么光是執(zhí)行內(nèi)存重分配的時間就會占去修改字符串所用時間的一大部分， 如果這種修改頻繁地發(fā)生的話， 可能還會對性能造成影響。

為了避免 C 字符串的這種缺陷， SDS 通過未使用空間解除了字符串長度和底層數(shù)組長度之間的關(guān)聯(lián)： 在 SDS 中，?buf?數(shù)組的長度不一定就是字符數(shù)量加一， 數(shù)組里面可以包含未使用的字節(jié)， 而這些字節(jié)的數(shù)量就由 SDS 的?free?屬性記錄。

通過未使用空間， SDS 實(shí)現(xiàn)了空間預(yù)分配和惰性空間釋放兩種優(yōu)化策略。

空間預(yù)分配

空間預(yù)分配用于優(yōu)化 SDS 的字符串增長操作： 當(dāng) SDS 的 API 對一個 SDS 進(jìn)行修改， 并且需要對 SDS 進(jìn)行空間擴(kuò)展的時候， 程序不僅會為 SDS 分配修改所必須要的空間， 還會為 SDS 分配額外的未使用空間。

其中， 額外分配的未使用空間數(shù)量由以下公式?jīng)Q定：

• 如果對 SDS 進(jìn)行修改之后， SDS 的長度（也即是?len?屬性的值）將小于?1?MB?， 那么程序分配和?len?屬性同樣大小的未使用空間， 這時 SDS?len?屬性的值將和?free?屬性的值相同。 舉個例子， 如果進(jìn)行修改之后， SDS 的?len?將變成?13?字節(jié)， 那么程序也會分配13?字節(jié)的未使用空間， SDS 的?buf?數(shù)組的實(shí)際長度將變成?13?+?13?+?1?=?27?字節(jié)（額外的一字節(jié)用于保存空字符）。
• 如果對 SDS 進(jìn)行修改之后， SDS 的長度將大于等于?1?MB?， 那么程序會分配?1?MB?的未使用空間。 舉個例子， 如果進(jìn)行修改之后， SDS 的?len?將變成?30?MB?， 那么程序會分配?1?MB?的未使用空間， SDS 的?buf?數(shù)組的實(shí)際長度將為?30?MB?+?1?MB?+?1?byte?。

通過空間預(yù)分配策略， Redis 可以減少連續(xù)執(zhí)行字符串增長操作所需的內(nèi)存重分配次數(shù)。

舉個例子， 對于圖 2-11 所示的 SDS 值?s?來說， 如果我們執(zhí)行：

sdscat(s, " Cluster");

那么?sdscat?將執(zhí)行一次內(nèi)存重分配操作， 將 SDS 的長度修改為?13?字節(jié)， 并將 SDS 的未使用空間同樣修改為?13?字節(jié)， 如圖 2-12 所示。

如果這時， 我們再次對?s?執(zhí)行：

sdscat(s, " Tutorial");

那么這次?sdscat?將不需要執(zhí)行內(nèi)存重分配： 因為未使用空間里面的?13?字節(jié)足以保存?9?字節(jié)的?"?Tutorial"?， 執(zhí)行?sdscat?之后的 SDS 如圖 2-13 所示。

在擴(kuò)展 SDS 空間之前， SDS API 會先檢查未使用空間是否足夠， 如果足夠的話， API 就會直接使用未使用空間， 而無須執(zhí)行內(nèi)存重分配。

通過這種預(yù)分配策略， SDS 將連續(xù)增長?N?次字符串所需的內(nèi)存重分配次數(shù)從必定?N?次降低為最多?N?次。

惰性空間釋放

惰性空間釋放用于優(yōu)化 SDS 的字符串縮短操作： 當(dāng) SDS 的 API 需要縮短 SDS 保存的字符串時， 程序并不立即使用內(nèi)存重分配來回收縮短后多出來的字節(jié)， 而是使用?free?屬性將這些字節(jié)的數(shù)量記錄起來， 并等待將來使用。

舉個例子，?sdstrim?函數(shù)接受一個 SDS 和一個 C 字符串作為參數(shù)， 從 SDS 左右兩端分別移除所有在 C 字符串中出現(xiàn)過的字符。

比如對于圖 2-14 所示的 SDS 值?s?來說， 執(zhí)行：

sdstrim(s, "XY");   // 移除 SDS 字符串中的所有 'X' 和 'Y'

會將 SDS 修改成圖 2-15 所示的樣子。

注意執(zhí)行?sdstrim?之后的 SDS 并沒有釋放多出來的?8?字節(jié)空間， 而是將這?8?字節(jié)空間作為未使用空間保留在了 SDS 里面， 如果將來要對 SDS 進(jìn)行增長操作的話， 這些未使用空間就可能會派上用場。

舉個例子， 如果現(xiàn)在對?s?執(zhí)行：

sdscat(s, " Redis");

那么完成這次?sdscat?操作將不需要執(zhí)行內(nèi)存重分配： 因為 SDS 里面預(yù)留的?8?字節(jié)空間已經(jīng)足以拼接?6?個字節(jié)長的?"?Redis"?， 如圖 2-16 所示。

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

與此同時， SDS 也提供了相應(yīng)的 API ， 讓我們可以在有需要時， 真正地釋放 SDS 里面的未使用空間， 所以不用擔(dān)心惰性空間釋放策略會造成內(nèi)存浪費(fèi)。

二進(jìn)制安全

C 字符串中的字符必須符合某種編碼（比如 ASCII）， 并且除了字符串的末尾之外， 字符串里面不能包含空字符， 否則最先被程序讀入的空字符將被誤認(rèn)為是字符串結(jié)尾 —— 這些限制使得 C 字符串只能保存文本數(shù)據(jù)， 而不能保存像圖片、音頻、視頻、壓縮文件這樣的二進(jìn)制數(shù)據(jù)。

舉個例子， 如果有一種使用空字符來分割多個單詞的特殊數(shù)據(jù)格式， 如圖 2-17 所示， 那么這種格式就不能使用 C 字符串來保存， 因為 C 字符串所用的函數(shù)只會識別出其中的?"Redis"?， 而忽略之后的?"Cluster"?。

雖然數(shù)據(jù)庫一般用于保存文本數(shù)據(jù)， 但使用數(shù)據(jù)庫來保存二進(jìn)制數(shù)據(jù)的場景也不少見， 因此， 為了確保 Redis 可以適用于各種不同的使用場景， SDS 的 API 都是二進(jìn)制安全的（binary-safe）： 所有 SDS API 都會以處理二進(jìn)制的方式來處理 SDS 存放在?buf?數(shù)組里的數(shù)據(jù)， 程序不會對其中的數(shù)據(jù)做任何限制、過濾、或者假設(shè) —— 數(shù)據(jù)在寫入時是什么樣的， 它被讀取時就是什么樣。

這也是我們將 SDS 的?buf?屬性稱為字節(jié)數(shù)組的原因 —— Redis 不是用這個數(shù)組來保存字符， 而是用它來保存一系列二進(jìn)制數(shù)據(jù)。

比如說， 使用 SDS 來保存之前提到的特殊數(shù)據(jù)格式就沒有任何問題， 因為 SDS 使用?len?屬性的值而不是空字符來判斷字符串是否結(jié)束， 如圖 2-18 所示。

通過使用二進(jìn)制安全的 SDS ， 而不是 C 字符串， 使得 Redis 不僅可以保存文本數(shù)據(jù)， 還可以保存任意格式的二進(jìn)制數(shù)據(jù)。

兼容部分 C 字符串函數(shù)

雖然 SDS 的 API 都是二進(jìn)制安全的， 但它們一樣遵循 C 字符串以空字符結(jié)尾的慣例： 這些 API 總會將 SDS 保存的數(shù)據(jù)的末尾設(shè)置為空字符， 并且總會在為?buf?數(shù)組分配空間時多分配一個字節(jié)來容納這個空字符， 這是為了讓那些保存文本數(shù)據(jù)的 SDS 可以重用一部分?<string.h>庫定義的函數(shù)。

舉個例子， 如圖 2-19 所示， 如果我們有一個保存文本數(shù)據(jù)的 SDS 值?sds?， 那么我們就可以重用?<string.h>/strcasecmp?函數(shù)， 使用它來對比 SDS 保存的字符串和另一個 C 字符串：

strcasecmp(sds->buf, "hello world");

這樣 Redis 就不用自己專門去寫一個函數(shù)來對比 SDS 值和 C 字符串值了。

與此類似， 我們還可以將一個保存文本數(shù)據(jù)的 SDS 作為?strcat?函數(shù)的第二個參數(shù)， 將 SDS 保存的字符串追加到一個 C 字符串的后面：

strcat(c_string, sds->buf);

這樣 Redis 就不用專門編寫一個將 SDS 字符串追加到 C 字符串之后的函數(shù)了。

通過遵循 C 字符串以空字符結(jié)尾的慣例， SDS 可以在有需要時重用?<string.h>?函數(shù)庫， 從而避免了不必要的代碼重復(fù)。

總結(jié)

表 2-1 對 C 字符串和 SDS 之間的區(qū)別進(jìn)行了總結(jié)。

表 2-1 C 字符串和 SDS 之間的區(qū)別

C 字符串	SDS
獲取字符串長度的復(fù)雜度為??。	獲取字符串長度的復(fù)雜度為??。
API 是不安全的，可能會造成緩沖區(qū)溢出。	API 是安全的，不會造成緩沖區(qū)溢出。
修改字符串長度?N?次必然需要執(zhí)行?N?次內(nèi)存重分配。	修改字符串長度?N?次最多需要執(zhí)行?N?次內(nèi)存重分配。
只能保存文本數(shù)據(jù)。	可以保存文本或者二進(jìn)制數(shù)據(jù)。
可以使用所有?<string.h>?庫中的函數(shù)。	可以使用一部分?<string.h>?庫中的函數(shù)。