关键字 |
| 分布式计算;MapReduce;Hadoop;负载平衡;HaSim |
介绍 |
| Hadoop框架[3][6][7]是用来处理大规模数据在分布式计算环境中基于MapReduce计算模型[4][5]。被Hadoop声称,框架促进基于分布式计算的应用程序的发展。这些设施是基于三个重要组件之间的交互主要是叫HDFS,地图实例(映射器)和减少实例(还原剂)技术(捷运)。尽管Hadoop框架的总体结构简化了加工、组件隐藏很多复杂的低层细节包括硬件和软件方面的背景。该框架还提供一个简单的作业调度器FIFO(先进先出),在订单提交的服务工作。顺序调度程序可以在一定程度上缓解管理工作,有时它是框架处理作业队列时有效。然而,一些重要的非均匀因素尚未被作业调度器。也都知道,目前,许多集群中运行高度同质环境。例如雅虎Hadoop[1]采用同构集群有4000个处理器,2 tb的内存和1.5 pb容量。大量的基准和排序竞赛测试基于环境。 The results have been published to show the powerful of Hadoop framework. In these distributed computing tasks, people focus on the extreme performances using homogenous environment which can ideally avoid the unbalanced load issues. Therefore, behind these highlighted results, the load balancing issue is quite considerable of which has been hidden deeply by the homogeneous environments. Normally, it is extremely hard to build up a homogenous cluster with a number of nodes up to several thousands. As a result, a number of Hadoop clusters with heterogeneous nodes are quite common. The architecture of Hadoop framework has been designed quite flexible to adapt to heterogeneous resources. Thus, it can be seen clearly that the heterogeneities of the resources will affect the performance of the cluster. Devaraj Das [2], the engineering manager of Yahoo Bangalore Grid Computing Group concludes the load issue from four aspects - imbalance in input splits, imbalance in computations, imbalance in partition sizes, and imbalance in heterogeneous hardware. |
| 在本文中,我们提出一个负载平衡算法在异构MapReduce环境考虑多种因素的相互作用,包括Hadoop参数。我们设计并实现了该算法使用Hadoop模拟器HaSim。然后我们评估算法的性能和比较是由MapReduce的其他负载平衡策略。结果显示一个伟大的改善性能的模拟集群的效率。 |
二世。审查现有的工作 |
| 目前有一些研究关注研究MapReduce的负载平衡。一个研究由斯文Groot[8]指出,由于数据复制的管理费用,网络传输、本地硬盘读写,映射器可以限制工作执行时间。显示不平衡负荷的影响问题,作者使用基于谷歌大型分布式文件系统[9]。在作者的情况下他实现两个哪一个是单个算法的算法称为“字数”[3],另一个是一个复杂的一个叫“平行FP-Growth频繁项目集挖掘算法”[10]。实验结果表明,节点延迟处理导致越慢越快节点不充分的利用。根据结果,作者声称mapper和减速器Hadoop框架性能的影响。然而,首先本文只是许多实验已经没有任何解决方案在解决负载不平衡问题。其次,应考虑减速机带来的影响。理论算法实验,多个还原剂可能参与的效率。相反,对一个实际的算法,减速器通常涉及收集最终的输出应该被视为一个整体数据集没有任何分割。 Thus for the data integrity, single reducer is better than multiple reducers which needs another job to collect parts from different reducers to form a whole data set. |
| 因此认为,在数据处理,在多个映射器的负载问题更重要。一组研究人员在Hadoop实现负载平衡的重要性问题。Sadasivam等。[11]试图优化Hadoop集群的性能,提出了一个方法称为并行混合PSO-GA使用基于遗传算法的MapReduce。他们的算法使用Hadoop框架本身处理遗传算法[12]旨在解决Hadoop中的负载不平衡问题。他们的算法主要的目标是实现一个优化调度程序为多个用户根据不同的资源能力。在处理期间,他们做出了最大限度的迭代次数保证30倍效率。他们的研究结果表明,PSOGA算法优于马克斯MIPS,典型的PSO和典型的遗传算法。然而,几点可以批评他们的设计和实现。第一点是,Hadoop的开销是相当可观的。当框架涉及计算的Hadoop作业调度器Hadoop本身,虽然工作后的开销可能会减少,调度程序计算的开销肯定无法避免。 The second point in their design is they just simply consider the capacity of a resource in terms of utilization of processor. This simply idea is lack of accuracy to describe the real Hadoop system. As studied in paper [13], there are a number of factors which may impact the performances of the framework including processing features, IO features and Hadoop working mechanisms. Therefore the fitness function based on pure utilizations of processors in Parallel Hybrid PSO-GA cannot compute the scheduler accurately. The third point is they considered balancing the load among multiple users but they do not consider the load among mappers for one job. Thus the unbalanced load will make certain number of mappers unutilized, which delays one job. Moreover the total number of jobs will be affected. |
三世。HADOOP模拟器-HASIM |
| Hadoop模拟器HaSim遵循一个主从方式的设计。相关参数模拟集群包括Hadoop的数量节点,这些节点的拓扑(目前只支持简单的货架),映射器的数量和还原剂,CPU速度,内存大小,平均读写速度的硬盘和网络带宽的每个节点。HaSim支持每个节点一个处理器,每个处理器可以有一个或多个处理器核心。 |
| 一些参数的值,如CPU速度和硬盘的读写速度可以被分配根据实际测量实验。NumberOfReducers指定数量的减少实例。图1显示了HaSim的软件架构。 |
| 验证是基于公布的基准测试结果使用Grep算法[14],选择和UDF聚合。图2和图3显示模拟器可以模拟框架稳定和准确的性能。 |
四、算法设计 |
| 为了解决优化问题,遗传算法的解决方案需要表示为染色体编码为一组字符串,通常是二进制字符串。然而,二进制表示不是可行的Hadoop集群环境中的映射器的数量通常是大导致长二进制字符串。小数字符串表示的染色体数据块分配给一个映射器是表示为一个基因。在Hadoop,总时间(T)的映射器处理一个数据块包含以下四个部分:数据复制时间(. . Tc . .)在复制数据块从Hadoop分布式文件系统到本地硬盘。处理器运行时间(Tp . .)在处理一个数据块。 |
| 中间数据合并时间(.Tm。)结合映射器的输出文件到一个文件中。 |
| 缓冲区溢出时间(结核病)清空缓冲区。T = Tc +结核+ Tm +结核病.......................... |
| 让 |
| Dm . .数据块的大小。 |
| 高清…硬盘的写作速度在MB /秒。 |
| Bw。网络带宽在MB /秒。 |
| Pr.be处理器的速度运行映射过程MB /秒。 |
| 男朋友。被映射的缓冲区的大小。 |
| 类风湿性关节炎。中间数据的大小的比例大小的数据块。 |
| Nf处理中间数据的频率。 |
| Nb的次数,缓冲区被填满。 |
| Vb是由处理器处理的数据量,当缓冲区被填满。 |
| S是Hadoop的因素排序。 |
| 因此Tc =。Bw Dm /分钟(高清) |
| 在Tc . .取决于硬盘的可用资源和网络带宽。较慢的两个因素之一将在复制数据块从瓶颈Hadoop分布式文件系统的本地硬盘mapper.Tp = Dm /公关。填充缓冲区时,处理器保持写作中间数据到缓冲区,同时扩散过程保持排序的数据缓冲区写入硬盘。因此灌装的速度可以由一个缓冲区 |
| 公关x Ra高清....因此时间填满缓冲区可以被男朋友/计算。公关x Ra高清。因此,缓冲区被填满,处理器会生成中间数据量的大小....这可以用下面的方程计算: |
| Vb =公关x。Ra x Bf /。公关x Ra高清。 |
| 中间数据的总量产生的原始数据块的大小.Dm . .isDm x Ra . .因此对缓冲区的次数填满可以用方程计算:Nb = Dm x Ra / Vb。一个缓冲区溢出的时候曾经是Bf /高清。,therefore the time for a buffer to be spilled for Nb.. times is Nb x Bf / Hd. Then we have |
| 结核病= Nb x Bf /高清 |
| 处理中间数据Nf的频率。可以使用方程计算:.Nf =。(Nb / s) 1 |
| 合并发生时,整个体积的中间数据将被写入到硬盘造成的开销Dm x Ra / Hd . . |
| 因此,如果合并发生Nf时期,所消耗的时间磁盘IO操作可以由Dm x Ra Nf /高清……我们有 |
| Tm = Dm x Ra Nf /高清 |
| 的总时间.Ttotal处理数据块在Hadoop MapReduce处理波的最长时间被k参与映射器,Ttotal = max (T1、T2、T3、..... Tk)。根据可分负载理论[15],达到最低Ttotal。,it is expected that all the mappers to complete data processing at the same time: |
| T1 = T2 = T3 = .....=,Tk。让 |
| Ti .ith映射器的处理时间 |
| T¯k映射器的平均时间在数据处理中,在同一时间:T¯=ΣTi / k |
| 适应度函数可以定义使用方程: |
 |
