Exactly-once stream processing in Kafka - Time & Space Complexity

Time Complexity: Exactly-once stream processing

O(n)

Understanding Time Complexity

When using Kafka for exactly-once stream processing, it is important to understand how the processing time changes as the amount of data grows.

We want to know how the cost of ensuring each message is processed once and only once scales with input size.

Scenario Under Consideration

Analyze the time complexity of the following Kafka stream processing code snippet.

    StreamsBuilder builder = new StreamsBuilder();
    builder.stream("input-topic")
           .transform(() -> new ExactlyOnceTransformer())
           .to("output-topic");

    KafkaStreams streams = new KafkaStreams(builder.build(), props);
    streams.start();
    

This code sets up a Kafka Streams application that reads from an input topic, applies a transformation ensuring exactly-once processing, and writes to an output topic.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Processing each message from the input topic one by one.
• How many times: Once per message received in the stream, which can be very large.

How Execution Grows With Input

As the number of messages increases, the processing steps also increase roughly in the same way.

Input Size (n)	Approx. Operations
10	About 10 message processing steps
100	About 100 message processing steps
1000	About 1000 message processing steps

Pattern observation: The work grows directly with the number of messages, so doubling messages roughly doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the processing time grows linearly with the number of messages to process.

Common Mistake

[X] Wrong: "Exactly-once processing means the system does extra work that grows faster than the number of messages."

[OK] Correct: The overhead for exactly-once is mostly constant per message, so total work still grows linearly with message count, not faster.

Interview Connect

Understanding how exactly-once processing scales helps you explain real-world streaming system behavior clearly and confidently.

Self-Check

"What if we added a batch commit step that processes messages in groups instead of one by one? How would the time complexity change?"