詳解redis數(shù)據(jù)結(jié)構(gòu)之sds

  字符串在redis中使用非常廣泛，在redis中，所有的數(shù)據(jù)都保存在字典（Map）中，而字典的鍵就是字符串類型，并且對(duì)于很大一部分字典值數(shù)據(jù)也是又字符串組成的。以下是sds的具體存儲(chǔ)結(jié)構(gòu)：

      從圖中可以看出，sds的屬性有三個(gè)：len、free和buf數(shù)組。這里len字段是用來(lái)保存sds字符串中所包含字符數(shù)目的，free字段則是用來(lái)保存buf數(shù)組中空余的部分的長(zhǎng)度的，而buf數(shù)組則是實(shí)際用來(lái)保存字符串的。比如如下結(jié)構(gòu)保存了“Hello World！”這個(gè)字符串：

      這里需要注意的是，sds和c字符串一樣，需要在字符串結(jié)尾加上一個(gè)“\0”表示該字符串的結(jié)束。這里這個(gè)sds對(duì)象的len屬性保存了“Hello World!”這個(gè)字符串的長(zhǎng)度，而free屬性保存了數(shù)組中空余的位數(shù)，buf數(shù)組則實(shí)際保存了這個(gè)字符串，空字符和空余位。

      redis使用sds結(jié)構(gòu)而不用c字符串保存字符串的原因有如下幾點(diǎn)：

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

      通過(guò)讀取sds對(duì)象的len屬性的值我們可以使用O(1)獲取sds對(duì)象保存的字符串長(zhǎng)度，而在c字符串中，我們必須對(duì)整個(gè)數(shù)組進(jìn)行遍歷從而獲取字符串的長(zhǎng)度，其時(shí)間復(fù)雜度為O(N)。

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

      在c字符串中，比如char *strcat(char *dest, const char *src)函數(shù)將src連接到dest的末尾，但是c字符串假定dest數(shù)組中有足夠的空余空間來(lái)保存src數(shù)組，如果dest數(shù)組長(zhǎng)度不夠就會(huì)造成緩沖區(qū)溢出；在sds對(duì)象中也提供了類似的函數(shù)sds sdscat(sds s, const char *t)和sds sdscatsds(sds s, const sds t)，這兩個(gè)函數(shù)在調(diào)用之前會(huì)檢查目標(biāo)sds對(duì)象s中free屬性是否能夠保存要連接的字符串的長(zhǎng)度，如果不夠，就會(huì)對(duì)目標(biāo)sds對(duì)象擴(kuò)容，這就保證了sds對(duì)象不會(huì)造成緩沖區(qū)溢出。

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

      在對(duì)sds進(jìn)行修改的時(shí)候，redis可以通過(guò)“空間預(yù)分配”和“惰性空間釋放”來(lái)保證后續(xù)對(duì)sds對(duì)象的頻繁修改而不會(huì)造成sds對(duì)象的buf數(shù)組經(jīng)常分配空間；而對(duì)于c字符串，每次對(duì)其進(jìn)行修改都需要進(jìn)行一次空間分配和復(fù)制操作。

      ④二進(jìn)制安全

      對(duì)于c字符串，由于其判斷是否結(jié)束的標(biāo)志是從字符串開(kāi)始到結(jié)尾碰到的第一個(gè)“\0”字符，這就限制了c字符串不能保存像圖片、音頻、視頻、壓縮文件等二進(jìn)制保存的內(nèi)容；而對(duì)于sds對(duì)象，由于判斷其是否結(jié)束的標(biāo)志是其len屬性，也就是說(shuō)無(wú)論在len長(zhǎng)度內(nèi)，buf數(shù)組中是否包含“\0”都不影響redis判斷其是否結(jié)束。

      上面講到了sds的空間預(yù)分配和惰性空間釋放，sds通過(guò)這兩種操作極大的簡(jiǎn)化了其對(duì)字符串的修改和對(duì)空間的分配工作。

      空間預(yù)分配指的是當(dāng)對(duì)一個(gè)sds對(duì)象進(jìn)行結(jié)構(gòu)性增加時(shí)，比如修改其內(nèi)容使其增長(zhǎng)或者連接另一個(gè)字符串到其末尾，sds會(huì)預(yù)先分配一定的空間以預(yù)防未來(lái)可能對(duì)其進(jìn)行的修改。如下是redis進(jìn)行空間預(yù)分配的主要代碼：

