Redis中的動(dòng)態(tài)字符串學(xué)習(xí)教程

sds 的用途
Sds 在 Redis 中的主要作用有以下兩個(gè)：

實(shí)現(xiàn)字符串對(duì)象（StringObject）；
在 Redis 程序內(nèi)部用作 char* 類(lèi)型的替代品；
以下兩個(gè)小節(jié)分別對(duì)這兩種用途進(jìn)行介紹。

實(shí)現(xiàn)字符串對(duì)象

Redis 是一個(gè)鍵值對(duì)數(shù)據(jù)庫(kù)（key-value DB）， 數(shù)據(jù)庫(kù)的值可以是字符串、集合、列表等多種類(lèi)型的對(duì)象， 而數(shù)據(jù)庫(kù)的鍵則總是字符串對(duì)象。

對(duì)于那些包含字符串值的字符串對(duì)象來(lái)說(shuō)， 每個(gè)字符串對(duì)象都包含一個(gè) sds 值。

“包含字符串值的字符串對(duì)象”，這種說(shuō)法初聽(tīng)上去可能會(huì)有點(diǎn)奇怪， 但是在 Redis 中， 一個(gè)字符串對(duì)象除了可以保存字符串值之外， 還可以保存 long 類(lèi)型的值， 所以為了嚴(yán)謹(jǐn)起見(jiàn)， 這里需要強(qiáng)調(diào)一下： 當(dāng)字符串對(duì)象保存的是字符串時(shí)， 它包含的才是 sds 值， 否則的話， 它就是一個(gè) long 類(lèi)型的值。
舉個(gè)例子， 以下命令創(chuàng)建了一個(gè)新的數(shù)據(jù)庫(kù)鍵值對(duì)， 這個(gè)鍵值對(duì)的鍵和值都是字符串對(duì)象， 它們都包含一個(gè) sds 值：

redis> SET book "Mastering C++ in 21 days"
OK

redis> GET book
"Mastering C++ in 21 days"

以下命令創(chuàng)建了另一個(gè)鍵值對(duì)， 它的鍵是字符串對(duì)象， 而值則是一個(gè)集合對(duì)象：

redis> SADD nosql "Redis" "MongoDB" "Neo4j"
(integer) 3

redis> SMEMBERS nosql
1) "Neo4j"
2) "Redis"
3) "MongoDB"

用 sds 取代 C 默認(rèn)的 char* 類(lèi)型

因?yàn)?char* 類(lèi)型的功能單一， 抽象層次低， 并且不能高效地支持一些 Redis 常用的操作（比如追加操作和長(zhǎng)度計(jì)算操作）， 所以在 Redis 程序內(nèi)部， 絕大部分情況下都會(huì)使用 sds 而不是 char* 來(lái)表示字符串。

性能問(wèn)題在稍后介紹 sds 定義的時(shí)候就會(huì)說(shuō)到， 因?yàn)槲覀冞€沒(méi)有了解過(guò) Redis 的其他功能模塊， 所以也沒(méi)辦法詳細(xì)地舉例說(shuō)那里用到了 sds ， 不過(guò)在后面的章節(jié)中， 我們會(huì)經(jīng)?？吹狡渌K（幾乎每一個(gè)）都用到了 sds 類(lèi)型值。

目前來(lái)說(shuō)， 只要記住這個(gè)事實(shí)即可： 在 Redis 中， 客戶端傳入服務(wù)器的協(xié)議內(nèi)容、 aof 緩存、 返回給客戶端的回復(fù)， 等等， 這些重要的內(nèi)容都是由 sds 類(lèi)型來(lái)保存的。

redis 中的字符串
在 C 語(yǔ)言中，字符串可以用一個(gè) \0 結(jié)尾的 char 數(shù)組來(lái)表示。

比如說(shuō)， hello world 在 C 語(yǔ)言中就可以表示為 "hello world\0" 。

這種簡(jiǎn)單的字符串表示，在大多數(shù)情況下都能滿足要求，但是，它并不能高效地支持長(zhǎng)度計(jì)算和追加（append）這兩種操作：

每次計(jì)算字符串長(zhǎng)度（strlen(s)）的復(fù)雜度為 θ(N) 。
對(duì)字符串進(jìn)行 N 次追加，必定需要對(duì)字符串進(jìn)行 N 次內(nèi)存重分配（realloc）。
在 Redis 內(nèi)部， 字符串的追加和長(zhǎng)度計(jì)算很常見(jiàn)， 而 APPEND 和 STRLEN 更是這兩種操作，在 Redis 命令中的直接映射， 這兩個(gè)簡(jiǎn)單的操作不應(yīng)該成為性能的瓶頸。

