南巴黎电信和皮埃尔大学联合博士论文玛丽·居里博士学院：巴黎计算机、电信和电子提交人索尼娅·伊肯要获得的等级南巴黎电信公司总裁云数据中心中大数据工作流的高效布局设计和存储成本节约于2017年12月14日在评审团面前进行了辩护，评审团成员包括：Hamamache Kheddouci报告员里昂第一Lynda Mokdad报告员巴黎第12皮埃尔·森斯审查员巴黎第六Véronique Vèque审查员南巴黎11Tahar Kechadi框架都柏林大学学院埃里克·雷诺论文主任巴黎南部电信NNT编号：2017TELE0020摘要云服务以即付即用的模式为用户提供高度可靠、可扩展且灵活的存储、计算和网络资源数据存储服务越来越受欢迎，许多类型的组织（如工业和科学界）都在考虑将数据移动到云数据中心云计算是加速大数据演变的一个因素，大数据也随之出现。面向云的多地理分布基础架构可实现计算和数据的搭配以及按需扩展，为支持大数据系统提供了一个有趣的选项。典型的云大数据系统是基于工作流的，包括MapReduce，它已成为开发大规模数据密集型应用程序的首选范例这些系统是与地理分布站点的研究人员合作开发的，以利用现有的云基础架构并进行大规模实验。这些实验产生的数据是巨大的、有价值的，并存储在多个地理位置以供重复使用。Indeed，工作流系统，由使用基于任务的协作模型的作业组成，引入了新的依赖性和中间数据交换需求。任务输入需要在工作流实例之间共享，这些实例需要将其部分（或全部）结果介于其他实例之间，以便用户可以使用这些结果。当选择分布式数据和存储资源以按时执行任务或作业，并以使用成本效益高的方式重新获取资源时，这就产生了新的问题。此外，任务处理的性能取决于中间数据管理的效率在本文中，我们通过考虑生成云多数据中心数据的工作流应用程序的要求，解决了云多数据中心中的中间数据管理问题。为此，我们设计并开发了用于大数据放置问题的模型和算法，同时考虑了在底层地理分布式云基础架构中运行的工作流和数据密集型应用程序的特性和要求，从而最大限度地降低了这些应用程序的数据管理成本。更具体地说，本文将中介数据放置问题作为一个一级公民来处理，通过考虑其多个方面和层次，不仅提供了一个具体的解决方案，而且提供了一个通用的和全面的方法。本 文 解 决 的 第 一 个 问 题 是 MapReduce-Hadoop 集 群 中 运 行 的 任 务 的 中 间 数 据MapReduce-Hadoop是一种执行微基准测试的方法，是大数据处理的参考系统我们的方法开发并探索了马尔可夫模型，该模型使用中间数据块的空间局部性并分析溢出文件的顺序性。我们还提出了一种预测算法。我ii.基于马尔可夫模型预测未来的中间数据请求。对整个模型和算法进行了评估，并证明了高预测准确性。本文解决的第二个问题涉及联合云存储中中间数据放置的存储通过联合机制，我们提出了一种名为ExactFed_BDWP的精确算法，以帮助多个云数据中心托管生成的中间数据依赖性。在问题的约束下，ExactFed_BDWP算法最大限度地降低了联邦管理的云数据中心的中间数据放置成本，考虑了科学用户需求、数据依赖性和数据大小。实验结果显示了所提出的云存储成本模型在中间数据依赖性放置方面的成本效益。最后，本文提出了两种算法，涉及两种变体的放置问题：可分割和不可分割的表中间数据依赖性。所提出的算法通过使用基于有向无环图的模型，不仅考虑它们在托管它们的不同数据中心内的源位置，而且考虑它们的依赖性来放置中间数据。主要目标是最大限度地降低总存储成本，包括根据需要进行转移、存储和移动的工作。为此，我们首先开发了一个名为SPL_LP的精确算法，该算法利用了工作内部依赖关系的需要，并证明了最优分数中间数据放置问题是NP难的。为了解决作业间依赖关系中的不可分割中间数据放置问题，我们提出了性能评估的结果表明，与其他策略相比，我们的中间数据放置算法在总存储成本方面具有很大的前景。此外，通过显示即使在不同 的 条 件 下 ， UNS_GREED_HEUR 算 法 的 成 本 比 也 接 近 最 优 解 ， 并 且 与 SPL_LP 和Exact_Fed_BDWP算法相比，它将收敛时间减少了几个数量级。确认;我谨向我的导师Eric Renault博士和Tahar Kechadi教授表示衷心的感谢这篇论文非常感谢埃里克博士的阅读和证明，他一定和我一样花了很多时间在这份手稿上。感谢教授。Kechadi让我发现并热爱大数据世界，没有这个发现，我的职业和个人背景会有很大的不同。非常感谢你的善良，完全可用，僵硬，和所有明智的建议，在我的博士研究年。我希望我们能继续合作。我想感谢两位论文推荐人（报告员）Lynda Mokdad教授和Hamamache Kheddouci教授，他们同意花大量时间阅读和审阅我的论文。我也要感谢教授。Véronique Vèque和教授皮埃尔·森斯接受成为我的论文考官并担任论文评审团主席。感谢所有其他人（南巴黎电信内外的同事和朋友），他们不厌其烦地阅读我的作品，帮助我改进它和/或为我的需要做出贡献，以便完成这篇论文：Amine，她的批评和合作一直是我不断丰富和反思的源泉，Djamila，她为我提供了一个完全不同但必要的编辑视角，Houria，她在实践中的技术性，以及我的办公室同事，特别是Oussama，她的评论对我非常有用。我不能忘记感谢我所有的家庭成员的支持和鼓励，特别是我亲爱的父母和丈夫。iii.内容物摘要I确认III图九列表表十三首字母缩略词xv1引言11.1引言。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...11.2研究背景。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...31.3研究问题&客观151.4研究贡献201.5论文大纲212云环境中的大数据管理方法232.1导言232.2数据密集型计算中的I/O数据放置行为2.3云中的大数据工作流管理262.4结论333MapReduce-Hadoop处理中来自协同调度任务的中间数据I/O干扰预测3.1导言35Vvi内容3.2MapReduce-Hadoop处理中中间数据的I/O行为3.3方法论383.4实验评估确认443.5结论504存储联盟意识到大数据工作流位置4.1导言534.255型系统4.3精确算法594.4绩效评估644.5结论725可扩展云大数据工作流放置算法735.1导言735.2系统型号755.3放置算法785.4绩效评估905.5结论1066一般结论和未来工作1096.1第109章第一次6.2未来研究方向111法语摘要115A.1 导言115A.2 捐款117内容七A.3 组织结构119A.4 以前的工作119A.5 贡献1：预测中间数据的I/O干扰-来自MapReduce-Hadoop121任务并发访问的区域A.6 贡献2：中间数据放置的精确算法联合云中的文件间区域123A.7 贡献3：可扩展算法125A.8 结论展望130B出版物133参考书目135图列表1.1主要云服务提供商... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...41.2数据中心增长分析[Net15]。. . . . . . . . . . . . . . . . . . . ... ... 41.3公共、私有、社区和混合云部署示例。... . . ... ...61.4供应/需求市场和拍卖机制... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...71.5存储在云数据中心的实际数据[Net15]。 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...81.6大数据量[Net15] ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 91.7联合云[DJL+13]。..............................................................................................................101.8MapReduce作业层次结构121.9Wordcount MapReduce作业的概述.............................................................................. 121.10 MapReduce作业的工作流阶段示例............................................................................... 141.11 云数据中心中的数据工作流放置问题.............................................................................161.12 作业处理阶段的工作流示例.............................................................................................183.1映射和归约函数。.............................................................................................................373.2方法概述描述在并发访问同一磁盘的映射任务上表征受干扰的未来溢出段的步骤3.3模型大小的I/O溢出大小（KB）的预测准确性结果......................................................473.4算法1的预测准确度结果...................................................................................................483.5基于I/O请求观察的数量预测算法1的准确性结果。.....................................................493.6算法1对顺序处理应用程序的准确性预测和并行。.............................................................................................................................49九我x图列表4.1联合云数据中心场景。.....................................................................................................564.2中间数据依赖关系矩阵。.................................................................................................584.3数据存储成本联合方法概述：输入/输出参数。594.4基于依赖矩阵大小变化的最优总存储成本 （副总裁）。..........................................674.5与依赖性文件对（Depi，j）数量相关的最佳总存储成本。...........................................684.66个联合数据中心的中间数据分发结果...........................................................................694.710个联合数据中心的中间数据分发结果.........................................................................704.818个联合数据中心的中间数据分发结果.........................................................................704.9使用不同编号的联合数据中心。.................................................................................................................714.10 当数据中心的数量设置为9时，ExactFed_BDWP算法的执行时间具有不同的depen-dency参数值λj................................................................................................................... 715.1系统模型。.........................................................................................................................765.2基于DAG的模型，用于从多个源数据中心生成中间数据文件（工作内部和工作之间的依赖关系）。.................................................................................................................775.3网络流图的第一部分构造Gp（对应于三个虚拟依赖的两种类型的虚拟依赖组件节点）源数据中心节点，其中四个任务在图G86中并列5.4生成的有向流图Gp=（DCp=Ap;Ep;u;c）885.5UNS_GREED_HEUR、SPL_LP、RAN算法的总存储成本DOM_HEUR和UNIFORM_HEUR通过改变中间数据大小而数据中心的数量设置为50。.........................................................................................935.6当模拟时间延长至48小时时，算法UNS_GREED_HEUR、SPL_LP、RANDOM_HEUR和UNIFORM_HEUR的总存储成本数据中心的数量设置为50。.............................................................................................94图XI列表5.7不可分割数据的每个时间槽累积的中间数据量分散式算法，数据中心编号范围从5到50。...................................................................945.8当α = 0.1且β = 18时，总存储成本的UNS_GREED_HEUR启发式与SPL_LP精确解。.................................................................................................................................... 965.9当α = 0.3且β = 14时，总存储成本的UNS_GREED_HEUR启发式与SPL_LP精确解。.................................................................................................................................... 965.10 当α = 0.5且β = 10时，总存储成本的UNS_GREED_HEUR启发式与SPL_LP精确解。.................................................................................................................................... 975.11 当α = 0.7且β = 6时，总存储成本的UNS_GREED_HEUR启发式与SPL_LP精确解。.................................................................................................................................... 975.12 当α = 0.9且β = 2时，总存储成本的UNS_GREED_HEUR启发式与SPL_LP精确解。.................................................................................................................................... 985.13 不同数据中心大小的UNS_GREED_HEUR和SPL_LP算法之间的时间执行比较数据为100GB。............................................................................................................... 1005.14 不同数据中心大小的UNS_GREED_HEUR和SPL_LP算法之间的时间执行比较数据为500GB。............................................................................................................... 1015.15 不同数据中心大小的UNS_GREED_HEUR和SPL_LP算法之间的时间执行比较数据为1000GB。............................................................................................................. 1025.16 ExactFed_BDWP算法与UNS_GREED_HEUR和SPL_LP解决方案在不同数量的数据中心上的托管的中间数据为100 GB。.......................................................................................... 1045.17 ExactFed_BDWP算法与UNS_GREED_HEUR和SPL_LP解决方案在不同数量的数据中心上的托管的中间数据为500 GB。.......................................................................................... 1045.18 ExactFed_BDWP算法与UNS_GREED_HEUR和SPL_LP解决方案在不同数量的数据中心上的时间执行比较托管的中间数据为1000 GB。........................................................................................ 105xii图列表5.19 ExactFed_BDWP算法和UNS_GREED_HEUR启发式算法的总存储成本，通过改变数据中心的数量，其中临时数据设置为1000 GB。............................................................................................ 106表列表2.1MapRe中数据放置方法相关工作的基于指令和工作流的处理系统.........................................................................................343.1算法1的输入和输出...........................................................................................................423.2配置Hadoop服务器节点以进行实验。.......................................................................... 453.3所用中间数据的特征.........................................................................................................454.1符号表.................................................................................................................................614.2三家云存储提供商的存储价格.........................................................................................655.1型号79的符号5.2UNS_GREED_HEUR启发式算法和SPL_LP算法之间的差距成本比99十三首字母缩略词物联网IDC国际数据公司 NIST国家理工学院投资回报率CRM客户关系管理IaaS基础架构即服务SaaS服务即服务平台即服务SaaS存储即服务WaaS工作流即服务DaaS数据库即服务HDFSHadoop分布式文件系统 HITS超链接诱导峰值搜索 ILP整数线性编程LP线性编程DAG有向无环图BDA大数据应用SDDF自定义数据格式逻辑块寻址MAPE平均绝对百分比误差MCMF最低成本多源多商品流十五C型HAPTER1简介总结1.1引言11.2研究背景31.2.1云计算&存储基础知识31.2.2大数据时代101.3研究问题客观151.4研究贡献201.5论文大纲............................................................................................................................. 211.1简介到目前为止，数字世界正面临着数据爆炸的后果，数据泛滥已成为一个可接受的现实。随着社交媒体、物联网（IoT）和多媒体的兴起，数据洪水（Data Deluge）--一个用来描述组织捕获的海量数据的短语--在在这种情况下，[FB13]考虑到2009年仅万维网就估计包含512EB的数据。这一数量的数据可从网络上当前可访问的超过1万亿个网页中获得。根据国际数据公司（IDC）[VON+15]的报告，一年内生成、创建和使用的所有数字数据量将从2012年的约3，000 EB增加到2020年的40，000 EB。目前，大约90%的可用数字数据是在过去2年内创建的[Gob13]。获取、存储、策展和处理这些呈指数级增长的新创建的数字数据是一个困难的挑战，通常被称为大数据。大数据描述了从上述所有类型的数据源生成和收集的异构、结构化或非结构化数据的前所未有的增长。管理具有多种数据格式的大数据是业务和管理竞争的主要基础。因此，大数据给工业组织带来了挑战，因为科学研究人员向他们提出了一系列复杂的有价值的使用、存储和分析问题。12第一章。简介要满足大数据管理的需求，就需要对数据管理系统的架构进行根本性的更改其中，高度分布式的工作流处理系统是管理大量复杂大数据的核心这些数据可以是应用程序的输入，也可以是需要存储和管理的中间输出。这种类型的一些应用包括高性能科学数据处理技术、数据密集型科学和实时流应用[WCAL14]。这些应用程序要经过一系列的计算阶段。工作流框架-集成和协调可能包含多个协作任务的多个作业[HPL 13，KJH+14，CBHTE 10]。这些任务中的一些是按顺序执行的，但其他任务可以在分布式平台上并行执行例如，像远程科学研究项目（LDU+）这样的科学组织在分布式和异构的共享资源池中执行并行的科学任务每个任务不仅生成有关显微镜和生物医学图像的数据，而且还需要其生物医学图像分析协作任务的中间输出，以进行相关性研究。另一个科学组织涉及气候公司的研究，该研究基于数据任务工作流系统。 他们采用了一个位于多个位置的组件传感器，以捕获和生成大量数据，包括高分辨率的农学、环境和天气领域1。这些工作流处理系统每天都会生成大量数据，这些数据具有极高的价值和广泛的类型。然而，处理和存储它们变得困难同样，其他应用程序使用MapReduce范式处理大规模数据任务工作流，该范式已被Google、FaceBook、Amazon和LinkedIn等主要公司采用和集成。这样的应用程序生态系统需要支持不同处理阶段的工作流任务的灵活与此同时，云服务的出现为外包组织提供了新的关键知识，即IT基础设施可以通过其灵活的定价模型[HSS+10]按需请求和返回云主要提供数据存储和处理服务，并针对高可用性和可持续性进行了优化因此，通过在分布式数据中心中采用云存储和处理模型，将协作工作流-操作性任务迁移到云可以直接执行大规模和复杂的大数据存储和处理，但以性能为代价，而这不是主要目标。尽管向云服务使用的快速过渡，但仍出现了一些关键问题，但这些问题尚未解决。对于商业和科学研究人员来说，一个具有挑战性的问题是如何以经济高效的方式运行这样的应用程序，以获得所需的性能水平进一步一些大数据工作流功能，如数据共享或中间结果重用和地理图形复制是主要选项，而许多其他功能不受支持：地理分布传输、成本优化、差异化服务质量、cus-1. http://www.concurrentinc.com/customer/the-climate-corporation/1.2. 研究背景3在成本和性能之间进行可分阶段权衡。所有这些都让人注意到，由于云数据管理的困难和效率低下，大数据工作流应用程序往往成本高昂（时间和金钱明智）或难以构建因此，提供多样化且高效的云数据管理服务是提高基于工作流的应用程序性能的关键里程因此，本文的重点是在云中管理大数据工作流，同时确保其具有成本效益的存储和处理。然而，在分布式云数据中心中采用大数据工作流功能是一个极具挑战性的问题。针对这一目标，我们提出了新的高效大数据放置策略，同时考虑了在地理分布式云基础架构中运行的工作流和数据密集型应用1.2研究背景1.2.1云计算存储基础知识各种组织和咨询公司（如Gartner2或IDC3）的IT领导者认为，在这种经济形势下，云范式是一个极具吸引力的主张，有望提供即时的ROI和长期的战略优势。考虑到云的创新潜力，本论文是在这个有前途的技术的背景下。云技术是下一代数据存储和分布式计算系统，可实现对虚拟化资源的访问，包括计算能力、存储容量和网络带宽这些资源作为满足特定服务级别协议的个性化库存按需动态提供[BYV08]。云计算解决方案用于首先访问地理数据，并允许用户专注于提取价值、租赁和扩展不同的服务和应用程序，以实现最佳的资源利用率。此外，资源可以快速地上下缩放以满足用户的随着云计算在这些年中的显著发展，许多云服务提供商都有IT运营外包服务，如图所示。1.1如Amazon Web Services、Google云平台、Microsoft Azure、Rackspace和IBM云。他们提供了许多流行的云服务和应用程序，对我们的日常生活非常有用。这些服务部署在地理位置分布在全球的多个大型资源数据中心[BYV08]。实际上，数据中心是一个集中式存储库2. http://www.gartner.com/technology/home.jsp3. https：www.idc.com/ab out/about.jsp
我的内容管理
收起
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助 
