欧美一区二区在线看,精品99无码视频

本文作者： Pushy
本文鏈接： http://pushy.site/2019/12/21/redis-sds/
版權(quán)聲明：本博客所有文章除特別聲明外，均采用 CC BY-NC-SA 3.0 許可協(xié)議。轉(zhuǎn)載請注明出處！

1. 什么是 SDS

眾所周知，在 Redis 的五種數(shù)據(jù)解構(gòu)中，最簡單的就是字符串：

redis> set msg "Hello World"

而 Redis 并沒有直接使用 C 語言傳統(tǒng)的字符串表示，而是自己構(gòu)建了一個名為簡單動態(tài)字符串（Simple dynamic string，即 SDS）的抽象數(shù)據(jù)結(jié)構(gòu)。

執(zhí)行上面的 Redis 命令，在 Server 的數(shù)據(jù)庫中將創(chuàng)建一個鍵值對，即：

鍵為 “msg” 的 SDS；
值為 “Hello World” 的 SDS。

我們再來看下 SDS 的定義，在 Redis 的源碼目錄 sds.h 頭文件中，定義了 SDS 的結(jié)構(gòu)體：

struct sdshdr {
    // 記錄 buf 數(shù)組中當(dāng)前已使用的字節(jié)數(shù)量
    unsigned int len;
    // 記錄 buf 數(shù)組中空閑空間長度
    unsigned int free;
    // 字節(jié)數(shù)組
    char buf[];

};

可以看到，SDS 通過 len 和 free 屬性值來描述字節(jié)數(shù)組 buf 當(dāng)前的存儲狀況，這樣在之后的擴(kuò)展和其他操作中有很大的作用，還能以 O(1) 的復(fù)雜度獲取到字符串的長度（我們知道，C 自帶的字符串本身并不記錄長度信息，只能遍歷整個字符串統(tǒng)計(jì)）。

那么為什么 Redis 要自己實(shí)現(xiàn)一套字符串?dāng)?shù)據(jù)解構(gòu)呢？下面慢慢來研究！

2. SDS 的優(yōu)勢

杜絕緩沖區(qū)溢出

除了獲取字符串長度的復(fù)雜度為較高之外，C 字符串不記錄自身長度信息帶來的另一個問題就是容易造成內(nèi)存溢出。舉個例子，通過 C 內(nèi)置的 strcat 方法將字符串 motto 追加到 s1 字符串后邊：

void wrong_strcat() {
    char *s1, *s2;

    s1 = malloc(5 * sizeof(char));
    strcpy(s1, "Hello");
    s2 = malloc(5 * sizeof(char));
    strcpy(s2, "World");

    char *motto = " To be or not to be, this is a question.";
    s1 = strcat(s1, motto);

    printf("s1 = %s \n", s1);
    printf("s2 = %s \n", s2);
}

// s1 = Hello To be or not to be, this is a question. 
// s2 = s a question.

但是輸出卻出乎意料，我們只想修改 s1 字符串的值，而 s2 字符串也被修改了。這是因?yàn)?strcat 方法假定用戶在執(zhí)行前已經(jīng)為 s1 分配了足夠的內(nèi)存，可以容納 motto 字符串中的內(nèi)容。而一旦這個假設(shè)不成立，就會產(chǎn)生緩沖區(qū)溢出。

通過 Debug 我們看到，s1 變量內(nèi)存的初始位置為 94458843619936 （10進(jìn)制）， s2 初始位置為 94458843619968，是一段相鄰的內(nèi)存塊：

[圖片上傳失敗...(image-b46e0c-1577019474368)]

所以一旦通過 strcat 追加到 s1 的字符串 motto 的長度大于 s1 到 s2 的內(nèi)存地址間隔時，將會修改到 s2 變量的值。而正確的做法應(yīng)該是在 strcat 之前為 s1 重新調(diào)整內(nèi)存大小，這樣就不會修改 s2 變量的值了：

void correct_strcat() {
    char *s1, *s2;

    s1 = malloc(5 * sizeof(char));
    strcpy(s1, "Hello");
    s2 = malloc(5 * sizeof(char));
    strcpy(s2, "World");

    char *motto = " To be or not to be, this is a question.";
    // 為 s1 變量擴(kuò)展內(nèi)存，擴(kuò)展的內(nèi)存大小為 motto * sizeof(char) + 空字符結(jié)尾(1)
    s1 = realloc(s1, (strlen(motto) * sizeof(char)) + 1);
    s1 = strcat(s1, motto);

    printf("s1 = %s \n", s1);
    printf("s2 = %s \n", s2);
}

// s1 = Hello To be or not to be, this is a question. 
// s2 = World

