Google Borg: the ancestor of Kubernetes

01 · CONTEXT

What Borg solves

Borg is Google's cluster manager. According to the paper, it admits, schedules, starts, restarts, and monitors the full range of applications the company runs. The text lists three benefits: hiding the details of resource management and failure handling, operating with very high reliability and availability, and allowing workloads to run across tens of thousands of machines.

The workload is heterogeneous. On one side there are long-running services that, in principle, should never go down and serve short latency-sensitive requests. On the other there are batch jobs, which take from a few seconds to a few days and are far less sensitive to short-term fluctuations. Borg has to handle all of these cases well.

Borg users submit jobs, and each job has one or more tasks that run the same program. Each job runs in a single cell, a set of machines managed as a unit. A cluster usually hosts one large cell and, sometimes, a few smaller cells for testing or special use; the median cell has about ten thousand machines, excluding test ones.

02 · CELL ARCHITECTURE

Borgmaster, Borglets, and a Paxos store

A cell has machines, a logically centralized controller, the Borgmaster, and an agent on each machine, the Borglet. Each cell's Borgmaster is made up of two processes: the main one and a separate scheduler.

The Borgmaster is logically a single process, but it is replicated five times. The cell state is also written to a distributed store based on Paxos. A single elected master per cell is at once the Paxos leader and the one that mutates state. Electing a new master and failing over typically takes about 10 s, and can reach a minute in a large cell, because some of the in-memory state must be reconstructed.

The Borglet starts and stops tasks, restarts those that fail, manages local resources, and reports machine state. It is the Borgmaster that polls each Borglet every few seconds. This design gives the Borgmaster control over the communication rate, removes the need for an explicit flow-control mechanism, and avoids recovery storms.

1. The user operates the job through RPC; the most common case is a command-line tool.

2. The elected master records the job persistently in the Paxos store and adds the tasks to the pending queue.

3. The Borgmaster is replicated and the state lives in the Paxos store; only the elected master, which is the Paxos leader, mutates state.

4. The scheduler, in a separate process, scans the queue asynchronously and assigns tasks to machines.

5. The Borglets start and stop tasks and report machine state; the Borgmaster polls them every few seconds.

03 · SCHEDULING

Feasibility, scoring, and preemption

When a job is submitted, the Borgmaster records it persistently and adds its tasks to the pending queue. The scheduler scans this queue asynchronously and assigns tasks to machines that have available resources and meet the job's constraints. The scan goes from highest to lowest priority, with round-robin within each priority to ensure fairness among users and prevent a large job from blocking the queue.

The algorithm has two parts: the feasibility check, which finds the machines where the task could run, and scoring, which picks one of the feasible ones.

1. The Borgmaster records the job and adds its tasks to the pending queue.

2. The scheduler scans the queue from highest to lowest priority, with round-robin within each priority.

3. Feasibility filters machines that meet the task's constraints and have resources, including those occupied by lower-priority tasks that can be evicted.

4. Scoring chooses among the feasible machines, taking into account, among other criteria, few and low preemptions, machines that already have the task's packages, and spreading across power and failure domains.

5. If the chosen machine has no room, Borg preempts lower-priority tasks, from lowest to highest, and puts them back in the pending queue.

6. The scheduler informs the master of the assignments, which applies them if they are appropriate, and the machine's Borglet starts the task.

The current model is a hybrid that tries to reduce stranded resources, those that cannot be used because another resource on the machine is fully allocated. The paper reports about 3–5% better packing efficiency over best fit on Google's workloads.

When more work arrives than fits, Borg turns to priority and quota. There are non-overlapping priority bands, in decreasing order: monitoring, production, batch, and best effort. Preemption cascades could occur; to eliminate most of them, tasks in the production band cannot preempt one another. Quota decides which jobs are admitted and is checked at admission, not at scheduling: a job without enough quota is rejected immediately at submission.

A task's startup time is highly variable, with a typical median of about 25 s, and package installation accounts for about 80% of the total. That is why the scheduler prefers machines that already have the necessary packages.

04 · SCHEDULER SCALE

How a large cell stays fast

A single Borgmaster manages many thousands of machines, and several cells have arrival rates above 10,000 tasks per minute. The first versions had a simple synchronous loop that accepted requests, scheduled tasks, and talked to the Borglets. To escalar larger cells, the scheduler was split into another process, which operates in parallel with the Borgmaster's other replicated functions.

A scheduler replica operates on a cached copy of the cell state. The master accepts the assignments unless they are inappropriate, for example because they came from stale state, in which case they are reconsidered on the next pass. The paper compares the idea to Omega's optimistic concurrency control.

