  It is cost-efficient for a tenant with a limited budget to establish a
virtual MapReduce cluster by renting multiple virtual private servers (VPSs)
from a VPS provider. To provide an appropriate scheduling scheme for this type
of computing environment, we propose in this paper a hybrid job-driven
scheduling scheme (JoSS for short) from a tenant's perspective. JoSS provides
not only job level scheduling, but also map-task level scheduling and
reduce-task level scheduling. JoSS classifies MapReduce jobs based on job scale
and job type and designs an appropriate scheduling policy to schedule each
class of jobs. The goal is to improve data locality for both map tasks and
reduce tasks, avoid job starvation, and improve job execution performance. Two
variations of JoSS are further introduced to separately achieve a better
map-data locality and a faster task assignment. We conduct extensive
experiments to evaluate and compare the two variations with current scheduling
algorithms supported by Hadoop. The results show that the two variations
outperform the other tested algorithms in terms of map-data locality,
reduce-data locality, and network overhead without incurring significant
overhead. In addition, the two variations are separately suitable for different
MapReduce-workload scenarios and provide the best job performance among all
tested algorithms.