四、仿真结果 |
| 集群的异质性是使用方程定义: |
 |
| whereP。代表整个集群的处理速度。 |
| π。代表第i个处理器的处理速度 |
| p¯。集群代表的平均处理速度。 |
| k代表处理器用于集群的数量。 |
| 表1显示了模拟环境的细节,和数字6、7和8显示仿真结果。 |
| 处理器的处理速度:根据异构性问题 |
| 异构性问题:从0到2.28 |
| 每个节点的硬盘数量:1 |
| 地图实例2 |
| 数量的减少实例1 |
| 首先10 gb的数据一直在测试模拟集群与不同程度的异质性。从图4中可以观察到当异质性的程度小于1.08,表明近均匀环境中,负载平衡方案不产生任何影响MR-LSI的性能。然而,MR-LSI的负载均衡方案减少了开销显著增加程度的异质性。 |
| 异质性保持相同的水平测试,但不同大小的数据从1 gb到10 gb。这组测试是用来评估负载平衡方案执行不同大小的数据集。图5显示了负载平衡方案可以减少MR-LSI的开销。 |
| 负载平衡方案基于遗传算法的收敛性影响MRLSI的效率。分析遗传算法的收敛,一代又一代的数量变化和MRLSI的开销在处理10 gb的数据集模拟Hadoop环境测量。图6显示MR-LSI达到性能稳定当一代又一代的遗传算法的数量达到300说明遗传算法的快速收敛。 |
六。结论 |
| 本文提出一种基于遗传算法的负载平衡算法映射降低环境支持数据密集型的分布式应用程序。仿真结果表明算法的有效性在平衡工作负载地图减少节点之间,MR-LSI算法加速计算的计算过程和保持高水平的信息检索的准确性。 |
表乍一看 |
 |
