redis 字典与渐进式哈希

大家都知道 ，redis是一个基于key-value 形式的 存储系统。而字典就是一个元素类型为key-value形式的一种数据结构， 那么可以这么认为：redis本身就是一个巨大的字典。

在redis的源码，中redis自己实现了字典。

首先是实现 key-value  键值对

typeof struct dictEntry{
   void *key;
   union{
      void *val;
      uint64_tu64;
      int64_ts64;
   }
   struct dictEntry *next;
}
           

之后又基于 dictEntry 实现了  哈希表类型

typedef struct dictht {
   dictEntry **table;//哈希表数组
   unsigned long size;//哈希表大小
   unsigned long sizemask;//哈希表大小掩码，用于计算索引值
   unsigned long used;//该哈希表已有节点的数量
}
           

这里需要思考一下，字典和哈希表有什么不同？

字典是将键映射到值（最终就是内存）上，为什么要这么做呢？当然是为了能够快速获得对应数值，不必像遍历数组一样挨个查询。因此，字典的实现，除了使用散列函数/哈希，还可以有其他方法，比如C++ STL 中的  map，其实现利用的是红黑树。

既然字典的实现可以有多种方式，那么该怎么定义字典类呢？

学习过python的同学都知道，dict类有很多内置方法。redis 当然是不需要那么多的

这里可以看redis给出了其自己的方案，如下所示

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;
           

这是redis中字典类的基类，其中只有几个方法/属性。

刚才我们讲到，有时候字典确实可以视作一个哈希表。因此如果只是为了实现字典的功能，只要实现哈希表基本上可以了。

但是redis 还做了一层改进。先给出代码如下：

typedef struct dict {
    dictType *type;
    void *privedata;
    dictht  ht[2]; // 定义两个 哈希表，用来渐进式地哈希 
    int rehashidx;  //flag位，表明当前在渐进式哈希过程中的状态

}
           

以上是redis实际使用的字典的类型

这里于我们设想的字典类型有哪些地方不同呢，除了一个dictType  类型的和私有的data，多出了两个ht[2] 和rehashidx 。

这是用来干嘛的呢？

回到上文，dictht 是哈希表类型的实现，按理说一个字典其内部有一套哈希表即可，但是这里实现了两个。

这是为什么呢？

这里就要设计到redis字典中的渐进式哈希的设计理念了。

我们先从单个 哈希表开始讲起。

哈希表扩容

对于哈希操作，我们知道，其实质是在有限的空间上按特定算法映射数据和内存。这意味着，在一开始，哈希表就必须设定大小。但是随着哈希次数/新增数据的增多，可用空间会越来越小。虽然可以采用开放寻址法和链地址法（拉链法）解决冲突，但这也增加了以后查询的成本，随着数据增多，给哈希表扩容是无法避免的。

既然要给哈希表扩容，我们则需要设立一个标准/阈值，一旦哈希表的负载因子（元素 个数/哈希列表长度）过了阈值则启动扩容。  

java hashmap扩容

对于 扩容这一操作 ，java中的 hashmap  是通过其内置的resize()方法进行扩容的。当负载因子超过0.75，便会进行扩容。

这会在临界点造成一个现象，即刚好插入新节点时，要进行扩容，之前的节点都需要重新计算哈希值，这会使得这个新节点的插入看起来比以往慢很多。

（详情点击--java hashmap扩容）

redis 字典扩容

redis 是一个高性能的数据库，其目标只有两个：快，更快！

由于其自身是基于key-value形式的，所以扩容在其内部是十分常见的。但是如果每次扩容都需要重新计算之前所有节点的哈希值到新哈希表，那无疑会使redis表现起来很怪异（性能会波动，也许并不会表现出来，毕竟redis十分快，这么点计算消耗可能还远不及网络的一次波动，但是当数据量大的时候的确有可能引起短暂的阻塞）。

redis采用了渐进式哈希的方式，将一次集中扩容、rehash 操作的成本，分摊到各个节点的插入/更新操作。使得扩容十分平稳。

渐进式哈希

redis中的字典 内部有两张哈希表，ht[0],ht[1] 

我们称负载因子为  ht[0].used/ht[0].size    。

在最开始的时候，ht[1]是个空表。

1. ht[0] 负载因子 未到临界点

所有操作都是在ht[0]上进行

直到当ht[0] 的负载因子  达到临界点，就会触发   扩容/缩容   操作。

这个时候会将字典的属性  rehashidx  设为0 ， 表示启动rehash过程。

2. rehash 过程

先给ht[1] 申请内存

• 扩容：ht[1]的大小为大于等于ht[0].used * 2的且为2^n的值。
• 收缩：ht[1]的大小为大于等于ht[0].used 的且为2^n的值。

在这之后，所有新增元素都会只在ht[1] 上进行分配。

                  而查找、更新操作，除了返回操作结果之外，还会将ht[0]表的该元素rehash到ht[1]

从而保证ht[0] 的元素一直是在减少，直到成为空表。

这时会将  rehashidx  变量  置为 -1 ，表示rehash 结束

3. rehash 结束

rehash结束之后，会有一个指针转向的操作。

先将ht[0]  表的内存释放，后将ht[0]  指向 ht[1] 。最后又重置ht[1]为空表。

rehash 过程中的查找

在rehash过程中，两个哈希表都有数据，查找顺序是从ht[0]到ht[1]。

rehash 的不足

由于rehash 会引起使用内存的变化，因此在redis满容或接近满容状态下 ， rehash 时可能会使内存恰好突破了限制，触发淘汰策略，删除大量的键。

负载因子

Redis在执行BGSAVE和BGREWRITEAOF命令时，

哈希表的负载因子大于等于5，而未执行这两个命令时大于等于1

当哈希表的负载因子小于0.1时，对哈希表执行收缩操作

在执行BGSAVE和BGREWRITEAOF命令时，Redis需要创建当前服务器进程的子进程，而大多数操作系统都采用写时 复制技术来由于子进程的使用效率，所以在子进程存在期间，服务器会提高执行扩展操作所需的负载因子，从而尽可 能避免在子进程存在期间进行哈希表扩展操作，这可以避免不必要的内存写入操作。