redis源代码分析 – hash table

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

redis_dict

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。

23 Comments

  1. fisk 说道:

    很高兴读到你的文章,我也在分析redis的代码。

    我有个疑问是,ht[1]的size一定是ht[0]的2倍吗? 我觉得也可以是四倍或二分之一等等??

  2. fisk 说道:

    你回复我的话,请给我的邮箱发信吧。
    谢谢

  3. hoterran 说道:

    /* Our hash table capability is a power of two */
    static unsigned long _dictNextPower(unsigned long size)
    {
    unsigned long i = DICT_HT_INITIAL_SIZE;

    if (size >= LONG_MAX) return LONG_MAX;
    while(1) {
    if (i >= size)
    return i;
    i *= 2;
    }
    }

  4. hoterran 说道:

    你的邮箱是多少?

    • fisk 说道:

      不好意思哈,之前不會用 LEAVE A REPLY, 原以為會把我提供的郵箱顯示出/

      2.4.0-rc8
      redis.c:425

      // REDIS_HT_MINFILL 默認是10%

      int htNeedsResize(dict *dict) {
      long long size, used;

      size = dictSlots(dict);
      used = dictSize(dict);
      return (size && used && size > DICT_HT_INITIAL_SIZE &&
      (used*100/size < REDIS_HT_MINFILL));
      }

      /* If the percentage of used slots in the HT reaches REDIS_HT_MINFILL
      * we resize the hash table to save memory */
      void tryResizeHashTables(void) {
      int j;

      for (j = 0; j < server.dbnum; j++) {
      if (htNeedsResize(server.db[j].dict))
      dictResize(server.db[j].dict);
      if (htNeedsResize(server.db[j].expires))
      dictResize(server.db[j].expires);
      }
      }

      對上面代碼的理解:
      當刪除一些key時,hash的size應該減小,這樣可以減少內存消耗; 但對於Hash數據結構可能沒有太大必要,因域的數目變化不大; 但對於top-LeveL的hash結構可能就必需/

  5. 皮包骨头的猪 说道:

    受益很多!本人一直从事java服务器端开发,最近想通过阅读redis源码来把c语言拾起来!

  6. brethorse 说道:

    你是什么意思?

  7. lisafang 说道:

    我比较关注redis的底层存储结构,不知楼主是否研究过。

  8. timebug 说道:

    请教2个问题:

    1. redis-2.4.6/src/dict.c:333

    static int dictGenericDelete(dict *d, const void *key, int nofree)
    {
    ...
                    if (!nofree) {
                        dictFreeEntryKey(d, he);
                        dictFreeEntryVal(d, he);
                    }
                    zfree(he);
    ...
    }
    

    为何这里要设置nofree模式? 这样nofree=1时释放dictEntry结构的时候不就会使得he->key和he->val变成野指针?

    2. redis-2.4.6/src/dict.c:531

    static int _dictExpandIfNeeded(dict *d)
    {
    ...
        if (d->ht[0].used >= d->ht[0].size &&
            (dict_can_resize ||
             d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
        {
            return dictExpand(d, ((d->ht[0].size > d->ht[0].used) ?
                                        d->ht[0].size : d->ht[0].used)*2);
        }
    ...
    }
    

    在调用dictExpand函数的时候,再判断一下d->ht[0].size > d->ht[0].used的大小有另外的作用吗?不是if语句中已经确定d->ht[0].used >= d->ht[0].size成立了吗?

    • jsz 说道:

      搭车同疑。2 感觉是疏忽吧,@timebug去github提个pull request问问看 :) 1 里边 nofree=1 的情况没有一处调用 (dictDeleteNoFree 没有在任何地方用到),09年的第一个commit就有了,所以貌似也是疏漏。

  9. 深海之尘 说道:

    请问在dictRehash中,为什么在对key进行hash后要跟sizemask求与呢?

  10. Alex 说道:

    1,rehash是在add或者find时,那如果一个key生成之后一直没有用过的话,这时怎么避免rehash一直没能完成?还是我理解有问题。。。
    2,rehash时内存占用是呈指数型增长,这时如果内存用完了怎么办?会不会有一个机制直接把swap用上?

    ps:还没真正读过redis源码,有空也读读

    • hoterran 说道:

      1. rehash是针对所有的kv记录而不仅仅是使用key.
      2. rehash不是呈指数增长,仅仅是两倍.内存完了目前仅仅依赖os的swap

  11. ycdoit 说道:

    留言,表示感谢.

  12. [...] 1.REDIS源代码分析 – HASH TABLE [...]

Leave a Reply