redis 5.0.7 源碼閱讀——動態字元串sds

redis中動態字元串sds相關的文件為：sds.h與sds.c 一、數據結構 redis中定義了自己的數據類型"sds"，用於描述 char*，與一些數據結構 1 typedef char *sds; 2 3 /* Note: sdshdr5 is never used, we just acce ...

redis中動態字元串sds相關的文件為：sds.h與sds.c

一、數據結構

redis中定義了自己的數據類型"sds"，用於描述 char*，與一些數據結構

 1 typedef char *sds;
 2 
 3 /* Note: sdshdr5 is never used, we just access the flags byte directly.
 4  * However is here to document the layout of type 5 SDS strings. */
 5 struct __attribute__ ((__packed__)) sdshdr5 {
 6     unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
 7     char buf[];
 8 };
 9 struct __attribute__ ((__packed__)) sdshdr8 {
10     uint8_t len; /* used */
11     uint8_t alloc; /* excluding the header and null terminator */
12     unsigned char flags; /* 3 lsb of type, 5 unused bits */
13     char buf[];
14 };
15 struct __attribute__ ((__packed__)) sdshdr16 {
16     uint16_t len; /* used */
17     uint16_t alloc; /* excluding the header and null terminator */
18     unsigned char flags; /* 3 lsb of type, 5 unused bits */
19     char buf[];
20 };
21 struct __attribute__ ((__packed__)) sdshdr32 {
22     uint32_t len; /* used */
23     uint32_t alloc; /* excluding the header and null terminator */
24     unsigned char flags; /* 3 lsb of type, 5 unused bits */
25     char buf[];
26 };
27 struct __attribute__ ((__packed__)) sdshdr64 {
28     uint64_t len; /* used */
29     uint64_t alloc; /* excluding the header and null terminator */
30     unsigned char flags; /* 3 lsb of type, 5 unused bits */
31     char buf[];
32 };

定義結構體時，加上了 __attribute__ ((__packed__)) 關鍵字，用於取消位元組對齊，使其按照緊湊排列的方式，占用記憶體。這樣做的目的並不僅僅只是為了節約記憶體的使用。結構體最後有一個 char buf[]，查了資料之後瞭解到，其只是定義一個數組符號，並沒有任何成員，不占用結構體的記憶體空間，其真實地址緊隨結構體之後，可實現變長結構體。由此可以只根據sds字元串的真實地址，取到sds結構體的任意成員變數數據。如flags：

1 void func(const sds s)
2 {
3     unsigned char flags = s[-1];      
4 }

這個flags，從源碼的註釋上看，其低三位用於表示sds類型，高五位是當sds類型為sdshdr5時，表明字元串長度的。對於非sdshdr5的類型，有專門的成員變數描述當前已使用的長度，及總buffer長度。

sds類型：

1 #define SDS_TYPE_5  0
2 #define SDS_TYPE_8  1
3 #define SDS_TYPE_16 2
4 #define SDS_TYPE_32 3
5 #define SDS_TYPE_64 4

sds定義了兩個巨集，用於獲取sds結構體首地址：

1 #define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
2 #define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))

由此可見sds結構體的大致結構為：

 1 /*
 2 sdshdr5
 3 +--------+----...---+
 4 |00011000|abc\0     |
 5 +--------+----...---+
 6 |flags   |buf
 7 
 8 sdshdr8
 9 +--------+--------+--------+----...---+
10 |00000011|00000011|00000001|abc\0     |
11 +--------+--------+--------+----...---+
12 |len     |alloc   |flags   |buf
13 */

sds的一些常規操作，如獲取字元串長度、獲取剩餘buf長度等，都是其於以上操作，首先根據sds字元串地址獲取其flags的值，根據flags低三位判斷sds類型，接著使用巨集SDS_HDR_VAR或SDS_HDR進行操作。如：

 1 #define SDS_TYPE_MASK 7   //0000,0111
 2 
 3 static inline size_t sdslen(const sds s) {
 4 //獲取flags
 5     unsigned char flags = s[-1];
 6 //根據flags低三位取類型，根據類型做不同處理
 7     switch(flags&SDS_TYPE_MASK) {
 8         case SDS_TYPE_5:
 9             return SDS_TYPE_5_LEN(flags);
10         case SDS_TYPE_8:
11             return SDS_HDR(8,s)->len;
12         case SDS_TYPE_16:
13             return SDS_HDR(16,s)->len;
14         case SDS_TYPE_32:
15             return SDS_HDR(32,s)->len;
16         case SDS_TYPE_64:
17             return SDS_HDR(64,s)->len;
18     }
19     return 0;
20 }

