Multi-tenant Job Scheduler
Dispatch pending jobs by priority, cap tenant streaks when alternatives exist, and reap soft cancellations.
A busy organization can keep filling a shared queue while another waits for its first job. Build a priority scheduler that preserves priority, supports cancellation, and limits one tenant's consecutive dispatches when others are waiting.
Implement FairJobScheduler. Its fair-use rule limits consecutive dispatches when another tenant has live work waiting.
Requirements
- Constructor receives
max_consecutive_per_org. RaiseValueErrorifmax_consecutive_per_org <= 0. enqueue(org, job_id, priority)adds a job. Lower priority number runs first. RaiseValueErrorifjob_idis already active (pending, including soft-canceled jobs that have not yet been reaped).cancel(job_id)marks a pending job canceled and returns whether it was still active. After a job has been successfully dispatched, latercancelreturnsFalse.- Canceling an already soft-canceled but unreaped ID also returns
True. Cancellation does not immediately free its ID. dispatch(count)returns up tocountjob IDs.- FIFO order breaks ties within the same priority.
- When the fairness cap blocks the next job from
last_org, pick the highest-priority pending job from another org (FIFO among equals). - If another org has pending work, dispatch may not return more than
max_consecutive_per_orgjobs from the same org in a row. The fairness streak is global and persists across separatedispatchcalls. - Canceled jobs are skipped and reaped (their IDs leave the active set) when dropped from the pending queue.
- At the start of each positive-count dispatch iteration, remove all canceled entries before choosing a job. Only live jobs count toward the streak or qualify as another org's pending work.
- A dispatched or reaped ID may be enqueued again; the new arrival gets a new FIFO position.
dispatch(count)withcount <= 0returns[]without changing state or reaping cancellations. If only one org has live work, continue dispatching it even beyond the cap.
Example
Although b1 has lower priority than a3, the two-job fairness cap gives organization b a turn before more work from a.
s = FairJobScheduler(2)
s.enqueue("a", "a1", 1)
s.enqueue("a", "a2", 1)
s.enqueue("a", "a3", 1)
s.enqueue("b", "b1", 5)
assert s.dispatch(4) == ["a1", "a2", "b1", "a3"]Splitting that request into dispatch(2) followed by dispatch(2) must return ["a1", "a2"], then ["b1", "a3"]. Starting a new API call does not reset the streak. Skipping a canceled job also does not reset it.
The cap controls job counts. Compute time and long-term service still depend on priority: if a and b continuously supply high-priority jobs, alternating them can keep a low-priority c waiting forever. Aging or weighted scheduling handles that case with a different policy. Dispatch removes queued jobs; actual worker execution is outside this exercise.
Constraints
- Keep state in memory.
- Org and job IDs are strings, priorities and counts are integers, and the fairness cap is an integer. Negative priorities are valid and sort before zero. Type validation is outside the scope; the specified invalid-cap and duplicate-ID errors are required.
- Calls are sequential. Cancel applies only to pending work and cannot stop a job that has already been dispatched.
- Maintain per-tenant and cross-tenant priority queues so dispatch scales logarithmically with active tenants and queued jobs rather than re-sorting the full queue on every step.