实验结果分析三课件

1面向一种云计算平台的调度技术研究学生：李丽英指导老师：李仁发教授

唐卓讲师时间：2011年5月28日1面向一种云计算平台的调度技术研究学生：李丽英主要内容研究背景及意义目前存在的问题研究内容及成果总结及展望2主要内容研究背景及意义目前存在的问题研究内容及成果总结及展望研究背景及意义云计算是把集成化的基础设施动态的分配给内部或者外部使用，这种充分利用现有资源并对资源进行整合形成资源池后，再按需分配给用户的服务提供方式受到了商业化应用的极大推荐。1、应用背景3研究背景及意义云计算是把集成化的基础设施动态的分配给内部或者研究背景及意义编程模型服务质量数据安全实用性强资源利用率高2、云计算特点43、云计算调度技术特点与发展现状Perfect？应该具备的特征发展现状可扩展性动态性服务等级区分性云技术调度技术研究处于刚起步的阶段存在不同的云计算平台，基于具体平台的调度技术甚少研究背景及意义编程服务数据实用性强资源利2、云计算特点43、主要内容研究背景及意义Hadoop调度技术目前存在的问题研究内容及成果总结及展望5主要内容研究背景及意义Hadoop调度技术目前存在的问题研究Hadoop平台调度技术目前存在的问题存在不足1、Hadoop是典型的处理数据密集型任务的分布式云计算平台。调度算法需要考虑数据的读取问题2、Hadoop自带的任务推测执行算法会导致过多的任务备份执行2、Hadoop的数据存储方式以及任务处理模式导致数据局部性问题异常突出3、数据局部性问题会严重影响Hadoop云计算平台的性能1、Hadoop云平台同时可能处理成千上万的任务，备份任务推测执行调度算法还处于不完善的阶段3、备份任务推测执行调度算法也需要考虑数据局部性优化问题信息隐蔽技术备份任务推测执行数据局部性问题Hadoop平台调度技术目前存在的问题存在不足1、Hadoo主要内容研究背景及意义目前存在的问题研究内容及成果总结及展望7主要内容研究背景及意义目前存在的问题研究内容及成果总结及展望研究内容及成果8本文从两方面分析Hadoop云计算平台中备份任务推测执行调度性能：在考虑数据局部性优化问题的同时，利用概率论原理权衡数据局部性优化问题和因其反而影响平台调度性能的问题基于数据局部性改进LATE备份任务推测执行调度算法，分机架考虑备份任务推测执行的调度方面一方面二研究内容及成果8本文从两方面分析Hadoop云计算平台中备份基于数据局部性对LATE算法的改进策略Hadoop系统架构9基于数据局部性对LATE算法的改进策略Hadoop系统架构9Hadoop集群部署Hadoop集群按数据中心、机架、节点三层架构部署集群10Hadoop集群部署Hadoop集群按数据中心、机架、节点三学习过程之一社保基础知识改进算法的详细设计11SpeculationCap同一时刻Hadoop系统中的备份任务执行数阈值判断任务是否需要备份执行阈值SlowTaskThreshold判断节点处理任务快慢的阈值SlowNodeThreshold改进算法中三个基本参数说明t是任务已经执行了的时间ProgresScore进程分Progressrate是进程速率T是最终要得到的任务完成还需要的时间判断为慢任务的计算公式：学习过程之一社保基础知识改进算法的详细设计11Specul改进算法的详细设计如果有一个节点请求新的任务，并且整个Hadoop集群中备份任务执行数量小于SpeculationCap，则往下执行：第一步：判断节点的快慢，如果低于SlowNodeThreshold，则忽略这个请求，结束整个算法，否则继续执行。12第二步：根据请求任务节点所在的机架，对该机架上正在执行的任务，首先根据SlowTaskThreshold的值判定是否为慢任务，如果是则计算完成还需要多少时间，并放入一个队列中，对这个队列按照时间长短从低到高进行排序，同时对于还没有标记且已经开始等待推测执行的任务进行标记。如果队列不为空，则执行第三步，否则执行第四步。改进算法的详细设计如果有一个节点请求新的任务，并且整个Had改进算法的详细设计第三步：在该队列中查找是否有数据存储在请求节点的任务，如果没有则查找队列中是否有等待时间大于T1的任务，否则从该队列中选择排在首位的任务推测执行。13第四步：对其它机架上正在执行的任务判断是否为慢任务，如果是则放进另外一个队列中，计算完成任务还需要多少时间后从低到高进行排序，同时对于还没有标记且已经开始等待推测执行的任务进行标记，首先选择队列中等待时间大于T2的任务，没有则选择排在队列中最前的任务推测执行。改进算法的详细设计第三步：在该队列中查找是否有数据存储在请求改进算法的详细设计T1、T2值设定采用一个简单的数学模式来评估任务等待本地节/机架处理时给任务响应时间带来的影响，由于在大规模集群中，请求任务处理的节点刚好是任务队列中首个任务需要这个节点数据的情况，服从概率论当中的稀有事件发生概率模型，即每t秒之内有这种事件发生。因此事件的发生概率服从泊松分布:t:代表每t秒之内有这种稀有事件发生t1:代表每个任务在非节点/机架处理比在本节点/机架处理需要花的时间多t1秒t2:任务等待在本节点/机架处理的时间为t2秒T1、T2值的设定14改进算法的详细设计T1、T2值设定采用一个简单的数学模式来评改进算法在云计算仿真平台Cloudsim中的仿真实验性能分析仿真平台环境配置：CloudSim仿真工具软件包Windows操作系统或linux操作系统1.86GHz以上处理器JDK1.6以上版本Eclipse开发平台扩展工具

