Scheduling shared scans of large data files

Parag Agrawal, Daniel Kifer, Christopher OlstonPVLDB 2008 · DOI · OpenReview

TL;DR

This paper tackles the challenge of efficiently scheduling jobs that scan large, shared data files in systems like Map-Reduce. They introduce novel scheduling policies that proactively consider future job arrivals to maximize data scan sharing, significantly outperforming traditional methods like Shortest Job First (SJF) in terms of perceived job wait times.

What Problem Does This Paper Address?

Modern data processing systems, particularly those employing architectures like Map-Reduce, often deal with massive datasets that are shared across numerous jobs. These jobs typically involve scanning large files, and the execution time is dominated by this I/O-intensive scan. When multiple jobs need to scan the same file, there's a significant opportunity to amortize the I/O cost by performing the scan once and feeding the data to all interested jobs simultaneously (cooperative scans). However, traditional scheduling algorithms, such as SJF, are designed for non-sharable workloads and can perform poorly in this scenario. They don't account for the potential benefits of delaying a job to allow more jobs to arrive and share its scan, nor do they effectively manage the trade-offs between minimizing average wait time and preventing excessively long waits for individual jobs. This paper aims to bridge this gap by developing scheduling policies specifically for these "sharable" workloads.

Methods

The authors propose a new family of scheduling policies derived from a formal model of job arrivals and execution. They abstract the system into job families (based on shared input files) and an executor, modeling job arrivals as Poisson processes. The core of their approach involves developing priority functions for job families.

Key methodological contributions include:

  • Relaxation-based Optimization: Since the exact scheduling problem is NP-hard, they use relaxations. Relaxation 1 assumes independent executors for each job family, optimizing for average perceived wait time (PWT). Relaxation 2 considers the serialization of batches on a single executor, leading to a more refined PWT optimization.
  • Priority-Based Scheduling: The derived invariants from the relaxations are translated into priority functions. When the executor becomes idle, the job family with the highest priority is selected for execution, and all currently enqueued jobs of that family are batched together.
  • Two Main Policies:
    • AA Policy 1 (Average Absolute PWT): Based on Relaxation 1, it prioritizes families based on a formula involving arrival rate, sharable scan time, and batch size.
  • AA Policy 2 (Average Absolute PWT): Based on Relaxation 2, it refines the priority by considering the impact of batch serialization, leading to better performance.
  • Hybrid Policy: To balance average and maximum PWT, they introduce a hybrid policy that linearly combines the objectives, allowing tuning via a parameter.
  • Practical Considerations: They address how to estimate arrival rates online and demonstrate that incorporating non-sharable execution times into priority functions is unnecessary and can be omitted for simplicity and robustness.

Datasets

The paper does not use pre-existing datasets. Instead, they introduce a simulated workload for evaluation. This workload consists of 100 job families, with arrival rates ($\lambda_i$) and sharable execution times ($t_i^s$) drawn from distributions (e.g., heavy-tailed for $t_i^s$, Pareto for initial $\lambda_i$). They also explore variations in workload characteristics like shared cost skew and bursty job arrivals.

Key Insights and Ideas

  • Traditional SJF is Suboptimal for Sharing: The paper clearly demonstrates that SJF, while good for non-sharable workloads, can lead to significant performance degradation (e.g., O(a) vs. O(a¹/²)) when jobs can share scans. This is because SJF doesn't anticipate future sharing opportunities.
  • Anticipating Future Arrivals is Crucial: The core insight is that scheduling decisions should be forward-looking. If a job can share its scan with many future jobs, it might be beneficial to delay it slightly (if it hasn't waited too long) to allow more jobs to accumulate, thereby maximizing the overall sharing benefit.
  • Sharability vs. Batch Size Trade-off: The derived policies effectively balance the desire to form large batches for maximum sharing (driven by sharability and arrival rates) against the need to avoid excessively long wait times for jobs within a batch and to prevent other jobs from starving.
  • Relaxation 2 is More Robust: The policy derived from Relaxation 2, which accounts for the serialization of batches, consistently outperforms the one from Relaxation 1, especially under certain workload conditions.
  • Ignoring Non-Sharable Costs is Viable: A key practical finding is that the priority functions work well even when the non-sharable execution time ($t_i^n$) is omitted. This simplifies implementation as $t_i^n$ is often harder to estimate accurately.
  • Hybrid Policy Offers Flexibility: The hybrid policy provides a tunable knob to balance the often competing goals of minimizing average wait time and bounding the maximum wait time, offering a practical middle ground.

Key Results

  • Significant Performance Gains: The proposed AA Policy 2 and Hybrid Policy consistently outperform baseline policies (FIFO, SJF variants) in terms of average and maximum perceived wait time (PWT) across various workload conditions, especially under higher system loads.
  • Reduced PWT: For instance, in stationary workloads, AA Policy 2 and the Hybrid Policy show substantially lower average PWT than SJF variants, particularly as load increases.
  • Robustness to Estimators: Online estimation of arrival rates ($\lambda_i$) works well and does not significantly degrade performance compared to knowing them precisely.
  • Hybrid Policy Tuning: The Hybrid Policy can achieve a good balance between average and maximum PWT, with a parameter setting of $\alpha \approx 0.99$ offering a "sweet spot" that is close to the average-optimized policy while keeping maximum PWT only slightly higher.
  • Bursty Workloads: While performance differences are less pronounced under extremely bursty workloads, the Hybrid Policy still performs comparably to SJF and avoids significantly worse outcomes.

Limitations and Future Work

  • Relative PWT: The paper notes that policies optimized for absolute PWT do not necessarily perform as well for relative PWT (stretch). Devising policies specifically for relative PWT is identified as an important area for future work.
  • Model Assumptions: The model assumes Poisson job arrivals and focuses on a single executor. While they discuss extensions, further work could explore more complex arrival patterns or multi-executor environments.
  • Workload Generation: While the simulated workload is designed to be realistic, real-world workloads can be more complex. Further validation on actual production traces would be valuable.
  • Tuning the Hybrid Policy: While a value of $\alpha \approx 0.99$ is suggested for the Hybrid Policy, finding the optimal tuning parameter in practice might require further investigation based on specific system requirements and user expectations.

Summary updated

BibTeX
@article{agrawal2008scheduling,
  author = {Parag Agrawal and Daniel Kifer and Christopher Olston},
  title = {{Scheduling shared scans of large data files}},
  journal = {Proc. VLDB Endow.},
  year = {2008},
  doi = {10.14778/1453856.1453960},
}
Figure