code benchmark

Prompt

You are a senior backend engineer. Implement a production-quality, persistent, dependency-aware background job scheduler in Python 3.12. Your solution must be executable, correct under concurrency, testable, and robust against crashes. You have no access to external libraries. Use only the Python standard library, including sqlite3, threading, concurrent.futures, json, uuid, and unittest. PROJECT REQUIREMENTS 1. PERSISTENT STORAGE Implement a JobScheduler class backed by SQLite. - All jobs must survive application restarts. - Use SQLite transactions for atomic state transitions. - Enable WAL mode and configure a busy timeout. - Multiple JobScheduler instances must safely share the same database file. - Never rely exclusively on process-local locks for correctness. Each job must store: - job_id: unique string - payload: JSON-serializable value - status: pending, running, succeeded, or failed - dependencies: list of job IDs - priority: integer (higher = more important) - attempts: integer - max_attempts: integer - created_at: integer milliseconds - available_at: integer milliseconds - lease_owner: nullable string - lease_token: nullable string - lease_expires_at: nullable integer - result: nullable JSON value - error: nullable string 2. JOB CREATION AND DEPENDENCIES Implement: add_jobs(jobs: list[dict], now_ms: int) -> list[str] Each input job has job_id, payload, dependencies (default []), priority (default 0), and max_attempts (default 3). Rules: - Insert the entire batch atomically. - Dependencies may reference existing jobs or other jobs in the same batch. - Reject duplicate IDs, unknown dependencies, and self-dependencies. - Detect circular dependencies, including multi-node cycles. - Reject the entire batch if any job is invalid. - max_attempts must be >= 1. - Dependency relationships must not change after creation. - Return job IDs in input order. 3. ATOMIC JOB CLAIMING Implement: claim_job(worker_id: str, now_ms: int, lease_ms: int) -> dict | None Rules: - A job is eligible only when every dependency has succeeded. - A pending job must satisfy available_at <= now_ms. - Select by highest priority, then oldest creation order. - Claiming must be atomic across processes and threads. - A job may never have two simultaneously valid leases. - Increment attempts when a job is claimed. - Generate a unique lease_token on each claim. - Return job_id, payload, attempts, lease_token, and lease_expires_at. - Return None if no job is eligible. - Reject lease_ms <= 0. 4. LEASES AND CRASH RECOVERY Workers may crash after claiming a job. Implement: recover_expired(now_ms: int) -> int Rules: - Locate running jobs whose lease_expires_at <= now_ms. - If attempts < max_attempts, return the job to pending. - If attempts >= max_attempts, permanently fail the job. - Preserve the original attempt count. - Clear expired lease ownership and token. - Return the number of jobs recovered or terminally failed. - Recovery must be safe when invoked concurrently by multiple schedulers. - A previous worker must never complete a job after losing its lease. 5. COMPLETION AND FAILURE Implement: complete_job(job_id: str, lease_token: str, result, now_ms: int) -> bool fail_job(job_id: str, lease_token: str, error: str, now_ms: int) -> bool Rules: - Only a currently valid lease token can modify a running job. - A lease is valid only when now_ms < lease_expires_at. - A successful completion is permanently recorded. - Failure schedules another attempt if attempts < max_attempts. - Retry backoff: min(60000, 1000 * 2**(attempts - 1)) milliseconds. - After max_attempts, the job becomes permanently failed. - A stale, invalid, or expired token must return False and cause no mutation. - All transitions must be atomic. - Repeating a completion request must not change stored results. 6. DEPENDENCY FAILURE - Jobs whose dependencies have permanently failed can never run. - Implement get_job(job_id: str) -> dict | None. - get_job must expose an effective_status field. - effective_status is 'blocked' for a pending job with any failed or transitively blocked dependency. - The underlying stored status remains pending for blocked jobs. - Dependency failure propagation must work across multiple levels. 7. OBSERVABILITY Implement: get_stats(now_ms: int) -> dict Return counts for: - pending - running - succeeded - failed - blocked - ready The categories pending, running, succeeded, failed, and blocked must be mutually exclusive and account for every job. 'ready' is a separate subset of pending jobs eligible for claiming at now_ms. 8. CONCURRENCY REQUIREMENTS The implementation must handle: - 10 workers trying to claim one job simultaneously. - 20 workers claiming 100 independent jobs. - Two scheduler instances accessing the same database. - A worker completing exactly as another scheduler attempts recovery. - SQLite lock contention. - Crash and restart with existing running jobs. Every job must execute under at most one valid lease at a time. Recovery may cause an unfinished job to be executed again, so do not claim exactly-once execution. 9. TESTING Write comprehensive executable unittest tests covering: - Basic job lifecycle. - Dependency chains. - Circular dependency rejection. - Atomic batch rollback. - Priority ordering and FIFO tie-breaking. - Maximum retry behavior. - Exponential backoff boundaries. - Expired lease recovery. - Stale lease-token rejection. - Transitive dependency blocking. - Persistence across scheduler restarts. - Concurrent claims from separate scheduler instances. - A stress test with at least 100 jobs and 20 worker threads. Tests must use temporary database files and deterministic injected timestamps rather than relying on real time or sleep-based scheduling. 10. IMPLEMENTATION REQUIREMENTS Use only Python 3.12 standard library. Use parameterized SQL statements. Avoid busy waiting. Handle SQLite connections safely across threads. Use suitable indexes. Use explicit transaction boundaries. Validate input data. Keep code modular and readable. Do not use pseudocode, incomplete functions, or TODO placeholders. Do not silently ignore exceptions. Do not substitute an in-memory queue for SQLite. Do not use third-party packages. DELIVERABLES Provide the complete contents of: scheduler.py test_scheduler.py README.md README.md must include: - Design decisions - Database schema explanation - Concurrency/transaction strategy - Crash recovery semantics - Limitations and tradeoffs - Commands to run the tests Provide a brief complexity analysis for job claiming, dependency validation, and recovery. OUTPUT RULES 1. Start with a concise architecture explanation of no more than 250 words. 2. Provide complete executable code for every file. 3. Provide the README. 4. Do not omit any code for brevity. 5. Do not invent test execution results. 6. If a requirement is not fully implemented, explicitly identify it at the end. You are evaluated primarily on functional correctness, concurrency safety, edge cases, and actual test execution — not on the persuasiveness of your explanation.