Message Queue

TL;DR

• Model the queue as a durable hand-off: producers append messages, consumers lease them, and acknowledgement deletes them.
• Use a write-ahead log with group commit for fast durable writes, then partition queues across brokers for horizontal throughput.
• Track visibility deadlines in a time-ordered structure such as a Redis sorted set so expiry scans visit only leases that are due.
• Use at-least-once delivery, opaque receipt handles, idempotent consumers, and a dead-letter queue for poison messages; do not promise exactly-once effects from the broker alone.
• Preserve FIFO only where the business needs it. Message group IDs give per-key ordering while allowing unrelated groups to run in parallel.
• Replicate partitions and use a quorum-backed controller for failover; make the acks setting an explicit durability/latency choice.

Scope and assumptions

This article designs a traditional distributed work queue with named queues, pull-based consumers, explicit acknowledgements, visibility timeouts, retries, and dead-letter routing. It is closer to SQS or RabbitMQ work-queue semantics than to a replayable log such as Kafka.

The illustrative interview scenario assumes:

• Aggregate throughput can reach 1 million messages per second, with messages small enough to batch and a visibility timeout typically around 30 seconds.
• A message is delivered to one consumer at a time while its lease is valid. If the consumer crashes or fails to acknowledge before expiry, the message is eligible for redelivery.
• At-least-once delivery is required. Consumers own idempotency for side effects; exactly-once processing, if needed, is an application-level protocol.
• A queue has bounded retention, message size, visibility timeout, delivery-count, and optional FIFO group configuration. Poison messages go to a dead-letter queue.
• A single-region cluster is the primary design. Cross-region active-active replication and provider-specific protocol details are out of scope.
• All rates, failure windows, and latency targets below are scenario requirements to validate with capacity tests, not guarantees of a particular queue product.

What is a distributed message queue?

A distributed message queue decouples producers from consumers: a producer writes a message to a named queue, and one or more consumers read it independently and asynchronously. The engineering challenge isn't the queue itself; it's the combination of visibility timeout mechanics (what happens when a consumer crashes mid-processing) and durable storage that survives broker failures without sacrificing throughput.

This question tests WAL-based persistence, partition design for horizontal scale, leader election under failure, and at-least-once delivery semantics.

Functional Requirements

Core Requirements

1. Producers publish messages to named queues.
2. Consumers receive and acknowledge messages.
3. Unacknowledged messages are redelivered after a visibility timeout.
4. Messages are durable: they survive broker restarts.

Scope Exclusions

• Fan-out pub-sub semantics (closer to Kafka/SNS).
• Message transformation or schema validation.

Non-Functional Requirements

Core Requirements

• Throughput: 1M messages/second aggregate across all queues.
• Latency: Message visible to consumer within 100ms of publish.
• Durability: No message loss on a single broker failure.
• Availability: 99.99% uptime (under 52 minutes of downtime per year).
• At-least-once delivery: Every published message is consumed at least once; zero deliveries never occurs.

Below the Line

• Exactly-once delivery
• Strict global message ordering across partitions
• Cross-region active-active replication

The hardest engineering problem in scope: Implementing atomic visibility-timeout tracking while sustaining 1M messages/second is the central challenge. The broker must efficiently identify expired in-flight leases across thousands of concurrent consumers without scanning every in-flight message on every tick.

This constraint should be stated early because it eliminates the naive approach: a clean-looking visibility tracker becomes a 30-million-entry scan at scale if it checks every in-flight message on every tick.

Exactly-once delivery is deferred because it requires distributed transactions or consumer-side idempotency, which belongs in the application layer rather than the queue. To add it: assign each message a deduplication ID, maintain a TTLed seen-IDs set in Redis, and reject reprocessed IDs on consumer acknowledgement.

Strict global ordering across partitions is deferred because it forces a single partition, collapsing horizontal throughput. To add it: use FIFO queues with message group IDs (covered in Deep Dive 3), which provide per-key ordering while allowing cross-key parallelism.

Cross-region active-active replication is deferred because it adds cross-datacenter round-trips to the synchronous write path. To add it: use async replication to a secondary region, accepting a recovery point objective of a few seconds in exchange for local write performance.

30-second answer

Use a partitioned broker cluster with a group-commit WAL. Producers batch messages into named queues, and the broker acknowledges only after the chosen durability policy persists the batch. Consumers long-poll, receive opaque receipt handles, and hold a visibility lease while processing; delete_message removes a message, while expired leases return to the visible queue or move to a DLQ after too many deliveries. A Redis sorted set or equivalent tracks lease expiry without scanning every in-flight message. Replicated partitions, a quorum-backed controller, consumer rebalancing, idempotent handlers, and explicit acks settings provide throughput, failover, and at-least-once delivery.

5-minute explanation

Start with the delivery contract rather than the broker brand. A producer writes to a named queue and receives a message ID. A consumer leases a batch for a visibility timeout; the message is hidden from other consumers, and the consumer acknowledges only after its side effect succeeds. A crash or timeout causes redelivery, so the broker exposes an opaque receipt handle and delivery count. Messages that repeatedly fail go to a dead-letter queue for isolation and diagnosis.

The first scaling bottleneck is durable writes. A per-message fsync cannot sustain the target, so each broker appends many messages to a WAL and group-commits them on a short interval. Partitioning distributes queues and producers across brokers, while replication and a controller provide failover. Consumers rebalance partition ownership after a broker change and resume from the last durable state.

