婷婷综合国产,91蜜桃婷婷狠狠久久综合9色 ,九九九九九精品,国产综合av

主頁(yè) > 知識(shí)庫(kù) > redis內(nèi)部數(shù)據(jù)結(jié)構(gòu)之SDS簡(jiǎn)單動(dòng)態(tài)字符串詳解

redis內(nèi)部數(shù)據(jù)結(jié)構(gòu)之SDS簡(jiǎn)單動(dòng)態(tài)字符串詳解

熱門標(biāo)簽:最簡(jiǎn)單的百度地圖標(biāo)注 太原營(yíng)銷外呼系統(tǒng) 地圖標(biāo)注如何即時(shí)生效 地圖標(biāo)注費(fèi)用 竹間科技AI電銷機(jī)器人 百度商家地圖標(biāo)注怎么做 玄武湖地圖標(biāo)注 西藏教育智能外呼系統(tǒng)價(jià)格 小紅書怎么地圖標(biāo)注店

前言

reids 沒有直接使用C語(yǔ)言傳統(tǒng)的字符串表示(以空字符結(jié)尾的字符數(shù)組)而是構(gòu)建了一種名為簡(jiǎn)單動(dòng)態(tài)字符串的抽象類型,并為redis的默認(rèn)字符串表示,因?yàn)镃字符串不能滿足redis對(duì)字符串的安全性、效率以及功能方面的需求

1、SDS 定義

在C語(yǔ)言中,字符串是以'\0'字符結(jié)尾(NULL結(jié)束符)的字符數(shù)組來(lái)存儲(chǔ)的,通常表達(dá)為字符指針的形式(char *)。它不允許字節(jié)0出現(xiàn)在字符串中間,因此,它不能用來(lái)存儲(chǔ)任意的二進(jìn)制數(shù)據(jù)。

sds的類型定義

typedef char *sds;

 

每個(gè)sds.h/sdshdr結(jié)構(gòu)表示一個(gè)SDS的值 
struct sdshdr{ 
//記錄buf數(shù)組中已使用的字節(jié)的數(shù)量 
//等于sds所保存字符串的長(zhǎng)度 
int len; 

//記錄buf中未使用的數(shù)據(jù) 
int free; 

//字符數(shù)組,用于保存字符串 
} 


* free 屬性的值為0,表示這個(gè)SDS沒有分配任何未使用的空間 
* len 屬性長(zhǎng)度為5,表示這個(gè)SDS保存一個(gè)五字節(jié)長(zhǎng)的字符串 
* buf 屬性是一個(gè)char類型的數(shù)組,數(shù)組的前5個(gè)字節(jié)分別保存了'R','e','d','i','s'五個(gè)字符,而最后一個(gè)字節(jié)則保存了空字符串'\0' 

肯定有人感到困惑了,竟然sds就等同于char *?

sds和傳統(tǒng)的C語(yǔ)言字符串保持類型兼容,因此它們的類型定義是一樣的,都是char *,在有些情況下,需要傳入一個(gè)C語(yǔ)言字符串的地方,也確實(shí)可以傳入一個(gè)sds。

但是sds和char *并不等同,sds是Binary Safe的,它可以存儲(chǔ)任意二進(jìn)制數(shù)據(jù),不能像C語(yǔ)言字符串那樣以字符'\0'來(lái)標(biāo)識(shí)字符串的結(jié)束,因此它必然有個(gè)長(zhǎng)度字段,這個(gè)字段在header中

sds的header結(jié)構(gòu)

