Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published April 2014 | Published + Presentation
Book Section - Chapter Open

GRASS: Trimming Stragglers in Approximation Analytics


In big data analytics, timely results, even if based on only part of the data, are often good enough. For this reason, approximation jobs, which have deadline or error bounds and require only a subset of their tasks to complete, are projected to dominate big data workloads. Straggler tasks are an important hurdle when designing approximate data analytic frameworks, and the widely adopted approach to deal with them is speculative execution. In this paper, we present GRASS, which carefully uses speculation to mitigate the impact of stragglers in approximation jobs. GRASS's design is based on first principles analysis of the impact of speculation. GRASS delicately balances immediacy of improving the approximation goal with the long term implications of using extra resources for speculation. Evaluations with production workloads from Facebook and Microsoft Bing in an EC2 cluster of 200 nodes shows that GRASS increases accuracy of deadline-bound jobs by 47% and speeds up error-bound jobs by 38%. GRASS's design also speeds up exact computations (zero error-bound), making it a unified solution for straggler mitigation.

Additional Information

© 2014 Usenix Association. We thank our shepherd Nina Taft and the anonymous reviewers for their suggestions to improve this work. We also thank Rohan Gandhi for his feedback on our early drafts. This research was partially funded by research grant NSF CNS-1319820, NSF CISE Expeditions award CCF-1139158, the DARPA XData Award FA8750-12-2-0331, and gifts from Qualcomm, Amazon Web Services, Google, SAP, Blue Goji, Cisco, Clearstory Data, Cloudera, Ericsson, Facebook, General Electric, Hortonworks, Huawei, Intel, Microsoft, NetApp, Oracle, Quanta, Samsung, Splunk, VMware and Yahoo!.

Attached Files

Presentation - ananthanarayanan.mp4

Published - nsdi14-paper-ananthanarayanan.pdf

Published - nsdi14_slides_ananthanarayanan.pdf


Files (132.3 MB)
Name Size Download all
1.9 MB Preview Download
816.9 kB Preview Download
129.6 MB Download

Additional details

August 20, 2023
August 20, 2023