d01 — Fault-Tolerant Distributed Job Scheduler

A fully worked design. This is the reported technical-screen design question (../../../research/source-report.md row 8), answered end to end in the nine-section template, then attacked by a hostile staff-level interviewer, then revised.

Attempt it yourself first. Reading a worked answer teaches you what a good answer looks like; writing one teaches you to produce one under a clock. The value is in the second thing.

Run it first. A companion page builds this as numbered, independently runnable blocks: at-most-once against at-least-once on the same 20,000 jobs, then the dual-write failure and lease renewal: Hands-On — Job Dispatch and Delivery Semantics. Every number on it was produced by running the code.

Table of Contents

• The Prompt
• How the 45 Minutes Were Spent
• 1. Requirements and Scope
• 2. Scale Numbers
• 3. API Surface
• 4. Data Model
• 5. High-Level Architecture
• 6. Deep Dive A: Exactly-Once Dispatch
• 7. Deep Dive B: Worker Liveness, Leases, Split Brain
• 8. Failure and Recovery
• 9. Bottlenecks and Evolution
• 10. Tradeoffs Explicitly Rejected
• The Hostile Critique
• The Revision
• What This Design Would Score
• References

The Prompt

"Let's design a distributed job scheduler. Users submit jobs — some run once at a specific time, some run on a recurring schedule, like a cron. The system runs them on a fleet of workers.

The important part is that it has to be fault-tolerant. Workers die. The scheduler itself can die. The network partitions. Jobs still need to run, and we care a lot about not silently dropping one.

Take it wherever you think is interesting. I'll interrupt with questions."

"Take it wherever you think is interesting" is the test. You choose what is load-bearing. Spending twenty minutes on the REST API and four on execution semantics is how this round is lost — silently, because nothing goes wrong, you just never reach the part that mattered.

How the 45 Minutes Were Spent

Section 10 is short because it was written in the last three minutes. That is correct prioritization, not an oversight — it is better to have a thin section 10 than no section 6.

1. Requirements and Scope

The clarifying questions I asked, and the answers I assumed

"At-least-once or at-most-once execution?" This is the fulcrum of the entire problem and most candidates never ask it. The prompt says "we care a lot about not silently dropping one" — that selects at-least-once. And at-least-once obligates me to say the next sentence:

Job handlers must therefore be idempotent, and I will give each execution a stable idempotency key so they can be.

Exactly-once execution of a side-effecting job is not achievable without cooperation from the job itself. I will not claim it.

"What's the scale?" Assumed, and stated aloud: 10M scheduled jobs, 50k executions/minute at peak, durations from 100 ms to 6 hours.

"How late can a job be before it's a bug?" Assumed p99 dispatch within 1 second of the scheduled time; a job 30 seconds late is degraded, not broken.

"Does anything need ordering?" Assumed per-job serialization required (no two concurrent runs of the same job under normal operation), no ordering across different jobs.

"Multi-tenant?" Assumed yes — isolation and fairness matter.

Functional

1. Submit a one-shot job with a fire time.
2. Submit a recurring job (cron-like) with a period and a schedule mode.
3. Cancel a job.
4. Query a job's status and execution history.
5. Execute jobs on a worker fleet.
6. Retry failures with backoff; dead-letter after N attempts.

Non-functional

Explicitly out of scope

Stated, so the interviewer knows these were decisions and not omissions:

• Job payload storage beyond a size cap (large payloads go to blob storage; we store a reference).
• Workflow/DAG dependencies between jobs — that is a different system (an orchestrator), and bolting it on here would compromise both.
• Exactly-once execution semantics — not achievable, see above.
• Cross-region active-active. Single region with multi-AZ; I will note where region failure hurts.

2. Scale Numbers

Done out loud, in about ninety seconds.

Dispatch rate. 50,000 executions/minute = ~830/s peak. Assume a 5:1 peak-to-average, so ~170/s average, ~15M executions/day.

