其他数据库 2023-06-17

探索Redis中扩展哈希分配的秘密（redis查看哈希分配）

Redis是一个高性能的键值存储系统，其内部的数据结构非常多样化。其中，哈希表是Redis中最常用的数据结构之一，主要用于存储和操作键值对。

然而，在某些场景下，单个哈希表可能不能满足我们的需求。例如，在需要存储大量键值对时，单个哈希表可能会变得非常庞大，导致性能下降。这时，我们需要一种更高效的哈希表扩展方式，这就是Redis中的扩展哈希分配。

扩展哈希分配的思想很简单：在单个哈希表容量达到一定阈值后，自动创建一个新的哈希表，并将新的键值对存储在新的哈希表中。这个过程可以无限重复，从而实现对键值对的高效扩展，同时保证常数时间内的访问性能。

实现扩展哈希分配的核心代码非常简单。在Redis源码中，可以找到以下关键函数：

static dictEntry *dictAddRaw(dict *d, void *key)
{
    // TODO: add hash table expansion logic here
}

static int dictExpandIfNeeded(dict *d)
{
    // TODO: add hash table expansion logic here
}

可以看到，这两个函数被定义为`TODO`，说明它们的具体实现被遗留给了后面的开发者。

下面，我们针对这两个函数分别进行探索。

### dictAddRaw函数探索

dictAddRaw函数负责将新的键值对插入到哈希表中。在这个函数中，我们需要保证插入操作的原子性，即锁定哈希表的同时进行插入操作。

static dictEntry *dictAddRaw(dict *d, void *key)
{
    // lock the hash table
    dictEntry *entry = dictFind(d, key);
    if (entry != NULL) {
        // the key already exists in the hash table
        return entry;
    }

    // TODO: add hash table expansion logic here

    // allocate memory for the new entry
    entry = zmalloc(sizeof(dictEntry));
    // initialize the new entry
    entry->key = key;
    entry->next = NULL;

    // insert the new entry into the hash table
    int index = dictHashKey(d, key) & (d->size - 1);
    entry->next = d->table[index];
    d->table[index] = entry;
    // increment the count of the hash table
    d->count++;
    // unlock the hash table
    return entry;
}

其中，我们可以看到`TODO`中的代码并不复杂，主要包括以下几个步骤：

1. 判断当前哈希表的负载因子是否达到临界值；

2. 如果达到临界值，则调用`dictExpandTableIfNeeded`函数进行哈希表的扩展。

### dictExpandIfNeeded函数探索

dictExpandIfNeeded函数负责对哈希表进行扩展。在这个函数中，我们需要分配新的哈希表，并将已有的键值对重新进行哈希，并分别存储在新的哈希表汇总。

static void dictExpandIfNeeded(dict *d)
{
    if (d->size == 0) {
        // initialize the hash table
        dictExpandTable(d, DICT_INIT_SIZE);
        return;
    }
    if (d->count / d->size > DICT_LOAD_FACTOR) {
        // allocate memory for the new hash table
        dict *newD = zcalloc(sizeof(dict));
        dictExpandTable(newD, d->size * 2);
        // rehash the original entries
        for (int i = 0; i size; i++) {
            dictEntry *entry = d->table[i];
            while (entry != NULL) {
                dictEntry *next = entry->next;
                int index = dictHashKey(newD, entry->key) & (newD->size - 1);
                entry->next = newD->table[index];
                newD->table[index] = entry;
                entry = next;
            }
        }

        // free the old hash table
        zfree(d->table);
        // update the hash table
        *d = *newD;
        zfree(newD);
    }
}