Near-data scheduling for data centers with multiple levels of data locality

Yekkehkhany, Ali

Permalink

https://hdl.handle.net/2142/97349 Copy

Description

Title

Near-data scheduling for data centers with multiple levels of data locality

Author(s)

Yekkehkhany, Ali

Issue Date

2017-04-19

Director of Research (if dissertation) or Advisor (if thesis)

Lu, Yi

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• Queueing theory
• Load balancing
• Scheduling
• Routing
• Near-data scheduling
• Data locality
• Data center

Abstract

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.

Graduation Semester

2017-05

Type of Resource

text

Permalink

http://hdl.handle.net/2142/97349

Copyright and License Information

Copyright 2017 Ali Yekkehkhany

Owning Collections