当前位置:首页 > 缓存 > 正文内容

redis中字典的底层实现

phpmianshi4年前 (2017-05-17)缓存183

哈希表概述

       表现为:存储位置 = 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


版权声明:本文由PHP面试资料网发布,如需转载请注明出处。
分享给朋友:

相关文章

redis中缓存穿透与缓存雪崩缓存击穿

背景缓存系统不得不考虑的另一个问题是缓存穿透与失效时的雪崩效应。缓存穿透缓存穿透是指查询一个一定不存在的数据,由于缓存是不命中时被动写的,并且出于容错考虑,如果从存储层查不到数据则不写入缓存,这将导致...

redis中分析key大小的几种方法

背景当redis被用作缓存时,有时我们希望了解key的大小分布,或者想知道哪些key占的空间比较大。本文提供了几种方法。一. bigKeys这是redis-cli自带的一个命令。对整个redis进行扫...

redis的bigkey问题如何解决

寻找big key有如下几种方法redis-cli自带--bigkeys,例如:redis-cli -h -a --bigkeys获取生产Redis的rdb文件,通过rdbtools分析rdb生成cs...

redis中底层的编码转换

redis中底层的编码转换

编码转化Redis 使用对象(redisObject)来表示数据库中的键值,当我们在 Redis 中创建一个键值对时,至少创建两个对象,一个对象是用做键值对的键对象,另一...

redis中字符串的底层实现-SDS

redis中字符串的底层实现-SDS

概述Redis 是用 C 语言开发完成的,但在 Redis 字符串中,并没有使用 C 语言中的字符串,而是用一种称为 S...

Redis中主从复制的原理详解

主从复制的方式命令slaveof。优点:无需重启。缺点:不便于管理 // 命令行使用 slaveof ip port // 使用命令后自身...

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。