Redis源码剖析——dict(二)

/ 0评 / 1

下面要探究的核心问题是dict中为何要用两个哈希表,这两个哈希表给Redis的dict带来了什么好处?我们从dict最开始的创建、插入、迭代器、以及删除等全过程来剖析

(ps: 下面有时候会把dict和字典混说)


我们不妨先看看Redis中哈希用的哈希函数

image.png

这是比较常用的MurmurHash2,这个哈希函数在这的实现做了两个假设

关于hash函数的细节在此我们当然就不研究了

image.png

还提供了一个不太敏感的哈希函数备选

image.png


创建的简单初始化

image.png

创建整个字典结构。不过注释里也直接说创建哈希表,这当然也是没什么问题的,毕竟有时候习惯性的把哈希和字典结构直接等同,不过私以为这个注释不太恰当

我们来看看字典的初始化函数做了什么

image.png

同样此处官方注释为初始化哈希表,但实际上实在初始化整个字典结构,你明白的~)

字典初始化做的事情也是比较直接:清空两张哈系表,把字典上的所有方法type字段构造好,赋值私有数据指针,把rehashidx赋为-1,迭代器赋为0,关于rehashidx你马上就会明白了。

接下来当然就是再看看这个Reset函数对哈希表做了什么

image.png

没错,什么都没做,就是清空了一下


真正的创建开始

以上实际上只能算是dict的简单初始化,真正的创建从下面的resize开始被发起

image.png

Resize函数用于发起对于哈希表的大小调整,调整的后的size(哈希桶的个数)是一个可以保证容纳当前所有元素,并且负载因子小于等于阈值。

关于我们暂且先给思维发起一个“中断”看看这个~

image.png

dict_can_resize即是一个表示是否允许发起resize的标识,当这个标识为1时,若当前负载因子未被超过阈值则不允许发起resize,当然负载因子被超过时还是允许扩容发起resize的,这个标识被设置的意义就在于当前负载因子未达到阈值就不准去resize

关于dict_can_resize这个标识提供了两个方法来修改

image.png

那么dict_force_resize_ratio呢?相信很多人都猜到了,它就是负载因子的阈值

我们从“中断”返回到我们的resize函数里~

很显然可以看到,以下两件个条件任一被满足时则不允许主动resize

(ps:当因负载因子达到阈值而扩容时并不通过这个resize函数来做扩容,会有别的函数来检查是否达到负载因子阈值而扩容)

如果可以resize,且当前表中元素小于默认初始值4时(这个初始值在上一篇说过了,在上一篇你可以看到这个值的定义),则会向上增加到4,为什么非要这么做呢,后面我们会看到这样做的原因是因为:每次resize后的size大小的都是2的正整数次幂。

继续往下到expand函数(建议稍作休息,因为下面需要你好好理一理)

image.png

首先明确一点,这个函数虽然叫expand,但是它不止用于扩容,表的初次创建也是使用它

首先看看realsize,realsize显然是把入参size进行调整后得到的一个值,那么到底做了什么调整呢?

image.png

很简单,调整为大于等于size的最小2的整数次幂(虽然代码已经很明白了,但还是为了避免有人没看懂这句话)即以下不等式

的最小整数解对应的

回到我们的expand函数,在计算完realsize后接下来便是判断以下条件任一是否被满足,若满足则直接返回错误

如果以上条件都不被满足,就判断是否d->ht[0]的size本来就等于realsize,如果等于则显然不必做后续的任何扩容操作,直接返回一个错误即可

接下来便给我们的新表分配以下空间,做一些基本的初始化,做完这些之后有两种情况

1、d->ht[0]表本身就为空,即我们为创建表而调用的expand,那么这时把创建好的新表的内容赋给d->ht[0]即可

(ps: 如果你对为何此处n这个局部变量做一个简单赋值就可以完成这件事有疑惑,我不想多解释,你应该好好看看dictht结构里是存什么)

2、d->ht[0]本身不为空,那么我们就要把n赋给d->ht[1],并把rehashidx赋值为0,意义为rehashing开始!

你能坚持读到这已经超越很多人了,接下来你会看到dict中最精华的部分


Incremental Rehashing

先问自己一个问题,你见过的很多实现或者你做的实现里,哈希表扩容后的再哈希是如何做的?

你会说:很简单啊,扩容时把旧表的挨个再哈希过去呗

有没有觉得再哈希似乎是一个开销不小的操作,需要集中式的做N次计算,事实上我在开头放上哈希函数就是在提醒你,哈希计算并不是一个多么快的加减乘除,对于CPU来说至少不是一个像简单加一次这么快的事情,当然上上面这个hash函数的计算部分大概至少多少条指令就不在此估计了,起码我们知道把这个过程进行一千次并不是一个时间极短的事情,在并发极高的情况下,服务器CPU不应该被任何单一事件长期占用,你有没有想过怎么优化?