另外， Redis 除了處理 C 字符串之外， 還需要處理單純的字節(jié)數(shù)組， 以及服務(wù)器協(xié)議等內(nèi)容， 所以為了方便起見(jiàn)， Redis 的字符串表示還應(yīng)該是二進(jìn)制安全的： 程序不應(yīng)對(duì)字符串里面保存的數(shù)據(jù)做任何假設(shè)， 數(shù)據(jù)可以是以 \0 結(jié)尾的 C 字符串， 也可以是單純的字節(jié)數(shù)組， 或者其他格式的數(shù)據(jù)。

考慮到這兩個(gè)原因， Redis 使用 sds 類(lèi)型替換了 C 語(yǔ)言的默認(rèn)字符串表示： sds 既可高效地實(shí)現(xiàn)追加和長(zhǎng)度計(jì)算， 同時(shí)是二進(jìn)制安全的。

sds 的實(shí)現(xiàn)

在前面的內(nèi)容中， 我們一直將 sds 作為一種抽象數(shù)據(jù)結(jié)構(gòu)來(lái)說(shuō)明， 實(shí)際上， 它的實(shí)現(xiàn)由以下兩部分組成：

typedef char *sds;


struct sdshdr {

  // buf 已占用長(zhǎng)度
  int len;

  // buf 剩余可用長(zhǎng)度
  int free;

  // 實(shí)際保存字符串?dāng)?shù)據(jù)的地方
  char buf[];
};

其中，類(lèi)型 sds 是 char * 的別名（alias），而結(jié)構(gòu) sdshdr 則保存了 len 、 free 和 buf 三個(gè)屬性。

作為例子，以下是新創(chuàng)建的，同樣保存 hello world 字符串的 sdshdr 結(jié)構(gòu)：

struct sdshdr {
  len = 11;
  free = 0;
  buf = "hello world\0"; // buf 的實(shí)際長(zhǎng)度為 len + 1
};

通過(guò) len 屬性， sdshdr 可以實(shí)現(xiàn)復(fù)雜度為 θ(1) 的長(zhǎng)度計(jì)算操作。

另一方面， 通過(guò)對(duì) buf 分配一些額外的空間， 并使用 free 記錄未使用空間的大小， sdshdr 可以讓執(zhí)行追加操作所需的內(nèi)存重分配次數(shù)大大減少， 下一節(jié)我們就會(huì)來(lái)詳細(xì)討論這一點(diǎn)。

當(dāng)然， sds 也對(duì)操作的正確實(shí)現(xiàn)提出了要求 —— 所有處理 sdshdr 的函數(shù)，都必須正確地更新 len 和 free 屬性，否則就會(huì)造成 bug 。

數(shù)據(jù)類(lèi)型定義
與sds實(shí)現(xiàn)有關(guān)的數(shù)據(jù)類(lèi)型有兩個(gè)，一個(gè)是 sds：

  // 字符串類(lèi)型的別名 
  typedef char *sds; 

另一個(gè)是 sdshdr：

  // 持有sds的結(jié)構(gòu) 
  struct sdshdr { 
    // buf中已經(jīng)被使用的字符串空間數(shù)量 
    int len; 
    // buf中預(yù)留字符串的空間數(shù)量 
    int free; 
    // 實(shí)際存儲(chǔ)字符串的地方 
    char buf[]; 
  }; 

其中，sds只是字符串?dāng)?shù)組類(lèi)型char*的別名，而sdshdr用于持有和保存sds的信息

比如，sdshdr.len可以用于在O（1）的復(fù)雜度下獲取sdshdr.buf中存儲(chǔ)的字符串的實(shí)際長(zhǎng)度，而sdshdr.free則用于保存sdshdr.buf中還有多少預(yù)留空間

（這里sdshdr應(yīng)該是sds handler的縮寫(xiě)）

將sdshdr用作sds
sds模塊對(duì)sdshdr結(jié)構(gòu)使用了一點(diǎn)小技巧：通過(guò)指針運(yùn)算，它使得sdshdr結(jié)構(gòu)可以像sds類(lèi)型一樣被傳值和處理，并在需要的時(shí)候恢復(fù)成sdshdr類(lèi)型

通過(guò)下面的函數(shù)定義來(lái)理解這個(gè)技巧

sdsnewlen 函數(shù)返回一個(gè)新的sds值，實(shí)際上，它創(chuàng)建的卻是一個(gè)sdshdr結(jié)構(gòu)：

  sds sdsnewlen(const void *init, size_t initlen) 
  { 
    struct sdshdr *sh; 
   
    if (init) { 
      // 創(chuàng)建 
      sh = malloc(sizeof(struct sdshdr) + initlen + 1); 
    } else { 
      // 重分配 
      sh = calloc(1, sizeof(struct sdshdr) + initlen + 1); 
    } 
   
    if (sh == NULL) return NULL; 
   
    sh->len = initlen; 
    sh->free = 0;  // 剛開(kāi)始free為0 
   
    if (initlen  init) { 
      memcpy(sh->buf, init, initlen); 
    } 
    sh->buf[initlen] = '\0'; 
   
    // 只返回sh->buf這個(gè)字符串部分 
    return (char *)sh->buf; 
  } 

