Redis底層探秘（一）：簡單動态字元串(SDS)
redis是我們使用非常多的一種緩存技術，他的性能極高，讀的速度是110000次/s,寫的速度是81000次/s。這麼高的性能背後，到底是怎麼樣的實作在支撐，這個系列的文章，我們一起去看看。
redis的底層資料結構有以下7種，包括簡單動态字元串(SDS)，連結清單、字典、跳躍表、整數集合、壓縮清單、對象。今天我們一起看下簡單動态字元串（simple dynamic string），後面的文章以SDS簡稱。
SDS簡介
Redis沒有直接使用C語言傳統的字元串表示（以空字元結尾的字元串數組，以下簡稱C字元串）。C字元串并不能滿足redis對字元串安全性、效率以及功能的要求，是以Ridis自定義SDS抽象類型。
Redis中，C字元串隻會作為字元串字面量（string literal）用在一些無須對字元串值進行修改的地方，比如列印日志。
在redis資料庫裡，包含字元串值的鍵值對在底層都是由SDS實作的。除了用來儲存資料庫中的字元串值之外，sds還被用來作緩沖區（buffer）：AOF（一種持久化政策）子產品中的AOF緩沖區，以及用戶端狀态中的輸入緩沖區，都是由SDS實作的。
至于SDS的具體好處，我們會在後文有詳細的論述。
SDS定義
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len; /* used 記錄buff數組中已使用位元組的數量 */
uint64_t free; /* 記錄未使用位元組數量*/
char buf[];
}; 下圖展示了sds示例
SDS遵循C字元串以空字元結尾的慣例，儲存空字元的1位元組空間不計算在SDS的len屬性裡面，并且為空字元配置設定額外的1位元組空間，以及添加空字元到字元串末尾等操作，都是有SDS函數自動完成的，是以這個空字元對于SDS的使用者來說完全透明。遵循空字元結尾這一慣例的好處是，SDS可以直接重用一部分C字元串函數庫裡面的函數。
常數複雜度擷取字元串長度
因為C字元串并不記錄自身的長度資訊，是以為了擷取一個C字元串的長度，程式必須周遊整個字元串，複雜度為O（N）。
和C字元串不同，因為SDS在len屬性中記錄了SDS本身的長度，是以擷取一個SDS長度的複雜度僅為O(1)。
通過使用SDS而不是C字元串，Redis将擷取字元串長度所需的複雜度從O(N)降低到了O(1)，這確定了擷取字元串長度的工作不會成為Redis的性能瓶頸。這樣即使我們隊一個非常長的字元串鍵反複執行StrLen指令，也不會對系統性能造成任何影響。
杜絕緩沖區溢出
除了擷取字元串長度的複雜度高之外，C字元串不記錄自身長度帶來的另一個問題是容易造成緩沖區溢出（buffer overflow）。舉個例子，<string.h>/strcat函數可以将src字元串中的内容拼接到dest字元串末尾。char *strcat( char * dest, const char *src);
因為C字元串不記錄自身的長度，是以strcat嘉定使用者在執行這個函數時，已經為dest配置設定了足夠多的記憶體，但是一旦假定不成立，就會産生緩沖溢出（導緻其他記憶體空間的資料被意外修改）。
與C字元串不同，SDS空間配置設定政策完全杜絕了發送緩沖區溢出的可能性：當SDS API需要對SDS進行修改時，API會先檢查SDS的空間是否滿足修改所需的要求，如果不滿足，API會自動将SDS的空間擴充至執行修改所需的大小，然後才執行實際的修改操作，是以使用SDS既不需要手動修改SDS空間大小，也不會出現前面所說的緩沖區溢出問題。
減少修改字元串時帶來的記憶體重配置設定次數
因為C字元串并不記錄自身長度，是以對于一個包含了N個字元串的C字元串來說，這個C字元串的底層實作總是一個N+1個字元長的數組（額外的一個用來儲存空字元）。因為C字元串的長度和底層數組的長度之間存在着這種關聯性，是以每次增長或縮短C字元串，程式都總要對儲存這個C字元串的數組進行一次記憶體重配置設定操作：因為記憶體重配置設定涉及複雜的算法，并且可能需要執行系統系統調用，是以它通常是一個比較耗時的操作，redis作為資料庫，經常被用于速度要求苛刻、資料頻繁修改的場合，如果每次修改字元串都需要執行一次記憶體重配置設定，那麼效率會相當低。
為避免C字元串這種缺陷，SDS通過未使用空間解除了字元串長度和底層數組長度之間的關聯：在SDS中，buf數組的長度不一定就是字元串數量加一，數組裡面可以包含未使用的位元組，而這些位元組的數量就是由SDS的free屬性記錄。通過未使用空間，SDS實作了空間預配置設定和惰性空間釋放兩種優化政策。
1、空間預配置設定
空間預配置設定用于優化SDS的字元串增長操作：當SDS的API對一個SDS進行修改，并且需要對SDS進行空間擴充的時候，程式不僅會為SDS配置設定配置設定修改所必須要的空間，還會為SDS配置設定額外的未使用空間（具體配置設定多少空間有一個特殊的算法，這裡不做深入讨論。）
在擴充SDS空間之前，SDS Api會先檢查未使用空間是否足夠，如果足夠的話，api會直接使用未使用空間，而無需執行記憶體配置設定。
通過這種預配置設定政策，SDS将連續增長N次字元串所需的記憶體重配置設定次數從必定N次降低為最多N次。
2、惰性空間釋放
惰性空間釋放用于優化SDS的字元串縮短操作：當SDS的ApI需要縮短SDS儲存的字元串時，程式并不立即使用記憶體重配置設定來回收縮短後多出來的位元組，而是使用free屬性見這些位元組的數量記錄起來，并等待将來使用。
通過惰性空間釋放政策，SDS避免了縮短字元串時所需的記憶體重配置設定操作，并為将來可能有的增長操作提供了優化。
與此同時，SDS也提供了相應的API，讓我們可以在有需要時，真正地釋放SDS的未使用空間，是以不用擔心惰性空間釋放政策會造成記憶體浪費。
二進制安全
C字元串中的字元必須符合某種編碼（比如ASCII），并且除了字元串的末尾之外，字元串裡面不能包含空字元，否則最先被程式讀入的空字元江北誤認為是字元串結尾，這些限制使得C字元串隻能儲存文本資料，而不能儲存像圖檔、音頻、視訊、壓縮檔案這樣的二進制資料。
雖然資料庫一般用于儲存文本資料，但使用資料庫來儲存二進制資料的場景也不少見，是以，為了確定Redis可以适用于各種不同的使用場景，SDS的API都是二進制安全。
這也是我們将SDS的buf屬性稱為位元組數組的原因—Redis不是用這個數組來儲存字元，而是用它來儲存一系列二進制資料。
相容部分C字元串函數
雖然SDS的API都是二進制安全的，但它們一樣遵循C字元串以空字元結尾的慣例：這些API總會将SDS儲存的資料末尾設定為空字元，并且總會在為BUF數組配置設定空間時多配置設定一個位元組來容納這個空字元，這是為了讓那些儲存文本資料的SDS可以重用一個部分<string.h>庫定義的函數。
比如我們可以重用<string.h>/strcasecmp函數，使用它來對比SDS儲存的字元串和另一個C字元串。
strcasecmp（sds->buf,”hello world”）;
這樣redis就不用自己專門去寫一個函數來對比SDS和C字元串的值了。
SDS API
參考資料：
redis設計與實作(第二版)
Redis in action