1研究背景和意义

云计算技术发展到今天已经日趋成熟，例如AmazonEC2、Google Cloud和Microsoft Azure等大型公有云平台拥有庞大的集群资源，能够同时满足不同租户各种各样的应用需求。

由于云服务的易用性和可靠性，使得租户越来越习惯把数据上传到云端存储和计算，而数以亿计的租户不分昼夜地产生级别的海量数据给云平台带来很大的负载和压力。

如何处理好不同租户或者应用之间的资源分配和作业调度问题，避免由于资源的恶性竞争而产生瓶颈，具有很大的挑战性和研究价值。

首先租户把他们的应用提交到云平台中，资源管理器会根据相应的请求给该应用划分一定的资源量（如CPU、内存、硬盘等），然后应用可以在所占有的资源中进行作业和任务的调度。

也就是说，这个逻辑过程可以抽象为两个层面的问题：一方面是底层的弹性资源分配策略，而另一方面则是上层的作业/任务调度引擎。

资源分配问题资源分配是在云平台中部署大数据集群的第一步，也是进行后续数据分析的基础。

传统的基于虚拟化技术开发的公有云平台通常是采用虚拟机模板的方法，租户可以按时或者按月租赁若干台虚拟机来构建计算集群。

这种静态的资源分配不够灵活，因为一旦租户有更多的资源需求，只能从节点数量上扩展，而不能弹性化地扩展单个节点的资源容量，重新租赁和部署给租户带来了成本上和时间上的开销。

而面向大数据处理的分布式架构Hadoop[8]最早版本1.0中的资源管理引入了“槽位”（Slot）的概念，将每个节点预先配置好1OVM是Virtual Machine的缩写。

即虚拟机，指通过软件模拟的具有完整硬件系统功能的、运行在一个完全隔离环境中的完整计算机系统。

可用的Slot总数，然而一旦启动后则无法动态修改这些Slot数目和配置。并且资源划分粒度过大，容易导致节点资源利用率过高或者过低。

比如，如果事先给一个Slot分配1个CPU和2GB内存，而实际任务运行只需要1GB内存，则会产生“资源碎片”，从而降低集群资源的利用率。

同样，如果一个任务需要2个CPU，则会隐式地抢占其他任务的资源，产生资源抢占现象，从而可能导致集群负载过高。

于是，在Hadoop后来的2.0版本中提出了资源管理系统并摒弃了Slot的概念。为了精确控制资源分配，让任务直接向调度器申请自己需要的资源（比如某个任务可申请1个CPU和1.5GB内存），但是资源总量仍然是静态配置的，不可动态修改

总的来说，目前的资源分配方案不够灵活和弹性化，难以适应上层应用的动态资源需求的变化。

作业调度问题作业/任务调度是大数据处理引擎中不可绕开的问题，也是直接影响到大数据处理性能的关键因素。

从最早的2004年Google提出的分布式处理架构MapRe-duce，一直到2012年加州大学伯克利分校的AMPLab提出的基于内存计算的Spark，处理性能提升了100倍，也说明人们一直没有停止过改善大数据处理性能的研究步伐。

针对不同的应用场景，学术界研究出了不少有价值的作业调度器，比如在异构性集群中，可能会出现落后节点和落后任务。

根据木桶原理，最慢的任务决定了作业的完成时间，Zaharia等人提出了LATE[13]调度器从而改善了探测落后任务的算法。

又比如在考虑具有多种资源类型（比如CPU和内存）需求的作业的公平性资源分配问题时，Ghodsi等人提出的DRF[14]调度器采用了多资源分配策略，并且在Mesos的设计和实现中进行了评估。

资源分配问题与作业调度问题的联系乍看之下，云计算资源分配问题与作业调度问题没有直接的关系，但事实上两者之间存在着密切的联系

一方面，云计算资源分配与作业调度之间存在互相制约的关系。底层的资源分配为上层的作业调度提供了支撑和实现接口。

例如任何一个调度算法都需要根据当前的系统资源利用状况来进行决策；而上层的作业调度结果又反过来影响底层的资源使用。

另一方面，资源分配与作业调度两者具有一致性的目标，即提高大数据在云中的处理性能。

一个弹性化的、细粒度的云计算资源分配方案与一个高效的分布式作业/任务调度策略有机结合起来，可以显著地改善大数据处理的资源划分公平、作业处理性能以及集群效率等问题。

目前，学术界对云计算的资源分配问题和作业调度问题虽然分别展开了大量的研究，然而，都还没有得出最理想的解决方案，

主要研究内容从本质上看，云计算中大数据的处理性能优化问题主要是由底层的资源分配方案及其上层的作业调度策略所共同决定的。

就云资源管理问题而言，现有的静态虚拟机固定分配策略相对古板，不利于用户弹性化地扩展其计算规模（Scale-up）。

更无法适应上层应用动态的资源需求变化，造成了资源冗余和碎片，降低了集群的资源利用率。

