TL;DR
This paper introduces MinFlow, a novel framework for optimizing data passing in serverless analytics. By intelligently constructing multi-level data passing topologies and employing an interleaved partitioning strategy for function scheduling, MinFlow significantly reduces shuffle time and storage costs, outperforming existing state-of-the-art solutions.
What Problem Does This Paper Address?
Serverless computing offers a compelling model for deploying applications, especially for I/O-intensive tasks like data analytics. However, a critical operation in these analytics jobs, known as "shuffle," presents a significant bottleneck. The shuffle operation involves passing intermediate data between stages of computation. In serverless environments, this typically means numerous PUT and GET requests to remote object storage (like AWS S3). This leads to high latency due to request rate limits, increased costs from frequent storage access, and overall performance degradation, negating some of the key benefits of serverless. Existing solutions address parts of this problem in isolation, leading to suboptimal performance and increased complexity.
Methods
MinFlow tackles the shuffle problem through a holistic, three-pronged approach:
- Topology Optimizer: Instead of relying on traditional single-level or fixed multi-level topologies, MinFlow dynamically generates a space of "progressively converging" multi-level topologies. This approach allows for more flexibility and can handle asymmetric function parallelism, unlike previous mesh-based methods. It uses a dynamic programming approach to efficiently find candidate topologies with the fewest edges.
- Function Scheduler: For each candidate topology, MinFlow employs an "interleaved partitioning strategy." This strategy divides the topology into smaller, complete bipartite graphs (CBGs). By co-locating functions within these CBGs on the same worker, data can be passed via local memory, significantly reducing the need for remote storage access. This is achieved by interleaving local memory transfers with remote storage transfers across different levels.
- Configuration Modeler: This component precisely models the performance and cost of each configuration (topology + scheduling) to pinpoint the optimal one. It uses a mathematical model that considers serverless platform characteristics and job-specific variables. To handle runtime-dependent parameters like intermediate data volume, it employs a sampling and profiling method.
Datasets
The paper evaluates MinFlow using three widely employed benchmarks:
- TeraSort: A standard benchmark for sorting large datasets.
- TPC-DS Query 16: A data-intensive SQL query involving large joins, representative of analytical workloads.
- WordCount: A common benchmark for counting word frequencies in documents.
These benchmarks were run with datasets generated by standard tools like Sort Benchmarks Generator, TPC-DS Tools, and Purdue MapReduce Benchmarks Suite. The input data sizes ranged from 50GB to 400GB, and the number of functions (parallelism) varied from 100 to 600.
Key Insights and Ideas
- Holistic Optimization is Key: The paper strongly argues that optimizing topology, function scheduling, and data transmission simultaneously is crucial for achieving significant improvements, rather than optimizing them in isolation.
- Multi-level Topologies are Powerful, but Need Careful Design: While multi-level shuffle reduces PUT/GET operations, simply projecting to a k-dimensional mesh can be inflexible and lead to other bottlenecks (like increased data volume). MinFlow's "progressively converging" approach offers a more adaptable way to generate these topologies.
- Interleaved Partitioning for Local Memory: The insight that interleaving local memory transfers with remote storage transfers across different levels can balance the benefits of local memory with the need for broader connectivity is a core contribution. This avoids straggler effects and improves overall efficiency.
- Serverless Analytics Bottlenecks Shift: The paper highlights how different serverless analytics workloads (e.g., TeraSort vs. WordCount) have different bottlenecks. TeraSort is often limited by PUT/GET operations, while WordCount can be more sensitive to function bandwidth due to reduced intermediate data. MinFlow's adaptability allows it to perform well across these variations.
Key Results
MinFlow demonstrates significant improvements over baseline (BL), FaaSFlow (FF), and Lambada (LBD):
- Shuffle Time Reduction:
- For TeraSort (600 functions, 200GB input), MinFlow achieved a 3x faster shuffle speed than Lambada and a 10.8x acceleration compared to the baseline.
- For WordCount (600 functions, 200GB input), MinFlow reduced shuffle time by up to 99.31% compared to the baseline.
- Storage Cost Savings:
- MinFlow achieved substantial cost savings, ranging from 86% to 98.84% compared to BL, FF, and LBD across different workloads.
- Overall Job Completion Time:
- MinFlow contributed significant improvements in overall job completion time, ranging from 12.26% to 77.98% across various workloads and configurations.
- Scalability: MinFlow's performance scales well with increasing parallelism, maintaining decreasing shuffle times without the degradation seen in some other approaches.
Limitations and Future Work
- Reproducibility Cost: The authors note that reproducing their results on Amazon EC2 instances can take tens of hours and thousands of dollars, highlighting the significant cloud resource requirements for such experiments.
- Prime Parallelism Handling: For cases where the function parallelism (N) is a prime number, MinFlow uses a substitution approach (N ± α) to generate suitable network levels. While effective, this is a workaround for a specific scenario.
- Future Work: The paper suggests that MinFlow's architecture can be extended to other serverless platforms and that further research can build upon its framework for optimizing serverless data analytics. The artifact provided also facilitates future research by allowing others to build upon MinFlow.
Summary updated