Dead-letter queue

Deep dive

How it works

In: a delivery attempt result (ack, retry, reject, timeout) per message · Out: the message either acked, redelivered later, or parked in the DLQ with a reason · State: per message receives and visible_at · Cost: O(log n) per receive or settle; O(1) to dead-letter

Per message the broker keeps receives (delivery count) and visible_at.

1. Receive: pop a visible message. If receives >= max_receives, move it to the DLQ with reason MaxReceives and take the next one. Otherwise receives += 1, hide it until now + visibility_timeout, hand it out.
2. Ack: delete it.
3. Retry (transient error): hide it for a backoff delay; it comes back later with its count intact.
4. Reject (permanent error, e.g. it doesn't parse): dead-letter it at once, skipping the remaining attempts.
5. Timeout (consumer crashed or stalled): the message reappears and the delivery counts as a failure.
6. Redrive: after the fix, move dead letters back to the source queue with the count reset, rate-limited.

send ─► [ ready ] ──receive──► consumer ──ack──► gone
           ▲  ▲                   │ │
           │  └── backoff/timeout ┘ └─reject or receives > max──► [ DLQ ] + reason, source, time
           └──────────────── redrive (after fix, rate-limited) ◄───────┘

Log-based systems (partitioned commit log) have no per-message ack: a consumer can only commit its offset past a record. Skipping means publishing the record to a dead-letter topic (often via retry topics with growing delays) and then committing; the partition keeps flowing but per-key order breaks.

Code

In-memory broker core with visibility timeouts, backoff, permanent rejects and redrive. Time is passed in (ms) to keep it deterministic. Timers live in a min-heap with lazy deletion, so acks never search the heap.

use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashMap, VecDeque};

#[derive(Clone, Debug)]
pub struct Msg { pub id: u64, pub body: Vec<u8>, pub receives: u32, pub enqueued_ms: u64 }

#[derive(Debug, PartialEq)]
pub enum Reason { MaxReceives, Rejected(String) }

#[derive(Debug)]
pub struct DeadLetter { pub msg: Msg, pub reason: Reason, pub dead_ms: u64 }

pub enum Outcome { Ack, Retry, Reject(String) } // Reject = permanent error, skip retries

pub struct Queue {
    ready: VecDeque<Msg>,
    invisible: HashMap<u64, (Msg, u64)>,        // id -> (msg, visible again at)
    timers: BinaryHeap<Reverse<(u64, u64)>>,    // (visible_at, id); stale entries skipped
    pub dlq: VecDeque<DeadLetter>,
    max_receives: u32, visibility_ms: u64, backoff_ms: u64, next_id: u64,
}

impl Queue {
    pub fn new(max_receives: u32, visibility_ms: u64, backoff_ms: u64) -> Self {
        Queue { ready: VecDeque::new(), invisible: HashMap::new(), timers: BinaryHeap::new(),
                dlq: VecDeque::new(), max_receives, visibility_ms, backoff_ms, next_id: 0 }
    }

    pub fn send(&mut self, body: &[u8], now: u64) -> u64 {
        self.next_id += 1;
        self.ready.push_back(Msg { id: self.next_id, body: body.to_vec(), receives: 0, enqueued_ms: now });
        self.next_id
    }

    fn hide(&mut self, msg: Msg, until: u64) {
        self.timers.push(Reverse((until, msg.id)));
        self.invisible.insert(msg.id, (msg, until));
    }

    /// Timed-out and backed-off messages become visible again; one past the limit goes to the DLQ.
    pub fn receive(&mut self, now: u64) -> Option<Msg> {
        while let Some(&Reverse((at, id))) = self.timers.peek() {
            if at > now { break; }
            self.timers.pop();
            // Only act if this timer is still current (not acked, not re-hidden later).
            if self.invisible.get(&id).map_or(false, |(_, u)| *u == at) {
                let (m, _) = self.invisible.remove(&id).unwrap();
                self.ready.push_back(m);
            }
        }
        while let Some(mut m) = self.ready.pop_front() {
            if m.receives >= self.max_receives {
                self.dlq.push_back(DeadLetter { msg: m, reason: Reason::MaxReceives, dead_ms: now });
                continue;
            }
            m.receives += 1;
            self.hide(m.clone(), now + self.visibility_ms); // crash = implicit failure after timeout
            return Some(m);
        }
        None
    }

    pub fn settle(&mut self, id: u64, outcome: Outcome, now: u64) {
        let Some((m, _)) = self.invisible.remove(&id) else { return }; // late ack after timeout: ignored
        match outcome {
            Outcome::Ack => {}
            Outcome::Retry => { // exponential backoff, capped at 2^10 * base
                let delay = self.backoff_ms << (m.receives - 1).min(10);
                self.hide(m, now + delay);
            }
            Outcome::Reject(why) => self.dlq.push_back(DeadLetter { msg: m, reason: Reason::Rejected(why), dead_ms: now }),
        }
    }

    /// Move up to `max` dead letters back after a fix; the receive count restarts.
    pub fn redrive(&mut self, max: usize) -> usize {
        let n = max.min(self.dlq.len());
        for d in self.dlq.drain(..n) {
            self.ready.push_back(Msg { receives: 0, ..d.msg });
        }
        n
    }
}

A real broker adds jitter to the backoff (exponential backoff with jitter), persists receives with the message, and writes the dead letter durably before deleting the original.

Complexity and constants

