1 簡單動態(tài)字符串

Redis是用C語言寫的，但是Redis的字符串不是 C 語言中的字符串（即以空字符’\0’結尾的字符數(shù)組）。Redis自己定義了一種名為簡單動態(tài)字符串（simple dynamic string,SDS）的抽象類型，并將SDS作為Redis的默認字符串表示。
SDS的定義在sds.h中：

/* 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由4部分組成:
len:SDS字符串已經(jīng)使用的空間（不包含C中字符串的結束符'\0'的長度1）。
alloc:申請的空間大小，減去len就是未使用的空間，初始時和len相等。
flags:使用低三位表示類型，細分SDS的分類。方便根據(jù)字符串的長度不同選擇不用的SDS結構體，節(jié)省一部分空間。
buf:使用C的不定長字符串。

從SDS的定義上看，5種定義對應了最大長度不同的字符串。定義這5種不同的類型是為了盡量減少sdshdr占用的空間。
為了區(qū)分sdshdr屬于哪一種類型，在每一種定義中都加上了一個8bit的flags字段，用其中的低3位標識sdshdr的類型。
在C/C++中，建立一個結構體時，會進行字節(jié)對齊操作，使得結構體的大小比其變量占用的字節(jié)要多一些。為了能從buf直接找到到flags，定義時在結構體聲明中加上__attribute__((__packed__))，強制不要按字節(jié)對齊(表示取消字節(jié)對齊，按照緊湊排列的方式)，這樣不管是哪種類型的hdr，都可以用buf[-1]找到對應的flags。

2 SDS與C字符串的區(qū)別

C語言使用長度為N+1的字符串數(shù)組來表示長度為N的字符串；字符串數(shù)組的最后一個元素一定是'\0'。C語言的這種表示字符串的方式，并不能滿足Redis對字符串在安全性、功能性以及效率性的要求。
使用SDS除了用C語言中的字符串數(shù)組buf[]表示了字符串的內(nèi)容，還記錄了Redis為該字符串分配的buf空間的總長度alloc、buf[]中已經(jīng)使用的長度len。Redis使用SDS有以下幾個好處。

2.1 常數(shù)復雜度獲取字符串長度

由于存在len屬性，獲取SDS字符串的長度只需要讀取len屬性，時間復雜度為O(1)。而對于 C 語言，獲取字符串的長度通常是經(jīng)過遍歷計數(shù)來實現(xiàn)的，時間復雜度為O(n)。通過strlen key命令獲取key的字符串長度的時間復雜度為O(1)，可以反復執(zhí)行而不會出現(xiàn)性能瓶頸。

2.2 杜絕緩沖區(qū)溢出

在 C 語言中使用strcat函數(shù)來進行兩個字符串的拼接，一旦沒有分配足夠長度的內(nèi)存空間，就會造成緩沖區(qū)溢出。而對于 SDS 數(shù)據(jù)類型，在進行字符修改的時候，會首先根據(jù)記錄的len屬性檢查內(nèi)存空間是否滿足需求，如果不滿足，會進行相應的空間擴展，然后在進行修改操作，所以不會出現(xiàn)緩沖區(qū)溢出。

2.3 減少修改字符串的內(nèi)存重新分配次數(shù)

C語言由于不記錄字符串的長度，所以如果要修改字符串，必須要重新分配內(nèi)存（先釋放再申請），因為如果沒有重新分配，字符串長度增大時會造成內(nèi)存緩沖區(qū)溢出，字符串長度減小時會造成內(nèi)存泄露。
　　而對于SDS，由于len屬性和alloc屬性的存在，對于修改字符串SDS實現(xiàn)了空間預分配和惰性空間釋放兩種策略：

空間預分配
對字符串進行空間擴展的時候，擴展的內(nèi)存比實際需要的多，這樣可以減少連續(xù)執(zhí)行字符串增長操作所需的內(nèi)存重分配次數(shù)。
額外分配空間策略：

1.1. 如果SDS修改之后，SDS的長度(len屬性的值)將小于1MB(1024*1024 Byte)，那么程序?qū)⒎峙浜蚻en屬性相同的大小的未使用空間，分配之后，alloc=len2。
示例：
SDS當前的長度len為6，alloc為12。此時執(zhí)行append方法，在后面追加hello redis!*字符串，修改之后的長度len將變成18。修改之后，SDS的len為18，同時分配18Byte的未使用空間，alloc為36。最終，buf[]的實際長度將變成alloc+1Byte=36Byte+1Byte(1Byte用于保存空字符'\0')=37Byte。
1.2 如果SDS進行修改之后，SDS的長度將大于等于1MB(1024*1024 Byte)，那么程序會分配1MB的未使用空間。
示例：
SDS當前長度為0，len=0,alloc=0。此時執(zhí)行set方法，字符串長度為2MB。那么執(zhí)行之后，len=2*1024*1024,alloc=len+1024*1024=3*1024*1024，buf[]的實際長度為：2MB+1MB+1Byte。
0sds.h中:

#define SDS_MAX_PREALLOC (1024*1024)

sds.c中

    newlen = (len+addlen);
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;

惰性空間釋放
對字符串進行縮短操作時，程序不立即使用內(nèi)存重新分配來回收縮短后多余的字節(jié)，而是使用alloc屬性將所有字節(jié)的數(shù)量記錄下來，等待后續(xù)使用（當然SDS也提供了相應的API，當我們有需要時，也可以手動釋放這些未使用的空間）。

2.4 二進制安全

因為C字符串以空字符作為字符串結束的標識，而對于一些二進制文件（如圖片、音頻、視頻、壓縮文件等），內(nèi)容可能包括空字符串，因此C字符串無法正確存??；而所有 SDS 的API 都是以處理二進制的方式來處理 buf 里面的元素，并且 SDS 不是以空字符串來判斷是否結束，而是以 len 屬性表示的長度來判斷字符串是否結束，因此SDS是二進制安全的。Redis的buf[]是字節(jié)數(shù)組，因為buf[]不是用于保存字符，而是保存一系列二進制數(shù)據(jù)。Redis使用二進制安全的SDS，可以保存任意格式的二進制數(shù)據(jù)。

2.5 兼容部分 C 字符串函數(shù)

雖然 SDS 是二進制安全的，但是一樣遵從每個字符串都是以空字符串結尾的慣例，這樣可以重用 C 語言庫<string.h> 中的一部分函數(shù)，避免了不必要的代碼重復。

綜上，用下面表格總結C字符串和SDS之間的區(qū)別。

C字符串	SDS
獲取字符串長度的復雜度為*O(N)*	獲取字符串長度的復雜度為*O(1)*
API是不安全的，可能會造成緩沖區(qū)溢出	API是安全的，不會造成緩沖區(qū)溢出
修改字符串長度N次需要執(zhí)行N次的內(nèi)存重分配	修改字符串長度N次最多需要執(zhí)行N次的內(nèi)存重分配
空字符'\0'作為文本數(shù)據(jù)的結束，只能保存文本數(shù)據(jù)	二進制安全，可以保存文本數(shù)據(jù)和所有格式的二進制數(shù)據(jù)
可以使用所有的C語言庫中的函數(shù)，如`<string.h>/strcasecmp`	可以使用部分C語言庫中的函數(shù)，如`<string.h>/strcasecmp`

3 SDS常用API

SDS常用API和常量定義。此處不詳細解釋，基本都可以根據(jù)函數(shù)名知道函數(shù)功能。
詳細參考Redis的sds.h源碼和sds.h的實現(xiàn)sds.c源碼。

#ifndef __SDS_H
#define __SDS_H

#define SDS_MAX_PREALLOC (1024*1024)
const char *SDS_NOINIT;

#include <sys/types.h>
#include <stdarg.h>
#include <stdint.h>

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

#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
#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))))
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)

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

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;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            return sh->alloc - sh->len;
        }
    }
    return 0;
}

static inline void sdssetlen(sds s, size_t newlen) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            {
                unsigned char *fp = ((unsigned char*)s)-1;
                *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
            }
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->len = newlen;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->len = newlen;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->len = newlen;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->len = newlen;
            break;
    }
}

static inline void sdsinclen(sds s, size_t inc) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            {
                unsigned char *fp = ((unsigned char*)s)-1;
                unsigned char newlen = SDS_TYPE_5_LEN(flags)+inc;
                *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
            }
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->len += inc;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->len += inc;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->len += inc;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->len += inc;
            break;
    }
}

/* sdsalloc() = sdsavail() + sdslen() */
static inline size_t sdsalloc(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)->alloc;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->alloc;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->alloc;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->alloc;
    }
    return 0;
}

