The Challenge of Dynamic Memory in Redis
Redis relies on a hash table-based dictionary structure to provide O(1) complexity for key lookups. As the number of keys grows, a standard hash table eventually faces collisions, degrading performance. While traditional implementations resolve this by allocating a larger table and moving all items at once, such a strategy would be fatal to Redis's single-threaded event loop, introducing massive latency spikes. To solve this, Redis employs a technique known as incremental rehashing.
The Dual-Table Architecture
At the core of the dictionary implementation are two distinct hash tables: ht[0] and ht[1]. Under normal operation, ht[0] holds all the data, while ht[1] remains empty and unallocated. When the load factor—the ratio of keys to slots—exceeds a specific threshold, Redis triggers a resizing process.
Allocation: Redis allocates ht[1], typically twice the size of ht[0].
Rehashing State: An internal rehash index is initialized to 0, signaling the start of the migration process.
Incremental Migration: During every subsequent read or write operation, Redis performs a small, fixed amount of rehashing work, moving a limited number of buckets from ht[0] to ht[1].
Handling Concurrent Operations
During the migration, the database exists in a split-state. When a request hits the system, Redis first searches ht[0]. If the key is not found, it checks ht[1]. Write operations, however, are exclusively performed on the new table, ht[1], to ensure consistency and prevent data from being re-migrated back to the old structure. This incremental approach ensures that no single command blocks the event loop for more than a few microseconds, effectively amortizing the cost of the resize over thousands of operations.
Trade-offs and Operational Reality
The primary trade-off for incremental rehashing is increased memory pressure. Because both tables must exist simultaneously for the duration of the migration, peak memory usage can spike. For environments with tight memory constraints, this behavior requires careful capacity planning. Additionally, while the incremental approach protects latency, extremely large datasets can result in longer migration windows where the system maintains two active tables, slightly increasing the overhead for every lookup until the process completes.
Understanding this mechanism is essential for engineers debugging latency during bulk key operations. By keeping the migration logic granular, Redis maintains its performance guarantees even when the underlying data structures undergo significant evolution.