Hash slots distribution in Redis - Time & Space Complexity

Time Complexity: Hash slots distribution

O(n)

Understanding Time Complexity

When using Redis clusters, data is split into parts called hash slots. Understanding how time grows when distributing keys into these slots helps us see how fast Redis can find or store data.

We want to know how the work changes as we add more keys to the cluster.

Scenario Under Consideration

Analyze the time complexity of the following Redis commands for distributing keys into hash slots.

# Calculate hash slot for each key
for key in KEYS {
  slot = CRC16(key) % 16384
  assign key to slot
}
    

This code calculates which of the 16384 hash slots each key belongs to using a hash function, then assigns the key to that slot.

Identify Repeating Operations

Look for repeated steps in the process.

• Primary operation: Calculating the hash slot for each key using CRC16 and modulo.
• How many times: Once for every key in the input list.

How Execution Grows With Input

As you add more keys, the number of hash calculations grows directly with the number of keys.

Input Size (n)	Approx. Operations
10	10 hash calculations
100	100 hash calculations
1000	1000 hash calculations

Pattern observation: The work grows evenly as you add more keys; doubling keys doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to assign keys to hash slots grows in direct proportion to the number of keys.

Common Mistake

[X] Wrong: "Calculating hash slots is constant time no matter how many keys there are."

[OK] Correct: Each key needs its own hash calculation, so more keys mean more work, not the same amount.

Interview Connect

Understanding how Redis distributes keys helps you explain how data is balanced and accessed quickly in real systems. This skill shows you can think about how systems handle growing data smoothly.

Self-Check

"What if we used a more complex hash function that takes longer to compute? How would the time complexity change?"

Practice

1. What is the total number of hash slots used by Redis Cluster to distribute data?

easy

A. 16384

B. 1024

C. 65536

D. 2048

Solution

1. Step 1: Recall Redis Cluster design

   Redis Cluster divides data into hash slots to distribute keys evenly.

2. Step 2: Identify the number of hash slots

   The standard number of hash slots in Redis Cluster is 16384.

3. Final Answer:

   16384 -> Option A

4. Quick Check:

   Redis Cluster uses 16384 hash slots [OK]

Hint: Remember Redis Cluster always uses 16384 slots [OK]

Common Mistakes:

• Confusing hash slots with number of keys
• Thinking slots are 1024 or 2048
• Assuming slots equal to max integer value

2. Which Redis command shows the current distribution of hash slots across cluster nodes?

easy

A. CLUSTER NODES

B. CLUSTER KEYS

C. CLUSTER SLOTS

D. CLUSTER INFO

Solution

1. Step 1: Understand Redis cluster commands

   Redis provides commands to inspect cluster state and slot distribution.

2. Step 2: Identify the command for slot distribution

   The CLUSTER SLOTS command returns how hash slots are assigned to nodes.

3. Final Answer:

   CLUSTER SLOTS -> Option C

4. Quick Check:

   CLUSTER SLOTS shows slot distribution [OK]

Hint: Use CLUSTER SLOTS to see slot assignments [OK]

Common Mistakes:

• Using CLUSTER NODES which shows node info but not slots
• Confusing CLUSTER INFO with slot details
• Assuming CLUSTER KEYS exists

3. Given a Redis Cluster with 3 nodes and the following slot ranges: Node1: 0-5460, Node2: 5461-10922, Node3: 10923-16383. Which node holds the key with hash slot 7000?

medium

A. None of the above

B. Node1

C. Node3

D. Node2

Solution

1. Step 1: Understand slot ranges per node

   Node1 covers slots 0 to 5460, Node2 covers 5461 to 10922, Node3 covers 10923 to 16383.

2. Step 2: Locate slot 7000

   Slot 7000 falls between 5461 and 10922, so it belongs to Node2.

3. Final Answer:

   Node2 -> Option D

4. Quick Check:

   7000 is in Node2's slot range [OK]

Hint: Check which node's slot range includes the slot number [OK]

Common Mistakes:

• Choosing Node1 because 7000 is less than 10922
• Choosing Node3 by mistake
• Not checking slot ranges carefully

4. You run CLUSTER SLOTS but get an error: "ERR This instance has cluster support disabled". What is the likely cause?

medium

A. The Redis instance is not running in cluster mode

B. The command syntax is incorrect

C. The cluster has no slots assigned yet

D. The Redis version is too new

Solution

1. Step 1: Analyze the error message

   The error says cluster support is disabled, meaning the instance is not a cluster node.

2. Step 2: Understand cluster mode requirement

   Only Redis instances running in cluster mode support CLUSTER SLOTS command.

3. Final Answer:

   The Redis instance is not running in cluster mode -> Option A

4. Quick Check:

   Cluster commands need cluster mode enabled [OK]

Hint: Check if Redis is started with cluster enabled [OK]

Common Mistakes:

• Assuming syntax error causes this
• Thinking slots are unassigned causes error
• Blaming Redis version without checking mode

5. In a Redis Cluster, if you want to evenly distribute 16384 hash slots across 4 nodes, which slot range should Node3 handle?

hard

A. 12288 to 16383

B. 8192 to 12287

C. 4096 to 8191

D. 0 to 4095

Solution

1. Step 1: Calculate slots per node

   16384 slots divided by 4 nodes = 4096 slots per node.

2. Step 2: Determine Node3's slot range

   Node1: 0-4095, Node2: 4096-8191, Node3: 8192-12287, Node4: 12288-16383.

3. Final Answer:

   8192 to 12287 -> Option B

4. Quick Check:

   Each node gets 4096 slots; Node3 starts at 8192 [OK]

Hint: Divide 16384 by nodes, assign consecutive ranges [OK]

Common Mistakes:

• Off-by-one errors in slot ranges
• Assigning wrong ranges to nodes
• Not dividing slots evenly