写在前面
2020年了，给自己加个任务，把redis代码完整读一遍。我新建了一个github项目（地址在文章末尾），会在redis源码之上增加注释，后续也会为其中一些值得拎出来说的点单独写文章。
本文内容：
- 常规哈希表科普
- redis rehash面临的问题
- redis的渐进式hash
- 什么时候会启动rehash
- 如何渐进式rehash
- 什么时候执行一步rehash
- rehash进行时又有增删改查如何处理
- 什么时候不允许rehash
- 桶的初始数量，扩容后大小，缩容后大小
- redis dict的其他优化
- dict benchmark
常规哈希表科普
首先，科普一下哈希表（hash table）的常规实现。一般来说，哈希表基于数组实现，数组的每个元素即为一个桶（bucket or slot），向哈希表插入键值对（key-value pair or entry）时，先对key使用hash函数得到hash code（一个整型值），然后用hash code取余桶数量得到对应的桶下标，最后将entry存入桶中。
删除、修改、查找的操作类似，增删改查的时间复杂度都是O(1)。
由于不同的entry可能哈希到同一个桶内，为了解决哈希冲突的问题，可以使用链地址法。即桶中存放链表，链表上存放哈希到这个桶的多个entry。
那么问题来了，由于桶数量是固定的，插入的entry越多，冲突也就越多，桶上的链表就越长，时间复杂度也就慢慢退化成遍历链表的时间复杂度。
那么桶数量设置为多大合适呢，太大浪费内存，太小不够快。所以一个高性能的哈希表内部都会提供扩容、缩容策略（rehash）。即根据内部存储的entry个数和桶个数的比例，决定是否调整桶个数。桶个数调整后，原本属于同一个桶的元素，可能变成属于不同的桶，所以所有的entry都需要重新计算归属于哪个桶。即rehash是O(n)的。
名词补充：哈希表的装载因子(load factor) = entry总数 / 桶个数
redis rehash面临的问题
很显然，当一个哈希表的元素个数非常多时，rehash可能会非常耗时。而redis面临的问题更严重，由于redis是个单线程模型，虽然省去了很多线程间同步、切换的开销，但是缺点也很明显，就是一旦有耗时或阻塞操作，所有其他工作都没法做，比如读取客户端的数据、处理其他哈希表等等。
redis的解决方案是，将rehash的操作分步进行。即rehash做一点，又去做其他工作，不让其他工作等太久，运用分治思想，将rehash的开销分摊开。下面我们来详细介绍一下redis的rehash实现。
redis的渐进式rehash
声明，为了后文不产生歧义，我们将redis中基于哈希表提供给上层使用的键值型数据结构统一描述成Dict（字典）。
什么时候会启动rehash
会导致dict中元素增加的函数，都会判断装载因子是否大于5，如果是，则开启rehash。
dict也直接提供了接口dictResize供上层调用。比如，上层可以在定时器中读取dict当前装载因子，决定是否手动触发rehash。
删除元素时内部并不会主动触发rehash，上层可以自行决定是否缩容。
如何渐进式rehash
Dict内部使用两块哈希表。在正常情况下，Dict只使用0号哈希表，只有rehash时，才会使用到1号哈希表。rehash时，是逐步将0号老哈希表迁移到1号新哈希表的过程，完全迁移完成后，再将1号哈希表标记为0号哈希表，并结束rehash。
这里说的逐步，顺序是从0号哈希表的第一个桶到最后最后一个桶。
rehash分步的最小粒度，是0号哈希表中的一个桶中所有entry都迁移到1号哈希表上。
迁移过程中，一个entry只会存在于一个哈希表上，不会同时重复存在。
什么时候执行一步rehash
增删改查时都会进行小步rehash，并且只迁移一个桶。
提供了dictRehash(dict *d, int n)接口，上层可以直接调用并传入参数，指定本次想要迁移的桶的数量来手动触发迁移。
迁移时有个细节，空桶和非空桶迁移时耗时是有明显区别，redis为了区分对待，将空桶单独计数，为想迁移桶的10倍。
另外还提供了dictRehashMilliseconds(dict *d, int ms)接口，上层可以通过传递限制时间，手动触发迁移，并设置此次迁移的时长。
rehash进行时又有增删改查如何处理
增加时，直接往新的1号哈希表增加。
删除、修改、查询时，由于无法确定entry在哪块哈希表上，所以只能先查0号哈希表，找不到再查1号哈希表。
什么时候不允许rehash
如果在rehash进行中，上层获取并长久持有了dict的迭代器，那么rehash需要暂停，以避免迭代器迭代时访问到重复entry或丢失entry。
另外redis如果正在将数据持久化，也会关闭rehash的开关，避免copy-on-write受影响。
桶的初始数量，扩容后大小，缩容后大小
redis dict的桶初始数量是4，后续缩容也最少保持4个桶。
扩容后大小为扩容前entry数量的两倍，取整到2的幂方。
缩容缩到当前entry个数，取整到2的幂方。
redis dict的其他优化
entry插入时，向桶链表的最前面插入，这里运用的是时间局部性原理，认为新插入的元素后续被访问的几率高。
桶数量永远为2的幂方，hash code换算成桶下标时，使用按位与运算而不是取余运算，更高效，我之前的文章 译- Go开源项目BigCache如何加速并发访问以及避免高额的GC开销 也有提到这种方式。
查找访问后删除这种通常需要两次查找开销的操作，可合并为一次查找操作。
dict的value使用了union，即可存储指针，又可存储int基础类型。
dict benchmark
dict.c中自带了一个benchmark程序，在我的macos上执行，输出如下：
Inserting: 5000000 items in 4778 ms
Linear access of existing elements: 5000000 items in 2685 ms
Linear access of existing elements (2nd round): 5000000 items in 2703 ms
Random access of existing elements: 5000000 items in 3664 ms
Accessing missing: 5000000 items in 2985 ms
Removing and adding: 5000000 items in 5919 ms
结语
redis字典的源码大概有1500行左右，本文还有许多细节没有讲，感兴趣的可以看看我提供了注释版本的源码：https://github.com/q191201771/yoko-read-redis
原文链接： https://pengrl.com/p/0010/
原文出处： yoko blog (https://pengrl.com)
原文作者： yoko (https://github.com/q191201771)
版权声明： 本文欢迎任何形式转载，转载时完整保留本声明信息（包含原文链接、原文出处、原文作者、版权声明）即可。本文后续所有修改都会第一时间在原始地址更新。
本篇文章由一文多发平台ArtiPub自动发布
网友评论