欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Redis源碼解析sds字符串實(shí)現(xiàn)示例

 更新時(shí)間:2023年08月02日 14:40:55   作者:hoohack  
這篇文章主要為大家介紹了Redis源碼解析sds字符串實(shí)現(xiàn)示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪

初衷

從開始工作就開始使用Redis,也有一段時(shí)間了,但都只是停留在使用階段,沒有往更深的角度探索,每次想讀源碼都止步在閱讀書籍上,因?yàn)榭赐陼芸煊滞?,這次逼自己先讀代碼。因?yàn)閭€(gè)人覺得寫作需要閱讀文字來增強(qiáng)靈感,那么寫代碼的,就閱讀更多代碼來增強(qiáng)靈感吧。

redis的實(shí)現(xiàn)原理,在《Redis設(shè)計(jì)與實(shí)現(xiàn)》一書中講得很詳細(xì)了,但是想通過結(jié)合代碼的形式再深入探索,加深自己的理解,現(xiàn)在將自己探索的心得寫在這兒。

sds結(jié)構(gòu)體的定義

#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
// sds結(jié)構(gòu)體,使用不同的結(jié)構(gòu)體來保存不同長度大小的字符串
typedef char *sds;
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* flags共8位,低三位保存類型標(biāo)志,高5位保存字符串長度,小于32(2^5-1) */
    char buf[]; // 保存具體的字符串
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* 字符串長度,buf已用的長度 */
    uint8_t alloc; /* 為buf分配的總長度,alloc-len就是sds結(jié)構(gòu)體剩余的空間 */
    unsigned char flags; /* 低三位保存類型標(biāo)志 */
    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結(jié)構(gòu)體從4.0開始就使用了5種header定義,節(jié)省內(nèi)存的使用,但是不會(huì)用到sdshdr5,我認(rèn)為是因?yàn)閟dshdr5能保存的大小較少,2^5=32,因此就不使用它。

其他的結(jié)構(gòu)體保存了len、alloc、flags以及buf四個(gè)屬性。各自的含義見代碼的注釋。

sds結(jié)構(gòu)體的獲取

上面可以看到有5種結(jié)構(gòu)體的定義,在使用的時(shí)候是通過一個(gè)宏來獲取的:

#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))

"##"被稱為連接符,它是一種預(yù)處理運(yùn)算符, 用來把兩個(gè)語言符號(hào)(Token)組合成單個(gè)語言符號(hào)。比如SDS_HDR(8, s),根據(jù)宏定義展開是:

((struct sdshdr8 *)((s)-(sizeof(struct sdshdr8))))

而具體使用哪一個(gè)結(jié)構(gòu)體,sds底層是通過flags屬性與SDS_TYPE_MASK做與運(yùn)算得出具體的類型(具體的實(shí)現(xiàn)可見下面的sdslen函數(shù)),然后再根據(jù)類型去獲取具體的結(jié)構(gòu)體。

sds特性的實(shí)現(xiàn)

在Redis設(shè)計(jì)與實(shí)現(xiàn)一書中講到,相比C字符串而言,sds的特性如下:

  • 常數(shù)復(fù)雜度獲取字符串長度
  • 杜絕緩沖區(qū)溢出
  • 減少內(nèi)存重新分配次數(shù)
  • 二進(jìn)制安全

那么,它是怎么做到的呢?看代碼。

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

因?yàn)閟ds將長度屬性保存在結(jié)構(gòu)體中,所以只需要讀取這個(gè)屬性就能獲取到sds的長度,具體調(diào)用的函數(shù)時(shí)sdslen,實(shí)現(xiàn)如下:

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

可以看到,函數(shù)是根據(jù)類型調(diào)用SDS_HDR宏來獲取具體的sds結(jié)構(gòu),然后直接返回結(jié)構(gòu)體的len屬性。

杜絕緩沖區(qū)溢出

