Borg: A Datacenter as One Machine

In one sentence

Borg is Google's cluster manager: users submit a declarative job spec (how many copies, how much CPU and memory each, what constraints), and Borg picks machines inside a cell of tens of thousands of them, starts the work, watches it, and restarts it on failure. Using priority-based preemption it packs latency-sensitive online services and throughput-oriented batch work onto the same machines, then uses resource reclamation to lend out capacity that was requested but never used — pushing datacenter utilization far up while keeping the online services available. It is the first systematic account of a decade-plus of Google production experience, and the direct design blueprint for Kubernetes.

Glossary

Coordinates

By Abhishek Verma, Luis Pedrosa, Madhukar Korupolu, David Oppenheimer, Eric Tune and John Wilkes of Google, published at EuroSys 2015. By the time it was written, Borg had been in production for over a decade — the systems behind famous papers like GFS, MapReduce and Bigtable are themselves just tasks running on Borg. Its external contemporaries were Mesos (2011) and YARN (2013); inside Google there was also Omega (2013), an experimental successor replacing Borg's monolithic master with shared state and optimistic concurrency. A year later the same people wrote Borg, Omega, and Kubernetes (2016) to review a decade of lessons — and Kubernetes is Borg's model rewritten in the open.

The problem and the motivation

Google had to keep two temperamentally opposite workloads alive on the same fleet. Online services (Search, Gmail, ad serving) run indefinitely and are sensitive to tail latency, but their traffic peaks and troughs across the day. Batch work (index building, log analysis, MapReduce jobs) runs from seconds to days, exits when done, and only cares about throughput.

The old approach was to carve the fleet into disjoint pools by purpose: each pool sized for its own peak, so each pool sits on a large idle margin that it cannot lend to its neighbor. Worse, at ten-thousand-machine scale hardware failure is routine, not exceptional — if humans had to patch, restart and reconfigure by hand, operations could never keep up.

So there were three problems, pulling against each other: raise utilization; but raising utilization means mixing workloads, and mixing lets neighbors interfere with the online services, so keep those available anyway; and let thousands of engineers ship and keep programs running without needing to know that machines exist.

Core ideas and method

1. You say what you want, not where it runs

Borg's first decision was to narrow the interface down to a declarative spec: a job declares how many copies, how many milli-cores / how much memory / how much disk each needs, and what kind of machine it requires. Then you hand it over. Borg picks machines, installs packages, starts the tasks, watches liveness, restarts failures, and moves work off dead machines. "Which machine is my program on" stops being a question engineers have to answer.

Two small parts make this actually usable. One is the alloc (short for allocation): a reserved slice of resources on a machine into which several cooperating tasks can be placed (a main program plus a log-shipping sidecar, say), moving together with the reservation — this is precisely the ancestor of the Kubernetes pod. The other is BNS (the Borg Name Service): every task gets a stable name (kept in Chubby) so others can find it without knowing which machine or port it currently sits on. Without that naming layer, "tasks move around at any time" would be a catastrophe rather than a feature.

The architecture itself is plain: a cell has one logical Borgmaster (in fact 5 replicas, holding cell state and electing a leader via Paxos, with the scheduler inside) plus a small agent, the Borglet, on every machine. The Borgmaster polls each Borglet every few seconds to pull current state and push pending work; polling rather than having Borglets report in lets the master control the pace of traffic, so it isn't swamped by tens of thousands of machines at once during recovery. Conversely, when the master is unreachable a Borglet keeps looking after the tasks already running, so a brief master outage doesn't reach the programs actually serving users.

2. Mixing: priority, preemption and quota

The main engine of utilization is putting online services and batch work on the same machines. Each task carries a priority, and priorities fall into non-overlapping bands (roughly, from high to low: monitoring → production → batch → best-effort). Production (prod) means the online services that must not go down; everything else is non-prod.

The rule is blunt: when a machine can't fit everything, a higher-priority task pushes a lower-priority one out — the latter is killed and re-queued. With one important exception: production tasks do not preempt one another, or a single eviction would set off a cascade of "I evict you, you evict him."

Priority alone isn't enough, or everyone would label their own work top priority. Hence quota: how much a team may request, at a given priority, over a given period, checked as admission control at submission time. Quota at high priority is expensive and scarce, while quota at the lowest priority is close to unlimited — the price being that such work can be preempted at any moment. Priority decides who yields at run time, quota decides who may ask for how much at submission time; the two must stay separate, or "priority" degenerates into an arms race nobody backs down from.

3. Reclamation: don't trust the request, trust the measurement

Mixing alone is not enough, because engineers almost always ask for more than they need — better to over-insure than be paged at 3am for out-of-memory. So on any machine there is a persistent gap between what has been "handed out" and what is actually in use.

Borg's answer is to split a task's resources into three lines. The limit is what you requested, and what you are charged for. The usage is the real consumption Borg keeps observing. In between sits the reservation, which Borg estimates from recent usage plus a safety margin. Everything between reservation and limit is judged "you almost certainly won't need this" and reclaimed — lent out to non-production work. When usage rises the reservation rises with it and the loan is called back immediately, with the cost borne by low-priority tasks that can survive being killed. The paper reports that roughly 20% of the workload runs on such reclaimed resources.

4. The scheduler: picking one machine out of ten thousand

