S3: An Efficient Shared Scan Scheduler on MapReduce Framework
Lei Shi, Xiaohui Li, Kian‐Lee Tan · 2011
Hadoop, an open-source implementation of Map-Reduce, has been widely used for data-intensive computing. In order to improve performance, multiple jobs operating on a common data file can be processed as a batch to eliminate redundant scanning. However, in practice, jobs often do not arrive at the same time, and batching them means longer waiting time for jobs that arrive earlier. In this paper, we propose S3- a novel Shared Scan Scheduler for Hadoop - which allows sharing the scan of a common file for multiple jobs that may arrive at different time. Under S3, a job is split into a sequence of (independent) sub-jobs, each operating on a different portion of the data file, moreover, multiple sub-jobs (from different jobs) that access a common portion of a data file can be processed as a batch to share the scan of the accessed data. S3operates as follows: at any time, the system may be processing a batch of sub-jobs (that access the same portion of data), at the same time, there are sub-jobs waiting in a job queue, as a new job arrives, its sub-jobs can be aligned with the waiting jobs in the queue, once the current batch of sub-jobs completes processing, the next batch of sub-jobs (which may include sub-jobs from newly arrived jobs) can be initiated for processing. In this way, an arriving job does not need to wait for a long time to be processed. We have implemented our S3approach in Hadoop, and our experimental results on a cluster of over 40 nodes show that S3outperforms the naive no-sharing scheme and the file-based shared-scan approach.