5月
11

redis源码阅读--字典

redis源码阅读

字典又叫映射或者说关联数组，是一种抽象的数据结构。本节主要来分析下它的源码。关于map应该说都是挺熟悉的数据结构了。

redis中字典的应用

redis字典的用途有以下两个：
1.实现数据库键空间；
2.用作hash类型键的底层实现之一；

字典的实现

实现字典的方法有很多种：

使用链表和数组
使用哈希表
平衡树

在redis种使用哈希表作为字典的底层实现。
其结构如下:

 typedef struct dict {
    dictType *type;
    void *privdata;
    //哈希表
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

0号哈希表是字典主要使用的哈希表，1号哈希表则只有在程序对0号哈希表rehash时使用。

哈希表实现

/* 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;
    //指针数组长度的掩码
    unsigned long sizemask;
    //哈希表现有的节点数量
    unsigned long used;
} dictht;

table 属性是个数组，数组的每个元素都是个指向 dictEntry 结构的指针。

每个 dictEntry 都保存着一个键值对，以及一个指向另一个 dictEntry 结构的指针：

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

next属性指向另一个dictEntry结构，多个dictEntry可以通过next指针串连成链表，所以dictht使用链地址法来处理键碰撞：当多个不同的键拥有相同的哈希值时，哈希表用一个链表将这些键连接起来。结构如下：
image.png-43kB

所以整个字典结构如下：
image.png-69.6kB

哈希算法

redis目前使用两种不同的哈希算法：

MurmurHash2 32 bit 算法：这种算法的分布率和速度都非常好
基于 djb 算法实现的一个大小写无关散列算法

dictCreate函数

dictCreate函数创建并返回一个新字典：

1	dict *d = dictCreate(&hash_type, NULL);

image.png-37.4kB
新创建的哈希表都没有为table属性分配任何空间:

ht[0]->table 的空间分配将在第一次往字典添加键值对时进行；
ht1->table 的空间分配将在rehash开始时进行;

添加键值对到字典

根据字典所处的状态，将给定的键值对添加到字典会引起一系列复杂的操作:

如果字典未初始化（即字典的0号哈希表的table属性为空），则程序需要对0号哈希表进行初始化；
如果在插入时发生了键碰撞，则程序需要处理碰撞；
如果插入新元素，使得字典满足了rehash条件，则需要启动rehash程序

当程序处理完以上三种情况之后，新的键值对才会被真正地添加到字典上。
整个添加流程如下：
image.png-140.7kB

添加新元素到空白字典

当第一次往空字典里添加键值对时，程序会根据dict.h/DICT_HT_INITIAL_SIZE里指定的大小为d->ht[0]->table分配空间（目前这个值是4）

字典空白
往字典添加了第一个键值对之后

添加新键值对时发生碰撞处理

在哈希表实现中，当两个不同的键拥有相同的哈希值时，称这两个键发生碰撞，而哈希表必须要对碰撞进行处理。字典哈希表所使用的碰撞解决方法被称之为链地址法：这种方法使用链表将多个哈希值相同的节点串连在一起，从而解决冲突问题。

添加新键值对时触发了rehash操作

对于使用链地址法来解决碰撞问题的哈希表dictht来说，哈希表的性能取决于大小（size属性）与保存节点数量（used属性）之间的比率：

哈希表的大小与节点数量，比率在1:1时，哈希表的性能最好；
如果节点数量比哈希表的大小要大很多的话，哈希表就会退化称多个链表，哈希表本身的性能优势便不复存在；

所以为了在字典的键值对不断增多的情况下保持良好的性能，字典需要对所使用的哈希表（ht[0]）进行rehash操作:在不修改任何键值对的情况下，对哈希表进行扩容，将比率维持在1:1左右。
dictAdd在每次向字典添加新键值对之前，都会对哈希表ht[0]进行检查，对于ht[0]的size和used属性，如果它们之间的比率ratio=used/size满足以下任何一个条件的话，rehash过程就会被激活：

自然 rehash ： ratio >= 1 ，且变量 dict_can_resize 为真。
强制 rehash ： ratio 大于变量 dict_force_resize_ratio（目前版本中， dict_force_resize_ratio的值为 5 ）。

Rehash执行过程

字典的rehash操作实际上就是执行以下任务:

创建一个比ht[0]->table更大的ht1->table；
将ht[0]->table中的所有键值对迁移到ht1->table;
将原有ht[0]的数据清空，并将ht1替换为新的ht[0]；

经过以上步骤，程序就在不改变原有键值对数据的基础上，增大了哈希表的大小。

渐进式rehash

rehash程序并不是在激活之后，就马上执行直到完成的，而是多次、渐进式地完成。
redis完成渐进式rehash主要由_dictRehashStep和dictRehashMilliseconds两个函数进行：

_dictRehashStep用于对数据库字典、以及哈希键的字典进行被动rehash；
dictRehashMilliseconds则由Redis服务器常规任务程序执行，用于对数据库字典进行主动rehash；

_dictRehashStep
每次执行_dictRehahshStep，ht[0]->table哈希表第一个不为空的索引上的所有节点就会全部迁移到ht1->table。
dictRehashMilliseconds
dictRehashMilliseconds可以在指定的毫秒数内，对字典进行rehash。
当Redis的服务器常规任务执行时，dictRehashMilliseconds就会被执行，在规定的时间内，尽可能对数据库字典中那些需要rehash的字典进行rehash，从而加速数据库字典的rehash进程。

因为在rehash时，字典会同时使用两个哈希表，所以在这期间的所有查找、删除等操作，除了在ht[0]进行，还会在ht1进行。在执行添加操作时，新的节点会直接添加到ht1而不是ht[0]，这样保证ht[0]的节点数量在整个rehash过程中都只减不增。

字典的收缩

对hash表进行收缩的过程与增加几乎一样；

创建一个比ht[0]->table小的ht1->table;
将ht[0]->table中的所有键值对迁移到ht1->table；
将原有ht[0]数据清空，并将ht1替换为新的ht[0];

字典的迭代

字典拥有其自己的迭代器实现—对字典进行迭代实际上就是对字典所使用的哈希表进行迭代：

迭代器首先迭代字典的第一个哈希表，然后，如果rehash正在进行的话，就继续对第二个哈希表进行迭代。
当迭代哈希表时，找到第一个不为空的索引，然后迭代这个索引上的所有节点。
当这个索引迭代完了，继续查找下一个不为空的索引，如此反覆，直到整个哈希表都迭代完为止。

字典的迭代器有两种：

安全迭代器：在迭代过程中，可以对字典进行修改。
不安全迭代器：在迭代过程中，不可以对字典进行修改。

总结

字典是由键值对构成的抽象数据结构
Redis中的数据库和哈希键都基于字典来实现
Redis字典的底层实现为哈希表，每个字典使用两个哈希表，一般情况下只使用0号哈希表，只有在rehash进行时，才会使用0号和1号哈希表。
哈希表使用链地址法来解决键冲突的问题。
Rehash可以用于扩展或收缩哈希表。
对哈希表的rehash是分多次、渐进式地进行的