In a regular reduce or aggregate functions in Spark (and the original MapReduce) all partitions have to send their reduced value to the driver machine, and that machine spends linear time on the number of partitions (due to the CPU cost in merging partial results and the network bandwidth limit). It becomes a bottleneck [13] ****when there are many partitions and the data from each partition is big.
Since Spark 1.1 [20] was introduced a new aggregation communication pattern based on multi-level aggregation trees. In this setup, data are combined partially on a small set of executors before they are sent to the driver, which dramatically reduces the load the driver has to deal with. Tests showed that these functions reduce the aggregation time by an order of magnitude, especially on datasets with a large number of partitions.
So, in treeReduce and in treeAggregate, the partitions talk to each other in a logarithmic number of rounds.
In case of treeAggregate imagine the follow n-ary tree that has all the partitions at its leaves and the root will contain the final reduced value. This way there is no single bottleneck machine.
Differences between reduceByKey and treeReduce
reduceByKey is only available on key-value pair RDDs, while treeReduceis a generalization of reduce operation on any RDD. reduceByKey is used for implementing treeReduce but they are not related in any other sense. reduceByKey performs reduction for each key, resulting in an RDD; it is not an action but a transformation that returns a Shuffled RDD.
On the other hand, treeReduce perform the reduction in parallel using reduceByKey (this is done by creating a key-value pair RDD on the fly, with the keys determined by the depth of the tree).
Differences between aggregate and treeAggregate
treeAggregate [19] is ****a specialized implementation of aggregate that iteratively applies the combine function to a subset of partitions. This is done in order to prevent returning all partial results to the driver where a single pass reduce would take place as the classic aggregate does.
Why you should use TreeReduce/TreeAggregate
Many of MLib's algorithms uses treeAggregate, in the case of GaussianMixture (https://tinyurl.com/n3l68a8) the use of treeAggregate rather than aggregate have increased the performance about 20%, while Online Variational Bayes for LDA (https://tinyurl.com/kt6kty6) uses a treeAggregate instead of a reduce to aggregate the expected word-topic count matrix (potentially a very large matrix) without scalability issues. Also MLlib's implementation of Gradient Descent use treeAggregate (https://tinyurl.com/l6q5nn7).
In fact curious about this I've decided to use treeAggregate instead of a reduce to compute Gradient in my implementation of Back Propagation. In my test of dataset with 100 features and 10M instance partitioned in 96 partitions, performed on a cluster consists of 3 Worker nodes and one Application Master node (each with 16 CPUs and 52 GB memory), the neural network performed 100 epochs in only 36 minutes instead of hours.
Code examples (Scala)
The follow Scala code generates two random double RDD that contains 1 million values and calculates the Euclidean distance using map-reduce pattern, treeReduce and treeAggregate:
