You are handed a buggy Python job scheduler that runs many independent jobs concurrently. Each **job** has an ID, a callable to execute, a maximum retry count, and a terminal status of either **succeeded** or **failed**. The scheduler maintains four job sets — `pending`, `running`, `completed`, and `failed` — dispatches work using either worker threads or asynchronous tasks, enforces a rate limit of **at most $R$ job starts per second**, and records per-job metrics such as start time, finish time, latency, retry count, and final status. Your job is to **debug and harden** this scheduler, then reason about its performance. The interviewer hands you the source and expects you to read it for concurrency defects, fix them, justify the fixes, write tests that catch the original bugs, and quantify scheduling time and success rate. This is a live debugging-and-design exercise, not a from-scratch implementation. Work through the five parts below. ### Constraints & Assumptions - Jobs are **independent** — no job depends on the output or ordering of another. - Each job runs up to `max_retries + 1` total attempts; a transient failure re-enqueues the job, a permanent failure (retries exhausted) moves it to `failed`. - Concurrency is bounded by a worker/concurrency limit $W$ (number of threads or in-flight async tasks). This is **separate** from the start-rate limit. - The rate limit governs **starts**: no more than $R$ jobs may *begin* executing per second. Jobs already running do not count against it. - Job callables are arbitrary user code: they may block, sleep, raise, or take an unpredictable amount of time. Treat their latency as untrusted. - Assume CPython, so the GIL makes individual bytecode ops atomic but does **not** make multi-step read-modify-write sequences atomic. The bugs are logical concurrency bugs (lost updates, non-atomic check-then-act, lock ordering), not low-level memory-model issues. - "Schedule a batch" means: submit $N$ jobs and run until every job reaches a terminal state (`completed` or `failed`). ### Clarifying Questions to Ask - Is the concurrency model **threads** (`threading`/`concurrent.futures`) or **asyncio**? The locking primitives and the "race" surface differ. - Does the rate limit need to be a **strict** per-second cap, or is a token-bucket burst acceptable? - Should cancellation **interrupt a running job** (cooperative vs. hard kill) or only prevent un-started jobs from starting? - What counts as a "failure" for the success-rate metric — a permanent failure only, or any job that ever raised? - Are job callables guaranteed **idempotent** on retry, or must we assume a duplicate execution can double-apply side effects? - What's the expected scale — hundreds of jobs or millions — and does that change whether a single global lock is acceptable? ### Part 1 — Concurrency defects: races, deadlocks, contention Read the scheduler and identify every **data race**, **deadlock**, and **lock-contention hot spot** you can find. For each, explain the failure mode (what interleaving triggers it, what observable corruption results) and propose a concrete fix. State the **state-machine invariants** the scheduler must preserve and explain how your fixes enforce them. ```hint State invariants first Before hunting bugs, write down the invariants the data structures must satisfy: a job is in **exactly one** of `pending`/`running`/`completed`/`failed` at any instant, a job is never started twice concurrently, and `len(running)` never exceeds $W$. Most races are violations of one of these — find them by stating the rule, then searching for the line that can break it. ``` ```hint Classic race shape Look for **check-then-act** sequences that aren't atomic: "is this job pending? → move it to running" or "pop from pending → mark running" done without holding one lock across *both* steps. Two workers can both pass the check and double-start the same job. Also scrutinize unsynchronized mutation of shared counters/metrics. The fix is to make claim-and-transition a single critical section. ``` ```hint Deadlock + contention Deadlocks usually come from **inconsistent lock ordering** (path A takes `state_lock` then `metrics_lock`; path B takes them in reverse). Contention comes from holding a lock while doing slow work. Two rules fix most of it: enforce a **global lock order** (or collapse to one lock for tightly-coupled state), and **never call the user's job callable while holding a scheduler lock**. ``` #### What This Part Should Cover - The full set of **state-machine invariants** written down *before* bug-hunting, with each defect framed as a violation of a named invariant rather than ad-hoc "this looks wrong." - Correct diagnosis of the **non-atomic check-then-act claim** (double-dispatch from the shared pending store) and **unsynchronized counter/metric mutation** (lost updates). - A **lock-discipline** prescription: single lock or strict global ordering, smallest possible critical section, and the user callable invoked *outside* any scheduler lock. - Clear articulation of *which interleaving* triggers each bug and *what observable corruption* results. ### Part 2 — Rate limiter correctness under concurrency Inspect the rate limiter and decide whether it actually enforces "at most $R$ starts per second" when many workers call it simultaneously. If it's broken, fix it; either way, **specify precisely** which semantics it guarantees (strict sliding window vs. token bucket with burst) and what clock it uses. ```hint What to check A limiter that reads a shared counter/timestamp, decides, then mutates — without a lock or atomic op around the *whole* sequence — is racy: $N$ workers can all observe "under the limit" at once and all start. Also check the **clock**: wall-clock time can jump backward (NTP) and silently break the window. ``` ```hint Two valid designs A **token bucket** (capacity = allowed burst, refill $R$ tokens/sec, consume 1 token per start) permits short bursts but bounds the long-run rate. A **strict sliding window** keeps a deque of recent start timestamps and only permits a start when fewer than $R$ fall inside the trailing 1-second window. Use a **monotonic** clock (`time.monotonic`), and protect the token/timestamp update with a lock or funnel all starts through one dispatcher. ``` #### What This Part Should Cover - A verdict on whether the existing limiter is **thread-safe**, naming the racy window (read-decide-mutate without one critical section). - An **explicit choice of semantics** — strict sliding window vs. token bucket — with the burst/long-run guarantee each provides stated precisely. - Use of a **monotonic clock** and an explanation of why wall-clock breaks under NTP/clock skew. - Awareness of boundary bugs (`<` vs `<=`) and of *not* sleeping while holding the lock. ### Part 3 — Tests that prove correctness Write tests that demonstrate correct behavior under **success, permanent failure, retry, cancellation, and high concurrency** — and, ideally, that would **fail against the original buggy code**. Describe what each test asserts and how you force the problematic interleavings. ```hint Make races reproducible Deterministic concurrency tests use **`threading.Barrier`** (or async events) to release many workers at the exact same instant, maximizing the chance of hitting the bad interleaving. Run such stress tests in a loop (e.g. 100×) — a single pass can pass by luck. Assert the invariants from Part 1 (every job in exactly one terminal state; no double-execution, tracked via a per-job attempt counter). ``` ```hint Rate-limit + retry assertions For the limiter, submit many zero-duration jobs and assert the **start-timestamp pattern** matches the documented semantics — but pick the right quantity for each design. A **strict** window bounds the *count*: no 1-second window has more than $R$ starts. A **token bucket** does not — its *instantaneous* burst is bounded by capacity $C$, but a fixed 1-second window can contain more than $C$ starts because tokens refill mid-window. Work out the windowed bound for a bucket before you assert on it (hint: it is larger than $C$), and separately assert the long-run rate stays $\le R$. For retries, use a callable that fails its first $k$ attempts then succeeds, and assert both the final state and the recorded `retry_count`. ``` #### What This Part Should Cover - Coverage of **all five behaviors** (success, permanent failure, retry, cancellation, high concurrency), not just the happy path. - A **no-double-execution** test that asserts each job ran exactly once and reached exactly one terminal state, made deterministic with **barriers** and **repetition**. - Rate-limit assertions that bound the **correct quantity for the chosen design** (count-per-window for strict; burst $\le C$ + long-run rate $\le R$ for a bucket). - A retry test that pins both the **final state** and the recorded **retry count** for a fail-$k$-then-succeed callable. ### Part 4 — Scheduling time and success rate Define and compute, from the recorded metrics: (a) the **total time to schedule the batch** and (b) the **final success rate**. Then give a **theoretical lower bound** on the makespan as a function of $N$, $R$, $W$, and the job durations $d_i$. ```hint Measured quantities Both observed quantities come straight from the per-job records, so be precise about *which* timestamps and *which* counts you use. The makespan spans the whole batch — from the earliest thing that happened to the latest — so reach for an extreme over the start times and an extreme over the finish times. The success rate is a ratio out of $N$; before you write it, decide exactly which terminal states land in the numerator (does a job that only succeeded after retries count? where do cancelled jobs go — numerator, denominator, or excluded?) and defend that choice. ``` ```hint Lower bound has three independent floors The makespan is held down by several constraints that act *independently* — the true bound is the largest of them, since the schedule can't beat any single one. Reason about three separate bottlenecks and express each as its own term, then combine: (1) the total work you must do spread across your parallelism budget; (2) the one job you can never split or shorten; (3) the rate at which you're even *allowed* to begin jobs. Convince yourself which variables ($N$, $R$, $W$, $d_i$) drive each term, and note whether the start-rate floor is an exact bound or a continuous-time approximation. ``` #### What This Part Should Cover - **Precise formulas** for makespan (latest finish minus earliest start over jobs that actually started) and success rate (a ratio out of $N$), each tied to the exact recorded fields. - A **defended convention** for retried-then-succeeded jobs (counted) and for cancelled jobs (numerator vs. denominator vs. excluded), stated rather than silently assumed. - A **makespan lower bound** built as the **max of three independent floors** — work/parallelism $\sum d_i / W$, the longest single job $\max_i d_i$, and the start-rate floor $\approx N/R$. - Acknowledgement that the start-rate term is a **continuous-time approximation** (the first start is free; $\lceil N/R\rceil$ under strict per-second discretization). ### Part 5 — Instrumentation for future debugging Explain what **logs, metrics, and traces** you would add so that the next concurrency bug is diagnosable from telemetry alone — and so you can tell a *business-logic* failure (a job that legitimately failed) apart from a *scheduler* bug (a race, a stuck queue, a limiter that's throttling too hard). ```hint Per-event vs. aggregate Think in two layers: **structured per-job log lines** (job_id, attempt, worker_id, state transition, enqueue/start/finish timestamps, error type, limiter wait time) that let you replay one job's life, plus **aggregate gauges/counters** (queue depth, active workers, throughput, retry rate, lock-wait time, p50/p95/p99 latency) that surface systemic problems like contention or a starving queue. ``` #### What This Part Should Cover - A **two-layer** observability design: per-job structured events (replay one job's life) plus aggregate gauges/counters (systemic health). - The specific signals that **separate a scheduler bug from a business-logic failure** — e.g. throughput exceeding $R$ or rising lock-wait points at the scheduler; a spike in a specific callable `error_type` points at job logic. - Mention of **lock-wait time** and **live throughput** as the telemetry that would have caught the Part 1 and Part 2 bugs. ### What a Strong Answer Covers These dimensions span all five parts and tie the exercise together: - A consistent **invariant-driven method**: every fix, test, and metric traces back to a stated state-machine invariant rather than ad-hoc reasoning. - **Lock discipline maintained throughout** — minimal critical sections and no user code under a lock — visible in the bug fixes (Part 1), the limiter (Part 2), and the contention story (Parts 1 and 5). - Explicit **trade-off awareness**: lock granularity vs. contention, strict vs. burst rate limiting, and retry idempotency vs. duplicate side effects. - **Precision under ambiguity** — clarifying the concurrency model, the limiter semantics, and the success-rate convention before committing to numbers. ### Follow-up Questions - Your current design re-enqueues failed jobs onto the pending set. How do you prevent a permanently-flaky job from **starving** fresh jobs, and how would you add exponential backoff with jitter between retries? - The scheduler must now run across **multiple processes or machines**. How does the rate limiter change (local token buckets vs. a shared/distributed limiter), and what new races appear? - If a worker crashes mid-job, how do you guarantee **at-least-once** vs. **at-most-once** execution, and how does that interact with retries and idempotency? - If profiling shows the single state lock is the bottleneck at high $W$, how would you **shard or restructure** the locking while preserving the invariants?