Log compaction in Kafka - Time & Space Complexity

Time Complexity: Log compaction

O(n)

Understanding Time Complexity

Log compaction in Kafka helps keep only the latest value for each key in a topic.

We want to understand how the time to compact logs grows as the log size increases.

Scenario Under Consideration

Analyze the time complexity of this simplified log compaction process.

    Map<String, String> latestRecords = new HashMap<>();
    for (Record record : log) {
        latestRecords.put(record.key(), record.value());
    }
    List<Record> compactedLog = new ArrayList<>();
    for (Map.Entry<String, String> entry : latestRecords.entrySet()) {
        compactedLog.add(new Record(entry.getKey(), entry.getValue()));
    }
    

This code keeps only the newest record for each key by scanning the log once and then rebuilding the compacted log.

Identify Repeating Operations

Look at what repeats as the log grows.

• Primary operation: Looping through all records in the log once.
• How many times: Exactly once for each record in the log.
• Secondary operation: Looping through unique keys to build the compacted log.
• How many times: Once for each unique key, which is at most the number of records.

How Execution Grows With Input

As the log size grows, the number of operations grows roughly the same way.

Input Size (n)	Approx. Operations
10	About 20 (10 to scan + up to 10 to rebuild)
100	About 200 (100 to scan + up to 100 to rebuild)
1000	About 2000 (1000 to scan + up to 1000 to rebuild)

Pattern observation: The total work grows roughly in direct proportion to the log size.

Final Time Complexity

Time Complexity: O(n)

This means the time to compact grows linearly with the number of records in the log.

Common Mistake

[X] Wrong: "Log compaction takes longer than linear time because it compares every record to every other record."

[OK] Correct: The process only scans the log once and uses a map to keep track of the latest record per key, so it does not compare records pairwise.

Interview Connect

Understanding how log compaction scales helps you explain efficient data processing in distributed systems.

Self-Check

What if the log contained many duplicate keys clustered together? How would that affect the time complexity?

Practice

1. What is the main purpose of log compaction in Kafka?

easy

A. To compress messages to save disk space

B. To delete all messages older than a certain time

C. To replicate messages across multiple brokers

D. To keep only the latest message for each key in a topic

Solution

1. Step 1: Understand log compaction concept

   Log compaction keeps the latest message per key, removing older duplicates.

2. Step 2: Compare with other options

   Deleting old messages is retention, compression is different, replication is for fault tolerance.

3. Final Answer:

   To keep only the latest message for each key in a topic -> Option D

4. Quick Check:

   Log compaction = latest message per key [OK]

Hint: Log compaction keeps latest per key, not all old messages [OK]

Common Mistakes:

• Confusing log compaction with time-based retention
• Thinking compression means log compaction
• Mixing replication with compaction

2. Which configuration enables log compaction on a Kafka topic?

easy

A. cleanup.policy=delete

B. cleanup.policy=compact

C. log.compaction.enabled=true

D. retention.ms=0

Solution

1. Step 1: Identify correct cleanup policy

   Log compaction is enabled by setting cleanup.policy=compact on the topic.

2. Step 2: Eliminate incorrect options

   cleanup.policy=delete is default retention, log.compaction.enabled is invalid, retention.ms controls time retention.

3. Final Answer:

   cleanup.policy=compact -> Option B

4. Quick Check:

   Enable compaction with cleanup.policy=compact [OK]

Hint: Remember: compact, not delete, enables log compaction [OK]

Common Mistakes:

• Using cleanup.policy=delete instead of compact
• Assuming a separate 'log.compaction.enabled' setting exists
• Confusing retention.ms with compaction setting

3. Given a compacted Kafka topic with keys and values:
key1: v1, key2: v2, key1: v3, key3: v4
What messages remain after log compaction?

medium

A. key1: v3, key2: v2, key3: v4

B. key1: v1, key2: v2, key3: v4

C. key1: v3, key2: v2

D. key2: v2, key3: v4

Solution

1. Step 1: Identify latest message per key

   For key1, latest is v3; key2 is v2; key3 is v4.

2. Step 2: List messages after compaction

   Only latest per key remain: key1:v3, key2:v2, key3:v4.

3. Final Answer:

   key1: v3, key2: v2, key3: v4 -> Option A

4. Quick Check:

   Latest message per key kept [OK]

Hint: Keep only last message per key after compaction [OK]

Common Mistakes:

• Keeping all messages instead of only latest per key
• Confusing order and keeping first message per key
• Dropping keys incorrectly

4. You set cleanup.policy=compact on a topic but notice old messages are not removed. What is a likely cause?

medium

A. The topic has no keys in messages

B. The retention.ms is set to 0

C. The broker is running in debug mode

D. The topic has too many partitions

Solution

1. Step 1: Understand log compaction requirement

   Log compaction requires messages to have keys to identify duplicates.

2. Step 2: Analyze why old messages remain

   If messages lack keys, compaction cannot remove duplicates, so old messages stay.

3. Final Answer:

   The topic has no keys in messages -> Option A

4. Quick Check:

   Compaction needs keys to remove old messages [OK]

Hint: Compaction needs keys; no keys means no compaction [OK]

Common Mistakes:

• Assuming retention.ms=0 disables compaction
• Blaming debug mode for compaction issues
• Thinking partition count affects compaction directly

5. You want to store the current state of user profiles in Kafka using log compaction. Which approach is best?

hard

A. Use a topic with cleanup.policy=delete and produce messages without keys

B. Use a topic with retention.ms=0 and produce messages with random keys

C. Use a topic with cleanup.policy=compact and produce messages with user ID as key

D. Use a topic with cleanup.policy=compact but produce messages without keys

Solution

1. Step 1: Identify requirements for storing current state

   Current state needs latest update per user, so keys must be user IDs.

2. Step 2: Choose correct topic configuration

   Log compaction enabled with cleanup.policy=compact keeps latest per key.

3. Step 3: Eliminate wrong options

   Delete policy removes old messages by time, no keys prevent compaction, random keys break state tracking.

4. Final Answer:

   Use a topic with cleanup.policy=compact and produce messages with user ID as key -> Option C

5. Quick Check:

   Compaction + keys = current state storage [OK]

Hint: Use compact policy and keys for current state topics [OK]

Common Mistakes:

• Using delete policy for state storage
• Producing messages without keys
• Using random keys that break compaction logic