Stratified Online Sampling for Sound Approximation in MapReduce
Mithuna S. Thottethodi, T. N. Vijaykumar, Milind V. Kulkarni, Nitin Nitin · Purdue e-Pubs (Purdue University System) · 2015
In the era of big data, many applications perform approximate computations to achieve performance improvements by producing less-precise, yet reasonable, results.Hadoop MapReduce is a widely-used big data framework that processes large amounts of data.A recent work, ApproxHadoop, extends Hadoop with a runtime abstraction to produce approximate results with statistical error bounds.ApproxHadoop uses a carefully-designed multistage sampling strategy to guide its approximation without exceeding target error bounds.However, ApproxHadoop suffers from a major limitation: It performs global uniform sampling across the entire key space of input data (modulo the effects of multistage sampling).Such uniform sampling not only oversamples popular keys but also perniciously undersamples rare keys, potentially skipping computations for the latter entirely.We present MaRSOS (MapReduce with Stratified, Online Sampling), to provide approximation with bounded errors across all keys.MaRSOS makes two key contributions to achieve this target: (1) A novel telescoping-based online sampling strategy that performs perkey sampling without missing rare keys; (2) A feedback system that allows efficient collaboration among distributed map tasks to minimize oversampling.Across a range of MapReduce benchmarks, we demonstrate that MaRSOS can deliver performance improvements while (statistically) bounding per-key errors.MaRSOS is guaranteed to never miss rare keys and varies the sampling rate based on key popularity to achieve better per-key errors than a global sampling approach that samples at the same overall rate.