Design a Delayed Payment Scheduling System

Understanding the Problem

Functional Requirements

1. Users should be able to create, query, and cancel scheduled payments.
2. The system should execute each payment at its due time, with retries and backoff on failure.
3. A payment must be charged at most once against the gateway, no matter what crashes.
4. Every attempt is audited in full; nothing terminal disappears silently.

Below the line (out of scope):

• The gateway's internals, and FX.
• Subscription billing logic. This system is the engine such logic would schedule onto: a subscription service creates rows here, keeping this engine single-shot.

Non-Functional Requirements

1. A payment executes at most once against the gateway no matter what crashes (the money-side requirement) and at least once gets attempted (the product-side requirement); the two are reconciled to exactly-once effect via gateway idempotency keys.
2. Amounts are integers in minor units (cents), never floats and never DECIMAL.
3. Trigger lateness p99 under 60 seconds, measured due_time to first attempt.
4. API availability 99.95%.

The Set Up

Defining the Core Entities

• Scheduled payment: who pays, how much, when, with a lifecycle (PENDING → PROCESSING → COMPLETED / FAILED / CANCELLED).
• Execution attempt: one try against the gateway, with its outcome; a payment has many, and the audit trail is their history.
• Due partition: the unit of "what is due now", a time bucket the schedulers sweep.
• Gateway: the external processor, reachable only through idempotency keys.
• The sentence to plant early: the database is the schedule. There is no separate queue holding truth; the payments table, indexed by due time, is what the schedulers read, and everything else is an optimization over that read.

API or System Interface

POST   /v1/scheduled-payments               // payer = authenticated actor
  Header: Idempotency-Key: key              // keys scoped (actor, key)
  { "payee": P, "amount": 2500, "dueAt": "2026-09-01T00:00:00Z" }
  → 201 { paymentId, status: PENDING }
  → 409 same key, different body
  // validated: amount > 0 and ≤ cap; dueAt in the future and ≤ horizon (1y)

GET    /v1/scheduled-payments/{id}          // { status, dueAt, attempts: [...] }
GET    /v1/scheduled-payments?status=&cursor=
DELETE /v1/scheduled-payments/{id}
  → 200 CANCELLED           // won the race
  → 409 ALREADY_PROCESSING  // lost it: too late

• Cancel is a compare-and-swap (CAS, an atomic compare-then-update) on status PENDING → CANCELLED. If execution already claimed the row, cancel honestly loses with 409 rather than pretending. The race is decided by one row's state, nowhere else (deep dive 5).
• All times are accepted and stored in UTC; presentation converts.

High-Level Design

1) Users should be able to create, query, and cancel scheduled payments

• Creating a payment is one insert with a scoped idempotency key: a unique index on (payer, key) dedupes retries, a retry with the same key is safe and returns 201 again, and the same key with a different body gets a 409.
• The Postgres payments table, partitioned by due day and indexed by (status, due_time), is the source of truth AND the schedule itself. Everything downstream reads it.
• Query is a read on the row plus its attempts; the user's list view rides an index on (payer, created_at).
• Cancel is the CAS from the API section: both cancel and the execution claim mutate the same status column of the same row, so there is no window where both win.

2) The system should execute each payment at its due time

• Scheduler pollers sweep the current partition every few seconds and claim batches of due rows (due_time ≤ now) with a conditional update: FOR UPDATE SKIP LOCKED, stamping status PROCESSING, a 2-minute lease, and attempt+1.
• SKIP LOCKED means concurrent pollers each grab a disjoint batch without blocking: rows another poller has locked are skipped, not waited on. N pollers scale the sweep with no leader election and no distributed lock.
• Executor workers call the gateway with the payment's id as the gateway idempotency key, then record the outcome as an attempt row and CAS the payment's status to COMPLETED or a retryable FAILED.
• Day partitions keep the sweep index tiny: pollers only touch today's partition, so the hot index covers about 100M rows, not all history; old partitions age out to cold storage after settlement.

3) Failures retry with backoff, and exhausted payments park for a human

