ROME: All Overlays Lead to Aggregation, but Some Are Faster than Others

Venue

(to appear/just accepted) ACM Transactions on Computer Systems 2022

Abstract

Aggregation is common in data analytics and crucial to distilling information from large datasets, but current data analytics frameworks do not fully exploit the potential for optimization in such phases. The lack of optimization is particularly notable in current “online” approaches which store data in main memory across nodes, shifting the bottleneck away from disk I/O toward network and compute resources, thus increasing the relative performance impact of distributed aggregation phases.
We present ROME, an aggregation system for use within data analytics frameworks or in isolation. ROME uses a set of novel heuristics based primarily on basic knowledge of aggregation functions combined with deployment constraints to efficiently aggregate results from computations performed on individual data subsets across nodes (e.g., merging sorted lists resulting from top-k). The user can either provide minimal information which allows our heuristics to be applied directly, or ROME can autodetect the relevant information at little cost. We integrated ROME as a subsystem into the Spark and Flink data analytics frameworks. We use real world data to experimentally demonstrate speedups up to 3 × over single level aggregation overlays, up to 21% over other multi-level overlays, and 50% for iterative algorithms like gradient descent at 100 iterations.

Bibtex

@article{2022-tocs-rome,
 Author = {Bl\"{o}cher, Marcel and Coppa, Emilio and Kleber, Pascal and Eugster, Patrick and Culhane, William and Ardekani, Masoud Saeida},
 Title = {{ROME}: All Overlays Lead to Aggregation, but Some Are Faster than Others},
 Journal={{ACM} Transactions on Computer Systems ({TOCS})},
 Publisher = {{ACM}},
 ISSN = {0734-2071},
 DOI = {10.1145/3516430},
 Month = {jan},
 Year = {2022},
 Note = {Just Accepted}
}