static inline void sdssetalloc(sds s, size_t newlen) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            /* Nothing to do, this type has no total allocation info. */
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->alloc = newlen;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->alloc = newlen;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->alloc = newlen;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->alloc = newlen;
            break;
    }
}

sds sdsnewlen(const void *init, size_t initlen);
sds sdsnew(const char *init);
sds sdsempty(void);
sds sdsdup(const sds s);
void sdsfree(sds s);
sds sdsgrowzero(sds s, size_t len);
sds sdscatlen(sds s, const void *t, size_t len);
sds sdscat(sds s, const char *t);
sds sdscatsds(sds s, const sds t);
sds sdscpylen(sds s, const char *t, size_t len);
sds sdscpy(sds s, const char *t);

sds sdscatvprintf(sds s, const char *fmt, va_list ap);
#ifdef __GNUC__
sds sdscatprintf(sds s, const char *fmt, ...)
    __attribute__((format(printf, 2, 3)));
#else
sds sdscatprintf(sds s, const char *fmt, ...);
#endif

sds sdscatfmt(sds s, char const *fmt, ...);
sds sdstrim(sds s, const char *cset);
void sdsrange(sds s, ssize_t start, ssize_t end);
void sdsupdatelen(sds s);
void sdsclear(sds s);
int sdscmp(const sds s1, const sds s2);
sds *sdssplitlen(const char *s, ssize_t len, const char *sep, int seplen, int *count);
void sdsfreesplitres(sds *tokens, int count);
void sdstolower(sds s);
void sdstoupper(sds s);
sds sdsfromlonglong(long long value);
sds sdscatrepr(sds s, const char *p, size_t len);
sds *sdssplitargs(const char *line, int *argc);
sds sdsmapchars(sds s, const char *from, const char *to, size_t setlen);
sds sdsjoin(char **argv, int argc, char *sep);
sds sdsjoinsds(sds *argv, int argc, const char *sep, size_t seplen);