sds sdsMakeRoomFor(sds s, size_t addlen) {

  struct sdshdr *sh, *newsh;

  // 獲取 s 目前的空余空間長(zhǎng)度
  size_t free = sdsavail(s);

  size_t len, newlen;

  // s 目前的空余空間已經(jīng)足夠，無(wú)須再進(jìn)行擴(kuò)展，直接返回
  if (free >= addlen) return s;

  // 獲取 s 目前已占用空間的長(zhǎng)度
  len = sdslen(s);
  sh = (void*) (s-(sizeof(struct sdshdr)));

  // s 最少需要的長(zhǎng)度
  newlen = (len+addlen);

  // 根據(jù)新長(zhǎng)度，為 s 分配新空間所需的大小
  if (newlen  SDS_MAX_PREALLOC)
    // 如果新長(zhǎng)度小于 SDS_MAX_PREALLOC 
    // 那么為它分配兩倍于所需長(zhǎng)度的空間
    newlen *= 2;
  else
    // 否則，分配長(zhǎng)度為目前長(zhǎng)度加上 SDS_MAX_PREALLOC
    newlen += SDS_MAX_PREALLOC;
  // T = O(N)
  newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);

  // 內(nèi)存不足，分配失敗，返回
  if (newsh == NULL) return NULL;

  // 更新 sds 的空余長(zhǎng)度
  newsh->free = newlen - len;

  // 返回 sds
  return newsh->buf;
}

      從圖中可以看出，當(dāng)要添加的內(nèi)容比目標(biāo)sds對(duì)象的free屬性要短時(shí)直接返回并將要添加的內(nèi)容添加到目標(biāo)sds對(duì)象的buf數(shù)組中即可；當(dāng)要添加的內(nèi)容比目標(biāo)sds對(duì)象的free屬性要長(zhǎng)時(shí)，就會(huì)計(jì)算要添加的內(nèi)容和sds對(duì)象的當(dāng)前長(zhǎng)度的和newlen，如果newlen小于SDS_MAX_PREALLOC也即1M的時(shí)候，新創(chuàng)建的buf數(shù)組的長(zhǎng)度為newlen的兩倍，如果newlen大于SDS_MAX_PREALLOC的時(shí)候，新創(chuàng)建的buf數(shù)組的長(zhǎng)度為newlen+SDS_MAX_PREALLOC，即只多分配1M的預(yù)留空間。空間預(yù)分配保證了sds對(duì)象的空余位長(zhǎng)度至多為擴(kuò)張之后字符串長(zhǎng)度的1倍，這也就保證了后續(xù)對(duì)sds對(duì)象的修改將盡可能少的分配空間。

      惰性空間釋放指的是當(dāng)對(duì)一個(gè)sds對(duì)象進(jìn)行縮短操作時(shí)，其不會(huì)直接將buf數(shù)組縮短為目標(biāo)數(shù)組的長(zhǎng)度，而是只改變sds對(duì)象的len屬性的值，數(shù)組中多余的部分則保存在free屬性中，這樣就可以保證后續(xù)可能的對(duì)該sds對(duì)象的增長(zhǎng)操作不需要重新分配空間。

      最后需要進(jìn)行說(shuō)明的是，sds對(duì)象也和c一樣使用“\0”作為字符串的結(jié)尾的原因是redis也是使用c語(yǔ)言編寫(xiě)的，使用“\0”結(jié)尾就可以直接使用部分c函數(shù)庫(kù)中對(duì)字符串操作的函數(shù)。

      通過(guò)上面對(duì)sds對(duì)象的說(shuō)明可以發(fā)現(xiàn)，redis對(duì)sds對(duì)象的處理極大的減少了字符串處理中可能出現(xiàn)的復(fù)雜操作，并且大部分操作基本上都可以在極短的時(shí)間內(nèi)完成，這就保證了redis對(duì)字符串處理的高速率。

       感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！