Redis中的動態(tài)字符串學習教程

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

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

實現(xiàn)字符串對象

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

對于那些包含字符串值的字符串對象來說， 每個字符串對象都包含一個 sds 值。

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

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

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

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

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

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

用 sds 取代 C 默認的 char* 類型

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

性能問題在稍后介紹 sds 定義的時候就會說到， 因為我們還沒有了解過 Redis 的其他功能模塊， 所以也沒辦法詳細地舉例說那里用到了 sds ， 不過在后面的章節(jié)中， 我們會經(jīng)?？吹狡渌K（幾乎每一個）都用到了 sds 類型值。

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

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

比如說， hello world 在 C 語言中就可以表示為 "hello world\0" 。

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

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

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

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

sds 的實現(xiàn)

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

typedef char *sds;


struct sdshdr {

  // buf 已占用長度
  int len;

  // buf 剩余可用長度
  int free;

  // 實際保存字符串數(shù)據(jù)的地方
  char buf[];
};

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

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

struct sdshdr {
  len = 11;
  free = 0;
  buf = "hello world\0"; // buf 的實際長度為 len + 1
};

通過 len 屬性， sdshdr 可以實現(xiàn)復雜度為 θ(1) 的長度計算操作。

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

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

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

  // 字符串類型的別名 
  typedef char *sds; 

另一個是 sdshdr：

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

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

比如，sdshdr.len可以用于在O（1）的復雜度下獲取sdshdr.buf中存儲的字符串的實際長度，而sdshdr.free則用于保存sdshdr.buf中還有多少預留空間

（這里sdshdr應該是sds handler的縮寫）

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

通過下面的函數(shù)定義來理解這個技巧

sdsnewlen 函數(shù)返回一個新的sds值，實際上，它創(chuàng)建的卻是一個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;  // 剛開始free為0 
   
    if (initlen  init) { 
      memcpy(sh->buf, init, initlen); 
    } 
    sh->buf[initlen] = '\0'; 
   
    // 只返回sh->buf這個字符串部分 
    return (char *)sh->buf; 
  } 

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

  static inline size_t sdslen(const sds s) 
  { 
    // 從sds中計算出相應的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]); 
  } 

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

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

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

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

內(nèi)存分配函數(shù)實現(xiàn)
和Reids 的實現(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; 
   
    // 預留空間可以滿足本地拼接  
    if (free >= addlen) return s; 
   
    len = sdslen(s); 
    sh = (void *)(s - (sizeof(struct sdshdr))); 
   
    // 設置新sds的字符串長度 
    // 這個長度比完成本次拼接實際所需的長度要大 
    // 通過預留空間優(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)存分配策略表明，在對sds 值進行擴展（expand）時，總會預留額外的空間，通過花費更多的內(nèi)存，減少了對內(nèi)存進行重分配(reallocate)的次數(shù)，并優(yōu)化下次擴展操作的處理速度

再把redis的如果實現(xiàn)對sds字符串擴展的方法貼一下，很不錯的思路：

  /** 
   * 按長度len擴展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; 
   
    // 復制 
    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; 
  } 
   
  /** 
   * 將一個char數(shù)組拼接到sds 末尾 
   */ 
  sds sdscat(sds s, const char *t) 
  { 
    return sdscatlen(s, t, strlen(t)); 
  }