Worker fleet. Mean job duration, say, 10 s. By Little's law, L = λW = 830 × 10 = 8,300 concurrent executions at peak. At 200 concurrent per worker (I/O-bound jobs), that is ~42 workers. Target 60% utilization → 70. Survive losing one of three AZs (×1.5) → ~105 workers. Round to 120.

If jobs were CPU-bound at 10 s of CPU each, this is 8,300 cores, which is a completely different system — so I would ask, and this is the number that changes everything.

Storage. 10M jobs × ~1 KB of metadata = 10 GB. Trivial; fits on one node with room to spare. The executions table is the one that grows: 15M/day × 300 B = 4.5 GB/day = 1.6 TB/year before replication. That needs a retention policy — 90 days hot, archive beyond — and it is the first thing that becomes a problem.

Due-job scan. The scheduler polls "what is due?" every 500 ms. With 830/s dispatch, each poll returns ~400 rows. That is a small, indexed range scan — completely fine. It is the write rate to next_run_at that will hurt, because updating it on every dispatch churns the index. Noted for section 9.

Conclusion stated aloud: this is not a data-volume problem. It is a coordination problem. Which is why the deep dives are on dispatch semantics and leases, not on storage.

3. API Surface

Deliberately small — five calls. The API is not where this problem is hard, and dwelling on it is how candidates burn the clock.

POST /jobs
  { "name", "payload_ref", "schedule": {"type": "once", "at": "2026-08-01T09:00:00Z"}
                                    | {"type": "cron", "expr": "0 9 * * *",
                                       "mode": "fixed_rate" | "fixed_delay",
                                       "catch_up": "run_all" | "run_latest_only" | "skip"},
    "max_attempts": 5, "timeout_s": 300, "tenant_id", "idempotency_key" }
  -> 201 { "job_id" }

DELETE /jobs/{job_id}            -> 204   (idempotent; cancels future runs)
GET    /jobs/{job_id}            -> 200   { job, next_run_at, state }
GET    /jobs/{job_id}/executions -> 200   [ { run_id, state, attempt, started, finished, error } ]
POST   /jobs/{job_id}/trigger    -> 202   { "run_id" }   (run now, out of band)

Three deliberate choices worth defending:

• idempotency_key on submission. Client retries of POST /jobs must not create duplicate jobs. The same reasoning as Stripe's API.
• catch_up is part of the schedule, not a global setting. What to do about missed occurrences is a per-job product decision and the API must surface it. See section 8.
• Executions are a first-class resource. Dispatched and completed are different states, and the user needs to see both — that distinction is what at-least-once actually promises.

4. Data Model

Postgres, partitioned. Justified in section 10.

CREATE TABLE jobs (
    job_id        uuid PRIMARY KEY,
    tenant_id     uuid        NOT NULL,
    shard         smallint    NOT NULL,        -- hash(job_id) % 256
    name          text        NOT NULL,
    payload_ref   text,
    schedule      jsonb       NOT NULL,
    next_run_at   timestamptz,                 -- NULL = not scheduled
    state         text        NOT NULL,        -- active | paused | cancelled
    max_attempts  int         NOT NULL DEFAULT 5,
    timeout_s     int         NOT NULL DEFAULT 300,
    created_at    timestamptz NOT NULL DEFAULT now()
);

-- The only index that matters. Partial: only rows that are actually schedulable.
CREATE INDEX jobs_due ON jobs (shard, next_run_at)
    WHERE state = 'active' AND next_run_at IS NOT NULL;

CREATE TABLE executions (
    run_id        uuid PRIMARY KEY,
    job_id        uuid        NOT NULL,
    scheduled_for timestamptz NOT NULL,
    attempt       int         NOT NULL,
    state         text        NOT NULL,   -- dispatched | running | succeeded
                                          -- | failed | timed_out | dead_lettered
    fence         bigint      NOT NULL,   -- monotonic; see deep dive B
    worker_id     text,
    lease_expires timestamptz,
    started_at    timestamptz,
    finished_at   timestamptz,
    error         text,
    UNIQUE (job_id, scheduled_for, attempt)   -- the dedupe guarantee
);

