Internal Mechanics of Redis SCAN and Analysis of Rehashing Scenarios

Redis's SCAN command is an alternative that iterates over keys without blocking the server, unlike the KEYS command. This article goes beyond the usage of SCAN to analyze the internal principles that ensure no data loss even during Rehashing, through source code examination.

Basic Structure of SCAN and Cursor

SCAN, SSCAN, ZSCAN, and HSCAN are processed via the common function scanGenericCommand. They follow a full iteration pattern, starting with a Cursor value of 0 and repeating until the returned Cursor becomes 0. The Cursor does not simply denote the next index; in the actual implementation, it uses a reverse-bit increment method. This is to align both the start and end of the iteration to 0, thereby clarifying the termination condition.

Dual Table Traversal During Rehashing

When a hash table exceeds a certain ratio, Redis doubles its size and initiates Rehashing. Instead of moving all data at once, it performs incremental Rehashing using rehashidx to move only one Bucket per step. During this process, ht[0] (the old table) and ht[1] (the new table) coexist.

SCAN considers both tables during Rehashing. It first traverses the Buckets in the smaller table (ht[0]), then additionally searches the Buckets in the larger table (ht[1]) corresponding to that index. This ensures that both data not yet moved and data already moved are included in the return, providing consistent results even during Rehashing.

Limitations and Caveats of SCAN

While SCAN mitigates the drawbacks of KEYS, it has the following constraints:

• No Guarantee of Exact Count: The COUNT option is merely a hint and does not return exactly that number of items.
• Possibility of Duplicates and Omissions: During Rehashing or table expansion, data at positions the Cursor has already passed may not be returned, or specific items may be returned as duplicates.
• Data Structure Dependency: If a Set or Hash is encoded as a ziplist, SCAN internally fetches all data at once, which can cause performance degradation similar to KEYS.