SDS 與 C 字符串的區(qū)別

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

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

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

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

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

舉個(gè)例子， 圖 2-4 展示了程序計(jì)算一個(gè) C 字符串長(zhǎng)度的過(guò)程。

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

舉個(gè)例子， 對(duì)于圖 2-5 所示的 SDS 來(lái)說(shuō)， 程序只要訪問(wèn) SDS 的?len?屬性， 就可以立即知道 SDS 的長(zhǎng)度為?5?字節(jié)：

又比如說(shuō)， 對(duì)于圖 2-6 展示的 SDS 來(lái)說(shuō)， 程序只要訪問(wèn) SDS 的?len?屬性， 就可以立即知道 SDS 的長(zhǎng)度為?11?字節(jié)。

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

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

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

杜絕緩沖區(qū)溢出

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

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

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

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

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

如果一個(gè)程序員決定通過(guò)執(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 需要對(duì) SDS 進(jìn)行修改時(shí)， API 會(huì)先檢查 SDS 的空間是否滿足修改所需的要求， 如果不滿足的話， API 會(huì)自動(dòng)將 SDS 的空間擴(kuò)展至執(zhí)行修改所需的大小， 然后才執(zhí)行實(shí)際的修改操作， 所以使用 SDS 既不需要手動(dòng)修改 SDS 的空間大小， 也不會(huì)出現(xiàn)前面所說(shuō)的緩沖區(qū)溢出問(wèn)題。

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

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

sdscat(s, " Cluster");

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

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

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

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

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

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

舉個(gè)例子， 如果我們持有一個(gè)值為?"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?的空間， 諸如此類。

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

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

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

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

空間預(yù)分配

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

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

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

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

舉個(gè)例子， 對(duì)于圖 2-11 所示的 SDS 值?s?來(lái)說(shuō)， 如果我們執(zhí)行：

sdscat(s, " Cluster");

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

如果這時(shí)， 我們?cè)俅螌?duì)?s?執(zhí)行：

sdscat(s, " Tutorial");

那么這次?sdscat?將不需要執(zhí)行內(nèi)存重分配： 因?yàn)槲词褂每臻g里面的?13?字節(jié)足以保存?9?字節(jié)的?"?Tutorial"?， 執(zhí)行?sdscat?之后的 SDS 如圖 2-13 所示。

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

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

惰性空間釋放

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

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

比如對(duì)于圖 2-14 所示的 SDS 值?s?來(lái)說(shuō)， 執(zhí)行：

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

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

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

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

sdscat(s, " Redis");

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

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

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

二進(jìn)制安全

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

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

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

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

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

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

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

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

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

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

這樣 Redis 就不用自己專門(mén)去寫(xiě)一個(gè)函數(shù)來(lái)對(duì)比 SDS 值和 C 字符串值了。

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

strcat(c_string, sds->buf);

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

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

總結(jié)

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

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

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