关于java:Redis源码剖析之字典dict

Dict 在 redis 中是最为外围的一个数据结构，因为它承载了 redis 里的所有数据，你能够简略粗犷的认为 redis 就是一个大的 dict，外面存储的所有的 key-value。

redis 中 dict 的实质其实就是一个 hashtable，所以它也须要思考所有 hashtable 所有的问题，如何组织 K -V、如何解决 hash 抵触、扩容策略及扩容形式……。实际上 Redis 中 hashtable 的实现形式就是一般的 hashtable，但 Redis 翻新的引入了 渐进式 hash以减小 hashtable 扩容是对性能带来的影响，接下来咱们就来看看 redis 中 hashtable 的具体实现。

dict 的定义在 dict.h 中，其各个字段及其含意如下：

typedef struct dict {
    dictType *type;  // dictType 构造的指针，封装了很多数据操作的函数指针，使得 dict 能解决任意数据类型（相似面向对象语言的 interface，能够重载其办法）void *privdata;  // 一个公有数据指针(privdata), 由调用者在创立 dict 的时候传进来。dictht ht[2];  // 两个 hashtable，ht[0]为主，ht[1]在渐进式 hash 的过程中才会用到。long rehashidx; /* 增量 hash 过程过程中记录 rehash 执行到第几个 bucket 了，当 rehashidx == - 1 示意没有在做 rehash */
    unsigned long iterators; /* 正在运行的迭代器数量 */
} dict;

重点介绍下 dictType *type 字段(个人感觉命名为 type 不太适合)，其作用就是为了让 dict 反对各种数据类型，因为不同的数据类型须要对应不同的操作函数，比方计算 hashcode 字符串和整数的计算形式就不一样，所以 dictType 通过函数指针的形式，将不同数据类型的操作都封装起来。从面相对象的角度来看，能够把 dictType 当成 dict 中各种数据类型相干操作的 interface，各个数据类型只须要实现其对应的数据操作就行。dictType 中封装了以下几个函数指针。

typedef struct dictType {uint64_t (*hashFunction)(const void *key);  // 对 key 生成 hash 值 
    void *(*keyDup)(void *privdata, const void *key); // 对 key 进行拷贝 
    void *(*valDup)(void *privdata, const void *obj);  // 对 val 进行拷贝
    int (*keyCompare)(void *privdata, const void *key1, const void *key2); // 两个 key 的比照函数
    void (*keyDestructor)(void *privdata, void *key); // key 的销毁
    void (*valDestructor)(void *privdata, void *obj); // val 的销毁 
} dictType;

dict 中还有另外一个重要的字段 dictht ht[2]，dictht 其实就是 hashtable，但这里为什么是 ht[2]? 这就不得不提到 redis dict 的 渐进式 hash，dict 的 hashtable 的扩容不是一次性实现的，它是先建设一个大的新的 hashtable 寄存在 ht[1]中，而后逐步把 ht[0]的数据迁徙到 ht[1]中，rehashidx就是 ht[0]中数据迁徙的进度，渐进式 hash 的过程会在后文中详解。

这里咱们来看下 dictht 的定义：

typedef struct dictht {
    dictEntry **table;  // hashtable 中的间断空间 
    unsigned long size; // table 的大小 
    unsigned long sizemask;  // hashcode 的掩码  
    unsigned long used; // 已存储的数据个数
} dictht;

其中 dictEntry 就是对 dict 中每对 key-value 的封装，除了具体的 key-value，其还蕴含一些其余信息，具体如下：

