《云环境下优化科学工作流执行性能的两阶段数据放置与任务调度策略ppt课件.ppt》由会员分享，可在线阅读，更多相关《云环境下优化科学工作流执行性能的两阶段数据放置与任务调度策略ppt课件.ppt（29页珍藏版）》请在三一办公上搜索。
1、云环境下优化科学工作流执行性能的两阶段数据放置与任务调度策略,姓名：张灿,摘要,云环境中跨数据中心科学工作流的高效执行通常面临数据交互量大的问题。本文给出基于相关度的两阶段高效数据放置策略和任务调度策略。最终通过实验表明，该策略能有效减少跨数据中心科学工作流执行时的数据传输量，从而能有效提升科学工作流的执行效率，并能减少资源的租赁费用。,主要内容,一、引言二、相关工作三、科学工作流形式化描述和问题分析 四、基于相关度的两阶段数据放置与任务调度策略五、实验分析六、结论与展望,一、引言,在众多科学研究领域中，科学计算过程往往由成千上万个步骤构成，这往往需要对TB甚至PB量级的数据进行分析和处理。在
2、过去，科学家通常使用简单的方法编排任务以及管理数据，但是这种方式不仅耗时而且容易出错。科学工作流系统开始受到关注并被用来进行自动化科学任务的编排、执行、监控以及追踪。随着问题求解规模的增大，当今大型科学工作流通常需要在复杂的分布式计算机系统上执行。构造这样的系统往往需要付出异常昂贵的代价，申请访问这些系统也需要复杂耗时的过程。云计算技术提供共享基础架构的方法，通过这种方式，云计算中心可以提供高性能的计算资源和海量的存储资源，而且成本低廉，使用简单。,科学工作流任务间存在较强的数据依赖关系，其执行往往需要频繁对跨数据中心的数据集进行传输和访问，不合理的数据放置和任务调度策略容易导致数据中心间数据
3、传输量和访问量过大：增加用户使用云资源的费用，严重影响了科学工作流的执行效率。研究基于云环境的高效数据放置策略和任务调度策略对减少跨数据中心数据传输量、提升科学工作流执行性能、减少用户费用等方面具有重要意义。,本文通过分析科学工作流数据集之间的依赖关系、数据集和数据中心之间的相关度以及任务和数据中心之间的相关度，提出了一种云平台下基于相关度的两阶段高效数据放置策略。根据数据依赖关系图在工作流建立阶段将关系紧密的数据集放置到同一个数据中心，将关系松散的数据集放置在不同数据中心。任务调度策略在运行阶段将任务调度到数据依赖最大的数据中心执行，并将新产生数据集放置到相关度最高的数据中心。实验表明：本文
4、提出的策略不但极大地减少了数据中心间的数据移动量，提高了工作流任务的并行执行效率，同时也节省了用户的云资源使用费用。,本文的贡献主要表现在以下几个方面：在科学工作流建立阶段，提出了基于数据依赖的初始化数据布局方法，充分挖掘数据相关性，使得数据布局尽可能的符合使用规则，同一个任务所需数据集最大规模地聚集在一个数据中心。在科学工作流运行阶段，提出一种相应的任务调度策略，将任务调度到所需数据集规模最大的数据中心上，减少数据中心之间的数据传输量，加快科学工作流执行速度。针对任务执行过程中产生的中间数据集，本文利用数据集之间的关系，通过量化计算将它们放置到合适的数据中心，使得后续的任务调度与执行能够快速
5、展开。,二、相关工作,Pegasus工作流数据放置策略：它首先预先分配数据到执行任务的计算单元，这样可以加快任务的执行速度，降低任务等待时间；然后动态地删除那些不会被后续任务使用的数据，以减少存储开销。这种策略只是保证了数据传输的可靠性和有效性，并没有考虑到云计算环境下因为数据交互引起的跨数据中心之间的传输开销。,副本机制它使用改进后的贪婪算法和经过优化的遗传算法计算副本的最佳放置策略，并利用基于Web服务的数据网络系统ADPPS产生工作流来进行实验验证。为了减少数据传输开销，但数据集副本机制增加了存储开销。该策略主要针对网络环境下多节点之间的数据传输而非针对云计算平台上多数据中心之间的数据传
6、输，并没有考虑到数据之间存在相关性和依赖关系。,BitDew由用户定义数据间的依赖关系，但并没有利用数据间的依赖关系减少传输开销。Sector/Sphere是由Gu等人设计和实现一种分布式文件系统该系统中数据集是规模庞大的若干未分块（non-block）的文件集合。Sphere通过设置目录和文件树将文件按照数据局部性原则聚合起来，同时使用高速传输协议UDT和文件副本减少传输延迟。实验结果表明，该系统比Hadoop处理数据要快倍，但Sphere只是根据任务来聚集数据，并没有对数据之间的关系进行仔细分析利用。Nephele项目是现有的第一个数据处理框架，注重发掘在任务的调度、执行过程中IaaS云环
7、境下资源的动态分配，有效地减少了资源使用开销，却没有减少数据传输开销。,聚类矩阵的数据放置策略：用于多数据中心之间数据集的放置。该方法的数据放置策略分为两步，在科学工作流建立阶段:构建一个相关度矩阵。通过BEA算法得到聚类矩阵。通过该矩阵将所有数据集划分为K个集合。科学工作流执行阶段，在考虑存储条件满足的情况下，新产生的数据集被放置在与它相关度最大的数据中心上。实验表明，该方法可以有效减少跨据中心之间的数据移动次数。但这种方法并未考虑移动的数据大小，如果移动次数较少，但所移动的数据太大，传输开销不一定降低，导致科学工作流的执行效率反而下降。,三、科学工作流形式化描述和问题分析,3.1相关模型和
8、符号定义定义1数据中心设为DC dcicapi ,csi,ini表示编号为i数据中心，capi表示dci的计算能力，并用执行同一任务所需的时间的倒数来量化表示，并假设该值保持不变；csi表示dci的存储空间大小；ini表示在科学工作流建立阶段，数据中心可以使用的存储空间的比例。因为科学工作流执行过程中产生的中间数据有可能规模庞大，因此在原始数据分配阶段要留有一定的空间来存储中间数据，所以0ini1。ini是一个经验值，它的大小取决于科学工作流的性质。,定义2 原始数据集设为DSinid1，d2，d3 DSini表示在科学工作流建立时所存在的数据集，即所有原始输入。 中间数据集设为DSgend1
9、，d2，d3 DSgen表示在科学工作流执行过程中所产生的数据集。 固定数据集和非固定数据集分别设为FD和NFDFD表示必须放置在固定数据中心的数据集，这是因为某些数据需要特定数据中心的特定设备才能处理，或者某些数据具有私有性和产权性NFD表示没有固定数据中心的数据集，这是相对FD而言。定义3 Tt1，t2，t3 表示在科学工作流上运行的任务集，每一个任务执行都需要若干数据集作为输入。定义4 diTi，si，dci，fixflag，deplink di表示科学工作流中编号为i的数据集。 Tit1，t2，t3表示使用di的任务集合； si表示数据集的大小； dci表示di所对应的数据中心； fi
10、xflag为true表示di是固定数据，反之则为非固定数据； deplink是一个链表。,3.2实例分析与问题说明,图（a）给出了一个科学工作流的例子，该科学工作流包含5个子任务t1，t2，t3，t4，t5，5个输入数据集d1，d2，d3，d4_f，d5和一个中间数据集d6，其中d4_f是dc2上的固定数据集，不能移动。,以图为例，科学工作流的数据放置策略需要考虑以下几点：（1）数据相关对科学工作流的影响。科学工作流运行中数据集和任务之间并不是一对多或者多对一的关系，而是多对多的关系，即一个数据集可能会被多个任务同时使用，一个任务也可能调用多个数据集。（2）数据集大小对科学工作流的影响。（3）
11、固定数据集对科学工作流的影响。固定数据集对科学工作流的影响。因为固定数据集只能放置在特定的数据中心，无法向外传输，一旦任务使用到固定数据集，该任务一定会被调度到这个数据中心上执行。（4）数据中心的计算能力、存储能力对科学工作流的影响由于各个数据中心隶属于不同的组织机构，其计算能力、存储能力可能差异较大。合理的数据放置策略也要也要将这两个因素考虑到，即在存储空间足够的前提下，向计算能力强的数据中心放置尽量多的数据集，以加快科学工作流的执行速度。由于数据移动开销对科学工作流性能影响较大，因此合理的数据放置策略应该努力减少数据移动量，本文针对这种情况提出了一种基于相关度的数据放置策略，该策略综合考虑
12、了数据相关度（即数据之间被相同任务使用的多少）、数据大小、固定数据集、数据中心的计算能力和存储能力，有效提升了科学工作流的执行效率。,四、基于相关度的两阶段数据放置与任务调度策略,4.1建立阶段数据放置策略在科学工作流建立阶段，该策略对所有的原始输入数据集在逻辑上进行预分配，这样做可以优化数据分配方案，防止前期出现不合理分配的情况。预分配主要从局部性考虑，使得子任务在调度后，所需使用的数据集都尽量在本地数据中心上存储。定义5 数据集相关度设为 count（TiTj）minsi，sj，di，djNFDdepij count（TiTj） si， diNFD， djFD count（TiTj） si
13、 ， di FD, djNFD 0， di，dj FD,depij表示数据di和数据dj的相关度大小。 count（TiTj）表示共同使用di和dj的任务数量。 depij与数据集大小有关。由定义知，数据集di有一个属性deplink，此处定义为deplink （i）=|ji，根据depij大小形成一个降序链表。定义6 预分配数据中心设为DCk，k1，2，m，假定DCk的存储空间值为相应的dck存储空间大小。在科学工作流建立阶段，需要先将原始数据集逻辑上分配到DCk，k1，2，m，然后按照DCkdck的映射原则，将逻辑上的分配方案在物理的数据中心上实现。定义7 待分配数据集集合设为DCwait
14、。在科学工作流建立阶段，该集合中存放的是与其它任何数据集相关度均为0的数据集；在科学工作流运行阶段，该集合中存放在后续过程中需要分配的数据集。,如图所示，在科学工作流建立阶段需要对所有的原始数据进行预分配，其流程大致如下:第1步（语句15）算法首先将所有的原始数据分为两类，固定数据集FD和非固定数据集NFD。第2步（语句622） 判断di的deplink中相关度最大的数据集di是固定数据集还是非固定数据集。第3步（语句2327） 对DCwait中的数据集进行预分配。,4.2运行阶段数据放置与任务调度策略在科学工作流执行阶段，基于相关度的数据放置策略将中间数据集放置到与它相关度最大的数据中心上，
15、如果该中心存储空间不足，则按照该策略中的Adjustment算法对全局数据集进行调整。定义8数据集dk和数据中心dcm的相关度dc_depmk Ti表示数据中心dcm上数据集di所需使用的任务集， N表示dcm上数据集的个数， Tk指使用数据集dk的任务集集合， sk表示数据集dk大小。,定义9调度任务tk在数据中心dcm上执行引起的传输开销设为transCostmksize(DSk) size(DSkDSm) size(DSgen-DSm) size(DS)表示集合DS中所有数据集大小之和， DSk是任务tk所需使用的数据集， DSm包含数据中心dcm上的所有数据集， DSgen表示任务tk
16、执行完毕后产生的数据集， DSm表示DSgen中应该放在dcm上的数据集。 size(DSk) size(DSkDSm) 表示tk在dcm上执行需要从其它数据中心调入的数据集大小， size(DSgen-DSm) )表示tk在dcm上执行完毕后产生的中间数据集向其它数据中心发送的数据集大小。如果transCosthk ，将tk调度到dch上执行所引起的传输开销是最低的。,科学工作流运行的时候，从任务集合中选取任务ti ，根据定义将ti调度到合适的数据中心执行，执行完毕后若产生新的任务和新的数据集，则首先更新任务集合，然后给新产生的数据集选择合适的数据中心放置。对新产生的中间数据dk，根据定义计
17、算其与所有数据中心的相关度dc_depmk，选择相关度最大的数据中心分配，如果该数据中心存储空间不足，表明科学工作流已经运行了一段时间，出现了负载不均衡，因此需要对所有数据集进行重新调整。,调整算法如图4所示，详细过程如下：第1步（语句131）对所有数据中心上的数据集进行预分配。第2步（语句3238）预分配完成以后，对所有逻辑数据中心DCi和物理数据中心dci上的每个数据集dk进行对比。,五、实验分析,5.1实验环境和设置为了验证基于相关度的数据放置策略效果，在“天河”集群上建立了一个包含80个节点的测试平台，每一个节点包含一个Intel Xeon E5540 2.53GHz的四核cpu。为了
18、模拟云计算平台，在每个节点上安装并在上面创建了虚拟集群以模拟数据中心；为每一个cpu核创建一个带有存储空间的计算实体，每个数据中心包含个计算实体，于是共有个数据中心；为了对数据进行管理，在每个数据中心上安装了Apache HDFS，并运行swinDew-C（Swinburne Decentralised Workflow for Cloud)用来解释和执行工作流。本文将采用模拟的、可定制的科学工作流来测试基于相关度的数据放置策略。通过分别改变科学工作流的数据集和任务的数量来控制科学工作流的复杂度；通过改变上界与下界来控制数据集大小的取值范围；同样，固定数据集的比例和数据中心的数量也可以进行调整
19、。实验过程中，为了保证结果的可靠性，每一个科学工作流在保持配置和云平台环境不变的情况下，运行300次后取平均值作为测试结果。,为了说明本文所提数据放置策略的效果，实验对比了种数据放置策略，分别是Random、Cluster和本文所提出的基于相关度的数据放置策略。Random策略：输入数据集在建立阶段随机的放到其中一个数据中心，如果是固定数据集则放置到指定的数据中心；运行阶段，如果空间足够，产生的中间数据集则存放在本地数据中心，否则随机放置到其中一个数据中心。在网格、集群系统中，产生的中间数据集就是存放在本地或者随机放在存储空间富余的结点上。Cluster策略：在文献11中提到的数据放置策略。在
20、建立阶段，把所有的输入数据分为犓个数据集合，把这犓个数据集合放置到合适的数据中心；在运行阶段，把新产生的数据集放置到合适的数据中心。基于相关度的数据放置策略：本文所提的数据放置策略，在文章后续部分所有图示中用Data- dependence表示该策略。,5.2测试结果及分析5.2.1数据集数量变化对结果的影响,图5显示的是当数据集数量增加时，数据移动次数和数据移动量的变化趋势。实验设定如下：科学工作流任务量犖和数据集数量犖取相同的值，数据集的变化范围设为1500MB，固定数据集比例为20，数据中心为15个。,原因分析： Cluster策略按照最大数量的原则将数据集聚集在同一个数据中心，而基于相
21、关度的数据放置策略按照最大流量的原则将数据集聚集在同一个数据中心；同时，在运行阶段Cluster策略将任务调度到包含数据个数最多的数据中心，基于相关度的数据放置策略则将任务调度到数据量最多的数据中心，所以任务执行时，基于相关度的数据放置策略引起的数据传输量就会明显减少。,5.2.2 数据集大小取值范围变化对数据移动量的影响,图6表示数据集大小幅度改变时数据移动量的变化趋势。实验设定如下：科学工作流任务量为80，数据集数量为80，固定数据集比例为20，数据中心为15个，数据集大小的平均值是250MB。,原因分析：若数据大小变化幅度很大，则Data-dependence策略在大多数情况下会选择移动
22、规模小的数据集，这样就降低了数据移动量。,5.2.3固定数据集比例的改变对数据移动量的影响,图7表出的是固定数据集比例改变时数据的移动量的变化趋势。实验设定如下：科学工作流任务量为80，数据集个数为80，数据中心为15个，数据集的变化范围是500MB。,原因分析：随着固定数据集比例的上升，因为固定数据集的因素，某些任务只能调度到特定数据中心执行，如果这些任务使用了非固定数据集，那么非固定数据集的移动次数会不断上升，导致传输的开销逐渐增大，导致种数据放置策略的数据移动量都呈上升趋势；当固定数据集达到一定比例后，非固定数据集的数量越来越少，种数据放置策略传输开销都在减少。在Data-depende
23、nce策略中，若任务中存在固定数据集，则该任务中使用的非固定数据集很有可能与固定数据集放置在同一个数据中心，相比Cluster明显减少了数据移动量。,5.2.4数据中心数量变化对数据移动量的影响,图8给出的是当数据中心数量改变时数据移动量的变化趋势。实验设定如下：科学工作流任务量为80，数据集数量为80，固定数据集比例20，数据集的变化范围是1500MB。,原因分析：随着数据中心数量的增多，平均每个数据中心分得的数据集将减少，任务执行时调用其它数据中心数据集的可能性增加，导致数据传输量上升。Data-dependence策略要优于Cluster策略，再次表明考虑数据集大小的计算调度方式可以减少数据传输流量。,六、结论与展望,本文首先对科学工作流在云平台上的执行过程做出了分析，指出了多个数据中心之间的数据传输开销是制约科学工作流执行性能的一个瓶颈，并在此基础上提出了一种基于相关度的数据放置策略，该策略综合考虑数据相关、数据集大小、固定数据集比例及数据中心计算能力。通过与其它数据放置策略进行实验对比，结果表明这种数据放置策略可以有效提升科学工作流的执行效率，减少跨数据中心之间的数据传输流量。下一步准备在本文工作的基础上进行副本机制的研究。注意到云计算平台收费的特点，在综合考虑计算代价和存储代价的基础上加入副本机制，进一步提升科学工作流的执行性能。,
