At-least-once delivery in Kafka - Time & Space Complexity

Time Complexity: At-least-once delivery

O(n)

Understanding Time Complexity

When using Kafka's at-least-once delivery, messages may be sent multiple times to ensure none are lost.

We want to understand how the number of message retries affects the processing time as the input grows.

Scenario Under Consideration

Analyze the time complexity of the following Kafka consumer processing with at-least-once delivery.

// Pseudocode for Kafka consumer with at-least-once delivery
while (true) {
  records = consumer.poll(timeout)
  for (record in records) {
    process(record)
  }
  consumer.commitSync()
}

This code continuously polls messages, processes each one, and commits offsets to ensure messages are not lost.

Identify Repeating Operations

Look for repeated actions that affect time.

• Primary operation: Loop over all messages received in each poll.
• How many times: Once per message batch, repeated continuously as messages arrive.

How Execution Grows With Input

As the number of messages increases, processing time grows roughly in direct proportion.

Input Size (n)	Approx. Operations
10	About 10 process calls
100	About 100 process calls
1000	About 1000 process calls

Pattern observation: Processing time grows linearly as more messages arrive.

Final Time Complexity

Time Complexity: O(n)

This means processing time grows directly with the number of messages received.

Common Mistake

[X] Wrong: "At-least-once delivery means each message is processed only once, so time stays constant regardless of retries."

[OK] Correct: Messages can be delivered multiple times, so processing may repeat, increasing total work as input grows.

Interview Connect

Understanding how message retries affect processing time helps you explain real-world Kafka behavior clearly and confidently.

Self-Check

What if we switched from at-least-once to exactly-once delivery? How would the time complexity change?