Design a Distributed Job Scheduler and Task Queue

This page is one interview loop in three rounds. All three rounds design the same system. Each round opens with the interviewer raising the scope, and the design from the round before has to evolve to meet it.

You can start at any round. Rounds 2 and 3 open with a "Where we left off" summary that catches you up.

Loop Opener: What Is a Job Scheduler?

You Already Know One: an Alarm Clock With a To-Do List

Your phone's alarm app does two things. It remembers when ("7:00 on weekdays"), and when the time comes it does something (plays a sound). A job scheduler is the same, for software:

The thing a job calls is its target: an HTTP endpoint, a queue, or a worker process. The job itself is small: when, what to call, with what payload, and what to do on failure.

What Makes It Hard

On one machine with one crontab, this is easy. In production, four things go wrong:

Every problem in the three rounds is one of three concerns:

• When: finding due jobs on time (timers, buckets, cron).
• Who: making sure one worker owns each run (claims, leases, fencing).
• What if it fails: retries, dead-letter queues, reapers.

The Question the Whole Loop Answers

A worker can crash after it called the target but before it wrote down "done". The next worker can't tell whether the call happened. So it has two choices: run the job again (maybe twice), or don't (maybe never). No design escapes this for side effects outside our own system. That's why "exactly once" is not something we can promise for an email or a payment.

How do we run every job at the right time, and make it safe when machines fail and a job runs twice?

The answer gets sharper every round:

• Round 1: at-least-once execution, plus an idempotency key the target uses to ignore repeats.
• Round 2: the same promise at 100,000 times the load, with fencing so a stale worker can't corrupt our own records.
• Round 3: a precise contract: exactly-once for the engine's own state transitions, at-least-once for everything it calls, across regions.

---

Round 1 · Mid-level · "Scheduled Emails and Nightly Jobs for One App"

~35 min · SDE II (L5) · 1 region, 3 AZs · ~100K scheduled jobs · 50 runs/s in the busiest minute · within ~1 min · 99.9%

R1.1 Establish Design Scope

The interviewer says: "Our app lets users set reminders, and we have a few nightly jobs. Design the scheduler." Before we draw anything, we ask questions and say what each answer changes.

Out of scope for this round:

• Priorities. Every job is equally important today.
• Very long jobs (hours). They'd need heartbeats and lease renewal.
• Workflows, where one job's output feeds the next. Each job stands alone.

R1.2 Functional Requirements, Derived Step by Step

Not yet: priorities, long jobs with heartbeats, cancelling a run that's already running, and workflows.

R1.3 Non-Functional Requirements: the Questions

• Durability: never lose a job. Once we return "created", the job must run even if every machine restarts.
• Never early. A reminder at 9:00 must not fire at 8:59.
• A little late is fine. Within about a minute of the scheduled time.
• Avoid duplicates, but we can't rule them out. If a worker dies after calling the target and before recording success, we can't know whether the call worked. We'd rather run twice than never, so the target must be able to ignore a repeat. We give it an idempotency key: a value that is the same every time we retry the same run, so the target can recognize and skip a repeat.
• Availability: 99.9%. The API and the scheduler can be down about 8.8 hours a year (0.1% × 8,760 h). Jobs due during an outage run late, not never.

R1.4 The API

Create a job

httpCopy
POST /v1/jobs HTTP/1.1
Content-Type: application/json
Idempotency-Key: 5d0c1f3a-8a7e-4b52-9a61-0e2f7c9b1d44

{
  "schedule": { "type": "CRON", "cron": "0 8 * * *", "time_zone": "America/New_York" },
  "target": { "url": "https://email.internal/v1/digests", "method": "POST", "timeout_seconds": 30 },
  "payload": { "user_id": 1001, "kind": "daily_digest" },
  "retry_policy": { "max_attempts": 5, "initial_backoff_seconds": 10, "max_backoff_seconds": 600 },
  "misfire_policy": "RUN_ONCE"
}

jsonCopy
{
  "job_id": "job_01J9ZK8V4T6Q",
  "status": "SCHEDULED",
  "next_run_at": "2026-09-28T12:00:00Z",
  "next_run_local": "2026-09-28T08:00:00-04:00"
}

A one-off job uses "schedule": { "type": "ONCE", "run_at": "2026-09-28T09:00:00", "time_zone": "Europe/Berlin" }.

Read a job

httpCopy
GET /v1/jobs/job_01J9ZK8V4T6Q HTTP/1.1

jsonCopy
{
  "job_id": "job_01J9ZK8V4T6Q",
  "status": "SCHEDULED",
  "next_run_at": "2026-09-28T12:00:00Z",
  "recent_runs": [
    { "scheduled_for": "2026-09-27T12:00:00Z", "attempt": 1, "outcome": "SUCCEEDED", "finished_at": "2026-09-27T12:00:04Z" }
  ]
}

Cancel a job

httpCopy
DELETE /v1/jobs/job_01J9ZK8V4T6Q HTTP/1.1

jsonCopy
{ "job_id": "job_01J9ZK8V4T6Q", "status": "CANCELLED" }

Why an Idempotency-Key on create? POST creates something new. If the network times out after we stored the job, the client retries, and without the key we'd store the reminder twice and send two emails. With the key, the server returns the job it already created.

What the target receives. Every call to the target carries Idempotency-Key: job_01J9ZK8V4T6Q:2026-09-28T12:00:00Z: the job ID plus the scheduled time of this run. It stays the same across retries of one run and changes for the next day's run.

Status codes

Recap

• Two schedule types: a one-off time and a cron expression, both with a time zone.
• About 100K scheduled jobs; runs must start within a minute and never early.
• Jobs call internal HTTP endpoints for seconds to minutes.
• Retries, then a dead-letter queue. Duplicates are possible, so targets get an idempotency key.

Let's build it, starting with what most teams already have.

R1.5 Design Evolution: From One Crontab to a Worker Fleet

Every step follows the same pattern: a problem, your turn to think, the answer, and what the answer costs us.

Step 1.0: The Baseline

One server runs cron. Its crontab has the nightly jobs, and a small script reads reminders from the app database every minute and sends the due ones.

Synthesizing vector architecture diagram...

Everything lives on one machine: the schedule, the loop that finds due work, and the calls.

What's good: it's simple, and it works for a while. Everything below exists because this server will die, and nobody will notice until the reminders stop.

Step 1.1: The Cron Server Died and the Nightly Job Didn't Run

We use Amazon DynamoDB for the table. In DynamoDB an index must have a partition key, so we can't just "index next_run_at". We give each waiting job two extra attributes, timer_shard (one of D#0 … D#3, from a hash of the job ID) and timer_at (its next_run_at), and build a global secondary index (GSI, a second copy of selected attributes, keyed differently) called timer-index on them. A worker asks each of the 4 shards for items with timer_at <= now. The index is sparse: only items that have timer_shard appear in it, so it holds waiting jobs and nothing else.

Why 4 shards and not 1? One partition key value lives on one partition, and DynamoDB serves each partition at up to 1,000 write units and 3,000 read units per second. We're nowhere near that today; 4 shards is cheap insurance, and Round 2 shows why the count must grow with the load.

Step 1.2: Two Workers Picked the Same Job

The claim, as the JSON request the worker sends to DynamoDB's UpdateItem:

jsonCopy
{
  "TableName": "jobs",
  "Key": { "job_id": { "S": "job_01J9ZK8V4T6Q" } },
  "ConditionExpression": "#st = :scheduled AND next_run_at = :seen_due",
  "UpdateExpression": "SET #st = :claimed, lease_owner = :me, lease_expires_at = :lease_end, timer_shard = :lease_shard, timer_at = :lease_end, attempt = attempt + :one",
  "ExpressionAttributeNames": { "#st": "status" },
  "ExpressionAttributeValues": {
    ":scheduled": { "S": "SCHEDULED" },
    ":claimed": { "S": "CLAIMED" },
    ":seen_due": { "N": "1790596800000" },
    ":me": { "S": "worker-az-b-7f3c" },
    ":lease_end": { "N": "1790597130000" },
    ":lease_shard": { "S": "L#2" },
    ":one": { "N": "1" }
  },
  "ReturnValues": "ALL_NEW"
}

