一斋泄、SDS結(jié)構(gòu)
老版本
// 3.0及以前
//查看到redis2.6版本 sds.h/sdshdr
struct sdshdr {
// 記錄buf數(shù)組中已使用字節(jié)數(shù)量
unsigned int len;
// 記錄buf數(shù)組中未使用的字節(jié)數(shù)量
unsigned int free;
// 字節(jié)數(shù)組，存儲(chǔ)字符串
//最后一個(gè)字節(jié)保存為空字符 '\0'
char buf[];
};
sds優(yōu)點(diǎn)
頻繁操作數(shù)據(jù)會(huì)對(duì)性能存在很大影響
- 空間預(yù)分配
a镐牺、小于1MB SDS分配的len和free 是相同炫掐，如len=5 ，free=5睬涧，buf總長(zhǎng)度為 5+5+1 募胃，其中1為結(jié)束符\0旗唁。
b、大于1MB SDS分配的空間 3MB+1MB+1btype 每次只擴(kuò)充1MB痹束。
在擴(kuò)展SDS空間之前检疫，SDS API會(huì)先檢查未使用空間是否足夠，如果足夠的話(huà)祷嘶，API就會(huì)直接使用未使用空間屎媳，而無(wú)須執(zhí)行內(nèi)存重分配。
通過(guò)這種預(yù)分配策略论巍，SDS將連續(xù)增長(zhǎng)N次字符串所需的內(nèi)存重分配次數(shù)從必定N次降低為最多N次烛谊。
（空間就是這么節(jié)省的）
- 惰性空間釋放
sds在對(duì)字符串做縮短操作時(shí)候 程序并不立即使用內(nèi)存重新分配來(lái)回收多出來(lái)的字符，而是通過(guò)free屬性來(lái)記錄起來(lái)多出來(lái)的字符長(zhǎng)度嘉汰，等待回來(lái)使用
現(xiàn)在使用版本
typedef char *sds;
/* Note: sdshdr5 is never used, we just access the flags byte directly.
* However is here to document the layout of type 5 SDS strings. */
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[];
};
1. len 記錄當(dāng)前字節(jié)數(shù)組的長(zhǎng)度（不包括\0）
2. alloc記錄了當(dāng)前字節(jié)數(shù)組總共分配的內(nèi)存大械べ鳌（不包括\0）
3. flags記錄了當(dāng)前字節(jié)數(shù)組的屬性、用來(lái)標(biāo)識(shí)到底是sdshdr8還是sdshdr16等
4. buf保存了字符串真正的值以及末尾的一個(gè)\0
5種不同類(lèi)型的數(shù)據(jù)結(jié)構(gòu)分別對(duì)應(yīng)不同長(zhǎng)度的字符串需求
static inline char sdsReqType(size_t string_size) {
if (string_size < 1<<5)
return SDS_TYPE_5;
if (string_size < 1<<8)
return SDS_TYPE_8;
if (string_size < 1<<16)
return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
if (string_size < 1ll<<32)
return SDS_TYPE_32;
#endif
return SDS_TYPE_64;
}
sdshdr5數(shù)據(jù)結(jié)構(gòu)說(shuō)明：
沒(méi)有alloc 和len
原因：
#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_TYPE只占用了0,1,2,3,4五個(gè)數(shù)字鞋怀，正好占用三位双泪。
由于sdshdr5的只用來(lái)存儲(chǔ)長(zhǎng)度為32字節(jié)以下的字符數(shù)，
因此flags的5個(gè)bit就能滿(mǎn)足長(zhǎng)度記錄接箫，加上type所需的3bit攒读，剛好為8bit一個(gè)字節(jié)。
因此sdshdr5不需要單獨(dú)的len記錄長(zhǎng)度辛友，并且只有32個(gè)字節(jié)的存儲(chǔ)空間薄扁，動(dòng)態(tài)的變更內(nèi)存余地較小，
所以 redis 直接不存儲(chǔ)alloc废累，當(dāng)sdshdr5需要擴(kuò)展時(shí)會(huì)直接變更成更大的SDS數(shù)據(jù)結(jié)構(gòu)邓梅。
除此之外，SDS都會(huì)多分配1個(gè)字節(jié)用來(lái)保存'\0'邑滨。
SDS 創(chuàng)建
/* Create a new sds string with the content specified by the 'init' pointer
* and 'initlen'.
* If NULL is used for 'init' the string is initialized with zero bytes.
*
* The string is always null-termined (all the sds strings are, always) so
* even if you create an sds string with:
*
* mystring = sdsnewlen("abc",3);
*
* You can print the string with printf() as there is an implicit \0 at the
* end of the string. However the string is binary safe and can contain
* \0 characters in the middle, as the length is stored in the sds header.
*/
sds sdsnewlen(const void *init, size_t initlen) {
void *sh;
sds s;
char type = sdsReqType(initlen);
/* Empty strings are usually created in order to append. Use type 8
* since type 5 is not good at this.
直接強(qiáng)制賦值為SDS_TYPE_8
*/
if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
int hdrlen = sdsHdrSize(type);
unsigned char *fp; /* flags pointer. */
sh = s_malloc(hdrlen+initlen+1);
if (!init)
memset(sh, 0, hdrlen+initlen+1);
if (sh == NULL) return NULL;
s = (char*)sh+hdrlen;
fp = ((unsigned char*)s)-1;
switch(type) {
case SDS_TYPE_5: {
*fp = type | (initlen << SDS_TYPE_BITS);
break;
}
case SDS_TYPE_8: {
SDS_HDR_VAR(8,s);
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break;
}
case SDS_TYPE_16: {
SDS_HDR_VAR(16,s);
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break;
}
case SDS_TYPE_32: {
SDS_HDR_VAR(32,s);
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break;
}
case SDS_TYPE_64: {
SDS_HDR_VAR(64,s);
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break;
}
}
if (initlen && init)
memcpy(s, init, initlen);
s[initlen] = '\0';
return s;
}
SDS擴(kuò)容
#define SDS_MAX_PREALLOC (1024*1024) 為1M
/* Enlarge the free space at the end of the sds string so that the caller
* is sure that after calling this function can overwrite up to addlen
* bytes after the end of the string, plus one more byte for nul term.
*
* Note: this does not change the *length* of the sds string as returned
* by sdslen(), but only the free buffer space we have. */
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;
/* Return ASAP if there is enough space left. */
if (avail >= addlen) return s;
len = sdslen(s);
sh = (char*)s-sdsHdrSize(oldtype);
newlen = (len+addlen);
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;
type = sdsReqType(newlen);
/* Don't use type 5: the user is appending to the string and type 5 is
* not able to remember empty space, so sdsMakeRoomFor() must be called
* at every appending operation. */
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 {
/* Since the header size changes, need to move the string forward,
* and can't use realloc */
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;
sdssetlen(s, len);
}
sdssetalloc(s, newlen);
return s;
}
該函數(shù)便是擴(kuò)大sds空間日缨，但是感覺(jué)上還是想讓sds中available空間的大小能夠容納addlen大小的字符串，并不是改變了sds中buf的長(zhǎng)度掖看，
而是改變了sds中available空間的大小匣距，
如果當(dāng)前available空間的大小大于addlen的大小，那么便不作修哎壳；
如果available空間的大小小于addlen的大小毅待，那么就會(huì)重新分配sds中alloc的大小，
newlen并不是無(wú)腦直接讓alloc加上addlen归榕，而且使用sds的長(zhǎng)度加上addlen的長(zhǎng)度
作為newlen尸红，但是經(jīng)常重新分配內(nèi)存會(huì)對(duì)效率有所影響，但是為了防止重新分配內(nèi)存
對(duì)效率的影響而讓newlen無(wú)腦翻倍的話(huà)，又會(huì)對(duì)內(nèi)存造成影響外里，造成內(nèi)存占用過(guò)高怎爵，
但是很大一部分內(nèi)存并沒(méi)有使用，所以取得了一個(gè)折中的辦法盅蝗，就是在newlen小于
SDS_MAX_PREALLOC(1M)鳖链，對(duì)newlen進(jìn)行翻倍，
在newlen大于SDS_MAX_PREALLOC的情況下风科，讓newlen加上SDS_MAX_PREALLOC撒轮。
符合前面提的空間預(yù)分配
SDS惰性空間釋放
在SDS的字符串縮短操作中，多余出來(lái)的空間并不會(huì)直接釋放贼穆，而是保留這部分空間题山，待以后再用
/* Remove the part of the string from left and from right composed just of
* contiguous characters found in 'cset', that is a null terminted C string.
*
* After the call, the modified sds string is no longer valid and all the
* references must be substituted with the new pointer returned by the call.
*
* Example:
*
* s = sdsnew("AA...AA.a.aa.aHelloWorld :::");
* s = sdstrim(s,"Aa. :");
* printf("%s\n", s);
*
* Output will be just "Hello World".
*/
sds sdstrim(sds s, const char *cset) {
char *start, *end, *sp, *ep;
size_t len;
sp = start = s;
ep = end = s+sdslen(s)-1;
while(sp <= end && strchr(cset, *sp)) sp++;
while(ep > sp && strchr(cset, *ep)) ep--;
len = (sp > ep) ? 0 : ((ep-sp)+1);
if (s != sp) memmove(s, sp, len);
s[len] = '\0';
sdssetlen(s,len);
return s;
}
真正將空間釋放還是會(huì)根據(jù)實(shí)際字符串情況返回對(duì)應(yīng)類(lèi)型。
例如以前是一個(gè)sdshdr64的sds故痊，在redis運(yùn)行過(guò)程中顶瞳，buf的內(nèi)容被修改了，變短了愕秫，那么多出來(lái)的內(nèi)容就需要釋放掉慨菱，還給系統(tǒng)，并且戴甩，如果修改得比較多符喝，現(xiàn)在一個(gè)sdshdr16的sds就能容納下，那么當(dāng)前sds的type還會(huì)被修改甜孤，因?yàn)椴煌膕ds類(lèi)型占用的空間也是不一樣的协饲。
/* Reallocate the sds string so that it has no free space at the end. The
* contained string remains not altered, but next concatenation operations
* will require a reallocation.
*
* After the call, the passed sds string is no longer valid and all the
* references must be substituted with the new pointer returned by the call. */
sds sdsRemoveFreeSpace(sds s) {
void *sh, *newsh;
char type, oldtype = s[-1] & SDS_TYPE_MASK;
int hdrlen, oldhdrlen = sdsHdrSize(oldtype);
size_t len = sdslen(s);
sh = (char*)s-oldhdrlen;
/* Check what would be the minimum SDS header that is just good enough to
* fit this string. */
type = sdsReqType(len);
hdrlen = sdsHdrSize(type);
/* If the type is the same, or at least a large enough type is still
* required, we just realloc(), letting the allocator to do the copy
* only if really needed. Otherwise if the change is huge, we manually
* reallocate the string to use the different header type. */
if (oldtype==type || type > SDS_TYPE_8) {
newsh = s_realloc(sh, oldhdrlen+len+1);
if (newsh == NULL) return NULL;
s = (char*)newsh+oldhdrlen;
} else {
newsh = s_malloc(hdrlen+len+1);
if (newsh == NULL) return NULL;
memcpy((char*)newsh+hdrlen, s, len+1);
s_free(sh);
s = (char*)newsh+hdrlen;
s[-1] = type;
sdssetlen(s, len);
}
sdssetalloc(s, len);
return s;
總結(jié)：
類(lèi)似java 的ArrayList
遺留問(wèn)題
- Redis的embstr編碼方式和raw編碼方式分別是什么，區(qū)別是什么
- 為什么會(huì)sdstype5 不被使用
