Research On Optimal Reduce Placement Algorithm Based On Data Skew

With the rapid development of network technology,Internet has become increasingly popular,businesses are affected by it and the number of Internet users continues to rise,which also makes the data be generated by the Internet toward huge quantity and miscellaneous direction.This has become a new direction of the Internet industry about the processing,search and mining of this type data.At the same time,these bring a great opportunity for the development of distributed computing and cloud computing.MapReduce is proposed for processing large amounts of data distri-buted parallel computing programming models by Google.Based on the framework applications can be easily writed.which can run on large clusters composed of thousands of machines.It has advantages of automatic parallel processing operation,high reliability,fault tolerance,easy to program and TB levels of massive data sets processed in parallel,etc.For frequent disk I/O and big data transmission among different racks and physical nodes,the intermediate data communication has become the biggest perform-ance bottle-neck in most running Hadoop systems.This paper proposes a reduce placement algorithm called CORP to schedule related map and reduce tasks on the near nodes or clusters or racks for the data locality.Since the number of keys cannot be counted until the input data are processed by map tasks,this paper firstly provides a sampling algorithm based on reservoir sampling to achieve the distribution of keys in intermediate data.With the random replacement policy in the randomly selected sample zone,the estimated results can be much better approximation to the real distribution.Based on the distribution matrix of intermediate results in each partition,through calculating the distance and cost matrices among the cross node communica-tion,the related map and reduce tasks can be scheduled to relatively near physical nodes for data locality.CORP is applicable to a wide range of applications and is transparent to the users.We implement CORP in Hadoop 2.4.0 and evaluate its performance using three widely used benchmarks:sort,grep,and join.Experimental results show that CORP can not only improve the balance of reduce tasks effectively,but also decrease the job execution time for the lower inner data communication.Comparing to some other reduce scheduling algorithms,the average data transmission of whole system on core switch have been decreased substantially.Not only do We finish this job in the cluster environment of Hadoop based on the data skewing to achieve the placement of tasks,but use the virtual machine to implement the place-ment of tasks as for the study of the cloud.The more closed to starting a task VM?the more localized data will be available.Based on existing models and work,we proposed the HM(Heuristic Migration)policy that can get more optimization of time.The experiment shows that we will get less executing time and the greater degree of localized data if there is a little the cross-rack traffic.