Who should read it
Read it for cloud research on scheduling, utilization and isolation, for infrastructure roles, or to understand ideas Kubernetes inherited, such as pods (from Borg’s allocs) and label-based grouping (from the limits of Borg’s jobs). Its cell-compaction method is a useful template for evaluating packing policies. It is not needed if you only need to operate Kubernetes for an application role, and it gives little detail on algorithms beyond the scheduler’s scoring ideas.
Study objectives
- Explain Borg’s user-facing concepts (cells, jobs, tasks, allocs, priorities, quota) and their Kubernetes counterparts.
- Describe the scheduler’s feasibility-checking and scoring phases and the trade-off between worst fit, best fit and the hybrid that targets stranded resources.
- Explain resource reclamation (limits versus reservations), compressible versus non-compressible resources, and how production and batch work share machines.
- Explain cell compaction as an evaluation method, including its assumptions and what it leaves out.
- Relate the lessons in Section 8 to design decisions in Kubernetes.
Prerequisites
Main concepts to understand
- Cells, jobs, tasks and allocs (the precursor of pods)
- Priority bands, quota and admission control
- Borgmaster replication with Paxos and a separate scheduler process
- Feasibility checking and scoring; stranded resources
- Preemption of lower-priority tasks and the pending queue
- Resource reclamation using reservations estimated from observed usage
- Latency-sensitive versus batch application classes; compressible versus non-compressible resources
- cgroup-based performance isolation and CPI as an interference signal
- Cell compaction as a packing-efficiency metric
What to inspect in the evaluation
- Methodology (Section 5.1): compaction via high-fidelity simulation on production checkpoints, the selection of cells, repeated trials with different random seeds, and reporting a high percentile of the trials; ask why that percentile rather than the mean.
- Point-in-time packing instead of long-term trace replay: which dynamic effects (arrivals, failures, growth) are excluded, and the authors’ reasons.
- Constraint relaxations used to obtain repeatable results, such as softening hard constraints for very large jobs and letting a few hard-to-place tasks stay pending.
- Reclamation experiment on a live cell (Section 5.5): what was varied over the weeks, which metrics were tracked (reservations versus usage, out-of-memory events) and possible confounders.
- Interference analysis with CPI (Section 5.2): what correlations were found, how much variance they explain, and the comparison between shared and dedicated cells using the Borglet as a control.
- Generality: Google-specific workloads, hardware and policies; which conclusions you would expect to transfer to other clusters.
Guarantees versus empirical results
Correctness or design arguments
- Availability design arguments: a replicated Borgmaster using Paxos, tasks that keep running when the master is unavailable, and spreading tasks across failure domains.
- Policy argument that quota-based admission control keeps high-priority work feasible within cell capacity.
- Production tasks are scheduled against limits so they never depend on reclaimed resources (a design rule, not a measured property).
Empirical results (depend on setup)
- Machine savings from sharing production and batch work and from using large cells, measured by compaction in simulation.
- Effects of bucketing resource requests versus fine-grained requests.
- Reclamation effectiveness and its out-of-memory trade-off in a live experiment.
- Scheduling delay as a function of machine utilization and CPI-based interference measurements.
Reading plan
- Pass 1 (about 30 minutes): abstract, introduction, Section 2 (the user perspective), Figure 1, and Section 8 (lessons). List the five concepts you would need to explain Borg to someone who knows Kubernetes.
- Pass 2 (about 90 minutes): Section 3 (Borgmaster, scheduling, Borglet, scalability), Section 4 (availability) and Section 6 (security and performance isolation). Write how a task goes from submission to running, including preemption.
- Pass 3 (about 60 minutes): Section 5 (utilization) with its methodology and figures. For each claim, note the metric, the method (simulation or live experiment) and one threat to validity; then compare the reclamation design with Kubernetes requests, limits and QoS classes.
Discussion prompts
- Why does Borg score machines with a hybrid instead of pure best fit, and what does a stranded resource look like on a machine with CPU and memory?
- Cell compaction measures machines needed for one snapshot. What would a trace-replay evaluation reveal that compaction hides?
- Production work is placed using limits and batch work using reservations. What failure modes appear when reservations are wrong?
- Which Borg lessons reappear in Kubernetes (pods, labels, an IP per pod, introspection), and which problems remain open?
- How would you evaluate a new reclamation policy without access to a production cell?