redis下位データ構造のdict辞書1

最近、redisのソースコードでredisを学びたいです.普段の仕事ではあまり使われていませんが、redisに興味があります.結局、性能はいいです.redisはオープンソースのプロジェクトで、ソースコードを通じてredisを理解することができます.私は后で自分の学习を通じて、redisのソースコードについての招待状を书きます.投稿の主な内容は、ソースコードを詳細に説明することなく、コード設計を分析することです.間違ったところがあれば、指摘してください.ソースコードはreids 3.0.3バージョンです.
dict辞書
一、データ構造

//    
typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;
typedef struct dictType {
    unsigned int (*hashFunction)(const void *key);    //  key    
    void *(*keyDup)(void *privdata, const void *key);    //  key   
    void *(*valDup)(void *privdata, const void *obj);    //  value   
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);//  key     
    void (*keyDestructor)(void *privdata, void *key);//  key   
    void (*valDestructor)(void *privdata, void *obj);//  value   
} dictType;
//            
/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;
//  
typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];    //     ， rehash         ，         
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;
/* If safe is set to 1 this is a safe iterator, that means, you can call
 * dictAdd, dictFind, and other functions against the dictionary even while
 * iterating. Otherwise it is a non safe iterator, and only dictNext()
 * should be called while iterating. */
typedef struct dictIterator {
    dict *d;
    long index;
    int table, safe;
    dictEntry *entry, *nextEntry;
    /* unsafe iterator fingerprint for misuse detection. */
    long long fingerprint;
} dictIterator;

二、マクロ実現の簡単な関数は三つの例を挙げる.

#define dictFreeVal(d, entry) \
    if ((d)->type->valDestructor) \
        (d)->type->valDestructor((d)->privdata, (entry)->v.val)
#define dictSetVal(d, entry, _val_) do { \
    if ((d)->type->valDup) \
        entry->v.val = (d)->type->valDup((d)->privdata, _val_); \
    else \
        entry->v.val = (_val_); \
} while(0)
#define dictSetSignedIntegerVal(entry, _val_) \
    do { entry->v.s64 = _val_; } while(0)

dictFreeValは、辞書エントリのvalueを解放するときに使用されます.実装中にdo{}while(0)を使用していないので、なぜ使用しないのか分かりませんが、追加すべきだと思います.そうしないと、使用しないと問題になります.具体的には、私のもう一つの投稿が表示されます.http://chhquan.blog.51cto.com/1346841/1358254dictSetSignedIntegerValにdo{}while(0)を付けるのは、表現形式でマクロを使用するのを阻止するためであるはずです.三、部分コード解析はdict行為の特徴が多いため、この投稿は部分コードを詳しく理解するつもりです.
1. dict_can_resize

/* Using dictEnableResize() / dictDisableResize() we make possible to
 * enable/disable resizing of the hash table as needed. This is very important
 * for Redis, as we use copy-on-write and don't want to move too much memory
 * around when there is a child performing saving operations.
 *
 * Note that even when dict_can_resize is set to 0, not all resizes are
 * prevented: a hash table is still allowed to grow if the ratio between
 * the number of elements and the buckets > dict_force_resize_ratio. */
static int dict_can_resize = 1;
static unsigned int dict_force_resize_ratio = 5;

dict_can_resizeは、dictがrehashを行うことができるかどうかを制御し、1時にrehashを許可し、0-通常はrehashを許可しないが、エントリ数/バケツ>dict_を満たす場合force_resize_ratioの場合、rehashを実行できます.dictEnableResize()またはdictDisableResize()でdict_を設定できます.can_resize.このような設定の目的は、redisがdictの保存操作を行う必要がある場合(ファイルを書く)は、dictの現在のスナップショットを保存し、dictを一定に保つことであるが、これにより辞書の書き込み操作を受信できなくなったり、rehashを行うことができなくなり、dictが要求を正常に処理できるようにするために、redisはcopy-on-writeのポリシー、すなわちdictに修正操作がある場合、dictをコピーして、保存操作と修正操作をサポートする必要があります.rehashもdictを修正するので、保存中のdictをコピーすることもあるのでdict_を使用しますforce_resize_ratioはrehashを阻止し、レプリケーションをある程度回避します.ただし、保存項目数/バケツ>dict_force_resize_ratioの場合、redisはこのときdictのエントリ数がバケツに比べて多すぎて、バケツに掛けられている元素の個数が多い可能性があり、dictの効率に深刻な影響を及ぼすと考えている.したがって、dictをコピーしても、dictのパフォーマンスを復元するためにrehashを許可する必要があります.もちろん具体的なdict_force_resize_ratioはいくらですか.実験から出るでしょう.あるいは,複製とdictの効率的な転換点をどのように測定するかも実験を行う必要があり,必ずしもエントリ/バケツではなく,具体的には実験から得られるだろう.実験がないので、私もあまり言えません.2.hashはhash値を計算する関数を計算して、具体的なアルゴリズムは私もよく知らないで、スキップします.3.ハッシュ表のリセット