關於sds結構體中的len與alloc，len表示的是sds字元串的當前長度，alloc表示的是buf的總長度。

二、一些操作。

首先是一個根據字元串長度來決定sds類型的方法

 1 static inline char sdsReqType(size_t string_size) {
 2     if (string_size < 1<<5)    //flags高五位最大數字為 1<<5 - 1
 3         return SDS_TYPE_5;
 4     if (string_size < 1<<8)    //uint8_t 最大數字為 1<<8 - 1
 5         return SDS_TYPE_8;
 6     if (string_size < 1<<16)  //uint16_t 最大數字為 1<<16 - 1
 7         return SDS_TYPE_16;
 8 #if (LONG_MAX == LLONG_MAX)  //區分32位/64位系統
 9     if (string_size < 1ll<<32)
10         return SDS_TYPE_32;
11     return SDS_TYPE_64;
12 #else
13     return SDS_TYPE_32;
14 #endif
15 }

創建一個新的sds結構體：

 1 sds sdsnewlen(const void *init, size_t initlen) {
 2     void *sh;
 3     sds s;
 4     char type = sdsReqType(initlen);
 5     if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
 6     int hdrlen = sdsHdrSize(type);
 7     unsigned char *fp; /* flags pointer. */
 8 
 9     sh = s_malloc(hdrlen+initlen+1);
10     if (init==SDS_NOINIT)
11         init = NULL;
12     else if (!init)
13         memset(sh, 0, hdrlen+initlen+1);
14     if (sh == NULL) return NULL;
15     s = (char*)sh+hdrlen;
16     fp = ((unsigned char*)s)-1;
17     switch(type) {
18         case SDS_TYPE_5: {
19             *fp = type | (initlen << SDS_TYPE_BITS);
20             break;
21         }
22         case SDS_TYPE_8: {
23             SDS_HDR_VAR(8,s);
24             sh->len = initlen;
25             sh->alloc = initlen;
26             *fp = type;
27             break;
28         }
29         case SDS_TYPE_16: {
30             //同SDS_TYPE_8，略
31         }
32         case SDS_TYPE_32: {
33             //同SDS_TYPE_8，略
34         }
35         case SDS_TYPE_64: {
36             //同SDS_TYPE_8，略
37         }
38     }
39     if (initlen && init)
40         memcpy(s, init, initlen);
41     s[initlen] = '\0';
42     return s;
43 }

由外部指定初始字元串與初始長度。先根據長度獲取sds類型，然後根據不同類型，可以獲得實際需要的總記憶體空間大小（包括sds結構體長度）。值得註意的是，如果初始長度為0的情況下，若為SDS_TYPE_5，則會被強制轉為SDS_TYPE_8。根據源碼的註釋，空串的定義，通常是為了向後追加內容。SDS_TYPE_5並不適合這種場景。分配完記憶體空間之後，設置好sds結構體的值，再把初始字元串拷至sds字元串的實際初始位置上（如果有），就可以了。

本方法做為最底層的sds字元串初始化介面，被其它介面所調用，如：

 1 //空string
 2 sds sdsempty(void) {
 3     return sdsnewlen("",0);
 4 }
 5 
 6 //指定string
 7 sds sdsnew(const char *init) {
 8     size_t initlen = (init == NULL) ? 0 : strlen(init);
 9     return sdsnewlen(init, initlen);
10 }
11 
12 //從現有sds string拷貝
13 sds sdsdup(const sds s) {
14     return sdsnewlen(s, sdslen(s));
15 }

sds的釋放也不是簡單地free sds字元串，同樣，它要先找到sds結構體的首地址，再進行free：

1 void sdsfree(sds s) {
2     if (s == NULL) return;
3     s_free((char*)s-sdsHdrSize(s[-1]));
4 }