The authors measure the effect of the whole: scheduling a cell's entire workload from scratch took a few hundred seconds, but did not finish in more than 3 days with the techniques turned off. In normal operation, an online pass over the pending queue finishes in under half a second.

05 · FAILURES AND AVAILABILITY

Failures are the norm

The paper starts from the premise that failures are the norm in large-scale systems. Applications should handle them with replication, persistent state in a distributed file system, and checkpoints, and Borg still tries to reduce the impact: it automatically reschedules evicted tasks, spreads a job's tasks across failure domains such as machines, racks, and power domains, and uses declarative representations of desired state with idempotent operations, so that a client that failed can resubmit forgotten requests without harm.

1. A Borglet stops responding to several Borgmaster polls.

2. The machine is marked down and the tasks that ran on it are rescheduled on other machines.

3. If communication returns, the Borgmaster tells the Borglet to kill the tasks that were already rescheduled, to avoid duplicates.

4. In another scenario, if all Borgmaster replicas fail, the Borglets keep operating and the running tasks stay up.

5. Even so, keeping the master up matters: with it down, new jobs cannot be submitted and existing ones cannot be updated, and tasks on failed machines are not rescheduled.

Borgmaster reaches 99.99% disponibilidade in practice by combining replication, admission control against overload, and deployment with simple, low-level tools to reduce external dependencies. Each cell is independent of the others to reduce correlated operator errors and failure propagation, and the paper says these goals, not scalability limits, are the main argument against larger cells.

One design detail: Borg limits the rate at which it finds new places for tasks from unreachable machines, because it cannot tell a large-scale machine failure from a network partition.

Creating and placing tasks is not enough, since clients need to find them even after they are relocated. Borg creates a stable BNS name per task, made of the cell name, the job name, and the task number, and writes the task's host and port to a consistent, highly available file in Chubby, which the RPC system uses to find the endpoint. It also writes the job size and the tasks' health whenever they change, so that the balanceadores can see where to route.

1. Borg writes the task's host and port to a Chubby file, identified by the task's stable BNS name.

2. Whenever the job size or the tasks' health changes, Borg updates this information in Chubby.

3. The load balancer uses this information to know where to route requests.

4. The client can find the task on the machine where it is now, even after it was relocated.

Each task also publishes its own health: almost every task has a built-in HTTP server that publishes health information, and Borg monitors the health-check URL and restarts tasks that do not respond quickly or return an HTTP error.

06 · UTILIZATION

Sharing machines and reusing reservations

One of Borg's central goals is to use the machine fleet well: raising utilization by a few percentage points can save millions of dollars.

Almost all machines run prod and non-prod tasks at the same time: 98% of machines in shared cells and 83% across the whole fleet. Segregating the two workloads into separate cells would require 20–30% more machines in the median cell, because prod jobs reserve resources for rare peaks and do not use them most of the time, whereas Borg reclaims what is not used.

Resource reclamation works like this: Borg estimates how much a task will use and reclaims the rest for work that tolerates lower-quality resources, such as batch. The scheduler uses the limits in the feasibility calculation for prod tasks, so they never depend on reclaimed resources or get exposed to overload; for non-prod tasks, it uses the reservations of existing tasks. About 20% of the workload runs on reclaimed resources in the median cell.

When a machine runs short of a resource, the reaction depends on the resource type. Compressible resources, such as CPU cycles and disk bandwidth, can be reduced without killing the task; non-compressible ones, such as memory and disk space, generally cannot. Without non-compressible resources, the Borglet kills tasks from lowest to highest priority; without compressible resources, it throttles usage, favoring latency-sensitive tasks, and so absorbs short spikes without killing tasks.

Resource requests are fine-grained: CPU in milli-cores, memory and disk in bytes, with no fixed-size buckets or slots. Rounding prod job limits up to the next power of two would require 30–50% more resources in the median case. Likewise, splitting a cell into smaller cells would require significantly more machines.

Sharing machines requires isolation. All tasks run in resource containers based on Linux cgroups, and a chroot is the main security isolation mechanism between tasks on the same machine. High-priority latency-sensitive (LS) tasks get the best treatment and can starve batch tasks of CPU for a few seconds.

07 · LESSONS AND THE PATH TO KUBERNETES

What Borg taught

The paper closes with qualitative lessons from operating Borg in production for more than a decade and how they were carried into the design of Kubernetes. According to the authors, virtually all of Google's cluster workloads have migrated to Borg.

Two other lessons deserve mention. The first is optimizing for power users at the expense of casual ones: the BCL specification lists about 230 parameters, and the richness of the API makes life hard for the casual user and limits its evolution. The second is that introspection is vital: Borg exposes debugging information to all users instead of hiding it, because with thousands of users, self-help has to be the first step.