2云环境下优化科学工作流执行性能的两阶段数据放置与任务调度策略

云环境下优化科学工作流执行性能的两阶段数据放置与任务调度策略姓名：张灿摘要云环境中跨数据中心科学工作流的高效执行通常面临数据交互量大的问题。本文给出基于相关度的两阶段高效数据放置策略和任务调度策略。最终通过实验表明，该策略能有效减少跨数据中心科学工作流执行时的数据传输量，从而能有效提升科学工作流的执行效率，并能减少资源的租赁费用。主要内容一、引言二、相关工作三、科学工作流形式化描述和问题分析四、基于相关度的两阶段数据放置与任务调度策略五、实验分析六、结论与展望一、引言在众多科学研究领域中，科学计算过程往往由成千上万个步骤构成，这往往需要对TB甚至PB量级的数据进行分析和处理。在过去，科学家通常使用简单的方法编排任务以及管理数据，但是这种方式不仅耗时而且容易出错。科学工作流系统开始受到关注并被用来进行自动化科学任务的编排、执行、监控以及追踪。随着问题求解规模的增大，当今大型科学工作流通常需要在复杂的分布式计算机系统上执行。构造这样的系统往往需要付出异常昂贵的代价，申请访问这些系统也需要复杂耗时的过程。云计算技术提供共享基础架构的方法，通过这种方式，云计算中心可以提供高性能的计算资源和海量的存储资源，而且成本低廉，使用简单。科学工作流任务间存在较强的数据依赖关系，其执行往往需要频繁对跨数据中心的数据集进行传输和访问，不合理的数据放置和任务调度策略容易导致数据中心间数据传输量和访问量过大：增加用户使用云资源的费用，严重影响了科学工作流的执行效率。研究基于云环境的高效数据放置策略和任务调度策略对减少跨数据中心数据传输量、提升科学工作流执行性能、减少用户费用等方面具有重要意义。本文通过分析科学工作流数据集之间的依赖关系、数据集和数据中心之间的相关度以及任务和数据中心之间的相关度，提出了一种云平台下基于相关度的两阶段高效数据放置策略。根据数据依赖关系图在工作流建立阶段将关系紧密的数据集放置到同一个数据中心，将关系松散的数据集放置在不同数据中心。任务调度策略在运行阶段将任务调度到数据依赖最大的数据中心执行，并将新产生数据集放置到相关度最高的数据中心。实验表明：本文提出的策略不但极大地减少了数据中心间的数据移动量，提高了工作流任务的并行执行效率，同时也节省了用户的云资源使用费用。本文的贡献主要表现在以下几个方面：在科学工作流建立阶段，提出了基于数据依赖的初始化数据布局方法，充分挖掘数据相关性，使得数据布局尽可能的符合使用规则，同一个任务所需数据集最大规模地聚集在一个数据中心。在科学工作流运行阶段，提出一种相应的任务调度策略，将任务调度到所需数据集规模最大的数据中心上，减少数据中心之间的数据传输量，加快科学工作流执行速度。针对任务执行过程中产生的中间数据集，本文利用数据集之间的关系，通过量化计算将它们放置到合适的数据中心，使得后续的任务调度与执行能够快速展开。二、相关工作Pegasus工作流数据放置策略：它首先预先分配数据到执行任务的计算单元，这样可以加快任务的执行速度，降低任务等待时间；然后动态地删除那些不会被后续任务使用的数据，以减少存储开销。这种策略只是保证了数据传输的可靠性和有效性，并没有考虑到云计算环境下因为数据交互引起的跨数据中心之间的传输开销。副本机制它使用改进后的贪婪算法和经过优化的遗传算法计算副本的最佳放置策略，并利用基于Web服务的数据网络系统ADPPS产生工作流来进行实验验证。为了减少数据传输开销，但数据集副本机制增加了存储开销。该策略主要针对网络环境下多节点之间的数据传输而非针对云计算平台上多数据中心之间的数据传输，并没有考虑到数据之间存在相关性和依赖关系。BitDew由用户定义数据间的依赖关系，但并没有利用数据间的依赖关系减少传输开销。Sector/Sphere是由Gu等人设计和实现一种分布式文件系统该系统中数据集是规模庞大的若干未分块（non-block）的文件集合。Sphere通过设置目录和文件树将文件按照数据局部性原则聚合起来，同时使用高速传输协议UDT和文件副本减少传输延迟。实验结果表明，该系统比Hadoop处理数据要快２～４倍，但Sphere只是根据任务来聚集数据，并没有对数据之间的关系进行仔细分析利用。Nephele项目是现有的第一个数据处理框架，注重发掘在任务的调度、执行过程中IaaS云环境下资源的动态分配，有效地减少了资源使用开销，却没有减少数据传输开销。聚类矩阵的数据放置策略：用于多数据中心之间数据集的放置。该方法的数据放置策略分为两步，在科学工作流建立阶段:①构建一个相关度矩阵。②通过BEA算法得到聚类矩阵。③通过该矩阵将所有数据集划分为K个集合。科学工作流执行阶段，在考虑存储条件满足的情况下，新产生的数据集被放置在与它相关度最大的数据中心上。实验表明，该方法可以有效减少跨据中心之间的数据移动次数。但这种方法并未考虑移动的数据大小，如果移动次数较少，但所移动的数据太大，传输开销不一定降低，导致科学工作流的执行效率反而下降。三、科学工作流形式化描述和问题分析3.1相关模型和符号定义定义1数据中心设为DC＝dci＝〈capi,csi,λini〉表示编号为i数据中心，capi表示dci的计算能力，并用执行同一任务所需的时间的倒数来量化表示，并假设该值保持不变；csi表示dci的存储空间大小；λini表示在科学工作流建立阶段，数据中心可以使用的存储空间的比例。因为科学工作流执行过程中产生的中间数据有可能规模庞大，因此在原始数据分配阶段要留有一定的空间来存储中间数据，所以0＜λini＜1。λini是一个经验值，它的大小取决于科学工作流的性质。1,2,...}{iidc定义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是一个链表。3.2实例分析与问题说明图１（a）给出了一个科学工作流的例子，该科学工作流包含5个子任务｛t1，t2，t3，t4，t5｝，5个输入数据集｛d1，d2，d3，d4_f，d5｝和一个中间数据集｛d6｝，其中｛d4_f｝是dc2上的固定数据集，不能移动。以图１为例，科学工作流的数据放置策略需要考虑以下几点：（1）数据相关对科学工作流的影响。科学工作流运行中数据集和任务之间并不是一对多或者多对一的关系，而是多对多的关系，即一个数据集可能会被多个任务同时使用，一个任务也可能调用多个数据集。（2）数据集大小对科学工作流的影响。（3）固定数据集对科学工作流的影响。固定数据集对科学工作流的影响。因为固定数据集只能放置在特定的数据中心，无法向外传输，一旦任务使用到固定数据集，该任务一定会被调度到这个数据中心上执行。（4）数据中心的计算能力、存储能力对科学工作流的影响．由于各个数据中心隶属于不同的组织机构，其计算能力、存储能力可能差异较大。合理的数据放置策略也要也要将这两个因素考虑到，即在存储空间足够的前提下，向计算能力强的数据中心放置尽量多的数据集，以加快科学工作流的执行速度。由于数据移动开销对科学工作流性能影响较大，因此合理的数据放置策略应该努力减少数据移动量，本文针对这种情况提出了一种基于相关度的数据放置策略，该策略综合考虑了数据相关度（即数据之间被相同任务使用的多少）、数据大小、固定数据集、数据中心的计算能力和存储能力，有效提升了科学工作流的执行效率。四、基于相关度的两阶段数据放置与任务调度策略4.1建立阶段数据放置策略在科学工作流建立阶段，该策略对所有的原始输入数据集在逻辑上进行预分配，这样做可以优化数据分配方案，防止前期出现不合理分配的情况。预分配主要从局部性考虑，使得子任务在调度后，所需使用的数据集都尽量在本地数据中心上存储。定义5数据集相关度设为count（Ti∩Tj）×min｛si，sj｝，di，dj∈NFDdepij＝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的任务数量。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中的数据集进行预分配。4.2运行阶段数据放置与任务调度策略在科学工作流执行阶段，基于相关度的数据放置策略将中间数据集放置到与它相关度最大的数据中心上，如果该中心存储空间不足，则按照该策略中的Adjustment算法对全局数据集进行调整。定义8数据集dk和数据中心dcm的相关度dc_depmk＝Ti表示数据中心dcm上数据集di所需使用的任务集，N表示dcm上数据集的个数，Tk指使用数据集dk的任务集集合，sk表示数据集dk大小。1()NikkicountsTT定义9调度任务tk在数据中心dcm上执行引起的传输开销设为transCostmk＝［size(DSk)－size(DSk∩DSm)＋size(DS’gen-DS’m)］size(DS)表示集合DS中所有数据集大小之和，DSk是任务tk所需使用的数据集，DSm包含数据中心dcm上的所有数据集，DS’gen表示任务tk执行完毕后产生的数据集，DS’m表示DS’gen中应该放在dcm上的数据集。［size(DSk)－size(DSk∩DSm)］表示tk在dcm上执行需要从其它数据中心调入的数据集大小，size(DS’gen-DS’m))表示tk在dcm上执行完毕后产生的中间数据集向其它数据中心发送的数据集大小。如果transCosthk＝，将tk调度到dch上执行所引起的传输开销是最低的。1minkmkitransCost科学工作流运行的时候，从任务集合中选取任务ti，根据定义９将ti调度到合适的数据中心执行，执行完毕后若产生新的任务和新的数据集，则首先更新任务集合，然后给新产生的数据集选择合适的数据中心放置。对新产生的中间数据dk，根据定义８计算其与所有数据中心的相关度dc_depmk，选择相关度最大的数据中心分配，如果该数据中心存储空间不足，