「Redis源码解读」—数据结构（二）哈希表

2019-06-30 本文已影响0人 wh4763

Redis的字典使用哈希表作为底层实现

知识点

1.数据结构

哈希节点
哈希表
类型处理函数

2.哈希

哈希算法
哈希冲突
索引定位

3.rehash

哈希表扩展
哈希表收缩
负载因子

4.渐进式rehash

数据结构定义

//哈希表
typedef struct dictht {
    dictEntry **table;             // 哈希表数组
    unsigned long size;            // 哈希表数组的大小
    unsigned long sizemask;        // 用于映射位置的掩码，值永远等于(size-1)
    unsigned long used;            // 哈希表已有节点的数量
} dictht;
//哈希节点
typedef struct dictEntry {
    void *key;                  // 键
    union {                     // 值
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;     // 指向下一个哈希表节点，形成单向链表
} dictEntry;
//字典
typedef struct dict {
    dictType *type;                        // 和类型相关的处理函数
    void *privdata;                        // 上述类型函数对应的可选参数
    dictht ht[2];                          // 两张哈希表，ht[0]为原生哈希表，ht[1]为 rehash 哈希表
    long rehashidx;                        // 当等于-1时表示没有在 rehash，否则表示 rehash 的下标
    int iterators;                         // 迭代器数量(暂且不谈)
} dict;

概述

字典被广泛用于实现Redis的各种功能，其中包括数据库和哈希键
redis中对字典倍用作数据库的底层实现，每个字典带有两个哈希表，一个平时使用，另一个仅在进行rehash时使用。
redis使用MurmurHash算法来计算键的哈希值
哈希表使用链地址法来解决哈希冲突，被分配到同一个索引上的多个键值对会连接成为一个单向链表
在对哈希表进行扩展或者收缩操作时，程序需要将现有哈希表包含对所有键值对rehash到新哈希表里面，并且这个rehash过程并不是一次性地完成的，而是渐进式地完成。

索引定位

当要将一个新的键值对添加到字典里面或者通过键查找值的时候都需要执行哈希算法，主要是获得一个需要插入或者查找的dictEntry 所在下标的索引，具体算法如下：
1.计算得到该键对应的哈希值
2.将哈希值和哈希表的 sizemask 属性做位与，得到索引值 index，其中 ht[x] 可以是 ht[0] 或者 ht[1]

冲突解决

哈希的冲突一定发生在键值对插入时:
判断当前的字典是否在进行 rehash，如果是，则执行一步 rehash，否则忽略。判断 rehash 的依据就是 rehashidx 是否为 -1；
通过 _dictKeyIndex 找到一个索引，如果返回-1表明字典中已经存在相同的 key；
根据是否在 rehash 选择对应的哈希表；
分配哈希表节点 dictEntry 的内存空间，执行插入，插入操作始终在链表头插入，这样可以保证每次的插入操作的时间复杂度一定是 O(1) 的，插入完毕，used属性自增；

rehash

随着字典操作的不断执行，哈希表保存的键值对会不断增多（或者减少），为了让哈希表的负载因子维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，需要对哈希表大小进行扩展或者收缩。

1.负载因子
当前已使用结点数量除上哈希表的大小，即：

load_factor = ht[0].used / ht[0].size

2.哈希表扩展

服务器目前没有在执行BGSAVE或者BGREWRITEAOP命令当哈希表当负载因子大于1时进行扩展。
服务器目前正在执行BGSAVE或者BGREWRITEAOP命令当哈希表的负载因子大于5时进行扩展。
扩展时为 ht[1] 分配空间，大小为第一个大于等于 ht[0].used * 2 的 2 的幂；
将保存在 ht[0] 上的键值对 rehash 到 ht[1] 上，rehash 就是重新计算哈希值和索引，并且重新插入到 ht[1] 中，插入一个删除一个；
当 ht[0] 包含的所有键值对全部 rehash 到 ht[1] 上后，释放 ht[0] 的控件，将 ht[1] 设置为 ht[0]，并且在 ht[1] 上新创件一个空的哈希表，为下一次 rehash 做准备；

渐进式rehash

扩展或者收缩哈希表的时候，需要将 ht[0] 里面所有的键值对 rehash 到 ht[1] 里，当键值对数量非常多的时候，这个操作如果在一帧内完成，大量的计算很可能导致服务器宕机，所以不能一次性完成，需要渐进式的完成。

渐进式 rehash 的详细步骤如下：
1、为 ht[1] 分配指定空间，让字典同时持有 ht[0] 和 ht[1] 两个哈希表；
2、将 rehashidx 设置为0，表示正式开始 rehash，前两步是在 dict.c/dictExpand 中实现的
3、在进行 rehash 期间，每次对字典执行增、删、改、查操作时，程序除了执行指定的操作外，还会将哈希表 ht[0].table中下标为 rehashidx 位置上的所有的键值对全部迁移到 ht[1].table 上，完成后 rehashidx 自增。这一步就是 rehash 的关键一步。为了防止 ht[0] 是个稀疏表（遍历很久遇到的都是NULL），从而导致函数阻塞时间太长，这里引入了一个 “最大空格访问数”，也即代码中的 enmty_visits，初始值为 n*10。当遇到NULL的数量超过这个初始值直接返回。
4.最后，当 ht[0].used 变为0时，代表所有的键值对都已经从 ht[0] 迁移到 ht[1] 了，释放 ht[0].table，并且将 ht[0] 设置为 ht[1]，rehashidx 标记为 -1 代表 rehash 结束。