Retry Semantics, Dead-Letter Queues & Idempotency Keys for Payroll Runs

A retried payroll message is either a duplicate about to overpay an employee or a permanent failure about to loop forever — and the only thing standing between those two outcomes is whether the retry layer classifies the failure correctly before it acts. This page specifies the retry, dead-letter, and idempotency layer that sits underneath the Async Batch Processing topic within the Multi-Format Payroll Data Ingestion & Normalization framework: how to tell a transient failure from a permanent one, back off with jitter inside a hard budget, route exhausted or poison messages to a dead-letter queue with a machine-readable reason code, and re-drive them safely once the root cause is fixed.

Problem Framing

Payroll runs sit on top of message transports — a durable queue, a stream, a task broker — that guarantee at-least-once delivery, never exactly-once. That guarantee is the correct tradeoff for throughput, but it means every consumer of a payroll message must manufacture its own exactly-once effect, and three shortcuts routinely break that guarantee in production:

• Retrying without classifying the failure. A schema-validation error and a database timeout look identical to a bare except Exception: retry() block, so a permanently malformed record retries forever, burning the retry budget meant for real transient failures and delaying the dead-letter escalation that should have paged a human immediately.
• Deriving the idempotency key from the retry itself. A key built from datetime.now() or uuid4() is unique per attempt by construction, which defeats the entire point of an idempotency key: every retry of the same underlying disbursement looks like a brand-new one, ON CONFLICT DO NOTHING never finds a prior conflict, and the employee is paid twice.
• Retrying on a fixed interval with no jitter. When an upstream outage recovers, every stalled consumer wakes on the same clock tick and retries in lockstep, reproducing the outage against the payroll ledger the instant it comes back online — a self-inflicted retry storm.

The fix is a bounded state machine, not an unbounded loop: classify first, back off with jitter inside a hard budget, and dead-letter deterministically the moment the budget is exhausted or the failure is permanent. Backoff for attempt $n$ (zero-indexed) uses full jitter over an exponential ceiling capped at $T_{\text{cap}}$:

$T_n = \text{Uniform}\bigl(0,\ \min(T_{\text{cap}},\ b \cdot 2^{n})\bigr)$

where $b$ is the base delay and $T_{\text{cap}}$ bounds runaway growth so attempt 20 does not sleep for a day. The uniform draw — not a fixed midpoint, not a fixed multiplier — is what desynchronizes competing consumers; a jittered ceiling without the uniform draw is still a thundering herd waiting to happen.

Prerequisites & Data Requirements

The retry layer operates on a message envelope, not the raw payroll record — the envelope carries the retry and dead-letter metadata that the record itself has no business knowing about.

Two preconditions hold outside the function signatures below:

1. The idempotency key is computed once, at ingestion, and carried through every retry. It is never recomputed at retry time — recomputing it against the current record state, rather than the immutable natural key, reintroduces exactly the non-determinism the key exists to eliminate.
2. Classification happens before the budget is consulted. An exception that is actually permanent must never consume retry budget it doesn’t need; misclassifying it as transient only delays the same guaranteed failure while starving the budget meant for genuinely recoverable errors.

Step-by-Step Implementation

Step 1 — Model the envelope and the failure taxonomy. A two-value enum keeps classification exhaustive and auditable, and the envelope carries every field the retry state machine needs without touching the payroll record itself.

from dataclasses import dataclass
from datetime import datetime
from decimal import Decimal
from enum import Enum
from typing import Optional
import hashlib
import logging

logger = logging.getLogger("payroll.retry")


class FailureClass(str, Enum):
    TRANSIENT = "transient"
    PERMANENT = "permanent"


@dataclass
class RetryEnvelope:
    message_id: str
    idempotency_key: str
    employee_id: str
    pay_period_start: str  # ISO date, part of the natural key
    source_run_id: str
    gross_pay: Decimal
    attempt: int = 0
    max_attempts: int = 6
    reason_code: Optional[str] = None
    status: str = "pending"


def derive_idempotency_key(
    employee_id: str, pay_period_start: str, source_run_id: str
) -> str:
    """Deterministic key from the natural key. Never time.time() or uuid4()."""
    natural_key = f"{employee_id}|{pay_period_start}|{source_run_id}"
    return hashlib.sha256(natural_key.encode("utf-8")).hexdigest()


# derive_idempotency_key("E-44817", "2026-07-06", "run-8831")
# -> same 64-char hex string every time, regardless of attempt count

