前言
说到redis中的dict，大家都知道是redis中的字典，如果只停留在理论层面的认识，那是远远不够的，因为理论和实际是完全不同的。只有真正深入到内部才能发现其中很多的奥秘。
一、字典的本质
哈希表
使用哈希表作为底层实现：将哈希表的每个下标比作是一个个的桶，把插入的key通过hash算法，计算出索引值，然后根据索引值找到表中index，并放入该桶中，如果有hash冲突，使用链表的方式，将相同的hash值的key，通过next指针形成一个链表，这样在桶中存放的就是一个链表。
那redis的哈希算法是什么呢？怎么防止哈希泛洪的攻击呢？
以前版本使用的是Murmurhash2算法，目前版本是siphash算法来实现。算法是如何实现，并且是如何免疫泛洪攻击的呢，我们放在之后的文章中，由于篇幅限制，这里就不展开了。
扩展
java1.7中，HashMap也是通过这种 桶 + 链表 实现的。
java1.8之后，使用 （桶 + 链表） + 红黑树 来实现HashMap
二、扩容
哈希表的初始大小为一般为2的幂次方。(在redis中默认初始化为4）
为什么要扩容？why？
随着新的键值对的不断加入，发生哈希表碰撞的几率会增加，就会导致各个桶中的链表长度增加，这样的话时间复杂度会退化。
什么时候扩容？when？
redis中规定：当负载因子 >= 1，即load_factor = d->ht[0].used >= d->ht[0].size时，进行扩容。
数据的每次新增都会触发_dictExpandIfNeeded(dict *d)方法去判断是否满足上述条件。
如何扩容？how？
每个dict有2个哈希表，ht0用来正常使用，ht1用来实现数据迁移。ht1的大小为原来的2倍。当resize时，会将ht0中的数据，迁移到ht1中。在迁移的过程中，新增的数据直接保存在ht1中，如果是查询操作，先查ht0，后查ht1.
任何时间都可以扩容么？
当服务端在进行bgsave和bgaofrewrite时，会调用updateDictResizePolicy(); 将dict_can_resize置为0，代表禁止resize
void updateDictResizePolicy(void) {
if (server.rdb_child_pid == -1 && server.aof_child_pid == -1)
dictEnableResize();
else
dictDisableResize();
}
为什么这个期间要禁止resize？why？
因为在bgsave和bgaofrewrite时，服务端为了保证不阻塞，而fork出子进程来进行rdb和aof文件的保存，而操作系统fork出的子进程，会和父进程
共享内存空间，只有当父或者子修改这些共享空间时，才回去创建新的内存并修改内容，（这就是cow，即写时复制）所以如果不禁止的话，会导致额外大量的内存被占用。
关于Copy On Write：fork()之后，kernel把父进程中所有的内存页的权限都设为read-only，然后子进程的地址空间指向父进程。当父子进程都只读内存时，相安无事。当其中某个进程写内存时，CPU硬件检测到内存页是read-only的，于是触发页异常中断（page-fault），陷入kernel的一个中断例程。中断例程中，kernel就会把触发的异常的页复制一份，于是父子进程各自持有独立的一份。
如果后台一直bgsave和bgaofrewrite，那岂不是不会扩容了么？
新的策略：当负载因子超过5，即load_factor>5，这个时候会进行强制扩容。但是这种情况一般是不会发生的，因为bgsave和bgaofrewrite的占用的时间一般不会太长。
总结
扩容的策略为2种：
- 满足负载因子大于等于1 且 后台没有bgsave和bgaofrewrite；
- 满足负载因子大于5
三、缩容
为什么要缩容？why？
如果随着时间的推移，可能hash表中的键值对越来越少，例如一段时间没新增，只有删除。那么使用这么大的表也不合适，也在占用着内存。
什么时候缩容？when？
redis中规定：当字典中元素的个数小于桶数的10%时，（可以理解为load_factor < 0.1），进行缩容。
我们会很自然的想到在每次dict执行删除操作中，去判断是否满足上述策略，然后进行缩容。但理论和实际是有区别，redis在缩容时，没有强制放在删除方法中，而是由业务自己去控制。
如何缩容？how？
和扩容的做法一致
实例
一个数据类型为哈希的编码类型如果是哈希表，在每次删除操作后触发。
if (o->encoding == OBJ_ENCODING_HT) {
if (dictDelete((dict*)o->ptr, field) == C_OK) {
deleted = 1;
/* Always check if the dictionary needs a resize after a delete. */
if (htNeedsResize(o->ptr)) dictResize(o->ptr);
}
}
redisDb.dict 和 redisDb.expires 的触发是在服务进行serverCron()->databasesCron()时触发。
void tryResizeHashTables(int dbid) {
if (htNeedsResize(server.db[dbid].dict))
dictResize(server.db[dbid].dict);
if (htNeedsResize(server.db[dbid].expires))
dictResize(server.db[dbid].expires);
}
四、渐进式rehash
扩容或者缩容大家都知道并不是一次性、集中式地完成，而是分多次、渐进式地完成。
为什么要渐进式？why？
这是为了保证在此期间，服务的可用性。如果字典的数据很大的话，如果一次完成的话，那么就会阻塞服务进程，这是不能接受的。
什么时间迁移数据？when？
每次对字典执行添加、删除、查找或者更新操作时，程序需会顺带进行小步搬运。
如何迁移？how？
小步搬运的方法为dictRehash(d,n);其中n代表步数。一般n=1，即每次一步。
- 在dict结构中有一个rehashidx代表rehash的进度。初始值为-1，在resize之后，rehashidx置为0，代表开始进行rehash了。每走一步将rehashidx++. 这里的步是指每次搬运一个桶里的所有数据，而不是一个数据。
- 当d->ht[0].used == 0时代表已经完成，将ht1设置为ht0，重新设置新的ht1。
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;
}
五、增量哈希
为什么要增量哈希？why?
由于服务器的Keys字典和Expires字典，数据量是比较大的，如果触发完扩容后，一段时间内操作比较少，那么小步搬运就太慢。
什么时候增量哈希？when？
在配置文件中：activerehashing yes/no，代表是否让服务端使用增量哈希。如果设置为yes, 就会在serverCron()->databasesCron()时触发。
如何增量？how？
在没有bgsave和bgaofrewrite的情况下，允许使用1ms的cpu时间来进行搬运，搬运的方法是每次100步执行，直到消耗1ms, 故称为增量哈希。
int incrementallyRehash(int dbid) {
/* Keys dictionary */
if (dictIsRehashing(server.db[dbid].dict)) {
dictRehashMilliseconds(server.db[dbid].dict,1);
return 1; /* already used our millisecond for this loop... */
}
/* Expires */
if (dictIsRehashing(server.db[dbid].expires)) {
dictRehashMilliseconds(server.db[dbid].expires,1);
return 1; /* already used our millisecond for this loop... */
}
return 0;
}
int dictRehashMilliseconds(dict *d, int ms) {
long long start = timeInMilliseconds();
int rehashes = 0;
while(dictRehash(d,100)) {
rehashes += 100;
if (timeInMilliseconds()-start > ms) break;
}
return rehashes;
}
备注：如果要求对redis环境的延迟要求比较高的话可以设置为no，默认为yes。
六、安全迭代模式
redis中在dictIterator结构中提供了一个字段safe，将safe设置为1，代表为安全迭代：在遍历的过程中，可以同时使用dictAdd、dictFind等等操作。如果不是安全的迭代，那么在遍历的过程中，只可以使用dictNext。
为什么要使用安全迭代，why？
如果在迭代的过程中，有触发小步搬运的逻辑，刚好迭代出的元素被运到了ht1，那么ht0中剩下的元素就不被跌倒到了，这样会导致迭代不全。
di = dictGetIterator(dict *d);
while((de = dictNext(di)) != NULL) {
//do something
...
dictAdd、dictFind...//触发小步搬运
}
什么时候使用？when？
在redis内部，大多数使用dict的结构数据在需要被迭代时，都会使用安全模式。比如：
- 在rdbSaveRio():以RDB格式保存数据
- 在rewriteAppendOnlyFileRio(): 以AOF格式保存数据
- latencyResetEvent(): 重置服务中延时事件样本数据
等等
如何实现的？how？
- 每使用一个安全模式迭代器，dict结构体中iterators值就会加1，代表当前有几个迭代器在使用。当迭代完成调用release释放掉，则iterators减1。
- 每次在进行搬运时，都会判断iterators是否等于0。如果为0，才回去移动数据。如果当前有迭代器在使用，那么不会搬运数据，这就是所谓的迭代器安全模式。
static void _dictRehashStep(dict *d) {
//如果当前有迭代器在使用，那么不会搬运数据，这就是所谓的迭代器安全模式
if (d->iterators == 0) dictRehash(d,1);
}
- 使用操作
di = dictGetSafeIterator(dict *d);
while((de = dictNext(di)) != NULL) {
//do something
...
dictAdd、dictFind、dictDelete....
//do something
...
}
dictReleaseIterator(di);
最后
上文涉及到的相关结构体
typedef struct dict {
dictType *type; //类型特定函数
void *privdata; //私有数据
dictht ht[2]; //两个ht
long rehashidx; //记录了rehash目前的进度（哈希桶的进度），如果目前没有在进行 rehash，那么它的值为-1 。
unsigned long iterators; /* number of iterators currently running 当前字典有几个迭代器在运行*/
} dict;
typedef struct dictht {
dictEntry **table; // 二维dictEntry数组
unsigned long size; //哈希表大小
unsigned long sizemask; //哈希表大小掩码，用于计算索引值 总是等于（size - 1）
unsigned long used; // 该哈希表已有节点的数量
} dictht;
typedef struct dictEntry {
void *key; // key 键
union {
void *val; //value 值
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next; // 下一个节点，形成链表
} dictEntry;
typedef struct dictIterator {
dict *d;
long index; //这里的index不是所有数据的下标，而是哈希桶的下标，即table一维的size
int table, safe;
dictEntry *entry, *nextEntry;
/* unsafe iterator fingerprint for misuse detection. 不安全迭代模式下的指纹，用来误用检测*/
long long fingerprint;
} dictIterator;
关注这个公众号，会让你成为一个 awesome Coder！
