Redis-簡單動態字符串(SDS)

1.何為SDS

  SDS(simple dynamic string)又名簡單動態字符串，是Redis的基本數據結構，Redis中包含字符串的鍵值對的底層均是SDS實現。眾所周知，Redis使用C語言編寫的，至於Redis為何不用C語言中的字符串表示，且聽我娓娓道來。

2.定義

下面我們來看看SDS的結構：

struct sdshdr{
  // 記錄了SDS保存的字符串的長度，換句話說就是buf數組中使用的字節數
  int len;
  // buf數組中未使用字節數
  int free;
  // 用來保存字符串的字節數組
  char bur[];
};
圖1-SDS結構圖示
  需要注意的是SDS中的buf數組雖然以空字符'\0'結尾，但是空字符的1位元組空間是不會計算在SDS的len屬性中，SDS在分配空間時會額外分多1位元組空間給空字符。由於SDS同C字符串一樣遵循空字符結尾，所以可以直接對SDS使用C語言的函數進行操作。
3.與C字符串的區別
  下面我們將對比SDS與C字符串的區別，解釋Redis選擇SDS而非C字符串的原因。
3.1獲取字符串長度僅需常數複雜度
  由於C字符串中無記錄自身長度信息的屬性，所以每次獲取C字符串的長度都需要程序從頭開始遍歷整個字符串直到遇到空字符，所以C字符串獲取自身長度的複雜度為O(N)。
  反觀SDS，Redis想獲取字符串長度只需訪問SDS的len屬性即可，其複雜度為O(1)。
3.2杜絕緩衝區溢出
  因C字符串不記錄自身長度，從而容易引發緩衝區溢出的問題——當給字符串分配的內存不足時，字符串的數據就會溢出到其他數據所處的空間之中，造成數據被修改。
  SDS的API在執行對SDS的修改時，會先檢查SDS的空間是否滿足修改的要求，不滿足的話API會自動將SDS的空間進行擴充至符合修改要求。
3.3減少修改字符串時帶來的內存重分配次數
  也因為C字符串不記錄自身長度的緣故，每次縮短或擴展一個字符串時，程序會對C字符串的數組進行內存重分配操作，主要分為append（拼接）和trim（截取），append時未擴充底層數組空間則會造成緩衝區溢出，trim時忘記釋放底層數組空間則會造成內存洩露。
  為了不踩C字符串的坑，SDS實現了空間預分配和惰性空間釋放兩種策略：
空間預分配
空間預分配用於解決SDS擴展的問題：對SDS進行擴展時，API不僅分配SDS修改所需空間，而且為SDS分配額外的未使用空間。修改後空間小於1MB時，修改後的len屬性將與free屬性相同；大於等於1MB時，將額外分配多1MB額外空間，下圖是將圖1的Ross字符串修改為Jim Ross的情況：
圖2-Ross字符串修改為Jim Ross
惰性空間釋放
惰性空間釋放用於解決SDS縮短的問題：API在縮短SDS時，不是直接將內存重分配來回收縮短空間，而是將多餘空間用free屬性記錄起來給以後使用，下圖是將圖2中的Jim Ross修改為Jim的情況：
圖3-Jim Ross修改為Jim3.4 二進位安全
  舉一個例子，假如我們有一個由多個空字符隔開的字符串比如一個英文句子，如果我們使用C字符串存儲則只會識別到第一個空字符就停止了。若我們使用SDS，API則會以處理二進位的方式處理SDS中buf數組的數據，程序不對其中的數據做任何限制。SDS是以len屬性為標準判斷一個字符串是否結束而不是空字符。
3.5兼容部分C字符串函數
  前面我們已經提到了我們可以直接對SDS使用C語言的函數進行操作，具體是C語言中的<string.h>中的部分函數比如strcasecmp、strcat等。
後記
  由於本人能力有限，如有不當或錯誤的地方，歡迎大家批評指正。
參考
《Redis設計與實現》