Redis 字典

在 redis 中我们经常用到的 hash 结构，以及整个 redis 的 db 中 key-value 结构，都是以 dict 的形式存在，也就是字典。

源码结构

    // 字典结构
    typedef struct dict {
    	// 类型特定函数
        dictType *type; 
    	// 保存类型特定函数需要使用的参数
        void *privdata; 
    	// 保存的两个哈希表，ht[0]是真正使用的，ht[1]会在rehash时使用
        dictht ht[2]; 
    	// rehash进度，如果不等于-1，说明还在进行rehash
        long rehashidx;
    	// 正在运行中的遍历器数量
        unsigned long iterators; 
    } dict;
    
    // hashtable结构
    typedef struct dictht {
    	// 哈希表节点数组
        dictEntry **table; 
    	// 哈希表大小
        unsigned long size; 
    	// 哈希表大小掩码，用于计算哈希表的索引值，大小总是dictht.size - 1
        unsigned long sizemask; 
    	// 哈希表已经使用的节点数量
        unsigned long used; 
    } dictht;
    
    // hashtable的键值对节点结构
    typedef struct dictEntry {
    	// 键名
        void *key; 
    	// 值
        union {
            void *val;
            uint64_t u64;
            int64_t s64;
            double d;
        } v; 
    	// 指向下一个节点, 将多个哈希值相同的键值对连接起来
        struct dictEntry *next; 
    } dictEntry;

由上面的结构我们可以看到 dict 结构内部包含两个 hashtable（以下简称ht），通常情况下只有一个 ht 是有值的。ht 是一个 dictht 的的结构，dictht 的结构和 Java 的 HashMap 几乎是一样的，都是通过分桶的方式解决 hash 冲突。第一维是数组，第二维是链表。数组中存储的是第二维链表的第一个元素的指针。这个指针在 ht 中就是指向一个 dictEntry 结构，里面存放着键值对的数据，以及指向下一个节点的指针。

Hash计算

Redis 计算哈希值和索引值的方法如下：

    // 使用字典设置的哈希函数，计算键 key 的哈希值
    hash = dict->type->hashFunction(key);
    // 使用哈希表的 sizemask 属性和哈希值，计算出索引值
    // 根据情况不同， ht 可以是 ht[0] 或者 ht[1]
    index = hash & dict->ht.sizemask;

hash函数我们这里就不说明了，计算出的 hash 值后将该值和 ht 的长度掩码（长度 - 1 ）做与运算得出数组的索引值，这里我要解释下这么做的原因：

保证不会发生数组越界
首先我们要知道，ht 中数组的长度按规定一定是2的幂（2的n次方）。因此，数组的长度的二进制形式是：10000…000，1后面有一堆0。那么，dict->ht.sizemask（dict->ht.size - 1） 的二进制形式就是01111…111，0后面有一堆1。最高位是0，和hash值相“与”，结果值一定不会比数组的长度值大，因此也就不会发生数组越界。

保证元素尽可能的均匀分布
由上边的分析可知，dict->ht.size 一定是一个偶数，dict->ht.sizemask 一定是一个奇数。假设现在数组的长度（dict->ht.size）为16，减去1后（dict->ht.sizemask）就是15，15对应的二进制是：1111。现在假设有两个元素需要插入，一个哈希值是8，二进制是1000，一个哈希值是9，二进制是1001。和1111“与”运算后，结果分别是1000和1001，它们被分配在了数组的不同位置，这样，哈希的分布非常均匀。

那么，如果数组长度是奇数呢？减去1后（dict->ht.sizemask）就是偶数了，偶数对应的二进制最低位一定是 0，例如14二进制1110。对上面两个数子分别“与”运算，得到1000和1000。结果都是一样的值。那么，哈希值8和9的元素都被存储在数组同一个index位置的链表中。在操作的时候，链表中的元素越多，效率越低，因为要不停的对链表循环比较。

为什么 ht 中数组的长度一定是2的n次方？因为其实计算索引的过程其实就是取模（求余数），但是取余操作 % 的效率没有位运算 & 来的高，而 hash%length==hash&(length-1)的条件就是 length 是 2的次方，这里的原因上面也解释过了。

渐进式rehash

随着操作的不断执行， 哈希表保存的键值对会逐渐地增多或者减少， 为了让哈希表的负载因子（load factor）维持在一个合理的范围之内， 当哈希表保存的键值对数量太多或者太少时， 程序需要对哈希表的大小进行相应的扩展或者收缩，也就是 rehash。

Redis 对字典的哈希表执行 rehash 的步骤如下：

