实验结果分析三课件

1面向一种云计算平台的调度面向一种云计算平台的调度技术研究技术研究学生：学生：李丽英李丽英指导老指导老师：师：李仁发李仁发 教授教授 唐唐 卓卓 讲师讲师时间：时间：20112011年年5 5月月2828日日1面向一种云计算平台的调度技术研究学生：李丽英面向一种云计算平台的调度技术研究学生：李丽英主要内容主要内容研究背景及意义目前存在的问题研究内容及成果总结及展望2主要内容研究背景及意义目前存在的问题研究内容及成果总结及展望主要内容研究背景及意义目前存在的问题研究内容及成果总结及展望研究背景及意义研究背景及意义云计算是把集成化的基础设施动态的分配给内部或者外部使用，这种充分利用现有资源并对资源进行整合形成资源池后，再按需分配给用户的服务提供方式受到了商业化应用的极大推荐。1、应用背景3研究背景及意义云计算是把集成化的基础设施动态的分配给内部或者研究背景及意义云计算是把集成化的基础设施动态的分配给内部或者研究背景及意义研究背景及意义编程编程模型模型服务服务质量质量数据数据安全安全实用实用性强性强资源利资源利用率高用率高2、云计算特点43、云计算调度技术特点与发展现状Perfect？应该具备的特征发展现状研究背景及意义编程服务数据实用性强资源利研究背景及意义编程服务数据实用性强资源利2、云计算特点、云计算特点43、主要内容主要内容研究背景及意义Hadoop调度技术目前存在的问题研究内容及成果总结及展望5主要内容研究背景及意义主要内容研究背景及意义Hadoop调度技术目前存在的问题研究调度技术目前存在的问题研究HadoopHadoop平台调度技术目前存在的问题平台调度技术目前存在的问题存在不足1、Hadoop是典型的处理数据密集型任务的分布式云计算平台。调度算法需要考虑数据的读取问题2、Hadoop自带的任务推测执行算法会导致过多的任务备份执行2、Hadoop的数据存储方式以及任务处理模式导致数据局部性问题异常突出3、数据局部性问题会严重影响Hadoop云计算平台的性能1、Hadoop云平台同时可能处理成千上万的任务，备份任务推测执行调度算法还处于不完善的阶段3、备份任务推测执行调度算法也需要考虑数据局部性优化问题信息隐蔽技术信息隐蔽技术备份任务推测执行备份任务推测执行数据局部性问题数据局部性问题Hadoop平台调度技术目前存在的问题存在不足平台调度技术目前存在的问题存在不足1、Hadoo主要内容主要内容研究背景及意义目前存在的问题研究内容及成果总结及展望7主要内容研究背景及意义目前存在的问题研究内容及成果总结及展望主要内容研究背景及意义目前存在的问题研究内容及成果总结及展望研究内容及成果研究内容及成果8本文从两方面分析本文从两方面分析HadoopHadoop云计算平台中备份任务推测执行调度性能：云计算平台中备份任务推测执行调度性能：在考虑数据局部性在考虑数据局部性优化问题的同时，优化问题的同时，利用概率论原理权利用概率论原理权衡数据局部性优化衡数据局部性优化问题和因其反而影问题和因其反而影响平台调度性能的响平台调度性能的问题问题基于数据局部性改基于数据局部性改进进LATELATE备份任务推备份任务推测执行调度算法，测执行调度算法，分机架考虑备份任分机架考虑备份任务推测执行的调度务推测执行的调度方面一方面一方面一方面一方面二方面二方面二方面二研究内容及成果研究内容及成果8本文从两方面分析本文从两方面分析Hadoop云计算平台中备份云计算平台中备份基于数据局部性对基于数据局部性对LATELATE算法的改进算法的改进策略策略HadoopHadoop系统架构系统架构9基于数据局部性对基于数据局部性对LATE算法的改进策略算法的改进策略Hadoop系统架构系统架构9HadoopHadoop集群部署集群部署HadoopHadoop集群按数据中心、机架、节点三层架构部署集群集群按数据中心、机架、节点三层架构部署集群10Hadoop集群部署集群部署Hadoop集群按数据中心、机架、节点三集群按数据中心、机架、节点三学习过程之一社保基础知识学习过程之一社保基础知识改进算法的详细设计改进算法的详细设计11 SpeculationCap同一时刻同一时刻Hadoop系系统中的备份任务执统中的备份任务执行数阈值行数阈值判断任务是否需要判断任务是否需要备份执行阈值备份执行阈值SlowTaskThreshold判断节点处理任务判断节点处理任务快慢的阈值快慢的阈值SlowNodeThreshold改进算法中三个基本参数说明改进算法中三个基本参数说明t是任务已经执行了的时间是任务已经执行了的时间ProgresScore进程分进程分Progressrate是进程速率是进程速率T是最终要得到的任务完成是最终要得到的任务完成还需要的时间还需要的时间判断为慢任务的计算公式：判断为慢任务的计算公式：学习过程之一社保基础知识改进算法的详细设计学习过程之一社保基础知识改进算法的详细设计11 Specul改进算法的详细设计改进算法的详细设计如果有一个节点请求新的任务，并且整个Hadoop集群中备份任务执行数量小于SpeculationCap，则往下执行：第一步：第一步：判断节点的快慢，如果低于SlowNodeThreshold，则忽略这个请求，结束整个算法，否则继续执行。12第二步：第二步：根据请求任务节点所在的机架，对该机架上正在执行的任务，首先根据SlowTaskThreshold的值判定是否为慢任务，如果是则计算完成还需要多少时间，并放入一个队列中，对这个队列按照时间长短从低到高进行排序，同时对于还没有标记且已经开始等待推测执行的任务进行标记。如果队列不为空，则执行第三步，否则执行第四步。改进算法的详细设计如果有一个节点请求新的任务，并且整个改进算法的详细设计如果有一个节点请求新的任务，并且整个Had改进算法的详细设计改进算法的详细设计第三步：第三步：在该队列中查找是否有数据存储在请求节点的任务，如果没有则查找队列中是否有等待时间大于T1的任务，否则从该队列中选择排在首位的任务推测执行。13第四步：第四步：对其它机架上正在执行的任务判断是否为慢任务，如果是则放进另外一个队列中，计算完成任务还需要多少时间后从低到高进行排序，同时对于还没有标记且已经开始等待推测执行的任务进行标记，首先选择队列中等待时间大于T2的任务，没有则选择排在队列中最前的任务推测执行。改进算法的详细设计第三步：在该队列中查找是否有数据存储在请求改进算法的详细设计第三步：在该队列中查找是否有数据存储在请求改进算法的详细设计改进算法的详细设计T1T1、T2T2值设定值设定采用一个简单的数学模式来评估任务等待本地节/机架处理时给任务响应时间带来的影响，由于在大规模集群中，请求任务处理的节点刚好是任务队列中首个任务需要这个节点数据的情况，服从概率论当中的稀有事件发生概率模型，即每t秒之内有这种事件发生。因此事件的发生概率服从泊松分布:t:代表每t秒之内有这种稀有事件发生t1:代表每个任务在非节点/机架处理比在本节点/机架处理需要花的时间多t1秒t2:任务等待在本节点/机架处理的时间为t2秒T1、T2值的设定14改进算法的详细设计改进算法的详细设计T1、T2值设定采用一个简单的数学模式来评值设定采用一个简单的数学模式来评改进算法在云计算仿真平台改进算法在云计算仿真平台CloudsimCloudsim中的仿真实验性能分析中的仿真实验性能分析仿真平台环境配置：仿真平台环境配置：FCloudSim仿真工具软件包FWindows操作系统或linux操作系统F1.86GHz以上处理器FJDK1.6以上版本FEclipse开发平台F扩展工具 ant 1.7.1模拟的模拟的HadoopHadoop集群配置：机架里的主机数，集群配置：机架里的主机数，虚拟机数都尽量参照了虚拟机数都尽量参照了EC2EC2部署部署HadoopHadoop集群的集群的方式方式机架虚拟机/主机（个）/（台）主机数（台）虚拟机数（个）机架12个/台10100202003个/台2010060300机架22个/台10100202003个/台2010060300机架32个/台10100202003个/台201006030015模拟两个实验场景：模拟两个实验场景：F第一个实验场景：没有故障的节点，但是节点之间有性能差异F第二个实验场景：设置集群中有故障节点的情况改进算法在云计算仿真平台改进算法在云计算仿真平台Cloudsim中的仿真实验性能分析中的仿真实验性能分析实验结果分析一：工作响应时间实验结果分析一：工作响应时间根据Hadoop集群中一个数据块的大小，处理任务的时间，以及部署集群时网络资源的性能等，设置了不同的T1、T2值验证工作响应时间，从上图可以分析出当T1=15秒、T2=20秒的情况下任务的响应时间最佳。16实验结果分析一：工作响应时间根据实验结果分析一：工作响应时间根据Hadoop集群中一个数据块集群中一个数据块实验结果分析一：工作响应时间实验结果分析一：工作响应时间17对两个场景分别进行了模拟实验，分析证明在没有故障节点的第一个场景下，改进的算法平均工作响应时间依然略高于其它两个算法；在第二个场景中，Hadoop没有采用备份任务推测执行调度算法的工作响应时间会明显大于推测执行算法。实验结果分析一：工作响应时间实验结果分析一：工作响应时间17对两个场景分别进行了模拟实验对两个场景分别进行了模拟实验实验结果分析一：工作响应时间实验结果分析一：工作响应时间18不同Sort工作大小在三种算法下任务响应时间对比不同Grep工作大小在三种算法下任务响应时间对比响应时间的减少率从30GB的约20%降到了90GB的15%，三个算法之间的性能差异随着工作的增大会越来越小。实验结果分析一：工作响应时间实验结果分析一：工作响应时间18不同不同Sort工作大小在三种算工作大小在三种算实验结果分析一：工作响应时间实验结果分析一：工作响应时间19Sort工作在三种算法下的响应时间Grep工作在三种算法下的响应时间1、最优性能：基于数据局部性改进的LATE算法高于其它两种算法2、最差性能：改进的算法跟LATE算法相差不大3、平均性能：改进的算法有着比较明显的优势4、不同的工作类型在性能表现上的差异：Sort工作使用改进后的推测执行算法在性能上会比其它两种算法会有更大程度的改善实验结果分析一：工作响应时间实验结果分析一：工作响应时间19Sort工作在三种算法下的响工作在三种算法下的响实验结果分析二：任务本地化处理率分析实验结果分析二：任务本地化处理率分析20为了验证基于数据局部性的改进算法对提高本地化处理任务的作用，设置了大小不同的工作，输入数据：640MB、3200MB、6400MB。即Map任务的个数分别是10、50、100，集群中机架数分别设置为4个和10个。10个Map任务时本节点/机架处理率4个机架时本节点/机架处理率10个机架时本节点/机架处理率实验结果分析二：任务本地化处理率分析实验结果分析二：任务本地化处理率分析20为了验证基于数据局部为了验证基于数据局部实验结果分析二：任务本地化处理率分析实验结果分析二：任务本地化处理率分析2150个Map任务时本节点/机架处理率4个机架时本节点/机架处理率10个机架时本节点/机架处理率100个Map任务时本节点/机架处理率4个机架时本节点/机架处理率10个机架时本节点/机架处理率实验结果分析二：任务本地化处理率分析实验结果分析二：任务本地化处理率分析2150个个Map任务时本任务时本22结论实验结果分析二：任务本地化处理率分析实验结果分析二：任务本地化处理率分析纵向比较，改进的LATE算法相对LATE算法任务的本地节点/机架处理率提高了6%9%，但相对Hadoop自带的算法优势并不是很明显。而对于较大的工作，数据局部性改进算法的处理优势没有小的工作增加的明显当机架数少于等于4个时，基本上数据块在不同的机架存有其副本，任务本节点/本机架处理的概率会很高，就算没有基于数据局部性的改进算法，任务推测执行本地化处理的性能也会比较理想横向比较，按照集群从小到大的顺序，LATE算法任务本节点/机架处理率依次减小从上述三组图中可以分析出以下结论：22结论实验结果分析二：任务本地化处理率分析纵向比较，改进的结论实验结果分析二：任务本地化处理率分析纵向比较，改进的实验结果分析三：系统吞吐率分析实验结果分析三：系统吞吐率分析231.从上图可以分析出基于数据局部性的改进算法无论在什么工作类型的情形下都能提高系统的吞吐率性能2.在绝大部分备份执行任务都在本节点/机架上处理时，系统吞吐率提高了近150%多个Sort工作系统吞吐率对比多个Grep工作系统吞吐率对比不同的工作类型系统吞吐率对比实验结果分析三：系统吞吐率分析实验结果分析三：系统吞吐率分析23从上图可以分析出基于数据局从上图可以分析出基于数据局主要内容主要内容研究背景及意义目前存在的问题研究内容及成果总结及展望24主要内容研究背景及意义目前存在的问题研究内容及成果总结及展望主要内容研究背景及意义目前存在的问题研究内容及成果总结及展望总结总结25根根据据Hadoop数数据据的的存存储储特特性性，提提 出出 了了 基基 于于 数数 据据 局局 部部 性性 对对LATE算算 法法 的的 改改 进进 策策 略略，在在Hadoop平平台台中中分分机机架架考考虑虑任任务务推推测测执执行行的的调调度度问问题题，选选择择备备份份任任务务推推测测执执行行时时，优优先先选选择择数数据据存存储储在在请请求求处处理理的的节节点点或或者者机机架架上上的的任任务务推推测测执执行行；如如果果没没有有数数据据存存储储在在本本节节点点或或者者本本机机架架的的任任务务需需要要推推测测执执行行，再再考考虑虑在在其其它它机机架架上上查查找找需需要要推测执行的任务推测执行的任务利利用用统统计计学学概概率率论论解解决决任任务务等等待待时时间间过过长长影影响响工工作作响响应应时时间间的的情情况况。根根据据泊泊松松分分布布，综综合合考考虑虑数数据据局局部部性性优优化化和和任任务务等等待待本本节节点点或或者者本本机机架架处处理理时时间间过过长长反反而而影影响任务响应时间的问题响任务响应时间的问题本文研究的主要贡献本文研究的主要贡献总结总结25根据根据Hadoop数据的存储特性，提出了基于数据局部性数据的存储特性，提出了基于数据局部性展望展望26本文还未解决的问题本文还未解决的问题改进的算法选择备份任务执行时，要对整个系统进行两次排序：一次是本机架内部改进的算法选择备份任务执行时，要对整个系统进行两次排序：一次是本机架内部的任务，一次是跨机架的任务，这样会消耗一部分时间，并且有可能会因为跨机架的任务，一次是跨机架的任务，这样会消耗一部分时间，并且有可能会因为跨机架的原因跳过最需要备份执行的任务，如果能考虑对其它机架上的任务由于跨机架读的原因跳过最需要备份执行的任务，如果能考虑对其它机架上的任务由于跨机架读取数据的原因而设定一个权值，然后在参考该权值的基础上引入排队论的原理对整取数据的原因而设定一个权值，然后在参考该权值的基础上引入排队论的原理对整个机架上所有的任务统一进行一次加权排序，这样性能估计会有更大程度上的提高，个机架上所有的任务统一进行一次加权排序，这样性能估计会有更大程度上的提高，只是这个权值比较难以取舍，需要一些理论依据，希望以后能从这方面加以改进只是这个权值比较难以取舍，需要一些理论依据，希望以后能从这方面加以改进由于实验条件的限制，只能在仿真平台中搭建模拟的环境进行仿真测试，由于实验条件的限制，只能在仿真平台中搭建模拟的环境进行仿真测试，跟实际系统上测试的性能会有所差别，所以希望能在实际的跟实际系统上测试的性能会有所差别，所以希望能在实际的HadoopHadoop平台平台中进行进一步的性能测试分析中进行进一步的性能测试分析ONEONETWOTWO展望展望26本文还未解决的问题改进的算法选择备份任务执行时，要对本文还未解决的问题改进的算法选择备份任务执行时，要对论文发表情况论文发表情况李丽英,唐卓，李仁发基于LATE的Hadoop数据局部性改进调度算法计算机科学，已录用，预计于2011第11期发表，文章编号 20101202451Li Liying,Tang Zhuo,Li RenfaNew improvement of the Hadoop relevant data locality scheduling algorithm based on LATE.IEEE Catalog Number:CFP1157N-;ISBN:978-1-61284-720-7.27论文发表情况论文发表情况27谢谢！谢谢！2828