97视频在线观看免费,99riav在线,中文字幕在线高清蜜臀

眾所周知，redis對(duì)外支持五種數(shù)據(jù)結(jié)構(gòu)：string、hash、list、set、sorted set。而在內(nèi)部實(shí)現(xiàn)中，則主要依賴(lài)于如下七種數(shù)據(jù)結(jié)構(gòu)：

SDS（simple dynamic string）：簡(jiǎn)單動(dòng)態(tài)字符串
ADList（a generic doubly linked list）：雙向鏈表
dict（Hash Tables）：字典
intset：整數(shù)集合
ziplist：壓縮表
quickList：快速列表
skipList：跳躍鏈表

在上述七種數(shù)據(jù)結(jié)構(gòu)中，本文主要就SDS進(jìn)行簡(jiǎn)單的討論。在redis的實(shí)現(xiàn)代碼中，SDS有著非常廣泛的使用。實(shí)際上，C語(yǔ)言字符串（也就是字符指針char*）僅被用于一些無(wú)需對(duì)字符串的值進(jìn)行修改的地方，比如日志。其他位置的實(shí)現(xiàn)，比如對(duì)外暴露的string數(shù)據(jù)結(jié)構(gòu)、AOF的緩沖區(qū)、客戶(hù)端狀態(tài)的輸入緩沖區(qū)，都在廣泛使用SDS。如今，SDS目前已被獨(dú)立出來(lái)成了一個(gè)單獨(dú)的項(xiàng)目，鏈接在此：https://github.com/antirez/sds。

數(shù)據(jù)結(jié)構(gòu)

首先，先來(lái)了解下SDS這種數(shù)據(jù)結(jié)構(gòu)的的基本實(shí)現(xiàn)。
在redis的3.2版本，SDS的實(shí)現(xiàn)有了比較大的改動(dòng)，不過(guò)對(duì)于理解其數(shù)據(jù)結(jié)構(gòu)影響不大。
由于3.2之前的版本實(shí)現(xiàn)比較簡(jiǎn)單，所以這里以此為例進(jìn)行分析，在最后會(huì)針對(duì)3.2前后的改動(dòng)進(jìn)行詳細(xì)說(shuō)明。

typedef char *sds
struct sdschar {
    // buf[] 中已使用的字節(jié)數(shù)
    int len;
    // buf[] 中未使用的字節(jié)數(shù)
    int free;
    // 字符數(shù)組，用于實(shí)際存儲(chǔ)字符串內(nèi)容
    char buf[];
}

如圖中注釋所示，在SDS中，并不是需要多少字節(jié)，就去申請(qǐng)多大的空間，而是會(huì)多申請(qǐng)一部分空間留以備用。舉個(gè)簡(jiǎn)單的例子，假設(shè)現(xiàn)在要存儲(chǔ)一個(gè)字符串“redis”，那么是用傳統(tǒng)的C語(yǔ)言字符串實(shí)現(xiàn)的話，其存儲(chǔ)示意圖如下：

而對(duì)于sds而言，其存儲(chǔ)就可能是這樣：

與char*的比較

很顯然，SDS相比于使用char*，在某些方面是具有一定的優(yōu)勢(shì)的，而其中優(yōu)勢(shì)則主要集中于如下幾個(gè)方面：

能夠以O(shè)(1)時(shí)間復(fù)雜度來(lái)獲取字符串的長(zhǎng)度

由于C語(yǔ)言字符串，在實(shí)現(xiàn)上僅僅是一個(gè)char指針，指向字符串對(duì)應(yīng)內(nèi)存的頭部，并不會(huì)記錄自身的長(zhǎng)度信息。所以每次需要獲取其長(zhǎng)度時(shí)，比如從字符串開(kāi)始位置，一直往后遍歷，直到遇到代表字符串結(jié)尾的終結(jié)符（也就是”\0”）。自然，這個(gè)操作的時(shí)間復(fù)雜度時(shí)O(n)。
而對(duì)于SDS，自身記錄了兩個(gè)int數(shù)據(jù)：已經(jīng)使用的字節(jié)數(shù)（len）和未使用的字節(jié)數(shù)（free）。所以，在需要時(shí)，只需要將代表已經(jīng)使用字節(jié)數(shù)的len數(shù)據(jù)返回即可，時(shí)間復(fù)雜度自然是O(1)。
不過(guò)，要注意，這里的len不會(huì)計(jì)算”\0”所占用的空間（與C語(yǔ)言保持一致）。

避免緩沖區(qū)溢出

