天天看點
傳回

Redis源碼分析之sds

1. SDS簡介

Redis

沒有直接使用C語言傳統的字元串而是自己建立了一種名為簡單動态字元串

SDS（simple dynamic string）

的抽象類型，并将SDS用作Redis的預設字元串表示。

在Redis裡面，C字元串隻會作為字元串字面量（string literal）用在一些無須對字元串值進行修改的地方，比如列印日志。

當Redis需要的不僅僅是一個字元串字面量，而是一個字元串值時，Redis就會使用SDS來表示字元串值，比如在Redis的資料庫裡面，包含字元串的鍵值對在底層都是由SDS實作的。

for example：

redis> SET msg "hello world"
OK

那麼Redis将在資料庫中建立一個新的鍵值對，其中：

鍵值對的鍵就是一個字元串對象，對象的底層實作是一個儲存着字元串“msg”的SDS。

鍵值對的值也是一個字元串對象，對象的底層實作是一個儲存着字元串“hello world”的SDS。

除了用來儲存資料庫中的

字元串值

之外，

SDS

還被用作

緩沖區(buffer):AOF子產品中的AOF緩沖區

，以及用戶端狀态中的輸入緩沖區，都是由SDS實作的。

我們需要知道，SDS的實作，SDS與C字元串的不同之處，解釋為什麼Redis要使用SDS而不是C字元串。

2.1 SDS的定義

Redis沒有使用C語言的字元串結構，而是自己設計了一個簡單的動态字元串結構sds。它的特點是：可動态擴充記憶體、二進制安全和傳統的C語言字元串類型相容。（sds的源碼主要實作在sds.c和sds.h兩個檔案中）

在sds.h檔案中，我們可以找到sds的資料結構定義如下：

typedef char *sds;

這不就是char嗎？的确，Redis采用一整段連續的記憶體來存儲sds結構，char類型正好可以和傳統的C語言字元串類型相容。但是，sds和char*并不等同，

sds和char*并不等同

，sds是二進制安全的，它可以存儲任意二進制資料，不能像C語言字元串那樣以’\0’來辨別字元串的結束，是以它必然存在一個長度字段，那麼這個長度字段在哪呢？如下：

