State stores in Kafka - Time & Space Complexity

Time Complexity: State stores

O(1)

Understanding Time Complexity

When using state stores in Kafka Streams, it's important to understand how the time to access and update data grows as the stored data grows.

We want to know how the operations on state stores scale with the amount of data inside them.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Accessing and updating a key in a state store
KeyValueStore<String, Long> store = context.getStateStore("counts");
Long currentCount = store.get(key);
if (currentCount == null) {
    store.put(key, 1L);
} else {
    store.put(key, currentCount + 1);
}

This code reads the current count for a key and updates it by adding one in a Kafka Streams state store.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing and updating a single key in the state store.
• How many times: Once per key update, typically inside a stream processing loop over incoming records.

How Execution Grows With Input

Each get or put operation looks up or updates one key in the store.

Input Size (number of keys)	Approx. Operations per key
10	1 get + 1 put
100	1 get + 1 put
1000	1 get + 1 put

Pattern observation: The time per key update stays about the same, no matter how many keys are stored.

Final Time Complexity

Time Complexity: O(1)

This means each key access or update takes about the same time, regardless of how many keys are stored.

Common Mistake

[X] Wrong: "Accessing a key in the state store gets slower as the store grows larger."

[OK] Correct: State stores use efficient data structures like RocksDB or in-memory hash maps that keep access time close to constant, so each key lookup or update stays fast even as the store grows.

Interview Connect

Understanding how state stores handle data efficiently shows you know how Kafka Streams manages data at scale, a useful skill for building real-time applications.

Self-Check

"What if the state store used a simple list instead of a key-value store? How would the time complexity change?"

Practice

1. What is the main purpose of a state store in Kafka Streams?

easy

A. To monitor Kafka cluster health

B. To send messages to Kafka topics

C. To configure Kafka brokers

D. To keep data between processing of different messages

Solution

1. Step 1: Understand state store role and compare options

   A state store holds data locally so the app can remember information across messages. Sending messages, configuring brokers, and monitoring health are unrelated to state stores.

2. Final Answer:

   To keep data between processing of different messages -> Option D

3. Quick Check:

   State store = remembers data between messages [OK]

Hint: State stores remember data across messages [OK]

Common Mistakes:

• Confusing state store with message sending
• Thinking state store configures Kafka brokers
• Assuming state store monitors cluster health

2. Which of the following is the correct way to add a persistent key-value state store named myStore to a StreamsBuilder in Kafka Streams?

easy

A. builder.addStateStore(Stores.keyValueStoreBuilder(Stores.persistentKeyValueStore("myStore"), Serdes.String(), Serdes.String()))

B. builder.addStore("myStore", persistentKeyValueStore())

C. builder.createStateStore("myStore", KeyValueStore.class)

D. builder.addKeyValueStore("myStore", Serdes.String(), Serdes.String())

Solution

1. Step 1: Recall correct syntax for adding state store and check options

   The correct method uses addStateStore with a store builder from Stores.keyValueStoreBuilder and Stores.persistentKeyValueStore. Only builder.addStateStore(Stores.keyValueStoreBuilder(Stores.persistentKeyValueStore("myStore"), Serdes.String(), Serdes.String())) matches the correct method signature and usage.

2. Final Answer:

   builder.addStateStore(Stores.keyValueStoreBuilder(Stores.persistentKeyValueStore("myStore"), Serdes.String(), Serdes.String())) -> Option A

3. Quick Check:

   Use addStateStore with keyValueStoreBuilder [OK]

Hint: Use addStateStore with keyValueStoreBuilder [OK]

Common Mistakes:

• Using incorrect method names like addStore or createStateStore
• Missing Serdes parameters for key and value
• Confusing persistent and in-memory store creation

3. Given the following Kafka Streams processor code snippet, what will be the output stored in the state store after processing the input key-value pairs ("key1", 1) and ("key1", 2)?

KeyValueStore<String, Integer> store = context.getStateStore("countStore");
Integer current = store.get("key1");
if (current == null) current = 0;
store.put("key1", current + value);

medium

A. The state store will have key "key1" with value 1

B. The state store will have key "key1" with value 2

C. The state store will have key "key1" with value 3

D. The state store will be empty

Solution

1. Step 1: Trace code execution for both inputs

   First ("key1", 1): store.get("key1") returns null, current = 0, store.put("key1", 0 + 1) = 1. Second ("key1", 2): store.get("key1") = 1, current = 1, store.put("key1", 1 + 2) = 3.

2. Final Answer:

   The state store will have key "key1" with value 3 -> Option C

3. Quick Check:

   Sum values for key1 = 3 [OK]

Hint: Add new value to existing store value for same key [OK]

Common Mistakes:

• Assuming store resets between messages
• Not handling null initial value
• Overwriting instead of adding values

4. Identify the error in this Kafka Streams processor code that tries to update a state store named myStore:

KeyValueStore<String, Long> store = context.getStateStore("myStore");
Long count = store.get(key);
count += 1L;
store.put(key, count);

medium

A. The getStateStore method is called incorrectly

B. The variable count may be null causing a NullPointerException

C. The put method should be called before incrementing count

D. The store should be cast to ReadOnlyKeyValueStore

Solution

1. Step 1: Check store.get(key) handling and increment operation

   If the key does not exist, store.get(key) returns null, so count is null. Trying to do count += 1L when count is null causes a NullPointerException.

2. Final Answer:

   The variable count may be null causing a NullPointerException -> Option B

3. Quick Check:

   Null check needed before incrementing count [OK]

Hint: Always check for null before incrementing store value [OK]

Common Mistakes:

• Ignoring null values from store.get()
• Incorrect method usage for state store access
• Wrong store type casting

5. You want to build a Kafka Streams application that counts the number of times each word appears in a stream of sentences. Which approach correctly uses a state store to maintain the counts?

hard

A. Use a persistent key-value state store to keep counts, update counts on each word, and query the store for results

B. Use an in-memory state store without updating counts, just print words as they arrive

C. Use a state store only to store the last processed sentence, ignoring counts

D. Use a state store to buffer all sentences without processing counts

Solution

1. Step 1: Understand word count requirement and evaluate options

   Counting words requires storing and updating counts per word, so a key-value store is needed. Use a persistent key-value state store to keep counts, update counts on each word, and query the store for results fits the requirement.

2. Final Answer:

   Use a persistent key-value state store to keep counts, update counts on each word, and query the store for results -> Option A

3. Quick Check:

   Persistent store + update counts = correct word count approach [OK]

Hint: Use persistent store and update counts per word [OK]

Common Mistakes:

• Using in-memory store without updating counts
• Storing sentences instead of counts
• Buffering data without processing