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?"

Practice

1. What is the main purpose of resharding hash slots in a Redis cluster?

easy

A. To balance data evenly across cluster nodes

B. To delete unused keys from the database

C. To backup data to an external storage

D. To increase the size of each hash slot

Solution

1. Step 1: Understand hash slots in Redis cluster

   Redis cluster divides data into 16384 hash slots distributed among nodes.

2. Step 2: Purpose of resharding

   Resharding moves hash slots to balance load and storage evenly across nodes.

3. Final Answer:

   To balance data evenly across cluster nodes -> Option A

4. Quick Check:

   Resharding = balance data [OK]

Hint: Resharding means redistributing data evenly [OK]

Common Mistakes:

• Thinking resharding deletes keys
• Confusing resharding with backup
• Assuming hash slot size changes

2. Which Redis command is used to mark a hash slot as migrating during resharding?

easy

A. CLUSTER ADDSLOTS <slot>

B. CLUSTER SETSLOT <slot> MIGRATING <node_id>

C. CLUSTER DELSLOTS <slot>

D. CLUSTER INFO

Solution

1. Step 1: Identify commands related to slot state changes

   CLUSTER SETSLOT command changes slot ownership or state.

2. Step 2: Marking migrating slot

   Using MIGRATING flag with CLUSTER SETSLOT marks slot as migrating from a node.

3. Final Answer:

   CLUSTER SETSLOT <slot> MIGRATING <node_id> -> Option B

4. Quick Check:

   MIGRATING slot = CLUSTER SETSLOT MIGRATING [OK]

Hint: Use CLUSTER SETSLOT with MIGRATING to mark slot move [OK]

Common Mistakes:

• Using ADDSLOTS or DELSLOTS instead of SETSLOT
• Confusing INFO command with slot state change
• Omitting node_id in command

3. Given the following commands during resharding, what is the correct order to migrate a hash slot 5000 from node A to node B?

1. CLUSTER SETSLOT 5000 MIGRATING nodeB_id
2. MIGRATE nodeB_ip 6379 "" 0 5000
3. CLUSTER SETSLOT 5000 IMPORTING nodeA_id
4. CLUSTER SETSLOT 5000 NODE nodeB_id

medium

A. 1, 2, 3, 4

B. 3, 1, 2, 4

C. 2, 1, 3, 4

D. 1, 3, 2, 4

Solution

1. Step 1: Mark slot as migrating on source node

   Use CLUSTER SETSLOT 5000 MIGRATING nodeB_id to mark slot migrating from node A.

2. Step 2: Mark slot as importing on destination node

   Use CLUSTER SETSLOT 5000 IMPORTING nodeA_id on node B to accept keys.

3. Step 3: Migrate keys with MIGRATE command

   Use MIGRATE to move keys of slot 5000 from node A to node B.

4. Step 4: Assign slot ownership to destination node

   Use CLUSTER SETSLOT 5000 NODE nodeB_id to finalize ownership.

5. Final Answer:

   1, 3, 2, 4 -> Option D

6. Quick Check:

   Mark migrating -> mark importing -> migrate keys -> assign slot [OK]

Hint: MIGRATING then IMPORTING before MIGRATE command [OK]

Common Mistakes:

• Migrating keys before marking IMPORTING
• Assigning slot ownership before migration
• Skipping IMPORTING step

4. You run the following commands to reshard slot 7000 but keys are not migrating correctly:

CLUSTER SETSLOT 7000 MIGRATING nodeB_id
MIGRATE nodeB_ip 6379 "" 0 7000
CLUSTER SETSLOT 7000 NODE nodeB_id

What is missing to fix the migration?

medium

A. Mark slot as IMPORTING on node B before MIGRATE

B. Run CLUSTER DELSLOTS 7000 on node A first

C. Use CLUSTER ADDSLOTS 7000 on node B after migration

D. Restart both nodes before migration

Solution

1. Step 1: Identify missing IMPORTING state

   Destination node must mark slot as IMPORTING before receiving keys.

2. Step 2: Add missing command

   Use CLUSTER SETSLOT 7000 IMPORTING nodeA_id on node B before MIGRATE.

3. Final Answer:

   Mark slot as IMPORTING on node B before MIGRATE -> Option A

4. Quick Check:

   IMPORTING state needed on destination [OK]

Hint: Always mark IMPORTING on target node before MIGRATE [OK]

Common Mistakes:

• Skipping IMPORTING step
• Deleting slots prematurely
• Restarting nodes unnecessarily

5. During a large-scale resharding, you want to move multiple hash slots from node A to node B without downtime. Which sequence of actions ensures data consistency and minimal disruption?

hard

A. Assign slots to node B first, then migrate keys, finally mark MIGRATING on node A

B. Migrate keys first, then mark slots IMPORTING on node B, finally mark MIGRATING on node A

C. Mark slots MIGRATING on node A, mark IMPORTING on node B, migrate keys, then assign slots to node B

D. Delete slots on node A, migrate keys, then assign slots to node B

Solution

1. Step 1: Mark slots as MIGRATING on source node

   This prevents writes to those slots on node A during migration.

2. Step 2: Mark slots as IMPORTING on destination node

   Allows node B to accept keys for those slots.

3. Step 3: Migrate keys using MIGRATE command

   Safely transfer keys from node A to node B.

4. Step 4: Assign slots ownership to node B

   Finalizes the slot ownership after migration completes.

5. Final Answer:

   Mark slots MIGRATING on node A, mark IMPORTING on node B, migrate keys, then assign slots to node B -> Option C

6. Quick Check:

   MIGRATING -> IMPORTING -> MIGRATE -> ASSIGN [OK]

Hint: Follow MIGRATING, IMPORTING, MIGRATE, then assign slots [OK]

Common Mistakes:

• Assigning slots before migration
• Migrating keys without marking IMPORTING
• Deleting slots before migration