  Data locality is a fundamental issue for data-parallel applications.
Considering MapReduce in Hadoop, the map task scheduling part requires an
efficient algorithm which takes data locality into consideration; otherwise,
the system may become unstable under loads inside the system's capacity region
and jobs may experience longer completion times which are not of interest. The
data chunk needed for any map task can be in memory, on a local disk, in a
local rack, in the same cluster or even in another data center. Hence, unless
there has been much work on improving the speed of data center networks,
different levels of service rates still exist for a task depending on where its
data chunk is saved and from which server it receives service. Most of the
theoretical work on load balancing is for systems with two levels of data
locality including the Pandas algorithm by Xie et al. and the JSQ-MW algorithm
by Wang et al., where the former is both throughput and heavy-traffic optimal,
while the latter is only throughput optimal, but heavy-traffic optimal in only
a special traffic load. We show that an extension of the JSQ-MW algorithm for a
system with thee levels of data locality is throughput optimal, but not
heavy-traffic optimal for all loads, only for a special traffic scenario.
Furthermore, we show that the Pandas algorithm is not even throughput optimal
for a system with three levels of data locality. We then propose a novel
algorithm, Balanced-Pandas, which is both throughput and heavy-traffic optimal.
To the best of our knowledge, this is the first theoretical work on load
balancing for a system with more than two levels of data locality. This is more
challenging than two levels of data locality as a dilemma between performance
and throughput emerges.
