redis數(shù)據(jù)庫(kù)底層沒(méi)有直接使用c的字符串表示，而是自己使用名為簡(jiǎn)單動(dòng)態(tài)字符串(simple dynamic string,SDS)

SDS定義

struct sdshdr{
    int len;       //記錄buf數(shù)組中以使用字節(jié)的數(shù)量，等于SDS所保存字符串的長(zhǎng)度
    int free;      //記錄buf數(shù)組中未使用字節(jié)的數(shù)量
    char buf[];    //字節(jié)數(shù)組，用于保存字符串 
}

示例

image.png

• free屬性值為0，表示sds沒(méi)有分配任何為使用空間
• len屬性為5，表示這個(gè)sds保存了一個(gè)5個(gè)字節(jié)長(zhǎng)的字符串
• buf屬性表示一個(gè)char類型的數(shù)組，前五個(gè)字節(jié)保存"Redis"，而最后一個(gè)字節(jié)保存空字符'\0'
  注：SDS遵循空字符結(jié)尾的好處是：SDS可以直接重用一部分c字符串函數(shù)庫(kù)的函數(shù)，比如直接打印字符串printf

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

1. 獲取字符串長(zhǎng)度時(shí)間復(fù)雜度不同(提高獲取字符串長(zhǎng)度性能)

• 普通C字符串獲取長(zhǎng)度需要遍歷整個(gè)字符串，因此復(fù)雜度為O(N)。
• SDS的len屬性直接保存字符串的長(zhǎng)度，復(fù)雜度為O(1)

2. SDS杜絕緩沖區(qū)溢出

• C:比如說(shuō)，拼接字符串函數(shù)char *strcat(char *dest,const char *sec)，當(dāng)dest不足夠存放src所有內(nèi)容時(shí)，就會(huì)產(chǎn)生緩沖區(qū)溢出
• SDS:SDS有自己的空間分配策略，當(dāng)SDS的API對(duì)字符串操作時(shí)，API會(huì)先檢查SDS的空間是否滿足操作，不滿足的話API會(huì)自動(dòng)將SDS的空間擴(kuò)展至所需大小，然后才執(zhí)行操作

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

• 當(dāng)C需要修改字符串長(zhǎng)度時(shí)，我們需要再次對(duì)使用內(nèi)存重新分配，由于內(nèi)存重新分配設(shè)計(jì)復(fù)雜的算法，并且可能執(zhí)行系統(tǒng)調(diào)用，所以通常是比較耗時(shí)的操作
• SDS的空間預(yù)分配跟惰性空間釋放會(huì)對(duì)字符串的內(nèi)存分配次數(shù)進(jìn)行優(yōu)化

1.空間預(yù)分配

• 如果對(duì)SDS修改后，SDS的長(zhǎng)度(len)<1MB，則程序?qū)⒎峙浜蚻en屬性同樣大小的free空間
• 如果對(duì)SDS修改后，SDS的長(zhǎng)度(len)>1MB，則程序?qū)⒎峙?MB的free空間

2.惰性空間釋放

• 惰性空間釋放用于優(yōu)化SDS縮短的操作，當(dāng)SDS縮短時(shí)，程序不會(huì)立即進(jìn)行內(nèi)存重新分配，而是用free保存多余出來(lái)的字節(jié)，方便未來(lái)使用

4.二進(jìn)制安全

• C字符串中的字符除了末尾外，不能包含空字符，否則會(huì)被識(shí)別成字符串結(jié)尾
• SDS可以用來(lái)保存二進(jìn)制數(shù)據(jù)，所以SDS的API都是二進(jìn)制安全(binary-safe)的，所有的SDS API 會(huì)以處理二進(jìn)制方式來(lái)處理buf的數(shù)據(jù)。因此數(shù)據(jù)寫入是什么樣的，讀取出來(lái)就是什么樣的。

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

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

總結(jié)