Understanding Redis Rehash Mechanism and Implementation

Redis is a high‑performance in‑memory database that stores key‑value pairs using a dictionary implemented as a hash table. When the number of entries grows, hash collisions increase, so Redis performs a rehash to keep lookup efficiency and memory usage optimal.

The dictionary contains two hash tables: the active one (ht[0]) and a secondary table (ht[1]) used as a temporary target during rehashing. When the load factor reaches certain thresholds, Redis allocates ht[1] with an appropriate size (a power‑of‑two greater than the required capacity) and begins migrating entries.

Rehash conditions

When no BGSAVE or BGREWRITEAOF is running and load_factor ≥ 1, Redis expands the hash table.

When a BGSAVE or BGREWRITEAOF is running and load_factor ≥ 5, Redis also expands the hash table.

If load_factor < 0.1, Redis shrinks the hash table.

Rehash process

Allocate space for the secondary hash table (ht[1]) based on the number of used nodes.

Initialize a rehash index (rehashidx) to 0; -1 indicates no rehash in progress.

During normal operations (add, delete, lookup, update), Redis moves a small batch of entries from ht[0] at rehashidx to ht[1] and increments rehashidx.

The serverCron function also performs incremental rehash work (e.g., 100 elements per millisecond) until all entries are migrated, after which rehashidx is set to -1.

Example steps:

Rehash starts and ht[1] is initialized.

Key k2 is rehashed.

Rehash completes and ht[0] is cleared.

The incremental rehash avoids a large, blocking operation, but during rehash a lookup may need to check both ht[0] and ht[1], potentially doubling the access cost for keys that have already moved.

Conclusion

This progressive rehash strategy reduces the computational and memory overhead of a full rehash, while ensuring Redis maintains high performance even as the dataset scales.