redis源码阅读之面向哈希表优化

栏目: IT技术 · 发布时间: 4年前

内容简介：2020年了，给自己加个任务，把redis代码完整读一遍。我新建了一个github项目（地址在文章末尾），会在redis源码之上增加注释，后续也会为其中一些值得拎出来说的点单独写文章。本文内容：首先，科普一下哈希表（hash table）的

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