Redis之字典内部

【内部使用到字典的结构】
>hash
>整个Redis库中的key和value也组成了一个全局字典
>带过期时间的key集合
>zset中存储value和score值的映射关系也是通过字典结构实现的

struct RedisDb {
    dict* dict; // all keys key=>value
    dict* expires; // all expired keys key=>long(timestamp)
    ...
}

struct zset {
    dict *dict; // all values value=>score
    zskiplist *zsl;
}

【字典内部结构】
字典结构内部包含两个hashtable，通常情况下只有一个有值，但在字典扩容缩容时，需要分配新的hashtable，然后进行渐进式搬迁，这时候两个hashtable存储的分别是旧的hashtable和新的hashtable，等到搬迁结束后，旧的hashtable被删除，新的hashtable取代。

hash的结构与Java中的hashmap一样，是在一个数组上挂上一个单链表。
单链表结构体：

struct dictEntry {
    void* key;
    void* val;
    dictEntry* next;
}

数组(hashtable)结构体：

struct dictht {
    dictEntry** table;
    long size; //数组长度
    long used; //元素个数
    ...
}

【渐进式rehash】
Redis中有两种搬迁的手段，一个是在字典增加元素的时候进行懒处理；另一个是定时任务，两者结合完成整个迁移。这对于比较大的hash来说，可以有效防止hash过大而带来的搬迁卡顿服务器的情况。
字典添加元素的流程代码如下：

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing){
    long index;
    dictEntry *entry;
    dictht *ht;
    
    //如果处于搬迁中，则进行小步搬迁
    if(dictIsRehashing(d)) _dictRehashStep(d);
    
    //-1表示该元素存在
    if((index=_dictKeyIndex(d, key, dictHashKey(d,key),existing))==-1){
    return NULL;
    }
    
    //分配新的空间，此时如果是搬迁过程，那么就将元素挂到新数组下
    ht = dictIsRehashing(d) ? &d->ht[1]:&d->ht[0];
    entry = zmalloc(sizeof(*entry));
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used++;
    
    dictSetKey(d, entry, key);
    return entry;
}

定时搬迁的流程：

void databaseCron(){
    ...
    if(server.activerehashing){
        //可以看到定时任务中的次数也是额定最大值的
        for(j=0;j<dbs_per_call;j++){
            int work_done = incrementallyRehash(rehash_db);
            if(work_done){
                break;
            }else{
                //如果这个槽不需要rehash，转入下一个槽（db0，db1，...）
                rehash_db++;
                rehash_db %= server.dbnum;
            }
        }
    }
}

【查找过程】
首先根据key进行hash计算，并与size求模运算，得到的结果即数组的下表index，再在这个位置的链表上进行查询。只有hash的映射均匀，二维链表的长度才不会很远。
所以hashtable性能如何完全取决于hash函数的质量，如果hash函数可以将key打散得比较均匀，那么这个hash函数就是个好函数。
Redis字典默认的hash函数是siphash。
【hash攻击】
如果hashtable的性能不好，导致分布不均匀，甚至所有元素都集中到个别链条中，那么查找性能就会下降，有限的服务器计算资源可能会被hashtable的查找效率拖垮。
【扩容缩容条件】
扩容
正常情况下，当hash表的元素个数等于第一维数组的长度时，就会开始扩容，大小为原先的2倍。
但当Redis做bgsave，为了减少内存页的过多分离（此时在用COW支撑快照的存储），Redis尽量不做扩容，但如果hash表已经非常满了，元素个数到达第一维数组长度的5倍，就会强制扩容。
缩容
元素个数低于数组长度的10%，就会缩容，缩容不会考虑bgsave。
【set结构】
set实现也是字典，只不过所有的value都是NULL。

【思考与扩展】
这里有一个问题，为什么缩容时不考虑bgsave。我觉得主要是空间使用率以及维护的复杂性：
1.从空间使用率上讲，缩容本身是一个不断del释放空间的过程，在大量的del元素之后，本身的父进程使用的页是不断缩小的，空间使用率是下降的，所以不考虑。
2.从另一个角度说说变化的链表元素在原先页的命中问题。缩容的时候，本身是一个大量del的过程，可能涉及到的页都已经COPY过了，这个时候剩下的1/10元素就算变化，父进程也不用大量COPY老页（在之前del时大概率已经被COPY），或者说概率很小。但是扩容如果是1倍就操作，虽然set过程中，也会COPY一些老页，但是这里考虑两个问题，1.add到新页的话，老页其实是不copy的，因为老页没变化；2.如果add到老页，虽然也会copy，但是只翻了一倍的数据就copy，这里很有可能有大量的老页是没有因为add而copy到，你这个时候直接去扩容了，好了，之前数据涉及到的页都会进行一次cow，这个应该是作者说的额外的更多的cow。但是到了数据增长到5倍的时候，一方面原有的链表可能有些会很长，影响查找效率，另外，数据增长5倍，原来的老页可能因为不断地add操作都已经被复制过了，你这个时候扩容，再新去copy的概率会比之前低很多。

【参考】

《Redis深度历险核心原理与应用实践》