Scheduling has two steps. First, feasibility checking: which machines could hold this task. What counts as "enough room" depends on priority — for production tasks it is computed against the neighbours' declared limits, for non-production tasks against their estimated reservations, and that is exactly where overcommitment happens. Second, scoring, to pick one of the feasible machines: the policy is a hybrid of spreading (scatter load, leaving headroom for spikes) and best fit (pack a machine tight, reducing fragmentation). Pure spreading leaves nowhere able to take a large task; pure packing falls over at the first peak.

The difficulty is scale: a cell has tens of thousands of machines, and some cells see arrival rates above 10,000 tasks per minute, so scoring machine by machine can never keep up. Borg cuts it down three ways: score caching (reuse the last score unless the machine changed materially), equivalence classes (the hundreds of tasks in one job have identical requirements, so score once, not hundreds of times), and relaxed randomization (examine a random subset and stop once there's enough, rather than chasing the global optimum). All three buy the same thing: trading "optimal" for "computable in time." One easily overlooked measurement: a task takes a median of about 25 seconds from scheduling to running, roughly 80% of it spent installing packages — which is why Borg prefers machines that already have the package. In real systems the bottleneck is often not in the algorithm you were staring at.

5. Isolation and availability: covering the cost of mixing

Once you pack strangers onto one machine, isolation becomes the crux. Borg uses cgroups-based containers rather than virtual machines — saving one operating system per VM, at the cost of less complete isolation. Resources are treated in two classes: compressible ones (CPU, disk I/O bandwidth) are simply throttled when exceeded; non-compressible ones (memory, disk space) cannot be slowed down, so exceeding them means the task is killed.

Availability rests on a set of habits: evicted tasks are automatically rescheduled; the replicas of a job are deliberately spread across failure domains (different racks, different power) so one outage can't take them all; and the rate of simultaneous disruptions is capped. The paper also mentions something very practical — Fauxmaster, a high-fidelity simulated master that can replay real cell state offline, used for debugging, capacity planning, and asking "what if we changed this policy?" The "how many machines did that save" results in the next section came out of it.

Key results

The evaluation method is itself worth learning: cell compaction — feed a real cell's workload to Fauxmaster, keep removing machines and re-packing from scratch each time until the workload no longer fits. The smallest machine count that still works is the workload's true cost; change one policy, recompute, and the difference tells you what that policy is worth in machines.

• What mixing saves: segregating production and non-production work into separate cells would need 20–30% more machines in the median cell.
• What fine-grained requests save: Borg lets you request in milli-cores and bytes. Coarsening that — rounding every request up to the next power of two — would cost the median cell 30–50% more resources. "Let's just round it off, it's easier to manage" is astonishingly expensive at this scale.
• Big cells beat small ones: subdividing one large cell into several smaller ones raises the machine count noticeably — the bigger the pool, the more peaks and troughs cancel out.
• The real mix: in a representative cell, production jobs are allocated about 70% of the CPU and account for about 60% of CPU usage; they are allocated about 55% of memory and account for about 85% of memory usage. The gap between allocation and usage is exactly the meat reclamation feeds on — about 20% of the workload runs on reclaimed resources.
• Scale: a single Borgmaster manages a cell of many thousands of machines, and several cells see arrival rates above 10,000 tasks per minute.

Why it matters

First, it turned "the cluster is the computer" from a slogan into an engineering fact with production evidence: a decade-plus of running records at ten-thousand-machine scale showing that "engineers declare needs and never touch machines" works, and that it saves fleet-sized money. "Mix, preempt by priority, overcommit against measured usage" became the default agenda for every cluster scheduler afterwards.

Second, it is the design blueprint for Kubernetes. The alloc became the pod; "declarative spec plus a master continuously pulling reality toward the desired state" became K8s's core loop; the Borglet became the kubelet. Most of what we now call cloud-native practice — containers, declarative configuration, control plane separated from data plane, priority and preemption — has its prototype in this paper.

Limitations and criticism

• Design mistakes the authors own up to: the job is the only grouping mechanism — there is no way to manage "several jobs of one service" (a canary track and a production track, say) as a single entity; one IP address per machine — every task on a machine shares the host's IP and port space, so ports have to be scheduled as a resource, with tasks pre-declaring how many they need and accepting whichever they're given (Kubernetes gave each pod its own IP precisely to cure this); over-optimizing for power users — the feature surface is rich for heavy users but steep for casual ones.
• Isolation while mixing is imperfect: cgroups containers share a kernel, and share cache and memory bandwidth, so neighbour interference can't be eliminated — especially for tail-latency-sensitive services. The paper acknowledges this is still being improved. Borg is also a single centralized logical master, whereas Google's own Omega argued that would become the bottleneck and moved to shared state with optimistic concurrency; neither has been settled, and Kubernetes ended up in between.
• The conclusions may not travel: Borg's gains lean heavily on Google's homogeneous environment — one RPC framework, one monitoring and naming stack, a controlled software base, a limited set of machine types. On a public cloud with wildly varied stacks and mutually distrustful tenants, the safe envelope for aggressive mixing is much narrower.
• Not reproducible, and told from the winning side: the system is closed-source and the data comes from Google's internal cells, so outsiders can neither verify nor compare; and while the utilization and scale numbers are generous, the paper is comparatively reticent about batch queueing delays and the wasted recomputation caused by repeated preemption.

Takeaways