Scalability! but at what cost?
Published 18 May 2015
Frank McSherry, Michael Isard, Derek G. Murray
Citations218
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
This work surveys measurements of data-parallel systems recently reported in SOSP and OSDI, and finds that many systems have either a surprisingly large COST, often hundreds of cores, or simply underperform one thread for all of their reported configurations.
Abstract
We offer a new metric for big data platforms, COST, or the Configuration that Outperforms a Single Thread. The COST of a given platform for a given problem is the hardware configuration required before the platform out-performs a competent single-threaded implementation. COST weighs a system’s scalability against the over-heads introduced by the system, and indicates the actual performance gains of the system, without rewarding sys-tems that bring substantial but parallelizable overheads. We survey measurements of data-parallel systems re-cently reported in SOSP and OSDI, and find that many systems have either a surprisingly large COST, often hundreds of cores, or simply underperform one thread for all of their reported configurations. 1
Keywords
Computer Science
The PageRank Citation Ranking : Bringing Order to the Web
12,645 Citations1999Lawrence M. Page, Sergey Brin +2 more
This paper describes PageRank, a mathod for rating Web pages objectively and mechanically, effectively measuring the human interest and attention devoted to them, and shows how to efficiently compute PageRank for large numbers of pages.
What is Twitter, a social network or a news media?
6,692 Citations2010Haewoon Kwak, Changhyun Lee +2 more
This work is the first quantitative study on the entire Twittersphere and information diffusion on it and finds a non-power-law follower distribution, a short effective diameter, and low reciprocity, which all mark a deviation from known characteristics of human social networks.
Communications of the ACMA bridging model for parallel computation
3,680 Citations1990Leslie G. Valiant
The bulk-synchronous parallel (BSP) model is introduced as a candidate for this role, and results quantifying its efficiency both in implementing high-level language features and algorithms, as well as in being implemented in hardware.
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.
Operating Systems Design and ImplementationPowerGraph: distributed graph-parallel computation on natural graphs
1,503 Citations2012Joseph E. Gonzalez, Yucheng Low +3 more
This paper describes the challenges of computation on natural graphs in the context of existing graph-parallel abstractions and introduces the PowerGraph abstraction which exploits the internal structure of graph programs to address these challenges.
The webgraph framework I
1,215 Citations2004Paolo Boldi, Sebastiano Vigna
This papers presents the compression techniques used in WebGraph, which are centred around referentiation and intervalisation (which in turn are dual to each other).
Operating Systems Design and ImplementationGraphChi: large-scale graph computation on just a PC
900 Citations2012Aapo Kyrola, Guy E. Blelloch +1 more
This work presents GraphChi, a disk-based system for computing efficiently on graphs with billions of edges, and extends GraphChi to support graphs that evolve over time, and demonstrates that, on a single computer, GraphChi can process over one hundred thousand graph updates per second, while simultaneously performing computation.
Ligra
808 Citations2013Julian Shun, Guy E. Blelloch
This paper presents a lightweight graph processing framework that is specific for shared-memory parallel/multicore machines, which makes graph traversal algorithms easy to write and significantly more efficient than previously reported results using graph frameworks on machines with many more cores.
X-Stream
687 Citations2013Amitabha Roy, Ivo Mihailovic +1 more
X-Stream is novel in using an edge-centric rather than a vertex-centric implementation of this model, and streaming completely unordered edge lists rather than performing random access, and competes favorably with existing systems for graph processing.
PEGASUS: A Peta-Scale Graph Mining System Implementation and Observations
637 Citations2009U Kang, Charalampos E. Tsourakakis +1 more
This paper describes PEGASUS, an open source Peta Graph Mining library which performs typical graph mining tasks such as computing the diameter of the graph, computing the radius of each node and finding the connected components, and describes a very important primitive for PEGasUS, called GIM-V (Generalized Iterated Matrix-Vector multiplication).
A lightweight infrastructure for graph analytics
589 Citations2013Donald Nguyen, Andrew Lenharth +1 more
This paper argues that existing DSLs can be implemented on top of a general-purpose infrastructure that supports very fine-grain tasks, implements autonomous, speculative execution of these tasks, and allows application-specific control of task scheduling policies.
Software Practice and ExperienceUbiCrawler: a scalable fully distributed Web crawler
564 Citations2004Paolo Boldi, Bruno Codenotti +2 more
The main features of UbiCrawler are platform independence, linear scalability, graceful degradation in the presence of faults, a very effective assignment function for partitioning the domain to crawl, and more in general the complete decentralization of every task.
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.
Filtering
233 Citations2011Silvio Lattanzi, Benjamin Moseley +2 more
This paper presents new algorithms in the MapReduce framework for a variety of fundamental graph problems for sufficiently dense graphs and implements the maximal matching algorithm that lies at the core of the analysis and achieves a significant speedup over the sequential version.
ACM SIGIR ForumA large time-aware web graph
163 Citations2008Paolo Boldi, Massimo Santini +1 more
The techniques developed to gather and distribute in a highly compressed, yet accessible, form a series of twelve snapshot of the .uk web domain make it possible to study the temporal evolution link-based scores, the growth of online communities, and in general time-dependent phenomena related to the link structure.
Knowledge and Information SystemsPEGASUS: mining peta-scale graphs
158 Citations2010U Kang, Charalampos E. Tsourakakis +1 more
GIM-V (generalized iterated matrix-vector multiplication), an open source Peta Graph Mining library which performs typical graph mining tasks such as computing the diameter of the graph, computing the radius of each node, finding the connected components, and computing the importance score of nodes is described.
The scalable commutativity rule
128 Citations2013Austin T. Clements, M. Frans Kaashoek +3 more
This paper introduces the following rule: Whenever interface operations commute, they can be implemented in a way that scales, which aids developers in building more scalable software starting from interface design and carrying on through implementation, testing, and evaluation.
Proceedings of the VLDB EndowmentSpinning fast iterative data flows
119 Citations2012Stephan Ewen, Kostas Tzoumas +2 more
This work proposes a method to integrate incremental iterations, a form of workset iterations, with parallel dataflows and presents an extension to the programming model for incremental iterations that alleviates for the lack of mutable state in dataflow and allows for exploiting the sparse computational dependencies inherent in many iterative algorithms.
ACM SIGMOD RecordJava support for data-intensive systems
39 Citations2001Mehul A. Shah, Michael J. Franklin +2 more
This paper highlights the pleasures of coding with Java, and some of the pains of coding around Java in order to obtain good performance in a data-intensive server, and presents concrete suggestions for evolving Java's interfaces to better suit serious software systems development.
arXiv (Cornell University)DimmWitted: A Study of Main-Memory Statistical Analytics
17 Citations2014Ce Zhang, Christopher Ré