Redis中采用了Incrementa Rehashing,常译作渐进式哈希,这个方案在零几年被学术界提出,在Redis中得到了极大的表现,渐进式哈希到底到底做了什么?

集中一次的哈希的会导致CPU占用过高与时间过长,那么:

渐进式哈希就把这个过程切分开,也就是说渐进式哈希决定把对旧表再哈希到新表的这个过程不一次做完,而是分多次做,每次rehash旧表的一部分,但不释放,因为在rehashing完全成之前,所有增、删、查、改操作全部要综合ht[0]与与ht[1]这两张表(显然)

新增加的元素在此期间直接插入ht[1]表

删除操作要保证两张表的一致性

查也要综合两张表来搜索

rehash有两种触发,一种是时间段触发,这时rehash一旦被触发,那么在一段时间内会一直进行rehash,直到把旧表的所有元素rehashing完为止,全部rehashing完之后交换ht[0]与ht[1]

关于上面的说的一段时间:默认为1ms,这1ms内未必只能进行一轮rehash,事实上如果从触发rehash后,第一次rehash执行用时还不到1ms的话,那么就可以继续rehash,直到时间超过1ms,后面代码关于这一点会更加清晰的体现

还有一种就是被事件触发


image.png

这个函数便是发起rehash,即对d->ht[0]中的一部分做rehash。注意这里的这个判断是为了确定没有任何迭代器在dict上,因为reshashing是可能引起迭代器访问出现某些混论,所以有迭代器在dict上时rehashing不应该被进行。

既然分散成很多次来做,那么怎么分?没错,就是刚才说的两种方式,一种是切分成1ms来触发,一种是事件触发,下面就是会触发rehash的事件:

如下会触发rehasing的事件(注意高亮部分)

插入触发

image.png

删除触发

image.png

查找触发

image.png

随机获取一个元素触发

image.png

随机获取N个元素尽量触发N次(很有可能不需要N次rehashing已经完成)

image.png

以上就是所有rehash被触发的时机,这种做法可谓十分巧妙~

下面看看Rehash函数本身

image.png

入参n的代表要对多少个桶进行rehash,也就是说rehash的粒度是桶。

empty_visits用于表明在遍历哈希桶过程中最多遇到多少空桶就直接返回

下面的过程代码写得非常漂亮,在while循环中处理完一个桶下挂的链表,每处理一个元素节点就把ht[0]->used--,ht[1]->used++,处理完整个桶后继续下一个桶(如果n-- != 0 的话),当然也要注意d->ht[0].uesd是否为0,因为可能已经全部rehashing完了整个d->ht[0]

进行完本轮后检查是否全部rehash完,如果是则释放d->ht[0]这个旧表,用d->ht[1]这个全部rehash迁移好的新表来取代它,同时记得把rehashidx置为-1,标志我们的rehash已经完成了!

dict的扩容根本上由这个内部函数来检查,这个static函数是不暴露给外部使用的

image.png

上面这个检查是否需要扩容的函数,在每次计算一个元素在哈希表中的index时会触发(也只被这个函数触发,事实上哪个操作不会调用下面这个计算下标的函数呢)

image.png


Incremental Rehashing 以一种相当巧妙的方式来降低了集中式Hash带来的CPU负载,其结合事件触发的设计颇为让人眼前一亮

关于插入、删除、搜索这些基本操作的实现在此就不展开了,因为dict中这些的实现都比较trivial,没有什么需要特别关注的地方

值得一提的是,其迭代器中有一个“扫描”函数比较巧妙,所谓“扫描”就是遍历并且对其进行某种操作(i.e: 比如对每个value进行+1)。这个“扫描”函数在表扩容时也可以继续,虽然可能有一些key会被扫到多次,但是可以做到让在rehash后能比较“合适”的继续扫描已经很不容易了(此处合适即不从头开始)。这部分需要单独一篇才能讲得明白,所以就不再展开了,毕竟这只能算redis源码海洋中的一颗小珍珠,我们必须有所取舍。不过还是简单说一下,这个“扫描”的主要设计在这个函数中

image.png

其中fn是一个回调函数,在迭代器遍历过程中会对每个entry调用该回调函数,其类型如下

image.png


迭代器实际分为safe和unsafe,由dictIterator结构中的safe属性是否为1来区分

image.png

这二者的主要区别主要体现在,对于不安全的迭代器,我们存在一个“指纹”的概念,“指纹”由这个函数生成

image.png

这个函数的意图很明显,由一个dict的元数据生成一个“指纹”,一旦dict发生了元素的增删(rehashing过程中的迁移也算),这个指纹就会变化,那么对于不安全的迭代器来说,我们不允许这件事的发生,不安全的迭代器每遍历一个entry就会更新一次“指纹”

image.png

不安全迭代器在被释放时,若当前dict的“指纹”已发生变化,则会触发一个redis自己定义的assert(注意不是glibc的那个assert)

image.png

发表评论

电子邮件地址不会被公开。 必填项已用*标注