redis 的 rehash 设计
本文思维导图如下：
HashMap 的 rehash 回顾
读过 HashMap 源码的同学，应该都晓得 map 在扩容的时候，有一个 rehash 的过程。
没有读过也没有关系，能够花工夫浏览下 从零开始手写 redis(13) HashMap 源码详解 简略理解下整个过程即可。
HashMap 的扩容简介
这里简略介绍下：
扩容 (resize) 就是从新计算容量，向 HashMap 对象里不停的增加元素，而 HashMap 对象外部的数组无奈装载更多的元素时，对象就须要扩充数组的长度，以便能装入更多的元素。
当然 Java 里的数组是无奈主动扩容的，办法是应用一个新的数组代替已有的容量小的数组，就像咱们用一个小桶装水，如果想装更多的水，就得换大水桶。
redis 中的扩容设计
HashMap 的扩容须要对汇合中大部分的元素进行从新计算，然而对于 redis 这种企业级利用，特地是单线程的利用，如果像传统的 rehash 一样把所有元素来一遍的话，预计要十几秒的工夫。
十几秒对于常见的金融、电商等绝对高并发的业务场景，是无法忍受的。
那么 redis 的 rehash 是如何实现的呢？
实际上 redis 的 rehash 动作并不是一次性、集中式地实现的，而是 分屡次、渐进式地实现的。
这里补充一点，不单单是扩容，缩容也是一样的情理，二者都须要进行 rehash。
只增不降就是对内存的节约，节约就是立功，特地是内存还这么贵。
ps: 这种思维和 key 淘汰有殊途同归之妙，一口吃不了一个大瘦子，一次搞不定，那就 1024 次，慢慢来总能解决问题。
Redis 的渐进式 rehash
这部分间接选自经典入门书籍《Redis 设计与实现》
为什么要渐进式解决？
实际上 redis 外部有两个 hashtable，咱们称之为 ht[0] 和 ht[1]。传统的 HashMap 中只有一个。
为了防止 rehash 对服务器性能造成影响，服务器不是一次性将 ht[0] 外面的所有键值对全副 rehash 到 ht[1]，而是分屡次、渐进式地将 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 属性的值增 1。
（4）随着字典操作的一直执行，最终在某个工夫点上，ht[0] 的所有键值对都会被 rehash 至 ht[1]，这时程序将 rehashidx 属性的值设为 -1，示意 rehash 操作已实现。
渐进式 rehash 的益处在于它采取分而治之的形式，将 rehash 键值对所需的计算工作均滩到对字典的每个增加、删除、查找和更新操作上，从而防止了集中式 rehash 而带来的宏大计算量。
rehash 间的操作怎么兼容呢？
因为在进行渐进式 rehash 的过程中，字典会同时应用 ht[0] 和 ht[1] 两个哈希表，那这期间的操作如何保障失常进行呢？
（1）查问一个信息
这个相似于咱们的数据库信息等迁徙，先查问一个库，没有的话，再去查问另一个库。
ht[0] 中没找到，咱们去 ht[1] 中查问即可。
（2）新数据怎么办？
这个和数据迁徙一样的情理。
当咱们有新旧的两个零碎时，新来的用户等信息间接落在新零碎即可，
这一措施保障了 ht[0] 蕴含的键值对数量会只减不增，并随着 rehash 操作的执行而最终变成空表。
一图胜千言
咱们来看图：
（1）筹备 rehash
（2）rehash index=0
（3）rehash index=1
（4）rehash index=2
（5）rehash index=3
（6）rehash 实现
缩容扩容的思考
看完了下面的流程，不晓得你对 rehash 是否有一个大略了思路呢？
上面让咱们来一起思考下几个缩扩容的问题。
什么时候扩容呢？
什么时候判断？
redis 在每次执行 put 操作的时候，就能够查看是否须要扩容。
其实也很好了解，put 插入元素的时候，判断是否须要扩容，而后开始扩容，是间接的一种思路。
留一个思考题：咱们能够在其余的时候判断吗？
redis 判断是否须要扩容的源码
/* Expand the hash table if needed */
static int _dictExpandIfNeeded(dict *d)
{
/* Incremental rehashing already in progress. Return. */
// 如果正在进行渐进式扩容，则返回 OK
if (dictIsRehashing(d)) return DICT_OK;
/* If the hash table is empty expand it to the initial size. */
// 如果哈希表 ht[0]的大小为 0，则初始化字典
if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
/* 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. */
/*
* 如果哈希表 ht[0]中保留的 key 个数与哈希表大小的比例曾经达到 1:1，即保留的节点数曾经大于哈希表大小
* 且 redis 服务以后容许执行 rehash，或者保留的节点数与哈希表大小的比例超过了平安阈值（默认值为 5）* 则将哈希表大小扩容为原来的两倍
*/
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);
}
return DICT_OK;
}扩容的条件总结下来就是两句话：
（1）服务器目前没有在执行 BGSAVE/BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 1；
（2）服务器目前正在执行 BGSAVE/BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 5；
这里其实体现了作者的一种设计思维：如果负载因子超过 5，阐明信息曾经很多了，管你在不在保留，都要执行扩容，优先保障服务可用性。如果没那么高，那就等长久化实现再做 rehash。
咱们本人在实现的时候能够简化一下，比方只思考状况 2。
扩容到原来的多少？
晓得了什么时候应该开始扩容，然而要扩容到多大也是值得思考的一个问题。
扩容的太小，会导致频繁扩容，节约性能。
扩容的太大，会导致资源的节约。
其实这个最好的计划是联合咱们理论的业务，不过这部分对用户是通明的。
个别是扩容为原来的两倍。
为什么须要扩容？
咱们在实现 ArrayList 的时候须要扩容，因为数据放不下了。
咱们晓得 HashMap 的底层是数组 + 链表（红黑树）的数据结构。
那么会存在放不下的状况吗？
集体了解实际上不会。因为链表能够始终加下去。
那为什么须要扩容呢？
实际上更多的是处于性能的思考。咱们应用 HashMap 就是为了晋升性能，如果始终不扩容，能够了解为元素都 hash 到雷同的 bucket 上，这时就进化成了一个链表。
这会导致查问等操作性能大大降低。
什么时候缩容呢？
何时判断
看了后面的扩容，咱们比拟直观地形式是在用户 remove 元素的时候执行是否须要缩容。
不过 redis 并不齐全等同于传统的 HashMap，还有数据的淘汰和过期，这些是对用户通明的。
redis 采纳的形式实际上是一个定时工作。
集体了解内存缩容很重要，然而没有那么紧急，咱们能够 1min 扫描一次，这样能够节俭机器资源。
理论工作中，个别 redis 的内存都是逐渐回升的，或者稳固在一个范畴内，很少去大批量删除数据。（除非数据搞错了，我就遇到过一次，数据同步错中央了）。
所以数据删除，个别几分钟内给用户一个反馈就行。
知其然，知其所以然。
咱们懂得了这个情理也就懂得了为什么有时候删除 redis 的几百万 keys，内存也不是间接降下来的起因。
缩容的条件
/* If the percentage of used slots in the HT reaches HASHTABLE_MIN_FILL
* we resize the hash table to save memory */
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);
}
/* Hash table parameters */
#define HASHTABLE_MIN_FILL 10 /* Minimal hash table fill 10% */
int htNeedsResize(dict *dict) {
long long size, used;
size = dictSlots(dict);
used = dictSize(dict);
return (size > DICT_HT_INITIAL_SIZE &&
(used*100/size < HASHTABLE_MIN_FILL));
}
/* Resize the table to the minimal size that contains all the elements,
* but with the invariant of a USED/BUCKETS ratio near to <= 1 */
int dictResize(dict *d)
{
int minimal;
if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;
minimal = d->ht[0].used;
if (minimal < DICT_HT_INITIAL_SIZE)
minimal = DICT_HT_INITIAL_SIZE;
return dictExpand(d, minimal);
}和扩容相似，不过这里的缩容比例不是 5 倍，而是当哈希表保留的 key 数量与哈希表的大小的比例小于 10% 时须要缩容。
缩容到多少？
最简略的形式是间接变为原来的一半，不过这么做有时候也不是那么好用。
redis 是 缩容后的大小为第一个大于等于以后 key 数量的 2 的 n 次方。
这个可能不太好了解，举几个数字就懂了：
| keys 数量 | 缩容大小 |
|---|---|
| 3 | 4 |
| 4 | 4 |
| 5 | 8 |
| 9 | 16 |
次要保障以下 3 点：
（1）缩容之后，要大于等于 key 的数量
（2）尽可能的小，节约内存
（3）2 的倍数。
第三个看过 HashMap 源码解说的小伙伴应该深有体会。
当然也不能太小，redis 限度的最小为 4。
实际上如果 redis 中只放 4 个 key，切实是杀鸡用牛刀，个别不会这么小。
咱们在实现的时候，间接参考 jdk 好了，给个最小值限度 8。
为什么须要缩容？
最外围的目标就是为了节约内存，其实还有一个起因，叫 small means fast（小即是快——老马）。
渐进式 ReHash 实现的思考
好了，扩容和缩容就聊到这里，那么这个渐进式 rehash 到底怎么一个渐进法？
扩容前
不须要扩容时应该有至多须要初始化两个元素：
hashtable[0] = new HashTable(size);
hashIndex=-1;
hashtable[1] = null;hashtable 中存储着以后的元素信息，hashIndex=-1 标识以后没有在进行扩容。
扩容筹备
当须要扩容的时候，咱们再去创立一个 hashtable[1]，并且 size 是原来的 2 倍。
hashtable[0] = new HashTable(size);
hashtable[1] = new HashTable(2 * size);
hashIndex=-1;次要是为了节约内存，应用惰性初始化的形式创立 hashtable。
扩容时
调整 hashIndex=0…size，逐渐去 rehash 到新的 hashtable[1]
新的插入全副放入到 hashtable[1]
扩容后
扩容后咱们应该把 hashtable[0] 的值更新为 hashtable[1]，并且开释掉 hashtable[1] 的资源。
并且设置 hashIndex=-1，标识曾经 rehash 实现
hashtable[0] = hashtable[1];
hashIndex=-1;
hashtable[1] = null;这样整体的实现思路就曾经差不多了，光说不练假把式，咱们下一节就来本人实现一个渐进式 rehash 的 HashMap。
至于当初，先让 rehash 的思路飞一会儿~
小结
本节咱们对 redis rehash 的原理进行了解说，其中也退出了不少本人的思考。
文章的结尾，也增加了简略的实现思路，当然理论实现还会有很多问题须要解决。
下一节咱们将一起手写一个渐进式 rehash 的 HashMap，感兴趣的搭档能够关注一波，即便获取最新动静~
开源地址：https://github.com/houbb/cache
感觉本文对你有帮忙的话，欢送点赞评论珍藏关注一波。你的激励，是我最大的能源~
不晓得你有哪些播种呢？或者有其余更多的想法，欢送留言区和我一起探讨，期待与你的思考相遇。