Redis作为KV数据库，整个数据库都使用字典进行储存的，很多高级语言也实现了字典结构。

# 字典构造

# Hash表

Redis字典低层的Hash表通过数组+单链表的方式实现：

/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
// 哈希表结构
typedef struct dictht {
    dictEntry **table;
    unsigned long size;	// hash数组(table)的长度
    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;	// 指向同Hash值的下一个元素
} dictEntry;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Hash表中要注意的是：

  1. sizemask掩码：用于计算键的索引。Hash计算结果需要和数组长度取余确定最终的储存位置，为了使除法运算更加快捷，redis的hash表大小永远是4,8,16...sizemask的值永远是3,7,15……对应二进制有效位都是1，因此取余可以被二进制与替换，与运算的计算速度比除法取余快得多；
  2. 在储存元素的时候是键值一起储存在结构体中，便于后续查找冲突时确定查找的对象（这在其他语言中也是同理）；
  3. 由于没有尾指针，所以hash在冲突时采用头插法的方式插入节点。

# 字典

字典结构是对Hash表的再次封装，便于应用时进行扩容缩容、遍历等操作：

typedef struct dict {
    dictType *type;	// 该字典对应的一些特定操作函数
    void *privdata;	// 该字典依赖的数据
    dictht ht[2];		// 两个hash表
    long rehashidx; // rehash标识
    unsigned long iterators;  // 访问的迭代器数量
} dict;
1
2
3
4
5
6
7

dictType是对字典操作的一些抽象，如键复制函数、值复制函数等，类似于接口，Redis多个地方都用到了字典结构，不同地方的具体方法不同，因此抽象出操作函数，搭配privdata一同使用。

rehashidx和iterators都是搭配字典迭代器使用的，在之后的字典迭代部分有详细讲述。

# 字典相关操作

# 1. 添加元素

字典的主要操作都在ht[0]进行，如果字典发生了扩容/缩容(rehash)，则会将操作放至ht[1]。

# 2. 字典扩容/缩容

初始化的字典容量为4，如果字典负载过大，则会发生扩容，此时字典会进入rehash，将size扩大若干倍（不一定是1倍，但大小一定是4、8、16...，直到装下所有元素）。在扩容过程中，会在ht[1]申请新的hash表，并将数据逐步插入新的表中：


























 






 





static int _dictExpandIfNeeded(dict *d)
{
    /* 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);
    }
		
  	// 其他内容省略
}
/* Expand or create the hash table */
int dictExpand(dict *d, unsigned long 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)
        return DICT_ERR;
    dictht n; /* the new hash table */
  	// 这里决定了下一个大小是多少
    unsigned long realsize = _dictNextPower(size);
		// 中间一些判断省略
    /* Prepare a second hash table for incremental rehashing */
    d->ht[1] = n;
  	// 标记进入rehash
    d->rehashidx = 0;
    return DICT_OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

同理，当字典的使用率不足10%时，会发生缩容，同样会创建新的hash表，进行rehash操作。

# 3. 渐进式rehash机制

rehash操作主要是将原hash表的每个元素提取出来，重新进行hash计算，插入到新的hash表中，在完成数据转移后将工作表ht[0]指向新的hash表。

redis字典储存着大量的数据，当数据库中键值对数量达到了百万、千万、亿级别时，整个rehash过程将非常缓慢，如果不优化rehash过程，可能会造成很严重的服务不可用现象。因此，redis采用分治思想，引入了渐进式rehash机制。

字典在执行插入、删除、查找、修改等操作前，都先判断当前字典rehash操作是否在进行中，进行中则调用dictRehashStep函数进行rehash操作（每次只对1个节点进行rehash操作，共执行1次）。除这些操作之外，当服务空闲时，如果当前字典也需要进行rehsh操作，则会调用incrementallyRehash函数进行批量rehash操作（每次对100个节点进行rehash操作，共执行1毫秒）。在经历N次rehash操作后，整个ht[0]的数据都会迁移到ht[1]中，这样做的好处就把是本应集中处理的时间分散到了上百万、千万、亿次操作中，所以其耗时可忽略不计。

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

# 字典的遍历

普通hash表遍历很容易理解，但是由于渐进式rehash机制的存在，当一个字典处于rehash状态时，字典的遍历就可能会由于键值对的移动产生遗漏、重复遍历的情况。

redis在字典遍历中有两种方式：keys迭代器遍历和scan间断遍历

# 1. 迭代器遍历

迭代器和部分高级语言的iterator一致，相对于对迭代操作的高层封装，redis字典迭代器结构如下：

/* If safe is set to 1 this is a safe iterator, that means, you can call
 * dictAdd, dictFind, and other functions against the dictionary even while
 * iterating. Otherwise it is a non safe iterator, and only dictNext()
 * should be called while iterating. */
typedef struct dictIterator {
    dict *d;	// 迭代的字典
    long index;	// 当前迭代的索引
    int table, safe;	// 迭代的表以及safe标识
    dictEntry *entry, *nextEntry;	//当前节点与下一个节点
    /* unsafe iterator fingerprint for misuse detection. */
    long long fingerprint;	// 字典指纹
} dictIterator;
1
2
3
4
5
6
7
8
9
10
11
12

迭代器分为普通迭代器和安全迭代器，普通迭代器会在迭代的过程中比对fingerprint字典指纹，如果指纹发生了变化，则抛出异常，因此迭代过程中不能进行如何增删改查操作（查可能也会在rehash中改变字典）。

安全迭代器会结合字典中的iterators字段，限制rehash的进行。当安全迭代器进行迭代时，会将对应字典的iterators字段+1，此时字典的rehash会暂停，因此迭代不会产生数据遗漏和重复遍历的情况。

迭代器遍历可以完整遍历一个字典，通过不同的方式保证迭代结果的正确性。但是当字典数据量很大时，迭代器会耗费大量时间，造成redis服务不可用，因此出现了类似数据库分页的间断遍历方法。

# 2. 间断遍历

间断遍历的思想是通过设置一个游标，每次遍历一部分数据，并返回新的游标值，整个遍历过程都是围绕这个游标值的改动进行，来保证所有的数据能被遍历到。

显然，rehash操作会对游标遍历产生影响：

如果整个遍历的过程中都没有rehash影响（可能从未发生rehash，也可能rehash已经完成），redis采用了一种逆转二进制算法来保证游标遍历不重复也不遗漏；

如果遍历的过程中正在进行rehash操作，游标会先找到两个散列表中更小的表，先对小的Hash表遍历，然后对大的Hash表遍历。如果发生了rehash，同一个元素可能会被返回多次，遍历过程中新增或者删除的Key可能会被返回，也可能不会。

参考资料： 《Redis5 设计与源码分析》