Papers
Large-scale cluster management at Google with Borg
Abhishek Verma, Luis Pedrosa, Madhukar Korupolu, David Oppenheimer, Eric Tune, John Wilkes · EuroSys 2015, 2015
The problem: running all of Google's workload on tens of thousands of machines
Borg is Google's cluster manager: it admits, schedules, starts, restarts, and monitors the applications the company runs. The paper presents it with three main benefits: hiding the details of resource management and failure handling, so users can focus on the application; operating with high reliability and availability; and allowing workloads to run efficiently across tens of thousands of machines. The workload is heterogeneous and has two parts. The first is long-running services that should never go down and serve latency-sensitive requests (products like Gmail and search, plus internal infrastructure such as BigTable). The second is batch jobs, which take from a few seconds to a few days and tolerate performance fluctuations better. The authors call the higher-priority jobs production (prod) and the rest non-production (non-prod). In a representative cell, prod jobs are allocated about 70% of the CPU and use about 60% of the total CPU. For memory, they are allocated about 55% and account for about 85% of usage. The difference between what is allocated and what is actually used becomes central later on, in resource reclamation.
The user's view: jobs, tasks, allocs, priority, and quota
The user submits work to Borg in the form of jobs, each with one or more tasks that run the same program. Each task runs as a set of Linux processes inside a container, and not in virtual machines, because the authors did not want to pay the cost of virtualization. A job runs in a single cell, which is the set of machines managed as a unit; the median cell has about 10 thousand machines. An alloc is a reserved set of resources on a machine, which stays assigned whether or not it is in use and can group tasks from different jobs. Every job has a priority, and a high-priority task can obtain resources at the expense of a lower-priority one, including by killing it (preemption). To avoid preemption cascades, tasks in the production priority band do not preempt one another. Quota is expressed as a vector of resources per priority and per period, and it is checked in admission control: a job without enough quota is rejected at submission, rather than waiting. Quota at the highest priority costs more, and priority-zero quota is treated as infinite, which makes the system sell more than exists at that level.
Architecture: replicated Borgmaster, Borglets and the scheduler
A cell has a logically centralized controller, the Borgmaster, and an agent called the Borglet on each machine. The Borgmaster is logically a single process, but in practice it is replicated five times. Each replica keeps the cell's state in memory, also written to a distributed store based on Paxos. An elected master acts as the Paxos leader and as the sole state mutator. Election and failover usually take about 10 seconds, and can reach a minute in large cells. The Borgmaster polls each Borglet every few seconds, which gives it control over the communication rate and avoids recovery storms. If a machine stops responding to several polls, it is marked as unavailable and its tasks are rescheduled. An important property is that running tasks keep running even if the entire Borgmaster goes down. The scheduler is a separate process: it asynchronously scans the queue of pending tasks, from highest priority to lowest, and has two phases. The feasibility check finds machines that meet the constraints and have available resources, and scoring picks one of them among the feasible ones.
Scheduling at scale: hybrid scoring, caching, and relaxed randomization
Borg originally used a variant of E-PVM to score machines. In practice, it spread the load across all machines, leaving headroom for spikes, but it fragmented resources and hurt large tasks (what the authors call worst fit). The opposite extreme, best fit, packs machines as tightly as possible, but it penalizes wrong resource estimates and hurts applications with bursty load. The current model is a hybrid that seeks to reduce stranded resources, that is, those that cannot be used because another resource on the machine is already fully allocated. It gives about 3 to 5% more packing efficiency than best fit. To scale to cells with tens of thousands of machines, the paper describes three techniques. Score caching stores the scores until something relevant changes. Equivalence classes evaluate feasibility and scoring only once for a group of tasks with identical requirements. Relaxed randomization examines machines in random order until it finds enough feasible ones, instead of scoring all of them. The scheduler was also separated from the Borgmaster and works on a cached copy of the state, similar to optimistic concurrency control. According to the authors, an online pass over the pending queue normally finishes in less than half a second.
Utilization and trade-offs: sharing machines and reclaiming resources
A central goal of Borg is to use the fleet well, because gaining a few percentage points of utilization saves a lot of money. To compare policies, the authors use cell compaction: given a workload, they measure how small the cell can get by removing machines until the workload no longer fits. With this metric, they show that separating prod and non-prod into different cells would require 20 to 30% more machines in the median cell. This happens because prod jobs tend to reserve more than they use, and Borg reuses that slack for non-prod work. In shared cells, 98% of machines run both types of task. The mechanism is resource reclamation: the Borgmaster estimates each task's reservation every few seconds, starting from the requested limit and slowly decaying toward actual usage plus a safety margin. Prod tasks never depend on reclaimed resources; non-prod tasks use the reservations and, if the estimate is wrong and resources run short, they are killed or throttled, never the prod ones. About 20% of the workload runs on reclaimed resources in the median cell. The paper also shows the cost of alternatives: rounding requests up to powers of 2 would require 30 to 50% more resources in the median case.
See the ideas at work
Practice the designs that use this paper in the System Design school.