Dead letter topics in GCP - Time & Space Complexity

Time Complexity: Dead letter topics

O(n)

Understanding Time Complexity

When using dead letter topics in Google Cloud Pub/Sub, it's important to understand how the time to process messages changes as the number of messages grows.

We want to know how the system behaves when many messages are sent and some are moved to the dead letter topic.

Scenario Under Consideration

Analyze the time complexity of publishing messages and handling dead letter topics.

// Publish messages to a main topic
for (int i = 0; i < n; i++) {
  publishMessage(mainTopic, message[i]);
}

// Messages that fail processing are sent to dead letter topic
subscribe(mainTopic, message => {
  if (!process(message)) {
    publishMessage(deadLetterTopic, message);
  }
});

This sequence publishes n messages to a main topic and routes failed messages to a dead letter topic.

Identify Repeating Operations

Identify the API calls, resource provisioning, data transfers that repeat.

• Primary operation: Publishing messages to the main topic and possibly to the dead letter topic.
• How many times: Publishing happens once per message (n times), and dead letter publishing happens for each failed message (up to n times).

How Execution Grows With Input

As the number of messages n increases, the number of publish operations grows roughly in proportion to n.

Input Size (n)	Approx. API Calls/Operations
10	About 10 publishes to main topic, plus failed messages to dead letter topic.
100	About 100 publishes to main topic, plus failed messages to dead letter topic.
1000	About 1000 publishes to main topic, plus failed messages to dead letter topic.

Pattern observation: The total operations grow linearly with the number of messages.

Final Time Complexity

Time Complexity: O(n)

This means the time to handle messages and dead letter routing grows directly in proportion to the number of messages.

Common Mistake

[X] Wrong: "Dead letter topics add a fixed extra cost regardless of message count."

[OK] Correct: The cost depends on how many messages fail and get sent to the dead letter topic, so it grows with message volume.

Interview Connect

Understanding how message processing scales with dead letter topics shows you can reason about system behavior as load grows, a key skill in cloud design.

Self-Check

"What if the dead letter topic also triggers retries? How would that affect the time complexity?"

Practice

1. What is the main purpose of a dead letter topic in Google Cloud Pub/Sub?

easy

A. To store all successfully delivered messages

B. To speed up message delivery

C. To catch messages that fail delivery multiple times

D. To encrypt messages before sending

Solution

1. Step 1: Understand message delivery failures

   Messages that cannot be delivered after several attempts need special handling to avoid blocking the main flow.

2. Step 2: Role of dead letter topics

   Dead letter topics collect these failed messages separately so the main topic stays clean and reliable.

3. Final Answer:

   To catch messages that fail delivery multiple times -> Option C

4. Quick Check:

   Dead letter topic = catch failed messages [OK]

Hint: Dead letter topics catch failed messages only [OK]

Common Mistakes:

• Thinking dead letter topics speed delivery
• Confusing dead letter topics with encryption
• Assuming they store successful messages

2. Which block in a Pub/Sub subscription configuration is used to set a dead letter topic?

easy

A. message_storage_policy

B. retry_policy

C. ack_deadline_seconds

D. dead_letter_policy

Solution

1. Step 1: Identify configuration blocks for subscriptions

   Pub/Sub subscriptions have specific blocks for retry, dead letter, and storage policies.

2. Step 2: Locate dead letter topic setting

   The dead_letter_policy block is where you specify the dead letter topic and max delivery attempts.

3. Final Answer:

   dead_letter_policy -> Option D

4. Quick Check:

   Dead letter topic set in dead_letter_policy [OK]

Hint: Dead letter topic is in dead_letter_policy block [OK]

Common Mistakes:

• Confusing with retry_policy block
• Using message_storage_policy incorrectly
• Setting dead letter topic in ack_deadline_seconds

3. Given this subscription config snippet:

{
  "dead_letter_policy": {
    "dead_letter_topic": "projects/myproj/topics/dlt",
    "max_delivery_attempts": 5
  }
}

What happens when a message fails delivery 6 times?

medium

A. The message is retried indefinitely

B. The message is sent to the dead letter topic

C. The message is deleted immediately

D. The message is sent back to the main topic

Solution

1. Step 1: Understand max_delivery_attempts meaning

   Messages are retried up to the max_delivery_attempts count before moving to dead letter topic.

2. Step 2: Apply max_delivery_attempts = 5

   After 5 failed attempts, the 6th failure triggers sending the message to the dead letter topic.

3. Final Answer:

   The message is sent to the dead letter topic -> Option B

4. Quick Check:

   Failures > max_delivery_attempts = dead letter send [OK]

Hint: Messages move to dead letter after max attempts exceeded [OK]

Common Mistakes:

• Thinking messages retry forever
• Assuming immediate deletion on failure
• Believing message returns to main topic

4. You configured a dead letter topic but messages are not appearing there after failures. What is a likely cause?

medium

A. Dead letter topic does not exist or lacks permissions

B. max_delivery_attempts is set to 1

C. Subscription ack deadline is too long

D. Main topic has no messages

Solution

1. Step 1: Check dead letter topic existence and permissions

   If the dead letter topic is missing or the subscription lacks publish permission, messages cannot be sent there.

2. Step 2: Understand other options

   max_delivery_attempts=1 means one try before dead letter, ack deadline affects delivery timing, and main topic empty means no messages to fail.

3. Final Answer:

   Dead letter topic does not exist or lacks permissions -> Option A

4. Quick Check:

   Dead letter topic must exist and be accessible [OK]

Hint: Dead letter topic must exist and allow publishing [OK]

Common Mistakes:

• Ignoring permissions errors
• Confusing ack deadline with dead letter setup
• Assuming empty main topic causes dead letter issues

5. You want to ensure messages that fail more than 3 times go to a dead letter topic, but also want to limit the total retry time to 10 minutes. Which configuration approach is best?

hard

A. Set dead_letter_policy.max_delivery_attempts to 3 and configure retry_policy.minimum_backoff and maximum_backoff to limit retry duration

B. Set dead_letter_policy.max_delivery_attempts to 10 and rely on ack deadline for timing

C. Only set retry_policy.maximum_backoff to 10 minutes without dead letter policy

D. Set dead_letter_policy.max_delivery_attempts to 3 and disable retries

Solution

1. Step 1: Use max_delivery_attempts to limit retries

   Setting max_delivery_attempts to 3 ensures messages move to dead letter after 3 failed deliveries.

2. Step 2: Control retry timing with retry_policy

   Configuring minimum and maximum backoff controls how long retries take, helping keep total retry time within 10 minutes.

3. Step 3: Evaluate other options

   Set dead_letter_policy.max_delivery_attempts to 10 and rely on ack deadline for timing ignores retry timing, C lacks dead letter handling, and D disables retries which may lose messages prematurely.

4. Final Answer:

   Set dead_letter_policy.max_delivery_attempts to 3 and configure retry_policy minimum and maximum backoff -> Option A

5. Quick Check:

   Combine max_delivery_attempts and retry_policy for retries and dead letter [OK]

Hint: Use max_delivery_attempts plus retry_policy for timing control [OK]

Common Mistakes:

• Ignoring retry_policy for timing
• Disabling retries loses messages
• Setting max_delivery_attempts too high