Concepts
Cluster scheduling (Borg-style)
Intuition
Imagine a huge parking lot where two kinds of cars arrive: those that cannot be left without a spot under any circumstances (ambulances) and those that are willing to wait or leave if necessary. Someone at the entrance decides which spot each car goes into, so as to use as much space as possible without leaving useless gaps. When space gets tight, the less important cars give up their spot to the important ones. The cluster scheduler is that gatekeeper: it decides where each program runs across a fleet of machines and how to take advantage of the slack nobody is using.
How it works
In Borg, the user submits jobs made up of tasks, which run as Linux processes in containers inside a cell (a set of machines managed as a unit). Each job has a priority and consumes quota (a vector of resources per priority and period), and quota is checked at admission control: a job without enough quota is rejected at submission. The Borgmaster, replicated five times with state in a Paxos-based store, holds the cell's state and polls each Borglet (per-machine agent). The scheduler is a separate process that asynchronously scans the queue of pending tasks, from highest to lowest priority, in two phases: the feasibility check filters out machines that meet the constraints and have resources, and scoring picks one among the feasible ones. Hybrid scoring tries to reduce stranded resources, avoiding both the worst fit of the original E-PVM and pure best fit. To scale, it uses score caching, equivalence classes (evaluates a group of identical tasks once), and relaxed randomization (examines machines in random order until it finds enough feasible ones). If resources are short, a higher-priority task can preempt a lower one, but production tasks don't preempt each other, to avoid cascades. Finally, the Borgmaster estimates each task's reservation (actual usage plus a safety margin) and reclaims the slack between the requested limit and that reservation, which is handed to non-prod tasks, which are killed or throttled if the estimate fails, never the prod ones.
In practice
The practical gain is utilization: according to the paper, separating prod and non-prod into distinct cells would require 20 to 30% more machines in the median cell, and about 20% of the workload runs on reclaimed resources. Choose this model when many teams share a large fleet with latency-sensitive services and tolerant batch jobs, and you need priority, quota and reuse of slack. Note also that running tasks keep running even if the entire Borgmaster goes down, so the control plane can fail without taking the applications down.
Use it in a design
Practice the cases that rely on this concept in the System Design school.