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

SDS 定義

每個(gè)sds.h/sdshdr 結(jié)構(gòu)表示一個(gè)SDS值

struct sdshdr {
  int len; // 記錄buf數(shù)組中已使用字節(jié)的數(shù)量 (=SDS所保存字符串的長度)
  int free; // 記錄buf數(shù)組中未使用的字節(jié)的數(shù)量
  char buf[]; // 字節(jié)數(shù)組, 保存字符串  
}

image-SDS.png

• free屬性值為0, 表示 SDS 未分配 未使用空間
• len 屬性為5, 表示 SDS 保存了一個(gè)5字節(jié)長的字符串
• buf 屬性是一個(gè)char類型的數(shù)組, 數(shù)組的前5個(gè)字節(jié)保存了 R, e,d,i, s, 五個(gè)字符, 最后一個(gè)字節(jié)保存了空字符串\0

為什么不使用C原生字符串呢 ?

1. C字符串獲取長度需要遍歷, SDS則記錄了自身長度(len), 將獲取字符串長度的時(shí)間復(fù)雜度從O(N)降低到了O(1), 即使反復(fù)執(zhí)行strlen, 也不會(huì)對系統(tǒng)造成任何影響
2. C字符串不記錄自身長度, 容易造成緩沖區(qū)溢出, eg. strcat可以將字符串拼接, 執(zhí)行這一操作時(shí), 系統(tǒng)假定用戶已分配了足夠長度的內(nèi)存, 假設(shè)不成立時(shí), 就會(huì)造成緩沖區(qū)溢出(覆蓋后邊的字符)
3. C的實(shí)現(xiàn)是一個(gè)N+1字符長的數(shù)組, 每次增長或縮短一個(gè)C字符串, 都會(huì)重新分配內(nèi)存
   • 若增長, eg. append、需要先擴(kuò)容, 否則會(huì)產(chǎn)生內(nèi)存溢出
   • 若縮容, eg. trim、需要先縮容, 否則會(huì)造成內(nèi)存泄露
4. 為避免C字符串的缺陷, SDS通過未使用空間分配, 實(shí)現(xiàn)了空間預(yù)分配和惰性空間釋放來優(yōu)化.
   • 空間預(yù)分配: 當(dāng)字符串?dāng)U展時(shí), 不僅分配必須空間, 還會(huì)分配額外空間(len<1M時(shí), free=len, len>=1M時(shí), free=1M), 來減少連續(xù)執(zhí)行字符串增長需要的內(nèi)存分配次數(shù), 將字符串連續(xù)增長N次需要的內(nèi)存重分配次數(shù)從必定N次, 降低到最多N次
   • 惰性釋放: 用free來標(biāo)記被釋放的空間, 而不真正操作內(nèi)存, 也提供了API, 在需要時(shí)釋放free空間, 不必?fù)?dān)心惰性釋放造成的空間浪費(fèi)
5. C字符串用\0標(biāo)記字符串結(jié)尾, 字符串本身不能包含空字符, 使得C字符串只能保存文本數(shù)據(jù), 而不能保存圖片、音頻、視頻、壓縮文件等二進(jìn)制數(shù)據(jù). 而redis SDS字符靠len屬性來判斷字符串結(jié)尾, 是二進(jìn)制安全的.
6. 兼容部分C字符. SDS總在結(jié)尾多分配一個(gè)字符\0 是為了保證C函數(shù)可以正常使用, 避免不必要的代碼重復(fù)

總結(jié)