首页 > redis > redis中字典的底层实现
2017
05-17

redis中字典的底层实现

哈希表概述

       表现为:存储位置 = f(key);

       存储过程如下:

  1. 根据 key 计算出它的 hash 值 h。 

  2. 假设箱子的个数为 n,那么这个键值对应该放在第(h%n)个箱子中。

  3. 如果该箱子中已经有了键值对,就是用开放寻址法或者拉链法解决冲突。

负载因子:它用来衡量哈希表的 空/满 程度,一定程度上也可以体现查询的效率,计算公式为:

负载因子 = 总键值对数 / 箱子个数

负载因子越大,意味着哈希表越满,越容易导致冲突,性能也就越低。因此,一般来说,当负载因子大于某个常数(可能是1, 或者 0.75等)时,哈希表将自动扩容。

哈希表在自动扩容时,一般会创建两倍于原来个数的箱子,因此即使 key 的哈希值不变,对箱子个数取余的结果也会发生改变,因此所有键值对的存放位置都有可能发生改变,这个过程也称为重哈希(rehash)。

哈希表的扩容并不是总是能够有效解决负载因子过大问题。假设所有 key 的哈希值都一样,那么即使扩容以后他们的位置也不会改变。虽然负载因子会降低,但实际存储在每个箱子中的链表长度并不发生改变,因此也就不能提高哈希表的查询性能。

基于以上总结,我们可以发现哈希表的两个问题:

  1. 如果哈希表中本来箱子就比较多,扩容时需要重新哈希并移动数据,性能影响大。

  2. 如果哈希函数设计不合理,哈希表在极端情况下会变成线性表,性能极低。


如果hash 函数设计的好的话,冲突节点是很少的,redis 里面使用了泊松分布来设计hash 函数

/* 
  * Redis hash表结构定义   * 这里就是我们的 hash table 结构,存储着数据库中所有的 key-value,
  * 不管是 sds,还是 set,还是什么结构,都存储在里面
  */
typedef struct dictht { 
    dictEntry **table;   // 哈希表数组
    unsigned long size;  // 哈希表的大小
    unsigned long sizemask; // 哈希表大小掩码
    unsigned long used;  // 哈希表现有节点的数量
} dictht;

实体化一下,如下图所指一个大小为4的空哈希表(Redis默认初始化值为4):

图片.png

/* 
 * 哈希桶 
 * Redis 哈希表中的table数组存放着哈希桶结构(dictEntry)
 * 里面就是Redis的键值对;Redis的dictEntry也是通过链表(next指针)方式来解决hash冲突:
 */
typedef struct dictEntry { 
    void *key;     // 键定义
    // 值定义
    union { 
        void *val;    // 自定义类型
        uint64_t u64; // 无符号整形
        int64_t s64;  // 有符号整形
        double d;     // 浮点型
    } v;     
    struct dictEntry *next;  //指向下一个哈希桶节点
} dictEntry;

图片.png

字典的数据结构如下所示:

/* 字典结构定义 */
typedef struct dict { 
   dictType *type;  // 字典类型
   void *privdata;  // 私有数据
   dictht ht[2];    // 哈希表[两个]
   long rehashidx;   // 记录rehash 进度的标志,值为-1表示rehash未进行
   int iterators;   //  当前正在迭代的迭代器数
} dict;

图片.png

总结一下:

  1. 在Cluster模式下,一个Redis实例对应一个RedisDB(db0);

  2. 一个RedisDB对应一个Dict;

  3. 一个Dict对应2个Dictht,正常情况只用到ht[0];ht[1] 在Rehash时使用。


重要的两个字段是 dictht 和 trehashidx,这两个字段与 rehash 有关,下面重点介绍 rehash。

Rehash

1、Rehash

