Redis中のダイナミック文字列学習教程

sdsの用途
SdsのRedisにおける主要な役割は以下の二つがある。
文字列オブジェクトを実現します。
Redisプログラムの内部でchar*タイプの代替品として使用されます。
以下の二つのセクションはそれぞれこの二つの用途を紹介します。
文字列オブジェクトを実現
Redisはキーとデータベース（key-value DB）であり、データベースの値は文字列、セット、リストなどの複数の種類のオブジェクトであり、データベースのキーは常に文字列オブジェクトである。
文字列の値を含む文字列オブジェクトには、各文字列オブジェクトに一つのsds値が含まれています。
「文字列の値が含まれている文字列オブジェクト」という言い方は最初はおかしいかもしれませんが、Redisでは文字列の値を保存できるほか、longタイプの値も保存できますので、厳密にするためには、文字列オブジェクトが格納されている文字列の場合は、sds値が含まれています。さもなければ、longタイプの値です。
例えば、以下のコマンドは新しいデータベースキーペアを作成しました。このキーペアのキーと値は文字列オブジェクトです。

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

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

次のコマンドは他のキーペアを作成しました。キーは文字列オブジェクトです。値はセットオブジェクトです。

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

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

Cのデフォルトのchar*タイプをsdsで置換します。
char*タイプの機能は単一で、抽象的なレベルが低く、かつ効率的にいくつかのRedisの一般的な動作（たとえば追加操作と長さ計算操作）をサポートできないので、Redisプログラムの内部では、ほとんどの場合、char*ではなくsdsを使用して文字列を表しています。
性能問題は後でsdsの定義を紹介すると、Redisの他の機能モジュールはまだ知られていませんので、詳しくはsdsを使ったとは言えませんが、後の章では他のモジュール（ほぼすべての）がsdsタイプの値を使っているのをよく見ます。
この事実を覚えていればいいです。Redisでは、クライアントがサーバに伝えたプロトコルの内容、aofキャッシュ、クライアントへの返信など、これらの重要な内容はすべてsdsタイプによって保存されています。
redis中の文字列
C言語では、文字列は\0の最後のchar配列で表現できます。
例えば、ハローワールドはC言語で「ハローワールド」と表現できます。
このような簡単な文字列表現は、多くの場合に要求を満たすことができるが、長さ計算と追加の2つの動作を効率的にサポートすることはできない。
各計算文字列長（streen（s））の複雑さは、θ(N）
文字列をN回追加するには、必ず文字列をN回メモリ再割り当てする必要があります。
Redis内部では、文字列の追加と長さ計算が一般的であるが、APPENDとSTRLENは、Redisコマンドにおける直接マッピングの2つの単純な動作は、パフォーマンスのボトルネックになるべきではない。
また、RedisはC文字列の処理に加えて、単純なバイト配列やサーバプロトコルなどの内容を処理する必要がありますので、Redisの文字列表示は、便宜上、バイナリセキュリティであるべきです。プログラムは文字列に保存されているデータに対しては一切の仮定をしません。データは\0で終わるC文字列とすることができます。単純なバイト配列、または他のフォーマットのデータであっても良い。
この2つの理由を考慮して、Redisはsdsタイプを使用してC言語のデフォルト文字列を置換して表しています。sdsは追加と長さ計算を効率的に実現することができます。
sdsの実現
前の内容では、sdsを抽象的なデータ構造として説明してきましたが、実際には、その実現は以下の2つの部分から構成されています。

typedef char *sds;


struct sdshdr {

  // buf      
  int len;

  // buf       
  int free;

  //             
  char buf[];
};

ただし、タイプsdsはchar*の別名であり、構造sdshdrはlen、free、bufの3つの属性を保持している。
例として、以下は新しく作成されたハロルド文字列のsdshdr構造を同様に保存します。

struct sdshdr {
  len = 11;
  free = 0;
  buf = "hello world\0"; // buf        len + 1
};

len属性により、sdshdrは複雑度がθ(1）長さ計算動作。
一方、bufに余分な空間を割り当てることによって、freeを使って未使用空間の大きさを記録することができます。sdshdrは追加操作を実行するために必要なメモリの再割当回数を大幅に減少させることができます。
もちろん、sdsも操作の正確な実現に対して要求を出しました。すべての処理sdshdrの関数は正確にlenとfree属性を更新しなければなりません。
データタイプ定義
sds実現に関するデータの種類は二つあります。一つはsdsです。

  //          
  typedef char *sds; 

もう一つはsdshdrです。

  //   sds    
  struct sdshdr { 
    // buf               
    int len; 
    // buf            
    int free; 
    //            
    char buf[]; 
  }; 

ここで、sdsは文字列配列タイプchar*の別名であり、sdshdrはsdsの情報を保持し保存するために用いられる。
例えば、sdshdr.lenは、O（1）の複雑さの下でsdshdr. bufに格納されている文字列の実際の長さを取得するために使用でき、sdshdr.freeはsdshdr.bufの中にどれだけの予備空間があるかを保存するために使用される。
（ここでsdshdrはsds handlerの略語であるべきです）
sdshdrをsdsとして使う
sdsモジュールはsdshdr構造に対して、ポインタ演算によってsdshdr構造をsdsタイプのように値と処理し、必要な時にsdshdrタイプに回復させるテクニックを使用しています。
以下の関数定義によってこのテクニックを理解します。
sdsnewlen関数は新しいsds値を返しますが、実際にはsdshdr構造を作成しています。

  sds sdsnewlen(const void *init, size_t initlen) 
  { 
    struct sdshdr *sh; 
   
    if (init) { 
      //    
      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の値自体を扱う関数に遭遇した場合、直接にsdsを渡すことができます。例えば、sdstoupper関数はその一例です。
 

  static inline size_t sdslen(const sds s) 
  { 
    //  sds       sdshdr   
    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構造を計算することができます。
sdsはchar*を指すbuf（ps：そして、空き配列はメモリ空間を使わず、配列名はメモリアドレス）ですが、割り当て時はsized（struct sdshdr）＋initlen＋1を割り当て、sds-sized（strut sdshdr）でstrut sdshdrの先頭アドレスを計算することができ、lenとfreeの情報を得ることができます。

sdsavail関数はこのテクニックを使った例です。
 

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

メモリ割り当て関数の実装
Reidsの実現に関する関数は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       
    //                      
    //                
    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; 
  } 

このようなメモリ割り当て戦略は、sds値を拡張する時、いつも余分な空間を残しておいて、より多くのメモリを使うことによって、メモリを再分配する回数を減らし、次の拡張操作の処理速度を最適化することを示しています。
またredisの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; 
   
    //     
    s[curlen + len] = '\0'; 
   
    return s; 
  } 
   
  /** 
   *    char     sds    
   */ 
  sds sdscat(sds s, const char *t) 
  { 
    return sdscatlen(s, t, strlen(t)); 
  }