typedef struct dictEntry {
    void *key;
    union {   // dictEntry 在不同用处时存储不同的数据 
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; // hash 抵触时开链，单链表的 next 指针 
} dictEntry;

dict 中的 hashtable 在呈现 hash 抵触时采纳的是开链形式，如果有多个 entry 落在同一个 bucket 中，那么他们就会串成一个单链表存储。

如果咱们将 dict 在内存中的存储绘制进去，会是下图这个样子。

在看 dict 几个外围 API 实现之前，咱们先来看下 dict 的扩容，也就是 redis 的渐进式 hash。何为渐进式 hash？redis 为什么采纳渐进式 hash？渐进式 hash 又是如何实现的？

要答复这些问题，咱们先来思考下 hashtable 扩容的过程。如果相熟 java 的同学可能晓得，java 中 hashmap 的扩容是在数据元素达到某个阈值后，新建一个更大的空间，一次性把旧数据搬过来，搬完之后再持续后续的操作。如果数据量过大的话，HashMap 扩容是十分耗时的，所有有些编程标准举荐 new HashMap 时最好指定其容量，防止出现主动扩容。

然而 redis 在新建 dict 的时候，没法晓得数据量大小，如果间接采纳 java hashmap 的扩容形式，因为 redis 是单线程的，势必在扩容过程中啥都干不了，阻塞掉前面的申请，最终影响到整个 redis 的性能。如何解决？其实也很简略，就是 化整为零，将一次大的扩容操作拆分成屡次小的步骤，一步步来缩小扩容对其余操作的影响，其具体实现如下：

上文中咱们曾经看到了在 dict 的定义中有个 dictht ht[2]，dict 在扩容过程中会有两个 hashtable 别离存储在 ht[0] 和 ht[1]中，其中 ht[0]是旧的 hashtable，ht[1]是新的更大的 hashtable。

/* 查看是否 dict 须要扩容 */
static int _dictExpandIfNeeded(dict *d)
{
    /* 曾经在渐进式 hash 的流程中了，间接返回 */
    if (dictIsRehashing(d)) return DICT_OK;

    /* If the hash table is empty expand it to the initial size. */
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

    /* 当配置了可扩容时，容量负载达到 100% 就扩容。配置不可扩容时，负载达到 5 也会强制扩容 */
    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].used*2); // 扩容一倍容量
    }
    return DICT_OK;
}

Redis 在每次查找某个 key 的索引下标时都会查看是否须要对 ht[0]做扩容，如果配置的是能够扩容那么当 hashtable 使用率超过 100%(uesed/size)就触发扩容，否则使用率操作 500% 时强制扩容。执行扩容的代码如下：

/* dict 的创立和扩容 */ 
int dictExpand(dict *d, unsigned long size)
{
    /* 如果 size 比 hashtable 中的元素个数还小，那 size 就是有效的，间接返回 error */
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;

    dictht n; /* 新的 hashtable */
    // 扩容时新 table 容量是大于以后 size 的最小 2 的幂次方，但有下限 
    unsigned long realsize = _dictNextPower(size);

    // 如果新容量和旧容量统一，没有必要继续执行了，返回 err
    if (realsize == d->ht[0].size) return DICT_ERR;

    /* 新建一个容量更大的 hashtable */
    n.size = realsize;
    n.sizemask = realsize-1;
    n.table = zcalloc(realsize*sizeof(dictEntry*));
    n.used = 0;

    // 如果是 dict 初始化的状况，间接把新建的 hashtable 赋值给 ht[0]就行 
    if (d->ht[0].table == NULL) {d->ht[0] = n;
        return DICT_OK;
    }

    // 非初始化的状况，将新表赋值给 ht[1], 而后标记 rehashidx 0
    d->ht[1] = n;
    d->rehashidx = 0; // rehashidx 示意以后 rehash 到 ht[0]的下标地位
    return DICT_OK;
}

这里 dictExpand 只是创立了新的空间，将 rehashidx 标记为 0(rehashidx==- 1 示意不在 rehash 的过程中)，并未对 ht[0] 中的数据迁徙到 ht[1]中 。数据迁徙的逻辑都在_dictRehashStep() 中。\_dictRehashStep()是只迁徙一个 bucket，它在 dict 的查找、插入、删除的过程中都会被调到，每次调用至多迁徙一个 bucket。 而 dictRehash()是_dictRehashStep()的具体实现，代码如下：

 /* redis 渐进式 hash，采纳分批的形式，逐步将 ht[0]依下标转移到 ht[2], 防止了 hashtable 扩容时大量
 * 数据迁徙导致的性能问题
 * 参数 n 是指这次 rehash 只做 n 个 bucket */
