Redis学習エッセイ (1)

I. Redisのデータ構造とオブジェクト

redisにはSDS、連鎖リスト、辞書、ジャンプテーブル、整数コレクション、圧縮リストなどのデータ構造があります。これらのデータ構造はredisを操作するために使われるわけではなく、 文字列オブジェクト、リストオブジェクト、ハッシュオブジェクト、コレクションオブジェクト、 順序付きコレクションオブジェクトなどのオブジェクトを使います。データ構造はこれらのオブジェクトの基礎となる実装です。例えば、ハッシュオブジェクトの基本的な実装は圧縮リストやハッシュテーブルかもしれません。

1.データ構造

SDS: Simple Dynamic Stringの略。SDS はデータベースで文字列を保持するために使用されるだけでなく、 バッファとしても使用されます。AOF モジュールでは AOF バッファとして、 クライアントステートではバッファとして使用されます。

• SDSの実施

  // redis ziplistのSDSはsdsで表される。.h/sdshdr 構造の定義
  typedef struct sdshdr {
   int len; // 使用スペース
   int free; // 未使用スペース
   char buf[]; // バイト配列、文字列の格納に使用される。
  } sdshdr;
  

• Cストリングスに対するSDSの利点

  文字列の長さを得るための複雑さが一定である；
  バッファオーバーフローをなくす；
  文字列を変更する際のフルメモリーの割り当て回数を減らす；
  バイナリセーフ
  

連鎖テーブル: 連鎖テーブルはredisで広く使われています。例えば、リストキーの基本的な実装の一つは連鎖テーブルです。リスト内の要素が多い場合や、リスト内の要素が長い文字列である場合、基礎となるリストは連鎖テーブルとして実装されます。redisサーバはリンクリストを使って複数のクライアントの状態情報を保存し、リンクリストを使ってクライアントの出力バッファを構築します。

• 連鎖テーブルの実装

  // redis adlistの連鎖リストがadlistでエンコードされている。.h/list 構造の定義
  typedef struct list {
   listNode *head; //  
   listNode *tail; //  
   unsigned long len; // リンクリストの長さ
   void*(*dup)(void *ptr); // コピー機能
   void*(*free)(void *ptr); // リリース関数
   int(*match)(void *ptr, void *key); // 比較関数
  } list;
  typedef struct listNode {
   struct listNode *prev;
   struct listNode *next;
   void *value;
  } listNode;
  

辞書：辞書はredisで広く使われており、redisデータベースの基本的な実装は辞書に基づいています。辞書はデータベースを実装するだけでなく、ハッシュキーの基礎となる実装の1つでもあります。辞書はハッシュテーブルとして実装されています。

• 辞書の実装

  // redis ziplistの辞書はdictで構成される。.h/dict 構造の定義
  typedef struct dict {
   dictType *type; // 型固有の関数
   void *privdata; // プライベート・データ
   dictht ht[2]; // 辞書は通常ht[0],htのみ[0] htがリハッシュに使われる。[1]
   int rehashidx; // 現在のリハッシュの進行状況を記録し、リハッシュが進行中でない場合は-1とする；
  } dict;
  // redis 使用するハッシュ・テーブルはdict.h/dictht 構造の定義
  typedef struct dictht {
   dictEntry **table; // ハッシュ・テーブル・データ
   unsigned long size; // ハッシュ・テーブルのサイズ
   unsigned long sizemask; //  =size - 1，rehash 負荷率の計算に使用する場合
   unsigned long used; // ハッシュ・テーブルに存在するノードの数
  } dictht;
  // ハッシュ・テーブルのノード構造
  typedef struct dictEntry {
   void *key;
   union {
   void *val;
   uint64_tu64;
   int64_ts64;
   }v;
   struct dictEntry *next;
  } dictEntry;
  

• ハッシュアルゴリズム

  // ハッシュ値とインデックス値を計算するためにハッシュ関数を使う。，
  アルゴリズムが正規の入力であっても良いランダムスコアを与えることができる。
  hash = dict->type->hashFunction(key);
  index = hash & dict->ht[x].sizemask;
  // ハッシュの衝突があった場合、redisはチェーン・アドレス・メソッドを使って衝突を解決する。ヘッダー挿入が速い。
  

