Redis dict源码分析

引言

Redis作为一个开源的NoSql数据库具有很大的使用率。最近闲来读一下Redis的源代码。学习一下各路大神的编程思想。是对自己很大的帮助。阅读的时候写个文章。记录一下自己的收货，也给大家一起分享分享。

HashTable

HashTable作为一个大家常用的kv数据存储容器，大家肯定都是特别的熟悉。一般的实现思想都是对key进行hash处理。根据处理得到的的keindex找到存储的位置。一般来说如果当前keyindex上有数据，那么久把当前属于同一keyindex的数据做成一个链表保存。当达到一定的阈值那么就对HashTable进行扩容，然后可以所有的数据进行重新计算keyindex，然后存储数据。查找的时候就对key计算keyindex，在keyindex下面的链表里面找出和key一样的数据。
所有一个基本的HashTable就是拥有一个数组存放对keyindex的数据，这个数组的每个元素就存放着一个链表。但是这样一个设计一般来说是米有问题的。但是如果在数据特别特别大的时候。就会有一个问题。当我们插入一个数据的时候。我们需要对这个HashTable进行扩容。这个时候根据处理的线性来说。如果我们的数据越大，那么我们所需要的重新hash的时间就越长。这个处理的时候，会占用掉我们的线程，并且会没有特殊处理的话。该table是不能再进行操作的。这个时候就会造成性能的急剧下降。这个是对于高性能来说是不能容忍的。所以我们来看下Redis是怎么处理的。

基本数据结构

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

typedef struct dictType {//dict对key value处理方法
    unsigned int (*hashFunction)(const void *key);//hash
    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 {//dict的hashtable  这个hashtable就可以对应成为一个我们普通的HashTable
    dictEntry **table; //存储记录的table
    unsigned long size; //记录table数组的大小
    unsigned long sizemask;//用于计算keyindex的具体位置
    unsigned long used;//当前ht的存储数据的数量
} dictht;

typedef struct dict {
    dictType *type;//key value的操作方法
    void *privdata;//创建时候赋予的私有数据
    dictht ht[2]; //两个HashTable 是两个
    long rehashidx; //当前rehash进行的位置
    int iterators; //有几个迭代器
} dict;

dictEntry 是一个链表。它存放着相同keyindex的数据
dictType 作为对HashTable key value数据的操作。
dictht 一个简单的HashTable和我们前面所讨论的基本HashTable一致
dict 使用dictht来实现Redis需要的HashTable。主要特点是拥有两个存放数据的HashTable

HashTable Add

读懂一个代码就要读懂他的流程。所以我们来从流程看代码。
我们来看一下如果我们一般的HashTable的增加一个元素的操作会是啥喃，一般来说就是下面的两步。
1.判断HashTable的存储空间是否足够。不够就扩容，不能扩容就GG。
2.计算Key的index，然后找到位置。一般来说找到一个一样的key就代表错误。正确的话就在这个位置上的列表插入我们的key vlaue数据。（一般来说如果是需要新建一个存放key value的数据结构，那就建，如果是预分配的那就用，没啥特别的）
咱们这种方法在Redis里面也是一样的实现方法。所以喃我们就来看扩容。

HashTable扩容

static unsigned long _dictNextPower(unsigned long size)
{
/*
保证一下每次返回的size是2的整数和最大size的限制
*/
    unsigned long i = DICT_HT_INITIAL_SIZE;

    if (size >= LONG_MAX) return LONG_MAX;
    while(1) {
        if (i >= size)
            return i;
        i *= 2;
    }
}
//检查有米有在进行rehash
#define dictIsRehashing(d) ((d)->rehashidx != -1)

/* Expand or create the hash table */
int dictExpand(dict *d, unsigned long size)
{
    dictht n; /* the new hash table */
    unsigned long realsize = _dictNextPower(size);//计算出一个2标准的size

    /* the size is invalid if it is smaller than the number of
     * elements already inside the hash table */
    if (dictIsRehashing(d) || d->ht[0].used > size)//新的size要比原来的已经用的多
        return DICT_ERR;

    /* Rehashing to the same table size is not useful. */
    if (realsize == d->ht[0].size) return DICT_ERR;//没变化的size就没啥改变头

    /* Allocate the new hash table and initialize all pointers to NULL */
    n.size = realsize; //把这个新的大小的HashTable初始化
    n.sizemask = realsize-1;
    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) {//这种是初始情况下当前table都还没数据
        d->ht[0] = n;
        return DICT_OK;
    }

    /* Prepare a second hash table for incremental rehashing */
    d->ht[1] = n;//有数据的话就把它给dict的第二个HashTable等于就是把第二个HashTable初始化下
    d->rehashidx = 0;//标记当前rehashidx
    return DICT_OK;
}
/* 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;//当前没有进行rehash操作

    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 */
        assert(d->ht[0].size > (unsigned long)d->rehashidx);//小了就是内存错误了
        while(d->ht[0].table[d->rehashidx] == NULL) {//这是一个空节点
            d->rehashidx++;//往前走一个index
            if (--empty_visits == 0) return 1;//空节点走完了停止rehash
        }
        de = d->ht[0].table[d->rehashidx];//拿出这个节点的list
        /* Move all the keys in this bucket from the old to the new hash HT */
        while(de) {//找到这个节点的数据取出来放入到第二个HashTable去 然后指向下一个节点
            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++;//后移idx
    }

    /* Check if we already rehashed the whole table... */
    if (d->ht[0].used == 0) {//ht0里面使用的已经没了
        zfree(d->ht[0].table);//进行释放
        d->ht[0] = d->ht[1];
        _dictReset(&d->ht[1]);
        d->rehashidx = -1;//标记rehash完成
        return 0;
    }
