Skip to content
TheChatArchiveThe Chat Archive
GPT 5.2· openaiHugging Face Frontier Reasoning Traces

Build a robust scheduler: priority queues, starvation prevention, distributed locks,…

  1. User

    Build a robust scheduler: priority queues, starvation prevention, distributed locks, delayed jobs.

  2. 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_at in 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_boost to 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 ASC
    

    This 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 LOCKED lets 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 RETURNING yields 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_at in 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, set state='queued' and push available_at forward 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 queued with available_at = now() + interval '5 seconds'
    • release row lease

    If acquired:

    • run handler
    • always pg_advisory_unlock(...) in finally

    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_key for 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)
    • 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_ms
    • LIST 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)

    1. Language/runtime (Go, Python, Java, Node, Rust?)
    2. Storage choice: Postgres-only vs Redis+Postgres
    3. Job volume/targets: jobs/sec, p95 latency target, max runtime
    4. Priority model: numeric priority vs fixed bands (high/med/low)
    5. 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.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.