目錄
（3）減少修改字符串時帶來的內(nèi)存重分配次數(shù)
一、引言
Reds沒有直接使用C語言傳統(tǒng)的字符串表示（以空字符結尾的字符數(shù)組，以下簡稱C字符串），而是自己構建了一種名為簡單動態(tài)字符串（ simple dynamic string，SDS）的抽象類型，并將SDS用作 Redis的默認字符串表示。
在 Redis里面，C字符串只會作為字符串字面量（ string literal）用在一些無須對字符串值進行修改的地方，比如打印日志。
下面我們說明SDS和C字符串的不同之處，解釋為什么Redis要使用SDS而不是C字符串。
二、SDS的定義
struct sdshdr{
int len;//記錄buf數(shù)組中已使用字節(jié)的數(shù)量
int free;//記錄buf數(shù)組中為使用字節(jié)的數(shù)量
char buf[];//字節(jié)數(shù)組，用于保存字符串
};
示例
image
- free屬性的值為0，表示這個SDS沒有分配任何未使用空間。
- len屬性的值為5，表示這個SDS保存了一個五字節(jié)長的字符串。
- buf屬性是一個char類型的數(shù)組，數(shù)組的前五個字節(jié)分別保存了'R’、'e'、'd'、'i'、's'五個字符，而最后一個字節(jié)則保存了空字符'\0'。
我們發(fā)現(xiàn)上面這個示例中，字符串的結尾遵循C字符串以空字符結尾的慣例，遵循空字符結尾這一慣例的好處是，SDS可以直接重用一部分C字符豐函數(shù)庫里面的函數(shù)。
三、為什么SDS比C字符串更適合于Redis
（1）常數(shù)復雜度獲取字符串長度
我們獲取一個C字符串長度的方法是遍歷，這一操作的時間復雜度是O(n)，而SDS獲取字符串長度的方法是直接去獲取sdshdr中的len屬性，這一操作的時間復雜度是O(1)。而設置和更新SDS長度的工作是由SDS的API在執(zhí)行時自動完成的，使用SDS無須進行任何手動修改長度的工作。
（2）杜絕緩沖區(qū)溢出
當我們在C語言中使用下面函數(shù)去拼接字符串時：
char* strcat(char* dest,const char* src);
如果我們事先沒有為dest分配足夠大小的空間，那么將src拼接到dest后，很可能會造成dest緩存區(qū)溢出，或者說是越界，從而修改了其他地址空間的內(nèi)存。
與C字符串不同，SDS的空間分配策略完全杜絕了發(fā)生緩沖區(qū)溢出的可能性：當SDS的API需要對SDS進行修改時，AP會先檢查SDS的空間是否滿足修改所需的要求，如果不滿足的話，AP會自動將SDS的空間擴展至執(zhí)行修改所需的大小，然后才執(zhí)行實際的修改操作，所以使用SDS既不需要手動修改SDS的空間大小，也不會出現(xiàn)前面所說的緩沖區(qū)溢出問題。
（3）減少修改字符串時帶來的內(nèi)存重分配次數(shù)
因為C字符串并不記錄自身的長度，所以對于一個包含了N個字符的C字符串來說，每次增長或者縮短一個C字符串，程序都總要對保存這個C字符串的數(shù)組進行次內(nèi)存重分配操作：
- 如果程序執(zhí)行的是增長字符串的操作，比如拼接操作（ append），那么在執(zhí)行這個操作之前，程序需要先通過內(nèi)存重分配來擴展底層數(shù)組的空間大小—如果忘了這步就會產(chǎn)生緩沖區(qū)溢出。
- 如果程序執(zhí)行的是縮短字符串的操作，比如截斷操作（trim），那么在執(zhí)行這個操作之后，程序需要通過內(nèi)存重分配來釋放字符串不再使用的那部分空間——如果忘了這一步就會產(chǎn)生內(nèi)存泄漏。
為了避免C字符串的這種缺陷，SDS通過未使用空間解決這個問題：在SDS中，buf數(shù)組的長度不一定就是字符數(shù)量加一，數(shù)組里面可以包含未使用的字節(jié)，而這些字節(jié)的數(shù)量就由SDS的free屬性記錄。通過未使用空間，SDS實現(xiàn)了空間預分配和惰性空間釋放兩種優(yōu)化策略。
例如：
image
1.空間預分配
當SDS的API對一個SDS進行修改并且需要對SDS進行空間擴展的時候，程序不僅會為SDS分配修改所必須要的空間，還會為SDS分配額外的未使用空間。其中，額外分配的未使用空問數(shù)量由以下公式?jīng)Q定:
- 如果對SDS進行修改之后，SDS的長度（也即是len屬性的值）將小于1MB，那么程序分配和len屬性同樣大小的未使用空間。舉個例子，如果進行修改之后，SDS的len將變成13字節(jié)，那么程序也會分配13字節(jié)的未使用空間，SDS的buf數(shù)組的實際長度將變成13+13+1=27字節(jié)。
- 如果對SDS進行修改之后，SDS的長度將大于等于1MB，那么程序會分配1MB的未使用空間。舉個例子，如果進行修改之后，SDS的len將變成30MB，那么程序會分配1MB的未使用空間，SDS的buf數(shù)組的實際長度將為30MB+MB+1byte 。
通過空間預分配策略， Redis可以減少連續(xù)執(zhí)行字符串增長操作所需的內(nèi)存重分配次數(shù)。在擴展SDS空間之前， SDS API會先檢查未使用空間是否足夠，如果足夠的話，API就會直接使用未使用空間，而無須執(zhí)行內(nèi)存重分配。
2.惰性空間釋放
惰性空間釋放用于優(yōu)化SDS的字符申縮短操作：當SDS的API需要縮短SDS保存的字符串時，程序并不立即使用內(nèi)存重分配來回收縮短后多出來的字節(jié)，而是使用free屬性將這些字節(jié)的數(shù)量記錄起來，并等待將來使用。
例如
image
對于上圖中的SDS我們執(zhí)行
sdstrim(s,"XY");//移除SDS字符串中的所有X和Y會將SDS變?yōu)槿缦聢D所示
image注意這里SDS并沒有釋放多出來的8字節(jié)空間，而是將這8字節(jié)空間作為未使用空間保留在了SDS里面，如果將來要對SDS進行增長操作的話，這些未使用空間就可能會派上用場。
通過情性空間釋放策略，SDS避免了縮短字符串時所需的內(nèi)存重分配操作，并為將來可能有的增長操作提供了優(yōu)化。
（4）二進制安全
C字符串中的字符必須符合某種編碼（比如ASCII），并且除了字符串的末尾之外，字符串里面不能包含空字符，否則最先被程序讀入的空字符將被誤認為是字符串結尾，這些限制使得C字符串只能保存文本數(shù)據(jù)，而不能保存像圖片、音頻、視頻、壓縮文件這樣的二進制數(shù)據(jù)。
而為了確保 Redis可以適用于各種不同的使用場景，SDS的API都是二進制安全的，所有 SDS API都會以處理二進制的方式來處理SDS存放在buf數(shù)組里的數(shù)據(jù)，程序不會對其中的數(shù)據(jù)做任何限制、過濾、或者假設，數(shù)據(jù)在寫人時是什么樣的，它被讀取時就是什么樣。
這也是我們將SDS的buf屬性稱為字節(jié)數(shù)組的原因—— Redis不是用這個數(shù)組來保存字符，而是用它來保存一系列二進制數(shù)據(jù)例如，使用SDS來保存之前提到的特殊數(shù)據(jù)格式就沒有任何問題，因為SDS使用len屬性的值而不是空字符來判斷字符串是否結束。
通過使用二進制安全的SDS，而不是C字符串，使得Reds不僅可以保存文本數(shù)據(jù)，還可以保存任意格式的二進制數(shù)據(jù)。
（5）兼容部分C字符串函數(shù)
雖然SDS的API都是二進制安全的，但它們一樣遵循C字符串以空字符結尾的慣例。這些API總會將SDS保存的數(shù)據(jù)的末尾設置為空字符，并且總會在為buf數(shù)組分配空間時多分配一個字節(jié)來容納這個空字符，這是為了讓那些保存文本數(shù)據(jù)的SDS可以重用一部分<string.h>庫定義的函數(shù)。
例如
image對于上述SDS，我們可以重用<string.h>/strcasecmp函數(shù)來和另外一個C字符串左比較。 這樣 Redis就不用自己專門去寫一個函數(shù)來對比SDS值和C字符串值了。
通過遵循C字符串以空字符結尾的慣例，SDS可以在有需要時重用< string.h>函數(shù)庫，從而避免了不必要的代碼重復。
四、SDS的用處
- 保存數(shù)據(jù)庫中的字符串值
- 用作緩沖區(qū)
- AOF緩沖區(qū)
- 客戶端狀態(tài)的輸入緩沖區(qū)
