Efficiently scheduling jobs in clouds is critical for job performance, system throughput and resource utilization. The growing importance of parallel applications in clouds introduces challenges in scheduling data-parallel jobs. Production data-parallel jobs increasingly have complex dependency structure, i.e., complex task dependencies expressed as directed acyclic graphs (DAGs), and heterogeneous resource demands. NP-hard problems are introduced by relaxing either of these challenges (i.e., scheduling of homogeneous tasks with dependency constraints or independent and heterogeneous tasks) for scheduler design. It is challenging to design a scheduler for simultaneously achieving low latency and high resource utilization due to the complex dependency structure and job heterogeneity. In this paper, we propose Sailfish, a dependency-aware and resource efficient scheduling for low latency in clouds. Sailfish first uses the machine learning algorithm to classify jobs into two categories (high priority jobs and low priority jobs) based on the extracted features. Next, Sailfish splits the jobs into tasks and distributes the tasks to the master nodes based on the dependency of tasks and the load of master nodes. Then, Sailfish utilizes the dependency information of tasks to determine tasks’ priority, and packs tasks by leveraging the complementary of tasks’ requirements on different resource types and task dependency. Finally, the master nodes leverage the proposed mutual reinforcement algorithm to distribute tasks to workers in the system based on the resource demands of tasks, the available resources of workers and task dependency. Extensive experimental results based on a real cluster and experiments using real-world Amazon EC2 cloud service show that Sailfish can improve the average resource utilization (by up to 40%) and reduce the latency (the average job completion time) significantly (by up to 91%) compared to the existing schedulers.

The Earth Mover's Distance (EMD) similarity join retrieves pairs of records with EMD below a given threshold. It has a number of important applications such as near duplicate image retrieval and pattern analysis in probabilistic datasets. However, the computational cost of EMD is super cubic to the number of bins in the histograms used to represent the data objects. Consequently, the EMD similarity join operation is prohibitive for large datasets. This is the first paper that specifically addresses the EMD similarity join and we propose to use MapReduce to approach this problem. The MapReduce algorithms designed for generic metric distance similarity joins are inefficient for the EMD similarity join because they involve a large number of distance computations and have unbalanced workloads on reducers when dealing with skewed datasets. We propose a novel framework, named Melody-Join, which transforms data into the space of EMD lower bounds and performs pruning and partitioning at a low cost because computing these EMD lower bounds has a constant complexity. Furthermore, we address two key problems, the limited pruning power and the unbalanced workloads, by enhancing each phase in the Melody-Join framework. We conduct extensive experiments on real datasets. The results show that Melody-Join outperforms the state-of-the-art technique by an order of magnitude, scales up better on large datasets than the state-of-the-art technique, and scales out well on distributed machines.