對(duì)于C字符串的操作函數(shù)來說,如果在修改字符串的時(shí)候忘了為字符串分配足夠的空間,就有可能出現(xiàn)緩沖區(qū)溢出的情況。而sds中的API就不會(huì)出現(xiàn)這種情況,因?yàn)樗谛薷膕ds之前,都會(huì)判斷它是否有足夠的空間完成接下來的操作。

拿書中舉例的sdscat函數(shù)來看,如果strcat想在原來的"Redis"字符串的基礎(chǔ)上進(jìn)行字符串拼接的操作,但是沒有檢查空間是否滿足,就有可能會(huì)修改了"Redis"字符串之后使用到的內(nèi)存,可能是其他結(jié)構(gòu)使用了,也有可能是一段沒有被使用的空間,因此有可能會(huì)出現(xiàn)緩沖區(qū)溢出。但是sdscat就不會(huì),如下面代碼所示:

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 sdscat(sds s, const char *t) {
    return sdscatlen(s, t, strlen(t));
}

從代碼中可以看到,在執(zhí)行memcpy將字符串寫入sds之前會(huì)調(diào)用sdsMakeRoomFor函數(shù)去檢查sds字符串s是否有足夠的空間,如果沒有足夠空間,就為其分配足夠的空間,從而杜絕了緩沖區(qū)溢出。sdsMakeRoomFor函數(shù)的實(shí)現(xiàn)如下:

sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    size_t avail = sdsavail(s);
    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;
    /* 只有有足夠空間就馬上返回,否則就繼續(xù)執(zhí)行分配空間的操作 */
    if (avail >= addlen) return s;
    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    // SDS_MAX_PREALLOC == 1MB,如果修改后的長度小于1M,則分配的空間是原來的2倍,否則增加1MB的空間
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;
    type = sdsReqType(newlen);
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;
    hdrlen = sdsHdrSize(type);
    if (oldtype==type) {
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        /* 新增空間后超過當(dāng)前類型的長度,使用malloc,并把原字符串拷貝過去 */
        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; // 給類型標(biāo)志位賦值
        sdssetlen(s, len);
    }
    sdssetalloc(s, newlen);
    return s;
}

減少內(nèi)存分配操作

sds字符串的很多操作都涉及到修改字符串內(nèi)容,比如sdscat拼接字符串、sdscpy拷貝字符串等等。這時(shí)候就需要內(nèi)存的分配與釋放,如果每次操作都分配剛剛好的大小,那么對(duì)程序的性能必定有影響,因?yàn)閮?nèi)存分配涉及到系統(tǒng)調(diào)用以及一些復(fù)雜的算法。

sds使用了空間預(yù)分配以及惰性空間釋放的策略來減少內(nèi)存分配操作。

空間預(yù)分配

前面提到,每次涉及到字符串的修改時(shí),都會(huì)調(diào)用sdsMakeRoomFor檢查sds字符串,如果大小不夠再進(jìn)行大小的重新分配。sdsMakeRoomFor函數(shù)有下面這幾行判斷:

// SDS_MAX_PREALLOC == 1MB,如果修改后的長度小于1M,則分配的空間是原來的2倍,否則增加1MB的空間
if (newlen < SDS_MAX_PREALLOC)
    newlen *= 2;
else
    newlen += SDS_MAX_PREALLOC;

函數(shù)判斷字符串修改后的大小,如果修改后的長度小于1M,則分配給sds的空間是原來的2倍,否則增加1MB的空間。

惰性空間釋放

如果操作后減少了字符串的大小,比如下面的sdstrim函數(shù),只是在最后修改len屬性,不會(huì)馬上釋放多余的空間,而是繼續(xù)保留多余的空間,這樣在下次需要增加sds字符串的大小時(shí),就不需要再為其分配空間了。當(dāng)然,如果之后檢查到sds的大小實(shí)在太大,也會(huì)調(diào)用sdsRemoveFreeSpace函數(shù)釋放多余的空間。

