??Redis沒有直接使用C語言傳統(tǒng)的字符串表示，而是構(gòu)建了一種名為簡單動態(tài)字符串（simple dynamic string，SDS）的抽象類型，并將SDS作為默認的字符串表示。

1 SDS定義

struct sdshdr{
    // 記錄buf數(shù)組已經(jīng)使用字節(jié)的數(shù)量
    // 等于SDS所保存字符串的長度
    int len;

    // 記錄buf數(shù)組中未使用字節(jié)的數(shù)量
    int free;

    // 字節(jié)數(shù)組
    char buf[];
}

SDS示例

??上圖展示了一個SDS示例：

(1) free屬性值為3，表示這個SDS還有3個未使用的空間。
(2) len屬性的值為5，表示這個SDS保存了一個5個字節(jié)長的字符串。
(3) buf屬性是一個char類型的數(shù)組，數(shù)據(jù)的前5個字節(jié)分別了‘R’、'e'、 'd'、 'i'、 's' 五個字符，而最后一個字節(jié)保存了空字符‘\0’。

??SDS遵循C字符串結(jié)尾的慣例，保存空字符串的1個字節(jié)空你就按不計算在SDS的len屬性里面，并且為空字符分配額外的1個字節(jié)空間。

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

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

??C字符串不記錄自身的長度信息，所以為了獲取一個C字符串的長度，需要遍歷整個字符串，直到遇到代表字符串結(jié)尾的空字符為止，這個操作的復(fù)雜度為O(N)。而SDS在len屬性中記錄了SDS本身的長度，所以獲取一個SDS長度的復(fù)雜度為O(1)。

??2.2 杜絕緩沖區(qū)溢出

??C字符串不記錄自身長度帶來的另一個問題是容易造成緩沖區(qū)溢出（buffer overflow）。例如，假設(shè)程序里有兩個在內(nèi)存中緊鄰的C字符串s1和s2，其中s1字符串是“Redis”，s2字符串是“MongoDB”，如下圖所示：

??如果一個要執(zhí)行：

strcat(s1," Cluster");

??將s1的內(nèi)容修改為“Redis Cluster”，但是卻執(zhí)行前沒有給s1分配足夠的內(nèi)存空間，那么在執(zhí)行之后，s1的數(shù)據(jù)將會溢出到s2的空間中，導(dǎo)致s2保存的內(nèi)容被意外的修改，如下圖所示。

image.png

??SDS的空間分配策略完全杜絕了發(fā)生緩沖區(qū)溢出的可能性，當(dāng)SDS API需要對SDS修改時，API會先檢查SDS的空間是否滿足修改所需的要求，如果不滿足的話，API會自動將SDS空間擴展至執(zhí)行修改所需的大小。

??注意：上圖的拼接操作之后，它還為SDS分配了13個字節(jié)未使用空間。

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

??因為C字符串不記錄自身的長度，所以對于一個包含了N個字符的C字符串來說，這個C字符串底層實現(xiàn)總是一個N+1個字符長的數(shù)組（額外的一個字符空間用于保存空字符）。正是因為C字符串的長度和底層數(shù)組的長度之間存在這這種關(guān)聯(lián)性，所以每次增長或縮短一個C字符串，程序總是要對保存這個C字符串的數(shù)組進行一次內(nèi)存重分配操作。

(1) 如果執(zhí)行增長字符串的操作，那么在執(zhí)行之前，需要先通過內(nèi)存重分配擴展底層數(shù)組的空間大小，如果沒有執(zhí)行這一步那么會導(dǎo)致緩沖區(qū)溢出。
(2) 如果執(zhí)行縮短字符串的操作，那么在執(zhí)行之后，需要通過內(nèi)存重分配釋放不再使用的那部分內(nèi)存，如果沒有則導(dǎo)致內(nèi)存泄漏。

??SDS通過未使用未使用空間解除了字符串長度和底層數(shù)組的關(guān)聯(lián)：在SDS中，buf數(shù)組的長度不一定是字符數(shù)量加1，數(shù)組中可以包含未使用字節(jié)，而這些字節(jié)數(shù)量就是SDS的free屬性。通過未使用空間，SDS實現(xiàn)了空間預(yù)分配和惰性空間釋放兩種優(yōu)化策略。
??(1) 空間預(yù)分配
??空間預(yù)分配用于優(yōu)化SDS的字符串增長操作：當(dāng)SDS的API對一個SDS 進行修改并且需要對SDS進行空間擴展的時候，程序不僅會為SDS分配修改所必須要的空間，還會為SDS分配額外的未使用空間。
????額外未使用空間的分配規(guī)則：

(1) 如果對SDS進行修改之后，SDS的長度（也即是len屬性的值） 將小于1MB，那么程序分配和len屬性同樣大小的未使用空間， 這時SDS的len屬性的值將和 free屬性的值相同，如上一小節(jié)圖所示。
(2) 如果對SDS進行修改之后，SDS 的長度將大于等千1MB, 那么程序會分配1MB的未用空間。例如，如果進行修改之后，SDS的len將變成30MB, 那么程序會分配1MB的未使用空間，SDS的buf數(shù)組的實際長度將為30 MB + 1MB + 1byte。

??通過空間預(yù)分配策略，Redis可以減少連續(xù)執(zhí)行字符串增長所需的內(nèi)存重分配次數(shù)。
??(2) 惰性空間釋放
惰性空間釋放用于優(yōu)化 SDS的字符串縮短操作：當(dāng) SDS的API需要縮短 SDS保存的字符串時，程序并不立即使用內(nèi)存重分配來回收縮短后多出來的字節(jié)，而是使用free屬性將這些字節(jié)的數(shù)量記錄起來，并等待將來使用。
??例如，sdstrim函數(shù)接受一個 SDS和一個C字符串作為參數(shù)， 移除 SDS中所有在C字符串中出現(xiàn)過的字符。

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

??執(zhí)行sdstrim之后SDS沒有釋放多余的8個字節(jié)的空間，而是將這8個字節(jié)的空間作為未使用的空間保留在SDS里面，如果將來要對SDS進行增長操作，這些未使用的空間就可以使用。

??2.4 二進制安全

C字符串中的字符必須符合某種編碼（比如ASCII)，并且除了字符串的末尾之外，字符串里面不能包含空字符，否則最先被程序讀人的空字符將被誤認為是字符串結(jié)尾，這些限制使得C字符串只能保存文本數(shù)據(jù)。SDS的API都是二進制安全的，所有SDS API都會已處理二進制的方式來處理SDS存放在buf數(shù)組里的數(shù)據(jù)，程序不會對其中的數(shù)據(jù)做任何限制、過濾或者假設(shè)，數(shù)據(jù)寫入時是什么樣子的，讀取的時候就是什么樣的。所以SDS不僅可以保存文本數(shù)據(jù)，還可以保存任意格式的二進制數(shù)據(jù)。

3 小結(jié)

(1) Redis只會使用C字符串作為字面量，在大多數(shù)情況下，Redis使用SDS（Simple Dynamic String，簡單動態(tài)字符串）作為字符串表示。

(2) 比起C字符串，SDS具有以下優(yōu)點：

1 常數(shù)復(fù)雜度獲取字符串長度。
2 杜絕緩沖區(qū)溢出。
3 減少修改字符串長度時所需的內(nèi)存重分配次數(shù)。修改字符串長度N次最多需要執(zhí)行N次內(nèi)存重分配。
4 二進制安全，可以保存任何格式的二進制數(shù)據(jù)。

??本文完

?? 注：本文參考《Redis設(shè)計與實現(xiàn)》，如發(fā)現(xiàn)錯誤，請指正！