引言

為何redis中大量使用的是SDS，而不是傳統(tǒng)的C語言字符串表示法存儲字符串？到底什么是SDS？為什么要使用SDS？其相對于傳統(tǒng)的C語言字符串有何優(yōu)點？本文會針對以上幾點做一個詳細(xì)的分析，幫助大家以及自己更好的理解redis中的簡單動態(tài)字符串

介紹SDS之前先簡單介紹一下C語言中的傳統(tǒng)字符串表示法

C語言字符串（C字符串）

始終以空字符結(jié)尾的字符數(shù)組，c語言為其封裝了大量的函數(shù)庫操作API

C字符串特點

• 字符數(shù)組存儲

• 以空字符結(jié)尾，除了末尾之外，字符串里面不可以包含空字符

• 由于采用字符數(shù)組，導(dǎo)致所存儲的字符必須符合某種編碼（如ASCII）

• 獲取C字符串長度必須遍歷整個字符串，并對遇到的每個字符計數(shù)，直到遇到空字符為止，時間復(fù)雜度為O(N)

那么基于以上特點，C字符串是否能夠滿足我們Redis高效，安全的需求呢？顯然是不能的，單是一個獲取字符串長度就需要遍歷整個字符串?dāng)?shù)組了，必須重新定義一種新的結(jié)構(gòu)以支持Redis中對于頻繁高效操作字符串的要求

SDS 簡單動態(tài)字符串

基于以上C字符串的缺陷，Redis自己構(gòu)建了一種名為簡單動態(tài)字符串的抽象類型，簡稱SDS

SDS結(jié)構(gòu)

struct sdshdr {

    // buf數(shù)組已經(jīng)使用字節(jié)數(shù)量，即SDS字符串長度
    int len;

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

    // 字節(jié)數(shù)組，用于保存二進(jìn)制數(shù)據(jù)
    char buf[];
}

可以看出，SDS定義的結(jié)構(gòu)中，增加了一個int類型的len屬性用于記錄SDS所保存的字符串長度，一個free屬性用于記錄數(shù)組中未使用的字節(jié)數(shù)量

SDS特點

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

Redis中利用SDS字符串的len屬性可以直接獲取到所保存的字符串的長
度，直接將獲取字符串長度所需的復(fù)雜度從C字符串的O(N)降低到了O(1)

• 減少修改字符串時導(dǎo)致的內(nèi)存重新分配次數(shù)

基于前面介紹的C字符串的特性，我們知道對于一個包含了N個字符的C字符串來說，其底層實現(xiàn)總是N+1個字符長的數(shù)組（額外一個空字符結(jié)尾），那么如果這個時候需要對字符串進(jìn)行修改，程序就需要提前對這個C字符串?dāng)?shù)組進(jìn)行一次內(nèi)存重分配（可能是擴(kuò)展或者釋放），而內(nèi)存重分配就意味著是一個耗時的操作

Redis巧妙的使用了SDS避免了C字符串的缺陷，再SDS中，buf數(shù)組的長度不一定就是字符串的字符數(shù)量加一，buf數(shù)組里面可以包含未使用的字節(jié)，而這些未使用的字節(jié)由free屬性記錄

SDS采用了空間預(yù)分配策略避免C字符串每一次修改時都需要進(jìn)行內(nèi)存重分配的耗時操作，將內(nèi)存重分配從原來的每修改N次就分配N次降低到了修改N次最多分配N次

字符串?dāng)U展：

首先檢查SDS未使用空間即free屬性是否夠用，如果夠用，則會直接使用未使用空間，而無須進(jìn)行內(nèi)存重分配

空間預(yù)分配

所謂預(yù)分配就是額外多分配一部分空間給SDS，并不是僅僅只分配剛好夠字符串?dāng)U展修改后的空間

分配策略：

2. 若SDS修改后，其長度（len的屬性）小于1MB，那么程序會分配和修改后的len屬性同樣大小的未使用空間

3. 若修改后，其長度大于1MB，那么程序只會分配固定1MB的未使用空間，不會再多分配了，考慮內(nèi)存的成本因素

字符串縮短：

針對SDS字符串的縮短場景，SDS并不會立即釋放多余出來的內(nèi)存空間，而是將這部分內(nèi)存空間記錄再其free屬性中，當(dāng)SDS字符串進(jìn)行擴(kuò)展時，這部分未使用的內(nèi)存空間就能直接用，而不需要進(jìn)行內(nèi)存重分配，這就是SDS的惰性空間釋放

• 杜絕緩沖區(qū)溢出

在C字符串的拼接操作過程中，例如某程序員操作S1拼接S2，由于程序員忘記了給需要拼接的字符串S1分配足夠的內(nèi)存空間（到底需要分配多少內(nèi)存呢？哈哈，當(dāng)然需要遍歷S2的字符數(shù)組才能知道S2的長度是多少，因為C字符串不記錄自身的長度），那么拼接的時候就會導(dǎo)致緩沖區(qū)溢出的可能性

針對以上情況，SDS的空間分配策略可以完全杜絕這種情況，因為當(dāng)SDS 的API對SDS進(jìn)行修改時，API會首先檢查SDS的未使用空間是否足夠，不夠的化會進(jìn)行內(nèi)存重分配以擴(kuò)展空間至足夠修改所需的大小，然后再執(zhí)行實際的修改操作，這樣就可以達(dá)到杜絕緩沖區(qū)溢出的可能

• 讓Redis保存更多類型的數(shù)據(jù)成為可能

由于C字符串中保存的字符必須符合某種編碼格式（如ASCII），這就限制了C字符串只能保存文本數(shù)據(jù)，而不能保存箱視頻，音頻，壓縮文件這種的二進(jìn)制數(shù)據(jù)

另一個限制是C字符串中間不能包含空字符，否則中間的空字符會被認(rèn)為是整個字符串的結(jié)尾，而導(dǎo)致后面的部分字符被忽略掉

SDS的API被設(shè)計成了二進(jìn)制安全的，以處理二進(jìn)制的方式來處理SDS中存放再buf數(shù)組中的數(shù)據(jù)，原樣存取，這就是為什么在SDS的結(jié)構(gòu)中采用的是字節(jié)數(shù)組，而不是C字符串中的字符數(shù)組

這樣的二進(jìn)制安全的SDS，使得Redis不僅可以保存文本，還可以保存任意格式的二進(jìn)制數(shù)據(jù)

• 兼容部分C字符串API

由于C字符串本身具有大量操作API，SDS如果可以利用一部分C字符串的API那樣就不用重復(fù)發(fā)明輪子了，所以Redis中的SDS遵循C字符串以空字符結(jié)尾的慣例，在SDS的API中，總會將SDS保存的數(shù)據(jù)末尾設(shè)置未空字符，在分配buf數(shù)組時也總會多分配一個字節(jié)來保存這個空字符，這樣SDS就可以重用一部分C字符串庫的API

C字符串與SDS對比

總結(jié)

Redis中采用SDS替代C語言中傳統(tǒng)字符串表示法，提升了獲取字符串長度的效率，擴(kuò)大了能夠保存數(shù)據(jù)的類型范圍，以及降低了每次修改字符串時候的內(nèi)存重分配次數(shù)，甚至規(guī)避了在操作C字符串中可能出現(xiàn)的緩沖區(qū)內(nèi)存溢出的可能性，從而為Redis中字符串操作的安全，高效提供了保障。