Broom: sweeping out garbage collection from big data systems
Published 18 May 2015
Ionel Gog, Jana Giceva, Malte Schwarzkopf, Kapil Vaswani, Dimitrios Vytiniotis, Ganesan Ramalingan
Citations83
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
The initial results show that region-based memory management reduces emulated Naiad vertex runtime by 34% for typical data analytics jobs, and could be memory-safe and inferred automatically.
Abstract
Many popular systems for processing “big data ” are im-plemented in high-level programming languages with automatic memory management via garbage collection (GC). However, high object churn and large heap sizes put severe strain on the garbage collector. As a result, ap-plications underperform significantly: GC increases the runtime of typical data processing tasks by up to 40%. We propose to use region-based memory management instead of GC in distributed data processing systems. In these systems, many objects have clearly defined life-times. Hence, it is natural to allocate these objects in fate-sharing regions, obviating the need to scan a large heap. Regions can be memory-safe and could be in-ferred automatically. Our initial results show that region-based memory management reduces emulated Naiad ver-tex runtime by 34 % for typical data analytics jobs. 1
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.
Resilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing
3,577 Citations2012Matei Zaharia, Mosharaf Chowdhury +7 more
Resilient Distributed Datasets is presented, a distributed memory abstraction that lets programmers perform in-memory computations on large clusters in a fault-tolerant manner and is implemented in a system called Spark, which is evaluated through a variety of user applications and benchmarks.
Dryad
2,460 Citations2007Michael Isard, Mihai Budiu +3 more
The Dryad execution engine handles all the difficult problems of creating a large distributed, concurrent application: scheduling the use of computers and their CPUs, recovering from communication or computer failures, and transporting data between vertices.
ComputerThe real-time specification for Java
988 Citations2000Greg Bollella, James Gosling
RTSJ's features and the thinking behind the specification's design are explained, which aims to provide a platform-a Java execution environment and application program interface (API) that lets programmers correctly reason about the temporal behavior of executing software.
Discretized streams
964 Citations2013Matei Zaharia, Tathagata Das +4 more
D-Streams enable a parallel recovery mechanism that improves efficiency over traditional replication and backup schemes, and tolerates stragglers, and can easily be composed with batch and interactive query models like MapReduce, enabling rich applications that combine these modes.
S4: Distributed Stream Computing Platform
905 Citations2010Leonardo Neumeyer, Bruce Robbins +2 more
The architecture resembles the Actors model, providing semantics of encapsulation and location transparency, thus allowing applications to be massively concurrent while exposing a simple programming interface to application developers.
Operating Systems Design and ImplementationDryadLINQ: a system for general-purpose distributed data-parallel computing using a high-level language
699 Citations2008Yuan Yu, Michael Isard +5 more
Information and ComputationRegion-Based Memory Management
617 Citations1997Mads Tofte, Jean-Pierre Talpin
A region-based dynamic semantics for a skeletal programming language extracted from Standard ML is defined and the inference system which specifies where regions can be allocated and de-allocated is presented and a detailed proof that the system is sound with respect to a standard semantics is presented.
Communications of the ACMA real-time garbage collector based on the lifetimes of objects
572 Citations1983Henry Lieberman, Carl Hewitt
This work presents a garbage collection algorithm that makes storage for short-lived objects cheaper than storage for long-livedObjects, that operates in real time, increases locality of reference, for better virtual memory performance, and works well with multiple processors and a large address space.
Region-based memory management in cyclone
404 Citations2002Dan Grossman, Greg Morrisett +4 more
This paper focuses on the region-based memory management of Cyclone and its static typing discipline, and combines default annotations, local type inference, and a novel treatment of region effects to reduce this burden.
Networked Systems Design and ImplementationMaking sense of performance in data analytics frameworks
332 Citations2015Kay Ousterhout, Ryan Rasti +3 more
It is found that CPU (and not I/O) is often the bottleneck, and improving network performance can improve job completion time by a median of at most 2%, and the causes of most stragglers can be identified.
A real-time garbage collector with low overhead and consistent utilization
322 Citations2003David F. Bacon, Perry Cheng +1 more
A mostly non-moving, dynamically defragmenting collector is presented that is able to obtain mutator utilization rates of 45% with only 1.6--2.5 times the actual space required by the application, a factor of 4 improvement in utilization over the best previously published results.
Memory management with explicit regions
213 Citations1998David Gay, Alex Aiken
It is shown that on a suite of allocation-intensive C programs, regions are competitive with malloc/free and sometimes substantially faster and that regions support safe memory management with low overhead.
Reconsidering custom memory allocation
182 Citations2002Emery D. Berger, Benjamin G. Zorn +1 more
The results indicate that programmers needing fast regions should use reaps, and that most programmers considering custom allocators should instead use the Lea allocator.
Language support for regions
151 Citations2001David Gay, Alex Aiken
This work generalises type annotations that make the structure of a program's regions more explicit in a region type system whose main novelty is the use of existentially quantified abstract regions to represent pointers to objects whose region is partially or totally unknown.
Experience with safe manual memory-management in cyclone
92 Citations2004Michael Hicks, Greg Morrisett +2 more
This paper found that statically-scoped regions and unique pointers can be combined to build alternative memory-management abstractions, such as reference counted objects and arenas with dynamic lifetimes, and thus provide a flexible basis for type safety.
FACADE
91 Citations2015Khanh Nguyen, Kai Wang +4 more
A novel compiler framework, called Facade, that can generate highly-efficient data manipulation code by automatically transforming the data path of an existing Big Data application by leading to significantly reduced memory management cost and improved scalability.
Combining region inference and garbage collection
90 Citations2002Niels Hallenberg, Martin Elsman +1 more
Measurements show that for a variety of benchmark programs, code generated by the compiler is as efficient, both with respect to execution time and memory usage, as programs compiled with Standard ML of New Jersey, another state-of-the-art Standard ML compiler.
Trash day: coordinating garbage collection in distributed systems
62 Citations2015Martin Maas, Tim Harris +2 more
This paper proposes a Holistic Runtime System, a distributed language runtime that collectively manages runtime services across multiple nodes that is effective both in reducing the impact of GC pauses on a batch workload, and in improving GC-related tail-latencies in an interactive setting.
A bloat-aware design for big data applications
56 Citations2013Yingyi Bu, Vinayak Borkar +2 more
Experimental results show that this new design paradigm is extremely effective in improving performance --- even for the moderate-size data sets processed, there are 2.5x+ performance gains, and the improvement grows substantially with the size of the data set.
Communications of the ACMThe Singularity system
23 Citations2010James R. Larus, Galen Hunt
Safe, modern programming languages let Microsoft rethink the architectural trade-offs in its experimental operating system.