ant1.7.1模拟的Hadoop集群配置：机架里的主机数，虚拟机数都尽量参照了EC2部署Hadoop集群的方式机架虚拟机/主机（个）/（台）主机数（台）虚拟机数（个）机架12个/台10~10020~2003个/台20~10060~300机架22个/台10~10020~2003个/台20~10060~300机架32个/台10~10020~2003个/台20~10060~30015模拟两个实验场景：第一个实验场景：没有故障的节点，但是节点之间有性能差异第二个实验场景：设置集群中有故障节点的情况改进算法在云计算仿真平台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结论实验结果分析二：任务本地化处理率分析纵向比较，改进的实验结果分析三：系统吞吐率分析23从上图可以分析出基于数据局部性的改进算法无论在什么工作类型的情形下都能提高系统的吞吐率性能在绝大部分备份执行任务都在本节点/机架上处理时，系统吞吐率提高了近150%多个Sort工作系统吞吐率对比多个Grep工作系统吞吐率对比不同的工作类型系统吞吐率对比实验结果分析三：系统吞吐率分析23从上图可以分析出基于数据局主要内容研究背景及意义目前存在的问题研究内容及成果总结及展望24主要内容研究背景及意义目前存在的问题研究内容及成果总结及展望总结25根据Hadoop数据的存储特性，提出了基于数据局部性对LATE算法的改进策略，在Hadoop平台中分机架考虑任务推测执行的调度问题，选择备份任务推测执行时，优先选择数据存储在请求处理的节点或者机架上的任务推测执行；如果没有数据存储在本节点或者本机架的任务需要推测执行，再考虑在其它机架上查找需要推测执行的任务利用统计学概率论解决任务等待时间过长影响工作响应时间的情况。根据泊松分布，综合考虑数据局部性优化和任务等待本节点或者本机架处理时间过长反而影响任务响应时间的问题本文研究的主要贡献总结25根据Hadoop数据的存储特性，提出了基于数据局部性展望26本文还未解决的问题改进的算法选择备份任务执行时，要对整个系统进行两次排序：一次是本机架内部的任务，一次是跨机架的任务，这样会消耗一部分时间，并且有可能会因为跨机架的原因跳过最需要备份执行的任务，如果能考虑对其它机架上的任务由于跨机架读取数据的原因而设定一个权值，然后在参考该权值的基础上引入排队论的原理对整个机架上所有的任务统一进行一次加权排序，这样性能估计会有更大程度上的提高，只是这个权值比较难以取舍，需要一些理论依据，希望以后能从这方面加以改进由于实验条件的限制，只能在仿真平台中搭建模拟的环境进行仿真测试，跟实际系统上测试的性能会有所差别，所以希望能在实际的Hadoop平台中进行进一步的性能测试分析ONETWO展望26本文还未解决的问题改进的算法选择备份任务执行时，要对论文发表情况李丽英,唐卓，李仁发．基于LATE的Hadoop数据局部性改进调度算法计算机科学，已录用，预计于2011第11期发表，文章编号20101202451LiLiying,TangZhuo,LiRenfa．NewimprovementoftheHadooprelevantdatalocalityschedulingalgorithmbasedonLATE.IEEECatalogNumber:CFP1157N-;ISBN:978-1-61284-720-7.27论文发表情况27谢谢！282829面向一种云计算平台的调度技术研究学生：李丽英指导老师：李仁发教授

