Redis 在處理字串資料時,另外實現了一個名為 SDS (Simple Dynamic String)的資料結構。
前置知識
在 C 語言中,字串是由字元陣列構成,並在最後加入 \0
(NULL Byte)作為結束標記,這種實作方式存在一些缺點
- 非 Binary Safe:對於一些 UTF-8 字串可能中間會夾雜 NULL Byte,此時就會被當字串結尾
- 在 CVE-2006-7234 中,因為 PHP 實作上的缺陷導致可以在插入 NULL Byte 導致預期外行為
- 長度計算為 $O(n)$:在計算字串長度時,需要走訪字元陣列並找到
\0
- 實際上,標準函式庫的
strlen()
在計算字串長度時會利用資料對齊的特性所以執行效率會略高於每個字元比對 - 在比較現代的 CPU 上,還可以利用一些較為現代的指令集去加速比對
- 實際上,標準函式庫的
SDS
在 Redis 中,為了保證 Binary Safe 及效率問題,其核心實作了 SDS,定義於 sds.h
中
struct __attribute__((__packed__)) sdshdr5 {
unsigned char flags;
char buf[];
}
struct __attribute__((__packed__)) sdshdr8 {
uint8_t len;
uint8_t alloc;
unsigned char flags;
char buf[];
}
- 另有
sdshdr16
,sdshdr32
,sdshdr64
分別使用uint16_t
,uint32_t
及uint64_t
作為len
及alloc
的資料型態
len 及 alloc
len
為有效字串長度,這使得 SDS 能夠在 $O(1)$ 複雜度下取得字串長度
alloc
表示記憶體分配時所申請的大小,即整個 SDS 的總大小。alloc - len
即為可使用的空閒空間。
flags
3 LSB(最小的 3 位元)代表型態,表示它是 sdshdr5
, sdshdr8
, sdshdr16
, sdshdr32
或 sdshdr64
在 sdshdr5
中,剩下的 5 MSB(最大的 5 位元)代表長度。因此, sdshdr5
僅能存放 32 bytes($2^5$)長度的字串;在其餘的型態中,剩下的 5 MSB 沒有作 用。
沿革
在 2009 年 5 月初時 Redis 的 First Commit 中:
struct sdshdr {
long len;
long free;
char buf[0];
}
到 2009 年 5 月底時以 Flexible Array Member 改寫 buf
struct sdshdr {
long len;
long free;
char buf[];
}
直到 Redis 3.2 RC1(2015 年 12 月)才成為當前的型式。
SDS 的操作分析
typedef char *sds;
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. */
if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
int hdrlen = sdsHdrSize(type);
unsigned char *fp; /* flags pointer. */
assert(initlen + hdrlen + 1 > initlen); /* Catch size_t overflow */
sh = s_malloc(hdrlen+initlen+1);
if (sh == NULL) return NULL;
if (init==SDS_NOINIT)
init = NULL;
else if (!init)
memset(sh, 0, hdrlen+initlen+1);
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;
}
確認 type
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;
return SDS_TYPE_64;
#else
return SDS_TYPE_32;
#endif
}
char type = sdsReqType(initlen);
if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
若長度為 0
,表示之後可能會加資料進去,此時就不會使用 SDS_TYPE_5
而應該用 SDS_TYPE_8
。
申請記憶體空間
#define SDS_TYPE_MASK 7
static inline int sdsHdrSize(char type) {
switch(type&SDS_TYPE_MASK) {
case SDS_TYPE_5:
return sizeof(struct sdshdr5);
case SDS_TYPE_8:
return sizeof(struct sdshdr8);
case SDS_TYPE_16:
return sizeof(struct sdshdr16);
case SDS_TYPE_32:
return sizeof(struct sdshdr32);
case SDS_TYPE_64:
return sizeof(struct sdshdr64);
}
return 0;
}
void *sh;
sh = s_malloc(hdrlen+initlen+1);
if (sh == NULL) return NULL;
- 因為不同種類的 SDS 會有不同大小,所以用
sdsHdrSize
預先取得要申請的記憶體空間大小。type&SDS_TYPE_MASK
表示只有 3 LSB 是代表 SDS Header Type
s_malloc
是一個串接zmalloc
的 macro,而zmalloc
則是 Redis 包裝記憶體管理機制的實作zmalloc
會依序使用tcmalloc
,jemalloc
或ptmalloc
- 總共的記憶體
hdrlen
:給struct sdshdr
的空間initlen
:因為buf
是一個 Flexible Array Member,所以其後需要加上額外的大小(字串長度)1
:用於存放 NULL Byte
賦值
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
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;
}
// ...
}
s
會指向字串的開頭sh
是整個結構 的起始,加上hdrlen
就是結構長度,所以s
指向struct sdshdr
的buf
空間
fp
會指向struct sdshdr
中的flag
- 利用
((unsigned char*)s)-1
取得flag
的位址,因為前面的大小不固定所以依賴s
的位址去取得flag
的位址
- 利用
SDS_TYPE_5 的賦值
因為 SDS_TYPE_5
沒有 len
及 alloc
,其資訊都儲存在 flag
中
|-----------------|-------------------- buf ---------------------------|
| flags: 01011000 | h | e | l | l | o | ' ' | w | o | r | l | d | '\0' |
|-----------------|----------------------------------------------------|
^
01011 代表長度(11)
000 代表類型(SDS_TYPE_5 = 0)
擴充容量
sds sdsMakeRoomFor(sds s, size_t addlen) {
void *sh, *newsh;
size_t avail = sdsavail(s);
size_t len, newlen, reqlen;
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);
reqlen = newlen = (len+addlen);
assert(newlen > len); /* Catch size_t overflow */
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);
assert(hdrlen + newlen + 1 > reqlen); /* Catch size_t overflow */
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;
}
取得可用空間
static inline size_t sdsavail(const sds s) {
unsigned char flags = s[-1];
switch(flags&SDS_TYPE_MASK) {
case SDS_TYPE_5: {
return 0;
}
case SDS_TYPE_8: {
SDS_HDR_VAR(8,s);
return sh->alloc - sh->len;
}
// ...
}
return 0;
}
size_t avail = sdsavail(s);
if (avail >= addlen) return s;
SDS_TYPE_5
是固定空間的字串,不會有可用空間- 其它會用已分配的空間
alloc
減去字串長度len
- 如果剩餘空間還夠,表示不需要擴充容量則直接回傳
決定新的 type
#define SDS_MAX_PREALLOC 1024*1024
reqlen = newlen = (len+addlen);
assert(newlen > len); /* Catch size_t overflow */
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;
type = sdsReqType(newlen);
if (type == SDS_TYPE_5) type = SDS_TYPE_8;
為了避免每次擴充容量都要做 memcpy
的成本,預設會分配較多的空間。
- 如果
newlen
小於2**20
(1 MB),就分配 2 倍的newlen
的空間 - 如果
newlen
大於等於 1 MB,就分配newlen + 1MB
的空間
新的 type
將會根據 newlen
的長度計算。
- 如果
newlen
算出來的type
是sdshdr5
就改成sdshdr8
,因為sdshdr5
不能被擴容
建立新的 SDS
hdrlen = sdsHdrSize(type);
assert(hdrlen + newlen + 1 > reqlen); /* Catch size_t overflow */
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);
}
- 根據新的
type
取得新的hdrlen
- 如果
oldtype
等於新的type
,表示其 SDS Header 大小相同- 只需要
realloc
多出來的記憶體空間即可
- 只需要
- 如果
oldtype
不等於新的type
,表示其 SDS Header 大小不同- 需要重新建立一個 SDS,並把舊字串的內容複製過去
- 最後再清空原本的 SDS
- 最後更新
len
及alloc