Redis 中的 dict 实现

[junnplus]

Redis 的字典（dict）使用哈希表（hashtable）作为底层实现：

// 5.0.3/src/dict.h

/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

哈希表结构体比较简单：

• table 表示哈希数组，
• size 表示哈希表大小（哈希数组长度），
• sizemask 表示哈希表大小掩码，用来计算键在哈希表数组上的索引值，
• used 表示哈希表有多少键值对，

二级 table 指针指向一个 dictEntry 结构体的数组，每个 dictEntry 保存了一个键值对：

// 5.0.3/src/dict.h

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

键是一个指针，值可以是一个指针、64 位的整数或浮点数。 next 指针指向下一个键值对，用来解决哈希冲突（链地址法）。

一个大小为 4 的哈希表：

Redis 中的字典有两个哈希表结构：

// 5.0.3/src/dict.h

typedef struct dict {
    ...
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

通常情况下只有哈希表 ht[0] 是有值，那为什么需要两个哈希表呢？

我们知道哈希函数不可避免的会产生哈希冲突，冲突会影响查询效率，产生冲突的多少有以下三个因素：

• 哈希函数
• 解决冲突方法
• 哈希表的负载因子（哈希表键值对个数/哈希表大小）

在哈希函数和解决冲突方法确定的情况下，为了让哈希表的负载因子（load factor）维持在一个合理的范围之内，当 ht[0] 保存的键值对数量太多或者太少时，就需要借助哈希表 ht[1] 对哈希表 ht[0] 进行相应的扩容或者缩容，把哈希表 ht[0] 的键值对迁移到哈希表 ht[1] 上，然后用哈希表 ht[1] 替换哈希表 ht[0]。

迁移过程是通过执行 rehash 操作来完成，rehashidx 属性记录 rehash 操作的进度，-1 表示没有正在进行 rehash。

// 5.0.3/src/dict.h

#define dictIsRehashing(d) ((d)->rehashidx != -1)

rehash

// 5.0.3/src/dict.c

/* Performs N steps of incremental rehashing. Returns 1 if there are still
 * keys to move from the old to the new hash table, otherwise 0 is returned.
 *
 * Note that a rehashing step consists in moving a bucket (that may have more
 * than one key as we use chaining) from the old to the new hash table, however
 * since part of the hash table may be composed of empty spaces, it is not
 * guaranteed that this function will rehash even a single bucket, since it
 * will visit at max N*10 empty buckets in total, otherwise the amount of
 * work it does would be unbound and the function may block for a long time. */
int dictRehash(dict *d, int n) {
    int empty_visits = n*10; /* Max number of empty buckets to visit. */
    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;
        }
        de = d->ht[0].table[d->rehashidx];
        /* Move all the keys in this bucket from the old to the new hash HT */
        while(de) {
            uint64_t h;

            nextde = de->next;
            /* Get the index in the new hash table */
            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++;
    }

    /* Check if we already rehashed the whole table... */
    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 函数一次循环 rehash 一个槽位的所有键值对：

• 从 d->rehashidx 开始遍历哈希表 ht[0]， 寻找可 rehash 的槽位，跳过没有键值对的槽位，
• 遍历槽位中的键值对，重新计算键的哈希值和在哈希表 ht[1] 上的索引值，然后将键值对放到哈希表 ht[1] 的指定位置上，
• 将槽位指针指空，d->rehashidx 值增一。

如果哈希表 ht[0] 的所有键值对都 rehash 到哈希表 ht[1]，就用哈希表 ht[1] 替换哈希表 ht[0]，释放哈希表 ht[0] 以及设置 d->rehashidx 为初始值 -1。

[junnplus]

创建

// 5.0.3/src/dict.c

/* Create a new hash table */
dict *dictCreate(dictType *type,
        void *privDataPtr)
{
    dict *d = zmalloc(sizeof(*d));

    _dictInit(d,type,privDataPtr);
    return d;
}

/* Initialize the hash table */
int _dictInit(dict *d, dictType *type,
        void *privDataPtr)
{
    _dictReset(&d->ht[0]);
    _dictReset(&d->ht[1]);
    ...
    d->rehashidx = -1;
    d->iterators = 0;
    return DICT_OK;
}

static void _dictReset(dictht *ht)
{
    ht->table = NULL;
    ht->size = 0;
    ht->sizemask = 0;
    ht->used = 0;
}

dictCreate 函数创建包含两个空哈希表的字典。

[junnplus]

查找

// 5.0.3/src/dict.c

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

    if (d->ht[0].used + d->ht[1].used == 0) return NULL; /* dict is empty */
    if (dictIsRehashing(d)) _dictRehashStep(d);
    h = dictHashKey(d, key);
    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;
        }
        if (!dictIsRehashing(d)) return NULL;
    }
    return NULL;
}

