Partition key and routing in Kafka - Time & Space Complexity

Time Complexity: Partition key and routing

O(n)

Understanding Time Complexity

When sending messages in Kafka, the partition key decides where each message goes.

We want to understand how the time to route messages grows as we send more messages.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

producer.send(new ProducerRecord(topic, key, value));
// Kafka uses the key to find the partition
// It hashes the key to pick a partition
// Then routes the message to that partition

This code sends one message with a key, which Kafka hashes to decide the partition for routing.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Hashing the partition key to find the partition.
• How many times: Once per message sent.

How Execution Grows With Input

Each message requires hashing its key once to find the partition.

Input Size (n)	Approx. Operations
10	10 hash operations
100	100 hash operations
1000	1000 hash operations

Pattern observation: The number of operations grows directly with the number of messages.

Final Time Complexity

Time Complexity: O(n)

This means the time to route messages grows linearly with how many messages you send.

Common Mistake

[X] Wrong: "Routing a message takes the same time no matter how many messages are sent."

[OK] Correct: Each message requires hashing its key, so more messages mean more hashing operations, increasing total time.

Interview Connect

Understanding how partition keys affect routing time helps you explain message distribution and performance in Kafka systems.

Self-Check

"What if we removed the partition key and let Kafka assign partitions randomly? How would the time complexity change?"

Practice

1. What is the main purpose of using a partition key in Kafka?

easy

A. To increase the message size limit

B. To encrypt the message content

C. To ensure related messages go to the same partition

D. To compress the message before sending

Solution

1. Step 1: Understand partition key role

   The partition key is used to decide which partition a message goes to in Kafka.

2. Step 2: Connect key to message ordering

   Using the same key ensures related messages stay in the same partition, preserving order.

3. Final Answer:

   To ensure related messages go to the same partition -> Option C

4. Quick Check:

   Partition key controls message placement = D [OK]

Hint: Partition key groups related messages together [OK]

Common Mistakes:

• Thinking partition key encrypts messages
• Confusing partition key with compression
• Believing partition key increases message size

2. Which of the following is the correct way to specify a partition key when producing a Kafka message in Java?

easy

A. producer.send(new ProducerRecord<>(topic, value));

B. producer.send(new ProducerRecord<>(value, key));

C. producer.send(new ProducerRecord<>(key, topic, value));

D. producer.send(new ProducerRecord<>(topic, key, value));

Solution

1. Step 1: Recall ProducerRecord constructor

   The correct constructor order is (topic, key, value) to specify partition key.

2. Step 2: Match options to constructor

   producer.send(new ProducerRecord<>(topic, key, value)); matches this order exactly, others mix parameters incorrectly.

3. Final Answer:

   producer.send(new ProducerRecord<>(topic, key, value)); -> Option D

4. Quick Check:

   Topic, key, value order = B [OK]

Hint: Remember ProducerRecord(topic, key, value) order [OK]

Common Mistakes:

• Swapping key and value positions
• Omitting the key parameter
• Placing key before topic incorrectly

3. Given a Kafka topic with 3 partitions, what will happen if you send messages with the same partition key "user123" repeatedly?

medium

A. All messages will go to the same partition

B. Messages will be evenly distributed across all partitions

C. Messages will be sent to partition 0 only

D. Messages will be randomly assigned to any partition

Solution

1. Step 1: Understand partition key hashing

   Kafka hashes the partition key to decide the partition number.

2. Step 2: Same key means same hash and partition

   Repeated messages with "user123" key will always hash to the same partition.

3. Final Answer:

   All messages will go to the same partition -> Option A

4. Quick Check:

   Same key -> same partition = C [OK]

Hint: Same key always hashes to same partition [OK]

Common Mistakes:

• Assuming keys distribute evenly without hashing
• Thinking messages go to partition 0 by default
• Believing messages are randomly assigned despite keys

4. You wrote this code to send messages with keys but all messages end up in different partitions. What is the likely mistake?

producer.send(new ProducerRecord<>(topic, null, value));

medium

A. The topic name is missing

B. The key is null, so messages are distributed randomly

C. The value is null, causing errors

D. ProducerRecord constructor is used incorrectly

Solution

1. Step 1: Check the key parameter

   The key is set to null, so Kafka cannot use it for partitioning.

2. Step 2: Understand default partitioning behavior

   Without a key, Kafka distributes messages randomly across partitions.

3. Final Answer:

   The key is null, so messages are distributed randomly -> Option B

4. Quick Check:

   Null key -> random partitions = A [OK]

Hint: Null key means random partition assignment [OK]

Common Mistakes:

• Assuming null key sends to partition 0
• Confusing missing topic with null key
• Thinking null value causes partitioning issues

5. You want to ensure that messages related to the same customer ID always go to the same partition, but your customer IDs sometimes are null or empty strings. How should you handle partition keys to maintain message order for valid IDs and avoid errors?

hard

A. Use the customer ID as key only if it is non-empty; otherwise, assign a default fixed key

B. Always send messages with null keys to let Kafka distribute randomly

C. Convert null or empty IDs to random UUIDs as keys

D. Ignore keys and rely on Kafka's default partitioning

Solution

1. Step 1: Identify the problem with null or empty keys

   Null or empty keys cause Kafka to distribute messages randomly, breaking order.

2. Step 2: Use a default fixed key for missing IDs

   Assigning a fixed key for missing IDs groups those messages in one partition, preserving order for them.

3. Step 3: Keep valid customer IDs as keys

   Valid IDs remain keys to ensure their messages go to the same partition.

4. Final Answer:

   Use the customer ID as key only if it is non-empty; otherwise, assign a default fixed key -> Option A

5. Quick Check:

   Non-empty key or default fixed key = A [OK]

Hint: Use default key for missing IDs to keep order [OK]

Common Mistakes:

• Sending null keys causing random partitioning
• Using random UUIDs breaking message grouping
• Ignoring keys and losing message order