redis源代码分析 – hash table

Datetime:2016-08-23 03:47:54          Topic: Redis  Source Code Analysis           Share

hashtable的实现有很多,redis的dict.c 是其中之一。

dict 包含了2个dictht hashtable ht[0], ht[1]。

client版本的dict 是没有dictht的概念。加入dictht的概念存在2个ht的目的是为了在rehash的时候可以平滑的迁移bucket里的数据,而不像client的dict要把老的hash table里的一次性的全部数据迁移到新的hash table,这在造成一个密集型的操作,在业务高峰期不可取。

ht是hashtable的简称,实际上是一个指针数组,数组的个数由dictht->size决定,是DICT_HT_INITIAL_SIZE的整数倍。每个元素(bucket)指向一个dictEntry的单链表来解决hash的conflict。查询某个key,需要先hash,定位到bucket,再通过链表遍历。

key经过hash函数后,与dictht->sizemask求与均分到ht的每个bucket上。dictht->used表示这个ht里包含的key的个数,也就是dictEntry的个数,每次dictAdd成功+1。链表的加入为头指针的方法加入,这样dictAdd更加的方便。

随着key不断的添加,bucket下的单链表越来越长,查找、删除效率越来越低,需要对ht进行expand,增加bucket个数,让链表的长度减少。bucket数量的增多,原有bucket的key需要迁移到新的bucket上,于是有了rehash的这个过程。

ht[1]就是为了rehash而产生,新的ht size是ht[0]的两倍2, 随着dictAdd,dictFind函数的调用,ht[0]的每个bucket会rehash加入到ht[1]里。dict->rehashidx 是ht[0] 需要rehash就是迁移到ht[1]的bucket的索引,从0开始直到ht->used==0。rehash除了每次伴随dictAdd,dcitFind而迁移一个bucket的所有dictEntry,还有一种一次hash100个bucket,直到消耗了某个时间点为止的做法。

rehash的步骤:

拿到一个bucket, 遍历这个链表的每个kv,对key进行hash然后于sizemask求与,定位ht[1]的新bucket位置,

加入到链表,迁移后ht[0].used–,ht[1].used++。

直到ht[0].used=0,释放ht[0]的table,再赋值ht[0]= ht[1],再把则ht[1]reset。

rehash的期间:

由于ht[1]是ht[0]size的2倍,每次dictAdd的时候都会rehash一次,不会出现后ht[1] 满了,而ht[0]还有数据的事情。

查询会先查ht[0]再查询ht[1],在rehash的过程中,不会出现再次expand。

新的key加到ht[1]。

expand的条件:

table的位置已经满了,糟糕的hash函数造成的skrew导致永远不会expand。

key的个数除以table的大小,超过了dict_force_resize_ratio。





About List