In-sync replicas (ISR) in Kafka - Time & Space Complexity

Time Complexity: In-sync replicas (ISR)

O(n)

Understanding Time Complexity

When working with Kafka's In-sync replicas (ISR), it's important to understand how the system keeps track of replicas that are up-to-date.

We want to know how the time to check and update ISR changes as the number of replicas grows.

Scenario Under Consideration

Analyze the time complexity of the following Kafka ISR update logic.

// Pseudocode for ISR update
for each replica in replicasList {
  if (replica.lastOffset == leader.lastOffset) {
    add replica to ISR
  } else {
    remove replica from ISR
  }
}
    

This code checks each replica's offset against the leader's offset to update the ISR list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through all replicas to compare offsets.
• How many times: Once per replica in the replicas list.

How Execution Grows With Input

The time to update ISR grows directly with the number of replicas.

Input Size (n)	Approx. Operations
10	10 comparisons
100	100 comparisons
1000	1000 comparisons

Pattern observation: Doubling replicas roughly doubles the work needed.

Final Time Complexity

Time Complexity: O(n)

This means the time to update ISR grows linearly with the number of replicas.

Common Mistake

[X] Wrong: "Checking ISR is constant time no matter how many replicas there are."

[OK] Correct: Each replica must be checked individually, so more replicas mean more work.

Interview Connect

Understanding how ISR updates scale helps you explain Kafka's reliability and performance in real systems.

Self-Check

"What if we only checked replicas that recently changed offset? How would the time complexity change?"

Practice

1. What does In-sync replicas (ISR) mean in Kafka?

easy

A. Replicas that are offline

B. Replicas that never receive data

C. Replicas that have the latest data from the leader

D. Replicas that only store old data

Solution

1. Step 1: Understand the role of ISR

   ISR are replicas that keep up-to-date with the leader's data.

2. Step 2: Compare options

   Only Replicas that have the latest data from the leader correctly describes ISR as replicas with the latest data.

3. Final Answer:

   Replicas that have the latest data from the leader -> Option C

4. Quick Check:

   ISR = Latest data replicas [OK]

Hint: ISR means replicas fully caught up with leader data [OK]

Common Mistakes:

• Thinking ISR includes offline replicas
• Confusing ISR with replicas that lag behind
• Assuming ISR means replicas with old data

2. Which Kafka configuration controls the minimum number of ISR replicas required to acknowledge a write?

easy

A. replica.fetch.max.bytes

B. min.insync.replicas

C. max.insync.replicas

D. offsets.retention.minutes

Solution

1. Step 1: Identify configuration related to ISR acknowledgments

   The setting min.insync.replicas defines the minimum ISR count for write success.

2. Step 2: Eliminate unrelated options

   Other options control fetch size or retention, not ISR acknowledgments.

3. Final Answer:

   min.insync.replicas -> Option B

4. Quick Check:

   Minimum ISR replicas = min.insync.replicas [OK]

Hint: min.insync.replicas sets minimum ISR for writes [OK]

Common Mistakes:

• Confusing min.insync.replicas with max.insync.replicas
• Choosing unrelated configs like offsets.retention.minutes
• Assuming replica.fetch.max.bytes controls ISR count

3. Given a Kafka topic with 3 replicas and ISR = [replica1, replica2], what happens if replica2 falls behind and leaves ISR?

medium

A. Only replica1 remains in ISR; leader continues with one ISR

B. Leader stops producing until replica2 catches up

C. All replicas are removed from ISR

D. Replica2 becomes the new leader immediately

Solution

1. Step 1: Understand ISR behavior when a replica falls behind

   If a replica lags, it is removed from ISR, leaving others in ISR.

2. Step 2: Analyze leader and ISR state

   The leader continues with remaining ISR replicas; it does not stop or change leader immediately.

3. Final Answer:

   Only replica1 remains in ISR; leader continues with one ISR -> Option A

4. Quick Check:

   Lagging replica leaves ISR, leader continues [OK]

Hint: Lagging replica leaves ISR; leader stays with remaining ISR [OK]

Common Mistakes:

• Thinking leader stops producing when ISR shrinks
• Assuming all replicas leave ISR together
• Believing lagging replica becomes leader immediately

4. You see this error in Kafka logs: "Not enough replicas are in ISR to satisfy min.insync.replicas". What is the likely cause?

medium

A. The consumer group is not committed

B. The leader replica is offline

C. The topic has zero partitions

D. Too few replicas are currently in ISR compared to min.insync.replicas

Solution

1. Step 1: Interpret the error message

   The error means the number of replicas in ISR is less than the configured minimum.

2. Step 2: Match cause with options

   Too few replicas are currently in ISR compared to min.insync.replicas directly matches the error cause; other options are unrelated to ISR count.

3. Final Answer:

   Too few replicas are currently in ISR compared to min.insync.replicas -> Option D

4. Quick Check:

   ISR count below min.insync.replicas causes error [OK]

Hint: Error means ISR count < min.insync.replicas [OK]

Common Mistakes:

• Blaming leader offline instead of ISR count
• Confusing consumer group commit with ISR errors
• Thinking zero partitions cause this error

5. You want to ensure high availability in Kafka by allowing leader failover only if at least 2 replicas are in ISR. Which configuration and setup achieve this?

hard

A. Set min.insync.replicas=2 and have at least 3 replicas per partition

B. Set min.insync.replicas=1 and have 2 replicas per partition

C. Set min.insync.replicas=3 with 2 replicas per partition

D. Set min.insync.replicas=0 and 1 replica per partition

Solution

1. Step 1: Understand min.insync.replicas meaning

   This setting defines the minimum ISR count required for leader failover and write success.

2. Step 2: Match configuration to requirement

   To require at least 2 ISR replicas, set min.insync.replicas=2 and have at least 3 replicas to allow failover.

3. Final Answer:

   Set min.insync.replicas=2 and have at least 3 replicas per partition -> Option A

4. Quick Check:

   High availability needs min.insync.replicas=2 with 3 replicas [OK]

Hint: min.insync.replicas ≤ replica count for failover [OK]

Common Mistakes:

• Setting min.insync.replicas higher than replica count
• Using too few replicas for desired availability
• Setting min.insync.replicas to zero disables safety