| 表1 |
|
|
数据乍一看 |
|
|
|
引用 |
- 雅虎。Hadoop在雅虎!可以在:http://developer.yahoo.com/hadoop/。(持续访问:20 - 7 - 2013)。
- Devaraj Das。如何Hadoop。可以在http://trac.nchc.org.tw/cloud/raw-attachment/Fwiki/HadoopWorkshop/h adoop-assembled。pdf(最后访问:03 - 9月- 2012年)
- Apache Hadoop !可以在http://hadoop.apache.org/(2012年11月2日通过)。
- 迪恩,J。,and Ghemawat, S. (2011). MapReduce: Simplified Data Processing on Large Clusters. In Proc. of OSDI'04: Sixth Symposium on Operating System Design and Implementation, San Francisco, CA.
- Lammel, r (2007)。谷歌的MapReduce编程模型,再现。科学。第一版。程序。卷》68。
- 文纳,j . (2011)。箴Hadoop(第1版)。纽约:施普林格。
- 白色,t (2012)。Hadoop:明确的指南(第二版)。CA: O ' reilly媒体。
- 大的,美国(2010年)。巨型:超越MapReduce工作负载平衡。VLDB 2010年第36 BasesSingapore国际会议上非常大的数据。
- Gobioff, H。,and Leung, S.T. (2003). The google file system. In SOSP '03, pp 29-43, New York, NY, USA.
- 李,H。,Wang, Y., Zhang, D., Zhang, M., and Chang, E. Y. (2008). Pfp: parallel fp-growth for query recommendation. In RecSys '08, pp 107-114, New York, NY, USA.
- Sadasivam, g S。,and Selvaraj, D. (2012). A Novel Parallel Hybrid PSO-GA using MapReduce to Schedule Jobs in Hadoop Data Grids. 2012 Four World Congress on Nature and Biologically Inspired Computing, Kitakyushu, Fukuoka, Japan.
- 戈德堡,d . e . (1989)。遗传算法在搜索、优化和机器学习。阅读质量。:addison - wesley, 1989年。
- Goda, K。,Tamura, T., Oguchi, M., and Kitsuregawa, M. (2002). Run-time load balancing system on san-connected pc cluster for dynamic injection of cpu and disk resource - a case study of data mining application.
- 保尔森E。葡萄干,。,Abadi, D. J., DeWitt, D. J., Madden, and S., Stonebraker, M. (2009). A comparison of approaches to large-scale data analysis. In: Proceedings of the 35th SIGMOD international conference on Management of data, New York, NY, USA.
- Shokripour,。,and Othman, M. (2011). Survey on Divisible Load Theory and its Applications. International Conference on Information Management and Engineering, pp 300-304.
- 李米。,Hammoud, S., Alham, N. K., and Ponraj, M. (2012). A MapReduce based distributed LSI. In: Proceedings of the 9th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD), YanTai, China. Pp 206-212
|
菜单
