White paper: Large-scale cluster management at Google with Borg

For the past month the club had read a book on the approaches used in Kubernetes — some good, some less so — and reading the ancestor of Kubernetes felt like the natural sequel. The 2015 white paper describes the architecture of the cluster manager after more than ten years of running Google's data centres worldwide. The central abstraction is the job: it is made of many tasks, a task of many ordinary processes, all running on bare metal. There is no virtualisation in Borg, and Vova explains why: in the early 2000s, when Borg began, virtualisation on x86 was not yet a de facto standard, and Google had already invested heavily in hardware it did not want to write off. The participants add that the fleet was assembled from whatever hardware was around and stayed deeply heterogeneous, and that the paper keeps returning to a reluctance to create fragmentation: it makes the scheduler's arithmetic harder, and the servers already number about a hundred thousand.

The authors call their clusters cells: ten or fifteen were taken for the analysis, with technical and very small ones — under five thousand machines — filtered out. The median, by the authors' account, is around ten thousand machines, some cells run to hundreds of thousands, and shrinking them makes no sense: big cells pack more densely, and a single SRE engineer looks after dozens of them alone. The central component is the Borgmaster: it schedules, manages resources and the life cycle of jobs, keeps state through Paxos and is replicated five times, the replicas holding state in memory and picking the work up if the master dies. Agents called borglets live on the machines, the counterpart of the kubelet: the master polls them, and if it cannot read a machine's state the tasks move elsewhere. One design decision reminds the participants of the static stability idea from Amazon's articles — a machine that loses its link keeps running its tasks and kills them only when the link returns, by which point they run elsewhere. Overall Borg would rather kill and restart than repair, which is normal where something is always being updated.

The participants compare scheduling to the knapsack problem: fitting items of different sizes into the best configuration — an NP-complete task, hence Borg's heuristics. Priorities split into prod and non-prod, and that is not the familiar split between environments: non-prod workloads are just as real, only asynchronous — batch jobs, bulk exports — and they are allowed to eat what the paper calls slack resources. The scheduler weighs things Kubernetes does not handle out of the box: what hardware a workload needs, whether it is latency-sensitive, which nodes already hold caches of the packages it wants; in Kubernetes that would take serious labelling of every node. Hence an amusing detail: an already-scheduled task takes some twenty to twenty-five seconds to start, around 80% of that on copying packages, so artefacts are shared between machines rather than served centrally — one participant recalls something torrent-like, or perhaps tree-like.

The history of packing is a history of experiments: new workloads were first spread thinly across all machines, then packed tightly by best fit, which left idle machines and batch tasks unable to scavenge leftovers from densely booked neighbours; the team settled on a combined variant and tuned it. The participants note almost no rigid policies: nearly everything is settled by experiment. Google has no fixed flavours either: the authors calculated that introducing them, starting, as one participant recalls, at half a CPU and a gigabyte of memory, doubling each step and rounding requests up, would need some twenty per cent more hardware. What does work is reclaiming resources: roughly every 300 seconds the borglet sends the master usage statistics for a job, and the master may claw part of it back, and a low-priority workload beside a more important one can simply be evicted. Kubernetes has nothing of the sort, so low-latency and batch workloads end up in separate clusters; at Google's scale a couple of points of utilisation are worth millions of dollars.

Almost all of the authors' conclusions come not from a live cluster but from a simulator — a fake master that loads the whole state and change log into itself, brings up stubs in place of the borglets, and replays what happened under different settings. Utilisation is measured through compaction: how far a cell can be shrunk by removing machines while the workloads still fit — the same knapsack, narrowing while the items stay the same. The data comes from a single day and is replayed many times; one experiment needed 200 thousand cores — far from trivial even at Google's scale, and beyond many companies. That is why the heuristics matter: without a cached score per node, equivalence classes of tasks and random sampling of a subset of nodes, scheduling may fail to converge even in three days, whereas with them a cold start takes around 200 seconds and an ordinary decision, as one participant remembers it, about half a second. The simulations also showed that splitting applications into separate smaller cells is a bad idea: it would take tens of per cent more hardware.

Borg builds isolation out of what the Linux system itself provides, and virtual machines appear in the paper only as a security sandbox for external workloads such as App Engine and Compute Engine, where the guest runs as a KVM process inside a Borg task. The paper carries more than eighty references, half of them in related work: Apache Mesos, Omega — built to replace Borg but never took hold — and Kubernetes itself, then only just starting out. The authors split their lessons into the good and the bad, and the hosts joke that the trio is missing its ugly. The bad: no proper labels, a single physical IP per machine hosting between 9 and 25 tasks with an endless fight over ports, and 230 tunable parameters, on top of which automation had to be built for people unwilling to learn them. The good: alloc, the forerunner of pods, and detailed introspection. At the end the participants answer their opening question: utilisation and flexibility outweigh the convenience of Kubernetes, everything at Google already runs on Borg, BigTable included, and such a double-edged tool only works in very strong hands.