CREATE INDEX exec_leases ON executions (lease_expires)
    WHERE state IN ('dispatched', 'running');

Why these keys — the part that is actually being graded:

• (shard, next_run_at) is the whole dispatch path. shard first so each scheduler replica scans only the shards it owns, without contending on a global index. next_run_at second so "what is due" is a range scan. Partial index on state='active' AND next_run_at IS NOT NULL keeps it small: cancelled and completed one-shots are excluded entirely, so the index is sized by pending work rather than by all work.
• UNIQUE (job_id, scheduled_for, attempt) is the deduplication guarantee, enforced by the database rather than by application logic. Two schedulers that both decide job J is due at 09:00 attempt 0 cannot both create an execution — one gets a unique-violation. That converts a distributed race into a local constraint, which is a much better place for it.
• fence is the monotonic token that makes at-least-once safe. Deep dive B.

5. High-Level Architecture

                                  ┌────────────────┐
   submit / cancel  ─────────────▶│    API tier    │  (stateless, autoscaled)
                                  └───────┬────────┘
                                          │ write job + next_run_at
                                          ▼
                            ┌─────────────────────────────┐
                            │  Job store (system of record)│
                            │  jobs · executions           │
                            │  partitioned by shard        │
                            └──────┬───────────────▲───────┘
                                   │ poll owned    │ execution records
                                   │ shards, 500ms │ (dispatched → running
                                   ▼               │  → succeeded/failed)
              ┌─────────────────────────────────┐  │
              │   Scheduler replicas (N=3)      │  │
              │   • own DISJOINT shards         │  │
              │   • claim due jobs atomically   │  │
              │   • issue lease + fence token   │  │
              │   • reap expired leases         │  │
              └───────────────┬─────────────────┘  │
                              │ enqueue            │
                              │ (run_id, fence)    │
                              ▼                    │
                    ┌──────────────────┐           │
                    │  Dispatch queue  │  visibility timeout ≈ lease
                    │  (per priority)  │           │
                    └────────┬─────────┘           │
                             ▼                     │
                    ┌──────────────────┐           │
                    │   Worker fleet   │───────────┘
                    │  • renew lease   │  heartbeat @ lease/3
                    │  • run handler   │
                    │  • write result  │  WHERE fence >= exec.fence
                    └──────────────────┘

              ┌─────────────────────────────┐
              │  etcd / Raft                │  shard ownership, membership,
              │  (metadata only, not data)  │  fence counter
              └─────────────────────────────┘

Shard ownership, not leader election. All three schedulers are active, each owning a disjoint subset of the 256 shards. Ownership is held in etcd with a lease. This gives 3× the dispatch throughput of a single-leader design, and a scheduler failure affects only its shards — roughly a third of jobs see a brief delay rather than all of them.

Consensus for metadata only. etcd holds shard ownership, membership, and the fence counter — kilobytes, changing rarely. It does not hold job data. Putting the data path through consensus would make every dispatch a majority round trip, which is exactly the cost named in Chapter 6.5 of the warmup.

6. Deep Dive A: Exactly-Once Dispatch

The problem. Three scheduler replicas exist for availability. Under normal operation they own disjoint shards, so only one of them ever considers job J. But during a membership change — a scheduler restarts, or is briefly partitioned and its etcd lease expires — ownership moves, and there is a window where two replicas both believe they own shard 7.

Both see job J due at 09:00:00. Both try to dispatch it.

Option 1 — Single leader (rejected)

One scheduler, elected via etcd, does all dispatch.

• ✅ Trivially correct: only one node ever decides.
• ❌ Throughput ceiling of one node. At 830/s that is survivable; at 10× it is not.
• ❌ Failover is a full dispatch outage of hundreds of milliseconds to seconds.

Rejected because it converts a 3× throughput opportunity into a single point of latency, and the correctness it buys is available more cheaply — see Option 3.

Option 2 — Partitioned ownership alone (insufficient)

Hash job to a shard; each scheduler owns some shards.

