Redis数据结构源码解析(二) 字典

对比HashMap

字典的使用和底层与Java中的HashMap还是很像的，比较特殊的就是扩容方式。

基本结构

dict

typedef struct dict {
    // 操作类型
    dictType *type;  
    // 依赖的数据
    void *privdata;	 
    // Hash表,是个数组两个元素
    dictht ht[2];
    // -1代表没有进行rehash值，否则代表hash操作进行到了哪个索引
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    // 当前运行的迭代器数
    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;

dictht

typedef struct dictht {  
    // 二维数组
    dictEntry **table;
    // table总大小
    unsigned long size;
    // 掩码=size-1
    unsigned long sizemask;
    // 已经保存的键值对
    unsigned long used;
} dictht;

dictEntry

typedef struct dictEntry {  
    //键
    void *key;
    //值
    union {
        void *val; //值
        uint64_t u64;
        int64_t s64; //过期时间
        double d;
    } v;
    // hash冲突的next指针
    struct dictEntry *next;
} dictEntry;

如何应对Hash冲突

既然使用了Hash表，就逃不掉Hash冲突的问题。

Java中的解决方式

HashMap 使用了数组+链表+红黑树的底层结构，每一个节点对象都会有 next属性，从而形成一个链表结构。当链表长度大于8时会升级为红黑树。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

其实这叫拉链法或者叫链地址法

拉链法

把具有相同散列地址的关键字(同义词)值放在同一个单链表中，称为同义词链表。

添加元素

dictAdd

/* Add an element to the target hash table */
int dictAdd(dict *d, void *key, void *val)
{
    // 新增元素,但是没有设置具体的值
    dictEntry *entry = dictAddRaw(d,key,NULL);
	// 新增失败则返回异常
    if (!entry) return DICT_ERR;
    // 设置真实值
    dictSetVal(d, entry, val);
    return DICT_OK;
}

dictAddRaw

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
    long index;
    dictEntry *entry;
    dictht *ht;

    // 该字典是否在进行 rehash 操作，是则执行一次 rehash
    if (dictIsRehashing(d)) _dictRehashStep(d);

    // 查询某个Key的索引下标,其实就是查询该key是否存在
    // 已存在返回-1
    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
        return NULL;

 	// 是否在进行 rehash 操作中，是则插入至散列表 ht[1] 中，否则插入散列表 ht[0] 
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    entry = zmalloc(sizeof(*entry)); // 申请新节点内存
    entry->next = ht->table[index]; // 将该节点的 next 指针指向 ht->table[index] 指针指向的位置
    ht->table[index] = entry; // 将 ht->table[index] 指针指向该节点
    ht->used++;

    /* Set the hash entry fields. */
    dictSetKey(d, entry, key);
    return entry;
}

其中的 rehash 会在扩容中讲述。

最关键的一个点：ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];。在进行 rehash放入 ht[1]反之则 ht[0]

查询操作

dictFetchValue

void *dictFetchValue(dict *d, const void *key) {
    dictEntry *he;
    // 关键在这一步,查询对应key所在的节点
    he = dictFind(d,key);
    // 根据节点查询里面的value,否则返回NULL
    return he ? dictGetVal(he) : NULL;
}

dictFind

dictEntry *dictFind(dict *d, const void *key)
{
    dictEntry *he;
    uint64_t h, idx, table;
    // 为空
    if (dictSize(d) == 0) return NULL; /* dict is empty */
    // 该字典是否在进行 rehash 操作，是则执行一次 rehash
    if (dictIsRehashing(d)) _dictRehashStep(d);
    // 根据字典的hash函数得到key的hash值
    h = dictHashKey(d, key);
    // 循环两次,分别在ht[0]和ht[1]中查找
    for (table = 0; table <= 1; table++) {
        // 根据hash值与掩码取table中的下标
        idx = h & d->ht[table].sizemask;
        // 获取到对应Entity
        he = d->ht[table].table[idx];
        // 如果出现了hash冲突会逐个遍历链表
        while(he) {
            // 判断key值是不是要查询的目标值
            if (key==he->key || dictCompareKeys(d, key, he->key))
                return he;
            // 遍历下一个元素
            he = he->next;
        }
        if (!dictIsRehashing(d)) return NULL;
    }
    return NULL;
}

几个关键点：

• idx = h & d->ht[table].sizemask; ：在日常开发中这种场景我们更喜欢使用取余（%），因为快、方便；在HashMap中使用的就是取余，但是限制了数组长度为2的幂+位运算快速取余；在Redis中则是使用了掩码进行 &运算

dictGetVal

#define dictGetVal(he) ((he)->v.val)

扩容操作

其实在前面的操作中已经看到了一些关于扩容的影子，例如什么是 rehash？为什么要有 ht[1]和 ht[2]

其实这些都是为了实现一个机制——渐进式扩容。

什么是渐进式扩容

就好像一口吃不成胖子，一口气吃太多吃太快对胃不好，要慢慢吃慢慢长胖

Redis中Hash类型使用了渐进式的扩容机制，因为遇到大Key时会对性能造成巨大的影响。
所以在dict对象中有这样一个属性：dictht ht[2] ，存放了一个长度为2的数组。

ht[0]，是存放数据的 table，作为非扩容时容器；

ht[1]，只有正在进行扩容时才会使用，它也是存放数据的table，长度为 ht[0]的两倍。

扩容时，单线程A负责把数据从 ht[0] 复制到 ht[1] 中。如果这时有其他线程
进行读操作：会先去 ht[0]中找，找不到再去 ht[1]中找。
进行写操作：直接写在 ht[1]中。
进行删除操作：与读类似。