唐卓讲师时间：2011年5月28日1面向一种云计算平台的调度技术研究学生：李丽英主要内容研究背景及意义目前存在的问题研究内容及成果总结及展望30主要内容研究背景及意义目前存在的问题研究内容及成果总结及展望研究背景及意义云计算是把集成化的基础设施动态的分配给内部或者外部使用，这种充分利用现有资源并对资源进行整合形成资源池后，再按需分配给用户的服务提供方式受到了商业化应用的极大推荐。1、应用背景31研究背景及意义云计算是把集成化的基础设施动态的分配给内部或者研究背景及意义编程模型服务质量数据安全实用性强资源利用率高2、云计算特点323、云计算调度技术特点与发展现状Perfect？应该具备的特征发展现状可扩展性动态性服务等级区分性云技术调度技术研究处于刚起步的阶段存在不同的云计算平台，基于具体平台的调度技术甚少研究背景及意义编程服务数据实用性强资源利2、云计算特点43、主要内容研究背景及意义Hadoop调度技术目前存在的问题研究内容及成果总结及展望33主要内容研究背景及意义Hadoop调度技术目前存在的问题研究Hadoop平台调度技术目前存在的问题存在不足1、Hadoop是典型的处理数据密集型任务的分布式云计算平台。调度算法需要考虑数据的读取问题2、Hadoop自带的任务推测执行算法会导致过多的任务备份执行2、Hadoop的数据存储方式以及任务处理模式导致数据局部性问题异常突出3、数据局部性问题会严重影响Hadoop云计算平台的性能1、Hadoop云平台同时可能处理成千上万的任务，备份任务推测执行调度算法还处于不完善的阶段3、备份任务推测执行调度算法也需要考虑数据局部性优化问题信息隐蔽技术备份任务推测执行数据局部性问题Hadoop平台调度技术目前存在的问题存在不足1、Hadoo主要内容研究背景及意义目前存在的问题研究内容及成果总结及展望35主要内容研究背景及意义目前存在的问题研究内容及成果总结及展望研究内容及成果36本文从两方面分析Hadoop云计算平台中备份任务推测执行调度性能：在考虑数据局部性优化问题的同时，利用概率论原理权衡数据局部性优化问题和因其反而影响平台调度性能的问题基于数据局部性改进LATE备份任务推测执行调度算法，分机架考虑备份任务推测执行的调度方面一方面二研究内容及成果8本文从两方面分析Hadoop云计算平台中备份基于数据局部性对LATE算法的改进策略Hadoop系统架构37基于数据局部性对LATE算法的改进策略Hadoop系统架构9Hadoop集群部署Hadoop集群按数据中心、机架、节点三层架构部署集群38Hadoop集群部署Hadoop集群按数据中心、机架、节点三学习过程之一社保基础知识改进算法的详细设计39SpeculationCap同一时刻Hadoop系统中的备份任务执行数阈值判断任务是否需要备份执行阈值SlowTaskThreshold判断节点处理任务快慢的阈值SlowNodeThreshold改进算法中三个基本参数说明t是任务已经执行了的时间ProgresScore进程分Progressrate是进程速率T是最终要得到的任务完成还需要的时间判断为慢任务的计算公式：学习过程之一社保基础知识改进算法的详细设计11Specul改进算法的详细设计如果有一个节点请求新的任务，并且整个Hadoop集群中备份任务执行数量小于SpeculationCap，则往下执行：第一步：判断节点的快慢，如果低于SlowNodeThreshold，则忽略这个请求，结束整个算法，否则继续执行。40第二步：根据请求任务节点所在的机架，对该机架上正在执行的任务，首先根据SlowTaskThreshold的值判定是否为慢任务，如果是则计算完成还需要多少时间，并放入一个队列中，对这个队列按照时间长短从低到高进行排序，同时对于还没有标记且已经开始等待推测执行的任务进行标记。如果队列不为空，则执行第三步，否则执行第四步。改进算法的详细设计如果有一个节点请求新的任务，并且整个Had改进算法的详细设计第三步：在该队列中查找是否有数据存储在请求节点的任务，如果没有则查找队列中是否有等待时间大于T1的任务，否则从该队列中选择排在首位的任务推测执行。41第四步：对其它机架上正在执行的任务判断是否为慢任务，如果是则放进另外一个队列中，计算完成任务还需要多少时间后从低到高进行排序，同时对于还没有标记且已经开始等待推测执行的任务进行标记，首先选择队列中等待时间大于T2的任务，没有则选择排在队列中最前的任务推测执行。改进算法的详细设计第三步：在该队列中查找是否有数据存储在请求改进算法的详细设计T1、T2值设定采用一个简单的数学模式来评估任务等待本地节/机架处理时给任务响应时间带来的影响，由于在大规模集群中，请求任务处理的节点刚好是任务队列中首个任务需要这个节点数据的情况，服从概率论当中的稀有事件发生概率模型，即每t秒之内有这种事件发生。因此事件的发生概率服从泊松分布:t:代表每t秒之内有这种稀有事件发生t1:代表每个任务在非节点/机架处理比在本节点/机架处理需要花的时间多t1秒t2:任务等待在本节点/机架处理的时间为t2秒T1、T2值的设定42改进算法的详细设计T1、T2值设定采用一个简单的数学模式来评改进算法在云计算仿真平台Cloudsim中的仿真实验性能分析仿真平台环境配置：CloudSim仿真工具软件包Windows操作系统或linux操作系统1.86GHz以上处理器JDK1.6以上版本Eclipse开发平台扩展工具

