How Redis's Keyspace Dict Rehashes, One Bucket at a Time

The idea: a hash table that resizes a little at a time

Every key of a Redis database lives in one hash table, the keyspace dict (dict.c). When it fills up it must grow, and copying millions of keys at once would stop the single command thread for a long time. So Redis keeps two tables during a resize, ht[0] (old) and ht[1] (new), and moves the keys over one bucket at a time: a little with every command, and a little more in the background timer. This is incremental rehashing.

The page has one dict with up to 32 keys, k1 … k32. The hashes come from a fixed table (the low 8 bits of what would be a 64-bit SipHash), so every run is the same. Pick a key and a command and press Run, or run a demo. The table sizes and the 1 ms of background rehashing are scaled down: a real keyspace has millions of buckets.

Buckets, chains and hash & sizemask

A table is an array of buckets. Its size is always a power of 2 (4, 8, 16, …), so the bucket of a key is just the low bits of its hash: index = hash & sizemask, where sizemask = size − 1. Keys that land in the same bucket form a linked list of dictEntry structs (chaining); a new entry goes at the head of the list. The command band at the top of the canvas shows the hash in binary and the & for each table.

Doubling the size adds one bit to the mask. So a key in bucket i of the old table goes to bucket i or i + size of the new one: bucket 1 of 4 splits into buckets 1 and 5 of 8.

When the table grows

Before adding a key, _dictExpandIfNeeded checks the load factor used / size. When it reaches 1 (used ≥ size), the dict allocates ht[1] with the next power of 2 ≥ used + 1, normally twice the size, and sets rehashidx = 0. Nothing is copied yet; the new key goes straight into ht[1]. (Demo 1: inserts until growth starts: the fifth key in 4 buckets starts a rehash to 8.)

Incremental rehashing

The field rehashidx is the next bucket of ht[0] to move. Moving a bucket means taking each entry off its chain, computing its bucket with the new mask, and linking it at the head of that chain in ht[1]. When ht[0] is empty, it is freed, ht[1] becomes ht[0], and rehashidx goes back to −1.

Who moves buckets	How much
Every dict call (add, find, delete), via _dictRehashStep	1 bucket; it may skip up to 10 empty buckets first, then stops for this call
serverCron → databasesCron, if activerehashing yes (default)	1 ms of work, in rounds of 100 buckets

So a busy server finishes a rehash through its commands, and an idle one through the timer. No command ever pays for more than a bucket. (Demo 2: rehash step by step: GET k1 moves bucket 0, SET k6 moves bucket 1, GET k2 skips empty bucket 2 and moves bucket 3, which ends the rehash.) The page counts one step per command; a real SET of a new key calls the dict twice (look up, then add), so it may move two buckets.

Reads and writes during a rehash

While rehashing, a key can be in either table: in ht[0] if its bucket has not been moved yet, in ht[1] if it has, or if it was added after the rehash started. So dictFind looks in ht[0], then in ht[1]; a missing key costs two bucket walks. Inserts go to ht[1] only: ht[0] never gets new work, so the rehash always ends. (Demo 3: a GET during a rehash finds k4 in ht[1], k2 in ht[0], and looks in both for the missing k9.)

BGSAVE, copy-on-write and the ratio 5

BGSAVE and AOF rewrites fork a child process that shares the parent's memory pages copy-on-write. Moving entries around writes to many pages, and each written page gets copied. So while a child exists, updateDictResizePolicy sets dict_can_resize = AVOID:

• the dict grows only when used / size > 5 (dict_force_resize_ratio), so the chains get long first;
• a rehash that has started only continues when the two sizes differ by at least 5×;
• databasesCron does no resizing or active rehashing at all.

(Demo 4: BGSAVE delays growth (ratio 5): 24 keys pile up in 4 buckets, six per chain. The 25th key makes the ratio 6 > 5 and forces a jump straight to 32 buckets, the next power of 2 ≥ 25. Once the child exits, serverCron finishes the work.)

Shrinking below 10 %

Deleting keys never shrinks the table by itself. serverCron checks each dict (htNeedsResize): if it has more than 4 buckets and used × 100 / size < 10 (HASHTABLE_MIN_FILL), dictResize starts a rehash into the next power of 2 ≥ used (at least 4). The same incremental machinery then moves the keys into the smaller table. (Demo 5: deletes, then a shrink: 5 keys in 16 buckets is 31 %, nothing happens; 1 key is 6 %, and the table shrinks to 4.)

SCAN and the reverse-binary cursor

SCAN walks the dict a few buckets per call and hands the client a cursor to continue from. The table may grow or shrink between calls, so the cursor cannot simply count 0, 1, 2, 3. Instead, it counts with its bits reversed: 0, 2, 1, 3 for 4 buckets (binary 00, 10, 01, 11: add 1 at the left). Because doubling the table only adds a high bit, the buckets already visited in the small table are exactly the ones whose children in the big table come first in the big order. So a cursor from the old table is still valid in the new one.

During a rehash, dictScan visits the cursor's bucket in the smaller table and then every bucket of the bigger table that it expands into. The guarantee: every key that is in the dict for the whole scan is returned at least once. Keys added or deleted during the scan may or may not appear, and after a shrink a key can come back twice. (Demo 6: SCAN across a resize: the cursor goes 0 → 2 → 1 → 3 → 0 while the table grows from 4 to 8 buckets, and all 5 keys come back once.)

See also how Redis serves many connections with one thread (why a long rehash would block everyone), Redis Cluster, and the other Redis internals pages: sorted sets, expiry and eviction, RDB and AOF persistence, replication, compact encodings, streams and transactions. For fork and copy-on-write see copy-on-write after fork; for other hash tables see open hashing, Java's HashMap (which resizes all at once) and ConcurrentHashMap (which also spreads a resize over many threads).

What the page leaves out

The other dicts of a database (expires, and in Redis 7.4+ one dict per cluster slot), the dict type callbacks and real SipHash values; values (an entry here is just a key); the second rehash step a SET of a new key makes, and the steps taken by expires lookups; safe iterators and pauserehash, which stop rehash steps while an iterator is open; the exact 100-bucket rounds and the 1 ms clock of active rehashing; AOF rewrite and replication forks (they behave like BGSAVE); Redis 7.4's change of the forced ratio to 4 and its separate shrink ratio; and Redis 8's new hashtable.c for the keyspace, which uses open addressing in cache-line buckets instead of chains.

References

Redis source: dict.c (dictRehash, _dictExpandIfNeeded, dictScan)

Redis source: server.c (databasesCron, htNeedsResize, updateDictResizePolicy)

Redis documentation: SCAN and its guarantees

Redis documentation: redis.conf (activerehashing)