1. 为字典的 ht[1] 哈希表分配空间， 这个哈希表的空间大小取决于要执行的操作， 以及 ht[0] 当前包含的键值对数量 （也即是 ht[0].used 属性的值）：

• 如果执行的是扩展操作， 那么 ht[1] 的大小为第一个大于等于 ht[0].used * 2 的 2^n （2 的 n 次方幂）；
• 如果执行的是收缩操作， 那么 ht[1] 的大小为第一个大于等于 ht[0].used 的 2^n 。

1. 将保存在 ht[0] 中的所有键值对 rehash 到 ht[1] 上面： rehash 指的是重新计算键的哈希值和索引值， 然后将键值对放置到 ht[1] 哈希表的指定位置上。
2. 当 ht[0] 包含的所有键值对都迁移到了 ht[1] 之后 （ht[0] 变为空表）， 释放 ht[0] ， 将 ht[1] 设置为 ht[0] ， 并在 ht[1] 新创建一个空白哈希表， 为下一次 rehash 做准备。

这就是为什么redis 的 dict 中要保存2个 ht 的原因，方便2个 ht 的迁移替换。

为什么不直接复制 ht[0] 中的所有节点到 ht[1] 上而是 rehash 一遍？

我们在看一遍计算索引的公式：index = hash & dict->ht.sizemask;

注意到了吗，索引值的计算与字典数组的长度有关，而我们rehash时数组的长度是已经变化了，所以需要重新计算。

那么rehash的条件是什么呢，ht 达到什么样的数量redis会去执行rehash呢？

当以下条件中的任意一个被满足时， 程序会自动开始对哈希表执行扩展操作：

1. 服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令， 并且哈希表的负载因子大于等于 1 ；
2. 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令， 并且哈希表的负载因子大于等于 5 ；

其中哈希表的负载因子可以通过公式：

    // 负载因子 = 哈希表已保存节点数量 / 哈希表大小
    load_factor = ht[0].used / ht[0].size

负载因子其实就是一个哈希表的使用比例，用来衡量哈希表的容量状态。

bgsave 或 bgrewriteaof 命令会造成内存页的过多分离 (Copy On Write)，Redis 尽量不去扩容 ，但是如果 hash 表已经非常满了，元素的个数已经达到了第一维数组长度的 5 倍，这个时候就会强制扩容。

另一方面， 当哈希表的负载因子小于 0.1 时， 程序自动开始对哈希表执行收缩操作。

为什么称为渐进式？

扩展或收缩哈希表需要将 ht[0] 里面的所有键值对 rehash 到 ht[1] 里面， 可想而知大字典的 rehash过程是很耗时的，所以 redis 使用了一种渐进式的 rehash，也就是慢慢地将 ht[0] 里面的键值对 rehash 到 ht[1]。

以下是哈希表渐进式 rehash 的详细步骤：

1. 为 ht[1] 分配空间， 让字典同时持有 ht[0] 和 ht[1] 两个哈希表。
2. 在字典中维持一个索引计数器变量 rehashidx ， 并将它的值设置为 0 ， 表示 rehash 工作正式开始。
3. 在 rehash 进行期间， 每次对字典执行添加、删除、查找或者更新操作时， 程序除了执行指定的操作以外， 还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] ， 当 rehash 工作完成之后， 程序将 rehashidx 属性的值增一。
4. 随着字典操作的不断执行， 最终在某个时间点上， ht[0] 的所有键值对都会被 rehash 至 ht[1] ， 这时程序将 rehashidx 属性的值设为 -1 ， 表示 rehash 操作已完成。

所以大家可以看到这整个过程是分步走的，每次rehash一点，直到执行完。那么问题也来的，在渐进式rehash的过程中，我们的字典里 ht[0] 和 ht[1] 会同时存在数据，那么这时候操作字典会不会混乱呢，redis为此提出了以下的逻辑判断：

因为在进行渐进式 rehash 的过程中， 字典会同时使用 ht[0] 和 ht[1] 两个哈希表， 所以在渐进式 rehash 进行期间， 字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行： 比如说， 要在字典里面查找一个键的话， 程序会先在 ht[0] 里面进行查找， 如果没找到的话， 就会继续到 ht[1] 里面进行查找， 诸如此类。

另外， 在渐进式 rehash 执行期间， 新添加到字典的键值对一律会被保存到 ht[1] 里面， 而 ht[0] 则不再进行任何添加操作： 这一措施保证了 ht[0] 包含的键值对数量会只减不增， 并随着 rehash 操作的执行而最终变成空表。