1. 概述

• Redis沒有直接使用C語言傳統的字符串表示，而是自己構建了一種名為簡單動態字符串（ simple dynamic string，SDS ）的抽象類型,并將SDS用作Redis的默認字符串表示。

• 如果客戶端執行如下命令

redis> RPUSH fruits "apple""banana""cherry"
(integer) 3

• 那么Redis將在數據庫中創建一個新的鍵值對,其中:

鍵值對的鍵是一個字符串對象，對象的底層實現是一個 保存了字符串"fruits"的SDS。

鍵值對的值是一個列表對象，列表對象包含了三個字符串對象，這三個字符串對象分別由三個SDS實現: 第一個SDS保存著字符串"apple"，第二個SDS保存著字符串"banana"，第三個SDS保存著字符串"cherry"。

• 除了用來保存數據庫中的字符串值之外，SDS還被用作緩沖區（ buffer ) :

AOF模塊中的AOF緩沖區，以及客戶端狀態中的輸人緩沖區，都是由SDS實現的，在之后介紹AOF持久化和客戶端狀態的時候，我們會看到SDS在這兩個模塊中的應用。

2. SDS的定義

• SDS數據結構

• 對于圖2-1解釋如下

free屬性的值為0，表示這個SDS沒有分配任何未使用空間。

len屬性的值為5，表示這個SDS保存了一個五字節長的字符串。

buf屬性是一個char類型的數組，數組的 前五個字節分別保存了'R'、'e'、'd '、'i'、's'五個字符，而最后一個字節則保存了空字符'\0*'。

SDS遵循C字符串以空字符結尾的慣例， 保存空字符的1字節空間不計算在SDS的len屬性里面，并且為空字符分配額外的1字節空間，以及添加空字符到字符串末尾等操作，都是由SDS函數自動完成的，所以這個空字符對于SDS的使用者來說是完全透明的。遵循空字符結尾這一慣例的好處是， SDS可以直接重用一部分C字符串函數庫里面的函數。

3. 選擇SDS而不是C字符串

3.1 獲取字符串長度是常數復雜度

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

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

3.2 杜絕緩沖區溢出

3.2.1 C字符串的緩沖區溢出問題

strcat函數可以將src字符串中的內容拼接到dest字符串的末尾,因為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所示。

3.2.2 SDS杜絕緩沖區區溢出

當SDS API需要對SDS進行修改時，API會先檢查SDS的空間是否滿足修改所需的要求， 如果不滿足的話，API會自動將SDS的空間擴展至執行修改所需的大小，然后才執行實際的修改操作，所以使用SDS既不需要手動修改SDS的空間大小，也不會出現前面所說的緩沖區溢出問題。

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

其中SDS值s 如圖2-9所示，那么sdscat將在執行拼接操作之前檢查s的長度是否足夠，在發現s目前的空間不足以拼接"cluster"之后，sdscat就會先擴展s的空間，然后才執行拼接"cluster"的操作，拼接操作完成之后的SDS 如圖2-10所示。

圖2-10所示的SDS， sdscat不僅對這個SDS進行了拼接操作，它還為SDS分配了13字節的未使用空間，并且拼接之后的字符串也正好是13字節長，這種現象既不是bug 也不是巧合，它和SDS的空間分配策略有關

3.3 減少修改字符串的內存重分配次數

3.3.1 內存重分配

• C字符串并不記錄自身的長度，所以對于一個包含了N個字符的C字符串來說，這個C字符串的底層實現總是一個N+1個字符長的數組（額外的一個字符空間用于保存空字符)。因為C字符串的長度和底層數組的長度之間存在著這種關聯性，所以每次增長或者縮短一個C字符串，程序都總要對保存這個C字符串的數組進行一次內存重分配操作:

• 內存重分配的隱患

如果程序執行的是增長字符串的操作，比如拼接操作（( append )，那么在執行這個操作之前， 程序需要先通過內存重分配來擴展底層數組的空間大小——如果忘了這一步就會產生緩沖區溢出。

如果程序執行的是縮短字符串的操作，比如截斷操作( trim )，那么在執行這個操作之后， 程序需要通過內存重分配來釋放字符串不再使用的那部分空間——如果忘了這一步就會產生內存泄漏。

• 內存重分配的缺點

因為內存重分配涉及復雜的算法，并且可能需要執行系統調用，所以它 通常是一個比較耗時的操作:

Redis作為數據庫，經常被用于速度要求嚴苛、數據被頻繁修改的場合，如果每次修改字符串的長度都需要執行一次內存重分配的話，那么光是執行內存重分配的時間就會占去修改字符串所用時間的一大部分， 如果這種修改頻繁地發生的話，可能還會對性能造成影響。

3.3.2 SDS優化策略

• 為了避免C字符串的這種缺陷，SDS通過未使用空間解除了字符串長度和底層數組長度之間的關聯:在SDS 中，buf數組的長度不一定就是字符數量加一，數組里面可以包含未使用的字節，而這些字節的數量就由SDS的free屬性記錄。通過未使用空間，SDS實現了空間預分配和惰性空間釋放兩種優化策略

• 優化策略-空間預分配

空間預分配用于優化SDS 的字符串增長操作:當SDS 的API對一個SDS進行修改,并且需要對SDS進行空間擴展的時候，程序不僅會為SDS分配修改所必須要的空間，還會為SDS 分配額外的未使用空間。其中，額外分配的未使用空間數量由以下公式決定

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

如果對SDS進行修改之后， SDS的長度將大于等于1MB，那么程序會分配1MB的未使用空間。舉個例子，如果進行修改之后，SDS的len 將變成30MB，那么程序會分配1MB的未使用空間，SDS的buf數組的實際長度將為 30 MB + 1MB + 1byte。

之后再次增長字符串長度時就無需進行內存重分配了，通過這種預分配策略，SDS將連續增N次字符串所需的內存重分配次數從必定N次降低為最多N次。

• 優化策略-惰性空間釋放

惰性空間釋放用于優化SDS的字符串縮短操作:當SDS的API需要縮短SDS保存的字符串時，程序并不立即使用內存重分配來回收縮短后多出來的字節，而是使用free屬性將這些字節的數量記錄起來，并等待將來使用。

3.4 二進制安全

• C字符串無法存儲二進制數據

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

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

SDS可以存儲二進制數據

因為SDS 使用len屬性的值而不是空字符來判斷字符串是否結束，所以使用SDS來保存之前提到的特殊數據格式沒有任何問題

3.5 兼容部分C字符串函數

• 我們有一個保存文本數據的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>函數庫，從而避免了不必要的代碼重復。

3.6 總結對比

• C字符串和SDS之間的區別如下表所示

3.7 SDS常用API

• SDS常用API如下表所示