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

写在前面

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上执行,输出如下:

1
2
3
4
5
6
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

本文完,作者yoko,尊重劳动人民成果,转载请注明原文出处: https://pengrl.com/p/20010/

0%