Spark tree aggregation improved to reduce memory load on driver
TreeRedux: Separating Concerns in Spark's Distributed Tree Aggregation
Distributed, Parallel, and Cluster Computing
Summary
Apache Spark is a tool for handling big data by breaking tasks into smaller parts arranged like a tree. Usually, the final step of combining all the parts happens on the main controller called the driver, which can cause it to run out of memory when working with very large data. The authors show this problem with examples like finding exact data rankings and tracking common items. They introduce TreeRedux, a method that finishes data combining earlier on worker nodes, sending a smaller summary to the driver instead. This approach reduces the driver's memory needs and allows Spark to handle much bigger data sets without errors.
Apache Sparktree aggregationdriver nodeexecutor nodesexact quantile computationheavy-hitter identificationmemory requirementsfinalize operationSpace-Saving sketchesGK Select
Authors
David A. G. Harrison, Ivan Cao
Abstract
By default, Apache Spark's tree aggregation primitives place the tree root on the driver, requiring the driver to participate in the same aggregation computation over intermediate aggregation state as executor nodes. For large aggregates, this can expose the single coordinator to substantial computation and memory requirements. Recent Spark versions optionally move the root to an executor, but the completed aggregate must still be returned to and materialized on the driver. We demonstrate this limitation using exact quantile computation and heavy-hitter identification, where the intermediate aggregation state can be substantially larger than the desired final result. We propose TreeRedux, a minimal extension that adds a terminal finalize operation, executed on an executor, that maps the aggregation state U to a compact result V, so that V rather than the potentially large U is materialized on the driver. For exact quantile computation, applying TreeRedux to GK Select removes the driver's epsilon-n memory term, reducing driver memory requirements to the same asymptotic order as Spark's GK Sketch. In our experiments, the default GK Select implementation encountered a driver out-of-memory error at 2.5 billion elements. Spark's executor-side final aggregation option extended this limit to approximately 16-18 billion elements but still required the final aggregation state to be materialized on the driver. Redux Select completed through 28 billion elements without a driver out-of-memory error. TreeRedux allowed Space-Saving sketches with up to 32x the capacity of the largest configuration that materializes a full sketch on the driver.