int dictRehash(dict *d, int n) {
    int empty_visits = n*10; /* 最大空 bucket 数量，如果遇到 empty_visits 个空 bucket，间接完结以后 rehash 的过程 */
    if (!dictIsRehashing(d)) return 0;

    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;

        /* Note that rehashidx can't overflow as we are sure there are more
         * elements because ht[0].used != 0 */
        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1; // 如果遇到了 empty_visits 个空的 bucket，间接完结 
        }
        // 遍历以后 bucket 中的链表，间接将其挪动到新的 hashtable 中  
        de = d->ht[0].table[d->rehashidx];
        /* 把所有的 key 从旧的 hash 桶移到新的 hash 桶中 */
        while(de) {
            uint64_t h;

            nextde = de->next;
            /* 获取到 key 在新 hashtable 中的下标 */
            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);  // 开释旧 ht 所占用的内存空间  
        d->ht[0] = d->ht[1];  // ht[0]始终是在用 ht，ht[1]始终是新 ht，ht0 全迁徙到 ht1 后会替换下  
        _dictReset(&d->ht[1]);
        d->rehashidx = -1;   
        return 0;  // 如果全表 hash 完，返回 0
    }

    /* 还须要持续做 hash 返回 1 */
    return 1;
}

能够看出，rehash 就是分批次把 ht[0]中的数据搬到 ht[1]中，这样将原有的一个大操作拆分为很多个小操作逐渐进行，防止了 redis 产生 dict 扩容是刹时不可用的状况，毛病是在 redis 扩容过程中会占用俩份存储空间，而且占用工夫会比拟长。

/* 向 dict 中增加元素 */
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;
}

/* 增加和查找的底层实现：* 这个函数只会返回 key 对应的 entry，并不会设置 key 对应的 value，而是把设值权交给调用者。* 
 * 这个函数也作为一个 API 间接裸露给用户调用，次要是为了在 dict 中存储非指针类的数据，比方
 * entry = dictAddRaw(dict,mykey,NULL);
 * if (entry != NULL) dictSetSignedIntegerVal(entry,1000);
 *
 * 返回值:
 * 如果 key 曾经存在于 dict 中了，间接返回 null，并把曾经存在的 entry 指针放到 &existing 里。否则
 * 为 key 新建一个 entry 并返回其指针。*/
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
    long index;
    dictEntry *entry;
    dictht *ht;

    if (dictIsRehashing(d)) _dictRehashStep(d);

    /* 获取到新元素的下标，如果返回 - 1 标识该元素曾经存在于 dict 中了，间接返回 null */
    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
        return NULL;

    /* 否则就给新元素分配内存，并将其插入到链表的头部(个别新插入的数据被拜访的频次会更高)*/
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    entry = zmalloc(sizeof(*entry));
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used++;

    /* 如果是新建的 entry，须要把 key 填进去 */
    dictSetKey(d, entry, key);
    return entry;
}

插入过程也比较简单，就是先定位 bucket 的下标，而后插入到单链表的头节点，留神这里也须要思考到 rehash 的状况，如果是在 rehash 过程中，新数据肯定是插入到 ht[1]中的。

dictEntry *dictFind(dict *d, const void *key)
{
    dictEntry *he;
    uint64_t h, idx, table;

    if (dictSize(d) == 0) return NULL; /* dict 为空 */
    if (dictIsRehashing(d)) _dictRehashStep(d);
    h = dictHashKey(d, key);
    // 查找的过程中，可能正在 rehash 中，所以新老两个 hashtable 都须要查 
    for (table = 0; table <= 1; table++) {idx = h & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        while(he) {if (key==he->key || dictCompareKeys(d, key, he->key))
                return he;
            he = he->next;
        }
        // 如果 ht[0]中没找到，且不再 rehas 中，就不须要持续找了 ht[1]了。if (!dictIsRehashing(d)) return NULL;
    }
    return NULL;
}