• ✅ Linear scaling, and a failure affects only that scheduler's shards.
• ❌ The membership-change window is exactly the failure case. Ownership is a lease, and during expiry-and-reassignment two nodes can both believe they own a shard.

Insufficient alone. It is the right scaling structure and it does not, by itself, give correctness.

Option 3 — Partitioned ownership + atomic claim (chosen)

Ownership gives scale; an atomic conditional insert gives correctness.

BEGIN;

  -- 1. Claim due jobs from MY shards. SKIP LOCKED means concurrent
  --    schedulers take disjoint rows without blocking each other.
  SELECT job_id, schedule, next_run_at, max_attempts, timeout_s
    FROM jobs
   WHERE shard = ANY(%s)                 -- shards I own
     AND state = 'active'
     AND next_run_at <= now()
   ORDER BY next_run_at
     FOR UPDATE SKIP LOCKED
   LIMIT 200;

  -- 2. Create the execution. The UNIQUE constraint is the real guarantee:
  --    if another scheduler already created this exact (job, time, attempt),
  --    this INSERT does nothing and we know not to enqueue.
  INSERT INTO executions
         (run_id, job_id, scheduled_for, attempt, state, fence, lease_expires)
  VALUES (%s, %s, %s, 0, 'dispatched', nextval('fence_seq'), now() + interval '60 s')
  ON CONFLICT (job_id, scheduled_for, attempt) DO NOTHING
  RETURNING run_id, fence;

  -- 3. Advance the schedule in the SAME transaction.
  UPDATE jobs SET next_run_at = %s WHERE job_id = %s;

COMMIT;

-- 4. Only AFTER commit, enqueue (run_id, fence) for the workers.

Why this is correct. The unique constraint on (job_id, scheduled_for, attempt) means the database — a single serialization point — decides who wins. Two schedulers racing on the same job produce one insert and one no-op. The distributed race becomes a local constraint, which is the whole trick: push the coordination into a component that is already coordinated.

Why the enqueue is after the commit — and this is the part people get wrong. If you enqueue inside the transaction and the transaction then rolls back, you have enqueued work that no execution record covers: a phantom run. Enqueuing after commit means the opposite risk — commit succeeds, the process dies before enqueue, and the execution record sits in dispatched forever with no worker.

That second failure is recoverable and the first is not, which is why this ordering is chosen: the lease reaper (deep dive B) finds dispatched records whose lease expired and re-enqueues them. So the failure mode is "a job runs late" rather than "a job runs twice with no record" or "a job silently never runs".

This is the dual-write problem (warmup §9.2) and I am solving it by making the database the source of truth and the queue a hint. A stricter version is the outbox pattern: insert into an outbox table in the same transaction and have a relay publish it. That removes the window entirely at the cost of a relay and extra latency. I would start with the reaper and move to an outbox if the observed re-dispatch delay proves unacceptable — and I would say exactly that, because knowing the stricter design and choosing the simpler one deliberately is the point.

7. Deep Dive B: Worker Liveness, Leases, Split Brain

The problem, stated as sharply as possible. A worker claims job J with a 60-second lease. Then it partitions, or GC-pauses, or the hypervisor deschedules it. The lease expires. The scheduler must decide: is the worker dead, or is it running the job right now on the other side of a partition?

It cannot tell. That is not a gap in my design — it is a theorem. An unreachable process and a dead process are indistinguishable from outside. Saying this out loud is worth more than any mechanism, because it frames everything that follows as choosing a failure mode rather than eliminating one.

The choice

The prompt says "we care a lot about not silently dropping one". That selects at-least-once — and it obligates me to make the double-execution case safe. Two mechanisms.

Mechanism 1 — Fencing tokens

Every execution carries a monotonically increasing fence, from a Postgres sequence.

t=0    Worker A claims run R. fence = 33. Lease to t=60.
t=10   A GC-pauses. From A's perspective, nothing happens.
t=60   Lease expires. The reaper re-dispatches: run R attempt 1, fence = 34.
t=70   Worker B claims fence 34, runs, and writes its result.
t=90   A wakes up. It believes no time has passed. It writes with fence 33.
       REJECTED — 33 < 34.