rehash 期间的查找会触发一次槽位的 rehash：

/* This function performs just a step of rehashing, and only if there are
 * no safe iterators bound to our hash table. When we have iterators in the
 * middle of a rehashing we can't mess with the two hash tables otherwise
 * some element can be missed or duplicated.
 *
 * This function is called by common lookup or update operations in the
 * dictionary so that the hash table automatically migrates from H1 to H2
 * while it is actively used. */
static void _dictRehashStep(dict *d) {
    if (d->iterators == 0) dictRehash(d,1);
}

rehash 之后在两个哈希表上查找：

• 确定键在哈希数组上的索引，
• 遍历索引位置上的键值对链表。

[junnplus]

添加

// 5.0.3/src/dict.c

/* 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;
}

/* Low level add or find:
 * This function adds the entry but instead of setting a value returns the
 * dictEntry structure to the user, that will make sure to fill the value
 * field as he wishes.
 *
 * This function is also directly exposed to the user API to be called
 * mainly in order to store non-pointers inside the hash value, example:
 *
 * entry = dictAddRaw(dict,mykey,NULL);
 * if (entry != NULL) dictSetSignedIntegerVal(entry,1000);
 *
 * Return values:
 *
 * If key already exists NULL is returned, and "*existing" is populated
 * with the existing entry if existing is not NULL.
 *
 * If key was added, the hash entry is returned to be manipulated by the caller.
 */
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
    long index;
    dictEntry *entry;
    dictht *ht;

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

    /* Get the index of the new element, or -1 if
     * the element already exists. */
    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
        return NULL;

    /* Allocate the memory and store the new entry.
     * Insert the element in top, with the assumption that in a database
     * system it is more likely that recently added entries are accessed
     * more frequently. */
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    entry = zmalloc(sizeof(*entry));
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used++;

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

rehash 期间的插入操作也会触发一次槽位 rehash。

dictAddRaw 函数通过 _dictKeyIndex 返回的索引值来确认键是否在哈希表中，不存在的话插入一个新的键值对在哈希表的槽位上。

// 5.0.3/src/dict.c

/* Returns the index of a free slot that can be populated with
 * a hash entry for the given 'key'.
 * If the key already exists, -1 is returned
 * and the optional output parameter may be filled.
 *
 * Note that if we are in the process of rehashing the hash table, the
 * index is always returned in the context of the second (new) hash table. */
static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing)
{
    unsigned long idx, table;
    dictEntry *he;
    if (existing) *existing = NULL;

    /* Expand the hash table if needed */
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;
    for (table = 0; table <= 1; table++) {
        idx = hash & d->ht[table].sizemask;
        /* Search if this slot does not already contain the given key */
        he = d->ht[table].table[idx];
        while(he) {
            if (key==he->key || dictCompareKeys(d, key, he->key)) {
                if (existing) *existing = he;
                return -1;
            }
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    return idx;
}

_dictKeyIndex 函数计算键的 hash 值在哈希表上的索引，也可以通过参数 existing 来查找键对应的键值对。

需要注意的是，_dictKeyIndex 函数会检查哈希表是否需要扩容：

// 5.0.3/src/dict.c

 * Note that even when dict_can_resize is set to 0, not all resizes are
 * prevented: a hash table is still allowed to grow if the ratio between
 * the number of elements and the buckets > dict_force_resize_ratio. */
static int dict_can_resize = 1;
static unsigned int dict_force_resize_ratio = 5;

/* Expand the hash table if needed */
static int _dictExpandIfNeeded(dict *d)
{
    /* Incremental rehashing already in progress. Return. */
    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);

    /* If we reached the 1:1 ratio, and we are allowed to resize the hash
     * table (global setting) or we should avoid it but the ratio between
     * elements/buckets is over the "safe" threshold, we resize doubling
     * the number of buckets. */
    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;
}

哈希表扩容条件：

• 正在 rehash 不会进行扩容，
• 哈希表的大小为 0，扩容到初始大小 DICT_HT_INITIAL_SIZE，
• 正常情况下 dict_can_resize 为 1，哈希表中键值对个数大于哈希表大小，就会扩容到键值对个数的两倍，
• 有些情况下 dict_can_resize 为 0，Redis 会避免扩容，但是如果哈希表已经很满（负载因子大于 5），这时候会强制扩容。

可以扩容就调用 dictExpand 函数调整哈希表的大小，如果进入 rehash 状态就需要把新的键值对插入到哈希表 ht[1] 上。

扩容

哈希表的大小由 dictExpand 函数调整：

// 5.0.3/src/dict.c

/* Expand or create the hash table */
int dictExpand(dict *d, unsigned long size)
{
    /* the size is invalid if it is smaller than the number of
     * elements already inside the hash table */
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;

    dictht n; /* the new hash table */
    unsigned long realsize = _dictNextPower(size);

    /* Rehashing to the same table size is not useful. */
    if (realsize == d->ht[0].size) return DICT_ERR;

    ...

size 决定调整的大小，实际调整的大小会通过 _dictNextPower 函数自动转化为 2 的下一个幂。

    /* Allocate the new hash table and initialize all pointers to NULL */
    n.size = realsize;
    n.sizemask = realsize-1;
    n.table = zcalloc(realsize*sizeof(dictEntry*));
    n.used = 0;

    /* Is this the first initialization? If so it's not really a rehashing
     * we just set the first hash table so that it can accept keys. */
    if (d->ht[0].table == NULL) {
        d->ht[0] = n;
        return DICT_OK;
    }

    /* Prepare a second hash table for incremental rehashing */
    d->ht[1] = n;
    d->rehashidx = 0;
    return DICT_OK;
}

创建新的哈希表并初始化。

如果字典的第一个哈希表 ht[0] 为空，那么将 ht[0] 指向新的哈希表， 反之将 ht[1] 指向新的哈希表，rehashidx 设置为 0 表示可以开始 rehash。

[junnplus]

删除

// 5.0.3/src/dict.c

/* Search and remove an element. This is an helper function for
 * dictDelete() and dictUnlink(), please check the top comment
 * of those functions. */
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);

    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 the element from the list */
                if (prevHe)
                    prevHe->next = he->next;
                else
                    d->ht[table].table[idx] = he->next;
                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; /* not found */
}

