Read replicas in GCP - Time & Space Complexity

Time Complexity: Read replicas

O(n)

Understanding Time Complexity

When using read replicas in cloud databases, it's important to understand how the number of replicas affects the work done by the system.

We want to know how the system's operations grow as we add more read replicas.

Scenario Under Consideration

Analyze the time complexity of the following operation sequence.

// Create a primary database instance
const primaryInstance = createInstance('primary-db');

// Create multiple read replicas
for (let i = 0; i < n; i++) {
  createReadReplica(primaryInstance, `replica-${i}`);
}

// Read queries are sent to replicas
sendReadQuery(`replica-${queryTarget}`);

This sequence creates one primary database and then creates n read replicas from it. Read queries are distributed to these replicas.

Identify Repeating Operations

Identify the API calls, resource provisioning, data transfers that repeat.

• Primary operation: Creating each read replica instance.
• How many times: Once for each replica, so n times.
• Data replication: Continuous data syncing from primary to each replica, happening n times in parallel.

How Execution Grows With Input

As you add more replicas, the system must create and maintain each one separately.

Input Size (n)	Approx. Api Calls/Operations
10	About 10 replica creation calls and 10 data sync streams
100	About 100 replica creation calls and 100 data sync streams
1000	About 1000 replica creation calls and 1000 data sync streams

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

Final Time Complexity

Time Complexity: O(n)

This means the time and work needed grow in a straight line as you add more read replicas.

Common Mistake

[X] Wrong: "Adding more read replicas does not increase system work because they just copy data automatically."

[OK] Correct: Each replica requires separate setup and continuous syncing, so the system's work increases with each one.

Interview Connect

Understanding how adding replicas affects system work helps you design scalable cloud databases and explain trade-offs clearly.

Self-Check

"What if we used a caching layer instead of read replicas? How would the time complexity of handling read requests change?"