• Receive and settle: O(log n) heap push/pop plus O(1) hash map work; dead-lettering is O(1). Lazy deletion leaves at most one stale heap entry per retry or ack, removed when it expires.
• Cost of a poison message before it is parked: up to max_receives × (processing time, or the visibility timeout if it crashes the consumer). With 10 receives and a 30 s timeout that is about 5 minutes of a worker slot and 10 receive calls.
• Durable brokers pay per attempt: the receive count is a state change, and the move to the DLQ is a write to the DLQ plus a delete at the source, which must be atomic or ordered write-then-delete (duplicate in the DLQ rather than loss).
• Dead letters carry the full payload plus metadata; size the DLQ's retention and storage for the worst incident (a bad deploy can dead-letter everything for hours), not the average.

Efficiency

• Cost: a poison message costs up to max_receives × (processing time, or the visibility timeout when it crashes the consumer) of a worker slot before it is parked: with 10 receives and a 30 s timeout, about 5 minutes and 10 receive calls (see above). Parking is one DLQ write plus one source delete. Bound: wasted worker time and broker round trips, not CPU.
• Levers:
  • reject permanent errors (parse, validation) at once — saves max_receives − 1 attempts — malformed inputs
  • order the move write-then-delete — no distributed transaction; a duplicate in the DLQ instead of loss — durable brokers
  • rate-limit redrive (SQS MaxNumberOfMessagesPerSecond) — recovery does not re-trigger the outage — after a fix
  • lazy deletion in the timer heap — at most one stale entry per retry or ack — in-memory brokers
  • size DLQ retention and storage for the worst incident — a bad deploy can park everything for hours — capacity planning
• Naive → standard → state of the art:
  • retry forever · one poison message holds a worker slot indefinitely
  • delivery counter plus DLQ after N receives · bounded at N attempts
  • classify errors, reject permanent ones at once, rate-limited redrive · 1 attempt for permanent errors

Implementation notes

• Classify errors in the consumer. Parse and validation errors are permanent: reject at once and save max_receives − 1 wasted attempts. Timeouts, 5xx and throttling are transient: retry with backoff. Unknown errors: retry, and let the counter decide.
• Record why. Store the source queue, reason, error type, a truncated stack trace, receive count and first/last failure time as headers next to the raw bytes. RabbitMQ writes an x-death header and compresses it by {queue, reason} so repeated cycles don't grow it unboundedly; Azure Service Bus recommends the exception type in DeadLetterReason.
• Keep the raw payload. Deserialization failures are a top cause; a DLQ that stores only decoded objects can't hold them.
• Visibility timeout > p99 processing time. Otherwise slow successes are redelivered, double-processed, and their counts climb into the DLQ. Extend the lease (heartbeat) for long jobs.
• Alarm on DLQ depth > 0 (SQS: ApproximateNumberOfMessagesVisible on the DLQ) and on dead-letter rate, per reason.
• Rate-limit redrive. SQS StartMessageMoveTask takes MaxNumberOfMessagesPerSecond; redriving a million messages at full speed into a just-recovered service knocks it over again. Consumers must be idempotent (idempotency keys, event deduplication) because redriven messages may have partly succeeded before.
• Per-key order in logs: once a key has a record in the DLQ, divert later records with the same key there too (a "parked keys" set) so they don't overtake it; release them together on redrive.
• Retention: for SQS standard queues a message keeps its original enqueue timestamp in the DLQ, so set the DLQ's retention (max 14 days) longer than the source's.

Pitfalls

• maxReceiveCount = 1: one network blip or one redelivery after a consumer restart sends a good message to the DLQ.
• Redrive before the fix ships: the messages loop straight back into the DLQ.
• DLQ consumer that throws on the same bad payload: dead letters need a raw, never-failing reader.
• RabbitMQ dead-lettering is at-most-once by default: if the target queue can't accept the message it is lost. Quorum queues offer at-least-once dead-lettering with internal publisher confirms.
• Pub/Sub counts delivery attempts approximately and only when the dead-letter topic is configured with the right IAM permissions; a message can arrive more often than the limit.
• FIFO queues: moving one message out breaks the order; AWS advises against a DLQ when order must hold exactly.
• Kafka Connect only writes to its DLQ topic with errors.tolerance=all; the default none fails the task instead.
• Sharing one DLQ across many sources without a source field makes redrive ambiguous.

Variants and alternatives

In production

Amazon SQS redrive policy and DLQ redrive, RabbitMQ dead-letter exchanges (x-dead-letter-exchange, reasons rejected, expired, maxlen, delivery_limit), Google Pub/Sub dead-letter topics, Azure Service Bus $deadletterqueue subqueues, Kafka Connect errors.deadletterqueue.topic.name, Spring Kafka DeadLetterPublishingRecoverer, Sidekiq dead set, AWS Lambda dead-letter queues for asynchronous invocations.

Implementations

Sources

• Gregor Hohpe, Bobby Woolf, Enterprise Integration Patterns, Addison-Wesley 2003, "Dead Letter Channel". pattern
• AWS, Using dead-letter queues in Amazon SQS. docs · StartMessageMoveTask
• RabbitMQ, Dead Letter Exchanges and Quorum Queues (delivery limit). dlx · quorum queues
• Google Cloud, Dead-letter topics (Pub/Sub). docs
• Microsoft, Service Bus dead-letter queues. docs
• Apache Kafka, Kafka Connect configs (errors.tolerance, errors.deadletterqueue.*). docs