Multi-key operations in cluster in Redis - Time & Space Complexity

Time Complexity: Multi-key operations in cluster

O(n)

Understanding Time Complexity

When using Redis clusters, some commands work on multiple keys at once. It's important to understand how the time to run these commands changes as you add more keys.

We want to see how the cost grows when handling many keys in a cluster.

Scenario Under Consideration

Analyze the time complexity of the following Redis cluster multi-key command.

# Example: MGET command in Redis cluster
MGET key1 key2 key3 ... keyN

# Each key may be on a different node in the cluster
# Redis sends requests to nodes holding the keys
# Then collects and returns all values
    

This command fetches values for multiple keys, possibly contacting different nodes in the cluster.

Identify Repeating Operations

Look for repeated actions in the command.

• Primary operation: Sending a request for each key to its node and waiting for the response.
• How many times: Once per key, so N times for N keys.

How Execution Grows With Input

As you add more keys, the number of requests and responses grows roughly with the number of keys.

Input Size (n)	Approx. Operations
10	About 10 requests to nodes
100	About 100 requests to nodes
1000	About 1000 requests to nodes

Pattern observation: The work grows directly with the number of keys requested.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the multi-key command grows linearly with the number of keys involved.

Common Mistake

[X] Wrong: "Multi-key commands in a cluster run as fast as single-key commands regardless of how many keys are involved."

[OK] Correct: Each key may be on a different node, so Redis must send separate requests and wait for all responses, making the total time grow with the number of keys.

Interview Connect

Understanding how multi-key commands behave in a cluster shows you can think about distributed systems and how work spreads across nodes. This skill helps you design efficient data access patterns.

Self-Check

"What if all keys in the multi-key command were stored on the same cluster node? How would the time complexity change?"

Practice

1. In a Redis cluster, why must keys be in the same hash slot for multi-key operations?

easy

A. Because Redis cluster does not support multi-key commands at all

B. Because keys in different slots cause syntax errors

C. Because keys in different slots are automatically merged

D. Because Redis cluster routes commands to a single node per hash slot

Solution

1. Step 1: Understand Redis cluster hash slots

   Redis cluster divides keys into 16384 hash slots, each handled by one node.

2. Step 2: Multi-key commands require single node routing

   Multi-key commands must operate on keys in the same slot to be routed to one node.

3. Final Answer:

   Because Redis cluster routes commands to a single node per hash slot -> Option D

4. Quick Check:

   Same hash slot = single node routing [OK]

Hint: Keys must share hash slot for multi-key commands [OK]

Common Mistakes:

• Thinking keys in different slots can be used together
• Assuming multi-key commands work cluster-wide automatically
• Confusing syntax errors with routing errors

2. Which of the following is the correct syntax to ensure two keys are in the same hash slot using key tags?

easy

A. SET user:1:name 'Alice'
SET user:1:age 30

B. SET {user:1}:name 'Alice'
SET {user:1}:age 30

C. SET {user1}:1:name 'Alice'
SET {user}:1:age 30

D. SET {user:1:name} 'Alice'
SET {user:1:age} 30

Solution

1. Step 1: Identify key tag usage

   Key tags are enclosed in curly braces {} and define the hash slot.

2. Step 2: Check which keys share the same tag

   Keys with the same substring inside {} share the same slot, e.g., {user:1}.

3. Final Answer:

   SET {user:1}:name 'Alice' and SET {user:1}:age 30 -> Option B

4. Quick Check:

   Same key tag inside {} means same slot [OK]

Hint: Use identical curly braces content for same slot keys [OK]

Common Mistakes:

• Placing braces incorrectly around parts of the key
• Using different tags for keys meant to be grouped
• Omitting braces and expecting same slot

3. Given these Redis commands in a cluster:

SET {order}:1001:status 'pending'
SET {order}:1001:amount 250
MGET {order}:1001:status {order}:1001:amount

What will be the output of the MGET command?

medium

A. ["pending", "250"]

B. ["pending", null]

C. [null, "250"]

D. Error: CROSSSLOT Keys in request don't hash to the same slot

Solution

1. Step 1: Check keys and their hash slots

   Both keys have the same tag {order}, so they share the same slot.

2. Step 2: Verify keys exist and MGET output

   Both keys were set, so MGET returns their values in order: 'pending' and '250'.

3. Final Answer:

   ["pending", "250"] -> Option A

4. Quick Check:

   Same slot keys return values correctly [OK]

Hint: MGET works if keys share same hash slot [OK]

Common Mistakes:

• Expecting CROSSSLOT error despite same key tags
• Confusing string and integer values
• Assuming null for existing keys

4. You run this Redis cluster command:

MGET user:1:name user:2:name

But get an error: CROSSSLOT Keys in request don't hash to the same slot. What is the best fix?

medium

A. Use key tags to put both keys in the same hash slot, e.g., {user}:1:name and {user}:2:name

B. Run the command on each key separately

C. Rename keys to have the same prefix without braces

D. Disable cluster mode to allow multi-key commands

Solution

1. Step 1: Understand CROSSSLOT error cause

   Keys user:1:name and user:2:name hash to different slots, causing the error.

2. Step 2: Use key tags to group keys

   Adding the same tag in braces, e.g., {user}, forces keys into the same slot.

3. Final Answer:

   Use key tags to put both keys in the same hash slot, e.g., {user}:1:name and {user}:2:name -> Option A

4. Quick Check:

   Key tags fix CROSSSLOT errors [OK]

Hint: Add identical key tags in braces to fix CROSSSLOT [OK]

Common Mistakes:

• Ignoring the error and retrying same command
• Assuming prefix alone groups keys
• Trying to disable cluster mode without reason

5. You want to atomically increment two counters in a Redis cluster using a multi-key command. The counters are counter:{2024}:a and counter:{2024}:b. Which approach correctly increments both counters in one command without errors?

hard

A. Use INCR counter:2024:a and INCR counter:2024:b separately

B. Use INCR counter:{2024}:a counter:{2024}:b in one command

C. Use MULTI with two INCR commands on the keys, then EXEC

D. Use INCR counter:{2024}:a and INCR counter:{2025}:b in a pipeline

Solution

1. Step 1: Confirm keys share the same hash slot

   Both keys have the same tag {2024}, so they are in the same slot.

2. Step 2: Use MULTI/EXEC for atomic multi-key operations

   Redis supports atomic transactions with MULTI/EXEC on keys in the same slot.

3. Final Answer:

   Use MULTI with two INCR commands on the keys, then EXEC -> Option C

4. Quick Check:

   Atomic multi-key needs MULTI/EXEC and same slot keys [OK]

Hint: Use MULTI/EXEC with same-slot keys for atomic multi-key ops [OK]

Common Mistakes:

• Trying to INCR multiple keys in one command
• Using keys without same hash tag
• Assuming pipeline is atomic