sds sdstrim(sds s, const char *cset) {
    char *start, *end, *sp, *ep;
    size_t len;
    sp = start = s;
    ep = end = s+sdslen(s)-1;
    /* 從頭部和尾部逐個(gè)字符遍歷往中間靠攏,如果字符在cest中,則繼續(xù)前進(jìn) */
    while(sp <= end && strchr(cset, *sp)) sp++;
    while(ep > sp && strchr(cset, *ep)) ep--;
    len = (sp > ep) ? 0 : ((ep-sp)+1); // 全部被去除了,長度就是0
    if (s != sp) memmove(s, sp, len); // 拷貝內(nèi)容
    s[len] = '\0';
    sdssetlen(s,len);
    return s;
}

二進(jìn)制安全

二進(jìn)制安全指的是只關(guān)心二進(jìn)制化的字符串,不關(guān)心具體格式。只會(huì)嚴(yán)格的按照二進(jìn)制的數(shù)據(jù)存取,不會(huì)妄圖以某種特殊格式解析數(shù)據(jù)。比如遇到'0'字符不會(huì)停止解析。

對(duì)于C字符串來說,strlen是判斷遇到'0'之前的字符數(shù)量。如果需要保存二進(jìn)制的數(shù)據(jù),就不能通過傳統(tǒng)的C字符串來保存,因?yàn)楂@取不到它真實(shí)的長度。而sds字符串是通過len屬性保存字符串的大小,所以它是二進(jìn)制安全的。

其他小函數(shù)實(shí)現(xiàn)

在閱讀源碼的過程中,也發(fā)現(xiàn)了兩個(gè)個(gè)人比較感興趣趣的函數(shù):

sdsll2str(將long long類型的整型數(shù)字轉(zhuǎn)成字符串)

sdstrim (去除頭部和尾部的指定字符)

我這兩個(gè)函數(shù)拉出來做了測(cè)試,在項(xiàng)目的redis-4.0/tests目錄下。sdstrim函數(shù)的實(shí)現(xiàn)源碼上面有列出,看看sdsll2str的實(shí)現(xiàn):

int sdsll2str(char *s, long long value) {
    char *p, aux;
    unsigned long long v;
    size_t l;
    /* 通過取余數(shù)得到原字符串的逆轉(zhuǎn)形式 */
    v = (value < 0) ? -value : value;
    p = s;
    do {
        *p++ = '0'+(v%10);
        v /= 10;
    } while(v);
    if (value < 0) *p++ = '-';
    /* Compute length and add null term. */
    l = p-s;
    *p = '\0';
    /* 反轉(zhuǎn)字符串 */
    p--;
    while(s < p) {
        aux = *s;
        *s = *p;
        *p = aux;
        s++;
        p--;
    }
    return l;
}

函數(shù)是通過不斷取余數(shù),得到原字符串的逆轉(zhuǎn)形式,接著,通過從尾部開始將字符逐個(gè)放到字符串s中,看起來像是一個(gè)反轉(zhuǎn)操作,從而實(shí)現(xiàn)了將整型轉(zhuǎn)為字符串的操作。

覺得感興趣是因?yàn)?code>sdsll2str這個(gè)函數(shù)在之前學(xué)習(xí)C語言的時(shí)候經(jīng)常能看到作為問題出現(xiàn),能看到如此簡潔的實(shí)現(xiàn),表示眼前一亮。而在PHP開發(fā)時(shí)經(jīng)常使用trim函數(shù),所以想看看它們的區(qū)別。

總結(jié)

通過詳細(xì)地閱讀sds的源碼,不僅學(xué)習(xí)到sds的實(shí)現(xiàn)細(xì)節(jié),還學(xué)習(xí)到了一些常用字符串操作函數(shù)的實(shí)現(xiàn)。如果只是僅僅看看數(shù)據(jù)結(jié)構(gòu)的定義也可以初步了解,但是要深入了解的話還是需要詳細(xì)的閱讀具體函數(shù)的實(shí)現(xiàn)代碼。還是那句,寫代碼的,需要閱讀更多代碼來增強(qiáng)靈感。