/* 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一共有5種類型的header。目的是節(jié)省內(nèi)存。

一個(gè)SDS字符串的完整結(jié)構(gòu),由在內(nèi)存地址上前后相鄰的兩部分組成:

  • 一個(gè)header。通常包含字符串的長(zhǎng)度(len)、最大容量(alloc)和flags。sdshdr5有所不同。
  • 一個(gè)字符數(shù)組。這個(gè)字符數(shù)組的長(zhǎng)度等于最大容量+1。真正有效的字符串?dāng)?shù)據(jù),其長(zhǎng)度通常小于最大容量。在真正的字符串?dāng)?shù)據(jù)之后,是空余未用的字節(jié)(一般以字節(jié)0填充),允許在不重新分配內(nèi)存的前提下讓字符串?dāng)?shù)據(jù)向后做有限的擴(kuò)展。在真正的字符串?dāng)?shù)據(jù)之后,還有一個(gè)NULL結(jié)束符,即ASCII碼為0的'\0'字符。這是為了和傳統(tǒng)C字符串兼容。之所以字符數(shù)組的長(zhǎng)度比最大容量多1個(gè)字節(jié),就是為了在字符串長(zhǎng)度達(dá)到最大容量時(shí)仍然有1個(gè)字節(jié)存放NULL結(jié)束符。

除了sdshdr5之外,其它4個(gè)header的結(jié)構(gòu)都包含3個(gè)字段:

  • len: 表示字符串的真正長(zhǎng)度(不包含NULL結(jié)束符在內(nèi))。
  • alloc: 表示字符串的最大容量(不包含最后多余的那個(gè)字節(jié))。
  • flags: 總是占用一個(gè)字節(jié)。其中的最低3個(gè)bit用來(lái)表示header的類型。

在各個(gè)header的類型定義中,還有幾個(gè)需要我們注意的地方:

  • 在各個(gè)header的定義中使用了__attribute__ ((packed)),是為了讓編譯器以緊湊模式來(lái)分配內(nèi)存。如果沒有這個(gè)屬性,編譯器可能會(huì)為struct的字段做優(yōu)化對(duì)齊,在其中填充空字節(jié)。那樣的話,就不能保證header和sds的數(shù)據(jù)部分緊緊前后相鄰,也不能按照固定向低地址方向偏移1個(gè)字節(jié)的方式來(lái)獲取flags字段了。
  • 在各個(gè)header的定義中最后有一個(gè)char buf[]。我們注意到這是一個(gè)沒有指明長(zhǎng)度的字符數(shù)組,這是C語(yǔ)言中定義字符數(shù)組的一種特殊寫法,稱為柔性數(shù)組(flexible array member),只能定義在一個(gè)結(jié)構(gòu)體的最后一個(gè)字段上。它在這里只是起到一個(gè)標(biāo)記的作用,表示在flags字段后面就是一個(gè)字符數(shù)組,或者說(shuō),它指明了緊跟在flags字段后面的這個(gè)字符數(shù)組在結(jié)構(gòu)體中的偏移位置。而程序在為header分配的內(nèi)存的時(shí)候,它并不占用內(nèi)存空間。如果計(jì)算sizeof(struct sdshdr16)的值,那么結(jié)果是5個(gè)字節(jié),其中沒有buf字段。
  • sdshdr5與其它幾個(gè)header結(jié)構(gòu)不同,它不包含alloc字段,而長(zhǎng)度使用flags的高5位來(lái)存儲(chǔ)。因此,它不能為字符串分配空余空間。如果字符串需要?jiǎng)討B(tài)增長(zhǎng),那么它就必然要重新分配內(nèi)存才行。所以說(shuō),這種類型的sds字符串更適合存儲(chǔ)靜態(tài)的短字符串(長(zhǎng)度小于32)。

至此,我們非常清楚地看到了:sds字符串的header,其實(shí)隱藏在真正的字符串?dāng)?shù)據(jù)的前面(低地址方向)。這樣的一個(gè)定義,有如下幾個(gè)好處:

  • header和數(shù)據(jù)相鄰,而不用分成兩塊內(nèi)存空間來(lái)單獨(dú)分配。這有利于減少內(nèi)存碎片,提高存儲(chǔ)效率(memory efficiency)。
  • 雖然header有多個(gè)類型,但sds可以用統(tǒng)一的char *來(lái)表達(dá)。且它與傳統(tǒng)的C語(yǔ)言字符串保持類型兼容。如果一個(gè)sds里面存儲(chǔ)的是可打印字符串,那么我們可以直接把它傳給C函數(shù),比如使用strcmp比較字符串大小,或者使用printf進(jìn)行打印。

弄清了sds的數(shù)據(jù)結(jié)構(gòu),它的具體操作函數(shù)就比較好理解了。

sds的一些基礎(chǔ)函數(shù)

  • sdslen(const sds s): 獲取sds字符串長(zhǎng)度。
  • sdssetlen(sds s, size_t newlen): 設(shè)置sds字符串長(zhǎng)度。
  • sdsinclen(sds s, size_t inc): 增加sds字符串長(zhǎng)度。
  • sdsalloc(const sds s): 獲取sds字符串容量。
  • sdssetalloc(sds s, size_t newlen): 設(shè)置sds字符串容量。
  • sdsavail(const sds s): 獲取sds字符串空余空間(即alloc - len)。
  • sdsHdrSize(char type): 根據(jù)header類型得到header大小。
  • sdsReqType(size_t string_size): 根據(jù)字符串?dāng)?shù)據(jù)長(zhǎng)度計(jì)算所需要的header類型。

二、SDS 數(shù)組動(dòng)態(tài)分配策略

header信息中的定義這么多字段,其中一個(gè)很重要的作用就是實(shí)現(xiàn)對(duì)字符串的靈活操作并且盡量減少內(nèi)存重新分配和回收操作。

redis的內(nèi)存分配策略如下

  • 當(dāng)SDS的len屬性長(zhǎng)度小于1MB時(shí),redis會(huì)分配和len相同長(zhǎng)度的free空間。至于為什么這樣分配呢,上次用了len長(zhǎng)度的空間,那么下次程序可能也會(huì)用len長(zhǎng)度的空間,所以redis就為你預(yù)分配這么多的空間。
  • 但是當(dāng)SDS的len屬性長(zhǎng)度大于1MB時(shí),程序?qū)⒍喾峙?M的未使用空間。這個(gè)時(shí)候我在根據(jù)這種慣性預(yù)測(cè)來(lái)分配的話就有點(diǎn)得不償失了。所以redis是將1MB設(shè)為一個(gè)風(fēng)險(xiǎn)值,沒過(guò)風(fēng)險(xiǎn)值你用多少我就給你多少,過(guò)了的話那這個(gè)風(fēng)險(xiǎn)值就是我能給你臨界值

reids的內(nèi)存回收策略如下

  • redis的內(nèi)存回收采用惰性回收,即你把字符串變短了,那么多余的內(nèi)存空間我先不還給操作系統(tǒng),先留著,萬(wàn)一馬上又要被使用呢。短暫的持有資源,既可以充分利用資源,也可以不浪費(fèi)資源。這是一種很優(yōu)秀的思想。

綜上所述,redis實(shí)現(xiàn)的高性能字符串的結(jié)果就把N次字符串操作必會(huì)發(fā)生N次內(nèi)存重新分配變?yōu)槿似纷畈顣r(shí)最多發(fā)生N次重新分配。

/* Enlarge the free space at the end of the sds string so that the caller
 * is sure that after calling this function can overwrite up to addlen
 * bytes after the end of the string, plus one more byte for nul term.
 *
 * Note: this does not change the *length* of the sds string as returned
 * by sdslen(), but only the free buffer space we have. */
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;
 
 /* Return ASAP if there is enough space left. */
 if (avail >= addlen) return s;
 
 len = sdslen(s);
 sh = (char*)s-sdsHdrSize(oldtype);
 newlen = (len+addlen);
 if (newlen  SDS_MAX_PREALLOC)
 newlen *= 2;
 else
 newlen += SDS_MAX_PREALLOC;
 
 type = sdsReqType(newlen);
 
 /* Don't use type 5: the user is appending to the string and type 5 is
 * not able to remember empty space, so sdsMakeRoomFor() must be called
 * at every appending operation. */
 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 {
 /* Since the header size changes, need to move the string forward,
  * and can't use 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[-1] = type;
 sdssetlen(s, len);
 }
 sdssetalloc(s, newlen);
 return s;
}
 
/* Reallocate the sds string so that it has no free space at the end. The
 * contained string remains not altered, but next concatenation operations
 * will require a reallocation.
 *
 * After the call, the passed sds string is no longer valid and all the
 * references must be substituted with the new pointer returned by the call. */
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);
 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的特點(diǎn)

