Replication strategies in DBMS Theory - Time & Space Complexity

Time Complexity: Replication strategies

O(r)

Understanding Time Complexity

Replication strategies in databases help copy data across servers to improve availability and reliability.

We want to understand how the time to replicate data grows as the amount of data increases.

Scenario Under Consideration

Analyze the time complexity of this simple replication process.

-- Pseudocode for synchronous replication
BEGIN TRANSACTION;
INSERT INTO master_table VALUES (...);
FOR EACH replica IN replicas LOOP
  SEND data TO replica;
  WAIT for replica ACKNOWLEDGEMENT;
END LOOP;
COMMIT TRANSACTION;

This code inserts data into the master database and sends it to each replica, waiting for confirmation before finishing.

Identify Repeating Operations

Look for repeated actions that affect time.

• Primary operation: Sending data and waiting for acknowledgement to each replica.
• How many times: Once per replica, so the number of replicas determines repetitions.

How Execution Grows With Input

As the number of replicas grows, the time to complete replication grows roughly in direct proportion.

Input Size (number of replicas)	Approx. Operations
10	10 sends and waits
100	100 sends and waits
1000	1000 sends and waits

Pattern observation: Doubling replicas roughly doubles the replication time.

Final Time Complexity

Time Complexity: O(r)

This means the replication time grows linearly with the number of replicas.

Common Mistake

[X] Wrong: "Replication time stays the same no matter how many replicas there are."

[OK] Correct: Each replica requires sending data and waiting, so more replicas mean more total time.

Interview Connect

Understanding how replication time grows helps you design systems that stay fast and reliable as they scale.

Self-Check

What if replication was asynchronous and did not wait for acknowledgements? How would the time complexity change?

Practice

1. Which replication strategy involves one main server handling all writes and one or more servers copying data from it?

easy

A. Master-Slave replication

B. Master-Master replication

C. Peer-to-Peer replication

D. Snapshot replication

Solution

1. Step 1: Understand Master-Slave replication

   In this strategy, one server (master) handles all write operations, and other servers (slaves) copy data from it.

2. Step 2: Compare with other strategies

   Master-Master allows multiple masters; Peer-to-Peer is decentralized; Snapshot copies data at intervals.

3. Final Answer:

   Master-Slave replication -> Option A

4. Quick Check:

   One main write server = Master-Slave [OK]

Hint: Master-Slave means one master writes, slaves copy [OK]

Common Mistakes:

• Confusing Master-Slave with Master-Master
• Thinking slaves can write data
• Mixing snapshot with continuous replication

2. Which of the following is the correct syntax to describe Master-Master replication?

easy

A. Two servers both accept writes and replicate changes to each other

B. One server writes, others read only

C. Data is copied only once at setup

D. Servers do not communicate

Solution

1. Step 1: Define Master-Master replication

   Both servers can accept writes and replicate changes to each other to keep data synchronized.

2. Step 2: Eliminate incorrect options

   Data is copied only once at setup describes snapshot; One server writes, others read only describes Master-Slave; Servers do not communicate is not replication.

3. Final Answer:

   Two servers both accept writes and replicate changes to each other -> Option A

4. Quick Check:

   Master-Master means both write and sync [OK]

Hint: Master-Master means both servers write and sync [OK]

Common Mistakes:

• Thinking only one server writes in Master-Master
• Confusing snapshot with replication
• Assuming no communication means replication

3. Consider a Master-Slave replication setup where the master server receives 100 write requests per second. If slaves replicate with a delay of 2 seconds, what is the expected delay in data consistency on slaves?

medium

A. Immediate consistency

B. No delay, slaves write directly

C. 2 seconds delay

D. 100 seconds delay

Solution

1. Step 1: Understand replication delay

   Slaves replicate data from master with a 2-second delay, so data on slaves lags behind master by 2 seconds.

2. Step 2: Analyze options

   Immediate consistency means no delay, which is incorrect. 100 seconds delay is unrelated to request rate. Slaves do not write directly.

3. Final Answer:

   2 seconds delay -> Option C

4. Quick Check:

   Replication delay = 2 seconds [OK]

Hint: Replication delay equals slave lag time [OK]

Common Mistakes:

• Confusing request rate with delay time
• Assuming slaves write directly
• Thinking slaves are always immediately consistent

4. A database administrator sets up Master-Master replication but notices data conflicts when both servers write the same record simultaneously. What is the best way to fix this?

medium

A. Allow only one server to write at a time without syncing

B. Switch to Master-Slave replication

C. Disable replication entirely

D. Implement conflict resolution rules or use timestamps

Solution

1. Step 1: Identify cause of conflicts

   Simultaneous writes cause conflicts in Master-Master replication because both servers can change the same data.

2. Step 2: Apply conflict resolution

   Using rules like timestamps or last-write-wins helps resolve conflicts automatically.

3. Final Answer:

   Implement conflict resolution rules or use timestamps -> Option D

4. Quick Check:

   Conflict resolution fixes simultaneous writes [OK]

Hint: Use conflict rules to fix Master-Master write clashes [OK]

Common Mistakes:

• Thinking disabling replication solves conflicts
• Switching to Master-Slave without need
• Ignoring conflict resolution mechanisms

5. You want a replication strategy that provides high availability and allows writes on multiple servers but can tolerate occasional conflicts. Which strategy fits best?

hard

A. Master-Slave replication

B. Master-Master replication

C. Snapshot replication

D. No replication

Solution

1. Step 1: Analyze requirements

   High availability and multiple write servers require a strategy where more than one server can accept writes.

2. Step 2: Match strategy to needs

   Master-Master replication allows multiple write servers but may have conflicts; Master-Slave does not allow multiple writes.

3. Final Answer:

   Master-Master replication -> Option B

4. Quick Check:

   Multiple writes + availability = Master-Master [OK]

Hint: Multiple write servers need Master-Master replication [OK]

Common Mistakes:

• Choosing Master-Slave for multiple writes
• Ignoring conflict tolerance
• Thinking snapshot replication supports writes