我在github有對(duì)Redis源碼更詳細(xì)的注解 Redis4.0源碼注解。

可以通過commit記錄查看已添加的注解。

以上就是Redis源碼解析sds字符串實(shí)現(xiàn)示例的詳細(xì)內(nèi)容,更多關(guān)于Redis sds字符串的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

  • Redis全量同步和增量同步原理

    Redis全量同步和增量同步原理

    主從第一次同步是全量同步:也就是說,當(dāng)你主從節(jié)點(diǎn)連接建立后,需要執(zhí)行一次全量同步,但如果slave重啟后同步,此時(shí)slave重啟后,slave節(jié)點(diǎn)和master節(jié)點(diǎn)的數(shù)據(jù)之間有落后,因此需要進(jìn)行增量同步,感興趣的同學(xué)可以參考閱讀
    2023-04-04
  • Redis系列之底層數(shù)據(jù)結(jié)構(gòu)SDS詳解

    Redis系列之底層數(shù)據(jù)結(jié)構(gòu)SDS詳解

    SDS(簡單動(dòng)態(tài)字符串)是Redis使用的核心數(shù)據(jù)結(jié)構(gòu),用于替代C語言的字符串,以解決長度獲取慢、內(nèi)存溢出等問題,SDS通過預(yù)分配與惰性釋放策略優(yōu)化內(nèi)存使用,增強(qiáng)安全性,且能存儲(chǔ)文本與二進(jìn)制數(shù)據(jù),可查看源碼src/sds.h和src/sds.c了解更多
    2024-11-11
  • Redis鎖完美解決高并發(fā)秒殺問題

    Redis鎖完美解決高并發(fā)秒殺問題

    本文主要介紹了Redis鎖完美解決高并發(fā)秒殺問題,文中通過示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-09-09
  • Linux 下redis5.0.0安裝教程詳解

    Linux 下redis5.0.0安裝教程詳解

    這篇文章主要介紹了Linux 下redis5.0.0安裝教程,本文圖文并茂給大家介紹的非常詳細(xì),具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2019-10-10
  • 虛擬機(jī)linux安裝redis實(shí)現(xiàn)過程解析

    虛擬機(jī)linux安裝redis實(shí)現(xiàn)過程解析

    這篇文章主要介紹了虛擬機(jī)linux安裝redis實(shí)現(xiàn)過程解析,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-08-08
  • Redis實(shí)現(xiàn)登錄注冊(cè)的示例代碼

    Redis實(shí)現(xiàn)登錄注冊(cè)的示例代碼

    本文主要介紹了Redis實(shí)現(xiàn)登錄注冊(cè)的示例代碼,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2022-06-06
  • Redis連接錯(cuò)誤的情況總結(jié)分析

    Redis連接錯(cuò)誤的情況總結(jié)分析

    這篇文章主要給大家總結(jié)介紹了關(guān)于Redis連接錯(cuò)誤的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧
    2019-02-02
  • redis緩存穿透解決方法

    redis緩存穿透解決方法

    在本篇文章里小編給大家分享了關(guān)于redis緩存穿透的解決方法以及相關(guān)實(shí)例內(nèi)容,需要的朋友們學(xué)習(xí)下。
    2019-06-06
  • 解決redis修改requirepass后不生效的問題

    解決redis修改requirepass后不生效的問題

    今天小編就為大家分享一篇解決redis修改requirepass后不生效的問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
    2018-05-05
  • 基于Redis驗(yàn)證碼發(fā)送及校驗(yàn)方案實(shí)現(xiàn)

    基于Redis驗(yàn)證碼發(fā)送及校驗(yàn)方案實(shí)現(xiàn)

    本文主要介紹了基于Redis驗(yàn)證碼發(fā)送及校驗(yàn)方案實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-01-01

最新評(píng)論