可以看到，擴(kuò)容后的 s1 變量內(nèi)存地址起始位置變?yōu)榱?94806242149024（十進(jìn)制），s2 起始地址為 94806242148992。這時候 s1 與 s2 內(nèi)存地址的間隔大小已經(jīng)足夠 motto 字符串的存放了：

[圖片上傳失敗...(image-eca5dd-1577019474368)]

而與 C 字符串不同， SDS 的空間分配策略完全杜絕了發(fā)生緩沖區(qū)溢出的可能性，具體的實(shí)現(xiàn)在 sds.c 中。通過閱讀源碼，我們可以明白之所以 SDS 能杜絕緩沖區(qū)溢出是因?yàn)樵僬{(diào)用 sdsMakeRoomFor 時，會檢查 SDS 的空間是否滿足修改所需的要求（即 free >= addlen 條件），如果滿足 Redis 將會將 SDS 的空間擴(kuò)展至執(zhí)行所需的大小，在執(zhí)行實(shí)際的 concat 操作，這樣就避免了溢出發(fā)生：

// 與 C 語言 string.h/strcat 功能類似，其將一個 C 字符串追加到 sds
sds sdscat(sds s, const char *t) {
    return sdscatlen(s, t, strlen(t));
}

sds sdscatlen(sds s, const char *t, size_t len) {
    struct sdshdr *sh;
    size_t curlen = sdslen(s);  // 獲取 sds 的 len 屬性值

    s = sdsMakeRoomFor(s, len);
    if (s == NULL) return NULL;
    // 將 sds 轉(zhuǎn)換為 sdshdr，下邊會介紹
    sh = (void *) (s - sizeof(struct sdshdr));
    // 將字符串 t 復(fù)制到以 s+curlen 開始的內(nèi)存地址空間
    memcpy(s + curlen, t, len);
    sh->len = curlen + len;     // concat后的長度 = 原先的長度 + len
    sh->free = sh->free - len;  // concat后的free = 原來 free 空間大小 - len
    s[curlen + len] = '\0';     // 與 C 字符串一樣，都是以空字符 \0 結(jié)尾
    return s;
}

// 確保有足夠的空間容納加入的 C 字符串, 并且還會分配額外的未使用空間
// 這樣就杜絕了發(fā)生緩沖區(qū)溢出的可能性
sds sdsMakeRoomFor(sds s, size_t addlen) {
    struct sdshdr *sh, *newsh;
    size_t free = sdsavail(s);  // 當(dāng)前 free 空間大小
    size_t len, newlen;

    if (free >= addlen) {
        /* 如果空余空間足夠容納加入的 C 字符串大小, 則直接返回, 否則將執(zhí)行下邊的代碼進(jìn)行擴(kuò)展 buf 字節(jié)數(shù)組 */
        return s;
    }
    len = sdslen(s);  // 當(dāng)前已使用的字節(jié)數(shù)量
    sh = (void *) (s - (sizeof(struct sdshdr)));
    newlen = (len + addlen);  // 拼接后新的字節(jié)長度

    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;
    newsh = realloc(sh, sizeof(struct sdshdr) + newlen + 1);
    if (newsh == NULL) return NULL; // 申請內(nèi)存失敗

    /* 新的 sds 的空余空間 = 新的大小 - 拼接的 C 字符串大小 */
    newsh->free = newlen - len;
    return newsh->buf;
}

另外，在看源碼時我對 sh = (void *) (s - sizeof(struct sdshdr)); 一臉懵逼，如果不懂可以看：Redis（一）之 struct sdshdr sh = (void) (s-(sizeof(struct sdshdr)))講解

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

對于包含 N 個字符的 C 字符串來說，底層總是由 N+1 個連續(xù)內(nèi)存的數(shù)組來實(shí)現(xiàn)。由于存在這種關(guān)系，因此每次修改時，程序都需要對這個 C 字符串?dāng)?shù)組進(jìn)行一次內(nèi)存重分配操作：

如果是拼接操作：擴(kuò)展底層數(shù)組的大小，防止出現(xiàn)緩沖區(qū)溢出（前面提到的）；
如果是截?cái)嗖僮鳎盒枰尫挪皇褂玫膬?nèi)存空間，防止出現(xiàn)內(nèi)存泄漏。

Redis 作為頻繁被訪問修改的數(shù)據(jù)庫，為了減少修改字符帶來的內(nèi)存重分配的性能影響，SDS 也變得非常需要。因?yàn)樵?SDS 中，buf 數(shù)組的長度不一定就是字符串?dāng)?shù)量 + 1，可以包含未使用的字符，通過 free 屬性值記錄。通過未使用空間，SDS 實(shí)現(xiàn)了以下兩種優(yōu)化策略：

Ⅰ、空間預(yù)分配

