Design a resilient scheduler: leases, checkpoints, preemption.
- User
Design a resilient scheduler: leases, checkpoints, preemption.
- Assistant
Resilient Scheduler Design: Leases, Checkpoints, Preemption
This design outlines a fault-tolerant, distributed scheduler inspired by systems like Kubernetes, Nomad, and Apache Mesos. It ensures high availability, handles node failures, supports workload prioritization, and minimizes task downtime via leases (for ownership and liveness), checkpoints (for fast recovery), and preemption (for resource contention). The system is resilient to master/worker crashes, network partitions, and overloads.
Key Assumptions
- Cluster: Multiple master nodes (for scheduling/leader election) + worker nodes (for task execution).
- Storage: Reliable, distributed KV store (e.g., etcd, Consul) for tasks, leases, checkpoints, and heartbeats. Supports watches for real-time notifications.
- Tasks: Computable units (e.g., jobs, containers) with priority (low/med/high), resource requests (CPU/Mem), and checkpointable state.
- Networking: Workers register with masters; heartbeats via gRPC/HTTP.
High-Level Architecture
[Task Queue] --> [Leader Scheduler (Lease-based)] <--> [KV Store (etcd)] | | Assign Lease + Task v [Worker Nodes] <--> Heartbeats/Renewals - Run Task - Checkpoint State - Handle Preempt- Leader Election: Masters compete for a "scheduler-lease" key in KV store (TTL: 10s). Active leader watches queues and assigns tasks.
- Failover: If leader lease expires, another master takes over seamlessly (<10s).
- Scalability: Workers scale horizontally; leader handles ~10k tasks/sec.
Core Mechanisms
1. Leases (Fault Detection & Ownership)
Leases prevent duplicate execution and enable fast failure detection.
- Lease Structure (stored in KV):
key: /leases/task-{task_id}-worker-{worker_id} value: { holder: worker_id, expiry: timestamp + TTL (30s default), resources: {cpu: 2, mem: 4GB}, version: 1 // Optimistic concurrency } - Assignment:
- Leader selects worker (bin-packing via resources, locality).
- Atomically writes lease to KV (
PutIfAbsent). - Notifies worker via RPC.
- Renewal:
- Worker heartbeats every 10s:
CompareAndSwaplease expiry forward. - If fails (e.g., network blip > TTL/3), exponential backoff retry.
- Worker heartbeats every 10s:
- Expiry Handling:
- Leader watches lease keys. On expiry/delete:
- Mark task as "failed" or "pending".
- Reschedule to new worker (resume from checkpoint).
- Leader watches lease keys. On expiry/delete:
- Resilience:
- No single point: Multiple masters watch leases.
- TTL tuned for 99.9% uptime (e.g., 30s allows 3 missed heartbeats).
2. Checkpoints (Fast Recovery)
Enable tasks to resume mid-execution after failures/preemption.
- Checkpoint Protocol:
- Tasks implement
Checkpoint()hook: Serialize state (e.g., ML model weights, DB tx log) to/checkpoints/{task_id}/{seq}in KV/object store (S3-compatible). - Frequency: Adaptive (e.g., every 1min or 10% progress).
- Metadata:
{seq: N, timestamp, size, hash}for integrity.
- Tasks implement
- Storage:
Type Use Case Durability KV (etcd) Metadata + small state CP Object Large blobs (e.g., models) AP - Recovery:
- On reschedule, new worker fetches latest valid checkpoint (
max seqwith matching hash). - Task resumes:
Resume(checkpoint_seq). - Leader tracks "resume_from" in task spec.
- On reschedule, new worker fetches latest valid checkpoint (
- Resilience:
- Idempotent: Checkpoints are append-only, versioned.
- Cleanup: Leader GCs old checkpoints post-success.
3. Preemption (Priority & Resource Control)
Gracefully evict low-priority tasks for high-priority ones.
- Priority Tiers: BestEffort (0), Batch (1), Service (2), Critical (3).
- Triggers:
- Resource pressure: Worker >90% util → preempt lowest priority.
- Gang scheduling: All-or-nothing for distributed tasks.
- Manual: API call
Preempt(task_id).
- Preemption Flow:
- Leader revokes lease:
Delete(lease_key)(atomic). - Worker detects via heartbeat failure or direct
PreemptRPC. - Worker:
SIGTERM→ Checkpoint →SIGKILLafter 30s grace. - Task requeued with "preempted" status → Rescheduled elsewhere.
- Leader revokes lease:
- Gang Preemption: Track "gang_id"; preempt entire group or none.
- Resilience:
- Fairness: Preemption score = priority + wait_time + resources.
- Backoff: Preempted tasks get scheduling boost.
Task Lifecycle
Submit Task --> Enqueue --> Leader Assigns Lease --> Worker Runs | | | | |<-- Heartbeat -- | Checkpoint | | | Fail/Preempt? --> No Yes --> Expire Lease --> Resume from Checkpoint | Success? --> Mark Done --> GC- States: Pending → Running (lease active) → Resuming → Succeeded/Failed/Preempted.
APIs (gRPC/REST)
SubmitTask(task_spec)→ task_idListTasks(?state=running)PreemptTask(task_id, reason)- Worker:
Register(),Heartbeat(lease_ids),ReportProgress(seq)
Resilience Guarantees
Failure Mode Detection Recovery Time MTTR Worker Crash Lease expiry <40s <1min Master Crash Leader lease <15s <30s Network Partition Heartbeat fail Graceful Auto Overload Preemption Immediate <1min - Metrics: Task completion rate >99%, reschedule latency p99<2min.
- Testing: Chaos engineering (kill workers, partition nets).
Implementation Notes
- Languages: Go (leaders/workers) for concurrency; Rust for perf-critical.
- Libs: etcd client, Prometheus for monitoring, CRD-like task specs.
- Extensions: Autoscaling (watch cluster util), Federated (multi-DC).
This design balances simplicity, resilience, and performance. Prototype in ~2 weeks. Questions?
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.