Replication lag monitoring in Redis - Time & Space Complexity

Time Complexity: Replication lag monitoring

O(n)

Understanding Time Complexity

We want to understand how the time to check replication lag changes as the number of replicas grows.

How does monitoring delay increase when more replicas are involved?

Scenario Under Consideration

Analyze the time complexity of the following Redis commands used to monitor replication lag.

# Get replication info from master (includes master_repl_offset and all replica offsets/lags)
INFO replication

# Parse output to extract offsets for each replica
# MASTER_OFFSET = parse master_repl_offset
# For each replica line (e.g., slave0:...,offset=...):
#   REPLICA_OFFSET = parse offset
#   LAG = MASTER_OFFSET - REPLICA_OFFSET
    

This code fetches replication info and calculates lag for each replica by parsing offsets from the output.

Identify Repeating Operations

• Primary operation: Parsing offset for each replica from INFO output and calculating lag.
• How many times: Once per replica (one output line per replica), so the number of replicas determines repetitions.

How Execution Grows With Input

As the number of replicas increases, the time to parse each replica's info grows proportionally.

Input Size (n)	Approx. Operations
10 replicas	10 offset parses and lag calculations
100 replicas	100 offset parses and lag calculations
1000 replicas	1000 offset parses and lag calculations

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

Final Time Complexity

Time Complexity: O(n)

This means the time to monitor replication lag increases linearly as the number of replicas grows.

Common Mistake

[X] Wrong: "Checking replication lag is always constant time regardless of replicas."

[OK] Correct: Parsing replica info from INFO output requires work proportional to the number of replicas.

Interview Connect

Understanding how monitoring scales with system size helps you design better tools and anticipate delays in real setups.

Self-Check

"What if we batch requests to get all replica offsets at once? How would the time complexity change?"