這里，先來(lái)了解一下什么是緩沖區(qū)溢出。而在此之前，先來(lái)看一個(gè)例子。
假設(shè)有兩個(gè)字符串s1和s2，其在內(nèi)存中的存儲(chǔ)位置相鄰，如下圖所示：

這時(shí)候，如果想在s1后面追加一段數(shù)據(jù)，比如追加“ Cluster”，正確的操作應(yīng)該是：
第一步：申請(qǐng)足夠的空間
第二步：執(zhí)行strcat(s1, “ Cluster”);
但是，假設(shè)忘記執(zhí)行第一步，直接進(jìn)行第二步操作，這時(shí)新的字符“ Cluster”將會(huì)直接寫(xiě)在s1字符串的末尾位置，也就是將抹掉s2的部分?jǐn)?shù)據(jù)。此時(shí)內(nèi)存中的數(shù)據(jù)將變成下圖的樣子：

這種現(xiàn)象就被稱(chēng)為緩沖區(qū)溢出。而假如此時(shí)取出s2的數(shù)據(jù)，將會(huì)得到錯(cuò)誤的字符串“Cluster”，而不是原先的“MongoDB”。
而對(duì)于SDS而言，作者專(zhuān)門(mén)封裝了一個(gè)類(lèi)似于strcat的方法：sdscatlen，作用正是對(duì)SDS進(jìn)行字符串拼接，具體實(shí)現(xiàn)代碼如下：

sds sdscatlen(sds s, const void *t, size_t len) {
    struct sdshdr *sh;
    size_t curlen = sdslen(s); // 獲取當(dāng)前已用的長(zhǎng)度（就是直接返回sds數(shù)據(jù)結(jié)構(gòu)中的len字段）

    s = sdsMakeRoomFor(s,len); // 判斷是否要擴(kuò)容，如果需要，執(zhí)行擴(kuò)容操作
    if (s == NULL) return NULL;
    sh = (void*) (s-sizeof *sh);;
    memcpy(s+curlen, t, len);
    sh->len = curlen+len; // 修改len字段
    sh->free = sh->free-len; // 修改free字段
    s[curlen+len] = '\0'; // 填充終結(jié)字符"\0"
    return s;    
}

如圖中注釋所述，SDS在長(zhǎng)度發(fā)生變化時(shí)，會(huì)自動(dòng)檢測(cè)是否需要進(jìn)行擴(kuò)容，這就規(guī)避了上文示例中緩沖區(qū)溢出的風(fēng)險(xiǎn)。這便是SDS的一大特點(diǎn)：可自主擴(kuò)容，不需要使用者關(guān)心空間的申請(qǐng)。
在上面的代碼中，有一個(gè)比較重要的函數(shù)：sdsMakeRoomFor，其實(shí)現(xiàn)代碼如下：

sds sdsMakeRoomFor(sds s, size_t addlen) {
    struct sdshdr *sh, *newsh;
    size_t free = sdsavail(s); // 獲取未使用的字節(jié)數(shù)（就是直接返回sds數(shù)據(jù)結(jié)構(gòu)中的free字段）
    size_t len, newlen;

    if (free >= addlen) return s; // 如果free還夠用，直接返回
    len = sdslen(s);
    sh = (void*) (s-sizeof *sh);;
    newlen = (len+addlen);
    if (newlen < SDS_MAX_PREALLOC) // SDS_MAX_PREALLOC的值為 1024*1024，也就是1M
        newlen *= 2; // 如果追加新字符串后，長(zhǎng)度小于1M，則直接申請(qǐng)兩倍的空間備用
    else
        newlen += SDS_MAX_PREALLOC; // 如果追加新字符串之后，長(zhǎng)度大于1M，則多申請(qǐng)1M備用
    newsh = realloc(sh, sizeof *newsh+newlen+1);
    if (newsh == NULL) return NULL;

    newsh->free = newlen - len; // 因?yàn)檫@時(shí)候還沒(méi)有做實(shí)際的字符串追加，所以 free = newlen - len
    return newsh->buf;
}

可以看到，這里規(guī)定了SDS的擴(kuò)容規(guī)則：如果新字符串長(zhǎng)度小于1M，申請(qǐng)雙倍空間，如果新字符串長(zhǎng)度大于1M，則只會(huì)多申請(qǐng)1M。

減少字符串變更帶來(lái)的內(nèi)存重分配次數(shù)