• 蒸し返し 膨張と収縮

  rehash 展開のタイミング
   1）サーバーが現在BGSAVEまたはBGREWRITEAOFコマンドを実行しておらず、負荷率が1以上である；
   2）サーバーが現在BGSAVEまたはBGREWRITEAOFコマンドを実行中で、負荷率が5以上である；
  rehash タイミングを縮める
   1）負荷率が0以下である。.1
  負荷率計算：負荷_factor = ht[0].used / ht[0].size
  rehash  
   1）ハッシュテーブルhtをエンコードする[1] 空間を割り当てる。空間のサイズは、リハッシュ操作とhtの比較に依存する。[0].used コードのサイズ。もし
  展開操作である。，ht[1] 最初のサイズがht以上である。[0].used * 2 2のn乗である。縮約オペレーションである場合，ht[1]
  最初のサイズがht以上である。[0].used 2のn乗。
   2）htを変換する[0] htのすべてのキーをhtにリハッシュする。[1] htをリリースしている間[0], htを変換する[1] htに設定する[0]， 
  ht[1] 空のハッシュ・テーブルを作成する。
   rehash 処理は一元化されず、インクリメンタルである。dict構造体にメンバrehashidxがあることに注意。，
  現在のリハッシュの進行状況は記録されているので、漸進的なリハッシュ処理は以下のようになる。:
   1) htの場合[1] スペースを確保する；
   2）rehashidxを0にセットし、リハッシュが正式に開始されたことを示す；
   3）辞書を追加、削除、修正、検索するたびに、現在の操作に加えて、rehashidxに対応するすべてのキーと値のペアをリハッシュする。
  ht[1]，すべてのリハッシュの後、rehashidxに-1をセットする。
  

ジャンピングテーブル：各ノードに他のノードへの複数のポインタを保持することで、高速にアクセスできる順序データ構造。Redisは、順序コレクションの基礎実装の1つとしてジャンピングテーブルを使用します。Redisは、順序付きコレクションが多数の要素を含む場合や、順序付きコレクション内の要素のメンバが長い文字列である場合に、順序付きコレクションキーの基礎実装としてジャンプテーブルを使用します。順序付き集合の実装に使用されるだけでなく、ジャンプテーブルはクラスタノードの内部データ構造としても使用されます。

// redis スキープリストがredisによってエンコードされている。.h/zskiplist 構造の定義
typedef struct zskiplist {
 struct skiplistNode *head, *tail; // 先頭と末尾のポインタ
 unsigned int length; // テーブルのノード数
 int level; // テーブルの中で最大のレベル数を持つノードのレベル数。
}
// skiplistノードがredisによって実装されている。.h/zskoplistNode  
typedef struct zskiplistNode {
 struct zkskiplistLevel {
 struct zskiplistNode *forward; // 前方ポインタ
 unsigned int span; //  
 } level[];
 struct zskiplistNode *backward; // 後方ポインタ
 double score; //  
 robj *obj; // メンバー・オブジェクト
}
// 注：各スキップリストの高さは1から32の間の乱数である。

整数コレクション: コレクションキーの基本実装のひとつです。コレクションが整数値の要素のみを含み、コレクションの要素数が少ない場合、redisはコレクションキーの基礎実装として整数コレクションを使用します。

圧縮リスト: 圧縮リストはリストキーやハッシュキーの基本実装の一つです。リストキーの値に少数のリスト項目が含まれ、それぞれが小さな整数値か短い文字列である場合、redisはリストキーの基本実装として圧縮リストを使用します。

2、オブジェクト：Redisは、キーと値のペアのデータベースを実現するためのデータ構造を使用していませんが、これらのデータ構造に基づいてオブジェクトシステムを作成します。このシステムには、文字列オブジェクト、リストオブジェクト、ハッシュオブジェクト、コレクションオブジェクト、およびこれら5種類のオブジェクトの順序付きコレクションオブジェクトが含まれます。

// redis オブジェクト構造がredisObject構造で定義されている。
typedef struct redisObject {
 unsigned type:4; //  
 unsigned encoding:4 //  
 void *ptr; // 基礎となる実装データ構造へのポインタ
 unsigned *lru:22; // アイドル時間
 ...
}
type 属性はオブジェクトのタイプを記録する。キー・オブジェクトは常に文字列オブジェクトなので、type keyは値オブジェクトの型を返す。
encoding 属性には、オブジェクトの基本実装としてどのデータ構造が使われているかを記録する。コマンド・オブジェクトのエンコーディング・キー
を表示する。

リスト・オブジェクト：エンコーディングはziplistまたはlinkedlist。