← Back
Home › Systems › Cloud platform and compute

cluster-scheduler

cluster and batch job scheduler

Borg, Slurm

SystemTechniques · 9Primitives · 25 cluster-scheduler Backfill schedulingdistributed · medium: Run small jobs in gaps ahead of reserved large jobs without delaying themGang schedulingdistributed · medium: All-or-nothing co-scheduling of a job's tasksMulti-Paxosdistributed · medium: Paxos run once per log slot with a stable leader that skips phase 1; the foundation of Chubby, Spanner and much production consensus.›Raftdistributed · medium: Leader-based consensus on a replicated log; one leader per term, majority commit; the default for a strongly consistent replicated state machine.›Checkpoint and restarthardware-os · medium: Periodically save enough state to resume a computation after a crash, preemption or move, with an interval that balances save cost against lost work.›Fair share schedulingsystems · medium: Dominant resource fairness and hierarchical fair-share queuesPriority and preemptionsystems · medium: Priority classes, quota and evicting lower-priority work to admit higherLeasesdistributed · low: A lock that expires on its own: bounded-time ownership that survives crashes and partitions, given bounded clock drift and fencing tokens on writes.›d-ary heapdata-structures · low: Array heap with d children per node (d = 4 typical): half the binary heap's depth, siblings in one cache line, faster priority queues.›Resource usage accountinghardware-os · low: Cgroup/procfs/GPU counters sampled into per-workload usageBin packingoptimization · low: Pack items of given sizes into the fewest fixed-capacity bins; sort descending, then first-fit, gives at most 11/9 of optimal and runs in O(n log n).›Phi accrual failure detectordistributed · low: Instead of a fixed heartbeat timeout, output a continuous suspicion level φ from the observed heartbeat interval distribution; adapts to each link's jitter.›Cgroups and namespaceshardware-os · low: Linux namespaces limit what a process can see; cgroup v2 limits and accounts what it may use. Containers, sandboxes and job schedulers are built from the two.›Interval treedata-structures · low: Index of ranges that answers "which intervals overlap this point or range?" in O(log n + k); static sorted-array form is the compact, cache-friendly choice.›Distributed barrierdistributed · low: Rendezvous/barrier for a dynamic worker group: join, agree on membership and rank assignment, restart on changeWrite-ahead logstorage · low: Append each change to a checksummed sequential log and fsync it before touching data pages; the basis of crash durability in nearly every database.›Exponential backoff with jittersystems · low: Retry after delays that grow geometrically and are randomized, so failed clients spread out instead of hammering a recovering service in synchronized waves.›Copy-on-write forkhardware-os · low: fork() gives the child the parent's whole address space by sharing pages read-only and copying one only when someone writes it; vfork and posix_spawn skip even that.›Dirty page trackinghardware-os · low: Write-protection or PML logs of modified guest/process pagesmmap and the page cachehardware-os · low: How read() and mmap reach file data through the kernel page cache, what readahead and madvise do, and why databases use their own buffer pool instead.›Ptrace process controlhardware-os · low: Ptrace: attach, read and write registers and memory, single-step, intercept signalsExponential smoothing (ETS, Holt-Wi…statistics · low: Forecast by keeping a few running states (level, trend, seasonal) updated by a fraction of each forecast error; O(1) memory per series and a strong baseline.›Graceful drainingsystems · low: On a termination signal, stop taking new work, finish in-flight work until a deadline, tell clients to reconnect elsewhere, then exit; clients resume from a token.›+ 2 more techniques+ 9 more primitives

Similar systems

Share the most building blocks with this one.

gpu-job-scheduler 59 %gpu-cloud 40 %container-orchestrator 19 %

In-house systems

Named systems of this kind at large companies, with their paper or write-up.

BorgAlphabetTwineMeta PlatformsFuxiAlibaba Group