dict

dict.h dict.c

dict是redis中定義的一個hashtable。

它的資料結構是這樣的

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

typedef struct dictType {
    uint64_t (*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;

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[];
    long rehashidx; 
    unsigned long iterators; 
} dict;
           

dictEntry是hashtable中的節點，它儲存了value和key，還有一個指向另一個dictEntry的指針，指向另一個和他被分到同一個數組節點的dictEntry。

dictType則儲存了一些hashtable需要用到的函數的指針。

dictht則是整個hashtable中實際儲存資料的表。這樣的表在同一個hashtable中有兩個。多出來的一個他們會在擴容的時候被用到，我們在後面會介紹。table字段則是一個指向dictEntry數組的指針，size是數組的大小，sizemask是給dictEntry安排位置的掩碼，用來替代求餘運算，used是目前裝載的dictEntry數量。

正主dict包含了一個dictType，reshashidx表示擴容的進度，iterators表示dict的疊代器。

dict的初始化

static void _dictReset(dictht *ht)
{
    ht->table = NULL;
    ht->size = ;
    ht->sizemask = ;
    ht->used = ;
}
dict *dictCreate(dictType *type,
        void *privDataPtr)
{
    dict *d = zmalloc(sizeof(*d));

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

沒什麼特别的地方，初始化各字段。

int dictResize(dict *d)
{
    int minimal;
    //檢查是否可以擴容
    if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;
    //檢查是否是dictht的初始化，如果是則按照dictht的最小空間擴容。
    minimal = d->ht[].used;
    if (minimal < DICT_HT_INITIAL_SIZE)
        minimal = DICT_HT_INITIAL_SIZE;
    return dictExpand(d, minimal);
}

int dictExpand(dict *d, unsigned long size)
{
    dictht n; 
    //擷取擴容到目标，每次擴容到原來的2倍，_dictNextPower就是下一個2次幂
    unsigned long realsize = _dictNextPower(size);

    if (dictIsRehashing(d) || d->ht[].used > size)
        return DICT_ERR;
    if (realsize == d->ht[].size) return DICT_ERR;

    n.size = realsize;
    //reasize是2次幂，股realsize-1用二進制表示則每一位上都是1。
    n.sizemask = realsize-;
    //給dictht中的dictEntry數組申請空間
    n.table = zcalloc(realsize*sizeof(dictEntry*));
    n.used = ;

    //如果是dictht的初始化，新生成的dictht則交給ht[0]指針
    if (d->ht[].table == NULL) {
        d->ht[] = n;
        return DICT_OK;
    }
    //如果不是，則把新生成的dictht交給ht[1]指針
    d->ht[] = n;
    d->rehashidx = ;
    return DICT_OK;
}
           

dictResize是個很有意思的過程。它根據新的大小生成新的dictht然後直接把新的dict交給ht[1]指針，同時維護了兩個表。然後通過dictRehash遷移資料

int dictRehash(dict *d, int n) {
    //設定遷移數量
    int empty_visits = n*;
    if (!dictIsRehashing(d)) return ;
    //遷移循環
    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;

        assert(d->ht[].size > (unsigned long)d->rehashidx);
        while(d->ht[].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        //找到一個非空的table節點
        de = d->ht[].table[d->rehashidx];
        //把連結清單上的節點逐個遷移
        while(de) {
            unsigned int h;

            nextde = de->next;
            h = dictHashKey(d, de->key) & d->ht[].sizemask;
            de->next = d->ht[].table[h];
            d->ht[].table[h] = de;
            d->ht[].used--;
            d->ht[].used++;
            de = nextde;
        }
        //清空原table節點
        d->ht[].table[d->rehashidx] = NULL;
        //遷移進度更新。
        d->rehashidx++;
    }

    //檢查是否遷移完成
    if (d->ht[].used == ) {
        zfree(d->ht[].table);
        d->ht[] = d->ht[];
        _dictReset(&d->ht[]);
        d->rehashidx = -;
        return ;
    }

    return ;
}
           

可以看到，這個遷移資料是有數量限制的，隻遷移一定數量的資料，如果沒遷完就先放着。

同時再有這兩個函數

//擷取目前時間
long long timeInMilliseconds(void) {
    struct timeval tv;

    gettimeofday(&tv,NULL);
    return (((long long)tv.tv_sec)*)+(tv.tv_usec/);
}

int dictRehashMilliseconds(dict *d, int ms) {
    long long start = timeInMilliseconds();
    int rehashes = ;

    while(dictRehash(d,)) {
        rehashes += ;
        if (timeInMilliseconds()-start > ms) break;
    }
    return rehashes;
}
           

可以看出來這兩個函數是用來控制遷移的時間的。如果hashtable過大，則一次性遷移完需要的時間實在太多，長時間處理會影響整個系統的性能。

redis的解決方案是螞蟻搬家式的。隻在dictRehash中大規模的遷移一次，然後在之後的每次增删查改中都攤派一次遷移工作，直到整個dictht遷移完成。

可以看到在dictAdd， dictDelete， dictFind， dictGetEandomKey等函數中都包含了

if (dictIsRehashing(d)) _dictRehashStep(d);
           

他們都會在執行過程中完成一組遷移。

那麼，如何保證在遷移完成前的正确性呢？

正确性就是靠dict中的rehashidx字段來保證的，它記錄了遷移的進度。

如果在增删查改中，發現涉及的key的hash指向table中的第i項，那麼就會先拿i和rehashidx比較，看看table中第i項的連結清單已經是否被遷移了，如果被遷移了，則到ht[1]中尋找，如果沒有遷移，則到ht[0]中尋找。

其他的增删查改沒什麼特别之處。

整個hashtable的實作似乎和JDK的非常相似。唯一的差別是這裡的hastable不會在連結清單過長的時候自動轉換為紅黑樹。