rehash 期间的删除操作也会进行一次槽位 rehash。 删除过程和查询过程类似，找到对应键值对，调整前后键值对的 next 指针然后释放内存。

当哈希表的键值对被删除变得稀疏时，Redis 会对哈希表进行缩容。

缩容

// 5.0.3/src/server.h
/* Hash table parameters */
#define HASHTABLE_MIN_FILL        10      /* Minimal hash table fill 10% */

// 5.0.3/src/server.c
int htNeedsResize(dict *dict) {
    long long size, used;

    size = dictSlots(dict);
    used = dictSize(dict);
    return (size > DICT_HT_INITIAL_SIZE &&
            (used*100/size < HASHTABLE_MIN_FILL));
}

缩容条件是哈希表中的键值对个数低于哈希表大小的 10% （哈希表的负载因子小于 0.1）。

[junnplus]

更新

// 5.0.3/src/dict.c

/* Add or Overwrite:
 * Add an element, discarding the old value if the key already exists.
 * Return 1 if the key was added from scratch, 0 if there was already an
 * element with such key and dictReplace() just performed a value update
 * operation. */
int dictReplace(dict *d, void *key, void *val)
{
    dictEntry *entry, *existing, auxentry;

    /* Try to add the element. If the key
     * does not exists dictAdd will succeed. */
    entry = dictAddRaw(d,key,&existing);
    if (entry) {
        dictSetVal(d, entry, val);
        return 1;
    }

    /* Set the new value and free the old one. Note that it is important
     * to do that in this order, as the value may just be exactly the same
     * as the previous one. In this context, think to reference counting,
     * you want to increment (set), and then decrement (free), and not the
     * reverse. */
    auxentry = *existing;
    dictSetVal(d, existing, val);
    dictFreeVal(d, &auxentry);
    return 0;
}

[junnplus]

渐进式 rehash

对大字典的 rehash 是比较耗时的，所以 Redis 中采用了渐进式的 rehash，将整个 rehash 过程所需的计算工作均摊到对字典的每个增删改查操作上。

在进行渐进式 rehash 的过程中，字典会同时使用 ht[0] 和 ht[1] 两个哈希表，所以在渐进式 rehash 进行期间，字典的删除、查找、更新等操作会在两个哈希表上进行。新添加到字典的键值对一律会被保存到 ht[1] 里面，而 ht[0] 则不再进行任何添加操作。

除了增删改查的操作外，Redis 还会定时对特殊的字典进行主动迁移，避免没有操作的情况下暂停 rehash。

// 5.0.3/src/server.c

/* This function handles 'background' operations we are required to do
 * incrementally in Redis databases, such as active key expiring, resizing,
 * rehashing. */
