Time Complexity: Cluster creation
O(n)
0
0
Cluster creation in Redis - Time & Space Complexity
Understanding Time Complexity
When creating a Redis cluster, it's important to understand how the time needed grows as the cluster size increases.
We want to know how the work changes when we add more nodes or slots to the cluster.
Scenario Under Consideration
Analyze the time complexity of the following Redis cluster creation commands.
CLUSTER MEET 192.168.1.2 7001
CLUSTER MEET 192.168.1.3 7002
CLUSTER ADDSLOTS 0-5460
CLUSTER ADDSLOTS 5461-10922
CLUSTER ADDSLOTS 10923-16383
This code connects nodes and assigns hash slots to each node to form a cluster.
Identify Repeating Operations
Look for repeated actions that take time.
- Primary operation: Assigning hash slots to nodes using CLUSTER ADDSLOTS.
- How many times: Each slot (up to 16384) is assigned once, so the operation repeats for each slot.
How Execution Grows With Input
As the number of slots or nodes grows, the time to assign slots grows roughly in direct proportion.
| Input Size (slots) | Approx. Operations |
|---|---|
| 10 | 10 slot assignments |
| 100 | 100 slot assignments |
| 1000 | 1000 slot assignments |
Pattern observation: Doubling the number of slots roughly doubles the work needed to assign them.
Final Time Complexity
Time Complexity: O(n)
This means the time to create the cluster grows linearly with the number of slots assigned.
Common Mistake
[X] Wrong: "Adding more nodes will not affect the time because slots are assigned independently."
[OK] Correct: Even though slots are assigned per node, the total number of slots remains fixed, so the total work depends on all slots assigned across nodes.
Interview Connect
Understanding how cluster creation scales helps you design systems that grow smoothly and avoid surprises when adding more nodes.
Self-Check
"What if we changed the number of hash slots from 16384 to a smaller number? How would the time complexity change?"