就作业调度问题而言，又可分为传统大数据离线调度和流数据实时调度两种场景：对于离线调度场景，现有的作业调度策略很少甚至没有对从作业到处理器的映射问题进行综合考虑。

如果服务器分配结果不良会极大影响到总的作业完工时间，同时现有的策略更多是从理论上证明其性能下界而没有提出可行性的实现系统架构。

对于实时调度场景，现有的方法没有考虑到离散流数据处理系统的特殊性，即每隔一段时间处理一小批数据，这样数据的到达是连续的。

而数据的处理则是离散的，直接导致了计算资源的浪费。同时现有的算法在机器查找和任务排序方面时间开销过大，大大降低了调度的效率，影响了流处理系统的稳定性。

此外，现有的资源分配策略及调度算法，大部分都是侧重于某个目标的优化，而如果要同时满足多个目标的优化以及针对任务的多种资源需求，形成一个从资源分配到作业调度的聚合调度器仍面临巨大的挑战。

研究云计算中资源分配的弹性化问题与模型研究如何提高云服务提供商的平台吞吐率以及集群资源的高效利用办法，从而接纳更多的租户作业请求。

由于通过测量可以发现大数据应用在其运行周期内出现严重的资源利用不均衡现象

由于传统意义的静态虚拟机无法满足大数据应用的动态资源需求变化，而单纯增加计算节点的数量无疑会增加租户的租用成本和重新配置的时间开销。

研究提高作业处理性能的启发式算法研究如何基于已知的大数据作业类型、作业到达时间和处理时间以及DAG2O内部依赖结构等信息。

采用线性规划松弛原理和最短关键路径技术，从而实现最小化总的作业完工时间以优化集群处理性能。

由于影响作业完工时间的关键因素是作业与服务器的映射问题（MSJO），因此本文研究如何对MSJO问题进行建模和分析。

但是由于MSJO是一个NP难问题，无法在多项式时间内求出最优解，因此首先研究如何通过迭代方式求出近似解的算法

研究高效的面向流处理系统的实时调度方法研究快速实时的任务调度方法，降低调度器的时间开销，最小化CPU资源的使用，提高流处理系统的执行效率。

快速地决定下一个任务应该分配给哪个处理器去运行，可以极大地降低传统的Best-Fit（BF）算法和Best-Fit-Decreasing（BFD）算法的机器查找时间和排序时间，保证流处理系统的稳定运行。

为了达到这一设计目标，本文通过机器的标记和任务分配方法，将基于装箱原理的任务分配策略进行优化。使得任务调度过程能在线性时间复杂度内完成。

此外，本文在进行问题分析和建模时，还运用熵综合考虑了任务的多样性和处理器的异构性等问题。

研究基于多目标权衡优化的多资源聚合调度方案研究如何在保证应用间良好的性能隔离前提下，优化作业处理性能和集群资源利用效率等次级目标。

通过对现有的经典调度器进行资源分配公平指数性、作业处理性能和集群效率三个方面的评估和比较，发现每个调度器各有利弊，即几乎都是某一指标表现很突出但其他指标却远远不如其他调度器。

为了达到三个指标的权衡和优化，基于长期性公平的利他原则思想，研究如何使得集群调度器不是一种运行在物理服务器和操作系统之间的中间软件层。

可允许多个操作系统和应用础上结合现有的云计算资源管理方法，进一步提出了基于弹性虚拟机动态调整的资源分配策略。

能够在现有的云服务体系结构基础上进行增量式部署。由于采取了“按需分配”的模式，并且能够在作业运行时间内进行动态资源调整，可以最大限度地避免了资源碎片和过度分配的情况。

因此，相比传统的静态虚拟机办法，弹性资源分配策略能够提高31.3%的作业吞吐率。

设计了基于线性规划的最小化作业完工时间的启发式算法论述了大数据作业与服务器映射问题对于作业处理性能影响的重要性，提出了基于线性规划的最小化总的加权作业完工时间模型。

包含了任务间的互相依赖关系、任务到达时间和处理时间等约束条件，根据线性规划松弛原理和最短关键路径。

设计了一个3倍于最优解的近似算法MarS求解模型。由于MarS算法在线性规划模型所求的理论解基础上，每次都按照最紧凑的路径执行任务，即尽可能避免任务之间的延迟时间以及单个处理器的空窗期，使得MarS启发式算法具有目前最小的上界，比以往最好的近似算法又改善了5倍。

当用户通过审计发现存储的数据已被破坏或删除时，其可利用该方法对存储的原始数据进行应急恢复，避免了因数据丢失而带来的财产损失。

从方案评估中可知，本章方案在各阶段都实现了数据的隐私保护。安全性分析表明所提出的方案是正确的，且能够提供存储证明的不可伪造性、抗恶意攻击等。

从效率分析和模拟分析的结果中可知，所提出的方案具有较高的计算效率，可满足实际云数据存储中的使用需求。