• The lease bounds crash damage: a worker that dies mid-execution leaves its rows PROCESSING with an expiring lease. A reaper CASes expired leases back to PENDING with the attempt count intact, and the next sweep retries them. A payment is never lost and never concurrently executed: at any instant exactly one holder has an unexpired lease, or the row is PENDING.
• Retry policy: exponential backoff with jitter (1m, 5m, 30m, 2h, 12h), a budget of about 5 for retryable failures (network, 5xx, rate limit).
• Terminal failures (card declined, account closed) skip retries: straight to FAILED plus a notification.
• An exhausted budget parks the payment in a Dead Letter Queue (DLQ, a holding pen for work that needs a human) with its full attempt history; a human tool re-drives or refunds. Nothing silently disappears, which is the audit requirement doing its job.

4) Every attempt is audited, and payers hear about outcomes

• Every status change and attempt flows out via Change Data Capture (CDC) to Kafka, feeding the audit trail and the notification service. These consumers are derived; the table stays the only truth.
• The audit requirement is also satisfied by construction below the stream: every attempt is a row (payment_id, attempt, started_at, gateway_key, outcome, gateway_ref).
• A daily reconciliation diffs the gateway's settlement report against the attempts table, in both directions. A charge with no COMPLETED row is our miss: repair status from gateway truth. A COMPLETED row with no charge is the gateway's miss or our bug: page. This closes the loop that per-request idempotency alone cannot, catching the failures neither side saw.

Potential Deep Dives

1) Why poll a database instead of using a delay queue?

• There are four standard ways to trigger future work, and the interviewer will expect you to have rejected three of them for stated reasons, not by default.

2) How is a due payment triggered exactly once, across concurrent pollers and crashing workers?

• The claim is the heart of the design: it must hand each due row to exactly one worker, survive that worker dying, and leave an audit trail of every try.

-- each poller, every ~5s, on the live partition:
UPDATE payments p SET
    status = 'PROCESSING',
    lease_until = now() + interval '2 min',
    attempt = attempt + 1
FROM (
  SELECT id FROM payments
  WHERE status = 'PENDING' AND due_time <= now()
  ORDER BY due_time
  LIMIT 100
  FOR UPDATE SKIP LOCKED
) due WHERE p.id = due.id
RETURNING p.*;

3) How do we make sure the gateway never charges twice?

• The external side effect is the one thing no transaction of ours can roll back, so every mechanism here exists to make retries collapse.

4) What breaks at midnight on the 1st of the month?

• Humans schedule for round times, so 00:00 on the 1st can hold 100x an average second. First, the data model that carries the design:

payments (
  id uuid pk, payer, payee
  amount_minor bigint        -- integer cents, never DECIMAL
  due_time timestamptz, due_day partition key
  status PENDING | PROCESSING | COMPLETED | FAILED | CANCELLED
  attempt int, lease_until
  idem_actor, idem_key unique (actor, key)
) PARTITION BY due_day
  INDEX (status, due_time)       -- the sweep index
  INDEX (payer, created_at)      -- user's list view

attempts ( payment_id, attempt pk, gateway_key, outcome, gateway_ref, at )

• What actually breaks at 100x: not the sweep (an index range read) and not the claim (batched row locks); the gateway's rate ceiling breaks first.
• Lever 1, smear: execute due payments over a window. The contract says "at due time"; delivery is due plus jitter within the lateness SLO, stated honestly.
• Lever 2, pace to the gateway's rate limit: the true bottleneck is the gateway's ceiling, not our sweep; the claim batches naturally form the pacing queue.
• The honest statement: a due-time spike converts throughput shortage into bounded, monitored lateness, never into drops or duplicates.
• Why Postgres: the claim needs multi-row transactional SKIP LOCKED semantics, and the schedule benefits from one strongly consistent table with real indexes. At 1.2K/s average this is one primary with partitioning, no exotics.

5) The races: cancel vs execute, zombie workers, edits

