搜索
云环境下优化科学工作流执行性能的两阶段数据放置与任务调度策略科学工作流建立阶段数据放置策略摘要云环境中跨数据中心科学工作流的高效执行通常面临数据交互量大的问题。本文给出基于相关度的两阶段高效数据放置策略和任务调度策略。最终通过实验表明，该策略能有效减少跨数据中心科学工作流执行时的数据传输量，从而能有效提升科学工作流的执行效率，并能减少资源的租赁费用。主要内容•一、引言•二、相关工作•三、科学工作流形式化描述和问题分析•四、基于相关度的两阶段数据放置•五、结论与展望引言科学工作流系统通过对复杂科研流程进行分解,并对各步骤间的数据依赖关系进行分析和组合,控制各步骤在时间空间和资源等约束条件下按照科学家指定的顺序完成。科学工作流是工作流技术在科学研究方面的应用和发展,它与传统的事务工作流有着一定的相似性,但由于科学工作流面向科学实验,它是以数据为中心的。引言I.在众多科学研究领域中，科学计算过程往往由成千上万个步骤构成，这往往需要对TB甚至PB量级的数据进行分析和处理。在过去，科学家通常使用简单的方法编排任务以及管理数据，但是这种方式不仅耗时而且容易出错。II.科学工作流系统开始受到关注并被用来进行自动化科学任务的编排、执行、监控以及追踪。随着问题求解规模的增大，当今大型科学工作流通常需要在复杂的分布式计算机系统上执行。III.构造这样的系统往往需要付出异常昂贵的代价，申请访问这些系统也需要复杂耗时的过程。云计算技术提供共享基础架构的方法，通过这种方式，云计算中心可以提供高性能的计算资源和海量的存储资源，而且成本低廉，使用简单。引言★科学工作流任务间存在较强的数据依赖关系，其执行往往需要频繁对跨数据中心的数据集进行传输和访问，不合理的数据放置和任务调度策略容易导致数据中心间数据传输量和访问量过大：增加用户使用云资源的费用，严重影响了科学工作流的执行效率。★研究基于云环境的高效数据放置策略和任务调度策略对减少跨数据中心数据传输量、提升科学工作流执行性能、减少用户费用等方面具有重要意义。引言★本文通过分析科学工作流数据集之间的依赖关系、数据集和数据中心之间的相关度以及任务和数据中心之间的相关度，提出了一种云平台下基于相关度的两阶段高效数据放置策略。根据数据依赖关系图在工作流建立阶段将关系紧密的数据集放置到同一个数据中心，将关系松散的数据集放置在不同数据中心。任务调度策略在运行阶段将任务调度到数据依赖最大的数据中心执行，并将新产生数据集放置到相关度最高的数据中心。★实验表明：本文提出的策略不但极大地减少了数据中心间的数据移动量，提高了工作流任务的并行执行效率，同时也节省了用户的云资源使用费用。引言本文的贡献主要表现在以下几个方面：在科学工作流建立阶段，提出了基于数据依赖的初始化数据布局方法，充分挖掘数据相关性，使得数据布局尽可能的符合使用规则，同一个任务所需数据集最大规模地聚集在一个数据中心。在科学工作流运行阶段，提出一种相应的任务调度策略，将任务调度到所需数据集规模最大的数据中心上，减少数据中心之间的数据传输量，加快科学工作流执行速度。针对任务执行过程中产生的中间数据集，本文利用数据集之间的关系，通过量化计算将它们放置到合适的数据中心，使得后续的任务调度与执行能够快速展开。二、相关工作★PEGASUS工作流PEGASUS是由美国南加州大学网格技术中心开发出的一个开源的工作流映射引擎，它的主要功能是将复杂抽象的科学工作流映射到分布式资源上，它使用户从实际的运行环境中解放出来，而只需要考虑抽象层面上的工作流表示问题。数据放置策略：它首先预先分配数据到执行任务的计算单元，这样可以加快任务的执行速度，降低任务等待时间；然后动态地删除那些不会被后续任务使用的数据，以减少存储开销。这种策略只是保证了数据传输的可靠性和有效性，并没有考虑到云计算环境下因为数据交互引起的跨数据中心之间的传输开销。二、相关工作★聚类矩阵的数据放置策略：由澳大利亚杨耘等人提出，用于多数据中心之间数据集的放置。该方法的数据放置策略分为两步，在科学工作流建立阶段:构建一个相关度矩阵。通过BEA算法得到聚类矩阵。通过该矩阵将所有数据集划分为K个集合。（每一个集合内部的数据集都是高内聚的，集合之间的数据集则是低耦合）科学工作流执行阶段，在考虑存储条件满足的情况下，新产生的数据集被放置在与它相关度最大的数据中心上。★实验表明，该方法可以有效减少跨据中心之间的数据移动次数。但这种方法并未考虑移动的数据大小，如果移动次数较少，但所移动的数据太大，传输开销不一定降低，导致科学工作流的执行效率反而下降。三、科学工作流形式化描述和问题分析•3.1相关模型和符号定义★定义1数据中心设为表示编号为i数据中心,capi表示数据中心的计算能力，并用执行同一任务所需的时间的倒数来量化表示，并假设该值保持不变；csi表示dci的存储空间大小；λini表示在科学工作流建立阶段，数据中心可以使用的存储空间的比例。因为科学工作流执行过程中产生的中间数据有可能规模庞大，因此在原始数据分配阶段要留有一定的空间来存储中间数据，所以0＜λini＜1。λini是一个经验值，它的大小取决于科学工作流的性质。★定义2原始数据集设为DSini＝｛d1，d2，d3…｝DSini表示在科学工作流建立时所存在的数据集，即所有原始输入。中间数据集设为DSgen＝｛d1，d2，d3…｝DSgen表示在科学工作流执行过程中所产生的数据集。固定数据集和非固定数据集分别设为FD和NFD．FD表示必须放置在固定数据中心的数据集，这是因为某些数据需要特定数据中心的特定设备才能处理，或者某些数据具有私有性和产权性．NFD表示没有固定数据中心的数据集，这是相对FD而言。★定义3T＝｛t1，t2，t3…｝表示在科学工作流上运行的任务集，每一个任务执行都需要若干数据集作为输入。★定义4di＝〈Ti，si，dci，fix＿flag，deplink〉di表示科学工作流中编号为i的数据集。Ti＝｛t1，t2，t3…｝表示使用di的任务集合；si表示数据集的大小；dci表示di所对应的数据中心；fix＿flag为true表示di是固定数据，反之则为非固定数据；deplink是一个链表。（depij与数据集大小有关。由定义４知，数据集di有一个属性deplink，此处定义为deplink（i）=｛di,depij|j≠i｝，根据depij大小形成一个降序链表。）•3.2实例分析与问题说明★图１（a）给出了一个科学工作流的例子，该科学工作流包含5个子任务｛t1，t2，t3，t4，t5｝，5个输入数据集｛d1，d2，d3，d4_f，d5｝和一个中间数据集｛d6｝，其中｛d4_f｝是dc2上的固定数据集，不能移动。从图１（ａ）中可以看出，｛d1，d2｝同时被任务{t1，t2，t3｝使用，｛d3，d4_f，d6｝同时被任务｛t４｝使用，｛d５｝被任务｛t５｝使用并且任务执行完毕后会产生一个中间数据｛d６｝．由于移动数据比调度任务代价更大，即相比之下调度任务的开销几乎可以忽略，所以需要将关系紧密的数据集尽量放置到同一个数据中心．★图１（ｃ）使用的数据放置策略则将｛d６｝放在dc２上，科学工作流总的数据移动次数是５次。★图１（ｂ）是按照文献［１１］（杨耘方案）中的数据放置策略对产生的中间数据集｛d６｝进行放置．因为｛d６｝和｛d１，d２｝同时被两个任务｛t２，t３｝使用，｛d６｝和｛d３，d４＿f｝同时被任务｛t４｝使用，所以｛d６｝产生后放置在dc１上，科学工作流总的数据移动次数是2次．★但如果考虑数据大小，比如｛d１＝１ＭＢ，d２＝１ＭＢ，d６＝３０ＭＢ｝，那么图１（ｂ）中数据移动次数虽然是两次，但数据移动量是６０ＭＢ，而图１（ｃ）的数据移动次数是５次，但数据移动量是３４ＭＢ，总的数据移动量大幅减少．所以数据集大小对于科学工作流的数据放置策略和任务调度有着很大影响。★以上图为例，科学工作流的数据放置策略需要考虑以下几点：（1）数据相关对科学工作流的影响。科学工作流运行中数据集和任务之间并不是一对多或者多对一的关系，而是多对多的关系，即一个数据集可能会被多个任务同时使用，一个任务也可能调用多个数据集。（2）数据集大小对科学工作流的影响。（3）固定数据集对科学工作流的影响。固定数据集对科学工作流的影响。因为固定数据集只能放置在特定的数据中心，无法向外传输，一旦任务使用到固定数据集，该任务一定会被调度到这个数据中心上执行。（4）数据中心的计算能力、存储能力对科学工作流的影响．由于各个数据中心隶属于不同的组织机构，其计算能力、存储能力可能差异较大。合理的数据放置策略也要也要将这两个因素考虑到，即在存储空间足够的前提下，向计算能力强的数据中心放置尽量多的数据集，以加快科学工作流的执行速度。★由于数据移动开销对科学工作流性能影响较大，因此合理的数据放置策略应该努力减少数据移动量，本文针对这种情况提出了一种基于相关度的数据放置策略，该策略综合考虑了数据相关度（即数据之间被相同任务使用的多少）、数据大小、固定数据集、数据中心的计算能力和存储能力，有效提升了科学工作流的执行效率。四、基于相关度的两阶段数据放置与任务调度策略•4.1建立阶段数据放置策略•在科学工作流建立阶段，该策略对所有的原始输入数据集在逻辑上进行预分配，这样做可以优化数据分配方案，防止前期出现不合理分配的情况。预分配主要从局部性考虑，使得子任务在调度后，所需使用的数据集都尽量在本地数据中心上存储。•定义5数据集相关度设为count（Ti∩Tj）×min｛si，sj｝，di，dj∈NFD•depij＝count（Ti∩Tj）×si，di∈NFD，dj∈FDcount（Ti∩Tj）×si，di∈FD,dj∈NFD0，di，dj∈FD★depij表示数据di和数据dj的相关度大小。count（Ti∩Tj）表示共同使用di和dj的任务数量。min{si,sj}表示选择数据集较小的数据集depij与数据集大小有关。由定义４知，数据集di有一个属性deplink，此处定义为deplink（i）=｛di,depij|j≠i｝，根据depij大小形成一个降序链表。★定义6预分配数据中心设为DCk，k＝1，2，…，m，假定DCk的存储空间值为相应的dck存储空间大小。在科学工作流建立阶段，需要先将原始数据集逻辑上分配到DCk，k＝1，2，…，m，然后按照DCk→dck的映射原则，将逻辑上的分配方案在物理的数据中心上实现。★定义7待分配数据集集合设为DCwait。在科学工作流建立阶段，该集合中存放的是与其它任何数据集相关度均为0的数据集；在科学工作流运行阶段，该集合中存放在后续过程中需要分配的数据集。•如图２所示，在科学工作流建立阶段需要对所有的原始数据进行预分配，其流程大致如下:•第1步（语句1～5）算法首先将所有的原始数据分为两类，固定数据集FD和非固定数据集NFD。•第2步（语句6～22）判断di的deplink中相关度最大的数据集di是固定数据集还是非固定数据集。•第3步（语句23～27）对DCwait中的数据集进行预分配。五、结论与展望★本文首先对科学工作流在云平台上的执行过程做出了分析，指出了多个数据中心之间的数据传输开销是制约科学工作流执行性能的一个瓶颈，并在此基础上提出了一种基于相关度的数据放置策略，该策略综合考虑数据相关、数据集大小、固定数据集比例及数据中心计算能力。通过与其它数据放置策略进行实验对比，结果表明这种数据放置策略可以有效提升科学工作流的执行效率，减少跨数据中心之间的数据传输流量。★下一步准备在本文工作的基础上进行副本机制的研究。注意到云计算平台收费的特点，在综合考虑计算代价和存储代价的基础上加入副本机制，进一步提升科学工作流的执行性能。