第2章
簡單動态字元串
簡單動态字元串（Simple Dynamic Strings，SDS）是Redis的基本資料結構之一，用于存儲字元串和整型資料。SDS相容C語言标準字元串處理函數，且在此基礎上保證了二進制安全。本章将詳細講解SDS的實作，為讀者了解Redis的原理和各種指令的實作打下基礎。
2.1 資料結構
在學習SDS源碼前，我們先思考一個問題：如何實作一個擴容友善且二進制安全的字元串呢？
什麼是二進制安全？通俗地講，C語言中，用“0”表示字元串的結束，如果字元串中本身就有“0”字元，字元串就會被截斷，即非二進制安全；若通過某種機制，保證讀寫字元串時不損害其内容，則是二進制安全。
SDS既然是字元串，那麼首先需要一個字元串指針；為了友善上層的接口調用，該結構還需要記錄一些統計資訊，如目前資料長度和剩餘容量等，例如：
struct sds {
int len;// buf 中已占用位元組數
int free;// buf 中剩餘可用位元組數
char buf[];// 資料空間
}; SDS結構示意如圖2-1所示，在64位系統下，字段len和字段free各占4個位元組，緊接着存放字元串。
Redis 3.2之前的SDS也是這樣設計的。這樣設計有以下幾個優點。
1）有單獨的統計變量len和free（稱為頭部）。可以很友善地得到字元串長度。
2）内容存放在柔性數組buf中，SDS對上層暴露的指針不是指向結構體SDS的指針，而是直接指向柔性數組buf的指針。上層可像讀取C字元串一樣讀取SDS的内容，相容C語言處理字元串的各種函數。
3）由于有長度統計變量len的存在，讀寫字元串時不依賴“0”終止符，保證了二進制安全。
上例中的buf[]是一個柔性數組。柔性數組成員（flexible array member），也叫伸縮性數組成員，隻能被放在結構體的末尾。包含柔性數組成員的結構體，通過malloc函數為柔性數組動态配置設定記憶體。
之是以用柔性數組存放字元串，是因為柔性數組的位址和結構體是連續的，這樣查找記憶體更快（因為不需要額外通過指針找到字元串的位置）；可以很友善地通過柔性數組的首位址偏移得到結構體首位址，進而能很友善地擷取其餘變量。
到這裡我們實作了一個最基本的動态字元串，但是該結構是否有改進的空間呢？我們從一個簡單的問題開始思考：不同長度的字元串是否有必要占用相同大小的頭部？一個int占4位元組，在實際應用中，存放于Redis中的字元串往往沒有這麼長，每個字元串都用4位元組存儲未免太浪費空間了。我們考慮三種情況：短字元串，len和free的長度為1位元組就夠了；長字元串，用2位元組或4位元組；更長的字元串，用8位元組。
這樣确實更省記憶體，但依然存在以下問題。
問題1：如何區分這3種情況？
問題2：對于短字元串來說，頭部還是太長了。以長度為1位元組的字元串為例，len和free本身就占了2個位元組，能不能進一步壓縮呢？
對于問題1，我們考慮增加一個字段flags來辨別類型，用最小的1位元組來存儲，且把flags加在柔性數組buf之前，這樣雖然多了1位元組，但通過偏移柔性數組的指針即能快速定位flags，區分類型，也可以接受；對于問題2，由于len已經是最小的1位元組了，再壓縮隻能考慮用位來存儲長度了。
結合兩個問題，5種類型（長度1位元組、2位元組、4位元組、8位元組、小于1位元組）的SDS至少要用3位來存儲類型（23＝8），1個位元組8位，剩餘的5位存儲長度，可以滿足長度小于32的短字元串。在Redis 5.0中，我們用如下結構來存儲長度小于32的短字元串：
struct __attribute__ ((__packed__))sdshdr5 {
unsigned char flags; /* 低3位存儲類型, 高5位存儲長度 */
char buf[];/*柔性數組，存放實際内容*/
}; sdshdr5結構（圖2-2）中，flags占1個位元組，其低3位（bit）表示type，高5位（bit）表示長度，能表示的長度區間為0～31（25-1），flags後面就是字元串的内容。
而長度大于31的字元串，1個位元組依然存不下。我們按之前的思路，将len和free單獨存放。sdshdr8、sdshdr16、sdshdr32和sdshdr64的結構相同，sdshdr16結構如圖2-3所示。
其中“表頭”共占用了S[2(len)+2(alloc)+1(flags)]個位元組。flags的内容與sdshdr5類似，依然采用3位存儲類型，但剩餘5位不存儲長度。
在Redis的源代碼中，對類型的宏定義如下：
#define SDS_TYPE_5 0
#define SDS_TYPE_8 1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4 在Redis 5.0中，sdshdr8、sdshdr16、sdshdr32和sdshdr64的資料結構如下：
struct __attribute__((__packed__))sdshdr8 {
uint8_t len; /* 已使用長度，用1位元組存儲 */
uint8_t alloc; /* 總長度，用1位元組存儲*/
unsigned char flags; /* 低3位存儲類型, 高5位預留 */
char buf[];/*柔性數組，存放實際内容*/
};
struct __attribute__((__packed__))sdshdr16 {
uint16_t len; /*已使用長度，用2位元組存儲*/
uint16_t alloc; /* 總長度，用2位元組存儲*/
unsigned char flags; /* 低3位存儲類型, 高5位預留 */
char buf[];/*柔性數組，存放實際内容*/
};
struct __attribute__((__packed__))sdshdr32 {
uint32_t len; /*已使用長度，用4位元組存儲*/
uint32_t alloc; /* 總長度，用4位元組存儲*/
unsigned char flags;/* 低3位存儲類型, 高5位預留 */
char buf[];/*柔性數組，存放實際内容*/
};
struct __attribute__((__packed__))sdshdr64 {
uint64_t len; /*已使用長度，用8位元組存儲*/
uint64_t alloc; /* 總長度，用8位元組存儲*/
unsigned char flags; /* 低3位存儲類型, 高5位預留 */
char buf[];/*柔性數組，存放實際内容*/
}; 可以看到，這4種結構的成員變量類似，唯一的差別是len和alloc的類型不同。結構體中4個字段的具體含義分别如下。
1）len：表示buf中已占用位元組數。
2）alloc：表示buf中已配置設定位元組數，不同于free，記錄的是為buf配置設定的總長度。
3）flags：辨別目前結構體的類型，低3位用作辨別位，高5位預留。
4）buf：柔性數組，真正存儲字元串的資料空間。
結構最後的buf依然是柔性數組，通過對數組指針作“減一”操作，能友善地定位到flags。在2.2節中，我們能更直覺地了解該用法。
源碼中的__attribute__((__packed__))需要重點關注。一般情況下，結構體會按其所有變量大小的最小公倍數做位元組對齊，而用packed修飾後，結構體則變為按1位元組對齊。以sdshdr32為例，修飾前按4位元組對齊大小為12(4×3)位元組；修飾後按1位元組對齊，注意buf是個char類型的柔性數組，位址連續，始終在flags之後。packed修飾前後示意如圖2-4所示。
這樣做有以下兩個好處。
- 節省記憶體，例如sdshdr32可節省3個位元組（12-9）。
- SDS傳回給上層的，不是結構體首位址，而是指向内容的buf指針。因為此時按1位元組對齊，故SDS建立成功後，無論是sdshdr8、sdshdr16還是sdshdr32，都能通過(char*)sh+hdrlen得到buf指針位址（其中hdrlen是結構體長度，通過sizeof計算得到）。修飾後，無論是sdshdr8、sdshdr16還是sdshdr32，都能通過buf[-1]找到flags，因為此時按1位元組對齊。若沒有packed的修飾，還需要對不同結構進行處理，實作更複雜。
2.2 基本操作
資料結構的基本操作不外乎增、删、改、查，SDS也不例外。由于Redis 3.2後的SDS涉及多種類型，修改字元串内容帶來的長度變化可能會影響SDS的類型而引發擴容。本節着重介紹建立、釋放、拼接字元串的相關API，幫助大家更好地了解SDS結構。在2.2.4節列出了SDS相關API的函數名和功能介紹，有興趣的讀者可自行查閱源代碼。
2.2.1 建立字元串
Redis通過sdsnewlen函數建立SDS。在函數中會根據字元串長度選擇合适的類型，初始化完相應的統計值後，傳回指向字元串内容的指針，根據字元串長度選擇不同的類型：
sds sdsnewlen(const void *init, size_t initlen) {
void *sh;
sds s;
char type = sdsReqType(initlen);//根據字元串長度選擇不同的類型
if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;//SDS_TYPE_5強制轉化為SDS_TYPE_8
int hdrlen = sdsHdrSize(type);//計算不同頭部所需的長度
unsigned char *fp; /* 指向flags的指針 */
sh = s_malloc(hdrlen+initlen+1);//"+1"是為了結束符'\0'
...
s = (char*)sh+hdrlen;//s是指向buf的指針
fp = ((unsigned char*)s)-1;//s是柔性數組buf的指針,-1即指向flags
...
s[initlen] = '\0';//添加末尾的結束符
return s;
} Redis 3.2後的SDS結構由1種增至5種，且對于sdshdr5類型，在建立空字元串時會強制轉換為sdshdr8。原因可能是建立空字元串後，其内容可能會頻繁更新而引發擴容，故建立時直接建立為sdshdr8。
建立SDS的大緻流程：首先計算好不同類型的頭部和初始長度，然後動态配置設定記憶體。需要注意以下3點。
1）建立空字元串時，SDS_TYPE_5被強制轉換為SDS_TYPE_8。
2）長度計算時有“+1”操作，是為了算上結束符“0”。
3）傳回值是指向sds結構buf字段的指針。
傳回值sds的類型定義如下：
typedef char *sds; 從源碼中我們可以看到，其實s就是一個字元數組的指針，即結構中的buf。這樣設計的好處在于直接對上層提供了字元串内容指針，相容了部分C函數，且通過偏移能迅速定位到SDS結構體的各處成員變量。
2.2.2 釋放字元串
SDS提供了直接釋放記憶體的方法—sdsfree，該方法通過對s的偏移，可定位到SDS結構體的首部，然後調用s_free釋放記憶體：
void sdsfree(sds s) {
if (s == NULL) return;
s_free((char*)s-sdsHdrSize(s[-1]));//此處直接釋放記憶體
} 為了優化性能（減少申請記憶體的開銷），SDS提供了不直接釋放記憶體，而是通過重置統計值達到清空目的的方法—sdsclear。該方法僅将SDS的len歸零，此處已存在的buf并沒有真正被清除，新的資料可以覆寫寫，而不用重新申請記憶體。
void sdsclear(sds s) {
sdssetlen(s, 0); //統計值len歸零
s[0] = '\0';//清空buf
} 2.2.3 拼接字元串
拼接字元串操作本身不複雜，可用sdscatsds來實作，代碼如下：
sds sdscatsds(sds s, const sds t) {
return sdscatlen(s, t, sdslen(t));
} sdscatsds是暴露給上層的方法，其最終調用的是sdscatlen。由于其中可能涉及SDS的擴容，sdscatlen中調用sdsMakeRoomFor對帶拼接的字元串s容量做檢查，若無須擴容則直接傳回s；若需要擴容，則傳回擴容好的新字元串s。函數中的len、curlen等長度值是不含結束符的，而拼接時用memcpy将兩個字元串拼接在一起，指定了相關長度，故該過程保證了二進制安全。最後需要加上結束符。
/* 将指針t的内容和指針s的内容拼接在一起，該操作是二進制安全的*/
sds sdscatlen(sds s, const void *t, size_t len) {
size_t curlen = sdslen(s);
s = sdsMakeRoomFor(s,len);
if (s == NULL) return NULL;
memcpy(s+curlen, t, len);//直接拼接，保證了二進制安全
sdssetlen(s, curlen+len);
s[curlen+len] = '\0';//加上結束符
return s;
} 圖2-5描述了sdsMakeRoomFor的實作過程。
Redis的sds中有如下擴容政策。
1）若sds中剩餘空閑長度avail大于新增内容的長度addlen，直接在柔性數組buf末尾追加即可，無須擴容。代碼如下：
sds sdsMakeRoomFor(sds s, size_t addlen)
{
void *sh, *newsh;
size_t avail = sdsavail(s);
size_t len, newlen;
char type, oldtype = s[-1] & SDS_TYPE_MASK;//s[-1]即flags
int hdrlen;
if (avail >= addlen) return s;//無須擴容，直接傳回
...
} 2）若sds中剩餘空閑長度avail小于或等于新增内容的長度addlen，則分情況讨論：新增後總長度len+addlen<1MB的，按新長度的2倍擴容；新增後總長度len+addlen>1MB的，按新長度加上1MB擴容。代碼如下：
sds sdsMakeRoomFor(sds s, size_t addlen)
{
...
newlen = (len+addlen);
if (newlen < SDS_MAX_PREALLOC)// SDS_MAX_PREALLOC這個宏的值是1MB
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;
...
} 3）最後根據新長度重新選取存儲類型，并配置設定空間。此處若無須更改類型，通過realloc擴大柔性數組即可；否則需要重新開辟記憶體，并将原字元串的buf内容移動到新位置。具體代碼如下：
sds sdsMakeRoomFor(sds s, size_t addlen)
{
...
type = sdsReqType(newlen);
/* type5的結構不支援擴容，是以這裡需要強制轉成type8*/
if (type == SDS_TYPE_5) type = SDS_TYPE_8;
hdrlen = sdsHdrSize(type);
if (oldtype==type) {
/*無須更改類型，通過realloc擴大柔性數組即可，注意這裡指向buf的指針s被更新了*/
newsh = s_realloc(sh, hdrlen+newlen+1);
if (newsh == NULL) return NULL;
s = (char*)newsh+hdrlen;
} else {
/*擴容後資料類型和頭部長度發生了變化，此時不再進行realloc操作，而是直接重新開辟記憶體，拼接完内容後，釋放舊指針*/
newsh = s_malloc(hdrlen+newlen+1);//按新長度重新開辟記憶體
if (newsh == NULL) return NULL;
memcpy((char*)newsh+hdrlen, s, len+1);//将原buf内容移動到新位置
s_free(sh);//釋放舊指針
s = (char*)newsh+hdrlen;//偏移sds結構的起始位址，得到字元串起始位址
s[-1] = type;//為falgs指派
sdssetlen(s, len);//為len屬性指派
}
sdssetalloc(s, newlen);//為alloc屬性指派
return s;
} 2.2.4 其餘API
SDS還為上層提供了許多其他API，篇幅所限，不再贅述。表2-1列出了其他常用的API，讀者可自行查閱源碼學習，學習時把握以下兩點。
1）SDS暴露給上層的是指向柔性數組buf的指針。
2）讀操作的複雜度多為O(1)，直接讀取成員變量；涉及修改的寫操作，則可能會觸發擴容。
2.3 本章小結
本章介紹了SDS的資料結構及基本API的實作。在源碼分析過程中，我們可以知道SDS的以下特性是如何實作的。
1）SDS如何相容C語言字元串？如何保證二進制安全？
SDS對象中的buf是一個柔性數組，上層調用時，SDS直接傳回了buf。由于buf是直接指向内容的指針，故相容C語言函數。而當真正讀取内容時，SDS會通過len來限制讀取長度，而非“0”，保證了二進制安全。
2）sdshdr5的特殊之處是什麼？
sdshdr5隻負責存儲小于32位元組的字元串。一般情況下，小字元串的存儲更普遍，故Redis進一步壓縮了sdshdr5的資料結構，将sdshdr5的類型和長度放入了同一個屬性中，用flags的低3位存儲類型，高5位存儲長度。建立空字元串時，sdshdr5會被sdshdr8替代。
3）SDS是如何擴容的？
SDS在涉及字元串修改處會調用sdsMakeroomFor函數進行檢查，根據不同情況動态擴容，該操作對上層透明。