The write path enforces it:

UPDATE executions
   SET state = 'succeeded', finished_at = now(), result_ref = %s
 WHERE run_id = %s
   AND fence <= %s;         -- the worker's token
-- 0 rows updated means a newer holder superseded me. Stop. Do not retry.

Where the token is checked matters more than the token itself. It must be enforced by the resource being protected, not by the worker. A zombie worker believes its token is current, because from inside the pause no time passed. If the worker checks its own token, you have gained nothing.

If a job's side effect is an external system with no conditional write — a third-party API — then I cannot fence it, and I must say so. The mitigations there are: pass the idempotency key to that API and rely on their dedupe (Stripe-style), or accept at-most-once for that class of job and mark it so. What I will not do is pretend fencing covers something it does not.

Mechanism 2 — Idempotency keys handed to the handler

Each execution gets a stable key, sha256(job_id | scheduled_for | attempt), passed to the handler. A handler that writes to a database uses it as a unique constraint; a handler that calls an external API passes it through. This is how at-least-once delivery becomes exactly-once effect — which is the only exactly-once anyone can actually have.

Lease renewal and the timing budget

Workers heartbeat at lease/3 — 20 s for a 60 s lease — so two consecutive missed heartbeats are tolerated before expiry.

UPDATE executions
   SET lease_expires = now() + interval '60 s', state = 'running'
 WHERE run_id = %s AND fence <= %s AND state IN ('dispatched','running');

If the renewal returns 0 rows, the worker has been superseded. It should abort immediately, not finish and write — because its write will be rejected anyway and its side effects are now racing with the replacement.

Choosing the lease duration is a genuine tradeoff and I would state the numbers:

• Too short (10 s) → a GC pause or a network blip causes spurious expiry, and you get double execution routinely rather than exceptionally.
• Too long (10 min) → a genuinely dead worker's job is stuck for ten minutes.
• 60 s with 20 s heartbeats tolerates two lost heartbeats, which covers ordinary GC pauses and brief network blips, and bounds recovery at about a minute.

Long-running jobs: a 6-hour job renews its lease ~1,000 times. That is fine, but it means the lease is a liveness signal, not a duration bound — so I also need an independent timeout_s per job, after which the execution is marked timed_out and the worker is asked to cancel. Otherwise a hung job renews forever and never completes.

The reaper

One scheduler role scans for expired leases and re-dispatches:

SELECT run_id, job_id, attempt FROM executions
 WHERE state IN ('dispatched','running')
   AND lease_expires < now()
 ORDER BY lease_expires
 LIMIT 100 FOR UPDATE SKIP LOCKED;

It uses now() from the database, not from the scheduler process — one clock, so no cross-node skew (warmup §3.2).

Rate-limit the reaper. If 5,000 leases expire at once — an AZ went down — re-dispatching all of them instantly is a thundering herd onto the surviving workers, which are already carrying extra load. Cap it at a few hundred per second and let recovery take a minute.

8. Failure and Recovery

Every row has all three legs.

The catch-up policy, in detail

This is the failure people forget, and it is the one that turns an outage into a worse outage.

Scheduler down for two hours. It comes back. 40,000 jobs are overdue. What happens?

This is a product decision the design must expose, not silently make. Per-job:

• run_all — fire every missed occurrence. Correct for billing runs where each period must be processed.
• run_latest_only — collapse missed occurrences into one. Correct for a cache refresh where only the current state matters. The right default.
• skip — drop the missed ones entirely. Correct for "send a good-morning notification", where a 2-hour-late one is worse than none.

Then, regardless of policy, rate-limit the drain: a token bucket on dispatch, with overdue work at lower priority than newly-due work. New work has someone waiting on it; overdue work does not.

9. Bottlenecks and Evolution

What breaks first, in order:

1. The next_run_at index, at ~10× dispatch rate. Every dispatch updates next_run_at, which churns the index. Postgres's MVCC means each update writes a new tuple and leaves a dead one, so the index bloats and autovacuum falls behind. At 8,300 dispatches/second this becomes the limit.