ant1.7.1模拟的Hadoop集群配置：机架里的主机数，虚拟机数都尽量参照了EC2部署Hadoop集群的方式机架虚拟机/主机（个）/（台）主机数（台）虚拟机数（个）机架12个/台10~10020~2003个/台20~10060~300机架22个/台10~10020~2003个/台20~10060~300机架32个/台10~10020~2003个/台20~10060~30043模拟两个实验场景：第一个实验场景：没有故障的节点，但是节点之间有性能差异第二个实验场景：设置集群中有故障节点的情况改进算法在云计算仿真平台Cloudsim中的仿真实验性能分析实验结果分析一：工作响应时间根据Hadoop集群中一个数据块的大小，处理任务的时间，以及部署集群时网络资源的性能等，设置了不同的T1、T2值验证工作响应时间，从上图可以分析出当T1=15秒、T2=20秒的情况下任务的响应时间最佳。44实验结果分析一：工作响应时间根据Hadoop集群中一个数据块实验结果分析一：工作响应时间45对两个场景分别进行了模拟实验，分析证明在没有故障节点的第一个场景下，改进的算法平均工作响应时间依然略高于其它两个算法；在第二个场景中，Hadoop没有采用备份任务推测执行调度算法的工作响应时间会明显大于推测执行算法。实验结果分析一：工作响应时间17对两个场景分别进行了模拟实验实验结果分析一：工作响应时间46不同Sort工作大小在三种算法下任务响应时间对比不同Grep工作大小在三种算法下任务响应时间对比响应时间的减少率从30GB的约20%降到了90GB的15%，三个算法之间的性能差异随着工作的增大会越来越小。实验结果分析一：工作响应时间18不同Sort工作大小在三种算实验结果分析一：工作响应时间47Sort工作在三种算法下的响应时间Grep工作在三种算法下的响应时间1、最优性能：基于数据局部性改进的LATE算法高于其它两种算法2、最差性能：改进的算法跟LATE算法相差不大3、平均性能：改进的算法有着比较明显的优势4、不同的工作类型在性能表现上的差异：Sort工作使用改进后的推测执行算法在性能上会比其它两种算法会有更大程度的改善实验结果分析一：工作响应时间19Sort工作在三种算法下的响实验结果分析二：任务本地化处理率分析48为了验证基于数据局部性的改进算法对提高本地化处理任务的作用，设置了大小不同的工作，输入数据：640MB、3200MB、6400MB。即Map任务的个数分别是10、50、100，集群中机架数分别设置为4个和10个。10个Map任务时本节点/机架处理率4个机架时本节点/机架处理率10个机架时本节点/机架处理率实验结果分析二：任务本地化处理率分析20为了验证基于数据局部实验结果分析二：任务本地化处理率分析4950个Map任务时本节点/机架处理率4个机架时本节点/机架处理率10个机架时本节点/机架处理率100个Map任务时本节点/机架处理率4个机架时本节点/机架处理率10个机架时本节点/机架处理率实验结果分析二：任务本地化处理率分析2150个Map任务时本50结论实验结果分析二：任务本地化处理率分析纵向比较，改进的LATE算法相对LATE算法任务的本地节点/机架处理率提高了6%~9%，但相对Hadoop自带的算法优势并不是很明显。而对于较大的工作，数据局部性改进算法的处理优势没有小的工作增加的明显当机架数少于等于4个时，基本上数据块在不同的机架存有其副本，任务本节点/本机架处理的概率会很高，就算没有基于数据局部性的改进算法，任务推测执行本地化处理的性能也会比较理想横向比较，按照集群从小到大的顺序，LATE算法任务本节点/机架处理率依次减小从上述三组图中可以分析出以下结论：22结论实验结果分析二：任务本地化处理率分析纵向比较，改进的实验结果分析三：系统吞吐率分析51从上图可以分析出基于数据局部性的改进算法无论在什么工作类型的情形下都能提高系统的吞吐率性能在绝大部分备份执行任务都在本节点/机架上处