Time Complexity: Automatic failover
O(n)
0
0
Automatic failover in Redis - Time & Space Complexity
Understanding Time Complexity
When Redis automatically switches to a backup server after a failure, it needs to check the status of servers and decide quickly.
We want to understand how the time it takes to do this changes as the number of servers grows.
Scenario Under Consideration
Analyze the time complexity of the following Redis Sentinel automatic failover process.
SENTINEL masters
SENTINEL slaves <master-name>
SENTINEL is-master-down-by-addr <ip> <port> <current-epoch>
SENTINEL failover <master-name>
This sequence checks master and slave servers, detects if the master is down, and triggers failover to a slave.
Identify Repeating Operations
In this process, the main repeating operations are:
- Primary operation: Checking the status of each slave server for the master.
- How many times: Once for each slave connected to the master.
How Execution Grows With Input
As the number of slaves increases, the time to check their status grows roughly in a straight line.
| Input Size (number of slaves) | Approx. Operations |
|---|---|
| 10 | 10 status checks |
| 100 | 100 status checks |
| 1000 | 1000 status checks |
Pattern observation: The work grows directly with the number of slaves to check.
Final Time Complexity
Time Complexity: O(n)
This means the time to complete failover checks grows in a straight line as the number of slave servers increases.
Common Mistake
[X] Wrong: "Failover time stays the same no matter how many slaves there are."
[OK] Correct: Because Redis must check each slave's status, more slaves mean more checks and more time.
Interview Connect
Understanding how failover time grows helps you explain system reliability and scaling in real projects.
Self-Check
"What if Redis used a way to check all slaves at once instead of one by one? How would the time complexity change?"