基于Agent-aid的Map-Reduce架构负载平衡优化研究与设计

【作者】 吴磊；

【导师】 徐杨；

【作者基本信息】 电子科技大学 ， 计算机应用技术， 2012， 硕士

【摘要】 Map-Reduce架构为大数据集云计算中复杂任务的分解和子任务的管理提供了一种新颖的计算模式。然而，系统中数据集的分布状况会对云计算的效率产生极大的影响。在本文中，我们针对诸如分布式数据挖掘等数据密集型的云计算运用，提出了一个新颖的模型，用于平衡分布式系统数据集的分布，从而提高整个云计算的效率。本文在经典的Map-Reduce结构模型之上增加了一个Agent层对其进行扩展，并将数据块的负载调节请求抽象为Token表示。文中对系统的负载调节分为两个部分：负载迁移调节和数据块副本数调节。在负载迁移调节中，Agent可以根据以往收到的资源请求Token推测出系统的局部状态，从而为后续的Token制定更加合理的路由策略，使其能够快速到达目标节点，从而高效的实现系统负载的均衡。在数据块副本数调节中，Agent可以根据系统中一段时期内数据块的访问热度状态，动态的对各个数据块副本数进行调整，从而分担高热数据节点的负载，实现系统的负载均衡。本文的主要贡献在于提出了一个Agent-aid系统对经典Map-Reduce结构进行扩展，辅助其进行系统负载的调节。针对Map-Reduce结构中子任务分配的特点，本文提出了负载迁移算法，对高负载节点进行负载的调节，并提出了一种高效的启发式路由算法对Token的路由决策进行支持。另一方面，针对系统中数据的访问特点，本文提出了数据块副本数调整算法，对访问热度不同的数据块进行副本数的调整，平衡各个节点的负载。在本文的最后，我们制定了详尽的实验，从多角度对我们的算法和系统进行了验证，证明了我们的算法和系统能够很好的辅助Map-Reduce结构对系统的负载进行高效调节。更多还原

【Abstract】 The Map-Reduce framework provides a creative computation schema for complextask decomposition and sub-task management in cloud computing with large data set.However, the distribution of data set in the system has great impact on the effectivenessof clouding computing. In order to solve similar problems occur in applications dealingwith intensive data set, such as distributed data mining, we propose a novel model tobalance distributed data set in the system.We extend the classical Map-Reduce framework by adding an agent level andabstracting the load adjustment request into token. In the dissertation, load adjustmentconsists of load migration adjustment and load chunk replica adjustment. In the loadmigration adjustment, agent can estimate local state from resource request tokenpreviously received and choose better routing policy for subsequent tokens so that theycan arrive at the target nodes as far as possible. In the load chunk replica adjustment,agents could dynamically adjust the number of data replica based on access frequencyin a period so as to balance the heavy load in popular nodes.The main contribution of this dissertation is developing an agent-aid system toextend the classical Map-Reduce framework to improve balance efficiency of systemload. Based on the characteristics of sub-task allocation in Map-Reduce framework, onone hand, we propose load migration algorithm to adjust the heavy load on busy nodesand an efficient heuristic algorithm for token routing. On the other hand, according tothe feature of data access in the system, we put forward a load chunk replica adjustmentalgorithm to balance the number of load chunk replica on nodes with different accessextent. Furthermore, we test the algorithm efficiency with a set of experiment. Theexperimental results show that our algorithm and system could efficiently improve theefficiency of load balancing in Map-Reduce framework.更多还原