Stream topology in Kafka - Time & Space Complexity

Time Complexity: Stream topology

O(n)

Understanding Time Complexity

When working with Kafka stream topology, it's important to understand how the processing time grows as the data flows through the stream steps.

We want to know how the number of operations changes as the input data size increases in the stream.

Scenario Under Consideration

Analyze the time complexity of the following Kafka Streams topology setup.

StreamsBuilder builder = new StreamsBuilder();

KStream<String, String> source = builder.stream("input-topic");

KStream<String, String> filtered = source.filter((key, value) -> value.contains("important"));

KStream<String, String> mapped = filtered.mapValues(value -> value.toUpperCase());

mapped.to("output-topic");

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

This code creates a stream that reads messages, filters them by a condition, transforms the values, and writes to an output topic.

Identify Repeating Operations

Look at the operations that happen repeatedly for each message in the stream.

• Primary operation: Processing each message through filter and map steps.
• How many times: Once per message arriving in the input topic.

How Execution Grows With Input

Each message is processed one by one through the steps, so the total work grows as more messages arrive.

Input Size (n)	Approx. Operations
10	About 10 filter and map operations
100	About 100 filter and map operations
1000	About 1000 filter and map operations

Pattern observation: The work grows linearly with the number of messages.

Final Time Complexity

Time Complexity: O(n)

This means the processing time increases directly in proportion to the number of messages.

Common Mistake

[X] Wrong: "The filter and map steps run only once regardless of input size."

[OK] Correct: Each message is processed individually, so these steps happen for every message, making the total work grow with input size.

Interview Connect

Understanding how stream processing scales with data size helps you explain system behavior clearly and shows you grasp real-world data flow challenges.

Self-Check

"What if we added a nested loop inside the mapValues step that processes each message multiple times? How would the time complexity change?"

Practice

1. What does a Kafka Streams topology represent?

easy

A. The configuration settings for Kafka brokers

B. The flow and processing steps of data in a Kafka Streams application

C. The list of Kafka topics available in the cluster

D. The schema of messages in a Kafka topic

Solution

1. Step 1: Understand the role of topology in Kafka Streams

   A topology defines how data flows and is processed in a Kafka Streams app.

2. Step 2: Differentiate topology from other Kafka concepts

   It is not about broker configs, topic lists, or message schemas, but about processing steps.

3. Final Answer:

   The flow and processing steps of data in a Kafka Streams application -> Option B

4. Quick Check:

   Topology = Data flow and processing [OK]

Hint: Topology means data flow and processing steps [OK]

Common Mistakes:

• Confusing topology with Kafka broker settings
• Thinking topology lists topics
• Assuming topology defines message schema

2. Which code snippet correctly builds a Kafka Streams topology?

easy

A. StreamsBuilder builder = new StreamsBuilder(); builder.run();

B. StreamsBuilder builder = new StreamsBuilder(); builder.start();

C. StreamsBuilder builder = new StreamsBuilder(); builder.create();

D. StreamsBuilder builder = new StreamsBuilder(); builder.build();

Solution

1. Step 1: Recall the correct method to build topology

   The method to finalize and get the topology is build().

2. Step 2: Check each option's method

   Only StreamsBuilder builder = new StreamsBuilder(); builder.build(); uses build(), others use invalid methods.

3. Final Answer:

   StreamsBuilder builder = new StreamsBuilder(); builder.build(); -> Option D

4. Quick Check:

   Use build() to create topology [OK]

Hint: Use build() method on StreamsBuilder to create topology [OK]

Common Mistakes:

• Using start(), create(), or run() instead of build()
• Confusing topology building with starting the stream

3. Given the code snippet:

StreamsBuilder builder = new StreamsBuilder();
builder.stream("input-topic").mapValues(value -> value.toUpperCase()).to("output-topic");
Topology topology = builder.build();
System.out.println(topology.describe());

What will the printed topology description include?

medium

A. A sink node for 'input-topic' and a source node for 'output-topic'

B. Only a source node for 'input-topic' without any processing

C. A source node for 'input-topic', a processor node for mapValues, and a sink node for 'output-topic'

D. An error because mapValues is not allowed in topology

Solution

1. Step 1: Analyze the stream processing steps

   The code reads from 'input-topic', applies mapValues to uppercase, then writes to 'output-topic'.

2. Step 2: Understand topology description output

   The description shows source nodes (input), processor nodes (mapValues), and sink nodes (output).

