根據傳統， C 語言使用長度為?`N+1`?的字符數組來表示長度為?`N`?的字符串， 并且字符數組的最后一個元素總是空字符?`'\0'`?。 比如說， 圖 2-3 就展示了一個值為?`"Redis"`?的 C 字符串：  C 語言使用的這種簡單的字符串表示方式， 并不能滿足 Redis 對字符串在安全性、效率、以及功能方面的要求， 本節接下來的內容將詳細對比 C 字符串和 SDS 之間的區別， 并說明 SDS 比 C 字符串更適用于 Redis 的原因。 ## 常數復雜度獲取字符串長度 因為 C 字符串并不記錄自身的長度信息， 所以為了獲取一個 C 字符串的長度， 程序必須遍歷整個字符串， 對遇到的每個字符進行計數， 直到遇到代表字符串結尾的空字符為止， 這個操作的復雜度為??。 舉個例子， 圖 2-4 展示了程序計算一個 C 字符串長度的過程。       和 C 字符串不同， 因為 SDS 在?`len`?屬性中記錄了 SDS 本身的長度， 所以獲取一個 SDS 長度的復雜度僅為??。 舉個例子， 對于圖 2-5 所示的 SDS 來說， 程序只要訪問 SDS 的?`len`?屬性， 就可以立即知道 SDS 的長度為?`5`?字節：  又比如說， 對于圖 2-6 展示的 SDS 來說， 程序只要訪問 SDS 的?`len`?屬性， 就可以立即知道 SDS 的長度為?`11`?字節。  設置和更新 SDS 長度的工作是由 SDS 的 API 在執行時自動完成的， 使用 SDS 無須進行任何手動修改長度的工作。 通過使用 SDS 而不是 C 字符串， Redis 將獲取字符串長度所需的復雜度從??降低到了??， 這確保了獲取字符串長度的工作不會成為 Redis 的性能瓶頸。 比如說， 因為字符串鍵在底層使用 SDS 來實現， 所以即使我們對一個非常長的字符串鍵反復執行?STRLEN?命令， 也不會對系統性能造成任何影響， 因為?STRLEN?命令的復雜度僅為??。 ## 杜絕緩沖區溢出 除了獲取字符串長度的復雜度高之外， C 字符串不記錄自身長度帶來的另一個問題是容易造成緩沖區溢出（buffer overflow）。 舉個例子，?`<string.h>/strcat`?函數可以將?`src`?字符串中的內容拼接到?`dest`?字符串的末尾： ~~~ char *strcat(char *dest, const char *src); ~~~ 因為 C 字符串不記錄自身的長度， 所以?`strcat`?假定用戶在執行這個函數時， 已經為?`dest`?分配了足夠多的內存， 可以容納?`src`?字符串中的所有內容， 而一旦這個假定不成立時， 就會產生緩沖區溢出。 舉個例子， 假設程序里有兩個在內存中緊鄰著的 C 字符串?`s1`?和?`s2`?， 其中?`s1`?保存了字符串?`"Redis"`?， 而?`s2`?則保存了字符串?`"MongoDB"`， 如圖 2-7 所示。  如果一個程序員決定通過執行： ~~~ strcat(s1, " Cluster"); ~~~ 將?`s1`?的內容修改為?`"Redis?Cluster"`?， 但粗心的他卻忘了在執行?`strcat`?之前為?`s1`?分配足夠的空間， 那么在?`strcat`?函數執行之后，?`s1`?的數據將溢出到?`s2`?所在的空間中， 導致?`s2`?保存的內容被意外地修改， 如圖 2-8 所示。  與 C 字符串不同， SDS 的空間分配策略完全杜絕了發生緩沖區溢出的可能性： 當 SDS API 需要對 SDS 進行修改時， API 會先檢查 SDS 的空間是否滿足修改所需的要求， 如果不滿足的話， API 會自動將 SDS 的空間擴展至執行修改所需的大小， 然后才執行實際的修改操作， 所以使用 SDS 既不需要手動修改 SDS 的空間大小， 也不會出現前面所說的緩沖區溢出問題。 舉個例子， SDS 的 API 里面也有一個用于執行拼接操作的?`sdscat`?函數， 它可以將一個 C 字符串拼接到給定 SDS 所保存的字符串的后面， 但是在執行拼接操作之前，?`sdscat`?會先檢查給定 SDS 的空間是否足夠， 如果不夠的話，?`sdscat`?就會先擴展 SDS 的空間， 然后才執行拼接操作。 比如說， 如果我們執行： ~~~ sdscat(s, " Cluster"); ~~~ 其中 SDS 值?`s`?如圖 2-9 所示， 那么?`sdscat`?將在執行拼接操作之前檢查?`s`?的長度是否足夠， 在發現?`s`?目前的空間不足以拼接?`"?Cluster"`之后，?`sdscat`?就會先擴展?`s`?的空間， 然后才執行拼接?`"?Cluster"`?的操作， 拼接操作完成之后的 SDS 如圖 2-10 所示。   注意圖 2-10 所示的 SDS ：?`sdscat`?不僅對這個 SDS 進行了拼接操作， 它還為 SDS 分配了?`13`?字節的未使用空間， 并且拼接之后的字符串也正好是?`13`?字節長， 這種現象既不是 bug 也不是巧合， 它和 SDS 的空間分配策略有關， 接下來的小節將對這一策略進行說明。 ## 減少修改字符串時帶來的內存重分配次數 正如前兩個小節所說， 因為 C 字符串并不記錄自身的長度， 所以對于一個包含了?`N`?個字符的 C 字符串來說， 這個 C 字符串的底層實現總是一個?`N+1`?個字符長的數組（額外的一個字符空間用于保存空字符）。 因為 C 字符串的長度和底層數組的長度之間存在著這種關聯性， 所以每次增長或者縮短一個 C 字符串， 程序都總要對保存這個 C 字符串的數組進行一次內存重分配操作： * 如果程序執行的是增長字符串的操作， 比如拼接操作（append）， 那么在執行這個操作之前， 程序需要先通過內存重分配來擴展底層數組的空間大小 —— 如果忘了這一步就會產生緩沖區溢出。 * 如果程序執行的是縮短字符串的操作， 比如截斷操作（trim）， 那么在執行這個操作之后， 程序需要通過內存重分配來釋放字符串不再使用的那部分空間 —— 如果忘了這一步就會產生內存泄漏。 舉個例子， 如果我們持有一個值為?`"Redis"`?的 C 字符串?`s`?， 那么為了將?`s`?的值改為?`"Redis?Cluster"`?， 在執行： ~~~ strcat(s, " Cluster"); ~~~ 之前， 我們需要先使用內存重分配操作， 擴展?`s`?的空間。 之后， 如果我們又打算將?`s`?的值從?`"Redis?Cluster"`?改為?`"Redis?Cluster?Tutorial"`?， 那么在執行： ~~~ strcat(s, " Tutorial"); ~~~ 之前， 我們需要再次使用內存重分配擴展?`s`?的空間， 諸如此類。 因為內存重分配涉及復雜的算法， 并且可能需要執行系統調用， 所以它通常是一個比較耗時的操作： * 在一般程序中， 如果修改字符串長度的情況不太常出現， 那么每次修改都執行一次內存重分配是可以接受的。 * 但是 Redis 作為數據庫， 經常被用于速度要求嚴苛、數據被頻繁修改的場合， 如果每次修改字符串的長度都需要執行一次內存重分配的話， 那么光是執行內存重分配的時間就會占去修改字符串所用時間的一大部分， 如果這種修改頻繁地發生的話， 可能還會對性能造成影響。 為了避免 C 字符串的這種缺陷， SDS 通過未使用空間解除了字符串長度和底層數組長度之間的關聯： 在 SDS 中，?`buf`?數組的長度不一定就是字符數量加一， 數組里面可以包含未使用的字節， 而這些字節的數量就由 SDS 的?`free`?屬性記錄。 通過未使用空間， SDS 實現了空間預分配和惰性空間釋放兩種優化策略。 ### 空間預分配 空間預分配用于優化 SDS 的字符串增長操作： 當 SDS 的 API 對一個 SDS 進行修改， 并且需要對 SDS 進行空間擴展的時候， 程序不僅會為 SDS 分配修改所必須要的空間， 還會為 SDS 分配額外的未使用空間。 其中， 額外分配的未使用空間數量由以下公式決定： * 如果對 SDS 進行修改之后， SDS 的長度（也即是?`len`?屬性的值）將小于?`1?MB`?， 那么程序分配和?`len`?屬性同樣大小的未使用空間， 這時 SDS?`len`?屬性的值將和?`free`?屬性的值相同。 舉個例子， 如果進行修改之后， SDS 的?`len`?將變成?`13`?字節， 那么程序也會分配`13`?字節的未使用空間， SDS 的?`buf`?數組的實際長度將變成?`13?+?13?+?1?=?27`?字節（額外的一字節用于保存空字符）。 * 如果對 SDS 進行修改之后， SDS 的長度將大于等于?`1?MB`?， 那么程序會分配?`1?MB`?的未使用空間。 舉個例子， 如果進行修改之后， SDS 的?`len`?將變成?`30?MB`?， 那么程序會分配?`1?MB`?的未使用空間， SDS 的?`buf`?數組的實際長度將為?`30?MB?+?1?MB?+?1?byte`?。 通過空間預分配策略， Redis 可以減少連續執行字符串增長操作所需的內存重分配次數。 舉個例子， 對于圖 2-11 所示的 SDS 值?`s`?來說， 如果我們執行： ~~~ sdscat(s, " Cluster"); ~~~ 那么?`sdscat`?將執行一次內存重分配操作， 將 SDS 的長度修改為?`13`?字節， 并將 SDS 的未使用空間同樣修改為?`13`?字節， 如圖 2-12 所示。   如果這時， 我們再次對?`s`?執行： ~~~ sdscat(s, " Tutorial"); ~~~ 那么這次?`sdscat`?將不需要執行內存重分配： 因為未使用空間里面的?`13`?字節足以保存?`9`?字節的?`"?Tutorial"`?， 執行?`sdscat`?之后的 SDS 如圖 2-13 所示。  在擴展 SDS 空間之前， SDS API 會先檢查未使用空間是否足夠， 如果足夠的話， API 就會直接使用未使用空間， 而無須執行內存重分配。 通過這種預分配策略， SDS 將連續增長?`N`?次字符串所需的內存重分配次數從必定?`N`?次降低為最多?`N`?次。 ### 惰性空間釋放 惰性空間釋放用于優化 SDS 的字符串縮短操作： 當 SDS 的 API 需要縮短 SDS 保存的字符串時， 程序并不立即使用內存重分配來回收縮短后多出來的字節， 而是使用?`free`?屬性將這些字節的數量記錄起來， 并等待將來使用。 舉個例子，?`sdstrim`?函數接受一個 SDS 和一個 C 字符串作為參數， 從 SDS 左右兩端分別移除所有在 C 字符串中出現過的字符。 比如對于圖 2-14 所示的 SDS 值?`s`?來說， 執行： ~~~ sdstrim(s, "XY"); // 移除 SDS 字符串中的所有 'X' 和 'Y' ~~~ 會將 SDS 修改成圖 2-15 所示的樣子。   注意執行?`sdstrim`?之后的 SDS 并沒有釋放多出來的?`8`?字節空間， 而是將這?`8`?字節空間作為未使用空間保留在了 SDS 里面， 如果將來要對 SDS 進行增長操作的話， 這些未使用空間就可能會派上用場。 舉個例子， 如果現在對?`s`?執行： ~~~ sdscat(s, " Redis"); ~~~ 那么完成這次?`sdscat`?操作將不需要執行內存重分配： 因為 SDS 里面預留的?`8`?字節空間已經足以拼接?`6`?個字節長的?`"?Redis"`?， 如圖 2-16 所示。  通過惰性空間釋放策略， SDS 避免了縮短字符串時所需的內存重分配操作， 并為將來可能有的增長操作提供了優化。 與此同時， SDS 也提供了相應的 API ， 讓我們可以在有需要時， 真正地釋放 SDS 里面的未使用空間， 所以不用擔心惰性空間釋放策略會造成內存浪費。 ## 二進制安全 C 字符串中的字符必須符合某種編碼（比如 ASCII）， 并且除了字符串的末尾之外， 字符串里面不能包含空字符， 否則最先被程序讀入的空字符將被誤認為是字符串結尾 —— 這些限制使得 C 字符串只能保存文本數據， 而不能保存像圖片、音頻、視頻、壓縮文件這樣的二進制數據。 舉個例子， 如果有一種使用空字符來分割多個單詞的特殊數據格式， 如圖 2-17 所示， 那么這種格式就不能使用 C 字符串來保存， 因為 C 字符串所用的函數只會識別出其中的?`"Redis"`?， 而忽略之后的?`"Cluster"`?。  雖然數據庫一般用于保存文本數據， 但使用數據庫來保存二進制數據的場景也不少見， 因此， 為了確保 Redis 可以適用于各種不同的使用場景， SDS 的 API 都是二進制安全的（binary-safe）： 所有 SDS API 都會以處理二進制的方式來處理 SDS 存放在?`buf`?數組里的數據， 程序不會對其中的數據做任何限制、過濾、或者假設 —— 數據在寫入時是什么樣的， 它被讀取時就是什么樣。 這也是我們將 SDS 的?`buf`?屬性稱為字節數組的原因 —— Redis 不是用這個數組來保存字符， 而是用它來保存一系列二進制數據。 比如說， 使用 SDS 來保存之前提到的特殊數據格式就沒有任何問題， 因為 SDS 使用?`len`?屬性的值而不是空字符來判斷字符串是否結束， 如圖 2-18 所示。  通過使用二進制安全的 SDS ， 而不是 C 字符串， 使得 Redis 不僅可以保存文本數據， 還可以保存任意格式的二進制數據。 ## 兼容部分 C 字符串函數 雖然 SDS 的 API 都是二進制安全的， 但它們一樣遵循 C 字符串以空字符結尾的慣例： 這些 API 總會將 SDS 保存的數據的末尾設置為空字符， 并且總會在為?`buf`?數組分配空間時多分配一個字節來容納這個空字符， 這是為了讓那些保存文本數據的 SDS 可以重用一部分?`<string.h>`庫定義的函數。  舉個例子， 如圖 2-19 所示， 如果我們有一個保存文本數據的 SDS 值?`sds`?， 那么我們就可以重用?`<string.h>/strcasecmp`?函數， 使用它來對比 SDS 保存的字符串和另一個 C 字符串： ~~~ strcasecmp(sds->buf, "hello world"); ~~~ 這樣 Redis 就不用自己專門去寫一個函數來對比 SDS 值和 C 字符串值了。 與此類似， 我們還可以將一個保存文本數據的 SDS 作為?`strcat`?函數的第二個參數， 將 SDS 保存的字符串追加到一個 C 字符串的后面： ~~~ strcat(c_string, sds->buf); ~~~ 這樣 Redis 就不用專門編寫一個將 SDS 字符串追加到 C 字符串之后的函數了。 通過遵循 C 字符串以空字符結尾的慣例， SDS 可以在有需要時重用?`<string.h>`?函數庫， 從而避免了不必要的代碼重復。 ## 總結 表 2-1 對 C 字符串和 SDS 之間的區別進行了總結。 * * * 表 2-1 C 字符串和 SDS 之間的區別 | C 字符串 | SDS | | --- | --- | | 獲取字符串長度的復雜度為??。 | 獲取字符串長度的復雜度為??。 | | API 是不安全的，可能會造成緩沖區溢出。 | API 是安全的，不會造成緩沖區溢出。 | | 修改字符串長度?`N`?次必然需要執行?`N`?次內存重分配。 | 修改字符串長度?`N`?次最多需要執行?`N`?次內存重分配。 | | 只能保存文本數據。 | 可以保存文本或者二進制數據。 | | 可以使用所有?`<string.h>`?庫中的函數。 | 可以使用一部分?`<string.h>`?庫中的函數。 |