空間預(yù)分配用于優(yōu)化 SDS 增長的操作：當(dāng)對 SDS 進(jìn)行修改時，并且需要對 SDS 進(jìn)行空間擴(kuò)展時，Redis 不僅會為 SDS 分配修改所必須的空間，還會對 SDS 分配額外的未使用空間。

在前面的 sdsMakeRoomFor 方法可以看到，額外分配的未使用空間數(shù)量存在兩種策略：

SDS 小于 SDS_MAX_PREALLOC：這時 len 屬性值將會和 free 屬性相等；
SDS 大于等于 SDS_MAX_PREALLOC：直接分配 SDS_MAX_PREALLOC 大小。

sds sdsMakeRoomFor(sds s, const char *t, size_t len) {
    ...
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;
    newsh = realloc(sh, sizeof(struct sdshdr) + newlen + 1);
    if (newsh == NULL) return NULL;
    newsh->free = newlen - len;
    return newsh->buf;
}

通過空間預(yù)分配策略，Redis 可以減少連續(xù)執(zhí)行字符串增長操作所需的內(nèi)存重分配次數(shù)。

Ⅱ、惰性空間釋放

惰性空間釋放用于優(yōu)化 SDS 字符串縮短操作，當(dāng)需要縮短 SDS 保存的字符串時，Redis 并不立即使用內(nèi)存重分配來回收縮短多出來的字節(jié)，而是使用 free 屬性將這些字節(jié)記錄起來，并等待來使用。

舉個例子，可以看到執(zhí)行完 sdstrim 并沒有立即回收釋放多出來的 22 字節(jié)的空間，而是通過 free 變量值保存起來。當(dāng)執(zhí)行 sdscat 時，先前所釋放的 22 字節(jié)的空間足夠容納追加的 C 字符串 11 字節(jié)的大小，也就不需要再進(jìn)行內(nèi)存空間擴(kuò)展重分配了。

#include "src/sds.h"

int main() {
    // sds{len = 32, free = 0, buf = "AA...AA.a.aa.aHelloWorld     :::"}
    s = sdsnew("AA...AA.a.aa.aHelloWorld     :::");  
    // sds{len = 10, free = 22, buf = "HelloWorld"}
    s = sdstrim(s, "Aa. :");  
    // sds{len = 21, free = 11, buf = "HelloWorld! I'm Redis"}
    s = sdscat(s, "! I'm Redis");   
    return 0;
}

通過惰性空間釋放策略，SDS 避免了縮短字符串時所需內(nèi)存重分配操作，并會將來可能增長操作提供優(yōu)化。與此同時，SDS 也有相應(yīng)的 API 真正地釋放 SDS 的未使用空間。

二進(jìn)制安全

C 字符串必須符合某種編碼，并且除了字符串的末尾之外，字符串不能包含空字符（\0）,否則會被誤認(rèn)為字符串的末尾。這些限制導(dǎo)致不能保存圖片、音頻等這種二進(jìn)制數(shù)據(jù)。

但是 Redis 就可以存儲二進(jìn)制數(shù)據(jù)，原因是因?yàn)?SDS 是使用 len 屬性值而不是空字符來判斷字符串是否結(jié)束的。

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

我們發(fā)現(xiàn)， SDS 的字節(jié)數(shù)組有和 C 字符串相似的地方，例如也是以 \0 結(jié)尾（但是不是以這個標(biāo)志作為字符串的結(jié)束）。這就使得 SDS 可以重用 <string.h> 庫定義的函數(shù)：

#include <stdio.h>
#include <strings.h>
#include "src/sds.h"

int main() {
    s = sdsnew("Cat");
    // 根據(jù)字符集比較大小
    int ret = strcasecmp(s, "Dog");
    printf("%d", ret);
    return 0;
}

3. 總結(jié)

看完 Redis 的 SDS 的實(shí)現(xiàn)，終于知道 Redis 只所以快，肯定和 epoll 的網(wǎng)絡(luò) I/O 模型分不開，但是也和底層優(yōu)化的簡單數(shù)據(jù)結(jié)構(gòu)分不開。

SDS 精妙之處在于通過 len 和 free 屬性值來協(xié)調(diào)字節(jié)數(shù)組的擴(kuò)展和伸縮，帶來了較比 C 字符串太多的性能更好的優(yōu)點(diǎn)。什么叫牛逼？這就牛逼！

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

Redis 動態(tài)字符串 SDS 源碼解析

Redis 動態(tài)字符串 SDS 源碼解析

1. 什么是 SDS

2. SDS 的優(yōu)勢

杜絕緩沖區(qū)溢出

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

二進(jìn)制安全

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

3. 總結(jié)

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

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

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

Redis 動態(tài)字符串 SDS 源碼解析

1. 什么是 SDS

2. SDS 的優(yōu)勢

杜絕緩沖區(qū)溢出

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

二進(jìn)制安全

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

3. 總結(jié)

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

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

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