void databasesCron(void) {
    ...
        /* Rehash */
        if (server.activerehashing) {
            for (j = 0; j < dbs_per_call; j++) {
                int work_done = incrementallyRehash(rehash_db);
                if (work_done) {
                    /* If the function did some work, stop here, we'll do
                     * more at the next cron loop. */
                    break;
                } else {
                    /* If this db didn't need rehash, we'll try the next one. */
                    rehash_db++;
                    rehash_db %= server.dbnum;
                }
            }
        }
    }
}

/* Our hash table implementation performs rehashing incrementally while
 * we write/read from the hash table. Still if the server is idle, the hash
 * table will use two tables for a long time. So we try to use 1 millisecond
 * of CPU time at every call of this function to perform some rehahsing.
 *
 * The function returns 1 if some rehashing was performed, otherwise 0
 * is returned. */
int incrementallyRehash(int dbid) {
    /* Keys dictionary */
    if (dictIsRehashing(server.db[dbid].dict)) {
        dictRehashMilliseconds(server.db[dbid].dict,1);
        return 1; /* already used our millisecond for this loop... */
    }
    /* Expires */
    if (dictIsRehashing(server.db[dbid].expires)) {
        dictRehashMilliseconds(server.db[dbid].expires,1);
        return 1; /* already used our millisecond for this loop... */
    }
    return 0;
}

定时函数会遍历每个数据库，对数据库的 dict 和 expires 两个字典进行 1 秒的 rehash。

long long timeInMilliseconds(void) {
    struct timeval tv;

    gettimeofday(&tv,NULL);
    return (((long long)tv.tv_sec)*1000)+(tv.tv_usec/1000);
}

/* Rehash for an amount of time between ms milliseconds and ms+1 milliseconds */
int dictRehashMilliseconds(dict *d, int ms) {
    long long start = timeInMilliseconds();
    int rehashes = 0;

    while(dictRehash(d,100)) {
        rehashes += 100;
        if (timeInMilliseconds()-start > ms) break;
    }
    return rehashes;
}

[kzinglzy]

💯

[wenbochang888]

提出一个问题。redis在查找key值的时候，逻辑如下：

h = dictHashKey(d, key);
    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;
        }
        if (!dictIsRehashing(d)) return NULL;
    }

这很明显，redis扫了两张table表。因为他并不确定key值在table0，还是table1.

那他为什么不根据rehashidx来判断rehash进行到了哪一步呢？

这样的话，他只用扫一张表，效率会大大的提高。（for里面是两重循环，效率很低）

[kzinglzy]

@wenbochang888 不是很明显的自查了一张表吗... if (!dictIsRehashing(d)) return NULL; 这里如果没在rehashing 直接就return 了

[wenbochang888]

@kzinglzy 这是没有rehash的情况。 假设在rehash了，他必须扫两张表。才能找到key。 如果第一张表的idx链表很长，最后没有找到。效率就会十分的低。

rehashidx表示rehash到了哪个位置，为什么不拿idx和rehashidx比较。判断此时key在哪个table中呢？

[wenbochang888]

redis 的pull request https://github.com/antirez/redis/pull/5692

[kzinglzy]

he = d->ht[table].table[idx] 这一步是否有值, 就相当于你说的比较idx 和 rehashidx了

如果是null, 那就直接查ht[1]了 如果不是 null, 那这的确是有可能查两张表

这两者其实是等价的(当然, 如果直接判断idx 和 rehashidx, 会少2步判断(while(he) + dictIsRehashing...不过..这个影响可以忽略了...)

[kzinglzy]

idx > rehashidx => he = d->ht[table].table[idx] != null idx <= rehashidx => he = d->ht[table].table[idx] == null @wenbochang888

[wenbochang888]

@kzinglzy 突然明白，应该是这样的。 如果 he = d->ht[table].table[idx]不为null。 很明显此时key值要么在h0中，要么不在redis。 因为此时这个桶的key值还没有rehash。

只是因为while循环没有返回，会再去查找h1，但此时 he = d->ht[table].table[idx]一定为null。也就不会走while，效率基本不会有损失。

明白了，感谢大佬

[junnplus]

@wenbochang888 其实重点是渐进式rehash的过程，每次保证rehash一个slot

[shunminli]

crontab 线程处理 rehash 会不会导致线程安全的问题？比如正在查询的用户请求跟 crontab 的 rehash 过程冲突了

[junnplus]

crontab 线程处理 rehash

没明白这个的意思？

[shunminli]

crontab 线程处理 rehash

没明白这个的意思？

我看了源码大概明白了，就是 serverCon 处理的时候也是主线程处理的，没有多线程的问题

[shunminli]

incrementallyRehash 这个其实只处理了普通的 key-value 和 ttl，没有处理用户创建的 hash