Incremental Rehash

The Implication of Incremental Rehashing in Redis

本文适合Java中高级、有HashMap的基础，略懂C基础的读者进行阅读。

关键词: incremental rehashing, Redis, HashMap

什么是Hash

散列函数（或散列算法，又称哈希函数，英语：Hash Function）是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。完美的散列算法可以均匀的真正随机输出。在Redis中，通过MurmurHash2算法（位于源码的dictGenHashFunction）返回的一个32位的unit；在Java中，HashCode由JVM的object.c 实现，同样返回uint32。

在本文我们只考虑理想情况，只需要知道上述Hash算法将返回一个[0,Integer.MAX_VALUE-1]之间均匀分布，且与输入值一一对应的正整数即可。

HashMap的扩容操作

在Java的HashMap源码中，当put操作中，如果已经使用了0.75的空间，将进行扩容(resize)操作。在不考虑链地址与红黑树等特例的情况下，步骤如下：

Expand: 新建一个为原数组oldTab两倍容量的新数组newTab
Rehash: 对oldTab进行for循环，找出不为空的元素，并放入新数组中，伪代码如下

int newCap = oldCap * 2;
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
oldTab.forEach((Node e) -> {
  newTab[e.hash & (newCap - 1)] = e;
})

可以看出，此操作为高耗时的O(N)操作，不仅要分配大内存，而且还要把旧数组进行for循环复制。如果HashMap的元素成千上万，在进行put操作时如果遇到了扩容，将造成极大的操作延迟。

Redis中的HashTable

在Redis中，由于它对实时性要求更高，因此使用了渐进式rehash

HashTable的构造

在Redis中，Hash表是这样定义的，可以看出，同样采用数组加链地址，redis与Java中的HashMap并没有什么不同

// dict.c and dict.h
// dict hashtable
typedef struct dictht {
    // 指针的指针，可以看成是一个全是指针的数组, 用Java写是这样的<dictEntry*>[]
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    // 供链地址冲突使用，本文不考虑此特例
    struct dictEntry *next;
} dictEntry;

正常情况下添加K-V Entry的实现

在没有冲突、没有替换、扩容的场景下，SET调用栈如下

void setCommand(t_string.c);
void setGenericCommand(t_string.c);
void setKey(db.c);
void dbAdd(db.c);
static int dictAdd(dict.c)
dictEntry *dictAddRaw(dict.c)

具体代码就不放了，先为Entry分配内存，接着放入ht数组的index中，最后写入指针的k-v数据。

Redis扩容实现

当redis中所用容量达到1.0左右时，在SET操作时将触发扩容操作；亦或在Redis启动时也会进行初始化扩容。扩容与Java一样，首先创建了一个两倍长度的数组，接着进行reHash将旧值放入新值中。

Expand

伪代码如下，ht就是上面的结构体。其中ht[0]是旧的hash表，ht[1]是新的hash表。可以看出通过zcalloc分配了一个双倍的内存。

// dict.c dictExpand
var realsize = 2 * ht[0].used;
// 创建一个新的 dictht，并分配内存
var ht[1] = {
  size: realsize,
  sizemask: realsize - 1,
  table: zcalloc(realsize*sizeof(dictEntry*)),
  used: 0
}

ReHash实现

由于reHash需要大量的数据，很难构造出断点，因此可以在Redis初始化时，在如下代码中打断点，这样就可以分析详细过程了。

// file:scr/dict.c
static void _dictRehashStep(dict *d) {
    if (d->iterators == 0) dictRehash(d,1);
}

首先上结论，如果正在进行ReHash：

当进行SET操作时，它将首先移动一个旧元素到新数组，再把K-V放入新的数组中
当进行GET操作时，它将首先移动一个旧元素到新数组，再依次从旧数组、新数组中搜索Value

上述操作每次只移动一个元素，类似于某个耐心的银行，取钱时扣一点，存钱时扣一点，最终总能扣完。这样就减少了一次性压垮导致双输的风险。

接下来开始分析移动一个旧元素到新数组的过程，即上文dictRehash(d,1)的过程。由于dictRehash的第二个参数在SET与GET场景中始终为1，因此下文代码去掉了部分内容。

int empty_visits = n*10;
dictEntry *de, *nextde;
// 遍历旧表ht[0]的数组，从rehashidx 到最 rehashidx+10，如果连续10次都为空，放弃此次机会
// 当然计数器rehashidx也相应增长了10
while(d->ht[0].table[d->rehashidx] == NULL) {
    d->rehashidx++;
    if (--empty_visits == 0) return 1;
}
// 老数组中刚刚找到的 dictEntry
de = d->ht[0].table[d->rehashidx];
// 移动元素到新数组，并处理链地址冲突
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;
}
// rehash 全部完成，rehashidx置为 -1
if (d->ht[0].used == 0) {
  zfree(d->ht[0].table);
  d->ht[0] = d->ht[1];
  _dictReset(&d->ht[1]);
  d->rehashidx = -1;
  return 0;
}
d->ht[0].table[d->rehashidx] = NULL;
d->rehashidx++;

太长不看的话，总结一下rehash的过程：

rehashidx开始为0
遍历旧数组[rehashidx, rehashidx+10]共10个元素是否有entity，没有找到就等待下次机会，每处理一个值，rehashidx就加一。
如果找到了，就重新计算hash值，并放入新数组中，并处理链地址冲突;否则接着执行1
rehash 全部完成后，rehashidx置为 -1

通过上述操作，每次在进行SET/GET操作时，都会保证向前遍历旧数组1～10步，最终ht[0]将被遍历完，而ht[1]将越来越多。

总结

Redis的reHash本质上就是分而治之的方法，降低了一次压垮的风险。通过渐进式操作，分散了put/get的时间复杂度到每次操作中，当然一定程度上也增加了框架的复杂度。

参考

《Redis的设计与实现》