Three details:

• next_run_at = :seen_due makes the claim fail if the job was rescheduled or cancelled after we read it from the index. The index is a copy that's updated a moment after the table, so what a worker sees there can be stale. The conditional claim is what makes stale reads harmless.
• The claim moves the job in the index. timer_shard changes from D#2 ("waiting to run") to L#2 ("claimed, lease ends at timer_at"). The same index now answers a second question: "which claims have expired?" (step 1.3). One index, one rule: every job has exactly one next timer.
• :lease_end comes from the worker's clock: now + timeout (30 s) + 5 minutes. DynamoDB's condition language has no "current server time". We come back to that in R1.9.

ReturnValues: ALL_NEW hands the worker the whole job (target, payload, retry policy) in the same call, so it doesn't need a second read.

Synthesizing vector architecture diagram...

Both workers see the same due job. The database applies the conditional updates one at a time, so the second one finds status CLAIMED and fails. To waste fewer claims, each worker shuffles its list of due jobs before claiming.

Primitive: Distributed Locks & Leases

Step 1.3: A Worker Died Holding a Job

Synthesizing vector architecture diagram...

A job is always in one state, and every arrow is a conditional update. A cron job whose attempts are exhausted records a failed run, goes to the dead-letter queue, and is re-armed for its next occurrence.

How a target makes itself idempotent. The email service keeps a table of idempotency keys it has handled, with a unique constraint. On a request, it inserts the key first; if the insert fails because the key exists, it returns the stored result and sends nothing. The key must be stored in the same transaction as the side effect, or a crash between them brings the problem back.

Step 1.4: The Target Was Down

Only some failures are worth retrying:

Primitive: Circuit Breaker, Bulkhead & Fault Tolerance

Step 1.5: A Daily Job Was Skipped in March and Ran Twice in November

Cron details that trip people up:

Trace: re-arming a daily job on the fall-back night (the night of Sunday, November 1, 2026 in New York)

textCopy
1. Job: cron "30 1 * * *", zone America/New_York, dialect Unix 5-field.
2. Run scheduled for 2026-10-31 01:30 EDT = 2026-10-31T05:30Z succeeds.
3. cron_next(after 2026-10-31T05:30Z) finds 01:30 on 2026-11-01.
4. 01:30 occurs twice that night: 01:30 EDT (05:30Z) and 01:30 EST (06:30Z).
5. Policy "run once, first occurrence" picks 05:30Z. next_run_at = 2026-11-01T05:30Z.
6. After that run, cron_next(after 2026-11-01T05:30Z) must return 2026-11-02 01:30 EST = 06:30Z,
   not the second 01:30 of the same night (06:30Z on Nov 1). The library's "after" logic,
   plus the policy, decide this. We test both DST nights for every zone we support.

Step 1.6: The Scheduler Was Down for an Hour: Run the Missed Jobs?

Round 1 Step Summary

R1.6 Architecture v1

Synthesizing vector architecture diagram...

The API only writes jobs. Workers do everything else: find due jobs, claim them, call targets, record runs, re-arm cron jobs and reap expired claims. The table is the only shared state, so any worker can die at any moment.

Tables

jobs (partition key job_id)

timer_at must be a Number. As a String, "999" sorts after "1000", and the index would return jobs in the wrong order.

