How Redis Implements Incremental Rehashing: A Deep Dive into Dictionary Internals

Introduction

Redis stores key‑value pairs in an in‑memory dictionary implemented as a hash table. As the number of entries grows, hash collisions increase; Redis uses chaining to resolve collisions and performs a rehash operation to resize the table and improve memory utilization.

Dictionary Structure

<code>// Hash table definition
typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

// Dictionary definition
typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2]; /* two hash tables */
    long rehashidx; /* -1 when not rehashing, otherwise current index */
    unsigned long iterators; /* number of active iterators */
} dict;
</code>

Rehash Conditions

The rehash is triggered based on the load factor (average elements per bucket):

When no BGSAVE or BGREWRITEAOF is running and load_factor >= 1 , the dictionary expands.

When a BGSAVE or BGREWRITEAOF is running and load_factor >= 5 , the dictionary expands.

When load_factor < 0.1 , the dictionary shrinks.

Rehash Process

Assume ht[0] is the active table and ht[1] is the temporary table used during rehash.

Allocate ht[1] with a size that is the smallest power‑of‑two greater than or equal to the required number of entries (twice the used count for expansion, equal to used count for shrinking).

Set rehashidx = 0 to start the incremental rehash; a value of -1 means no rehash is in progress.

During each normal dictionary operation (add, delete, lookup, update), Redis also moves all entries in the bucket at rehashidx from ht[0] to ht[1] , then increments rehashidx .

The server cron calls the rehash routine every millisecond, moving a limited number of entries (e.g., 100) to avoid long pauses.

When ht[0] becomes empty, Redis swaps ht[1] into ht[0] , frees the old table, resets rehashidx to -1 , and the rehash is complete.

Rehash Implementation (Code)

<code>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;
        /* Find next non‑empty bucket */
        while (d->ht[0].table[d->rehashidx] == NULL) {
            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++;
    }
    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;
    }
    return 1; /* Rehash not finished */
}
</code>

Example

The following images illustrate the three stages of an incremental rehash:

Conclusion

This incremental rehash strategy avoids the massive computation and memory overhead of a full‑stop rehash, but during rehashing a normal lookup may need to probe both ht[0] and ht[1] , potentially doubling the access cost for keys that have already moved.