Step 2 — Classify the failure before touching the budget. Route by exception type first, then by an explicit reason_code supplied by the caller, and fail closed: an exception type the classifier has never seen is treated as permanent rather than silently retried. A message that crashes deserialization itself — a poison message — never reaches this function at all; wrap the deserialization step in its own try/except and dead-letter it immediately with reason_code="poison_message", since retrying a payload the consumer cannot even parse only reproduces the crash.

TRANSIENT_EXCEPTIONS = (TimeoutError, ConnectionError)
PERMANENT_REASON_CODES = {
    "schema_validation_failed",
    "duplicate_natural_key",
    "statutory_cap_breach",
    "poison_message",
}


def classify_failure(exc: Exception, reason_code: str) -> FailureClass:
    """Route by exception type first, then by explicit reason_code."""
    if reason_code in PERMANENT_REASON_CODES:
        return FailureClass.PERMANENT
    if isinstance(exc, TRANSIENT_EXCEPTIONS):
        return FailureClass.TRANSIENT
    return FailureClass.PERMANENT  # unknown exceptions fail closed, not open


# classify_failure(TimeoutError(), "upstream_timeout") -> FailureClass.TRANSIENT
# classify_failure(ValueError(), "schema_validation_failed") -> FailureClass.PERMANENT

Step 3 — Compute bounded backoff with full jitter. The delay is a uniform draw over [0, ceiling], not the ceiling itself — the draw, not the exponential growth alone, is what desynchronizes competing consumers after a shared outage.

import random
from decimal import Decimal

BASE_SECONDS = Decimal("2")
CAP_SECONDS = Decimal("120")


def compute_backoff_seconds(attempt: int) -> Decimal:
    """Full-jitter bounded exponential backoff: Uniform(0, min(cap, base * 2**n))."""
    ceiling = min(CAP_SECONDS, BASE_SECONDS * (Decimal(2) ** attempt))
    jitter = Decimal(str(random.uniform(0, float(ceiling))))
    return jitter.quantize(Decimal("0.01"))


# compute_backoff_seconds(0) -> some Decimal in [0.00, 2.00]
# compute_backoff_seconds(6) -> some Decimal in [0.00, 120.00], capped by CAP_SECONDS

Step 4 — Enforce the retry budget and route to the dead-letter queue. A permanent failure dead-letters on attempt 0, spending no budget at all; a transient failure only dead-letters once attempt >= max_attempts.

from dataclasses import dataclass
from datetime import datetime, timezone
from typing import Optional, Tuple


@dataclass
class DeadLetter:
    envelope: RetryEnvelope
    reason_code: str
    failure_class: FailureClass
    last_error: str
    dead_lettered_at: datetime


def route_or_retry(
    envelope: RetryEnvelope, exc: Exception, reason_code: str
) -> Tuple[str, Optional[Decimal]]:
    """Decide retry vs. dead-letter. Returns (action, backoff_seconds)."""
    failure = classify_failure(exc, reason_code)

    if failure is FailureClass.PERMANENT:
        logger.warning(
            "event=dead_letter emp=%s key=%s reason=%s attempt=%s",
            envelope.employee_id, envelope.idempotency_key, reason_code, envelope.attempt,
        )
        return "dead_letter", None

    if envelope.attempt >= envelope.max_attempts:
        logger.warning(
            "event=dead_letter emp=%s key=%s reason=%s attempt=%s budget=%s",
            envelope.employee_id, envelope.idempotency_key,
            "retry_budget_exhausted", envelope.attempt, envelope.max_attempts,
        )
        return "dead_letter", None

    backoff = compute_backoff_seconds(envelope.attempt)
    envelope.attempt += 1
    logger.info(
        "event=retry_scheduled emp=%s key=%s attempt=%s backoff_s=%s",
        envelope.employee_id, envelope.idempotency_key, envelope.attempt, backoff,
    )
    return "retry", backoff


# route_or_retry(envelope, TimeoutError(), "upstream_timeout")
# -> ("retry", Decimal("1.34"))  when envelope.attempt < envelope.max_attempts
# -> ("dead_letter", None)       once envelope.attempt >= envelope.max_attempts

Step 5 — Disburse idempotently, then support a manual re-drive. The upsert is the exactly-once boundary on top of an at-least-once substrate: ON CONFLICT DO NOTHING keyed on idempotency_key makes a repeated delivery a safe no-op instead of a second paycheck.

