Large-scale cluster management at Google with Borg
Published 13 April 2015Open access
Abhishek Verma, Luis Pedrosa, Madhukar Korupolu, David Oppenheimer, Eric Tune, John Wilkes
Citations1,345
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A summary of the Borg system architecture and features, important design decisions, a quantitative analysis of some of its policy decisions, and a qualitative examination of lessons learned from a decade of operational experience with it are presented.
Abstract
Google's Borg system is a cluster manager that runs hundreds of thousands of jobs, from many thousands of different applications, across a number of clusters each with up to tens of thousands of machines.
Keywords
Computer Science
Communications of the ACMMapReduce
18,538 Citations2008Jay B. Dean, Sanjay Ghemawat
This presentation explains how the underlying runtime system automatically parallelizes the computation across large-scale clusters of machines, handles machine failures, and schedules inter-machine communication to make efficient use of the network and disks.
ACM SIGOPS Operating Systems ReviewThe Google file system
5,003 Citations2003Sanjay Ghemawat, Howard Gobioff +1 more
Pregel
3,534 Citations2010Grzegorz Malewicz, Matthew H. Austern +5 more
A model for processing large graphs that has been designed for efficient, scalable and fault-tolerant implementation on clusters of thousands of commodity computers, and its implied synchronicity makes reasoning about programs easier.
ACM Transactions on Computer SystemsBigtable
3,432 Citations2008Fay W. Chang, Jay B. Dean +7 more
The simple data model provided by Bigtable is described, which gives clients dynamic control over data layout and format, and the design and implementation of Bigtable are described.
ACM Transactions on Computer SystemsThe part-time parliament
2,714 Citations1998Leslie Lamport
The Paxon parliament's protocol provides a new way of implementing the state machine approach to the design of distributed systems.
Condor-a hunter of idle workstations
2,272 Citations2003Michael Litzkow, Miron Livny +1 more
The design, implementation, and performance of the Condor scheduling system, which operates in a workstation environment, are presented and a performance profile of the system is presented that is based on data accumulated from 23 stations during one month.
Apache Hadoop YARN
1,816 Citations2013Vinod Kumar Vavilapalli, Arun C. Murthy +14 more
The design, development, and current state of deployment of the next generation of Hadoop's compute platform: YARN is summarized, which decouples the programming model from the resource management infrastructure, and delegates many scheduling functions to per-application components.
Synthesis lectures on computer architectureThe Datacenter as a Computer: An Introduction to the Design of Warehouse-Scale Machines
1,746 Citations2009Luiz André Barroso, Urs Hölzle
The architecture of WSCs is described, the main factors influencing their design, operation, and cost structure, and the characteristics of their software base are described.
Communications of the ACMThe tail at scale
1,740 Citations2013Jay B. Dean, Luiz André Barroso
Software techniques that tolerate latency variability are vital to building responsive large-scale Web services.
UC BerkeleyMesos: a platform for fine-grained resource sharing in the data center
1,593 Citations2011Benjamin Hindman, Andy Konwinski +6 more
The results show that Mesos can achieve near-optimal data locality when sharing the cluster among diverse frameworks, can scale to 50,000 (emulated) nodes, and is resilient to failures.
The Google file system
1,366 Citations2003Sanjay Ghemawat, Howard Gobioff +1 more
This paper presents file system interface extensions designed to support distributed applications, discusses many aspects of the design, and reports measurements from both micro-benchmarks and real world use.
UC BerkeleyDominant resource fairness: fair allocation of multiple resource types
1,085 Citations2011Ali Ghodsi, Matei Zaharia +4 more
Dominant Resource Fairness (DRF), a generalization of max-min fairness to multiple resource types, is proposed, and it is shown that it leads to better throughput and fairness than the slot-based fair sharing schemes in current cluster schedulers.
Heterogeneity and dynamicity of clouds at scale
1,029 Citations2012Charles Reiss, Alexey Tumanov +3 more
Analysis of the first publicly available trace data from a sizable multi-purpose cluster finds that many longer-running jobs have relatively stable resource utilizations, which can help adaptive resource schedulers.
IEEE MicroWeb search for a planet: the google cluster architecture
1,026 Citations2003Luiz André Barroso, Jay B. Dean +1 more
Googless architecture features clusters of more than 15,000 commodity-class PCs with fault tolerant software that achieves superior performance at a fraction of the cost of a system built from fewer, but more expensive, high-end servers.
Operating Systems Design and ImplementationThe Chubby lock service for loosely-coupled distributed systems
899 Citations2006Mike Burrows
The paper describes the initial design and expected use, compares it with actual use, and explains how the design had to be modified to accommodate the differences.
Quincy
852 Citations2009Michael Isard, Vijayan Prabhakaran +4 more
It is argued that data-intensive computation benefits from a fine-grain resource sharing model that differs from the coarser semi-static resource allocations implemented by most existing cluster computing architectures.
Matchmaking: distributed resource management for high throughput computing
756 Citations2002Rajesh Raman, Miron Livny +1 more
The classified advertisement (classad) matchmaking framework is developed and implemented, a flexible and general approach to resource management in distributed environment with decentralized ownership of resources.
Proceedings of the VLDB EndowmentDremel
709 Citations2010Sergey Melnik, Andrey Gubarev +5 more
This paper describes the architecture and implementation of Dremel, and explains how it complements MapReduce-based computing, and presents a novel columnar storage representation for nested records.
Quasar
698 Citations2014Christina Delimitrou, Christos Kozyrakis
This work presents Quasar, a cluster management system that increases resource utilization while providing consistently high application performance, over a wide range of workload scenarios, including combinations of distributed analytics frameworks and low-latency, stateful services.
Megastore: Providing Scalable, Highly Available Storage for Interactive Services
654 Citations2011Jason D. Baker, Chris T. Bond +8 more
Megastore provides fully serializable ACID semantics within ne-grained partitions of data, which allows us to synchronously replicate each write across a wide area network with reasonable latency and support seamless failover between datacenters.
Omega
638 Citations2013Malte Schwarzkopf, Andy Konwinski +2 more
This work presents a novel approach to address increasing scale and the need for rapid response to changing requirements using parallelism, shared state, and lock-free optimistic concurrency control to address monolithic cluster scheduler architectures.
Paragon
618 Citations2013Christina Delimitrou, Christos Kozyrakis
Paragon is an online and scalable DC scheduler that is heterogeneity and interference-aware, derived from robust analytical methods and uses collaborative filtering techniques to quickly and accurately classify an unknown, incoming workload, by identifying similarities to previously scheduled applications.
Bubble-Up
598 Citations2011Jason Mars, Lingjia Tang +3 more
Bubble-Up is presented, a characterization methodology that enables the accurate prediction of the performance degradation that results from contention for shared resources in the memory subsystem and can predict the performance interference between co-locate applications with an accuracy within 1% to 2% of the actual performance degradation.
Proceedings of the VLDB EndowmentMillWheel
533 Citations2013Tyler Akidau, Alex Balikov +8 more
In practice, this paper finds that MillWheel's unique combination of scalability, fault tolerance, and a versatile programming model lends itself to a wide variety of problems at Google.
Synthesis lectures on computer architectureThe Datacenter as a Computer: An Introduction to the Design of Warehouse-Scale Machines, Second edition
491 Citations2013Luiz André Barroso, Jimmy Clidaras +1 more
The architecture of WSCs is described, the main factors influencing their design, operation, and cost structure, and the characteristics of their software base are described.
Multi-resource packing for cluster schedulers
418 Citations2014Robert Grandl, Ganesh Ananthanarayanan +3 more
ACM SIGMETRICS Performance Evaluation ReviewTowards characterizing cloud backend workloads
378 Citations2010Asit Mishra, Joseph L. Hellerstein +2 more
An approach to workload classification and its application to the Google Cloud Backend, arguably the largest cloud backend on the planet is described.
Lecture notes in computer scienceCore Algorithms of the Maui Scheduler
363 Citations2001David Jackson, Quinn Snell +1 more
This paper focuses on three areas of Maui scheduling, specifically, backfill, job prioritization, and fairshare and briefly discusses the goals of each component, the issues and corresponding design decisions, and the algorithms enabling the Maui policies.
FlumeJava
336 Citations2010Craig Chambers, Ashish Raniwala +5 more
The combination of high-level abstractions for parallel data and computation, deferred evaluation and optimization, and efficient parallel primitives yields an easy-to-use system that approaches the efficiency of hand-optimized pipelines.
An Analysis of Traces from a Production MapReduce Cluster
317 Citations2010Soila Kavulya, Jiaqi Tan +2 more
This paper analyzes 10-months of MapReduce logs from the M45 supercomputing cluster which Yahoo! made freely available to select universities for academic research to characterize resource utilization patterns, job patterns, and sources of failures.
Operating Systems Design and ImplementationApollo: scalable and coordinated scheduling for cloud-scale computing
303 Citations2014Éric Boutin, Jaliya Ekanayake +6 more
CPI <sup>2</sup>
283 Citations2013Xiao Zhang, Eric Tune +4 more
CPI2, which uses cycles-per-instruction (CPI) data obtained by hardware performance counters to identify problems, select the likely perpetrators, and then optionally throttle them so that the victims can return to their expected behavior.
Cambridge University Press eBooksWorkload Modeling for Computer Systems Performance Evaluation
255 Citations2015Dror G. Feitelson
Using this book, readers will be able to analyze collected workload data and clean it if necessary, derive statistical models that include skewed marginal distributions and correlations, and consider the need for generative models and feedback from the system.
Synthesis lectures on computer architectureThe Datacenter as a Computer
245 Citations2013Luiz André Barroso, Jimmy Clidaras +1 more
Reconciling high server utilization and sub-millisecond quality-of-service
216 Citations2014Jacob Leverich, Christos Kozyrakis
It is demonstrated that some latency-critical workloads can be aggressively co-located with other workloads, achieve good QoS, and that such co-location can improve a datacenter's effective throughput per TCO-$ by up to 52%.
ACM SIGOPS Operating Systems ReviewAutopilot
203 Citations2007Michael Isard
The first version of Autopilot is described, the automatic data center management infrastructure developed within Microsoft over the last few years, responsible for automating software provisioning and deployment; system monitoring; and carrying out repair actions to deal with faulty software and hardware.
Modeling and synthesizing task placement constraints in Google compute clusters
185 Citations2011Bikash Sharma, Victor Chudnovsky +3 more
This paper develops methodologies for incorporating task placement constraints and machine properties into performance benchmarks of large compute clusters and provides a simple model of the performance impact of constraints in that task scheduling delays increase with UM.
Choosy
176 Citations2013Ali Ghodsi, Matei Zaharia +2 more
This work proposes Constrained Max-Min Fairness (CMMF), an extension to max-min fairness that supports placement constraints, and shows that it is the only policy satisfying an important property that incentivizes users to pool resources.
IEEE Transactions on Parallel and Distributed SystemsAn opportunity cost approach for job assignment in a scalable computing cluster
174 Citations2000Yair Amir, Baruch Awerbuch +3 more
A new method is presented for job assignment to and reassignment between machines in a computing cluster based on a theoretical framework that has been experimentally tested and shown to be useful in practice, and was found to perform well.
Characterization and Comparison of Cloud versus Grid Workloads
171 Citations2012Sheng Di, Derrick Kondo +1 more
This paper comprehensively characterize the job/task load and host load in a real-world production data center at Google Inc, using a detailed trace of over 25 million tasks across over 12,500 hosts.
AT&T Bell Laboratories Technical JournalOpen and Closed Models for Networks of Queues
164 Citations1984Ward Whitt
This paper investigates ways to use open models to approximate closed models with specified expected equilibrium populations, especially effective for approximately solving large closed models, where “large” may mean many nodes or many jobs.
Beyond dominant resource fairness
163 Citations2012David C. Parkes, Ariel D. Procaccia +1 more
It is shown that DRF generalizes to more expressive settings, and is leverage a new technical framework to formally extend its guarantees, and the relation between social welfare and properties such as truthfulness is studied.
Proceedings of the VLDB EndowmentFuxi
151 Citations2014Zhuo Zhang, Chao Li +4 more
This paper presents Fuxi, a resource management and job scheduling system that is capable of handling the kind of workload at Alibaba where hundreds of terabytes of data are generated and analyzed everyday to help optimize the company's business operations and user experiences.
Characterizing Machines and Workloads on a Google Cluster
143 Citations2012Zitao Liu, Sangyeun Cho
This paper characterizes how the machines in the cluster are managed and the workloads submitted during a 29-day period behave and focuses on the frequency and pattern of machine maintenance events, job- and task-level workload behavior, and how the overall cluster resources are utilized.
Reservation-based Scheduling
133 Citations2014Carlo Curino, Djellel Difallah +4 more
This paper proposes a reservation definition language (RDL) that allows users to declaratively reserve access to cluster resources, and formalizes planning of current and future cluster resources as a Mixed-Integer Linear Programming (MILP) problem, and proposes scalable heuristics.
Apress eBooksGoogle Compute Engine
128 Citations2015S. P. T. Krishnan, Jose L. Ugia Gonzalez
Google Compute Engine is an infrastructure service provided as part of the Google Cloud Platform that neither charges any upfront fees for deployment nor locks down the customer.
No justified complaints
117 Citations2012Danny Dolev, Dror G. Feitelson +3 more
This work provides a new definition for the simultaneous fair allocation of multiple continuously-divisible resources that is called bottleneck-based fairness (BBF), and shows that BBF has several desirable properties such as providing an incentive for sharing, and also promotes high overall utilization of resources.
Characterizing Cloud Applications on a Google Data Center
114 Citations2013Sheng Di, Derrick Kondo +1 more
This paper characterize Google applications, based on a one-month Google trace with over 650k jobs running across over 12,000 heterogeneous hosts from a Google data center, via a K-means clustering algorithm with optimized number of sets,based on task events and resource usage.
On designing and deploying internet-scale services
104 Citations2007James R. Hamilton
This paper summarizes the best practices accumulated over many years in scaling some of the largest services at MSN and Windows Live.
IEEE International Conference on High Performance Computing, Data, and AnalyticsMeasuring interference between live datacenter applications
90 Citations2012Melanie Kambadur, Tipp Moseley +2 more
Characterizing Task Usage Shapes in Google Compute Clusters
72 Citations2011Qi Zhang, Joseph L. Hellerstein +1 more
Through experiments using workload traces from Google production clusters, it is found that simply using the mean of task usage can generate synthetic workload traces that accurately reproduce resource utilizations and task waiting time.
An Opportunity Cost Approach for Job Assignment and Reassignment in a Scalable Computing Cluster
57 Citations2002Yair Amir, Baruch Awerbuch +3 more
A new method is presented for job assignment to and reassignment between machines in a computing cluster that converts the usage of several heterogeneous resources in a machine to a single homogeneous “cost.”
alsched
54 Citations2012Alexey Tumanov, James Cipar +2 more
The need for and an approach for accommodating diverse tenant needs, based on having resource requests indicate any soft and hard constraints in the form of composable utility functions, are promoted.
Design Insights for MapReduce from Diverse Production Workloads
52 Citations2012Yanpei Chen, Sara Alspaugh +1 more
This paper analyzes seven MapReduce workload traces from production clusters at Facebook and at Cloudera customers in e-commerce, telecommunications media, and retail and deploys a public workload repository with workload replay tools so that the researchers can systematically assess design priorities and compare performance across diverse Map Reduce workloads.
Towards Understanding the Usage Behavior of Google Cloud Users: The Mice and Elephants Phenomenon
46 Citations2014Omar Abdul-Rahman, Kento Aida
This study considers user behavior in composing applications from the perspective of topology, maximum requested computational resources, and workload type and model user dynamic behavior around the user's session view to reveal interesting insight into the heterogeneous structure of the Google cloud workload.
CPU bandwidth control for CFS
41 Citations2010Paul Turner, Bharata B Rao +1 more
The requirements behind this feature, the challenges involved in incorporating into CFS (Completely Fair Scheduler), and the future development road map for this feature are detailed.
IEEE Transactions on Parallel and Distributed SystemsOn Simulation and Design of Parallel-Systems Schedulers: Are We Doing the Right Thing?
39 Citations2008Edi Shmueli, Dror G. Feitelson
A novel scheduler called CREASY is presented that exploits knowledge on user behavior to directly improve user satisfaction and is compared to the original packing-based EASY scheduler, showing that user productivity improves by up to 50 percent under the user-aware design, while according to the conventional metrics, performance may actually degrade.
Selling T-shirts and Time Shares in the Cloud
35 Citations2012Daniel Gmach, Jerry Rolia +1 more
Private and public clouds should consider offering both resource sharing models to meet the needs of customers, and a tool is presented to help customers make informed decisions about which approach works most efficiently for their workloads in aggregate and for each workload separately.
Evaluating job packing in warehouse-scale computing
35 Citations2014Abhishek Verma, Madhukar Korupolu +1 more
This paper explains some of the complexities and issues in evaluating warehouse scale schedulers, focusing on what it finds to be the single most important aspect in practice: how well they pack long-running services into a cluster.
HaPPy: hyperthread-aware power profiling dynamically
33 Citations2014Yan Zhai, Xiao Zhang +3 more
A hyperthread-aware power model that differentiates between the states when both hardware threads of a core are in use, and when only one thread is in use is introduced, able to accurately attribute power to each logical CPU in modern servers.
ACM SIGOPS Operating Systems ReviewAvailability in the Sprite distributed file system
21 Citations1991Mary Baker, John K. Ousterhout
This work aims to reduce file server recovery times to less than 90 seconds, and takes advantage of the distributed state already present in the file system, and a high-performance log-structured file system currently under implementation.