Geo-replication strategies in Kafka - Time & Space Complexity

Time Complexity: Geo-replication strategies

O(m x c)

Understanding Time Complexity

When using geo-replication in Kafka, we want to know how the time to sync data grows as the amount of data or number of clusters increases.

We ask: How does the replication process scale with more data and more locations?

Scenario Under Consideration

Analyze the time complexity of the following Kafka geo-replication logic.

// Pseudocode for geo-replication sync
for each topicPartition in sourceCluster {
  for each message in topicPartition {
    send message to all remoteClusters
  }
}
    

This code sends every message from each partition in the source cluster to all remote clusters.

Identify Repeating Operations

Look at what repeats in the code:

• Primary operation: Sending each message to all remote clusters.
• How many times: For every message in every partition, repeated for each remote cluster.

How Execution Grows With Input

As the number of messages or partitions grows, and as the number of remote clusters grows, the total work grows too.

Input Size (messages x clusters)	Approx. Operations
10 messages x 2 clusters	20 sends
100 messages x 3 clusters	300 sends
1000 messages x 5 clusters	5000 sends

Pattern observation: The work grows proportionally with both messages and clusters multiplied together.

Final Time Complexity

Time Complexity: O(m × c)

This means the time grows in direct proportion to the number of messages m and the number of clusters c.

Common Mistake

[X] Wrong: "The replication time only depends on the number of messages, not the number of clusters."

[OK] Correct: Each message must be sent to every remote cluster, so more clusters mean more total sends and more time.

Interview Connect

Understanding how replication scales helps you design systems that stay fast as they grow. This skill shows you can think about real-world data flow and performance.

Self-Check

"What if we batch messages before sending to remote clusters? How would the time complexity change?"