原文地址：https://mp.weixin.qq.com/s/Cvqe56v3TAPC-OBGiZoAaw

redis沒有直接使用C語言傳統的字符串表示，而是自己構建了一種名為簡單動態字符串（simple dynamic string， SDS）的抽象類型，并將SDS用作Redis的默認字符串表示。

SDS的定義

每個sds.h/sdshdr結構表示一個SDS值：

Struct sdshdr{  //記錄buf數組中已使用字節的數  //等于SDS所保存字符串的長度  int len;  //記錄buf數組中未使用字節的數量  int free;  //字節數組，用于保存字符串  char buf[];}

free屬性的值為0，表示這個SDS沒有分配任何未使用空間。

len屬性的值為5，表示這個SDS保存了一個五字節長的字符串。

buf屬性是一個char類型的數組，數組的前五個字節分別保存了‘R’、‘e’、‘d’、‘i’、‘s’五個字符，而最后一個字節則保存了空字符‘’。

SDS遵循C字符串以空字符結尾的慣例，保存空字符的1字節空間不計算在SDS的len屬性里面，并且為空字符分配額外的1字節空間，以及添加字符到字符串末尾等操作，都是由SDS函數自動完成的，所以這個空字符對于SDS的使用者來說是完全透明的。

遵循空字符結尾這一慣例的好處是，SDS可以直接重用一部分C字符串函數庫里面的函數。

SDS與C語言字符串的區別

常數復雜度獲取字符串長度

因為C語言字符串并不記錄自身的長度信息，所有獲取一個C字符串的長度，程序需要遍歷整個字符串，對遇到的每個字符串進行計數，直到遇到代表字符串結尾的空字符為止，這個操作的復雜度為O(N)。

而SDS在len屬性中記錄了SDS本身的長度，所以獲取一個SDS長度的復雜度僅為O(1)。

通過使用SDS而不是C語言字符串，Redis將獲取字符串長度所需的復雜度從O(N)降低到了O(1)，這確保了獲取字符串長度的工作不會成為Redis的性能瓶頸。

杜絕緩沖區溢出

除了獲取字符串長度的復雜度高之外，C語言字符串不記錄自身長度帶來的另一個問題是容易造成緩沖區溢出（buffer overflow）。

與C語言字符串不同，SDS的空間分配策略完全杜絕了發生緩沖區溢出的可能性：當SDS API需要對SDS進行修改時，API會先檢查SDS的空間是否滿足修改所需的要求，如果不滿足的話，API會自動將SDS的空間擴展至執行修改所需的大小，然后才執行實際的修改操作，所以使用SDS既不需要手動修改SDS的空間大小，也不會出現前面所說的緩沖溢出問題。

減少修改字符串時帶來的內存重分配次數

C語言字符串的長度和底層數組的長度之間存在著關聯性，所以每次增長或者縮短一個C語言字符串時，程序要總要對保存這個C語言字符串的數組進行一次內存重分配操作。

• 如果程序執行的是增長字符串的操作，那么在執行這個操作之前，程序需要先通過內存重分配來擴展底層數組空間的大小，如果忘記這一步操作就會產生緩沖區溢出。
• 如果程序執行的是縮短字符串的操作，那么在執行這個操作之后，程序需要通過內存重新分配來釋放字符串不再使用的那部分空間，如果忘記這一步就會產生內存泄漏。

為了避免C語言字符串這種缺陷，SDS通過未使用空間解除了字符串長度和底層數組長度之間的關聯：在SDS中，buf數組的長度不一定就是字符串數量加1，數組里面可以包含未使用的字節，而這些字節的數量就由SDS的free屬性記錄。

通過未使用空間，SDS實現了空間預分配和惰性空間釋放兩種優化策略。

空間預分配

空間預分配用于優化SDS的字符串增長操作：當SDS的API對一個SDS進行修改，并且需要對SDS進行空間擴展的時候，程序不僅會為SDS分配修改所必需的空間，還會為SDS分配額外的未使用空間。

其中額外分配的未使用空間數據由以下公式決定：

• 如果對SDS進行修改之后，SDS的長度（也就是len屬性的值）將小于1M，那么程序分配和len屬性同樣大小的未使用空間，這時SDS len值將和free屬性值相同。
• 如果對SDS進行修改之后，SDS的長度將大于等于1M，那么程序會分配1M的未使用空間。

通過空間預分配策略，Redis可以減少連續執行字符串增加操作所需的內存重分配次數。

在擴展SDS空間之前，SDS API會先檢查未使用空間是否足夠，如果足夠的話，API就會直接使用未使用空間，而無須執行內存重分配。

通過這種預分配策略，SDS將連續增長N次字符串所需的內存重分配次數從必定N次降低為最多N次。

惰性空間釋放

惰性空間釋放用于優化SDS的字符串縮短操作：當SDS的API需要縮短SDS保存的字符串時，程序并不立即使用內存重分配來回收縮短后多出來的字節，而是使用free屬性將這些字符的數量記錄起來，并等待將來使用。

通過惰性空間釋放策略，SDS避免來縮短字符串時所需的內存重分配操作，并為將來可能有的增長操作提供了變化。

二進制安全

C語言字符串中的字符必須符合某種編碼（比如ASCII），并且除了字符串的末尾之外，字符串里面不能包含空字符，否則最先被程序讀入空字符將被誤認為是字符串結尾，這些限制使得C字符串只能保存文本數據，而不能保存像圖片、音頻、視頻、壓縮文件這樣的二進制數據。

為了確保Redis可以適用于各種不同的使用場景，SDS的API都是二進制安全的，所有SDS API都會以處理二進制的方式來處理SDS存放在buf數組里的數據，程序不會對其中數組做任何限制、過濾、或者假設，數據在寫入時是什么樣的，它被讀取時就是什么樣。

兼容部分C字符串函數

通過遵從C語言字符串以空字符結尾的慣例，SDS可以在有需要時重用<string.h>函數庫，從而避免來不必要的代碼重復。

總結

比起C語言字符串，SDS具有以下優點：

• 常數復雜度獲取字符串長度
• 杜絕緩沖區溢出
• 減少修改字符串時帶來的內存沖分配次數
• 二進制安全
• 兼容部分C字符串函數