Reject Queue Work by Deadline Slack Before Utilization Looks Dangerous

At 09:12, workers are 62% utilized and every health check is green. At 09:14, users receive results after their deadlines. CPU never crossed the alert threshold; the queue accumulated work faster than it could drain.

Utilization describes resource occupancy. It does not tell whether queued work can still finish on time.

For each job, record:

deadline_slack = deadline - now - estimated_service_time

When slack is negative, starting the job cannot meet its declared deadline under the estimate. Admission should reject or degrade it before spending more capacity.

Instrument the queue

Minimum fields:

job_id_hash: 9f2a

class: interactive

queued_at: 2026-07-23T09:12:00Z

deadline_at: 2026-07-23T09:12:08Z

attempt: 1

estimated_service_ms: 1800

queue_age_ms: 2400

deadline_slack_ms: 3800

outcome: admitted

Export distributions, not unbounded job IDs. Useful metrics are queue age by class, slack at admission, service time, completion lateness, rejection count, retry count, and worker saturation.

Admission rule

A starting policy can be explicit:

def admit(job, now, service_p95_ms, safety_ms=250):

    remaining_ms = (job.deadline - now).total_seconds() * 1000

    slack_ms = remaining_ms - service_p95_ms - safety_ms



    if slack_ms < 0:

        return "reject_deadline"

    if job.queue_age_ms > job.max_queue_age_ms:

        return "reject_stale"

    return "admit"

Use a recent service-time percentile for the same workload class, not one global average. Averages hide heavy tails; an estimate from image jobs should not govern text jobs. Clamp stale or tiny samples and version the estimator.

Rejection needs semantics:

• interactive work: return a retryable overload response with bounded guidance;


• asynchronous work: move to a delayed tier only if its deadline permits;


• optional enrichment: skip and return the base result;


• mandatory expired work: dead-letter with a reason, not blind retry.

Retries without a new budget increase load and reduce slack further.

Local failure drill

Run a declared workload against a staging queue:

arrival_rate: 30 jobs/s

worker_count: 8

service_time:

  p50_ms: 120

  p95_ms: 400

  injected_tail_ms: 1800

injection:

  after_seconds: 60

  affected_fraction: 0.35

deadline_ms: 3000

Observe three phases:

1. steady state: queue age and lateness near baseline;


2. injected tail: slack falls before CPU necessarily saturates;


3. admission: expired work stops consuming workers and valid work recovers.

Expected evidence, not claimed measurements:

queue_age_p95 rises

slack_p10 crosses zero

reject_deadline increases

completion_late stops growing

queue drains after injection removal

Compare admission enabled and disabled with the same fixed-seed workload. Record completed-on-time as the primary outcome; raw throughput can reward finishing useless late work.

Alert-to-action runbook

Avoid autoscaling solely on queue depth. Scaling may take longer than remaining deadlines, and a poison-job loop can turn depth into an expensive false signal.

Cleanup and rollback

Roll out in observe-only mode first. Log the decision without rejecting. Compare predicted expiry with actual completion. Then enable for one workload class with a conservative threshold.

Rollback means disabling rejection while retaining telemetry—not deleting deadlines. Drain or explicitly expire dead-lettered work, remove fault-injection jobs, and confirm temporary capacity is scaled down.

Limits

Service-time prediction is uncertain, clocks can skew, and some jobs have business value after a soft deadline. Model those as separate classes. This policy does not replace backpressure, fair scheduling, capacity planning, or dependency timeouts.

The operational question is concrete: when slack turns negative, should the system reject, degrade, or keep spending capacity on work already too late to matter?