//返回1 代表rehash还没有完成 0 rehash完成了
    /* More to rehash... */
    return 1;
}
static void _dictRehashStep(dict *d) {//进行一步rehash操作
    if (d->iterators == 0) dictRehash(d,1);
}

我们来看expand代码。他的操作很简单。如果当前的dict米有数据，就创建一个跟size相关的格式化大小的dictht放入ht0,如果是有数据。就创建来赋值给ht0。并且标记idx为0
rehash方法。增加了一个最大更新hash槽数量。更新每个hash槽的操作都是找出这个槽，遍历这个槽的list然后把取出来的数据放到新的hashtable。根据rehashidx来知道开始的位置。
根据这两个代码喃就发现expand就完成个空间分配。rehash完成转移操作（从0到1如果转移完成就又从1到0这个时候就rehash完成了）。rehash传入最大的转移插槽数。可以保证及时的性能。
然后各处塞满了_dictRehashStep 当然你也可以手动调用rehash。

HashTable 插入

static int _dictExpandIfNeeded(dict *d)//判断是不是要扩容
{
    /* Incremental rehashing already in progress. Return. */
    if (dictIsRehashing(d)) return DICT_OK;

    /* If the hash table is empty expand it to the initial size. */
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

    /* If we reached the 1:1 ratio, and we are allowed to resize the hash
     * table (global setting) or we should avoid it but the ratio between
     * elements/buckets is over the "safe" threshold, we resize doubling
     * the number of buckets. */
    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
    {
        return dictExpand(d, d->ht[0].used*2);
    }
    return DICT_OK;
}

/* Returns the index of a free slot that can be populated with
 * a hash entry for the given 'key'.
 * If the key already exists, -1 is returned.
 *
 * Note that if we are in the process of rehashing the hash table, the
 * index is always returned in the context of the second (new) hash table. */
static int _dictKeyIndex(dict *d, const void *key)//查找keyindex
{
    unsigned int h, idx, table;
    dictEntry *he;

    /* Expand the hash table if needed */
    if (_dictExpandIfNeeded(d) == DICT_ERR)//判断扩容不
        return -1;
    /* Compute the key hash value */
    h = dictHashKey(d, key);//算出keyindex
    for (table = 0; table <= 1; table++) {//看下这个插槽有没有
        idx = h & d->ht[table].sizemask;
        /* Search if this slot does not already contain the given key */
        he = d->ht[table].table[idx];//找到插槽
        while(he) {
            if (key==he->key || dictCompareKeys(d, key, he->key))//判断有米有一样的key
                return -1;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;//只有在rehash的情况下ht1才会有数据
    }
    return idx;
}

dictEntry *dictAddRaw(dict *d, void *key)
{
    int index;
    dictEntry *entry;
    dictht *ht;

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

    /* Get the index of the new element, or -1 if
     * the element already exists. */
    if ((index = _dictKeyIndex(d, key)) == -1)//找出keyindex
        return NULL;

    /* Allocate the memory and store the new entry.
     * Insert the element in top, with the assumption that in a database
     * system it is more likely that recently added entries are accessed
     * more frequently. */
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];//如果是rehash状态下就插入ht1否则ht0
    entry = zmalloc(sizeof(*entry));//分配个保存空间
    entry->next = ht->table[index];//维持list
    ht->table[index] = entry;
    ht->used++;//增加使用数目

    /* Set the hash entry fields. */
    dictSetKey(d, entry, key);
    return entry;
}
int dictAdd(dict *d, void *key, void *val)
{
    dictEntry *entry = dictAddRaw(d,key);//分配给保存空间

    if (!entry) return DICT_ERR;
    dictSetVal(d, entry, val);//保存数据
    return DICT_OK;
}

插入操作是当前是rehash状态下的话就会被插入到ht1的那个HashTable（因为插入0的话0的有些插槽的数据已经被rehash过了<idx > keyindex>）其他操作都是常规操作。
后面的删除修改就不在叙述了。

总结

Redis实现了一个常规的HashTable即dictht 他拥有散列和保存功能。dict 使用两个dictht 他们的作用分别是
ht0:在没有rehash的时候，他作为唯一保存数据的位置，所有的插入，删除，查找等操作都只在他上面运行。在进行rehash的时候，他是作为一个元数据往ht1里面写数据。没有插入功能，但是具有删除和查找功能。
ht1:在没有rehash的时候他是个NULL所有啥都不会干。在rehash的时候，接收ht0来的元数据。这时候插入功能只会在ht1上。查找和删除功能也有。当rehash完成的时候，他会被赋值给ht0然后自己被情况。
Redis通过两个dictht来实现一次不全部完成rehash，但是也保证一个HashTable的全部功能。通过穿插的操作来碎片化rehash的时间，保证及时性。总体来说还是一个很值得学习的处理方式。