redis中的sds結構解析
0丶源碼基于redis 6.2.7
1丶什麼是sds
sds 即: simple dynamic string,簡單動态字元串 2丶redis為什麼使用sds,不适用c語言的字元串呢?
1丶sds可以在O(1)的時間範圍中擷取字元串長度,c語言需要周遊
2丶sds擁有自動擴容機制.
3丶sds擁有惰性空間釋放機制,減少了記憶體配置設定次數.
4丶sds是二進制安全的. 3丶從源碼探究
3.1 ,下載下傳源碼
Download | Redis
3.2. 檢視源碼
打開sds.h
/*
* sdshdr5從未被使用過,隻是通路flag辨別;
* flag 低三位 存儲類型; 高5位 存儲資料長度. 2^5=32. 因為buf最後以/0結尾. 故最大長度為31.
* typedef unsigned char uint8_t;
typedef unsigned short uint16_t;
typedef unsigned int uint32_t;
typedef unsigned __int64 uint64_t;
* */
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; /*flag 低三位 存儲類型; 高5位 存儲資料長度. 2^5=32. 因為buf最後以/0結尾. 故最大長度為31.*/
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* 已使用的資料長度 */
uint8_t alloc; /* 總長度 */
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[];
}; 短字元串,長度小于32時,使用的資料結構sdshdr5,結構如下.
相比redis3.0.0結構:
struct sdshdr {
//記錄buf數組中已使用位元組的數量
//等于SDS所儲存字元串的長度
unsigned int len;
//記錄buf數組中未使用位元組的數量
unsigned int free;
//char數組，用于儲存字元串
char buf[];
}; 3.3. sds的優化
因為曆史版本的sds,無論字元串多長,它header裡面的len,free字段,都需要占用8個位元組的大小,這如果儲存小字元串實在是太浪費了,
故在6.2.7中我們發現,他根據不同的字元串長度,使用不同的結構類型. 如果字元串長度在32位以内,則隻多了1個位元組的長度來存儲字元串長度資訊.
4丶優勢解讀
4.1, 為什麼是O(1)的時間複雜度擷取字元串長度?
根據,6.2.7源碼中看出,無論字元串長度多少,隻是增加了一個字段.
unsigned char flags; 1位=8位元組. flags字段,它使用第三位儲存資料結構
如下圖擷取字元串長度的源碼:
#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
#define SDS_TYPE_BITS 3
//這裡的sizeof 傳回實際的類型
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
//falgs字段向右移動三位,就是字元串長度
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)
/**擷取字元串長度*/
static inline size_t sdslen(const sds s) {
//因為sds的指針指向buf數組,則buf數組往前一位,就是falgs字段.
unsigned char flags = s[-1];
//flags字段的低3位是資料結構,與7 &; 則得到實際的資料結構.
// 7 = 0 0 0 0 0 1 1 1
//flags= X X X X X X X X
switch(flags&SDS_TYPE_MASK) {
case SDS_TYPE_5:
//因為高5位是字元串長度,拿到高5位的值即可.
return SDS_TYPE_5_LEN(flags);
//餘下方式都一樣,拿到實際對應的資料結構,見源碼3.2. 然後拿出期中的len字段
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;
} 由上圖可見,因為字元串長度是用屬性存儲的,故直接擷取即可,不需要像c語言一樣循環得出.
4.2 sds是二進制安全的.
** 什麼是二進制安全？**
通俗地講，C語言中，用’0’表示字元串的結束，如果字元串本身就有’0’字元，字元串就會被截斷，即非二進制安全；若通過某種機制，保證讀寫字元串時不損害其内容，則是二進制安全。
SDS使用len屬性的值判斷字元串是否結束，不會受’\0’的影響。
4.3 sds的的自動擴容
首先看C語言中的字元串拼接
char * __cdecl strcat (char * dst, const char * src)
{
char * cp = dst;
while( *cp )
cp++; /* 找到 dst 的結尾 */
while( *cp++ = *src++ ) ; /* 無腦将 src 複制到 dst 中; 要是dst的長度不夠呢?就會被覆寫!!!!!!!! */
return( dst ); /* 傳回 dst */
} 在看redis中的擴容:
sds sdscatsds(sds s, const sds t) {
return sdscatlen(s, t, sdslen(t));
}
/* s: 源字元串
* t: 待拼接字元串
* len: 待拼接字元串長度
*/
sds sdscatlen(sds s, const void *t, size_t len) {
// 擷取目前字元串的長度
size_t curlen = sdslen(s);
// SDS 自動擴容. 傳入原字元串長度與拼接字元串長度
s = sdsMakeRoomFor(s,len);
if (s == NULL) return NULL;
// 将目标字元串拷貝至源字元串末尾
memcpy(s+curlen, t, len);
// 更新 SDS 長度
sdssetlen(s, curlen+len);
// 追加結束符
s[curlen+len] = '\0';
return s;
}
/* s: 源字元串
* addlen: 新增長度
*/
sds sdsMakeRoomFor(sds s, size_t addlen) {
void *sh, *newsh;
// sdsavail: s->alloc - s->len, 擷取 SDS 的剩餘長度;
//如果是SDS_TYPE_5 則直接傳回0;
size_t avail = sdsavail(s);
size_t len, newlen, reqlen;
// 根據 flags 擷取 SDS 的類型 oldtype
char type, oldtype = s[-1] & SDS_TYPE_MASK;
int hdrlen;
size_t usable;
/* Return ASAP if there is enough space left. */
// 剩餘空間大于等于新增空間，無需擴容，直接傳回源字元串
if (avail >= addlen) return s;
// 擷取目前長度
len = sdslen(s);
//
sh = (char*)s-sdsHdrSize(oldtype);
// 新長度
reqlen = newlen = (len+addlen);
// 斷言新長度比原長度長，否則終止執行
assert(newlen > len); /* 防止資料溢出 */
// SDS_MAX_PREALLOC = 1024*1024, 即1MB
if (newlen < SDS_MAX_PREALLOC)
// 新增後長度小于 1MB ，則按新長度的兩倍擴容
newlen *= 2;
else
// 新增後長度大于 1MB ，則按新長度加上 1MB 擴容
newlen += SDS_MAX_PREALLOC;
// 重新計算 SDS 的類型
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. */
// 不使用 sdshdr5 . 因為sdshdr5是沒有len屬性與alloc屬性 無法記住 空的 空間.
if (type == SDS_TYPE_5) type = SDS_TYPE_8;
// 擷取新的 header 大小
hdrlen = sdsHdrSize(type);
assert(hdrlen + newlen + 1 > reqlen); /* Catch size_t overflow */
if (oldtype==type) {
// 類型沒變
// 調用 s_realloc_usable 重新配置設定可用記憶體，傳回新 SDS 的頭部指針
// usable 會被設定為目前配置設定的大小
newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
if (newsh == NULL) return NULL; // 配置設定失敗直接傳回NULL
// 擷取指向 buf 的指針
s = (char*)newsh+hdrlen;
} else {
// 類型變化導緻 header 的大小也變化，需要向前移動字元串，不能使用 realloc
newsh = s_malloc_usable(hdrlen+newlen+1, &usable);
if (newsh == NULL) return NULL;
// 将原字元串copy至新空間中
memcpy((char*)newsh+hdrlen, s, len+1);
// 釋放原字元串記憶體
s_free(sh);
s = (char*)newsh+hdrlen;
// 更新 SDS 類型
s[-1] = type;
// 設定長度
sdssetlen(s, len);
}
// 擷取 buf 總長度(待定)
usable = usable-hdrlen-1;
if (usable > sdsTypeMaxSize(type))
// 若可用空間大于目前類型支援的最大長度則截斷
usable = sdsTypeMaxSize(type);
// 設定 buf 總長度
sdssetalloc(s, usable);
return s;
} 自動擴容機制總結：
擴容階段：
- 若 SDS 中剩餘空閑空間 avail 大于新增内容的長度 addlen，則無需擴容； 注意:若是sdshdr5 則直接範圍0,必然擴容.
- 若 SDS 中剩餘空閑空間 avail 小于或等于新增内容的長度 addlen：
- 若新增後總長度 len+addlen < 1MB，則按新長度的兩倍擴容；
- 若新增後總長度 len+addlen > 1MB，則按新長度加上 1MB 擴容。
記憶體配置設定階段：
- 根據擴容後的長度選擇對應的 SDS 類型：
- 若類型不變，則隻需通過
s_realloc_usable
- 若類型變化，則需要為整個 SDS 重新配置設定記憶體，并将原來的 SDS 内容拷貝至新位置。
4.4 惰性空間釋放機制,空間預配置設定政策
1丶空間預配置設定政策. 這樣子擴容N次,SDS 将連續增長N次字元串所需的記憶體重配置設定次數從必定N次降低為最多N次。
見4.3的擴容邏輯,因為每次是*2或者增加1M大小,預留了空間,減少記憶體配置設定的次數.
2丶惰性空間釋放機制
空間預配置設定,是減少增加字元串擴容的次數,凍醒空間釋放則相反,是優化了減少字元串空間配置設定的次數.
sds sdstrim(sds s, const char *cset) {
char *start, *end, *sp, *ep;
size_t len;
sp = start = s;
ep = end = s+sdslen(s)-1;
// strchr()函數用于查找給定字元串中某一個特定字元
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';
// 僅僅更新了len
sdssetlen(s,len);
return s;
} sds sdsRemoveFreeSpace(sds s) {
void *sh, *newsh;
//sds類型
char type, oldtype = s[-1] & SDS_TYPE_MASK;
// 擷取 header 大小
int hdrlen, oldhdrlen = sdsHdrSize(oldtype);
//原字元串長度
size_t len = sdslen(s);
//原sds剩餘空間
size_t avail = sdsavail(s);
//擷取指向頭部的指針; s的指針
sh = (char*)s-oldhdrlen;
/* Return ASAP if there is no space left. */
if (avail == 0) return s;
/* 擷取實際需要的類型,與header大小 */
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;
} 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;
}