3. Final Answer:

   A source node for 'input-topic', a processor node for mapValues, and a sink node for 'output-topic' -> Option C

4. Quick Check:

   Topology describe shows source, processor, sink [OK]

Hint: Topology describe shows source, processor, and sink nodes [OK]

Common Mistakes:

• Thinking mapValues is not part of topology
• Confusing source and sink nodes
• Expecting no processor nodes in description

4. Identify the error in this Kafka Streams topology code:

StreamsBuilder builder = new StreamsBuilder();
builder.stream("input-topic").filter(value -> value.length() > 5);
Topology topology = builder.build();
System.out.println(topology.describe());

medium

A. The filtered stream is not sent to any sink topic, so no output node is created

B. The filter method is invalid and causes a syntax error

C. StreamsBuilder cannot build topology without a source topic

D. Calling build() before defining streams causes runtime error

Solution

1. Step 1: Check the stream processing chain

   The code filters the stream but does not write the result to any output topic.

2. Step 2: Understand topology implications

   Without a sink node, the topology has no output, which is usually an error or incomplete.

3. Final Answer:

   The filtered stream is not sent to any sink topic, so no output node is created -> Option A

4. Quick Check:

   Missing sink node causes incomplete topology [OK]

Hint: Always send processed stream to sink topic [OK]

Common Mistakes:

• Assuming filter causes syntax error
• Thinking build() requires no streams
• Ignoring missing sink topic after processing

5. You want to create a Kafka Streams topology that reads from two topics, merges their streams, filters messages containing 'error', and writes to an output topic. Which code snippet correctly builds this topology?

hard

A. StreamsBuilder builder = new StreamsBuilder();
KStream stream1 = builder.stream("topic1");
KStream stream2 = builder.stream("topic2");
KStream merged = stream1.merge(stream2);
merged.filter((k, v) -> v.contains("error")).to("output-topic");
Topology topology = builder.build();

B. StreamsBuilder builder = new StreamsBuilder();
KStream stream = builder.stream("topic1", "topic2");
stream.filter(v -> v.contains("error")).to("output-topic");
Topology topology = builder.build();

C. StreamsBuilder builder = new StreamsBuilder();
KStream stream1 = builder.stream("topic1");
KStream stream2 = builder.stream("topic2");
KStream merged = stream1.join(stream2, (v1, v2) -> v1 + v2);
merged.filter((k, v) -> v.contains("error")).to("output-topic");
Topology topology = builder.build();

D. StreamsBuilder builder = new StreamsBuilder();
builder.stream("topic1").filter(v -> v.contains("error")).to("output-topic");
builder.stream("topic2").filter(v -> v.contains("error")).to("output-topic");
Topology topology = builder.build();

Solution

1. Step 1: Understand the requirement

   Read from two topics, merge streams, filter messages with 'error', write to output.

2. Step 2: Evaluate each option

   StreamsBuilder builder = new StreamsBuilder(); KStream stream1 = builder.stream("topic1"); KStream stream2 = builder.stream("topic2"); KStream merged = stream1.merge(stream2); merged.filter((k, v) -> v.contains("error")).to("output-topic"); Topology topology = builder.build(); merges streams correctly, filters, then writes once. StreamsBuilder builder = new StreamsBuilder(); KStream stream = builder.stream("topic1", "topic2"); stream.filter(v -> v.contains("error")).to("output-topic"); Topology topology = builder.build(); incorrectly tries to stream two topics in one call. StreamsBuilder builder = new StreamsBuilder(); KStream stream1 = builder.stream("topic1"); KStream stream2 = builder.stream("topic2"); KStream merged = stream1.join(stream2, (v1, v2) -> v1 + v2); merged.filter((k, v) -> v.contains("error")).to("output-topic"); Topology topology = builder.build(); joins streams (not merge). StreamsBuilder builder = new StreamsBuilder(); builder.stream("topic1").filter(v -> v.contains("error")).to("output-topic"); builder.stream("topic2").filter(v -> v.contains("error")).to("output-topic"); Topology topology = builder.build(); filters separately and writes twice, not merging.

3. Final Answer:

   Option A correctly merges, filters, and writes to output topic -> Option A

4. Quick Check:

   Merge streams, filter, then write [OK]

Hint: Merge streams before filtering and writing output [OK]

Common Mistakes:

• Using join instead of merge for combining streams
• Trying to stream multiple topics in one call incorrectly
• Writing filtered streams separately without merging