• Cancel vs execute: cancel is UPDATE ... SET status='CANCELLED' WHERE id=? AND status='PENDING'. If the claim got there first, the row is PROCESSING, cancel matches zero rows and returns 409 ALREADY_PROCESSING. If cancel got there first, the claim's inner SELECT no longer sees the row. Both orders are correct because both mutations are CAS on the same status column of the same row; there is no window where both win.
• If pushed on "user cancels at 11:59:59.9 for a midnight payment": two CAS mutations race on one status column. Cancel wins → row CANCELLED, the sweep never sees it. Claim wins → cancel returns 409, truthfully. There is no interleaving where both proceed, because neither mutation is a read-then-write.
• Zombie worker: the lease expires at T, the reaper flips the row to PENDING, a new claim executes with attempt N+1 and the same gateway key; the zombie finishes its stale call late. The gateway key collapses the charge to one regardless, and the zombie's outcome write is fenced: UPDATE attempts SET outcome=? WHERE payment_id=? AND attempt=N touches only its own attempt row, never the payment's status, which only the current attempt's owner CASes.
• Edit before due: not supported, by design; cancel (CAS-guarded) and re-create with a new key. One less mutable path through the money state machine. Say it as a choice, not a gap.

6) What happens when things die, and how do we operate it?

• Poller or executor crash: nothing is lost, the schedule is rows; leases expire, the reaper returns work, attempt counts survive.
• Gateway outage: circuit-break and stop claiming (leave rows PENDING rather than churning attempts); on recovery, drain the backlog oldest-first, paced to the gateway's rate limit. Backlog size and oldest-due age are the outage dashboards.
• Database failover: the schedule is on the primary with synchronous replication; a failover pauses execution for seconds. Claims in flight either committed (the lease holds) or did not (rows still PENDING); the state machine has no torn middle.
• SLOs: trigger lateness p99 < 60s (due_time to first attempt); at-most-once violation count: zero, audited by reconciliation; API availability 99.95%.
• Alerts: oldest-due PENDING age (the single best health number: if the sweep stalls, this grows), claim throughput vs due inflow, lease-expiry rate (worker health), DLQ arrival rate, gateway error and latency, reconciliation mismatches (any nonzero pages).
• Deploys: pollers and executors are stateless; roll freely, leases cover the gap. Partitions pre-create a week ahead by a boring cron that is itself monitored.
• Open questions to volunteer: the poll interval (5s) and lease length (2m) are guesses; derive them from the measured execution latency distribution and the lateness SLO. The smear window is a product conversation: how late is "at midnight" allowed to be? The lever exists; the number needs an owner.
• What I would cut first: the Kafka audit fan-out. At this scale the attempts table plus the database's own CDC to a warehouse may serve audit and notifications without a streaming tier; keep Kafka only if notification latency or consumer count demands it.
• Multi-region: single region of record; scheduled work tolerates a brief regional failover better than most systems, since due times are minutes-grained.

Final Design

• Creating a payment is one insert with a scoped idempotency key; the table, partitioned by due day and indexed by (status, due_time), is itself the schedule.
• Pollers sweep the current partition every few seconds and claim due rows with SKIP LOCKED, stamping a lease and an attempt number; executors call the gateway with paymentId as the idempotency key, so any number of retries collapses into at most one charge.
• The reaper reclaims expired leases from crashed workers and parks exhausted payments in the DLQ for a human.
• Every status change flows via CDC to Kafka for audit and notifications, and a daily reconciliation diffs the gateway's settlement report against the attempts table, both directions.
• The design is the one-cron-job baseline grown exactly three mechanisms: SKIP LOCKED claims, leases, and gateway idempotency keys. Nothing else was added, which is the argument that the component count is earned.

What is Expected at Each Level

• Mid-level candidates are expected to produce a working schedule table, a poller that executes due rows, a retry path with backoff, and a cancel endpoint, and to know amounts are integer minor units.
• Senior candidates are expected to nail the claim machinery (SKIP LOCKED batches, leases, the reaper), to key the gateway by paymentId and say why per-attempt keys double-bill, to keep the cancel race a one-row CAS with an honest 409, and to treat ambiguous gateway outcomes as "never guess, re-ask with the same key".
• Staff candidates are expected to open with the scale math that makes this a correctness problem, to name delay queues, Redis ZSETs, and timing wheels and decline each with reasons, to state that the midnight spike breaks the gateway ceiling first and converts into bounded lateness via smear and pacing, to close the loop with two-directional settlement reconciliation, to volunteer what they would cut (the Kafka tier) and which numbers are guesses (poll interval, lease length, smear window), and to frame the whole design as a cron job grown exactly three mechanisms.