首先解釋一下C語(yǔ)言中字符串變更引發(fā)的內(nèi)存重分配行為：
如上文所述，在C語(yǔ)言中，字符串是不會(huì)記錄自身長(zhǎng)度的。獲取一個(gè)字符串內(nèi)容時(shí)，是從當(dāng)前位置開(kāi)始一直往后讀取，直到遇到終結(jié)字符“\0”。由此，在執(zhí)行字符串的變更操作時(shí)，如果長(zhǎng)度有增加，要考慮提前申請(qǐng)空間，否則有可能造成緩沖區(qū)溢出。
而在申請(qǐng)空間時(shí)，總避不開(kāi)malloc、realloc、calloc等幾個(gè)函數(shù)。下面看一段關(guān)于malloc的非官方解釋?zhuān)?/p>

對(duì)于malloc、calloc函數(shù)，是直接申請(qǐng)了一整塊兒足夠大的內(nèi)存。所以想要完成字符串的擴(kuò)展，在申請(qǐng)完空間之后，還需要進(jìn)行字符串的拷貝工作。而realloc會(huì)檢查當(dāng)前字符串所在內(nèi)存段，判斷其后有沒(méi)有緊鄰的未使用空間。如果有的話，則會(huì)直接將這部分未使用空間劃過(guò)來(lái)，這時(shí)候就不需要進(jìn)行后續(xù)的字符串拷貝了。但是如果沒(méi)有足夠的未使用空間，realloc也會(huì)與malloc一樣，新申請(qǐng)一整塊兒空間，然后必須執(zhí)行字符串拷貝才能完成字符串的擴(kuò)展。如果發(fā)生了字符串的拷貝，則字符串之前所占用的空間就會(huì)自動(dòng)釋放掉（類(lèi)似于調(diào)用free函數(shù)）。
上面所描述的對(duì)于內(nèi)存的申請(qǐng)和釋放行為就是內(nèi)存的重分配?？梢钥吹?，內(nèi)存的重分配還是比較復(fù)雜的，換句話說(shuō)，是比較耗費(fèi)資源的。而SDS的一個(gè)優(yōu)勢(shì)就在于此，SDS每次擴(kuò)展長(zhǎng)度的時(shí)候，并不是需要多少，申請(qǐng)多少，而總是會(huì)預(yù)留出一定的空間備用。這樣的話，就可以避免每次字符串長(zhǎng)度擴(kuò)大都去申請(qǐng)空間，也就減少了需要進(jìn)行內(nèi)存重分配的次數(shù)。一句話總結(jié)一下，就是，SDS的內(nèi)存預(yù)分配規(guī)則，保證了一個(gè)字符串連續(xù)增長(zhǎng)N次所需要的內(nèi)存重分配次數(shù)，從必定N次，降低到了最多N次。

對(duì)二進(jìn)制數(shù)據(jù)更加友好

還是如上文所述的原因，C語(yǔ)言中，判斷一個(gè)字符串結(jié)尾，是會(huì)從指針?biāo)赶蛭恢瞄_(kāi)始，一直往后遍歷，直到遇到“\0”。對(duì)于常用的文本數(shù)據(jù)，當(dāng)然沒(méi)有問(wèn)題。但是對(duì)于圖片、視頻這些數(shù)據(jù)，如果要以字符串形式進(jìn)行存儲(chǔ)，就會(huì)出現(xiàn)問(wèn)題，因?yàn)檫@類(lèi)數(shù)據(jù)自身攜帶的“\0”會(huì)影響到正常的字符串讀取。不過(guò)，使用SDS的話，可以避開(kāi)此類(lèi)問(wèn)題。因?yàn)镾DS并不以“\0”作為字符串結(jié)尾的判斷，而是每次總會(huì)讀取len所記錄長(zhǎng)度的字符串（這也就能保證，存進(jìn)去的數(shù)據(jù)是什么樣子的，讀出來(lái)的就是什么樣子的，不會(huì)少，不會(huì)多）。
不過(guò)，SDS依然會(huì)給整個(gè)字符串的末尾給帶上”\0”，這是為了方便復(fù)用C語(yǔ)言本身的字符串庫(kù)函數(shù)，不需要每個(gè)相關(guān)的庫(kù)函數(shù)，都得自己重新封裝。

顯而易見(jiàn)，為了具有上述的幾個(gè)特點(diǎn)，SDS要比C語(yǔ)言字符串占用更多的空間。也就是說(shuō)，SDS其實(shí)就是在拿空間換時(shí)間。所以，具體SDS和char*，在表示字符串時(shí)，誰(shuí)更有優(yōu)勢(shì)，還得考慮實(shí)際的業(yè)務(wù)場(chǎng)景。而在redis這個(gè)場(chǎng)景下，既然作者選用了SDS，那么姑且可以認(rèn)為SDS在這里帶來(lái)的速度優(yōu)勢(shì)要比多占用的那部分空間更有價(jià)值。