/*   * 实际扩容触发机制:  * 如果哈希表的已用节点数 >= 哈希表的大小,并且以下条件任一个为真:  * 1) dict_can_resize 为真   * 2) 已用节点数除以哈希表大小之比大于 dict_force_resize_ratio=5  * 那么调用 dictExpand 对哈希表进行扩展,扩展的体积至少为已使用节点数的两倍 

 * hash 表的容量一定是 2 的幂次方  */  

Redis 中 Rehash 的过程。

由上段代码,我们可知 dict 中存储了一个 dictht 的数组,长度为 2,表明这个数据结构中实际存储着两个哈希表 ht[0] 和 ht[1],为什么要存储两张 hash 表呢?

当然是为了 Rehash,Rehash 的过程如下:

为 ht[1] 分配空间。如果是扩容操作,ht[1] 的大小为第一个大于等于 ht[0].used*2 的 2^n;如果是缩容操作,ht[1] 的大小为第一个大于等于 ht[0].used 的 2^n。

将 ht[0] 中的键值 Rehash 到 ht[1] 中。

当 ht[0] 全部迁移到 ht[1] 中后,释放 ht[0],将 ht[1] 置为 ht[0],并为 ht[1] 创建一张新表,为下次 Rehash 做准备。

为什么一定要是2的n次方呢?主要有两个原因:

a.减小哈希冲突概率

       假如当前table数组长度为len,插入节点时,需要对key的hashcode进行哈希,然后跟len-1相与(得到的值一定小于len,避免数组越界) 如果len是2的N次方,那么len-1的后N位二进制一定是全1。假设有两个key,他们的hashcode不同,分别为hashcode1和hashcode2 ,hashcode1和hashcode2 分别与一个后N位全1的二进制相与,结果一定也不同 但是,如果hashcode1和hashcode2 分别与一个后N位非全1的二进制相与,结果有可能相同。也就是说,如果len是2^N,不同hashcode的key计算出来的数组下标一定不同; 否则,不同hashcode的key计算出来的数组下标一定相同。所以Redis 长度为全1,可以减小哈希冲突概率。

b.提高计算下标的效率

       如果len的二进制后n位非全1,与len-1相与时,0与1相与需要取反。如果len的二进制后n位全1,完全不需要取反。

如果len为2N,那么与len-1相与,跟取余len等价,而与运算效率高于取余。如果len不是2N,与len-1相与,跟取余len不等价。

2、渐进式Rehash

由于 Redis 的 Rehash 操作是将 ht[0] 中的键值全部迁移到 ht[1],如果数据量小,则迁移过程很快。但如果数据量很大,一个 Hash 表中存储了几万甚至几百万几千万的键值时,迁移过程很慢并会影响到其他用户的使用。

为了避免 Rehash 对服务器性能造成影响,Redis 采用了一种渐进式 Rehash 的策略,分多次、渐进的将 ht[0] 中的数据迁移到 ht[1] 中。

前一过程如下:

  • 为 ht[1] 分配空间,让字典同时拥有 ht[0] 和 ht[1] 两个哈希表。

  • 字典中维护一个 rehashidx,并将它置为 0,表示 Rehash 开始。

  • 在 Rehash 期间,每次对字典操作时,程序还顺便将 ht[0] 在 rehashidx 索引上的所有键值对 rehash 到 ht[1] 中,当 Rehash 完成后,将 rehashidx 属性+1。当全部 rehash 完成后,将 rehashidx 置为 -1,表示 rehash 完成。

注意:由于维护了两张 Hash 表,所以在 Rehash 的过程中内存会增长。

另外,在 Rehash 过程中,字典会同时使用 ht[0] 和 ht[1]。所以在删除、查找、更新时会在两张表中操作,在查询时会现在第一张表中查询,如果第一张表中没有,则会在第二张表中查询。但新增时一律会在 ht[1] 中进行,确保 ht[0] 中的数据只会减少不会增加。

图片.png

图片.png

图片.png

图片.png

图片.png

图片.png


本文》有 0 条评论

留下一个回复