/* 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[];
};

sds一共有五種Header定義，其目的是為了瞞住不同長度的字元串可以使用不同大小的Header，進而節省記憶體。

Header部分主要包含以下幾個部分，其目的是為了滿足不同長度的字元串可以使用不同大小的Header，進而節省記憶體。

Header部分主要包含以下幾個部分：

+len

：表示字元串真正的長度，不包括空終止字元

+alloc

：表示字元串的最大容量，不包含Header和最後的空終止字元

+flags

：表示Header的類型

// 五種header類型，flags取值為0~4

#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

由于sds是采用一段連續的記憶體空間來存儲動态字元串，那麼，我們進一步來分析一下sds在記憶體中的布局。如圖是字元串“redis”在記憶體中的布局示例圖：

Redis源碼分析之sds

由于sds的header共有五種，要想得到sds的header屬性，就必須先知道header的類型，flags字段存儲了header的類型。假如我們定義了sds*s，那麼擷取flags字段僅僅需要将s向前移動一個位元組，即unsigned char flags = s[-1]

擷取了

header

的類型之後，我們就可以按照每個類型header的定義來擷取

sds

的長度，最大容量等屬性了。Redis定義了如下幾個

宏定義

來操作header

#define SDS_TYPE_MASK 7 // 類型掩碼

#define SDS_TYPE_BITS 3

#define SDS_HDR_VAR(T,s) struct sdshdr##T sh = (void)((s)-(sizeof(struct sdshdr##T))); // 擷取header頭指針

#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T)))) // 擷取header頭指針

#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS) // 擷取sdshdr5的長度

其中

SDS_HDR

是為了擷取

header

的頭指針，即s指針按照header的結構大小向前偏移

sizeof(struct sdshdr##T)

位，找到了header的頭指針，就很容易擷取

len

和

alloc

的大小了。

到這裡，sds的資料結構定義就基本清楚了，下面來看看sds的一些基本操作函數。

sds基本操作函數

sds建立函數

Redis在建立sds時，會為其申請一段連續的記憶體空間，其中包含sds的header和資料部分buff[]。其建立函數如下：

sds sdsnewlen(const void *init, size_t initlen) {

void sh;

sds s;

char type = sdsReqType(initlen);

// 空的字元串通常被建立成type 8，因為type 5已經不實用了。

if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;

// 得到sds的header的大小

int hdrlen = sdsHdrSize(type);

unsigned char fp; // flags字段的指針

// s_malloc等同于zmalloc，+1代表字元串結束符

sh = s_malloc(hdrlen+initlen+1);

if (!init)

memset(sh, 0, hdrlen+initlen+1);

if (sh == NULL) return NULL;

// s為資料部分的起始指針

s = (char)sh+hdrlen;

fp = ((unsigned char)s)-1; // 得到flags的指針

// 根據字元串類型來設定header中的字段

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’; // 與C字元串相容

return s; // 傳回建立的sds字元串指針

}

sds釋放函數

sds的釋放采用s_free來釋放記憶體。其實作代碼如下：

void sdsfree(sds s) {

if (s == NULL) return;

// 得到記憶體的真正其實位置，然後釋放記憶體

s_free((char*)s-sdsHdrSize(s[-1]));

}

sds動态調整函數

sds最重要的性能就是動态調整，Redis提供了擴充sds容量的函數。

// 在原有的字元串中取得更大的空間，并傳回擴充空間後的字元串

sds sdsMakeRoomFor(sds s, size_t addlen) {

void *sh, *newsh;

size_t avail = sdsavail(s); // 擷取sds的剩餘空間

size_t len, newlen;

char type, oldtype = s[-1] & SDS_TYPE_MASK;

int hdrlen;

// 如果剩餘空間足夠，則直接傳回

if (avail >= addlen) return s;

len = sdslen(s);

sh = (char*)s-sdsHdrSize(oldtype);

newlen = (len+addlen);

// sds規定：如果擴充後的字元串總長度小于1M則新字元串長度為擴充後的兩倍

// 如果大于1M，則新的總長度為擴充後的總長度加上1M

// 這樣做的目的是減少Redis記憶體配置設定的次數，同時盡量節省空間

if (newlen < SDS_MAX_PREALLOC) // SDS_MAX_PREALLOC = 1024*1024

newlen *= 2;

else

newlen += SDS_MAX_PREALLOC;

// 根據sds的長度來調整類型

type = sdsReqType(newlen);

// 不使用SDS_TYPE_5，一律按SDS_TYPE_8處理

if (type == SDS_TYPE_5) type = SDS_TYPE_8;

// 擷取新類型的頭長度

hdrlen = sdsHdrSize(type);

if (oldtype==type) {

// 如果與原類型相同，直接調用realloc函數擴充記憶體

newsh = s_realloc(sh, hdrlen+newlen+1);

if (newsh == NULL) return NULL;

s = (char*)newsh+hdrlen;

} else {

// 如果類型調整了，header的大小就需要調整

// 這時就需要移動buf[]部分，是以不能使用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

s[-1] = type; // 設定新的flags參數

sdssetlen(s, len); // 更新len

}

sdssetalloc(s, newlen); // 更新sds的容量

return s;

}

另外，Redis還提供了回收sds空餘空間的函數。

// 用來回收sds空餘空間，壓縮記憶體，函數調用後，s會無效

// 實際上，就是重新配置設定一塊記憶體，将原有資料拷貝到新記憶體上，并釋放原有空間

// 新記憶體的大小比原來小了alloc-len大小

sds sdsRemoveFreeSpace(sds s) {

void sh, newsh;

char type, oldtype = s[-1] & SDS_TYPE_MASK;

int hdrlen;

size_t len = sdslen(s); // 擷取字元串的實際大小

sh = (char)s-sdsHdrSize(oldtype);

type = sdsReqType(len);

hdrlen = sdsHdrSize(type);

if (oldtype==type) {

newsh = s_realloc(sh, hdrlen+len+1); // 申請的記憶體大小為hdrlen+len，原有的空餘空間不算

if (newsh == NULL) return NULL;

s = (char)newsh+hdrlen;

} 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;

}

sds連接配接操作函數

sds提供了字元串的連接配接函數，用來連接配接兩個字元串

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其他操作函數

sds還提供了一系列的操作函數，如下：

sds sdsempty(void); // 清空sds

sds sdsdup(const sds s); // 複制字元串

sds sdsgrowzero(sds s, size_t len); // 擴充字元串到指定長度

sds sdscpylen(sds s, const char *t, size_t len); // 字元串的複制

sds sdscpy(sds s, const char *t); // 字元串的複制

sds sdscatfmt(sds s, char const *fmt, …); //字元串格式化輸出

sds sdstrim(sds s, const char *cset); //字元串縮減

void sdsrange(sds s, int start, int end); //字元串截取函數

void sdsupdatelen(sds s); //更新字元串最新的長度

void sdsclear(sds s); //字元串清空操作

void sdstolower(sds s); //sds字元轉小寫表示

void sdstoupper(sds s); //sds字元統一轉大寫

sds sdsjoin(char **argv, int argc, char *sep); //以分隔符連接配接字元串子數組構成新的字元串

sds總結

sds

是

Redis

中最基本的資料結構，使用一整段連續的記憶體來存儲

sds

頭資訊和資料資訊。其中，字元串的

header

包括了

sds

的字元串長度，字元串的最大容量以及

sds

的類型這三種資訊。這三種基本的類型能夠簡化許多

sds

的操作，如字元串的長度隻需要O(1)即可，而strlen的O(N)好很多。

另外，

sds

還提供了很多的操作函數，在其擁有的

字元串的原生特性

之外，還能

動态擴充記憶體

和符合

二進制安全

等。

Redis設計與實作 redis源碼分析 sds簡介 sds記憶體布局 動态擴充記憶體 二進制安全
上一篇: 學習java基礎關鍵字之synchronized和volatile
下一篇: JDK1.8 HashMap源碼解析HashMap源碼解析

繼續閱讀