Priority Job Queue
Schedule durable background work with priorities, bounded retries, tenant fairness and explicit dead-letter recovery.
Schedule durable background work with priorities, bounded retries, tenant fairness and explicit dead-letter recovery. This worked design targets SDE-2; the scale figures below are exercise assumptions, not claims about a named company's implementation.
Clarify the prompt
| Ask the interviewer | Decision to record |
|---|---|
| Strict priority or weighted fairness? | Strict priority can starve low-priority work. |
| What side effects do jobs perform, and can the receiver deduplicate? | |
| What are retry deadlines and maximum attempts? | Delayed retries must not monopolize active capacity. |
Requirements and scope
The core deliverable is: Schedule durable background work with priorities, bounded retries, tenant fairness and explicit dead-letter recovery. The first design implements the APIs below and the state constraints in the data model. Agree the latency, freshness, retention and failure policy before adding infrastructure. Every successful acknowledgment must have an explicit meaning: accepted intent, committed state or completed external work. These are separate milestones.
Capacity and bottleneck reasoning
Assume 10,000 jobs/s at 1 KB each: 10 MB/s and 864 GB/day raw. At 200 ms average service time, 2,000 concurrent attempts sustain 10,000/s before overhead. Capacity must account for retries and per-dependency limits.
Keep average and peak demand separate. Add replication, indexes, retries and safety headroom to raw arithmetic before selecting capacity. Load-test the busiest ownership key and recovery traffic as well as uniform happy-path throughput.
APIs and data model
- POST /jobs {payloadRef,priority,requestKey,deadline} -> jobId
- POST /leases/claim {capabilities,limit} -> leased jobs and tokens
- POST /jobs/{id}/complete {generation,result}; POST /dlq/{id}/redrive -> audited attempt
job(job_id PK,tenant,priority,not_before,deadline,state,attempt,generation)
lease(job_id,generation,owner,expires_at); result(job_id UNIQUE,payload_hash)
dlq(job_id,reason,failed_at,redrive_generation)Authorize resource ownership at the API boundary; do not trust IDs or state supplied by a client. Bind retry identity to the caller and payload for mutating operations. Reject an incompatible replay instead of returning an unrelated stored result.
Component relationships
Read the diagram
Follow the labeled relationship panels; they are separate directed paths, not one global timeline.
Step-by-step design
1. Establish the authority
Persist job intent before acknowledging enqueue. Partition by tenant or workload while selecting among priority bands using weighted fair shares and aging. Enforce tenant admission limits so priority cannot become a noisy-neighbor bypass.
2. Make retries and concurrent work safe
A claim creates a lease generation; heartbeat renewals and completion require that generation. Workers checkpoint long work and acknowledge only after durable effect/result. A late worker cannot overwrite a newer result, but external effects still need receiver-side idempotency.
3. Scale and recover the critical path
Use exponential backoff with jitter and a retry budget. Invalid payloads fail permanently; transient failures retry until deadline or attempt limit. Redrive preserves original operation identity and records a new administrative generation.
Worked request and concurrency example
High-priority work receives 70% of capacity and normal work 30%, with unused capacity borrowed. Worker A claims J at generation 4, pauses and loses its lease. Worker B claims generation 5 and completes. A resumes and its completion is rejected. If both called an external API, that API must use J as its deduplication key; fencing the result row alone cannot undo duplicate side effects.
Failure and recovery walkthrough
A poison job repeatedly crashes workers. Quarantine after bounded attempts, retain a safe payload reference and error reason, and require correction before redrive. A downstream outage should reduce dispatch concurrency, not create an unlimited retry storm.
Read the diagram
This numbered trace follows one scenario; explain the durable evidence at each transition.
Deep dive: fair service is a scheduling policy
This original queue has three priority bands H, N and L. In one worker pool, the illustrative admitted policy offers three dispatch opportunities to H, two to N and one to L in each six-opportunity cycle. With unit-cost jobs and all bands eligible, twelve opportunities produce H=6, N=4, L=2. This is a guarantee about selection opportunities under these assumptions, not completion latency for arbitrary-duration jobs.
| Opportunity | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| Chosen band | H | H | H | N | N | L |
An empty band lends capacity to eligible work; define the borrowing rule. Within each band, round-robin active tenants before taking the next job. Admit only work within per-tenant/band limits. A tenant cannot bypass its quota by labelling every job critical. Long jobs need cost-aware deficit scheduling or separate resource classes; a count-based policy can otherwise give one tenant most CPU despite equal dispatch counts.
Aging and starvation limits
Under a stable admitted unit-cost workload, L gets at least one opportunity every cycle while continuously eligible. If H can monopolize all actual worker slots indefinitely, selection fairness cannot make L start. Bound execution duration, reserve capacity or preempt safely where supported. Aging may promote a job after a waiting threshold, but promotion must still obey tenant admission and resource isolation. Do not claim an unconditional maximum wait while arrivals exceed service or jobs run forever.
For 600 safe starts/s in the balanced example, L's nominal share is 100/s. A burst of 1,000 L jobs needs at least ten seconds of that share if no older L jobs exist. If new L arrivals are 80/s, the net drain is 20/s and the burst takes fifty seconds under a fluid approximation. Measure actual queue age and skew rather than treating ideal share as a p99 latency result.
Claims, renewals and completion share a generation
claim(job): atomically require ready, not_before <= authoritative_now
move to running; generation += 1; set lease deadline
renew(job, generation): require running, same current generation,
lease still eligible under the chosen policy
complete(job, generation): require running, same current generation,
lease still eligible; commit durable resultA lease reaper makes expired work eligible for a new attempt. A worker's local monotonic clock measures elapsed time, but a database deadline is compared under the authority's clock contract. Do not compare unrelated machine monotonic values. An old worker cannot renew or publish once a newer claim owns the job. Result publication and any local business effect need one supported atomic boundary or separate idempotency.
Read the diagram
Worker A claims generation 4 → A pauses beyond its lease → Worker B claims generation 5 → A stale completion is rejected → B commits result for the logical job
A database queue can claim candidates with FOR UPDATE SKIP LOCKED under a short transaction. Skipping locks gives an inconsistent selection view and may temporarily skip a ready older job; it is useful for queue-like claiming, not proof of strict global FIFO. The statement does not make a later external effect atomic. See the PostgreSQL SELECT documentation for the exact locking behavior.
Retry identity survives redrive
| Failure class | Policy | Identity consequence |
|---|---|---|
| Temporary dependency overload | Backoff/jitter within attempt and deadline budget | Same logical operation, new attempt |
| Invalid payload | Fail/quarantine without pointless repeated execution | Preserve diagnostic evidence |
| Lease lost after external call | Resolve same destination operation | New worker does not invent new intent |
| Administrative DLQ redrive | Validate correction and authorization; record redrive generation | Original business identity remains unless explicitly creating a new operation |
A poison job must not occupy the front of a partition forever. Quarantine with safe payload references and error reasons, and isolate its tenant/class. A downstream outage should reduce active dispatch, not enqueue an unbounded retry storm. Respect per-job deadlines; retrying obsolete exports forever is not useful reliability.
Commit and acknowledge the right boundary
If the worker writes an internal result then crashes before queue acknowledgement, redelivery should find the same result. If it acknowledges first and then crashes, required work can disappear. For external effects, receiver-side idempotency or a durable unknown-result path is still required. A scheduler's job row cannot fence a provider that does not understand its generation.
Monitor ready age by band/tenant, weighted share, running slots, expired leases, retries per operation, DLQ age and redrive outcomes. Rebuild due indexes from durable job state and throttle recovery. A control plane that reads only queue depth misses one starving tenant hidden behind a healthy aggregate.
Queue assessment: defend the admitted guarantee
Question: All three bands are continuously eligible and jobs have equal cost. What do twelve HHHNNL opportunities allocate?
Show answer and explanation
Answer: Six H, four N and two L selections. This is selection share under the stated pool and workload; completion latency depends on service time and occupancy.
Question: A's generation 4 effect timed out before B claimed generation 5. Does rejecting A's completion remove its possible provider effect?
Show answer and explanation
Answer: No. B must resolve the same provider operation identity. Local generation fencing and external idempotency protect different boundaries.
Question: Can an operator redrive with a new business key just to avoid a dedupe conflict?
Show answer and explanation
Answer: Not as ordinary recovery. That can repeat the effect. Preserve the original identity, reconcile it and record an intentional new operation only when business policy authorizes it.
Score one point for weighted selection, tenant isolation, lease-generation conditions, external-effect identity and bounded redrive. Change unit-cost jobs to a mix of 10 ms and 30 s work and explain why count-based fairness must change.
Decisions and alternatives
| Decision | Trade-off |
|---|---|
| Alternative 1 | Separate queues isolate priorities and dependencies but need a fairness scheduler. One global sorted queue is easier to inspect but becomes a shared contention point. |
| Alternative 2 | At-least-once leases give recovery. At-most-once claiming can lose work when a worker crashes after dequeue; choose it only for explicitly disposable tasks. |
Operational contract
Track oldest age per priority/tenant, runnable backlog, attempt amplification, lease loss and DLQ reason. Test lost acknowledgments, stale completions and a continuous high-priority flood with a low-priority sentinel job.
Choose alert thresholds from the agreed user-facing objective. Assign an owner for stuck work and a replay/repair procedure that preserves the original business identity. Bound queue depth, concurrency and recovery throughput so an outage does not produce an uncontrolled catch-up burst.
Foundation, senior and staff depth
- Foundation: Explain durable enqueue, claim and acknowledgement.
- Senior: Calculate weighted tenant shares and fence stale completion/renewal.
- Staff: Defend cost-aware scheduling, aggregate budgets and audited DLQ redrive.
Practice before revealing the answer
Spend 45 minutes: 5 clarifying scope, 7 on capacity/APIs/state, 12 on the first architecture, 15 on the concurrency and failure examples, and 6 on trade-offs and operations. Draw your own design before comparing it with this chapter.
Question: Can urgent work guarantee latency while low-priority work is never starved?
Show answer and explanation
Answer: Only within an admitted workload and reserved capacity budget. Use weighted shares, aging and rejection/backpressure when arrival rates exceed service rates; priority cannot create capacity.
Verification and rollout
Enumerate stale/current claim generations, duplicate completion and redrive after an uncertain external effect. Under admitted unit-cost work, verify HHHNNL selections and finite queues; then introduce long jobs to demonstrate the guarantee's limits. Roll out weights gradually while tracking age and share by tenant/band.
Primary technical reference
Official documentation for the mechanism used in this exercise. This lesson is an original interview design, not a description of undisclosed company internals.
Related study
Before this design, review these mechanisms and identify which owns the critical state transition:
Use the Interview Playbook to adapt the depth and timing, then return to the question breakdown overview.
Shared foundation: Reliability and Overload Control
Reliability and Overload Control: Bound deadlines, queues, concurrency and retry work; calculate safe admission and recovery. Work its failure history before extending this design.