Redis源碼解析sds字符串實現(xiàn)示例
初衷
從開始工作就開始使用Redis,也有一段時間了,但都只是停留在使用階段,沒有往更深的角度探索,每次想讀源碼都止步在閱讀書籍上,因為看完書很快又忘了,這次逼自己先讀代碼。因為個人覺得寫作需要閱讀文字來增強靈感,那么寫代碼的,就閱讀更多代碼來增強靈感吧。
redis的實現(xiàn)原理,在《Redis設(shè)計與實現(xiàn)》一書中講得很詳細了,但是想通過結(jié)合代碼的形式再深入探索,加深自己的理解,現(xiàn)在將自己探索的心得寫在這兒。
sds結(jié)構(gòu)體的定義
#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 #define SDS_TYPE_MASK 7 // sds結(jié)構(gòu)體,使用不同的結(jié)構(gòu)體來保存不同長度大小的字符串 typedef char *sds; struct __attribute__ ((__packed__)) sdshdr5 { unsigned char flags; /* flags共8位,低三位保存類型標(biāo)志,高5位保存字符串長度,小于32(2^5-1) */ char buf[]; // 保存具體的字符串 }; struct __attribute__ ((__packed__)) sdshdr8 { uint8_t len; /* 字符串長度,buf已用的長度 */ uint8_t alloc; /* 為buf分配的總長度,alloc-len就是sds結(jié)構(gòu)體剩余的空間 */ unsigned char flags; /* 低三位保存類型標(biāo)志 */ 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[]; };
sds結(jié)構(gòu)體從4.0開始就使用了5種header定義,節(jié)省內(nèi)存的使用,但是不會用到sdshdr5,我認(rèn)為是因為sdshdr5能保存的大小較少,2^5=32,因此就不使用它。
其他的結(jié)構(gòu)體保存了len、alloc、flags以及buf四個屬性。各自的含義見代碼的注釋。
sds結(jié)構(gòu)體的獲取
上面可以看到有5種結(jié)構(gòu)體的定義,在使用的時候是通過一個宏來獲取的:
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
"##"被稱為連接符,它是一種預(yù)處理運算符, 用來把兩個語言符號(Token)組合成單個語言符號。比如SDS_HDR(8, s)
,根據(jù)宏定義展開是:
((struct sdshdr8 *)((s)-(sizeof(struct sdshdr8))))
而具體使用哪一個結(jié)構(gòu)體,sds底層是通過flags屬性與SDS_TYPE_MASK
做與運算得出具體的類型(具體的實現(xiàn)可見下面的sdslen函數(shù)),然后再根據(jù)類型去獲取具體的結(jié)構(gòu)體。
sds特性的實現(xiàn)
在Redis設(shè)計與實現(xiàn)一書中講到,相比C字符串而言,sds的特性如下:
- 常數(shù)復(fù)雜度獲取字符串長度
- 杜絕緩沖區(qū)溢出
- 減少內(nèi)存重新分配次數(shù)
- 二進制安全
那么,它是怎么做到的呢?看代碼。
常數(shù)復(fù)雜度獲取字符串長度
因為sds將長度屬性保存在結(jié)構(gòu)體中,所以只需要讀取這個屬性就能獲取到sds的長度,具體調(diào)用的函數(shù)時sdslen,實現(xiàn)如下:
static inline size_t sdslen(const sds s) { unsigned char flags = s[-1]; switch(flags&SDS_TYPE_MASK) { case SDS_TYPE_5: return SDS_TYPE_5_LEN(flags); case SDS_TYPE_8: return SDS_HDR(8,s)->len; case SDS_TYPE_16: return SDS_HDR(16,s)->len; case SDS_TYPE_32: return SDS_HDR(32,s)->len; case SDS_TYPE_64: return SDS_HDR(64,s)->len; } return 0; }
可以看到,函數(shù)是根據(jù)類型調(diào)用SDS_HDR宏來獲取具體的sds結(jié)構(gòu),然后直接返回結(jié)構(gòu)體的len屬性。
杜絕緩沖區(qū)溢出
對于C字符串的操作函數(shù)來說,如果在修改字符串的時候忘了為字符串分配足夠的空間,就有可能出現(xiàn)緩沖區(qū)溢出的情況。而sds中的API就不會出現(xiàn)這種情況,因為它在修改sds之前,都會判斷它是否有足夠的空間完成接下來的操作。
拿書中舉例的sdscat
函數(shù)來看,如果strcat
想在原來的"Redis"字符串的基礎(chǔ)上進行字符串拼接的操作,但是沒有檢查空間是否滿足,就有可能會修改了"Redis"字符串之后使用到的內(nèi)存,可能是其他結(jié)構(gòu)使用了,也有可能是一段沒有被使用的空間,因此有可能會出現(xiàn)緩沖區(qū)溢出。但是sdscat
就不會,如下面代碼所示:
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; } sds sdscat(sds s, const char *t) { return sdscatlen(s, t, strlen(t)); }
從代碼中可以看到,在執(zhí)行memcpy
將字符串寫入sds之前會調(diào)用sdsMakeRoomFor
函數(shù)去檢查sds字符串s是否有足夠的空間,如果沒有足夠空間,就為其分配足夠的空間,從而杜絕了緩沖區(qū)溢出。sdsMakeRoomFor
函數(shù)的實現(xiàn)如下:
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; int hdrlen; /* 只有有足夠空間就馬上返回,否則就繼續(xù)執(zhí)行分配空間的操作 */ if (avail >= addlen) return s; len = sdslen(s); sh = (char*)s-sdsHdrSize(oldtype); newlen = (len+addlen); // SDS_MAX_PREALLOC == 1MB,如果修改后的長度小于1M,則分配的空間是原來的2倍,否則增加1MB的空間 if (newlen < SDS_MAX_PREALLOC) newlen *= 2; else newlen += SDS_MAX_PREALLOC; type = sdsReqType(newlen); if (type == SDS_TYPE_5) type = SDS_TYPE_8; hdrlen = sdsHdrSize(type); if (oldtype==type) { newsh = s_realloc(sh, hdrlen+newlen+1); if (newsh == NULL) return NULL; s = (char*)newsh+hdrlen; } else { /* 新增空間后超過當(dāng)前類型的長度,使用malloc,并把原字符串拷貝過去 */ newsh = s_malloc(hdrlen+newlen+1); if (newsh == NULL) return NULL; memcpy((char*)newsh+hdrlen, s, len+1); s_free(sh); s = (char*)newsh+hdrlen; s[-1] = type; // 給類型標(biāo)志位賦值 sdssetlen(s, len); } sdssetalloc(s, newlen); return s; }
減少內(nèi)存分配操作
sds字符串的很多操作都涉及到修改字符串內(nèi)容,比如sdscat
拼接字符串、sdscpy
拷貝字符串等等。這時候就需要內(nèi)存的分配與釋放,如果每次操作都分配剛剛好的大小,那么對程序的性能必定有影響,因為內(nèi)存分配涉及到系統(tǒng)調(diào)用以及一些復(fù)雜的算法。
sds使用了空間預(yù)分配以及惰性空間釋放的策略來減少內(nèi)存分配操作。
空間預(yù)分配
前面提到,每次涉及到字符串的修改時,都會調(diào)用sdsMakeRoomFor
檢查sds字符串,如果大小不夠再進行大小的重新分配。sdsMakeRoomFor
函數(shù)有下面這幾行判斷:
// SDS_MAX_PREALLOC == 1MB,如果修改后的長度小于1M,則分配的空間是原來的2倍,否則增加1MB的空間 if (newlen < SDS_MAX_PREALLOC) newlen *= 2; else newlen += SDS_MAX_PREALLOC;
函數(shù)判斷字符串修改后的大小,如果修改后的長度小于1M,則分配給sds的空間是原來的2倍,否則增加1MB的空間。
惰性空間釋放
如果操作后減少了字符串的大小,比如下面的sdstrim
函數(shù),只是在最后修改len屬性,不會馬上釋放多余的空間,而是繼續(xù)保留多余的空間,這樣在下次需要增加sds字符串的大小時,就不需要再為其分配空間了。當(dāng)然,如果之后檢查到sds的大小實在太大,也會調(diào)用sdsRemoveFreeSpac
e函數(shù)釋放多余的空間。
sds sdstrim(sds s, const char *cset) { char *start, *end, *sp, *ep; size_t len; sp = start = s; ep = end = s+sdslen(s)-1; /* 從頭部和尾部逐個字符遍歷往中間靠攏,如果字符在cest中,則繼續(xù)前進 */ while(sp <= end && strchr(cset, *sp)) sp++; while(ep > sp && strchr(cset, *ep)) ep--; len = (sp > ep) ? 0 : ((ep-sp)+1); // 全部被去除了,長度就是0 if (s != sp) memmove(s, sp, len); // 拷貝內(nèi)容 s[len] = '\0'; sdssetlen(s,len); return s; }
二進制安全
二進制安全指的是只關(guān)心二進制化的字符串,不關(guān)心具體格式。只會嚴(yán)格的按照二進制的數(shù)據(jù)存取,不會妄圖以某種特殊格式解析數(shù)據(jù)。比如遇到'0'字符不會停止解析。
對于C字符串來說,strlen
是判斷遇到'0'之前的字符數(shù)量。如果需要保存二進制的數(shù)據(jù),就不能通過傳統(tǒng)的C字符串來保存,因為獲取不到它真實的長度。而sds字符串是通過len屬性保存字符串的大小,所以它是二進制安全的。
其他小函數(shù)實現(xiàn)
在閱讀源碼的過程中,也發(fā)現(xiàn)了兩個個人比較感興趣趣的函數(shù):
sdsll2str(將long long類型的整型數(shù)字轉(zhuǎn)成字符串)
sdstrim (去除頭部和尾部的指定字符)
我這兩個函數(shù)拉出來做了測試,在項目的redis-4.0/tests
目錄下。sdstrim
函數(shù)的實現(xiàn)源碼上面有列出,看看sdsll2str
的實現(xiàn):
int sdsll2str(char *s, long long value) { char *p, aux; unsigned long long v; size_t l; /* 通過取余數(shù)得到原字符串的逆轉(zhuǎn)形式 */ v = (value < 0) ? -value : value; p = s; do { *p++ = '0'+(v%10); v /= 10; } while(v); if (value < 0) *p++ = '-'; /* Compute length and add null term. */ l = p-s; *p = '\0'; /* 反轉(zhuǎn)字符串 */ p--; while(s < p) { aux = *s; *s = *p; *p = aux; s++; p--; } return l; }
函數(shù)是通過不斷取余數(shù),得到原字符串的逆轉(zhuǎn)形式,接著,通過從尾部開始將字符逐個放到字符串s中,看起來像是一個反轉(zhuǎn)操作,從而實現(xiàn)了將整型轉(zhuǎn)為字符串的操作。
覺得感興趣是因為sdsll2str
這個函數(shù)在之前學(xué)習(xí)C語言的時候經(jīng)常能看到作為問題出現(xiàn),能看到如此簡潔的實現(xiàn),表示眼前一亮。而在PHP開發(fā)時經(jīng)常使用trim函數(shù),所以想看看它們的區(qū)別。
總結(jié)
通過詳細地閱讀sds的源碼,不僅學(xué)習(xí)到sds的實現(xiàn)細節(jié),還學(xué)習(xí)到了一些常用字符串操作函數(shù)的實現(xiàn)。如果只是僅僅看看數(shù)據(jù)結(jié)構(gòu)的定義也可以初步了解,但是要深入了解的話還是需要詳細的閱讀具體函數(shù)的實現(xiàn)代碼。還是那句,寫代碼的,需要閱讀更多代碼來增強靈感。
我在github有對Redis源碼更詳細的注解 Redis4.0源碼注解。
可以通過commit記錄查看已添加的注解。
以上就是Redis源碼解析sds字符串實現(xiàn)示例的詳細內(nèi)容,更多關(guān)于Redis sds字符串的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
Redis系列之底層數(shù)據(jù)結(jié)構(gòu)SDS詳解
SDS(簡單動態(tài)字符串)是Redis使用的核心數(shù)據(jù)結(jié)構(gòu),用于替代C語言的字符串,以解決長度獲取慢、內(nèi)存溢出等問題,SDS通過預(yù)分配與惰性釋放策略優(yōu)化內(nèi)存使用,增強安全性,且能存儲文本與二進制數(shù)據(jù),可查看源碼src/sds.h和src/sds.c了解更多2024-11-11