通過(guò)使用變量持有一個(gè)sds的值，在遇到那些只處理sds值本身的函數(shù)時(shí)，可以直接將sds傳給它們。比如說(shuō)，sdstoupper 函數(shù)就是其中的一個(gè)例子：

  static inline size_t sdslen(const sds s) 
  { 
    // 從sds中計(jì)算出相應(yīng)的sdshdr結(jié)構(gòu) 
    struct sdshdr *sh = (void *)(s - (sizeof(struct sdshdr))); 
   
    return sh->len; 
  } 
   
   
  void sdstoupper(sds s) 
  { 
    int len = sdslen(s), j; 
   
    for (j = 0; j  len; j ++) 
      s[j] = toupper(s[j]); 
  } 

這里有一個(gè)技巧，通過(guò)指針運(yùn)算，可以從sds值中計(jì)算出相應(yīng)的sdshdr結(jié)構(gòu)：

sds雖然是指向char *的buf（ps：并且空數(shù)組不占用內(nèi)存空間，數(shù)組名即為內(nèi)存地址），但是分配的時(shí)候是分配sizeof(struct sdshdr) + initlen + 1的，通過(guò)sds - sizeof(struct sdshdr)可以計(jì)算出struct sdshdr的首地址，從而可以得到len和free的信息

sdsavail 函數(shù)就是使用這中技巧的一個(gè)例子：

  static inline size_t sdsavail(const sds s) 
  { 
    struct sdshdr *sh = (void *)(s - (sizeof(struct sdshdr))); 
   
    return sh->free; 
  } 

內(nèi)存分配函數(shù)實(shí)現(xiàn)
和Reids 的實(shí)現(xiàn)決策相關(guān)的函數(shù)是 sdsMakeRoomFor ：

  sds sdsMakeRoomFor(sds s, size_t addlen) 
  { 
    struct sdshdr *sh, *newsh; 
    size_t free = sdsavail(s); 
    size_t len, newlen; 
   
    // 預(yù)留空間可以滿足本地拼接  
    if (free >= addlen) return s; 
   
    len = sdslen(s); 
    sh = (void *)(s - (sizeof(struct sdshdr))); 
   
    // 設(shè)置新sds的字符串長(zhǎng)度 
    // 這個(gè)長(zhǎng)度比完成本次拼接實(shí)際所需的長(zhǎng)度要大 
    // 通過(guò)預(yù)留空間優(yōu)化下次拼接操作 
    newlen = (len + addlen); 
    if (newlen  1024 * 1024) 
      newlen *= 2; 
    else 
      newlen += 1024; 
   
    // 重新分配sdshdr 
    newsh = realloc(sh, sizeof(struct sdshdr) + newlen + 1); 
    if (newsh == NULL) return NULL; 
   
    newsh->free = newlen - len; 
   
    // 只返回字符串部分 
    return newsh->buf; 
  } 

這種內(nèi)存分配策略表明，在對(duì)sds 值進(jìn)行擴(kuò)展（expand）時(shí)，總會(huì)預(yù)留額外的空間，通過(guò)花費(fèi)更多的內(nèi)存，減少了對(duì)內(nèi)存進(jìn)行重分配(reallocate)的次數(shù)，并優(yōu)化下次擴(kuò)展操作的處理速度

再把redis的如果實(shí)現(xiàn)對(duì)sds字符串?dāng)U展的方法貼一下，很不錯(cuò)的思路：

  /** 
   * 按長(zhǎng)度len擴(kuò)展sds，并將t拼接到sds的末尾 
   */ 
  sds sdscatlen(sds s, const void *t, size_t len) 
  { 
    struct sdshdr *sh; 
   
    size_t curlen = sdslen(s); 
   
    // O(N) 
    s = sdsMakeRoomFor(s, len); 
    if (s == NULL) return NULL; 
   
    // 復(fù)制 
    memcpy(s + curlen, t, len); 
   
    // 更新len和free屬性 
    sh = (void *)(s - (sizeof(struct sdshdr))); 
    sh->len = curlen + len; 
    sh->free = sh->free - len; 
   
    // 終結(jié)符 
    s[curlen + len] = '\0'; 
   
    return s; 
  } 
   
  /** 
   * 將一個(gè)char數(shù)組拼接到sds 末尾 
   */ 
  sds sdscat(sds s, const char *t) 
  { 
    return sdscatlen(s, t, strlen(t)); 
  }