其他

redis3.2中SDS的改版

在redis3.2，對(duì)SDS做過(guò)比較大的改版，主要就在于對(duì)于不同長(zhǎng)度的字符串，使用不同的數(shù)據(jù)結(jié)構(gòu)。其數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)代碼如下：

/* 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 { // 對(duì)應(yīng)字符串長(zhǎng)度小于 1<<5（32）
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 { // 對(duì)應(yīng)字符串長(zhǎng)度小于 1<<8（256）
    uint8_t len; /* used（目前已經(jīng)使用的長(zhǎng)度）*/
    uint8_t alloc; /* excluding the header and null terminator（分配的總長(zhǎng)度）*/
    unsigned char flags; /* 3 lsb of type, 5 unused bits（3bit用來(lái)表示類(lèi)型，剩余的5bit目前沒(méi)用） */
    char buf[]; // 字符數(shù)組，用于實(shí)際存儲(chǔ)字符串內(nèi)容
};
struct __attribute__ ((__packed__)) sdshdr16 { // 對(duì)應(yīng)字符串長(zhǎng)度小于 1<<16（64k）
    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 { // 對(duì)應(yīng)字符串長(zhǎng)度小于 1<<32（4G）
    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 { // 對(duì)應(yīng)字符串長(zhǎng)度小于 1<<64
    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[];
};

可以看到，新版本要求針對(duì)不同長(zhǎng)度的字符串，選用不同的struct。而各個(gè)struct的區(qū)別就在于，len和alloc的類(lèi)型不一樣。其中，uint8_t占用1個(gè)字節(jié)，uint16_t占用2個(gè)字節(jié)，uint32_t占用4個(gè)字節(jié)，uint64_t占用8個(gè)字節(jié)。而舊版本中統(tǒng)一使用的int占用4個(gè)字節(jié)（32位機(jī)器和64位機(jī)器都是4個(gè)字節(jié)）。
此外，attribute ((packed))要求編譯器取消字節(jié)對(duì)齊，所以最終結(jié)構(gòu)體的大小，就是結(jié)構(gòu)體每個(gè)成員的大小之和。但是因?yàn)樽止?jié)對(duì)齊能夠大大加快CPU的內(nèi)存訪問(wèn)速度，所以新版本中，redis直接封裝了一下malloc方法，在申請(qǐng)空間的時(shí)候，手動(dòng)做字節(jié)對(duì)齊，相關(guān)代碼如下（注意：這部分代碼在redis的源碼中zmalloc.c文件中，sds中的源碼中并沒(méi)有相關(guān)的內(nèi)容）：

#define update_zmalloc_stat_alloc(__n) do { \
    size_t _n = (__n); \
    if (_n&(sizeof(long)-1)) _n += sizeof(long)-(_n&(sizeof(long)-1)); \
    atomicIncr(used_memory,__n); \
} while(0)

#define update_zmalloc_stat_free(__n) do { \
    size_t _n = (__n); \
    if (_n&(sizeof(long)-1)) _n += sizeof(long)-(_n&(sizeof(long)-1)); \
    atomicDecr(used_memory,__n); \
} while(0)

顯而易見(jiàn)，上述兩個(gè)改版都是為了優(yōu)化SDS的內(nèi)存占用，盡可能避免無(wú)謂的內(nèi)存消耗。

SDS的惰性空間釋放

從上文的描述中，可以發(fā)現(xiàn)，在字符串長(zhǎng)度擴(kuò)大時(shí)，如果空間不夠用時(shí)，會(huì)自動(dòng)申請(qǐng)更多空間。不過(guò)，如果字符串長(zhǎng)度縮小時(shí)，sds并不會(huì)自動(dòng)進(jìn)行空間釋放。它仍然會(huì)保留已申請(qǐng)的所有空間，以做備用。這樣顯然有可能造成空間的浪費(fèi)，所以，作者提供了一個(gè)專(zhuān)門(mén)的函數(shù)sdsRemoveFreeSpace，支持手動(dòng)對(duì)SDS的空閑空間進(jìn)行清理，不過(guò)這個(gè)函數(shù)只會(huì)保留已用的空間，會(huì)將所有未用的空間都給釋放掉。

內(nèi)存對(duì)齊