做為一個變長字元串，與傳統c字元串，最大的區別，是可以動態擴展，就像c++ stl里的變長數組 vector一樣。sds的擴容有自己的機制：

 1 sds sdsMakeRoomFor(sds s, size_t addlen) {
 2     void *sh, *newsh;
 3     size_t avail = sdsavail(s);
 4     size_t len, newlen;
 5     char type, oldtype = s[-1] & SDS_TYPE_MASK;
 6     int hdrlen;
 7 
 8     /* Return ASAP if there is enough space left. */
 9     if (avail >= addlen) return s;
10 
11     len = sdslen(s);
12     sh = (char*)s-sdsHdrSize(oldtype);
13     newlen = (len+addlen);
14     if (newlen < SDS_MAX_PREALLOC)
15         newlen *= 2;
16     else
17         newlen += SDS_MAX_PREALLOC;
18 
19     type = sdsReqType(newlen);
20 
21     /* Don't use type 5: the user is appending to the string and type 5 is
22      * not able to remember empty space, so sdsMakeRoomFor() must be called
23      * at every appending operation. */
24     if (type == SDS_TYPE_5) type = SDS_TYPE_8;
25 
26     hdrlen = sdsHdrSize(type);
27     if (oldtype==type) {
28         newsh = s_realloc(sh, hdrlen+newlen+1);
29         if (newsh == NULL) return NULL;
30         s = (char*)newsh+hdrlen;
31     } else {
32         /* Since the header size changes, need to move the string forward,
33          * and can't use realloc */
34         newsh = s_malloc(hdrlen+newlen+1);
35         if (newsh == NULL) return NULL;
36         memcpy((char*)newsh+hdrlen, s, len+1);
37         s_free(sh);
38         s = (char*)newsh+hdrlen;
39         s[-1] = type;
40         sdssetlen(s, len);
41     }
42     sdssetalloc(s, newlen);
43     return s;
44 }

本方法用於擴容sds，並可以指定長度。首先其先取出了當前還空閑的buf長度，方法如下：

 1 static inline size_t sdsavail(const sds s) {
 2     unsigned char flags = s[-1];
 3     switch(flags&SDS_TYPE_MASK) {
 4         case SDS_TYPE_5: {
 5             return 0;
 6         }
 7         case SDS_TYPE_8: {
 8             SDS_HDR_VAR(8,s);
 9             return sh->alloc - sh->len;
10         }
11         case SDS_TYPE_16: {
12             SDS_HDR_VAR(16,s);
13             return sh->alloc - sh->len;
14         }
15         case SDS_TYPE_32: {
16             SDS_HDR_VAR(32,s);
17             return sh->alloc - sh->len;
18         }
19         case SDS_TYPE_64: {
20             SDS_HDR_VAR(64,s);
21             return sh->alloc - sh->len;
22         }
23     }
24     return 0;
25 }

若當前空閑的長度，比需要的長度大，則認為不用再額外分配空間，直接return。否則就啟用擴容操作。

擴容時，先根據當前已使用的長度len與需要增加的長度addlen，算出一個初始新長度newlen，然後對其進行判斷，若newlen大於1M，則在newlen的基礎上，繼續增加1M，否則直接翻倍。然後再根據newlen的最終大小，獲取sds的新類型。此時，若類型依然為SDS_TYPE_5，也要強行修正為SDS_TYPE_8。因為SDS_TYPE_5類型並不知道當前空閑空間的大小。此時，若sds的新類型與原來相同，則只需要調用realloc重新分配一下空間即可。此方法會分配出一塊新空間的同時，把原來空間的內容拷過去，並釋放原有空間。而sds類型發生改變的時候，就需要手動新造一個新的sds了。擴容完成之後，需要修正一下當前已使用的空間len，與總buf大小 alloc。

擴容完成之後，或者是其它什麼操作，如人工修改了sds字元串，並更新的len的情況下，會存在空閑空間太大的情況。此時如果想釋放這部分空間，sds也提供了相應的操作：

 1 sds sdsRemoveFreeSpace(sds s) {
 2     void *sh, *newsh;
 3     char type, oldtype = s[-1] & SDS_TYPE_MASK;
 4     int hdrlen, oldhdrlen = sdsHdrSize(oldtype);
 5     size_t len = sdslen(s);
 6     size_t avail = sdsavail(s);
 7     sh = (char*)s-oldhdrlen;
 8 
 9     /* Return ASAP if there is no space left. */
10     if (avail == 0) return s;
11 
12     /* Check what would be the minimum SDS header that is just good enough to
13      * fit this string. */
14     type = sdsReqType(len);
15     hdrlen = sdsHdrSize(type);
16 
17     /* If the type is the same, or at least a large enough type is still
18      * required, we just realloc(), letting the allocator to do the copy
19      * only if really needed. Otherwise if the change is huge, we manually
20      * reallocate the string to use the different header type. */
21     if (oldtype==type || type > SDS_TYPE_8) {
22         newsh = s_realloc(sh, oldhdrlen+len+1);
23         if (newsh == NULL) return NULL;
24         s = (char*)newsh+oldhdrlen;
25     } else {
26         newsh = s_malloc(hdrlen+len+1);
27         if (newsh == NULL) return NULL;
28         memcpy((char*)newsh+hdrlen, s, len+1);
29         s_free(sh);
30         s = (char*)newsh+hdrlen;
31         s[-1] = type;
32         sdssetlen(s, len);
33     }
34     sdssetalloc(s, len);
35     return s;
36 }

