[TOC] ## `SDS`頭文件及作用 * sds.h: sds聲明 * sdsalloc.h： 為sds分配內存 源碼文件`sds.h`中有這樣一行代碼 ```cpp typedef char *sds; ``` 很清晰、明了，`sds`其實就是`char*`。 最新的6.2分支的代碼： ```cpp struct __attribute__ ((__packed__)) sdshdr5 { unsigned char flags; /* 3 lsb of type, and 5 msb of string length */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr8 { uint8_t len; /* used */ uint8_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr16 { uint16_t len; /* used */ uint16_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr32 { uint32_t len; /* used */ uint32_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr64 { uint64_t len; /* used */ uint64_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; ``` >`__attribute__ ((__packed__)) `的設置是告訴編譯器取消字節對齊，則結構體的大小就是按照結構體成員實際大小相加得到的。 Redis是在3.2版本(包括3.2)之后把`sdshdr`改為現在這樣的。 看到這五個結構體有點懵，我想程序都有個初始版本，萬變不離其宗，我切換到2.2版本的分支上,看到了`sdshdr`最初的模樣 ```cpp struct sdshdr { int len; int free; char buf[]; }; ``` ?注意:這里的len是buf字符數組中，不包括最后的空字符的字符個數。`sdshdr` 是一個包含字符串數組和長度的結構體。 ## 相比`C`字符串，`SDS`的優勢 `sdshdr`和C字符串有什么優勢和劣勢呢？請繼續往下看 ### 獲取字符串的時間復雜度 * `SDS`字符串： O(1) * `C`字符串：O(n)，需要遍歷字符串，以`\0`結尾 * 使用SDS可以確保獲取字符串長度的操作不會成為Redis的性能瓶頸。 ### 杜絕緩沖區溢出 * `C`字符串不會記錄自身的長度和空閑空間，容易造成緩沖區溢出，而SDS則不會，在拼接字符串之前，會通過`free`字段檢測是否能滿足數據的存放，如果不滿足則會進行擴容。 ### 減少修改字符串時帶來的內存重分配次數 * `C`字符串在對字符進行拼接或者縮短的情況下，都會對這個`C`字符串的內存進行重新分配。比如拼接字符串時，需要重新分配來擴展原有字符串數組的大小，避免溢出緩沖區；在對字符串進行縮短操作時，需要重新分配內存來釋放不需要的那部分，避免內存泄漏。所以C語言中每次修改字符串都會造成內存重分配。 * `SDS`字符串則有`len`和`free`屬性，可以實現兩種內存分配和釋放操作：**內存預分配和內存惰性釋放** * 在對`SDS`進行擴展的時候，程序不僅會為`SDS`分配所必需的內存，還會為`SDS`分配額外的空閑內存。這樣就減少連續增長字符串所需內存重新分配的次數。通過內存預分配，`SDS`將`N`次字符串增長操作所需內存分配的次數從必須`N次降低為最多`N`次。 * 額外未分配的內存的大小的策略：在擴展sds空間之前，sds api會檢查未使用的空間是否夠用，如果夠用則直接使用未使用的空間，無須執行內存重分配。如果不夠用則重新分配內存：  * 內存釋放策略：在`SDS`進行字符串縮短操作時，程序不會立馬重新分配內存來縮短多出來的字節，而是使用屬性`free`記錄下來等待將來使用。通過惰性內存釋放策略，`SDS`避免因縮短字符串操作而進行內存重新分配的次數，為將來有可能的增長操作帶來了優化。 * 可以通過sds api來釋放未使用的空間，不用擔心惰性空間釋放策略會造成內存浪費 ### 二進制安全 * 為了確保redis可以保存二進制數據（圖片、視頻等），SDS的API是二進制安全的。 程序不會對其中的數據做任何的限制，過濾，數據存進去是什么樣子，讀出來就是什么樣子，這也是buf數組叫做字節數組而不是叫字符數組的原因。Redis不僅可以保存文本數據，還可以保存任意格式是二進制數。 * `C`字符串中除了末尾的空字符，字符串其他位置不能包含空字符，所以C語言字符串只能保存文本數據，不能保存二進制數據。 總結：  ## 6.2分支的`SDS` 我們回到6.2的分支上，可以看到五個結構體可以歸納為一種包含`Header`與`數據包`的結構體。  想要得到`sdshdr`的屬性，需要知道`header`類型，`flags`字段存儲了`header`類型，假如我們定義了`sds* s`，那么獲取`flags`字段僅僅需要將s向前移動一個字節，即`unsigned char flags = s[-1]` , `header`的五類型如下： ```cpp #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 ``` 然后通過以下宏定義來對header進行操作： ```cpp #define SDS_TYPE_MASK 7 // 類型掩碼 #define SDS_TYPE_BITS 3 #define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T))); // 獲取header頭指針 #define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T)))) // 獲取header頭指針 #define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS) // 獲取sdshdr5的長度 ``` ## SDS的創建 & 擴容 & 銷毀 創建一個sds字符串函數： ``` sds sdsnew(const char *init) { size_t initlen = (init == NULL) ? 0 : strlen(init); return sdsnewlen(init, initlen); } ``` 觸發擴容操作： ``` sds sdscatfmt(sds s, char const *fmt, ...) { ... switch(*f) { case '%': next = *(f+1); f++; switch(next) { case 's': case 'S': str = va_arg(ap,char*); l = (next == 's') ? strlen(str) : sdslen(str); if (sdsavail(s) < l) { //當剩余空間小于要加入數據的大小時需要擴容 s = sdsMakeRoomFor(s,l); //擴容 } memcpy(s+i,str,l); sdsinclen(s,l);//設置 已使用字符長度 屬性。 i += l; break; ... } f++; } va_end(ap); /* Add null-term */ s[i] = '\0'; return s; } ``` 惰性刪除操作， 設置 `len`字段為0，但是并沒有釋放內存。這是一個比較極端的例子， ``` void sdsclear(sds s) { sdssetlen(s, 0); s[0] = '\0'; } ``` 惰性刪除操作，這個例子比較正常，如果新數據的長度小于等于當前數據的長度則不進行擴容，不擴容只需要修改`len`這個字段的值即可，不需要釋放內存。反之則需要進行擴容。 ``` sds sdsgrowzero(sds s, size_t len) { size_t curlen = sdslen(s); if (len <= curlen) return s; //新數據的長度小于等于數據的長度則不進行擴容。 s = sdsMakeRoomFor(s,len-curlen); //擴容操作 if (s == NULL) return NULL; /* Make sure added region doesn't contain garbage */ memset(s+curlen,0,(len-curlen+1)); /* also set trailing \0 byte */ sdssetlen(s, len); //設置已使用數據長度，len字段 return s; } ``` 釋放空閑空間 ``` sds sdsRemoveFreeSpace(sds s) {} ``` 銷毀`SDS` ``` void sdsfree(sds s) { if (s == NULL) return; s_free((char*)s-sdsHdrSize(s[-1])); } ```