fsucas.jpg

Computer Architecture and SysTems Research Lab (CASTL)

Address: 114 Milton Carothers Hall (MCH), Tallahassee, FL 32306; Contact: Dr. Weikuan Yu (yuw@cs.fsu.edu), 850-644-5442

Efficient MapReduce for Big Data Analytics

Contact: Dr. Weikuan Yu

MapReduce has become a popular programming model for large-scale data processing and analytics. Hadoop is an open-source implementation of MapReduce that has gained its popularity because of its portability, ease of use, and fault resilience. Currently, we collaborate with many leading companies, such as IBM, Mellanox, on improving the I/O and schedulers of Hadoop MapReduce. Our goal is to push forward the evolution of the MapReduce systems through introducing innovative while effective algorithms and breaking through the limitations in existing architecture.

Hadoop Acceleration Through Network Levitated Merge

Hadoop is a popular open-source implementation of the MapReduce programming model for cloud computing. However, it faces a number of issues to achieve the best performance from the underlying system. These include a serialization barrier that delays the reduce phase, repetitive merges and disk access, and lack of capability to leverage latest high speed interconnects. We designed Hadoop-A, an acceleration framework that optimizes Hadoop with plugin components implemented in C++ for fast data movement, overcoming its existing limitations. A novel network-levitated merge algorithm is introduced to merge data without repetition and disk access. In addition, a full pipeline is designed to overlap the shuffle, merge and reduce phases. Our experimental results show that Hadoop-A doubles the data processing throughput of Hadoop, and reduces CPU utilization by more than 36%.

Architecture of Hadoop Acceleration Framework

Network Levitated Merge Algorithm

With the performance of interconnects is becoming so close to memory. It is unwise to firstly pull data from remote to local disks before merging. Disk bottleneck can drastically reduces the efficiency of the entire system. In order to achieve a balanced MapReduce system, we introduce Network Levitated Merge Algorithm which effectively leverages the performance advantages provided by both memory and high-speed interconnects while eliminates the disk accesses within the ReduceTasks.

 network levitated merge

The main idea of the Network Levitated Merge is that instead of pulling the entire map output file locally before merge, our new algorithm only fetches a small portion, called header, of each data partition. With all the header from all the data partition, we can establish a minimum priority queue to conduct in-memory merging.

Major Modifications to Hadoop

  1. We identify the serialization barrier rooted in Hadoop ReduceTasks. This barrier can significantly delay the reduce phase. Hadoop Acceleration pipelines the intermediate data shuffling, merging and reducing, therefore, efficiently eliminates the serialization barrier.
  2. We identify the repetitive merge issue within the ReduceTasks. It causes extra disk I/O and leads to longer data shuffling. In addition, when there are multiple tasks running on the same node, this issue can cause severe resource contention.
  3. We design a novel Network Levitate Merge Algorithm that eliminates the drawback of external merge and efficiently uses memory to accelerate the progress of ReduceTask.
  4. Existing Hadoop MapReduce cannot take advantage of the high bandwidth, low latency provided by Remote Direct Memory Access (RDMA) capability within high-performance interconnects, such as InfiniBand and RoCE. Hadoop Acceleration solves this issue through leveraging RDMA protocol to transfer intermediate data.

Performance Improvement

Being able to leverage more nodes to process large amounts of data is an essential feature of Hadoop. Hadoop- A can deliver scalability in a similar manner. The following results show the benefit of the total execution time of TeraSort in two scaling patterns: one with fixed amount of total data (128GB) and increasing number of nodes, and the other with fixed data (4GB) per ReduceTask and increasing number of nodes. The aggregated throughput is calculated by dividing the total size with the program execution time. Hadoop-A can cut the execution time by up to 40% and 43%, compared to Hadoop on IPoIB and GigE, respectively. Conversely, this results in an throughput improvement of 66.7%, and 75.4%, respectively. These results adequately demonstrate better scalability of Hadoop- A for large-scale data processing compared to the original Hadoop.

Scalability Evaluation

People

  • FACULTY
  • STUDENTS
  1. Yandong Wang
  2. Cong Xu
  3. Xiaobing Li
  4. Yizheng Jiao
  5. Zhuo Liu
  6. Fang Zhou

Publications

  1. Yandong Wang, Robin Goldstone, Weikuan Yu, Teng Wang. Characterization and Optimization of Memory-Resident MapReduce on HPC Systems. 28th IEEE International Parallel and Distributed Processing Symposium. Tucson, AZ. May 2014.
  2. Weikuan Yu, Yandong Wang, Xinyu Que, Cong Xu. Virtual Shuffling for Efficient Data Movement in MapReduce. IEEE Transactions on Computers.
  3. Xiaobing Li, Yandong Wang, Yizheng Jiao, Cong Xu. Weikuan Yu. Cross-Task Coordination for Efficient Data Management in MapReduce Programs. Li and Wang contributed equally to the paper. International Conference for High performance Computing Networking, Storage and Analysis. Denver, CO. November 2013.
  4. Yandong Wang, Jian Tan, Weikuan Yu, Li Zhang, Xiaoqiao Meng. Preemptive ReduceTask Scheduling for Fair and Fast Job Completion. 10th International Conference on Autonomic Computing (ICAC'13). (Acceptance Rate: 22%). June 2013.
  5. Yandong Wang, Yizheng Jiao, Cong Xu, Xiaobing Li, Teng Wang, Xinyu Que, Cristi Cira, Bin Wang, Zhuo Liu, Bliss Bailey, Weikuan Yu. Assessing the Performance Impact of High-Speed Interconnects on MapReduce. Third Workshop on Big Data Benchmarking (WBDB), July, 2013 Xi'an, China
  6. Yandong Wang, Cong Xu, Xiaobing Li, Weikuan Yu. (2013). JVM-Bypass Shuffling for Hadoop Acceleration. 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS'13). (Acceptance Rate: 21%).
  7. Weikuan Yu, Yandong Wang, Xinyu Que. (2013). Design and Evaluation of Network-Levitated Merge for Hadoop Acceleration. IEEE Transactions on Parallel and Distributed Computing (TPDS). 2013.
  8. Xinyu Que, Yandong Wang, Cong Xu, and Weikuan Yu. (2012). Hierarchical Merge for Scalable MapReduce. International Workshop on Management of Big Data Systems (MBDS 2012), in conjunction with ICAC 2012. Paper
  9. Yandong Wang, Xinyu Que, Weikuan Yu, Dror Goldenberg, Dhiraj Sehgal. (2011). Hadoop Acceleration through Network Levitated Merge. International Conference for High Performance Computing, Networking, Storage and Analysis (SC'11). (Acceptance Rate: 21%). Seattle, WA. Paper

Acknowledgements

This work is funded in part by a Mellanox grant to Auburn University, by National Science Foundation awards CNS-1059376 and CNS-1320016, and by an Alabama Innovation Award.

Get Source Code

If you are interested in getting a copy of our source code, please file in a request via this from. A link to download the source code will be povided to your email account.


Personal Tools