Fix, in order of cost: partition jobs by shard so each partition's index is smaller and vacuum is parallel; tune autovacuum aggressively on this table; if that is exhausted, move the hot dispatch path to a purpose-built store (a per-shard timer wheel in memory, backed by periodic checkpoints) while keeping Postgres as the system of record.

2. The executions table, at 1.6 TB/year. Partition by month, drop old partitions rather than DELETE (which is far more expensive and generates enormous vacuum load), and archive to object storage.

3. The single fence sequence. Every dispatch takes nextval. Postgres sequences are fast and non-transactional, so this is fine to well past 10×. If it were not, I would shard the sequence per-shard and make the fence (shard, counter) — comparable within a shard, which is all the fencing check needs, since a run never moves between shards.

4. Queue fan-out at 10×. One queue becomes a bottleneck and a single failure domain. Shard the queue by priority class first (which I want anyway for fairness), then by shard.

What I would build differently at 100×: replace the poll-based scheduler with an in-memory timer wheel per shard, checkpointed to the store. Polling every 500 ms across 256 shards is fine at 830/s and wasteful at 83,000/s. A hierarchical timer wheel gives O(1) insert and O(1) tick, which is how the Linux kernel and Kafka's purgatory schedule timers.

10. Tradeoffs Explicitly Rejected

Written in the last three minutes, and it still matters more than another paragraph of architecture.

Rejected: a dedicated queue as the system of record (SQS/Kafka with delayed delivery). Attractive because the queue already does visibility timeouts and retries. Rejected because: recurring schedules need mutable state that a queue does not model; cancellation of an already enqueued message is not supported by most queues; SQS caps delayed delivery at 15 minutes, and these jobs schedule months ahead. What would flip it: if all jobs were one-shot and within 15 minutes, the queue alone would be simpler and I would use it.

Rejected: Raft leader election for a single active scheduler. Simplest correct design. Rejected because it caps dispatch throughput at one node and makes failover a full dispatch outage. Shard ownership plus an atomic claim gives the same correctness with 3× throughput. What would flip it: if the dispatch rate were under ~100/s, the simplicity would be worth more than the throughput, and I would take the leader.

Rejected: putting job data through Raft. Consensus is a majority round trip per write — ~1 ms same-DC, 50–150 ms cross-region — and the leader is a throughput ceiling. Metadata (ownership, membership) goes through etcd; data does not. What would flip it: a requirement for cross-region strong consistency on the schedule itself.

Rejected: at-most-once semantics. Simpler — no fencing, no idempotency requirement on handlers. Rejected because the prompt explicitly prioritizes not dropping jobs, and at-most-once means a worker that dies mid-job silently drops it. What would flip it: a job class where a duplicate is genuinely worse than a miss — sending a payment, for instance — for which I would support a per-job at_most_once flag and document that it can drop.

Rejected: Redis as the primary store. Faster, and its sorted sets are a natural fit for next_run_at. Rejected because durability is weaker (RDB/AOF both have a loss window), it lacks the transactional guarantee that makes the atomic claim work, and I would have to build the unique-constraint dedupe in application code. What would flip it: if dispatch rate demanded it and I could tolerate a small loss window, Redis as a cache in front of Postgres — never as the record.

The Hostile Critique

What a staff-level interviewer does to the design above. Every one of these is a real gap; the answers are in the revision.

C1. "You enqueue after commit. Commit succeeds, the process dies, no enqueue. You say the reaper catches it — but the lease is 60 seconds and the execution row is dispatched with a lease you set at insert time. So a job whose scheduler died at the wrong instant is up to 60 seconds late, every time. Your stated p99 dispatch latency is 1 second. Your design violates its own SLO in a failure mode you have already admitted is possible. What do you do?"

C2. "Your reaper does SELECT ... WHERE lease_expires < now() LIMIT 100 FOR UPDATE SKIP LOCKED. That index is on lease_expires filtered by state. At 8,300 concurrent executions, every one of those rows is being updated every 20 seconds by lease renewal. You have built a write hotspot on the exact index the reaper scans. Have you costed that?"

