Abstract
In the era of Big Data, huge amounts of structured and unstructured data are being produced daily by a myriad of ubiquitous sources. Big Data is difficult to work with and requires massively parallel software running on a large number of computers. MapReduce is a recent programming model that simplifies writing distributed applications that handle Big Data. MapReduce does this by dividing its workload amongst computers in a network and then processing the work in parallel. Often intertwined with the concept of MapReduce is Cloud Computing. Cloud Computing is a method of computing that shares computing resources over the Internet. Cloud Computing is a perfect match for handling Big Data and the MapReduce model by providing a hardware platform and framework that is flexible and elastic. Cloud Computing provides the resources needed for the data intensive computation required by MapReduce and its data. This dissertation looks at resource utilization within a cluster or data center and focuses on load balancing and data placement in MapReduce. Load balancing is a method to distribute workload across multiple computers or a computer cluster and involves central processing units, disk drives, and other resources. The purpose of load balancing is to achieve optimal resource utilization, maximize throughput, minimize response time, and avoid overload. Data placement is closely related to load balancing and refers to where data is in the network during the lifetime of a job. In this dissertation, we investigate load balancing and data placement for MapReduce and how it applies in different situations. We then propose several algorithms that can improve load balancing for MapReduce. Firstly we introduce an improved sampling method for total order partitioning. Secondly we present a multiway join algorithm that uses dynamic data redistribution and finally we show how data can be more intelligently distributed within a heterogeneous cloud environment. In our first topic, we propose an improved sampling and partitioning method for strings. In this topic, we present the XTrie, ETrie and ATrie algorithms. The XTrie algorithm uses a fixed memory footprint, which is unlike the traditional total order partitioning method that stores all elements in a sample set in memory. Furthermore, we show XTrie has better performance, and is able to execute 7 times faster on 200,000 samples. Both ETrie and ATrie algorithms further improve the memory requirements used by XTrie. ETrie was able to reduce memory consumption to 1/16 of that used by XTrie. Finally, ATrie was able to reduce memory consumption by 1/16384 of that used by XTrie, by using an adaptive method on birthdate data and a 2-level trie. In our second topic, we propose a network aware multiway join for MapReduce (SmartJoin) that improves performance and considers network traffic when redistributing workload amongst reducers. We show this can reduce the time required to join multiple datasets. In our evaluation, we show that SmartJoin has up to 39% improvement compared to the non-redistribution method, a 26.8% improvement over random redistribution and 27.6% improvement over WorstJoin redistribution. Finally, in our third topic we propose a dynamic data partitioner and virtual machine mapper for MapReduce when deployed on a heterogeneous cloud environment. Simulation and experimental results show an improvement in MapReduce performance, improving data locality by 33% and optimizing total completion time by 41%. Furthermore, by using the Load Aware Virtual Machine Mapper obtained an additional 13% improvement in reduce phase completion time.