Redis勉強----4.辞書

4.1辞書の実現
ハッシュ・テーブルはdict.h/dictht構造によって定義されます.

typedef struct dictht{
      dictEntry **table;      //      
      unsigned long size;     //   
      unsigned long sizemask; //     size-1、       ，       
      unsigned long used;     //            
}dictht;

ハッシュ表ノード:

typedef struct dictEntry{
      void *key; //  
      union{
            void *val;
            uint64_t u64;
            int64_t s64;
      }v;
      struct dictEntry *next; //         ，    
}dictEntry;

Redisの辞書はdict.h/dict構造で表されます.

typedef struct dict{
      dictType *type;  //       
      void  *privdata; //     
      dictht ht[2];    //    
      int rehashidx;   // rehash  ， rehash     ，  -1
}dict;

typeプロパティとprivdataプロパティは、異なるタイプのキー値ペアに対して、マルチステート辞書を作成するために設定されます.
①type属性はdictType構造へのポインタであり、各dictType構造には特定のタイプのキー値ペアを操作するための関数がクラスタ化されており、Redisは用途の異なる辞書に異なるタイプの特定関数を設定します.
②privdataプロパティには、どのタイプの特定の関数に渡す必要があるかのオプションパラメータが保存されます.

typedef struct dictType{
      unsigned int (*hashFunction)(const void *key);    //         

      void *(*keyDup)(void *privdata, const void *key); //       

      void *(*valDup)(void * privdata, const void *obj); //       

      int (*keyCompare)(void *privdata,const void *key1,const void *key2); //       

      void (*keyDestructor)(void *privdata, void *key); //       

      void (*valDestructor)(void *privdata, void *obj); //       
}dictType;

4.2ハッシュアルゴリズム
データベースの下位実装として辞書が使用される場合、またはハッシュキーの下位実装として使用される場合、Redisは、MurmurHash 2アルゴリズムを使用してキーのハッシュ値を計算する.
MurmurHashアルゴリズムは最初にAustin Applebyによって2008年に発見されたが,このアルゴリズムの点は,入力されたキーが規則的であってもアルゴリズムが良好なランダム分布性を与えることができ,アルゴリズムの計算速度も非常に速いことである.アルゴリズムのホームページ:http://code.google.com/p/smhasher/
4.3キー競合の解決
Redisのハッシュ表はチェーンアドレス法を用いてキー衝突を解決する.
4.4 rehash
ハッシュ・テーブルの拡張と縮小は、rehash(再ハッシュ)操作を実行することによって実行できます.
ハッシュテーブルの拡張と収縮
条件のいずれかが満たされると、プログラムはハッシュ・テーブルの拡張操作を自動的に開始します.
1)サーバは現在BGSAVEコマンドまたはBGREWRITEAOFコマンドを実行しておらず、ハッシュテーブルの負荷銀は1以上である.
2)サーバは現在、BGSAVEコマンドまたはBGREWRITEAOFコマンドを実行しており、ハッシュテーブルの負荷銀は5以上である.

//       =            /      
load_factor = ht[0].used / ht[0].size

一方、ハッシュ・テーブルの負荷係数が0.1未満の場合、グレー化は、ハッシュ・テーブルの収縮動作を自動的に開始する

 
 
4.5    rehash
 
 
   rehash    ，  ，  ，               。     ht[1] 
 
 

 
 
 
4.7     
 
 
Ⅰ          Redis     ，           
 
 
Ⅱ Redis               ，           ，      ，       rehash   
 
 
Ⅲ               ，           ，Redis  MurmurHash2          
 
 
Ⅳ                ，                          
 
 
Ⅴ                 ，                  rehash       ，    rehash            ，        。