扩容流程

int _dictExpand(dict *d, unsigned long size, int* malloc_failed)
{
    if (malloc_failed) *malloc_failed = 0;

    //  如果此时正在扩容，或者是扩容大小小于 ht[0] 的表大小，则抛错
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;

    dictht n;  // new了一个新的hash表
    unsigned long realsize = _dictNextPower(size);

    // 是否存在溢出可能
    if (realsize < size || realsize * sizeof(dictEntry*) < realsize)
        return DICT_ERR;

    // 重新计算的值如果和原来的 size 相等，则无效
    if (realsize == d->ht[0].size) return DICT_ERR;

    // 分配新 Hash 表，并初始化所有指针为 NULL
    n.size = realsize;
    n.sizemask = realsize-1;
    if (malloc_failed) {
        n.table = ztrycalloc(realsize*sizeof(dictEntry*));
        *malloc_failed = n.table == NULL;
        if (*malloc_failed)
            return DICT_ERR;
    } else
        n.table = zcalloc(realsize*sizeof(dictEntry*));

    n.used = 0;

    // 初始化的情况，而不是进行 rehash 操作，就用 ht[0] 来接收值
    if (d->ht[0].table == NULL) {
        // 如果是初始化阶段,赋值后直接就结束了
        d->ht[0] = n;
        return DICT_OK;
    }

    /* 准备第二个 Hash 表，以便执行渐进式哈希操作 */
    d->ht[1] = n;
    d->rehashidx = 0;
    return DICT_OK;
}

redis中的key可能有成千上万，如果一次性扩容，会对性能造成巨大的影响，所以redis使用渐进式扩容，每次执行插入，删除，查找，修改等操作前，都先判断当前字典的rehash操作是否在进行，如果是在进行中，就对当前节点进行rehash操作，只执行一次。除此之外，当服务器空闲时，也会调用incrementallyRehash函数进行批量操作，每次100个节点，大概一毫秒。将rehash操作进行分而治之。

渐进式rehash流程

rehash的准备工作

• 设置字典的 rehashidx 为 0 ，标识着 rehash 的开始；
• 为 ht[1]->table 分配空间，大小至少为 ht[0]->used 的两倍；

dictRehash

int dictRehash(dict *d, int n) {
    // 一次最多rehash n*10个空桶 n的大小根据触发场景而定
    // 在添加新的元素时也会触发Rehash操作 _dictRehashStep n=1,一次最多rehash10个空桶
    // dictRehashMilliseconds 在给定毫秒内，对字典进行rehash的一个方法,n=100,一次最多1000个空桶
    int empty_visits = n*10; 
    // 如果不在Rehash则返回0
    if (!dictIsRehashing(d)) return 0;
	// 开始循环，执行
    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;
        // 为防止 rehashidx 越界，当 rehashidx 大于 ht[0] 的数组大小时，不继续执行 
        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        // d->rehashidx 是记录着上一次rehash进行到了哪一个索引
        // 一直往下遍历,直到遇到不是空桶的就结束(前提是没有因为空桶数而终止)
        while(d->ht[0].table[d->rehashidx] == NULL) {
            // 如果为空表示当前索引rehash成功 +1
            // 并且空桶数+1
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        // 这个桶一定是有数据的
        de = d->ht[0].table[d->rehashidx];
        // 遍历桶中元素，移动元素至新表
        while(de) {
            uint64_t h;

            nextde = de->next;
            // 获取在新桶时的下标
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            // 此处使用了头插法
            de->next = d->ht[1].table[h]; 
            d->ht[1].table[h] = de; 
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }
        // 处理完成 设置为空
        d->ht[0].table[d->rehashidx] = NULL;
        d->rehashidx++;
    }

    // 检查是否已经 rehash 完成
    if (d->ht[0].used == 0) {
        zfree(d->ht[0].table);
        d->ht[0] = d->ht[1];
        _dictReset(&d->ht[1]);
        d->rehashidx = -1;
        return 0;
    }

    /* More to rehash... */
    return 1;
}

• 首先梳理 dictRehash方法，N和N*10的关系。

  • 一次 dictRehash方法最多迁移N个桶。
  • 但是每次 dictRehash不一定都是需要迁移的，可能有些桶的数据为NULL，遇到N*10次空桶则结束（为什么这么做？不能无休止的让他遍历下去，防止过久的阻塞）

• 关于头插法

  • de->next = d->ht[1].table[h]; 首先将 ht1中的de对象的尾节点
  • 再将de对象设置到 d->ht[1].table[h]

总结

• Redis 中的数据库和哈希键都基于字典来实现。

• 字典是由键值对构成的抽象数据结构。

• Redis自己实现了一套哈希表的逻辑，与Java中的HashMap相似但是不完全一样，拿两者比较的总结一下。

  • 两者都通过拉链法解决了Hash冲突问题，只不过HashMap有升级红黑树的机制，Redis没有
  • Redis实现了逐渐式扩容，不会一下子把所有Key进行迁移（遇到大Key可能出现异常）；HashMap就是普通的迁移。
    • 逐渐式扩容使Redis底层需要使用到两个Hash表，一般情况下只使用 0 号哈希表，只有在 rehash 进行时，才会同时使用 0 号和 1 号哈希表。
  • HashMap通过指定规则：数组长度为2的幂+位运算进行取数组下标；Redis使用掩码的方式。
  • HashMap在1.8之前为头插法，之后为尾插法；Redis中一直为头插法。

致谢

• Redis源码解析 - 有赞技术团队
• Redis 设计与实现