sds正是在Redis中被廣泛使用的字符串結(jié)構(gòu),它的全稱是Simple Dynamic String。與其它語(yǔ)言環(huán)境中出現(xiàn)的字符串相比,它具有如下顯著的特點(diǎn):

  • 可動(dòng)態(tài)擴(kuò)展內(nèi)存。SDS表示的字符串其內(nèi)容可以修改,也可以追加。在很多語(yǔ)言中字符串會(huì)分為mutable和immutable兩種,SDS屬于mutable類型的。
  • 二進(jìn)制安全(Binary Safe)。sds能存儲(chǔ)任意二進(jìn)制數(shù)據(jù)。
  • 與傳統(tǒng)的C語(yǔ)言字符串類型兼容。
  • 預(yù)分配空間,可以懶惰釋放,在內(nèi)存緊張的時(shí)候也可以縮減不需要的內(nèi)存
  • 常數(shù)復(fù)雜度獲取字符串長(zhǎng)度
  • 杜絕緩沖區(qū)溢出,邊界檢查

四、淺談SDS與string的關(guān)系

127.0.0.1:6379> set test test
OK
127.0.0.1:6379> append test " test"
(integer) 9
127.0.0.1:6379> get test
"test test"
127.0.0.1:6379> setbit test 36 1
(integer) 0
127.0.0.1:6379> get test
"test(test"
127.0.0.1:6379> getrange test -5 -1
"(test"
  • append操作使用SDS的sdscatlen來(lái)實(shí)現(xiàn)。
  • setbit和getrange都是先根據(jù)key取到整個(gè)sds字符串,然后再?gòu)淖址x取或修改指定的部分。由于SDS就是一個(gè)字符數(shù)組,所以對(duì)它的某一部分進(jìn)行操作似乎都比較簡(jiǎn)單。