//     
/* Reset a hash table already initialized with ht_init().
 * NOTE: This function should only be called by ht_destroy(). */
static void _dictReset(dictht *ht)
{
    //      table  ，      table           ，
    //          ，          table          
    ht->table = NULL;    
    ht->size = 0;
    ht->sizemask = 0;
    ht->used = 0;
}

4.dictの作成

//  dict
/* Create a new hash table */
dict *dictCreate(dictType *type,
        void *privDataPtr)
{
    dict *d = zmalloc(sizeof(*d));
    _dictInit(d,type,privDataPtr);
    return d;
}

5.dictの初期化

//   dict
/* Initialize the hash table */
int _dictInit(dict *d, dictType *type,
        void *privDataPtr)
{
    _dictReset(&d->ht[0]);
    _dictReset(&d->ht[1]);
    d->type = type;
    d->privdata = privDataPtr;
    d->rehashidx = -1;    // -1   rehash  ，>= 0  rehash 
    d->iterators = 0;
    return DICT_OK;
}

6.サイズ変更

//resize，  dict          resize，            。
/* Resize the table to the minimal size that contains all the elements,
 * but with the invariant of a USED/BUCKETS ratio near to <= 1 */
int dictResize(dict *d)
{
    int minimal;
    if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;
    minimal = d->ht[0].used;    //          resize
    if (minimal ht[0].used > size)
        return DICT_ERR;
    /* Rehashing to the same table size is not useful. */
    if (realsize == d->ht[0].size) return DICT_ERR;
    /* Allocate the new hash table and initialize all pointers to NULL */
    n.size = realsize;
    n.sizemask = realsize-1; //size-1，bit 1     ，       size          
    n.table = zcalloc(realsize*sizeof(dictEntry*));
    n.used = 0;
    /* Is this the first initialization? If so it's not really a rehashing
     * we just set the first hash table so that it can accept keys. */
    if (d->ht[0].table == NULL) {
        d->ht[0] = n;
        return DICT_OK;
    }
    /* Prepare a second hash table for incremental rehashing */
    d->ht[1] = n;
    d->rehashidx = 0;//>=0，  rehash 
    return DICT_OK;
}

7. rehash

//rehash  ，   dict  rehash
//redis         dict rehash，     rehash        rehash     ，
//   rehash            ，   n  。        ，   rehash     
//     rehash      ，           n*10   。
//redis        ，               ，        ，rehash        。
/* Performs N steps of incremental rehashing. Returns 1 if there are still
 * keys to move from the old to the new hash table, otherwise 0 is returned.
 *
 * Note that a rehashing step consists in moving a bucket (that may have more
 * than one key as we use chaining) from the old to the new hash table, however
 * since part of the hash table may be composed of empty spaces, it is not
 * guaranteed that this function will rehash even a single bucket, since it
 * will visit at max N*10 empty buckets in total, otherwise the amount of
 * work it does would be unbound and the function may block for a long time. */
int dictRehash(dict *d, int n) {
    int empty_visits = n*10; /* Max number of empty buckets to visit. */
    if (!dictIsRehashing(d)) return 0;
    //  ht[0]   ，     ，        ht[1] 。
    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;
        /* Note that rehashidx can't overflow as we are sure there are more
         * elements because ht[0].used != 0 */
    // rehashidx  ，rehashidx      rehash       
        assert(d->ht[0].size > (unsigned long)d->rehashidx);
    //       ，         empty_visits    
        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;    //  1  rehash    ，      
        }
        de = d->ht[0].table[d->rehashidx];
    //         ht[1] 
        /* Move all the keys in this bucket from the old to the new hash HT */
        while(de) {
            unsigned int h;
            nextde = de->next;
            /* Get the index in the new hash table */
            h = dictHashKey(d, de->key) & d->ht[1].sizemask; //   
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }
        d->ht[0].table[d->rehashidx] = NULL;
        d->rehashidx++;    //     rehashidx   ，    
    }
    //  ht[0]       ，   ht[1]   ht[0]，   ht[1]。
    /* Check if we already rehashed the whole table... */
    if (d->ht[0].used == 0) {
        zfree(d->ht[0].table);    //  ht[0]    
        d->ht[0] = d->ht[1];
        _dictReset(&d->ht[1]);
        d->rehashidx = -1;
        return 0;
    }
    /* More to rehash... */
    return 1;
}

rehashプロセスから分かるように、rehashプロセスではht[0]とht[1]が同時にエントリを有し、すなわち辞書内のすべてのエントリがht[0]とht[1]に分布し、このとき面倒も生じる.主に以下の問題があります:(現在、どのように解決したのかは答えません)1.keyの検索方法.2.新しいキーを挿入する方法.3.キーを削除する方法.4.dictのすべてのエントリを巡回する方法、巡回順序を確保する方法.5.rehashプロシージャがエントリを挿入、削除し続け、rehashにエラーがないことを確認する方法.6.反復器が有効で正確であることを確認する方法.