C3. "You said fencing makes at-least-once safe. Walk me through a job whose only side effect is POST /charge to a third-party payment API with no idempotency support. Where does your fence token get checked?"

C4. "Two schedulers both own shard 7 during a membership change. You say the unique constraint saves you. But scheduler A inserts the execution and then updates next_run_at in the same transaction. Scheduler B's insert conflicts and does nothing — but does B also skip its next_run_at update? What if B commits its update with a different value?"

C5. "Your catch-up policy is per job. A tenant has 10,000 jobs, all run_all, and you were down for two hours with a 1-minute period. That is 1.2 million executions to catch up. Your rate limiter drains them. How long until that tenant's newly-due jobs run on time again, and what does every other tenant experience meanwhile?"

C6. "You provisioned 1.5× for AZ loss. An AZ dies. You now have 5,000 leases expiring over 60 seconds while running at 100% on the remaining workers. Your reaper re-dispatches them, rate-limited. Meanwhile new jobs keep arriving at 830/s. Does this converge or diverge?"

The Revision

Each change, with what it costs.

R1 — Fix the enqueue gap (answers C1)

The critique is correct: the design violates its own SLO in a failure mode I admitted.

Change: set the initial lease_expires to a short dispatch grace — 5 seconds — rather than the full 60. The lease is only extended to 60 s when a worker actually claims it.

INSERT INTO executions (..., state, lease_expires)
VALUES (..., 'dispatched', now() + interval '5 s');
-- worker claim:
UPDATE executions SET state='running', worker_id=%s,
       lease_expires = now() + interval '60 s'
 WHERE run_id=%s AND fence <= %s;

Now an execution that was committed but never enqueued is reaped within ~5 s instead of ~60 s. dispatched and running are now genuinely different states with different timeouts, which they should have been from the start.

Cost: a worker that takes more than 5 s to pick up a message gets its run re-dispatched, producing a duplicate. Acceptable — fencing makes duplicates safe, and queue pickup is milliseconds under normal load. The real fix if 5 s is still too slow is the outbox pattern, which removes the window entirely; I would move to it if measurement showed this mattering.

R2 — Remove the lease-renewal hotspot (answers C2)

The critique is correct and I had not costed it. 8,300 executions renewing every 20 s is ~415 UPDATEs/second on rows the reaper is also scanning, and under MVCC each one writes a new tuple.

Change: move lease state out of the executions row.

• Keep executions as an append-mostly audit log: written on dispatch, on terminal state, and nowhere else.
• Put liveness in a separate small table (or Redis) keyed by run_id, holding only (worker_id, fence, expires_at). It is ~8,300 rows of ~40 bytes — a few hundred KB, easily memory-resident, and it can be a non-durable store because it is reconstructible: on loss, every in-flight run's lease is treated as expired and re-dispatched. Correct, just noisy.

Cost: one more component, and a re-dispatch storm if the lease store is lost. Mitigated by the same rate limiter as R5.

R3 — Be honest about unfenceable side effects (answers C3)

The critique exposes an overclaim. Fencing protects my storage. It cannot protect a third-party API that does not check my token.

Change: classify jobs by side-effect safety, in the API.

unsafe_external genuinely can drop a job, and that is the honest cost. The design now surfaces the drop as an alert on an unknown-state execution rather than pretending it did not happen. Making the user choose is better than silently choosing for them.

R4 — Make the claim transaction correct (answers C4)

The critique found a real bug. As written, if B's insert conflicts, B's UPDATE next_run_at still runs — and if B computed a different next occurrence (clock skew, or a different interpretation of a DST boundary), it overwrites A's.

Change: make the next_run_at update conditional on having won the insert, and make it idempotent:

