Resharding hash slots in Redis - Time & Space Complexity

Time Complexity: Resharding hash slots

O(n)

Understanding Time Complexity

When Redis redistributes hash slots between nodes, it moves keys from one place to another.

We want to know how the time to reshard grows as the number of keys changes.

Scenario Under Consideration

Analyze the time complexity of the following redis commands used in resharding.

# Move keys from source node to target node
for each slot in slots_to_move:
  keys = redis-cli --cluster getkeysinslot slot count
  for each key in keys:
    redis-cli --cluster MIGRATE target_host target_port key 0 5000

This code moves all keys in certain hash slots from one node to another.

Identify Repeating Operations

Look for loops or repeated actions.

• Primary operation: Moving each key in the slots one by one.
• How many times: Once for every key in the slots being moved.

How Execution Grows With Input

As the number of keys to move grows, the time to move them grows too.

Input Size (n keys)	Approx. Operations
10	About 10 moves
100	About 100 moves
1000	About 1000 moves

Pattern observation: The time grows roughly in direct proportion to the number of keys moved.

Final Time Complexity

Time Complexity: O(n)

This means the time to reshard grows linearly with the number of keys moved.

Common Mistake

[X] Wrong: "Resharding time depends only on the number of slots, not keys."

[OK] Correct: Each slot can have many keys, so moving slots means moving all their keys, which takes time proportional to key count.

Interview Connect

Understanding how redis resharding scales helps you explain system behavior and design better data distribution strategies.

Self-Check

"What if we batch move keys instead of one by one? How would the time complexity change?"