Time Complexity: Master-replica architecture
O(n)
0
0
Master-replica architecture in Redis - Time & Space Complexity
Understanding Time Complexity
When using Redis master-replica setup, it is important to understand how the time to process commands grows as data or replicas increase.
We want to know how the system handles more data or more replicas in terms of speed.
Scenario Under Consideration
Analyze the time complexity of replicating data from master to replicas.
# Setup on each replica (once):
REPLICAOF master_host master_port
# Master writes data
SET key value
# Master automatically sends updates to all connected replicas
# Replica receives and applies updates
# This happens continuously as master changes
This code shows a master writing data and replicas copying those changes continuously.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Master sends each write command to all replicas.
- How many times: For each write, the master sends data to every replica.
How Execution Grows With Input
As the number of replicas grows, the master must send the same data to more places.
| Input Size (n = replicas) | Approx. Operations |
|---|---|
| 1 | 1 send per write |
| 10 | 10 sends per write |
| 100 | 100 sends per write |
Pattern observation: The work grows directly with the number of replicas.
Final Time Complexity
Time Complexity: O(n)
This means the time to replicate data grows linearly as you add more replicas.
Common Mistake
[X] Wrong: "Adding more replicas does not affect the master's speed because replicas work independently."
[OK] Correct: The master must send data to each replica, so more replicas mean more work for the master.
Interview Connect
Understanding how replication scales helps you design systems that stay fast as they grow. This skill shows you can think about real system limits and plan accordingly.
Self-Check
"What if the master batches updates before sending to replicas? How would the time complexity change?"