對(duì)于CPU而言，每次從內(nèi)存中存取數(shù)據(jù)都需要一定的開(kāi)銷(xiāo)。為了減少存取次數(shù)，CPU每次總會(huì)以2/4/8/16/32字節(jié)為單位進(jìn)行存取操作。這個(gè)存取單位就叫做內(nèi)存存取粒度。
為了迎合CPU的這種存取機(jī)制，應(yīng)用程序應(yīng)該盡可能相關(guān)聯(lián)的數(shù)據(jù)所占用的數(shù)據(jù)塊兒大小，剛好是存取單位字節(jié)數(shù)的整數(shù)倍，這樣才能夠保證CPU的存取次數(shù)最小。
舉個(gè)例子：
存取粒度為4個(gè)字節(jié)，對(duì)比如下兩種場(chǎng)景：
場(chǎng)景一：應(yīng)用程序數(shù)據(jù)所在位置為0到7，其中，位置0代表一份單獨(dú)的數(shù)據(jù)；位置1 - 位置4代表第二份單獨(dú)的數(shù)據(jù)；位置5 - 位置7代表第三份單獨(dú)的數(shù)據(jù)。
現(xiàn)在CPU要獲取第二份數(shù)據(jù)。那么，CPU需要先從0讀取4個(gè)字節(jié)，然后向上偏移1個(gè)字節(jié)，保留下位置1 - 位置3的數(shù)據(jù)；然后從位置4讀取4個(gè)字節(jié)，然后向下偏移3個(gè)字節(jié)，保留位置4的數(shù)據(jù)。最后將兩部分?jǐn)?shù)據(jù)拼接起來(lái)，交給寄存器。
場(chǎng)景二：應(yīng)用程度數(shù)據(jù)所在位置為0到12，其中，位置0代表一份單獨(dú)的數(shù)據(jù)；位置1 - 位置3填充空字符；位置4 - 位置6代表第二份單獨(dú)的數(shù)據(jù)；位置6 - 位置7填充空字符；位置8 - 位置10代表第三份數(shù)據(jù)；位置11填充空字符。
現(xiàn)在CPU要獲取第二份數(shù)據(jù)。那么，CPU只需要從位置4開(kāi)始，讀取4個(gè)字節(jié)即可。
顯然，對(duì)于第一種情況，CPU的存取開(kāi)銷(xiāo)會(huì)大增，部分CPU甚至?xí)苯舆M(jìn)入異常狀態(tài)，告知程序無(wú)法執(zhí)行。當(dāng)然，第二種情況會(huì)有一定的空間消耗，不過(guò)個(gè)人認(rèn)為大多數(shù)情況下，一份應(yīng)用數(shù)據(jù)的大小總會(huì)大于一個(gè)存取單位的大小，由于內(nèi)存對(duì)齊引起的空間浪費(fèi)率并沒(méi)有那么高。

參考

https://juejin.im/post/5b53ee7e5188251aaa2d2e16
https://zhuanlan.zhihu.com/p/38380467
https://blog.csdn.net/yangbodong22011/article/details/78419966
https://cloud.tencent.com/developer/article/1441547
http://redisbook.com/preview/sds/different_between_sds_and_c_string.html
https://blog.csdn.net/czrzchao/article/details/78990345
http://www.itdecent.cn/p/a371e2613ec8
https://zhuanlan.zhihu.com/p/65737134
https://github.com/antirez/sds
https://github.com/antirez/redis
https://www.cnblogs.com/coder2012/p/3150757.html

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

SDS

SDS

數(shù)據(jù)結(jié)構(gòu)

與char*的比較

能夠以O(shè)(1)時(shí)間復(fù)雜度來(lái)獲取字符串的長(zhǎng)度

避免緩沖區(qū)溢出

減少字符串變更帶來(lái)的內(nèi)存重分配次數(shù)

對(duì)二進(jìn)制數(shù)據(jù)更加友好

其他

redis3.2中SDS的改版

SDS的惰性空間釋放

內(nèi)存對(duì)齊

參考

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

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

SDS

數(shù)據(jù)結(jié)構(gòu)

與char*的比較

能夠以O(shè)(1)時(shí)間復(fù)雜度來(lái)獲取字符串的長(zhǎng)度

避免緩沖區(qū)溢出

減少字符串變更帶來(lái)的內(nèi)存重分配次數(shù)

對(duì)二進(jìn)制數(shù)據(jù)更加友好

其他

redis3.2中SDS的改版

SDS的惰性空間釋放

內(nèi)存對(duì)齊

參考

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

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