Redis実装の原理(2)--辞書

1、   Dict    
2.1データ構造定義dict.h

//      



typedef struct dictht {



    dictEntry **table; //       



    unsigned long size;  //     



    unsigned long sizemask; //  ，hash   



    unsigned long used; //       



} dictht;



//         



typedef struct dictEntry {



    void *key; 



    union {



        void *val;



        uint64_t u64;



        int64_t s64;



    } v;  //  ，       、uint64 int64



    struct dictEntry *next;  //             



} dictEntry;



//    



typedef struct dict {



    dictType *type;



    void *privdata;



    dictht ht[2];



    int rehashidx; //      -1        



    int iterators; //      



} dict;



//     



//   dictType                 ，       type  



typedef struct dictType {



       // hash  



unsigned int (*hashFunction)(const void *key);



// key   



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



// value   



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



// key   



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



// key   



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



// value   



    void (*valDestructor)(void *privdata, void *obj);



} dictType;

 
2.2 hash
typeのhashFunctionメソッドを呼び出してkeyのhash値を計算し、redis内部で使用されるhashアルゴリズムはAustin Applebyが開発したMurmurHash 2アルゴリズムである
h = d->type->hashFunction(key)
keyのインデックス値を計算し、ht[0]で検索し、rehashが見つからない場合はht[1]で検索し続けます.
idx = h & d->ht[table].sizemask
ハッシュ競合の解決ではredisが採用するファスナー法では,同じインデックス値のkeyが1つの単一チェーンテーブルに格納されるため,インデックス値が決定された後も対応する単一チェーンテーブルで検索する必要がある.

while(he) {



            if (dictCompareKeys(d, key, he->key))



                return -1;



            he = he->next;



        }

 
2.3 rehash
辞書の使用効率を保証するために、redisは辞書構造に対して定期的にrehashのメカニズムを採用した.rehashは再CPUの操作であるため、過程中に対外的に応答しない状況を避けるために、ここでは増分rehashの最適化を行った.
rehashの流れは次のとおりです.
1)空のhashテーブルを新規作成し、sizeは2 n以上の整数である.

unsigned long i = DICT_HT_INITIAL_SIZE;



if (size >= LONG_MAX) return LONG_MAX;



while(1) {



    if (i >= size)



       return i;



    i *= 2;



}

 
2)ht[0]のkeyをhashとindexを再計算し、ht[1]にインデックスし、ht[0]の対応するインデックス値を空にする
3)ht[0]のデータをすべてht[1]にrehashした後ht[1]をht[0]に設定し、新しいhtを作成する[1]
インクリメンタルrehashは、ステップ2を最適化し、毎回1つのindexのkeyのみをrehashし、rehash中に読み書き操作を制限する.
1)読み:ht[0]を先に調べ、ht[1]で検索しなかったら
2)書き込み:rehashプロセスでは、新しいkeyはht[1]にのみ書き込まれ、インデックスに対応するすべてのkeyがht[1]に再hashされます.
最終的には、ある時点ht[0]のすべてのkeyがht[1]に再hashされる.
 
http://www.yancey.info/?p=180