查找的过程比较简单，就是用 hashcode 做定位，而后遍历单链表。但这里须要思考到如果是在 rehash 过程中，可能须要查找 ht[2]中的两个 hashtable。

/* 查找并删除一个元素，是 dictDelete()和 dictUnlink()的辅助函数。*/
static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
    uint64_t h, idx;
    dictEntry *he, *prevHe;
    int table;

    if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL;

    if (dictIsRehashing(d)) _dictRehashStep(d);
    h = dictHashKey(d, key);

    // 这里也是须要思考到 rehash 的状况，ht[0]和 ht[1]中的数据都要删除掉 
    for (table = 0; table <= 1; table++) {idx = h & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        prevHe = NULL;
        while(he) {if (key==he->key || dictCompareKeys(d, key, he->key)) {
                /* 从列表中 unlink 掉元素 */
                if (prevHe)
                    prevHe->next = he->next;
                else
                    d->ht[table].table[idx] = he->next;
                // 如果 nofree 是 0，须要开释 k 和 v 对应的内存空间 
                if (!nofree) {dictFreeKey(d, he);
                    dictFreeVal(d, he);
                    zfree(he);
                }
                d->ht[table].used--;
                return he;
            }
            prevHe = he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    return NULL; /* 没找到 key 对应的数据 */
}

其余的 API 实现都比较简单，我在 dict.c 源码中做了大量的正文，有趣味能够自行浏览下，我这里仅列举并阐明下其大抵的性能。

dict *dictCreate(dictType *type, void *privDataPtr);  // 创立 dict 
int dictExpand(dict *d, unsigned long size);  // 扩缩容
int dictAdd(dict *d, void *key, void *val);  // 增加 k -v
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing); // 增加的 key 对应的 dictEntry 
dictEntry *dictAddOrFind(dict *d, void *key); // 增加或者查找 
int dictReplace(dict *d, void *key, void *val); // 替换 key 对应的 value，如果没有就增加新的 k -v
int dictDelete(dict *d, const void *key);  // 删除某个 key 对应的数据 
dictEntry *dictUnlink(dict *ht, const void *key); // 卸载某个 key 对应的 entry 
void dictFreeUnlinkedEntry(dict *d, dictEntry *he); // 卸载并革除 key 对应的 entry
void dictRelease(dict *d);  // 开释整个 dict 
dictEntry * dictFind(dict *d, const void *key);  // 数据查找
void *dictFetchValue(dict *d, const void *key);  // 获取 key 对应的 value
int dictResize(dict *d);  // 重设 dict 的大小，次要是缩容用的
/************    迭代器相干     *********** */
dictIterator *dictGetIterator(dict *d);  
dictIterator *dictGetSafeIterator(dict *d);
dictEntry *dictNext(dictIterator *iter);
void dictReleaseIterator(dictIterator *iter);
/************    迭代器相干     *********** */
dictEntry *dictGetRandomKey(dict *d);  // 随机返回一个 entry 
dictEntry *dictGetFairRandomKey(dict *d);   // 随机返回一个 entry，但返回每个 entry 的概率会更平均 
unsigned int dictGetSomeKeys(dict *d, dictEntry **des, unsigned int count); // 获取 dict 中的局部数据

其余的 API 见代码 dict.c 和 dict.h.

本文是 Redis 源码分析系列博文，同时也有与之对应的 Redis 中文正文版，有想深刻学习 Redis 的同学，欢送 star 和关注。
Redis 中文注解版仓库：https://github.com/xindoo/Redis
Redis 源码分析专栏：https://zxs.io/s/1h
如果感觉本文对你有用，欢送 一键三连。

关于java:Redis源码剖析之字典dict

Redis 中 Dict 的实现

扩容

外围 API

插入

查找

删除

其它 API