async def disburse_idempotent(conn, envelope: RetryEnvelope) -> bool:
    """Exactly-once disbursement on an at-least-once substrate."""
    result = await conn.execute(
        """
        INSERT INTO disbursements
            (idempotency_key, employee_id, pay_period_start, source_run_id,
             gross_pay, posted_at)
        VALUES ($1, $2, $3, $4, $5, now())
        ON CONFLICT (idempotency_key) DO NOTHING
        """,
        envelope.idempotency_key, envelope.employee_id, envelope.pay_period_start,
        envelope.source_run_id, envelope.gross_pay,
    )
    inserted = result.split()[-1] == "1"  # asyncpg-style status tag
    logger.info(
        "event=disburse emp=%s key=%s inserted=%s gross=%s",
        envelope.employee_id, envelope.idempotency_key, inserted, envelope.gross_pay,
    )
    return inserted


async def redrive_dead_letter(conn, dead_letter: DeadLetter) -> bool:
    """Manual re-drive after the root cause is fixed. Resets the retry budget."""
    dead_letter.envelope.attempt = 0
    dead_letter.envelope.status = "pending"
    logger.info(
        "event=redrive emp=%s key=%s prior_reason=%s",
        dead_letter.envelope.employee_id,
        dead_letter.envelope.idempotency_key,
        dead_letter.reason_code,
    )
    return await disburse_idempotent(conn, dead_letter.envelope)


# First delivery:  disburse_idempotent(conn, envelope) -> True  (row inserted)
# Re-delivery with the same idempotency_key: -> False (ON CONFLICT DO NOTHING fired)

Verification

Confirm the state machine’s correctness with the boundary cases specific to retry and dead-letter behavior, not just happy-path disbursement:

1. Idempotency replay produces no double post. Call disburse_idempotent twice with an identical envelope.idempotency_key. Assert the first call returns True, the second returns False, and the disbursements row count for that key is exactly 1.
2. Budget exhaustion routes to the dead-letter queue. Set max_attempts=3 and feed three consecutive TimeoutError failures through route_or_retry. Assert the first three calls return "retry" and the fourth returns ("dead_letter", None) with reason_code == "retry_budget_exhausted".
3. Jitter stays within its bounds and is not deterministic. Call compute_backoff_seconds(5) 1,000 times. Assert every result lies in [Decimal("0.00"), min(CAP_SECONDS, BASE_SECONDS * 2**5)], and assert the returned values are not all equal — a constant result across calls means the uniform draw was dropped somewhere and the “jitter” is a fixed delay in disguise.
4. Permanent failures short-circuit the budget. Call route_or_retry with reason_code="schema_validation_failed" on an envelope where attempt == 0. Assert it dead-letters immediately without incrementing attempt — a permanent failure must never be retried even once.
5. Re-drive resets the budget and remains idempotent. After redrive_dead_letter, assert envelope.attempt == 0. If the underlying row already posted through a separate path before the re-drive ran, assert disburse_idempotent still returns False rather than raising — a re-drive of an already-settled disbursement is a safe no-op, not an error.

Failure Modes

• Idempotency key derived from time or a random UUID. Root cause: the key is built from datetime.now(), time.time(), or uuid4() instead of the natural key, so every retry attempt generates a distinct key by construction. Remediation: derive the key purely from (employee_id, pay_period_start, source_run_id) as in derive_idempotency_key, compute it once at ingestion, and carry it unchanged through every retry and re-drive.
• Unbounded retry budget on a misclassified permanent failure. Root cause: the classifier treats an unrecognized exception as transient by default (“fail open”), so a structurally broken record retries indefinitely and never reaches the dead-letter queue where a human would see it. Remediation: fail closed — unknown exception types classify as PERMANENT, as in classify_failure above — and enforce a hard max_attempts ceiling as a second, independent backstop against any classifier gap.
• Retry storms from unjittered, synchronized backoff. Root cause: every consumer computes the same fixed delay for a given attempt number, so a shared outage produces a shared recovery-time retry spike that re-triggers the outage against the payroll ledger. Remediation: apply full jitter — a uniform draw over [0, ceiling], not the ceiling itself — and keep the concurrent-write ceiling at the same semaphore bound used for async batch processing’s fetches and upserts, so a retry wave still cannot exceed the connection-pool limit.

Frequently Asked Questions

Related

• Async Batch Processing — the parent topic whose semaphore-gated fetch/upsert model this retry and dead-letter layer plugs into.
• Async Batch Processing for Large Payroll Files — streaming and checkpointing at multi-gigabyte scale, built on the same bounded-concurrency pattern.
• Fallback Routing Strategies — the framework-level dead-letter hierarchy this queue’s reason codes plug into.
• Manual-Review Queue Escalation SLAs — the escalation clock that starts the moment a message lands in the dead-letter queue.