詳解redis數據結構之sds

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

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

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

      redis使用sds結構而不用c字符串保存字符串的原因有如下幾點：

      ①常數復雜度獲取字符串長度

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

      ②杜絕緩沖區溢出

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

      ③減少修改字符串時內存重分配的次數

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

      ④二進制安全

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

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

      空間預分配指的是當對一個sds對象進行結構性增加時，比如修改其內容使其增長或者連接另一個字符串到其末尾，sds會預先分配一定的空間以預防未來可能對其進行的修改。如下是redis進行空間預分配的主要代碼：

sds sdsMakeRoomFor(sds s, size_t addlen) {

  struct sdshdr *sh, *newsh;

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

  size_t len, newlen;

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

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

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

  // 根據新長度，為 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);

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

  // 更新 sds 的空余長度
  newsh->free = newlen - len;

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

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

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

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

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

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