/* Low level functions exposed to the user API */
sds sdsMakeRoomFor(sds s, size_t addlen);
void sdsIncrLen(sds s, ssize_t incr);
sds sdsRemoveFreeSpace(sds s);
size_t sdsAllocSize(sds s);
void *sdsAllocPtr(sds s);

/* Export the allocator used by SDS to the program using SDS.
 * Sometimes the program SDS is linked to, may use a different set of
 * allocators, but may want to allocate or free things that SDS will
 * respectively free or allocate. */
void *sds_malloc(size_t size);
void *sds_realloc(void *ptr, size_t size);
void sds_free(void *ptr);

#ifdef REDIS_TEST
int sdsTest(int argc, char *argv[]);
#endif

#endif

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

Redis5.x底層數(shù)據(jù)結構之——字符串

Redis5.x底層數(shù)據(jù)結構之——字符串

1 簡單動態(tài)字符串

2 SDS與C字符串的區(qū)別

2.1 常數(shù)復雜度獲取字符串長度

2.2 杜絕緩沖區(qū)溢出

2.3 減少修改字符串的內(nèi)存重新分配次數(shù)

2.4 二進制安全

2.5 兼容部分 C 字符串函數(shù)

3 SDS常用API

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

Redis5.x底層數(shù)據(jù)結構之——字符串

1 簡單動態(tài)字符串

2 SDS與C字符串的區(qū)別

2.1 常數(shù)復雜度獲取字符串長度

2.2 杜絕緩沖區(qū)溢出

2.3 減少修改字符串的內(nèi)存重新分配次數(shù)

2.4 二進制安全

2.5 兼容部分 C 字符串函數(shù)

3 SDS常用API

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av