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

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

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

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

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

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

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

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

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

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

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

      ④二進(jìn)制安全

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

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

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

sds sdsMakeRoomFor(sds s, size_t addlen) {

  struct sdshdr *sh, *newsh;

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

  size_t len, newlen;

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

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

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

  // 根據(jù)新長度，為 s 分配新空間所需的大小
  if (newlen  SDS_MAX_PREALLOC)
    // 如果新長度小于 SDS_MAX_PREALLOC 
    // 那么為它分配兩倍于所需長度的空間
    newlen *= 2;
  else
    // 否則，分配長度為目前長度加上 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 的空余長度
  newsh->free = newlen - len;

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

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

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

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

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

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