Designing Idempotent Retries for Distributed Queues

Every message queue we operate at Meridian will, sooner or later, deliver the same message twice. This is not a bug we intend to fix — it is a property of the universe we have chosen to inhabit. At-least-once delivery is the honest contract of distributed messaging: the broker promises that your message will arrive, and in exchange it reserves the right to hand it to you again whenever a network partition, a consumer crash, or an ill-timed deploy makes it unsure whether the first attempt landed. The question was never whether our consumers would see duplicates. The question was what they would do when they did.

For our first two years, the answer was “mostly nothing bad, occasionally something terrible.” A duplicate invoice.finalized event once charged a customer twice. A replayed fleet.scale command doubled a Kubernetes node pool during a traffic spike, which was accidentally helpful, and then doubled it again during the retry storm that followed, which was not. Each incident produced a bespoke fix: a dedupe check here, a conditional write there. What we lacked was a shared discipline — a single, boring, well-tested answer to the duplicate-delivery problem that every team could adopt without thinking.

The discipline we settled on is idempotency keys with a durable outcome store. Every side-effecting operation in the system is named by a key that is deterministic for the logical operation, not the delivery attempt. Charging invoice inv_8842 gets the key charge:inv_8842 no matter how many times the message is delivered, requeued, or replayed from a dead-letter archive. Before performing the work, the consumer claims the key; after performing it, the consumer records the outcome against the key. A second delivery finds the recorded outcome and simply returns it, performing no work at all. The duplicate becomes a cache hit.

The subtle part is the gap between “claimed” and “recorded.” If a consumer claims a key, begins the work, and dies, a naive implementation leaves the key locked forever — or worse, releases it and lets a retry re-run a half-completed side effect. We close this gap with a lease: a claim carries an expiry, and the recorded outcome is written in the same transaction as the side effect wherever the datastore allows it. Where it doesn’t — third-party payment APIs, for instance — we lean on the provider’s own idempotency support and store their key alongside ours, so a recovery pass can ask the provider what actually happened rather than guessing.

func (s *Store) Execute(ctx context.Context, key string, op Op) (Result, error) {
	claim, err := s.Claim(ctx, key, 30*time.Second) // lease, not lock
	if errors.Is(err, ErrAlreadyDone) {
		return claim.Result, nil  // duplicate delivery: replay outcome
	}
	if err != nil {
		return Result{}, fmt.Errorf("claim %s: %w", key, err)
	}

	res, err := op(ctx)             // the actual side effect
	if err != nil {
		s.Release(ctx, claim)        // safe: op is transactional
		return Result{}, err
	}
	return res, s.Record(ctx, claim, res) // outcome survives restarts
}

Rolling this out taught us that correctness was the easy half; the hard half was cost. Outcome records are small, but at our volume they accumulate fast, and every consumer now performs an extra read on the hot path. We tiered the store — a seven-day window in Redis backed by a ninety-day archive in Postgres — and measured the overhead across our three busiest pipelines before committing. The numbers made the case better than any design document could.

The single-digit-millisecond tax bought us something harder to quantify: retries stopped being scary. Teams that once wrapped every consumer in defensive, one-off dedupe logic now retry aggressively — exponential backoff with jitter, generous attempt budgets, automatic replay from dead-letter queues — because the worst case of an unnecessary retry is a cheap key lookup. Incident recovery changed character too. During a recent regional failover we replayed six hours of the billing stream wholesale, something we would never have dared before, and watched 1.4 million messages resolve to outcome-store hits without a single doubled charge.

If you take one thing from our experience, take this: make idempotency a platform primitive, not a per-team virtue. A library that every consumer imports, a key-naming convention enforced in code review, and an outcome store operated centrally will do more for your reliability than any amount of exhortation to “handle duplicates carefully.” Distributed systems will keep delivering your messages twice. The goal is to build a system where that fact is no longer interesting.