WITH claimed AS (
  INSERT INTO executions (run_id, job_id, scheduled_for, attempt, state, fence, lease_expires)
  VALUES (%s, %s, %s, 0, 'dispatched', nextval('fence_seq'), now() + interval '5 s')
  ON CONFLICT (job_id, scheduled_for, attempt) DO NOTHING
  RETURNING job_id, scheduled_for
)
UPDATE jobs j
   SET next_run_at = %s
  FROM claimed c
 WHERE j.job_id = c.job_id
   AND j.next_run_at = c.scheduled_for   -- only if nobody else advanced it
RETURNING j.job_id;

If the insert conflicted, claimed is empty and the update touches nothing. And the j.next_run_at = c.scheduled_for predicate makes it a compare-and-swap, so a stale scheduler cannot move the schedule backwards.

Cost: none. This is strictly better and I should have written it this way.

R5 — Bound catch-up per tenant (answers C5)

The critique is right that a global rate limiter does not stop one tenant's backlog from consuming the whole recovery budget.

Change: two-level rate limiting.

• Global dispatch budget for overdue work, capped at a fraction — say 20% — of total dispatch capacity, so overdue work can never starve new work.
• Per-tenant share of that overdue budget, weighted fairly. One tenant with 1.2M overdue executions gets its slice and no more.
• Cap the catch-up depth: run_all collapses to run_latest_only beyond a configurable number of missed occurrences (default 100), with an alert. Nobody wants 1.2 million one-minute-period runs replayed; they want to know it happened.

Cost: run_all is no longer literally all past a threshold. That is a semantic change and it must be documented in the API — but the alternative is a recovery that never completes, which is a worse contract.

R6 — Prove convergence under AZ loss (answers C6)

The critique demands arithmetic, and it deserves it.

Losing one of three AZs: 120 workers → 80. Capacity 80 × 200 / 10 s = 1,600 executions/s versus 830/s of new work. So there is ~770/s of headroom — it converges, but only because I provisioned 1.5×.

The 5,000 expiring leases re-dispatch at the reaper's rate limit. At 200/s that is 25 seconds of recovery, consuming 200 of the 770/s headroom. Fine.

But the failure case is real: if utilization were 80% rather than 60% before the AZ loss, remaining capacity would be 1,600/s against 830/s of new work plus the re-dispatch, and every re-dispatched job would itself risk lease expiry — a re-dispatch spiral.

Change: add a circuit breaker on the reaper. If the fleet is above 85% utilization, stop re-dispatching expired leases and alert instead. Jobs run late, which is bad; the alternative is a spiral where nothing completes, which is worse.

Cost: during severe overload, jobs are delayed indefinitely until capacity returns. That is a deliberately accepted failure mode, and it is the right one — a scheduler that delays under overload is recoverable; one that spirals is not.

What This Design Would Score

Against ../../../diagnostics/RUBRIC.md:

Hire-bar verdict: strong hire (staff) — but only after the revision. The pre-critique version has a real bug (R4), an SLO violation in an admitted failure mode (R1), an uncosted hotspot (R2), and an overclaim (R3).

That is the honest lesson of this document. The first draft looks complete and is not. The gap between hire (senior) and strong hire (staff) is not knowing more primitives — it is having your own design attacked enough times that you find those four things yourself, before the interviewer does.

Which is why the critique loop exists, and why you should attempt every design before reading its worked answer.

References

• ../WARMUP.md — every primitive used here, explained from zero
• ../README.md — the template, the drills, the critique loop
• ../calculators/envelope.py — the section 2 arithmetic, runnable
• ../../coding/WARMUP.md#chapter-5-heaps-and-deterministic-scheduling — the single-node scheduler this distributes
• Kleppmann, M. Designing Data-Intensive Applications, 2nd ed. — Ch. 8 (fencing tokens), Ch. 9 (leases, consensus)
• Kleppmann, M. How to do distributed locking. https://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html
• Burrows, M. The Chubby Lock Service. OSDI 2006 — sequencers, which are fencing tokens
• PostgreSQL docs — SELECT ... FOR UPDATE SKIP LOCKED, and Routine Vacuuming for the index-churn argument in §9
• Amazon Builders' Library — Avoiding insurmountable queue backlogs, which is the catch-up-storm problem