操作與擴容類似，同樣是會根據sds類型是否發生變化，來決定是使用realloc還是重新造一個sds。

除此之外，sds還實現了一些轉義、數據類型轉換、一些類似c風格的字元串操作等。如：strcpy、strcat、strlen、strcmp等。只是其更加多樣化，如sds的strcat實現，就可以支持類似printf的方式。如：

 1 /* Like sdscatprintf() but gets va_list instead of being variadic. */
 2 sds sdscatvprintf(sds s, const char *fmt, va_list ap) {
 3     va_list cpy;
 4     char staticbuf[1024], *buf = staticbuf, *t;
 5     size_t buflen = strlen(fmt)*2;
 6 
 7     /* We try to start using a static buffer for speed.
 8      * If not possible we revert to heap allocation. */
 9     if (buflen > sizeof(staticbuf)) {
10         buf = s_malloc(buflen);
11         if (buf == NULL) return NULL;
12     } else {
13         buflen = sizeof(staticbuf);
14     }
15 
16     /* Try with buffers two times bigger every time we fail to
17      * fit the string in the current buffer size. */
18     while(1) {
19         buf[buflen-2] = '\0';
20         va_copy(cpy,ap);
21         vsnprintf(buf, buflen, fmt, cpy);
22         va_end(cpy);
23         if (buf[buflen-2] != '\0') {
24             if (buf != staticbuf) s_free(buf);
25             buflen *= 2;
26             buf = s_malloc(buflen);
27             if (buf == NULL) return NULL;
28             continue;
29         }
30         break;
31     }
32 
33     /* Finally concat the obtained string to the SDS string and return it. */
34     t = sdscat(s, buf);
35     if (buf != staticbuf) s_free(buf);
36     return t;
37 }
38 
39 /* Append to the sds string 's' a string obtained using printf-alike format
40  * specifier.
41  *
42  * After the call, the modified sds string is no longer valid and all the
43  * references must be substituted with the new pointer returned by the call.
44  *
45  * Example:
46  *
47  * s = sdsnew("Sum is: ");
48  * s = sdscatprintf(s,"%d+%d = %d",a,b,a+b).
49  *
50  * Often you need to create a string from scratch with the printf-alike
51  * format. When this is the need, just use sdsempty() as the target string:
52  *
53  * s = sdscatprintf(sdsempty(), "... your format ...", args);
54  */
55 sds sdscatprintf(sds s, const char *fmt, ...) {
56     va_list ap;
57     char *t;
58     va_start(ap, fmt);
59     t = sdscatvprintf(s,fmt,ap);
60     va_end(ap);
61     return t;
62 }

其它方法在此不再過多描述

三、sds相比c的標準庫優勢：

1、相比於c標準庫，獲取字元串的len複雜讀從O(N)降低到O(1)，sds結構中存儲了字元串的長度，所以類似strlen(str)的操作不會成為redis的性能瓶頸。
2、在記憶體分配策略上，redis總是會嘗試多分配一些空間，比如小於1MB的字元串，總是分配2倍記憶體空間，對於大於1MB的空間追加1MB冗餘空間，這對於字元串操作（如strcat等）能減少重新記憶體分配的幾率，提升運行性能。
3、SDS總是安全的，sds總是會自動追加字元串結尾符號’\0’，有效防止溢出發生。
4、惰性釋放記憶體，改變原字元串時，標準庫需要重新分配記憶體的複雜度為O(N)，SDS最大為O(N)，最優情況下無需重新分配記憶體空間。

redis 5.0.7 下載鏈接

http://download.redis.io/releases/redis-5.0.7.tar.gz

源碼閱讀順序參考：

https://github.com/huangz1990/blog/blob/master/diary/2014/how-to-read-redis-source-code.rst

其它參考資料：

https://blog.csdn.net/zzuchengming/article/details/51840067

https://blog.csdn.net/junlon2006/article/details/101369299