但是,string除了支持這些操作之外,當(dāng)它存儲(chǔ)的值是個(gè)數(shù)字的時(shí)候,它還支持incr、decr等操作。它的內(nèi)部存儲(chǔ)不是SDS,這種情況下,setbit和getrange的實(shí)現(xiàn)也會(huì)有所不同。

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了,希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,如果有疑問(wèn)大家可以留言交流,謝謝大家對(duì)腳本之家的支持。

參考文章

  • http://blog.csdn.net/xiejingfa/article/details/50972592
  • http://blog.csdn.net/acceptedxukai/article/details/17482611
  • https://segmentfault.com/a/1190000003984537
您可能感興趣的文章:
  • Redis底層數(shù)據(jù)結(jié)構(gòu)詳解
  • 詳解Redis數(shù)據(jù)結(jié)構(gòu)之跳躍表
  • redis中的數(shù)據(jù)結(jié)構(gòu)和編碼詳解
  • redis數(shù)據(jù)結(jié)構(gòu)之intset的實(shí)例詳解
  • 詳解redis數(shù)據(jù)結(jié)構(gòu)之sds
  • 詳解redis數(shù)據(jù)結(jié)構(gòu)之壓縮列表
  • Redis中5種數(shù)據(jù)結(jié)構(gòu)的使用場(chǎng)景介紹
  • Redis底層數(shù)據(jù)結(jié)構(gòu)之dict、ziplist、quicklist詳解

標(biāo)簽:澳門 景德鎮(zhèn) 揚(yáng)州 贛州 香港 廣東 唐山 林芝

巨人網(wǎng)絡(luò)通訊聲明:本文標(biāo)題《redis內(nèi)部數(shù)據(jù)結(jié)構(gòu)之SDS簡(jiǎn)單動(dòng)態(tài)字符串詳解》,本文關(guān)鍵詞  redis,內(nèi)部,數(shù)據(jù)結(jié)構(gòu),之,;如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問(wèn)題,煩請(qǐng)?zhí)峁┫嚓P(guān)信息告之我們,我們將及時(shí)溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò),涉及言論、版權(quán)與本站無(wú)關(guān)。
  • 相關(guān)文章
  • 下面列出與本文章《redis內(nèi)部數(shù)據(jù)結(jié)構(gòu)之SDS簡(jiǎn)單動(dòng)態(tài)字符串詳解》相關(guān)的同類信息!
  • 本頁(yè)收集關(guān)于redis內(nèi)部數(shù)據(jù)結(jié)構(gòu)之SDS簡(jiǎn)單動(dòng)態(tài)字符串詳解的相關(guān)信息資訊供網(wǎng)民參考!
  • 推薦文章
    主站蜘蛛池模板: 江西省| 旌德县| 株洲县| 如东县| 抚远县| 文昌市| 平度市| 山西省| 湘潭市| 灵璧县| 林西县| 石棉县| 高要市| 博罗县| 灵寿县| 乌拉特中旗| 巢湖市| 常宁市| 娄烦县| 桃园市| 嘉祥县| 台北县| 彭水| 京山县| 三亚市| 大渡口区| 昌乐县| 沽源县| 柳州市| 醴陵市| 安乡县| 枝江市| 闽清县| 福泉市| 同仁县| 连平县| 丰原市| 邢台县| 潞城市| 景东| 天津市|