Build a robust scheduler: priority queues, starvation prevention, distributed locks,…
- User
Build a robust scheduler: priority queues, starvation prevention, distributed locks, delayed jobs.
- Assistant
Designing a job scheduling system
I'm outlining a job scheduling system that includes components like an API for job management, leveraging PostgreSQL for storage with a jobs table for durability and state management, and implementing a dispatcher to handle job prioritization. I’m considering using PostgreSQL features like SKIP LOCKED to manage distributed locking and prevent starvation. Additionally, using an effective priority system with aging seems like a better approach for efficiency in scheduling.Implementing job recovery and fairness
To handle recovery, I need to detect expired leases and requeue jobs. For preventing starvation, I can implement priority aging with an effective priority calculation based on the base priority and aging intervals. I’ll consider using weighted fair scheduling to manage credits per priority. Computing the effective priority dynamically can be complex, but using an expression index might help. Alternatively, I could maintain separate score values or use Redis sorted sets for job management, though balancing complexity and speed is important. I’ll outline a robust implementation approach with Redis and a persistent store.Drafting the job scheduling system
I’m planning to create a design and a concrete implementation in Python using PostgreSQL or MySQL, with PostgreSQL offering strong features like advisory locks and SKIP LOCKED for distribution. The system will handle priority queues, aging for starvation prevention, and delayed jobs using available_at. Workers will run a loop to select and update jobs, transitioning states based on processing success. I will also implement a sweeper to reset jobs that exceed their lease expiration. This design ensures robust lock management and job scheduling efficiency.Addressing starvation prevention and job scheduling
For preventing starvation, I’m focusing on an aging system where effective priority is calculated using base priority and a minimum age boost to ensure older, low-priority jobs eventually outrank newer, high-priority ones. To reduce computation overhead, I might maintain a 'score' column that updates periodically. My answer will include a data model schema in PostgreSQL, claim algorithm SQL, worker logic pseudocode, and details on handling delayed jobs and backoffs. I’ll also cover distributed locks, concurrency, and failure modes to enhance reliability and scaling.Designing a Redis-based job scheduling system
I can propose a Redis-based variant that includes ready queues by priority and a delayed ZSET. We can use a Lua script for atomic job transitions. Fairness could be managed with a weighted round-robin approach. Since the user wants a build, I’ll include a design overview and key code snippets, with some minimal Python for workers. My structured answer will cover goals, data structures, enqueueing, claiming locks, execution, retries, starvation prevention, and operational notes. Using PostgreSQL's SKIP LOCKED and pg_try_advisory_lock for distributed locks will enhance the design’s robustness. Below is a proven “robust scheduler” design that covers priority queues, starvation prevention, distributed locking, and delayed jobs, while remaining simple enough to run in production. I’ll present a Postgres-backed approach (durable, transactional, distributed by nature), plus an optional Redis variant for ultra-low latency.
1) Core semantics (what you get)
- At-least-once execution (recommended): if a worker crashes mid-job, the job will be retried after a lease timeout. Handlers must be idempotent (or use a dedupe key).
- Delayed jobs: schedule for
run_at/available_atin the future. - Priorities: higher priority runs first.
- Starvation prevention: low-priority jobs eventually rise (“priority aging”) or via fairness (“weighted fair”).
- Distributed locks:
- Job-claim lock so only one worker runs a job.
- Optional resource locks so only one job touching the same resource runs at once (e.g., same customer/account).
2) Data model (Postgres)
A single table works well for most deployments:
CREATE TYPE job_state AS ENUM ('queued','running','succeeded','failed','cancelled'); CREATE TABLE jobs ( id BIGSERIAL PRIMARY KEY, queue TEXT NOT NULL DEFAULT 'default', -- priority: bigger = more urgent priority INT NOT NULL DEFAULT 0, -- delayed jobs / retries available_at TIMESTAMPTZ NOT NULL DEFAULT now(), state job_state NOT NULL DEFAULT 'queued', -- leasing (distributed lock for execution) leased_by TEXT, lease_expires_at TIMESTAMPTZ, attempts INT NOT NULL DEFAULT 0, max_attempts INT NOT NULL DEFAULT 25, -- optional: prevent duplicates dedupe_key TEXT, -- optional: resource-level mutual exclusion resource_key TEXT, payload JSONB NOT NULL, created_at TIMESTAMPTZ NOT NULL DEFAULT now(), updated_at TIMESTAMPTZ NOT NULL DEFAULT now() ); -- Helpful indexes CREATE INDEX jobs_ready_idx ON jobs (state, available_at, priority DESC, id); CREATE UNIQUE INDEX jobs_dedupe_idx ON jobs (queue, dedupe_key) WHERE dedupe_key IS NOT NULL;
3) Priority + starvation prevention (choose one)
Option A — Priority Aging (simple, effective)
Compute an effective priority that increases with wait time:
effective = priority + floor(wait_seconds / aging_interval_seconds) * aging_step- Cap it with
max_age_boostto avoid unbounded growth.
In SQL ordering, you can do:
-- Example constants -- aging_interval = 30s, aging_step = 1, max_boost = 100 ORDER BY (priority + LEAST(100, FLOOR(EXTRACT(EPOCH FROM (now() - available_at)) / 30) )) DESC, available_at ASC, id ASCThis guarantees a job that waits long enough will eventually outrank newer arrivals.
Option B — Weighted Fair Scheduling (more control)
Keep strict priorities but allocate “service share” per priority (e.g., 70% high, 20% medium, 10% low) using deficit round robin. This is better when you must protect low priority from starvation and protect high priority from being overwhelmed by aging.
(If you want, I can provide an exact DRR implementation for N priority bands.)
4) Claiming a job (distributed lock via row locks + lease)
Key idea:
SELECT ... FOR UPDATE SKIP LOCKEDlets many workers race safely. The winner updates the row with a lease; others skip it.BEGIN; WITH candidate AS ( SELECT id FROM jobs WHERE state = 'queued' AND available_at <= now() AND (lease_expires_at IS NULL OR lease_expires_at < now()) ORDER BY (priority + LEAST(100, FLOOR(EXTRACT(EPOCH FROM (now() - available_at)) / 30) )) DESC, available_at ASC, id ASC LIMIT 1 FOR UPDATE SKIP LOCKED ) UPDATE jobs j SET state = 'running', leased_by = $1, -- worker id lease_expires_at = now() + INTERVAL '60 sec', -- lease duration attempts = attempts + 1, updated_at = now() FROM candidate WHERE j.id = candidate.id RETURNING j.*; COMMIT;If
RETURNINGyields no rows, there’s nothing ready.Lease renewal (“heartbeat”)
For long-running jobs, renew periodically:
UPDATE jobs SET lease_expires_at = now() + INTERVAL '60 sec', updated_at = now() WHERE id = $1 AND state='running' AND leased_by=$2;Crash recovery
A periodic “reaper” requeues expired leases:
UPDATE jobs SET state='queued', leased_by=NULL, lease_expires_at=NULL, updated_at=now() WHERE state='running' AND lease_expires_at < now();
5) Delayed jobs + retries with backoff
Enqueue a delayed job
Set
available_atin the future:INSERT INTO jobs(queue, priority, available_at, payload, dedupe_key, resource_key) VALUES ($1, $2, $3, $4, $5, $6);Retry on failure
On handler failure:
- If
attempts < max_attempts, setstate='queued'and pushavailable_atforward using exponential backoff (+ jitter). - Else
state='failed'.
Example backoff:
delay = min(base * 2^(attempts-1), max_delay) + random(0..jitter)
-- on retry UPDATE jobs SET state='queued', available_at = now() + ($1::int || ' seconds')::interval, leased_by=NULL, lease_expires_at=NULL, updated_at=now() WHERE id=$2 AND leased_by=$3;
6) Resource-level distributed locks (optional but common)
Sometimes you need “only one job per customer/account/tenant runs at once”.
Approach: Postgres advisory locks (fast, distributed)
- Derive a stable 64-bit hash from
resource_key - Try lock at execution time; if not acquired, requeue with a short delay.
-- In the worker transaction before marking job running (or immediately after claim): SELECT pg_try_advisory_lock(hashtext($1)) AS acquired;If
acquired=false:- set job back to
queuedwithavailable_at = now() + interval '5 seconds' - release row lease
If acquired:
- run handler
- always
pg_advisory_unlock(...)infinally
This provides cross-worker mutual exclusion without needing a lock table.
7) Worker loop (minimal pseudocode)
loop: job = claim_one_job(worker_id) if none: sleep(short) continue if job.resource_key: if !try_advisory_lock(job.resource_key): requeue_soon(job) continue start heartbeat thread (extend lease every 20s) try: handle(job.payload) mark_succeeded(job) catch err: if job.attempts < job.max_attempts: requeue_with_backoff(job) else: mark_failed(job, err) finally: stop heartbeat if resource lock held: unlock
8) Operational hardening checklist
- Idempotency: handlers should tolerate reruns (at-least-once). Use
dedupe_keyfor enqueue-side dedupe when needed. - Clock: use database
now()to avoid worker clock skew issues. - Visibility: metrics for:
- queue depth (
state='queued' AND available_at<=now()) - running jobs
- lease expirations / requeues
- latency (
now()-created_at) and wait time (now()-available_at)
- queue depth (
- Poison pills: cap attempts, keep last error, optionally send to DLQ table.
- Graceful shutdown: stop claiming, finish current jobs, release locks.
- Throughput: run multiple workers; each claim is a cheap indexed query.
9) If you prefer Redis (fast path)
A common Redis layout:
ZSET delayed:{queue}score =available_at_epoch_msLIST ready:{queue}:{priority}for ready jobs- A small Lua script atomically moves due jobs from delayed ZSET → ready lists
- Workers pop from ready lists using a fairness policy (aging or weighted RR)
- Distributed locks via
SET lock:{job_id} value NX PX lease_ms(or Redlock if multi-Redis)
Redis is faster but you must handle durability (AOF/RDB) and replay/duplication carefully; Postgres is simpler for correctness.
What I need from you to produce a concrete build (code + deployment)
- Language/runtime (Go, Python, Java, Node, Rust?)
- Storage choice: Postgres-only vs Redis+Postgres
- Job volume/targets: jobs/sec, p95 latency target, max runtime
- Priority model: numeric priority vs fixed bands (high/med/low)
- Exactly-once requirement? (Usually “no”, and we do at-least-once + idempotency)
If you answer those, I’ll generate a full implementation (schema migrations, worker code, enqueue API, retry/backoff, starvation prevention policy, and lock strategy) tailored to your constraints.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.