本发明涉及大数据流式处理领域，特别涉及一种基于资源成本和拓扑感知的分布式流计算调度方法。
背景技术：
1、在大数据时代，流计算是一种实时计算框架，它能够在几分钟内将任意复杂的数据处理工作部署到数百到数千个计算节点上，然后实时地处理输入数据流，从中提取有价值的信息。由于越来越多的新兴应用场景严重依赖数据流的实时处理，流计算正获得很大的关注。现在有几个被广泛采用的流计算框架，包括apache storm、apache flink、apachespark streaming等。考虑到云提供的按需、庞大且可扩展的计算和存储资源，这些大数据处理框架在公共云上安装和部署变得越来越受欢迎。
2、apache storm框架基于java和clojure，可免费使用并支持分布式实时计算，它能够以简单的方式可靠地处理无界数据流。它的三个主要组件是：spout、bolt和topology(拓扑)；在storm中，流应用逻辑被抽象为流拓扑。拓扑是有向无环图(dag)。dag中的顶点表示spout或者bolt组件。spout是数据流的源，通常从外部读取数据源，然后将元组发射到bolt中。一个bolt使用来自spout或其他的bolt的元组(tuple)，并以用户提交的代码逻辑来进行处理。它们能够在多台物理主机上并行的执行任务。dag中的边表示这些顶点之间的通信通道。dag提交到流计算系统并部署在一个或多个计算节点上。在物理逻辑上，storm集群是由其主节点nimbus和从节点supervisor组成的，它们之间是使用zookeeper来进行通信。一旦用户提交拓扑信息，nimbus就会根据其任务信息，将任务分发给各个节点下的supervisor来进行处理。在任务调度方面，storm中的任务调度是两级调度：(1)将进程分配给节点，(2)将线程分配给进程。
3、由于使用云的成本是基于实际资源使用情况而定，因此面向性能的部署模型应该根据实际需求定制资源供应；随着storm部署平台从同构的本地集群向弹性云资源池的转变，如何以最小的资源消耗实现高速数据的快速处理在调度过程中提出了新的挑战。与此同时，如何在性能和成本之间进行权衡，以更低资源成本的方式调度工作流，仍有待探索。storm的默认调度算法没有考虑以更低成本的方式调度任务；此外，storm任务调度没有考虑拓扑结构中的任务关联关系，将增加通信成本，storm中默认的任务调度方式也没有考虑集群中节点的异构性，这同样也会使得集群负载不均从而导致节点的性能下降或者节点资源的浪费，这会增加一些不必要的资源消耗。
技术实现思路
1、针对dsms部署平台从同构的本地集群向弹性云资源池的转变带来的高资源消耗和高成本问题，需要设计一种具有成本效益的qos模型，以便正确衡量性能与异构集群中任务调度的成本之间的关系。为了在保证成本约束的条件下同时将性能作为主要的调度目标，能够在资源相对较少的情况下，实现一种低延迟和高吞吐量的调度，本发明提出了一种基于资源成本和拓扑感知的分布式流计算调度方法。
2、具体方案包括以下步骤：
3、s1.基于storm数据流管理系统构建用于流式计算的c-qos模型；
4、s2.提交topology任务后，将该topology任务划分为多个块，每个块包括多个节点；
5、s3.根据c-qos模型计算该topology任务中每一节点的适应度值；
6、s4.为该topology任务中每一节点创建随机移动，并计算每一节点的随机移动增益；
7、s5.判断所有节点的随机移动增益是否均为负值，若是，则返回步骤s4，若不是，则执行步骤s6；
8、s6.若只存在一个节点的随机移动增益为正值，则让该节点执行随机移动，并进入步骤s7；若存在一个以上的节点的随机移动增益为正值，则采用轮盘赌方法从中选择一个节点执行随机移动，然后进行步骤s7；
9、s7.更新每个块的适应度值，判断是否同时满足约束条件c1和约束条件c2，若是，则输出调度方案；若不是，则返回步骤s4。
10、进一步的，topology任务中任一节点的适应度值，表示为：
11、
12、η+γ＝1
13、
14、其中，g(i)表示节点i的适应度值，表示节点i的cpu，表示节点i的内存可利用率，costcloud表示节点i所在机器在时刻t0到时刻t1这时段内的云成本，η表示节点i的资源权重，γ表示节点i所在机器云成本权重，pi(t)表示节点i在时刻t的资源使用单位价格，ui(t)表示节点i在时刻t的资源使用量；n表示节点i所在机器承载的节点数量。
15、进一步的，每一节点的随机移动增益表示为：
16、
17、其中，fi表示节点i的随机移动增益，表示节点i的内向成本，表示节点i的外向成本，v表示块集合，vi表示节点i所在的块，g(i,j)表示节点i到节点j的边权值，βi为二元移动变量，若节点i随机移动到其上游节点，则βi＝0；若节点i随机移动到其下游节点，则βi＝1。
18、进一步的，节点i到节点j的边权值g(i,j)的计算公式为：
19、
20、δ+ξ+σ＝1
21、其中，li,j表示节点i到节点j的时延，ti,j表示节点i到节点j的通信数据量，lmax表示节点i到节点j的最大时延，lmin表示节点i到节点j的最小时延，tmax表示节点i到节点j的最大通信数据量，tmin表示节点i到节点j的最小通信数据量，comnode表示节点i到节点j的通信成本，δ为时延权重，ξ为通信数据量权重，σ为通信成本权重。
22、进一步的，步骤s6中，当存在一个以上的节点的随机移动增益为正值时，将所有随机移动增益为正值的节点作为可移动节点组成移动节点集合；根据适应度值，采用轮盘赌方法计算每一个可移动节点的移动概率，选择最大移动概率对应的可移动节点执行随机移动；其中移动概率的计算公式为：
23、
24、其中，g(i)表示可移动节点i的适应度值，p表示移动节点集合，pi表示可移动节点i的移动概率，fi表示可移动节点i的随机移动增益。
25、进一步的，约束条件c1表示为：
26、
27、其中，c(vk)表示第k个块vk的权值，k表示块数量，表示最大平均块权值，∈∈(0,1)是不平衡参数；表示块vk的负载情况，uk,c表示块vk的cpu使用情况，uk,m表示块vk的内存使用情况；
28、约束条件c2表示为：
29、
30、其中，αk,j表示位于第k个块的节点j的随机移动增益是否为正，若为正，则αk,j＝1，若不为正，则αk,j＝0；n表示topology任务中的总节点数，μnode表示topology任务中随机移动增益为正的节点数量，θ表示最小移动参数；
31、在步骤s7中，若此次创建的随机移动中，topology任务中随机移动增益为正的节点数量大于等于最小移动参数，且每个块的负载均小于等于最大平衡参数，则表示同时满足约束条件c1和约束条件c2。
32、进一步的，块的适应度值表示为：
33、
34、其中，v表示块集合，vi表示节点i所在的块，g(i,j)表示节点i到节点j的边权值，表示块vi的适应度值，γi,j为二元变量，若节点i与节点j属于同一块，则γi,j＝0，若节点i与节点j属于不同块，则γi,j＝1。
35、本发明的有益效果：
36、本发明从提高应用程序性能并减少资源占用方面入手，提出了一种基于资源成本和拓扑感知的分布式流计算调度方法，解决了任务通信导致的系统性能下降和开销大问题。通过基于qos的成本模型，计算每个节点的适应度值，为每个节点创造随机游走，具体移动到哪个节点由节点的适应度值来决定，适应度值越强的节点捕获其他节点的能力就越强，这样就能保证优先将通信开销大的和任务关联性强的划分到同一个机器上，即尽量降低每个节点之间任务通信的开销，以便更好根据客户的期望保持qos的同时，最大限度地提高系统的性能并减少更少的资源占用。
1.一种基于资源成本和拓扑感知的分布式流计算调度方法，其特征在于，包括以下步骤：
2.根据权利要求1所述的一种基于资源成本和拓扑感知的分布式流计算调度方法，其特征在于，topology任务中任一节点的适应度值，表示为：
3.根据权利要求1所述的一种基于资源成本和拓扑感知的分布式流计算调度方法，每一节点的随机移动增益表示为：
4.根据权利要求3所述的一种基于资源成本和拓扑感知的分布式流计算调度方法，节点i到节点j的边权值g(i,j)的计算公式为：
5.根据权利要求1所述的一种基于资源成本和拓扑感知的分布式流计算调度方法，步骤s6中，当存在一个以上的节点的随机移动增益为正值时，将所有随机移动增益为正值的节点作为可移动节点组成移动节点集合；根据适应度值，采用轮盘赌方法计算每一个可移动节点的移动概率，选择最大移动概率对应的可移动节点执行随机移动；其中移动概率的计算公式为：
6.根据权利要求1所述的一种基于资源成本和拓扑感知的分布式流计算调度方法，约束条件c1表示为：
7.根据权利要求1所述的一种基于资源成本和拓扑感知的分布式流计算调度方法，块的适应度值表示为：