job_runs (partition key job_id, sort key scheduled_for#attempt): one item per attempt with the outcome, the HTTP status and timings. A 30-day TTL cleans it up. TTL deletion is a background process that typically removes an item within a few days of its expiry time, so the table holds a little more than 30 days, and reads filter out expired items.

Trace 1: a one-off reminder

1. At 08:40 the app creates a job for 09:00 Berlin time. The API converts it to 07:00:00Z, puts the item with timer_shard = D#1, and returns 201.
2. At 07:00:03Z, worker AZ-a's poll of D#1 returns the job. It claims it (step 1.2).
3. It calls the email service with Idempotency-Key: job_…:2026-09-28T07:00:00Z, gets 200, writes a job_runs item, and sets the job COMPLETED with timer_shard removed, conditional on lease_owner being itself and status still CLAIMED.

Trace 2: a cron re-arm

1. The digest for 08:00 New York (12:00Z) succeeds.
2. The worker computes the next occurrence from scheduled_for = 12:00Z: 08:00 tomorrow New York = 12:00Z tomorrow.
3. One conditional update sets status = SCHEDULED, next_run_at and timer_at to tomorrow, timer_shard back to D#…, and clears the lease.

Trace 3: a worker crash

1. Worker AZ-c claims the 02:00 report; its lease ends at 02:05:30.
2. The task is killed at 02:01.
3. At 02:05:47 (the next 30-second reaper pass after the lease end plus a 5-second margin), worker AZ-a finds it in L#…, returns it to SCHEDULED due now, and claims it on its next poll.
4. The report runs again from the start with the same idempotency key. If the report service had already finished the first attempt's work under that key, it returns the stored result.

R1.7 Numbers

Targets

Jobs and runs (assumptions: the app has 1M users; these are our estimates, not given numbers)

The busiest minute. Averages hide clustering. Users keep the default digest time (08:00) about 20% of the time (assumption), and half our users live in one time zone: 25K × 20% × 50% = 2,500 digests due at 08:00 in that zone. Add about 500 reminders people set for a round time like 09:00 in the same minute (assumption): 3,000 jobs due in one minute.

• If all 3,000 had to start in the first second: 3,000 runs/s.
• Our target is "within 60 s", so we can spread them over the minute: 3,000 ÷ 60 s = 50 runs/s. That's the number we size for.

Workers

Polling load

Writes per run (DynamoDB bills one write unit per 1 KB written; changing a GSI key costs a delete plus a put in the index)

That's 7 per cron run (claim 3, finish 3, run item 1) and 8 per one-off job over its life (create 2, claim 3, finish 2, run item 1): 150K × 8 + 25K × 7 = 1.375M writes a day, about 41M a month.

Storage: jobs about 100K × 1 KB = 100 MB. job_runs: 175K a day × 30 days × ~0.5 KB = 2.6 GB, plus the few days TTL may lag, so plan for ~3 GB.

Rough monthly cost (us-east-1 list prices; check the AWS Pricing Calculator before quoting)

The fleet costs more than the database. At this size, the scheduler is almost free to run; what costs is building and owning it.

R1.8 Trade-Offs

Polling a table vs a delay queue

A delay queue can't hold a reminder set for next week without re-queuing it every 15 minutes, and we couldn't cancel it. It's useful for short retry delays (Round 2), not as the schedule.

Relational vs key-value store

At 100K jobs, Postgres is an equally good choice, and now() in the query makes lease math simpler. We pick DynamoDB because it needs no operating and because Round 2's scale will need it anyway. Either answer is fine in an interview if you name what the other one gives you.

Build or buy? Honestly, at this scale: buy. The app would create one EventBridge Scheduler schedule per reminder (one-time schedules with ActionAfterCompletion: DELETE, since completed one-time schedules still count against the quota until deleted) and one per digest (cron with the user's time zone). 175K runs a day is about 5.3M invocations a month, inside the 14M free invocations a month; after that it's $1.00 per million. The schedule's target would be an SQS queue or a Lambda function that calls the internal endpoint. What we'd give up: 60-second precision (fine here), status history (we'd log it ourselves), and our own misfire policies. The design above is what we'd build if the interviewer says "no managed scheduler", and it's the foundation for Rounds 2 and 3.

R1.9 Failure Modes

R1.10 Pillar Check

R1.11 Round 1 Rubric and Follow-Ups

What a strong mid-level (L5) answer shows

• Asks about precision, duration, failure handling and time zones before designing.
• Moves the schedule out of one machine into a shared table with stateless workers.
• Claims with a conditional write and explains why read-then-write fails.
• Says plainly that a crashed worker means a possible duplicate, and gives targets an idempotency key.
• Handles DST gaps and overlaps with a stated policy, and knows cron dialects differ.
• Derives the busiest minute instead of using an average, and names the managed alternative.

Follow-up questions

1. "Why not have one leader worker that assigns jobs to the others?" Answer: it works, but we'd need leader election, and the leader becomes a bottleneck and a single point of failure until a new one is elected. Conditional claims let every worker take work directly, with the database as the referee. At Round 1's 50 runs/s the claim conflicts cost almost nothing.

2. "A user edits a reminder from 9:00 to 9:30 while a worker is claiming the 9:00 run. What happens?" Answer: the edit sets next_run_at to 9:30. If the edit lands first, the claim's condition next_run_at = 9:00 fails and nothing runs at 9:00. If the claim lands first, the 9:00 run goes ahead and the edit, which is also conditional on the job being SCHEDULED, gets a 409 telling the user the reminder is running now.

3. "Why compute the next cron time from the scheduled time and not from now?" Answer: if a 02:00 job starts at 02:00:40 and we compute from now, a job like */1 * * * * drifts, and a slow run could make us skip an occurrence. From the scheduled time, every occurrence is exactly where the cron expression says; lateness is handled by the misfire policy, separately.

Interview gotchas from this round's wrong answers

---

Round 2 · Senior · "100M Active Jobs and the Top-of-the-Hour Stampede"

~40 min · Senior SDE (L6) · 1 region, 3 AZs · 100M active jobs · 500M runs/day: 5,787/s average, ~36.8K/s for 5 minutes after midnight UTC · dispatch P99 < 1 s · 99.99%

R2.0 Where We Left Off

This is what the candidate says aloud in the first 60 seconds of Round 2. If you're starting here, it's everything you need from Round 1.

Round 1 in 60 seconds. "We built a scheduler for one app: about 100K jobs, one-off reminders and cron jobs with time zones, 175K runs a day and 50 runs a second in the busiest minute. Jobs live in a DynamoDB table with next_run_at in UTC. Three stateless Fargate workers poll a sparse, sharded index for due jobs and claim each one with a conditional update that sets a lease. If a worker dies, the lease expires and a reaper returns the job, so a job can run twice; every call carries an idempotency key so the target can ignore repeats. Failures retry with exponential backoff and full jitter, then go to an SQS dead-letter queue. The next cron time is computed in the job's time zone from the scheduled time, with explicit rules for DST gaps and overlaps, and a misfire policy says what to do with runs missed during an outage. About $145 a month; honestly, at that size we'd buy EventBridge Scheduler. Open costs: polling one index doesn't scale, and nothing stops one slow target or one crowded minute from delaying everyone."

Architecture v1, compact

Synthesizing vector architecture diagram...

Round 1 in one picture: the table is the only shared state; workers find, claim, run, retry and reap.

Round 1 step summary

Open costs: every worker polls the same few index shards; all jobs share one pool of workers; a lease is checked only when the job finishes.

R2.1 The Scope Raise

Interviewer: "Every team in the company wants your scheduler. We're at 100 million active jobs and 500 million runs a day. The payments team schedules retries and settlement jobs; the analytics teams schedule thousands of reports. Payments must never wait behind reports."

Interviewer: "Some jobs now run for hours. Most targets are team webhooks, and some of them slow down badly under load. We want a job dispatched within a second of its time, P99. And it has to survive losing an AZ: 99.99%."

A scope raise is not the end of scoping. We ask back, and say what each answer changes.

Scope change

R2.2 What Breaks in the Round 1 Design

The order we fix it in: finding due jobs (2.1), isolating priorities (2.2), the midnight burst (2.3), stale workers (2.4), long jobs (2.5) and slow targets (2.6).

R2.3 New Requirements and API Additions

The job gains a priority and a dispatch window.

httpCopy
POST /v1/jobs HTTP/1.1
Content-Type: application/json
Idempotency-Key: 7b2e0c55-1a9d-4f3e-8f0a-3d6c2b1e9a70

{
  "schedule": { "type": "CRON", "cron": "0 * * * *", "time_zone": "UTC" },
  "priority": "DEFAULT",
  "dispatch_window_seconds": 300,
  "target": { "type": "HTTP", "target_id": "tgt_reports_rollup", "path": "/v1/rollups", "timeout_seconds": 60 },
  "payload": { "report": "hourly_sales" },
  "retry_policy": { "max_attempts": 5, "initial_backoff_seconds": 10, "max_backoff_seconds": 900 }
}

• dispatch_window_seconds: the job may start anywhere in [scheduled time, scheduled time + window). The default for new jobs is 300. 0 means strict: it needs a CRITICAL allowance (step 2.2).
• max_backoff_seconds is capped at 900 so every retry fits in an SQS message delay (15 minutes maximum).
• The target is a registered target (target_id), not a free URL. Registering it sets its owner, its base URL and its concurrency limits:

jsonCopy
{
  "target_id": "tgt_reports_rollup",
  "owner_team": "analytics-platform",
  "base_url": "https://rollups.analytics.internal",
  "max_concurrency": 200,
  "initial_concurrency": 50,
  "latency_slo_ms": 2000,
  "auth": { "type": "HMAC_SHA256", "secret_arn": "arn:aws:secretsmanager:us-east-1:111122223333:secret:sched-tgt-rollups" }
}

Long jobs run on the team's workers, which pull work.

httpCopy
POST /v1/task-queues/ledger-rebuild/tasks:poll HTTP/1.1
Content-Type: application/json

{ "worker_id": "ledger-worker-12", "wait_seconds": 20 }

jsonCopy
{
  "run_id": "job_7Q2M:2026-09-28T00:00:00Z",
  "epoch": 3,
  "lease_expires_at": "2026-09-28T00:00:31Z",
  "heartbeat_every_seconds": 10,
  "payload": { "ledger": "EU-2" },
  "idempotency_key": "job_7Q2M:2026-09-28T00:00:00Z"
}

httpCopy
POST /v1/runs/job_7Q2M:2026-09-28T00:00:00Z:heartbeat HTTP/1.1
Content-Type: application/json

{ "epoch": 3, "progress": { "rows_done": 1200000 } }

jsonCopy
{ "lease_expires_at": "2026-09-28T00:07:41Z", "cancel_requested": false }

A heartbeat with a stale epoch gets 409 Conflict with "reason": "EPOCH_SUPERSEDED", and the worker must stop at once (step 2.4). Completion is POST /v1/runs/{run_id}:complete with the epoch and an outcome.

Cancel while running. POST /v1/runs/{run_id}:cancel sets cancel_requested. A pulling worker learns it from its next heartbeat response. An HTTP call already in flight can't be recalled; if it succeeds anyway, the run is recorded as SUCCEEDED_AFTER_CANCEL, so nobody is misled.

Redrive. After the cause is fixed:

httpCopy
POST /v1/dlq:redrive HTTP/1.1
Content-Type: application/json

{ "filter": { "target_id": "tgt_reports_rollup", "failed_after": "2026-09-28T00:00:00Z" }, "max_per_second": 200 }

Redriven runs start a new attempt series under a new epoch, at a capped rate so a recovered target isn't flattened again.

R2.4 Design Evolution: Surviving the Stampede

Step 2.1: Scanning 100M Jobs for Due Ones Is Too Slow

Why two stores can disagree safely. The bucket is a hint; the conditional claim in DynamoDB decides. A member that's stale because its job was cancelled or rescheduled after loading fails the claim's condition (next_run_at = :scheduled) and is dropped. So:

• Cancel updates the table (the truth) and removes the member as a courtesy. If the loader re-adds it a moment later from a stale index read, the claim still fails. Correctness never depends on the bucket being clean.
• Missing members are the dangerous direction: a job in the table but not in any bucket never runs. Three layers stop that:
  1. The loader writes a marker key loaded:{017}:202609280000 after it finishes a shard-minute. Valkey deletes a sorted set when its last member is removed, so an empty bucket and a never-loaded bucket look the same; the marker tells them apart. When a minute arrives without its marker (a failover lost it), the dispatcher reads that shard-minute straight from due-index.
  2. One minute after each shard-minute's windows close, the dispatcher runs a straggler query on due-index for it. Claimed jobs have moved to their next minute's key, so anything still there was missed, and it's dispatched late. That's 256 × 1,440 = 368,640 small queries a day.
  3. Direct adds by writers cover jobs created after the loader passed their minute.

The {017} in the key is a hash tag: Valkey places a key by the part in braces, so all of shard 17's buckets and markers live on the same node, and one dispatcher talks to one node for them.

Sorted-set scores are doubles, exact for integers up to 2^53 ≈ 9.0 × 10^15. Epoch milliseconds are about 1.79 × 10^12, far below that, so scores are exact.

Who owns which shard? Each dispatcher holds a lease on its shards in a small DynamoDB table (one item per shard: owner, epoch, lease end), renewed every 3 seconds with a 10-second lease. If a dispatcher dies, its shards are claimed by others within about 10 seconds. Two dispatchers briefly owning one shard would send some members twice; the conditional claim turns the second copy into a no-op.

Synthesizing vector architecture diagram...

The table is truth, the buckets are a 2-hour cache of it, and the dotted path is how the dispatcher recovers anything the cache lost.

Primitive: Distributed Cache Patterns & Eviction · Database Sharding & Partition Keys

Step 2.2: Payments Wait Behind Reports

Which jobs are CRITICAL? Only strict jobs (window 0) from teams with a CRITICAL allowance. The allowance caps how many strict jobs may be due in the same second, platform-wide: 5,000. The API counts them per due second and rejects a strict job that would exceed its team's share (409 STRICT_ALLOWANCE_EXCEEDED, with the nearest second that has room). That cap is what makes "P99 < 1 s" provable for strict jobs: a pool sized for 5,000 runs a second can't be handed 50,000.

Primitive: Circuit Breaker, Bulkhead & Fault Tolerance

Step 2.3: At 00:00, 10M Jobs Fire at Once

The peak, stated once: with 10M due at 00:00, the dispatch rate is burst ÷ window:

A 60-second jitter doesn't lower the peak below the "first minute" rate: it only makes the minute uniform. The window length sets the rate.

Why a queue at all, rather than having dispatchers call targets directly? A direct call ties the dispatcher's pace to the slowest target and has nowhere to put a burst: the target either absorbs 33K calls a second or fails them. With a queue in between, dispatchers stay fast and precise, executors drain at the rate targets can take, and executors can be scaled and fail independently. The price is one more hop and one more component to watch (queue age). What happens when an executor dies halfway through a message is in R2.5.

Drill: Message queue order pipeline

Step 2.4: A Paused Worker Finished a Job Someone Else Already Re-Ran

Synthesizing vector architecture diagram...

Worker A's writes to our table fail on the epoch. Its late call to the target is harmless only because the target checks the idempotency key or the token.

Why an epoch and not a worker ID? Round 1's completion was conditional on lease_owner = me. Two holes: a restarted process can come back with the same worker ID, and a worker can hold two claims on the same run over time (claimed, lost, reclaimed by itself). An epoch is unique per claim. And it's a number, so a downstream system can compare "higher wins"; worker IDs have no order.

Why not just optimistic concurrency at the database, with no leases at all? That's partly what we do: every write is a conditional write on a version (the epoch, or next_run_at for the job item). Optimistic concurrency works well when conflicts are rare, and here they are: a few claimers per run. Under heavy contention it would cause a storm of failed writes and retries. What version checks alone can't do is tell anyone that a worker has died: the lease adds the expiry, the reaper acts on it, and the epoch makes the reaper's takeover safe. An external lock service would add a component and a network hop and still need the same fencing token at the resource.

Primitive: Distributed Locks & Leases · Drill: Distributed lock fencing token

Step 2.5: Long Jobs Look Dead and Get Reclaimed

Why the lease index has 16 shards. Each heartbeat changes the index's sort key, which costs a delete and a put in the GSI: 2,000 × 2 = 4,000 index writes a second. In one partition-key value that's four times what one partition serves; over 16 it's 250 each.

An adaptive reaper. A reaper that reclaims everything it finds is dangerous exactly when many leases expire at once, and the most common cause of that isn't 20K dead workers: it's our heartbeat API or its network having an outage. Reclaiming every lease would start a second copy of every running job. So:

Step 2.6: A Target Is Slow and We're Making It Worse

Why not just very short timeouts? A 50 ms timeout on every call would free executor slots quickly, but a healthy service with normal jitter would fail a share of good calls, and each false timeout becomes a retry, which adds load. A timeout sets how long one call may take; the breaker and AIMD decide whether to call at all. We set timeouts per target from its own latency SLO (here 2 s), and let the breaker cut off a target that's truly down.

Why executors run out of slots without this. Each executor holds at most 500 calls in flight. If a target slows from 200 ms to 8 s, each of its calls holds a slot 40 times longer: at 1,000 calls a second to that target, it would hold 1,000 × 8 s = 8,000 slots, the whole default pool, and every other target's jobs would wait behind it. The per-target limit caps that target at L slots, so the slowdown stays its own problem.

Go deeper: SQS fair queues. In a standard SQS queue, if messages carry a MessageGroupId (here, the target), SQS watches how many messages from each group are in flight; when one group has far more than the others, it prefers returning messages from the other groups, which keeps their waiting time low while the heavy group's backlog drains. It doesn't limit any group's rate and doesn't enforce order. It's a useful second line behind AIMD for the same "one target hogs the pool" problem, and Round 3 uses it for tenants.

Primitive: Distributed Rate Limiting · Circuit Breaker, Bulkhead & Fault Tolerance · Drill: Circuit breaker cascading thread stall

Round 2 Step Summary

R2.5 Architecture v2

Synthesizing vector architecture diagram...

Read it as three concerns. When: loaders copy the next 2 hours into Valkey buckets; dispatchers move due members into priority queues. Who: executor pools claim runs in DynamoDB with epochs; team workers claim long jobs through the API and heartbeat. What if it fails: retries through delayed messages, the DLQ, and the reaper. Every finished run flows to S3 through the table's stream.

Tables (one DynamoDB table, jobs, holds both item types)

A one-off job keeps its single run on the job item itself, so it doesn't pay for a second item.

The task state machine (a run)

Synthesizing vector architecture diagram...

Every arrow is a conditional write, and every arrow into RUNNING raises the epoch, which is what fences the previous holder.

The executor's rules (short webhook jobs, timeout at most 5 minutes)

1. Receive up to 10 messages with long polling, and process them concurrently. Messages from one receive share one visibility clock that started at the receive; working through them one after another would let the last ones reappear and run twice.
2. Take a target slot (step 2.6); if none, delete and re-send with a delay.
3. Claim the run first: create or update the run item IF it doesn't exist, or is in RETRY_WAIT, or is RUNNING with a lease that ended more than 5 s ago. The claim raises the epoch and sets the lease to now + timeout + 60 s.
4. Then advance the job: IF next_run_at = :scheduled AND job_state = ACTIVE, set the next occurrence (or DONE for one-offs), with ReturnValues: ALL_NEW to get the target and payload in the same call. If the next occurrence is within 2 hours, add it to its bucket. If a crash happens between steps 3 and 4, the job is still due; the next claimer finds the run item and finishes the advance. If the condition fails, the executor reads the job: if it has already moved past this occurrence (a retry, or a claimer that crashed after advancing), it carries on; if the job was cancelled, paused or rescheduled away from this time, the run is marked CANCELLED and nothing is called.
5. Call the target with Idempotency-Key and X-Fencing-Token.
6. Complete IF epoch = :e, then delete the message.
7. If the claim failed because another executor holds a live lease, don't delete the message; hide it until just after that lease ends. If that holder dies, the message comes back and the next executor reclaims the run. Delete a message only when the run is finished or we finished it.

An executor that crashes halfway through a message never deletes it, so after the visibility timeout (timeout + 60 s) the message reappears and another executor reclaims the run with epoch + 1. A message that has crashed executors 10 times moves to a poison-message queue (maxReceiveCount = 10), separate from our DLQ of failed runs.

Retries. On a retryable failure the executor sets RETRY_WAIT with attempt + 1 (IF epoch = :e), sends a new message with DelaySeconds equal to the backoff (at most 900 s), and deletes the old one.

Trace 1: the midnight burst

Synthesizing vector architecture diagram...

Across all shards, about 33.3K windowed jobs a second leave the buckets from 00:00:00 to 00:05:00, plus 3,449 a second of background work.

Trace 2: a zombie rejected by fencing is the sequence in step 2.4: the reaper raises the epoch, and every later write by the paused worker fails its condition.

Trace 3: a slow target throttled

Synthesizing vector architecture diagram...

The target sees its load cut in half within a second of slowing down, and nothing at all while its breaker is open. Its own jobs wait in delayed messages; other targets' jobs never notice.

History. Every finished run is a change on the table, so the table's DynamoDB stream carries it. A Lambda function reads the stream, keeps only the changes into a final state (an event filter drops the rest before the function runs), packs them into newline-delimited JSON records of up to about 1,000 KB, and sends them to Amazon Data Firehose, which writes GZIP files to S3. Packing matters: Firehose bills each record rounded up to the next 5 KB, so 1 KB records sent one by one would be billed as 5 KB each. The lake answers "what happened to my job last month" with Athena, and holds 13 months.

R2.6 Numbers and Cost

Targets

Where the 500M runs come from (the interviewer's shape, plus our assumptions for the rest)

Dispatch latency budget (steps happen one after another, so they add up; each figure is an assumption to confirm in load tests)

This holds only if a free executor is waiting when the message arrives, which is why pools are sized for the peak, not the average.

Valkey buckets

Executors (assumption to load-test: one 1-vCPU, 2 GB Graviton task sustains 500 runs a second of I/O-bound HTTP work)

Why × 1.5: losing one AZ of three leaves two-thirds of the tasks. The pools are separate bulkheads, so the math must hold for each pool on its own, rounding up: HIGH and LOW 15 × 1.5 = 22.5 → 23 (23 × 2/3 ≈ 15.3, still ≥ 15; 22 would leave 14.7), DEFAULT 45 × 1.5 = 67.5 → 68 (68 × 2/3 ≈ 45.3 ≥ 45). Off-peak, the background 3,449/s needs 7 tasks; 12 keeps one per AZ per pool with room. The burst comes every hour (≤ 9.5M at other hours: 9.5M ÷ 300 + 3,449 ≈ 35.1K/s), so scheduled scaling runs the 114 from :57 to :08, 11 minutes of every hour.

Long jobs: 20K running at once (assumption), heartbeats every 10 s = 2,000/s.

DynamoDB writes (one write unit per 1 KB; moving an item in a GSI costs 2)

Average: 3.04B ÷ 86,400 ≈ 35.2K writes a second. At the midnight peak: 33.3K × 5 (the burst's runs) + 3,449 × 5 (background) + 6,000 (heartbeats) ≈ 190K writes a second. We set the table's and indexes' warm throughput above that, so DynamoDB has the partitions ready before the first midnight. On-demand tables also have a default maximum of 40,000 write request units a second per table and per GSI (adjustable), so we request a quota increase to cover ~190K before launch.

On-demand or provisioned? Provisioned capacity costs $0.00065 per write unit per hour, which is $0.00065 ÷ 3,600 = $0.18 per million writes if every unit is used every second; on-demand costs $0.625 per million. Provisioned wins only above 0.18 ÷ 0.625 ≈ 29% average utilization. Provisioned flat at ~190K, we'd use 35.2K on average, 18.5%: far worse. Provisioned that follows the spike is cheaper on paper: ~190K for the 11 minutes around each top of the hour and ~40K otherwise averages (190K × 11 + 40K × 49) ÷ 60 ≈ 67K write units, 67,000 × $0.00065 × 730 ≈ $32,000 a month, well below on-demand's $57,000. DynamoDB allows enough decreases for that (four at the start of a day, then one per hour, up to 27 a day). The catch is the increase: before :57 every hour, the table and every GSI must go from ~40K to ~190K, a large increase isn't instant and isn't guaranteed to finish on time, and if it's late the burst is throttled and the 1-second SLO is broken for everyone at the worst moment. Provisioned wins only with pre-scaling that reliably completes every hour. We take on-demand, with warm throughput for the spike, pay about $25K a month for that certainty, and revisit when longer windows flatten the load (R2.7).

Storage

S3 is designed for 99.999999999% (11 nines) durability of objects. That figure is S3's, for the history files; it says nothing about whether a job runs, which is what the durability target above is about.

Rough monthly cost (us-east-1 list prices; check the AWS Pricing Calculator before quoting)

Three lessons:

• DynamoDB writes are 85% of the bill. Every run costs about five writes, and the index moves are two of them. The biggest levers are fewer writes per run and a flatter load (R2.7).
• The fleet is cheap because it's I/O-bound and scaled to the hour. Running the 114 windowed executors all day would cost 114 × 730 × $0.0395 ≈ $3,290 instead of about $890.
• Firehose's 5 KB rounding would have made its line five times bigger. Packing records is a one-line design decision worth about $1,700 a month.

R2.7 Trade-Offs

Where the timers live

Honestly, the index-only design would work at this scale, and it's simpler. We keep the buckets because they turn every dispatcher pass into one in-memory range read with exact per-job scores (offsets included), and they keep the hot midnight read path off DynamoDB, which is already absorbing ~190K writes a second. The index remains the fallback for any bucket we lose. SQS delays are right for what they're good at: retry backoff up to 15 minutes.

Push to webhooks vs workers pulling

We support both, because the scope asked for both.

The size of the window

The window is a product decision and the biggest cost lever we have. A good next step: default LOW-priority jobs to a 30-minute window, and show teams what their window costs.

Buy: EventBridge Scheduler at this scale? List price: 15B invocations a month × $1.00 per million ≈ $15,000, far less than our $67,000. What stops us: 60-second precision (we need P99 < 1 s), no priority classes or reserved capacity, no heartbeat-and-lease model for long jobs, and no per-target AIMD. Its default quotas (10M schedules, 1,000 invocations a second) are adjustable, AWS says to billions of schedules and tens of thousands of invocations a second, so quotas alone wouldn't decide it. If the business dropped the 1-second requirement, buying would be the right call for most of the jobs. COST 11

R2.8 Failure Modes

Primitive: Message Queues vs Event Streams

R2.9 Production Gotchas

1. All timers in one sorted set

• Symptom: one Valkey node at 100% CPU at midnight while the others idle; dispatch lag in minutes.
• Cause: a single key holding every timer; one key lives on one node and one thread.
• Fix: per-minute, per-shard buckets with hash tags (step 2.1).

2. No fencing on heartbeats

• Symptom: a job reclaimed after a pause keeps both workers heartbeating "successfully", and two results are recorded.
• Cause: heartbeats conditional only on the run ID.
• Fix: every heartbeat and completion is IF epoch = :e AND run_state = RUNNING (step 2.4).

3. Synchronous webhook calls inside the dispatcher

• Symptom: one slow target delays thousands of unrelated jobs by seconds.
• Cause: the dispatcher waits on HTTP calls between bucket passes.
• Fix: dispatchers only enqueue; executors call targets under AIMD limits (steps 2.3, 2.6).

4. Non-idempotent jobs

• Symptom: after an AZ event, some customers got two invoices.
• Cause: the target ignored the Idempotency-Key.
• Fix: make the key part of the target's contract, and test it: our staging environment deliberately delivers 1% of calls twice.

5. Deferring with ChangeMessageVisibility

• Symptom: healthy jobs for a throttled target end up in the poison-message queue.
• Cause: each deferral is another receive, counted toward maxReceiveCount.
• Fix: defer by deleting and re-sending with a delay (step 2.6).

6. Random jitter instead of hashed offsets

• Symptom: after a bucket reload, some jobs run twice in one hour: once at their old random time, once at the new one.
• Cause: a new random offset on every load gives the same run two dispatch times.
• Fix: offset = hash(job_id) mod window, stable across reloads and the same every hour (step 2.3); and the conditional claim rejects the second copy anyway.

R2.10 Pillar Check

Security in detail. A job can only name a registered target, and registering one requires the owning team's approval, so a team can't point jobs at another team's admin endpoint or at the instance metadata address. Every call is signed with an HMAC of the body, the timestamp and the idempotency key using the target's secret from Secrets Manager, so the target can reject calls that didn't come from us or that were replayed later. Executors have one IAM role: receive and delete on their own pool's queue, send to the delay path, conditional updates on the jobs table, read the target secrets. Dispatchers can send to queues but can't touch the table except their shard leases. The API authenticates callers by IAM identity and scopes each team to its own jobs.

Operations in detail.

R2.11 Round 2 Rubric and Follow-Ups

What a strong senior (L6) answer adds over L5

• Derives the peak from how cron jobs cluster, rejects the uniform multiplier, and shows the window sets the rate.
• Keeps the durable table as the truth and treats the in-memory buckets as a rebuildable cache, with a way to detect what the cache lost.
• Uses bulkheads, not a priority field, to protect critical work, and caps strict jobs so the SLO is provable.
• Explains fencing honestly: it protects our records; external effects need the target to check the key or the token.
• Designs heartbeats and a reaper that won't turn our own outage into 20K duplicate jobs.
• Protects targets with AIMD and a breaker, and knows the SQS receive-count trap.
• Finds the cost driver (writes per run) and the lever (the window).

Follow-up questions

1. "Can a job run early?" Answer: not by design. Offsets only move jobs later, and an executor won't claim a run whose scheduled time is still ahead by its own clock. The remaining risk is a worker whose clock runs fast; we alarm on clock offset above 1 s, and a job that must never be early by even a second should be strict, where the only delay is dispatch.

2. "How would you add a 'run at most once' option for a team that would rather miss a run than repeat it?" Answer: mark the run STARTED with a conditional write before calling the target, and never reclaim a STARTED run: if its executor dies, the run becomes UNKNOWN and goes to the team's DLQ instead of being retried. That's at-most-once: some runs will be lost, and the team must accept that in writing.

3. "Your executors call a target that takes 4 minutes. What visibility timeout do you set, and why does it matter?" Answer: the job's timeout plus a margin, here 5 minutes. Shorter, and the message reappears while the first executor is still working; the second executor's claim fails on the live lease, and it hides the message until after that lease ends (rule 7), so nothing breaks, but we waste receives. Longer, and a crashed executor's run waits longer to be retried.

Interview gotchas from this round's wrong answers

---

Round 3 · Architect · "Workflows, Tenants, and Regions"

~45 min · Principal (L7) · 3 regions · 5,000 tenants · 1B job runs + 500M workflow steps a day · 1.7B pending timers · survives a region with duplicates bounded by replication lag

R3.0 Where We Left Off

This is what the candidate says aloud in the first 60 seconds of Round 3. If you're starting here, it's everything you need from Round 2.

Round 2 in 60 seconds. "We run the company's scheduler: 100M active jobs, 500M runs a day, 5,787 a second on average, in one region across three AZs. The worst moment is midnight UTC, when 10M jobs are due at once; we derived the peak from that, not from a multiplier. Non-strict jobs get a forward-only dispatch window, 5 minutes by default, with an offset hashed from the job ID, which turns the burst into about 36.8K runs a second. Strict jobs need a CRITICAL allowance capped at 5,000 a second. DynamoDB is the source of truth; a due-index keyed by minute and shard feeds 2-hour Valkey buckets, with markers and straggler queries to catch anything the cache loses. Dispatchers move due jobs into four priority queues with separate executor pools. Every run has an epoch: every write is conditional on it, and targets get it plus an idempotency key. Long jobs run on team workers with 10-second heartbeats and an adaptive reaper. AIMD limits protect each target. About $67K a month, 85% of it DynamoDB writes. Open costs: jobs have no memory of each other, every team shares one pool, and it all lives in one region."

Architecture v2, compact

Synthesizing vector architecture diagram...

Round 2 in one picture: the table is the truth, the buckets make time precise, the queues and pools isolate priorities, and epochs fence stale workers.

Round 2 step summary

Open costs: a multi-step process is a chain of unrelated jobs; one team's flood competes with everyone's; a region outage stops every timer.

R3.1 The Scope Raise

Interviewer: "We're turning the scheduler into a product that outside customers pay for. They don't just want jobs: they want workflows. Charge a card, reserve stock, ship; if shipping fails, release the stock and refund the card. Some workflows wait days for a signal, like 'the courier picked it up'."

Interviewer: "We'll have thousands of tenants. One of them already has 50 million jobs, almost all at midnight, and it must not delay anybody else. We're going into three regions. If a region fails, timers must still fire, and when the region comes back we can't have a flood of duplicate charges. And finance wants to know what each tenant costs us."

Scope change

R3.2 What Breaks in the Round 2 Design

The order we fix it in: durable workflows (3.1), tenant isolation (3.2), regions (3.3), the contract (3.4), metering (3.5), and build or buy (3.6).

R3.3 New Requirements and API Additions

A workflow definition (declarative; the engine interprets it)

yamlCopy
workflow: order_fulfillment
version: 7
region_policy: HOME_ASYNC
steps:
  - id: charge_card
    activity: { task_queue: payments, type: CHARGE }
    timeout: 30s
    retry: { max_attempts: 5, initial_backoff: 2s, max_backoff: 5m }
    compensate_with: refund_card
  - id: reserve_stock
    activity: { task_queue: inventory, type: RESERVE }
    timeout: 30s
    retry: { max_attempts: 5, initial_backoff: 2s, max_backoff: 5m }
    compensate_with: release_stock
  - id: wait_for_pickup
    wait_for_signal: { name: picked_up, timeout: 3d }
    on_timeout: compensate
  - id: ship
    activity: { task_queue: shipping, type: CREATE_SHIPMENT }
    timeout: 60s
    retry: { max_attempts: 8, initial_backoff: 5s, max_backoff: 15m }
compensations:
  - id: release_stock
    activity: { task_queue: inventory, type: RELEASE }
    retry: { max_attempts: unlimited, initial_backoff: 10s, max_backoff: 1h }
  - id: refund_card
    activity: { task_queue: payments, type: REFUND }
    retry: { max_attempts: unlimited, initial_backoff: 10s, max_backoff: 1h }

Start a workflow (the caller picks the ID, so a retried start is recognized)

httpCopy
POST /v1/workflows HTTP/1.1
Content-Type: application/json
X-Tenant-Id: tnt_4411

{ "workflow_id": "order-88213", "definition": "order_fulfillment", "version": 7, "input": { "order_id": 88213, "amount_cents": 4599 } }

jsonCopy
{ "workflow_id": "order-88213", "run_id": "wr_01JA0M3", "status": "RUNNING", "home_region": "us-east-1" }

Send a signal (deduplicated by signal_id)

httpCopy
POST /v1/workflows/order-88213/signals/picked_up HTTP/1.1
Content-Type: application/json
X-Tenant-Id: tnt_4411

{ "signal_id": "courier-evt-5521", "payload": { "courier": "ACME", "at": "2026-09-30T14:02:00Z" } }

Per-tenant quotas

jsonCopy
{
  "tenant_id": "tnt_4411",
  "cell": "use1-shared-3",
  "quotas": {
    "job_runs_per_second": 2000,
    "workflow_steps_per_second": 1000,
    "strict_jobs_per_second": 50,
    "pending_timers": 20000000,
    "api_requests_per_second": 500
  },
  "default_region_policy": "HOME_ASYNC",
  "home_region": "us-east-1"
}

Region policies (chosen per workflow or job; the price differs)

Status codes gain 409 WORKFLOW_ID_IN_USE, 422 NONDETERMINISTIC_DEFINITION_CHANGE (a new version must not change steps that running workflows already recorded), and 429 with "scope": "tenant" when a tenant is over its quota.

R3.4 Design Evolution: Durable Workflows Across Tenants and Regions

Step 3.1: A 3-Step Order Workflow Failed at Step 2

Writing an event safely. The history uses items keyed PK = WF#<workflow_id>, SK = EV#<epoch>#<sequence>, both zero-padded (EV#0007#00000042) so string order equals number order. A state item (SK = STATE) holds next_seq, the status, pending timers, the owning region's epoch, and the sequence at which each epoch took over. The epoch is in the key so that a region returning after a failover can't occupy sequence numbers the new owner needs: its late appends land under the old epoch's prefix, and replay reads each epoch only up to the point where the next one took over. An engine host appends event 42 with a PutItem conditional on attribute_not_exists(SK), then updates the state item IF next_seq = 42. If it crashes between the two, event 42 exists and next_seq is still 42; the next host sees that, finishes the state update, and moves on. It's the same "write the record, then advance the pointer, both idempotent" pattern as Round 2's run-then-job claim. Two hosts racing to append event 42 can't both succeed: the key is unique.

Determinism. Replay only works if the same history always produces the same decisions. So a definition's choices may depend only on recorded values: step results, signal payloads, the recorded start time. Never on the current wall clock, a random number, or a fresh read from another service; those must be recorded as events first. A code-based engine (Temporal, for example) enforces the same rule on workflow code. And a new version of a definition must not change steps that running workflows have already recorded; running workflows keep the version they started with.

When a compensation fails too. A refund can fail: the payment provider is down. Compensations retry with backoff for as long as it takes (max_attempts: unlimited, backoff capped at 1 hour), and each carries an idempotency key (order-88213:refund_card) so a repeat can't refund twice. If a compensation still hasn't succeeded after a tenant-set deadline (say 24 hours), the workflow moves to COMPENSATION_STUCK: it goes to the tenant's DLQ, pages their on-call, and appears on a reconciliation report that compares our history with the provider's records. Money isn't lost silently: the history says exactly which charge has no refund yet.

Why a saga and not two-phase commit? Two-phase commit (2PC) needs every participant to lock its data, vote, and wait for the coordinator's decision. If the coordinator fails after the vote, participants stay locked until it recovers. Across services owned by different companies, over days, with a payment provider that doesn't support 2PC at all, that blocking is unacceptable. A saga never holds locks across steps; the price is that other readers can see the in-between state (card charged, stock not reserved), so each step's effect must be acceptable to see, and each must be undoable.

Synthesizing vector architecture diagram...

Every decision comes from the history. A crash anywhere just means another engine host replays the same events and continues from the first step without a result.

Primitives: Two-Phase Commit & Saga Orchestration · Event Sourcing & CQRS · Drill: Saga orchestration compensating failure

Step 3.2: One Tenant's Flood Delays Everyone

Moving a tenant to another cell works like a region takeover (step 3.3) on a small scale: the tenant's timers are copied into the new cell's tables; the old cell stops dispatching for that tenant at a set instant under the tenant's current epoch; the new cell starts under epoch + 1; conditional claims reject anything the old cell still sends.

What about a query across all tenants, like a platform-wide "failed runs by region" report? We never scatter a query across cells' live tables. Every cell streams its finished runs and workflow events to the S3 history lake (R2.5), which we query with Athena. The report is minutes behind and costs nothing on the serving path.

Primitives: Circuit Breaker, Bulkhead & Fault Tolerance · Database Sharding & Partition Keys · Drill: Sharding tenant hotspot

Step 3.3: A Region With 1B Pending Timers Failed

Why the leases use our clocks, not DynamoDB's. DynamoDB conditions can't read the server's time, and conditions on MREC tables are checked against the local replica only. So the safety rule is built from our own clocks with margins on both sides: the old owner stops 5 s before the lease ends by its clock, and the new owner starts 5 s after by its clock. With clock skew under 5 s (we alarm at 1 s), there is a gap of at least a few seconds when nobody owns the group, never an overlap. For STRICT workflows we get more: their state tables are MRSC too, so every conditional write, including the epoch check, is evaluated against the latest version in all regions, and a stale owner's write simply fails.

Why not make every workflow STRICT? Because it's paid for on every write, all day: each write waits for a round trip to another region (tens to a couple of hundred milliseconds, depending on the regions), MRSC tables don't support TTL, so cleanup becomes our job, and there's still no escaping duplicates of external calls that were in flight during the failure. We offer it for the workflows that need zero lost state (payments), and keep HOME_ASYNC as the default.

How many duplicates? (numbers from R3.6)

Each repeat reaches a tenant with the same idempotency key as the first, so a tenant that honors the key sees no double effect. When us-east-1 returns, its unreplicated writes replicate out. Its events are keyed under the old epoch (EV#0007#…), so they never collide with the new owner's appends (EV#0008#…), and replay ignores anything under epoch 7 past the takeover point; a reconciliation job lists, per tenant, every step that ran under the old epoch after the takeover point, so the tenant can check it.

Synthesizing vector architecture diagram...

The old owner stops before the lease ends; the new one starts after it. The 15-second gap costs us late timers, not duplicate ones. What us-east-1 did between 12:00:02 and 12:00:10 may not have replicated, and that is the duplicate window.

Primitive: Cloud Disaster Recovery & Multi-Region Active-Active · Drill: Replication multi-region consistency

The drill's two questions, answered here. A booking visible in one region and not another is replication lag plus a claim checked against a local copy: exactly why we never let two regions own the same group, and why the takeover condition runs in the strongly consistent ownership table. Why not replicate every write synchronously? Because every write would pay a cross-region round trip and stop when another region is unreachable; we scope that cost to the STRICT workflows that need it and to the tiny ownership table.

Step 3.4: "Exactly Once?"

AWS draws the same line. Step Functions Standard workflows follow an exactly-once model where tasks and states are never run more than once unless you configure Retry; asynchronous Express workflows are at-least-once, and synchronous Express workflows at-most-once. Even "exactly-once" there means the workflow won't start a task twice; a task that calls an outside API and times out still leaves the same question for that API.

Primitive: Database Isolation Levels, ACID & Concurrency Anomalies

Step 3.5: What Does Each Tenant Cost?

The meter records are counted once per engine host per minute and keyed (tenant, region, host, minute), so a record re-sent after a crash overwrites itself in the daily rollup instead of adding to it.

Step 3.6: Build or Buy?

The recommendation, with its conditions. We are selling a scheduling product, the volume is large, and we need three-region failover with per-tenant fairness that none of the managed options gives us directly. Our list cost of about $9 per million steps is well below the managed alternatives at this volume, even after a team costing a few million dollars a year. So: build, and consider building on the open-source Temporal server rather than from scratch. For an internal platform at a twentieth of this volume, the same table says buy Step Functions Standard, whose exactly-once semantics and one-year limit fit most business workflows, and spend the team elsewhere. COST 11

Round 3 Step Summary

R3.5 Global Architecture

Synthesizing vector architecture diagram...

Any region's API accepts a request and forwards it to the region that currently owns the workflow's placement group. Each region runs its own cells; data for HOME_ASYNC and STRICT workflows exists in all three regions, but only the owner of a group acts on it. The small ownership table is the only thing every region must agree on synchronously.

Where each piece lives

Trace 1: a saga with compensation is the sequence in step 3.1.

Trace 2: a region failover is the sequence in step 3.3, followed by recovery:

Synthesizing vector architecture diagram...

Trace 3: a tenant flood contained

Synthesizing vector architecture diagram...

T's midnight never touches the shared cell. Inside a shared cell, a tenant that bursts past its quota is pushed later in its own buckets and ranked behind quieter tenants in the fair queues.

R3.6 Numbers and Cost

Targets

Volumes (the interviewer's figures; the rest are our assumptions)

History growth

A workflow that runs for months would grow its history without limit, so a definition can continue as new: close this execution and start a fresh one with the current state as input, and an empty history. Hosted engines cap histories for the same reason: Temporal, for example, warns at 10,240 events or 10 MB and terminates at 51,200 events or 50 MB. We cap ours at 10,000 events or 10 MB (our choice).

DynamoDB writes (home region first; replicated writes are billed as replicated write units, at the same list price as ordinary writes since November 2024)

Replication volume: 16.7B replicated writes a day of items averaging about half a kilobyte, roughly 8 TB a day crossing regions. DynamoDB doesn't charge data transfer for global-table replication; the cost is the replicated write units. If we replicated ourselves instead, the far side would still pay the same writes, plus inter-Region transfer, which is $0.02/GB out of us-east-1 and differs by Region (it's higher out of several Asia Pacific Regions), so check each pair.

Failover headroom. When a region fails, its groups are split between the two survivors. Each region's compute must cover its own load plus half of the largest region it might inherit:

That 72.5% overhead applies to what we must pre-provision: compute and Valkey. DynamoDB on-demand follows the load (with warm throughput set ahead), and the survivors already hold replicas of the failed region's data. On-demand tables default to a maximum of 40,000 write request units a second per table and per GSI; our busiest job tables need far more (~190K at the top of the hour, and more in a survivor after a failover), so we raise that quota for every table, in every replica Region, before launch.

Failover timing (from step 3.3): a failure just after a renewal leaves 20 s on the lease, and takeover waits 5 s more: ~25 s before a survivor owns the groups. Then, per survivor: overdue timers ~25 s × 9,028/s ÷ 2 ≈ 113K, plus the next 10 minutes 9,028 × 600 ÷ 2 ≈ 2.7M timers loaded at 50K/s ≈ 55 s. Timers are back on schedule about 1.5 minutes after the failure, inside the 2-minute target.

Rough monthly cost (us-east-1 list prices applied everywhere for simplicity; Tokyo and Ireland prices differ, so check the AWS Pricing Calculator before quoting)

Cost per unit

Three lessons:

• Replication is the bill. 62% of all writes are replicas. A job costs 2.4× more per run than in Round 2 almost entirely because it's written in three regions.
• The levers are per policy. Replicating to one partner instead of two cuts replicated writes in half; jobs that can wait out a regional outage can be SINGLE_REGION and cost a third; longer windows let job tables move to provisioned capacity at ~$0.30 instead of $0.625 per million. Reserved capacity can't be bought for replicated write capacity, so it only helps the home-region share.
• Tenants must see this. A STRICT workflow and a SINGLE_REGION one are different products at different prices; metering (step 3.5) makes that visible.

R3.7 Trade-Offs

Closing the loop on the loop's question. "How do we run every job at the right time, and make it safe when machines fail and a job runs twice?"

• Round 1: at the right time within a minute, with at-least-once execution and an idempotency key.
• Round 2: at the right time within a second, where "right time" is honestly redefined for 10M simultaneous jobs as "within your window", and a stale worker can't touch our records.
• Round 3: our own state changes happen exactly once, within an owner and across regions for STRICT; everything we deliver to tenant code happens at least once, with a key that makes it safe; and after a region failure the repeats are bounded by replication lag, counted, and reported.

R3.8 Failure Modes

R3.9 Runbook

Signals, per cell and per tenant OPS 8 · REL 6

Procedure: a stampede bigger than planned

1. Confirm it's a known top-of-hour burst: bucket sizes for the coming minutes, per tenant.
2. Check the executor pools were pre-scaled and that warm throughput covers the new peak; raise both if not.
3. If a tenant is over quota, its members are already being pushed later; if the burst is inside quotas and still too big, lengthen LOW windows for that minute (forward only) and tell the affected tenants.
4. Never shorten a window or run anything early.

Procedure: redrive after a fix

1. Confirm the cause is fixed with a handful of manual redrives.
2. Redrive the rest through the redrive API with max_per_second well below the target's normal rate; AIMD will raise it if the target is healthy.
3. For the poison-message queue (messages that crashed executors), redrive with SQS's message move task once the executor bug is fixed.

Procedure: evacuate a region (planned, for a degraded region)

1. Stop placing new tenants in it. 2. Move its placement groups one at a time: the owner drains, waits for replication latency to reach its normal level, then hands the lease over under epoch + 1. 3. Watch dispatch lag in the receiving regions after each group. 4. Leave the region passive until the cause is understood; fail back the same way.

Game days. Monthly, AWS Fault Injection Service pauses global-table replication for one region (it supports isolating a replica for both MREC and MRSC tables) and we confirm self-fencing, takeover and the reconciliation report. Quarterly, a full evacuation during business hours. Every surprise gets a blameless Correction of Error with owners and dates. REL 12 · OPS 11

Go deeper: CLI playbook

Plain commands an on-call engineer runs, one at a time. Replace the names with real ones.

textCopy
# 1. Depth, in-flight and delayed counts for one priority queue in one cell
aws sqs get-queue-attributes --queue-url https://sqs.us-east-1.amazonaws.com/111122223333/cell3-jobs-default --attribute-names ApproximateNumberOfMessages ApproximateNumberOfMessagesNotVisible ApproximateNumberOfMessagesDelayed

# 2. Replication latency from us-east-1 to eu-west-1 for one cell's history table
aws cloudwatch get-metric-statistics --region us-east-1 --namespace AWS/DynamoDB --metric-name ReplicationLatency --dimensions Name=TableName,Value=cell3-history Name=ReceivingRegion,Value=eu-west-1 --start-time 2026-09-28T00:00:00Z --end-time 2026-09-28T00:15:00Z --period 60 --statistics Average Maximum

# 3. Redrive the poison-message queue back to its source queue at a capped rate
aws sqs start-message-move-task --source-arn arn:aws:sqs:us-east-1:111122223333:cell3-jobs-poison --max-number-of-messages-per-second 200

# 4. Watch that redrive
aws sqs list-message-move-tasks --source-arn arn:aws:sqs:us-east-1:111122223333:cell3-jobs-poison

# 5. Raise a table's warm throughput before a known burst (indexes are set separately;
#    above the 40,000 write units/s on-demand default, raise the per-table quota first, in every replica Region)
aws dynamodb update-table --table-name cell3-jobs --warm-throughput ReadUnitsPerSecond=20000,WriteUnitsPerSecond=250000

# 6. Scheduled scale-out of an executor pool at :57 every hour
aws application-autoscaling put-scheduled-action --service-namespace ecs --resource-id service/cell3/executor-default --scalable-dimension ecs:service:DesiredCount --scheduled-action-name top-of-hour-out --schedule "cron(57 * * * ? *)" --scalable-target-action MinCapacity=68,MaxCapacity=90

Without --destination-arn, the move task sends messages back to the queue they originally came from, which is what we want for the poison-message queue.

R3.10 Pillar Check

R3.11 Round 3 Rubric and Follow-Ups

What an architect (L7) answer adds over L6

• Replaces job chains with a durable history and replay, and knows why decisions must be deterministic.
• Chooses sagas over two-phase commit for a reason, and plans for a compensation that fails.
• Isolates tenants with quotas, fair dispatch and cells, and has a plan for the tenant that outgrows a shared cell.
• Makes region failover safe without trusting DynamoDB's clock or local conditions: strongly consistent ownership, self-fencing by time with margins, and an honest duplicate window.
• States the exactly-once contract precisely, the way AWS does for Step Functions.
• Prices the system, finds the driver (replicated writes), and turns it into per-policy, per-tenant prices.
• Treats build vs buy as a volume-and-team decision, with the crossover point named.

Follow-up questions

1. "A tenant sends the picked_up signal at the same moment the 3-day timer fires. Which wins?" Answer: whichever event is appended first. Both try to append the next event number to the history; the key is unique, so one succeeds and the other retries on the next number. When the loser's host replays, it sees the winner's event and acts on that: if the signal won, the timer's event is recorded as ignored; if the timer won, the late signal is recorded and reported as arriving after the timeout. Either way the decision is made once, from the history.

2. "Why not run the ownership leases on DynamoDB TTL, so a dead region's lease item just disappears?" Answer: TTL deletes items in the background, typically within a few days of expiry, never at a deadline, so a lease could outlive its owner by days. MRSC tables don't support TTL anyway. Lease expiry must be a timestamp that readers compare against their own clocks, with margins.

3. "Your biggest tenant asks for its own region." Answer: it gets a dedicated cell in any of our regions today; a new region is a business decision priced from R3.6: its own cells, a partner region for replication, and headroom for failover. If it only wants its data kept in one region, SINGLE_REGION in its home region does that for the workflows it chooses, at the cost of waiting out that region's outages.

Interview gotchas from this round's wrong answers

---

Loop Closer: Interview Strategy for All Three Rounds

How to Run Each 60-Minute Round

For how to spend a single 45-minute round, see the 45-minute interview blueprint. Related loops: the distributed message queue goes deeper on queues, and the distributed rate limiter on protecting shared targets.

The Two Sentences That Matter Most

• Opening a round: "Before I design, let me ask a few scoping questions."
• When the scope is raised: "Here's what breaks in the current design, and here's the order I'll fix it in."

And the one sentence specific to this system: "We run at least once, make our own state changes exactly once with conditional writes, and give every target an idempotency key so a repeat does no harm."

Well-Architected Review Sheet

Rubric Across Levels