The second bottleneck is lease expiry. At high throughput, millions of messages can be in flight. Store expiry timestamps in a time-ordered index and scan only the due prefix; atomically remove the lease and requeue or dead-letter the message. Preserve FIFO only within a required message group. Across the whole design, at-least-once delivery is the honest guarantee: duplicate deliveries are expected, and exactly-once business effects require idempotency keys or a transaction at the consumer.

45-minute interview approach

Use this agenda to make the delivery semantics and failure model explicit before optimizing the broker:

• 0-5 minutes — clarify the prompt: Confirm queue versus replayable stream, pull versus push delivery, message size, retention, ordering scope, visibility timeout, acknowledgement semantics, and whether a DLQ is required.
• 5-10 minutes — requirements and estimates: State 1M messages/sec, 100ms visibility target, 99.99% availability, no loss on a broker failure, 30-second illustrative leases, and the fact that 30 seconds of backlog can mean about 30M in-flight messages.
• 10-15 minutes — entities and APIs: Define Queue, Message, Consumer, and DeadLetterQueue. Sketch send, receive, delete/ack, and visibility-extension APIs, including receipt handles and delivery counts.
• 15-25 minutes — baseline architecture and critical flows: Draw the broker, in-memory queue, WAL, consumer path, visibility tracker, redelivery scanner, and DLQ. Walk through publish, receive, acknowledge, crash/redelivery, and restart recovery.
• 25-35 minutes — choose the deep dive: Prioritize group-commit and partitioning for throughput, sorted lease expiry for visibility, FIFO group IDs for ordering, or replication and leader election for broker failure. Compare the naive design with the selected evolution.
• 35-41 minutes — reliability, security, and operations: Cover acks, ISR/quorum health, WAL replay, consumer rebalances, poison messages, idempotency, access control, encryption, quotas, lag, lease age, and DLQ monitoring.
• 41-45 minutes — trade-offs and close: State where duplicates can occur, what the queue does not guarantee, why Kafka would be a different choice, and how the design changes for strict global ordering or multi-region durability.

Core Entities

• Queue: Named channel with configuration including visibility timeout, retention period, max message size, and an optional dead-letter queue reference.
• Message: Payload unit with a unique ID, body (opaque bytes), user-defined attributes, delivery count, and a visibility deadline timestamp.
• Consumer: Client that polls a queue and holds an opaque receipt_handle token while processing; identified by consumer_group_id.
• DeadLetterQueue (DLQ): A standard queue that receives any message exceeding its source queue's max_delivery_count.

Full schema is deferred to the deep dives. The critical relationship: a Message belongs to exactly one Queue, and a DLQ is simply another Queue with a source queue pointer.

API Design

This system exposes an SDK-style API. The calling application links against a client library that manages connection pooling, retries, and serialization.

FR 1 - Producer publishes a message:

send_message(
  queue_url: string,
  body: bytes,
  delay_seconds?: int = 0,
  message_group_id?: string
) -> { message_id: string }

delay_seconds defers visibility to consumers by the specified number of seconds. Use it for debounce patterns or scheduled jobs without a separate scheduler service.

FR 2 - Consumer receives messages:

receive_messages(
  queue_url: string,
  max_messages: int,         // 1-10
  visibility_timeout: int    // seconds, up to 43200
) -> [{ message_id, body, attributes, receipt_handle, delivery_count }]

Batch up to 10 messages per call to amortize network round-trips. The receipt_handle is an opaque token the consumer presents to delete or extend the message's visibility window. Return delivery_count so consumers can detect redeliveries and apply idempotency logic without maintaining separate delivery state.

FR 3 - Consumer acknowledges a message:

delete_message(
  queue_url: string,
  receipt_handle: string
) -> void

Deletion is the acknowledgement. A message is only removed from the queue when the consumer explicitly calls delete_message with a valid receipt handle.

FR 4 - Consumer extends visibility for long-running jobs:

change_visibility(
  queue_url: string,
  receipt_handle: string,
  new_timeout: int           // seconds
) -> void

Use change_visibility as a heartbeat: call it periodically when processing takes longer than the initial visibility timeout to prevent redelivery. This is the correct pattern for long-running jobs rather than setting an artificially high initial timeout.

High-Level Design and Critical Flows

1. Producer publishes to a named queue

Solving: The basic write path. A producer sends a message and the broker stores it for future retrieval.

Components:

• Producer Client: Application code calling send_message. Connects to the broker over TCP.
• Broker: Single process. Accepts messages, assigns a unique ID, and appends to a named in-memory queue.
• In-Memory Queue: A FIFO data structure per named queue. Fast but not yet durable.

Request walkthrough:

1. Producer calls send_message("orders", body).
2. Broker receives the message and assigns a UUID.
3. Broker appends the message to the target queue's in-memory FIFO structure.
4. Broker returns { message_id } to the producer.

This diagram shows the write path only. Consumer delivery and visibility timeout mechanics come next. Notice we start deliberately simple: one broker, in-memory only, no durability. This is the baseline that everything else evolves from.

2. Consumer receives and acknowledges messages with visibility timeout

Solving: The consumer pull path and the core visibility timeout mechanic. When a consumer receives a message, that message must become invisible to other consumers until either acknowledged or the timeout expires.

Components:

• Consumer Client: Application code calling receive_messages. Long-polls the broker.
• Visibility Tracker: An in-memory map of receipt_handle -> (message_id, expiry_timestamp).
• Receipt Handle: An opaque token encoding the consumer's lease on the message.

Request walkthrough: