The Power of Nested Parallelism in Big Data Processing - Hitting Three Flies with One Slap -

Many common data analysis tasks, such as performing hyperparameter optimization, processing a partitioned graph, and treating a matrix as a vector of vectors, offer natural opportunities for nestedparallel operations, i.e., launching parallel operations from inside other parallel operations. However, state-of-the-art dataflow engines, such as Spark and Flink, do not support nested parallelism. Users must implement workarounds, causing orders of magnitude slowdowns for their tasks, let alone the implementation effort.

We present Matryoshka, a system that enables dataflow engines to support nested parallelism, even in the presence of control flow statements at inner nesting levels. Matryoshka achieves this via a novel two-phase flattening process, which translates nested-parallel programs to flat-parallel programs that can efficiently run on existing dataflow engines. The first phase introduces novel nesting primitives into the code, which allows for dynamic optimizations based on intermediate data characteristics in the second phase at run time. We validate our system using several common data analysis tasks, such as PageRank and K-means. The results show the superiority of Matryoshka over the state-of-the-art approaches (the DIQL system as well as the outer-and inner-parallel workarounds) to support nested parallelism in dataflow engines.

The success of parallel dataflow engines, such as Spark [48,49] and Flink [1,16], is largely due to abstracting a dataset as an immutable, distributed collection. They process these datasets via a well-defined set of parallel operators that provide scalability and ease-of-use.

Yet, many modern data analysis tasks, in domains ranging from web analytics to graph analytics and machine learning, are not well supported in these systems. Many of these modern tasks require nested parallelism [8], which means launching a parallel operation from the inside of another parallel operation. For instance, the user-defined function (UDF) of a map operator can invoke further parallel operations, such as another map operator.

We now explain through examples what nested parallelism is and when it occurs. First, there can be natural nesting in the data itself. For example, a nested collection might arise when treating a matrix as a vector of vectors [13] or when processing a set of