CN108241530A - 一种基于Storm的流式计算二分图任务调度方法 - Google Patents
一种基于Storm的流式计算二分图任务调度方法 Download PDFInfo
- Publication number
- CN108241530A CN108241530A CN201611203987.2A CN201611203987A CN108241530A CN 108241530 A CN108241530 A CN 108241530A CN 201611203987 A CN201611203987 A CN 201611203987A CN 108241530 A CN108241530 A CN 108241530A
- Authority
- CN
- China
- Prior art keywords
- graph
- cluster
- node
- job
- bipartite graph
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 238000000034 method Methods 0.000 title claims abstract description 22
- 230000005540 biological transmission Effects 0.000 claims abstract description 20
- 125000002015 acyclic group Chemical group 0.000 claims abstract description 8
- 230000005012 migration Effects 0.000 claims abstract description 5
- 238000013508 migration Methods 0.000 claims abstract description 5
- 230000008569 process Effects 0.000 claims description 8
- 230000004044 response Effects 0.000 claims description 4
- 230000001934 delay Effects 0.000 abstract 1
- 238000004364 calculation method Methods 0.000 description 6
- 238000012545 processing Methods 0.000 description 6
- 238000005516 engineering process Methods 0.000 description 2
- 238000007726 management method Methods 0.000 description 2
- 230000007246 mechanism Effects 0.000 description 2
- 230000007423 decrease Effects 0.000 description 1
- 230000007812 deficiency Effects 0.000 description 1
- 238000011161 development Methods 0.000 description 1
- 238000010586 diagram Methods 0.000 description 1
- 238000009826 distribution Methods 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 238000011156 evaluation Methods 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 239000013589 supplement Substances 0.000 description 1
- 238000009827 uniform distribution Methods 0.000 description 1
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
- G06F9/46—Multiprogramming arrangements
- G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
- G06F9/5005—Allocation of resources, e.g. of the central processing unit [CPU] to service a request
- G06F9/5027—Allocation of resources, e.g. of the central processing unit [CPU] to service a request the resource being a machine, e.g. CPUs, Servers, Terminals
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2209/00—Indexing scheme relating to G06F9/00
- G06F2209/50—Indexing scheme relating to G06F9/50
- G06F2209/502—Proximity
Landscapes
- Engineering & Computer Science (AREA)
- Software Systems (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
本发明公开了基于Storm的流式计算二分图任务调度方法，其特征在于：将Storm作业有向无环图DAJG(Directed Acyclic Job Graph)节点和集群物理机节点无向图(Undirected Node Graph)节点看作二分图的两类顶点，构建二分图模型，综合集群物理机各节点的计算能力以及集群中网络传输延迟，根据任务与节点资源之间的可调度关系，采用解决二分图最大权值匹配算法进行任务调度，本发明方法在保证集群物理机资源负载均衡的情况下，减少任务执行中数据流迁移过程中的网络延迟，从而提升系统整体性能。
Description
技术领域
本发明涉及一种基于Storm的流式计算二分图任务调度方法。
背景技术
随着信息科学技术的飞速发展，云计算和物联网环境下的应用呈现出数据量大，数据流连续，表现出多源并发，实时处理等特征。针对这些流数据的实时处理，称为流式数据处理或流式计算。在大数据流式计算系统Storm中，多任务调度是影响流式计算系统Storm性能的关键因素。流式计算系统中的任务具备两个典型的特征：
(1)多任务多阶段特性。
从理论模型上来说，提交到系统中的任务在处理过程可用一个有向无环图(DAG)表示[1]。即表示的任务调度是多任务分多阶段执行，不同的阶段之间的任务需要协同执行，同一阶段的任务则需要独立并行地执行。
(2)时间特性
由于需要较集中的对数据进行计算，传统的批式大数据计算在计算耗时上的要求比较宽松。但在流式计算中，数据从数据源到计算结果都是在内存中，为了保证计算的时效性，往往对计算耗时要求比较苛刻，甚至达到毫秒级[2]。
流式计算的这些典型的特征，使得分布式环境中的多作业调度成为流式计算处理过程中的关键问题之一[3]。分布式环境下的作业调度早已被证明是一个NP难问题[4，5]。如何将待处理的作业合理地调度到相应的计算节点上执行，是作业调度的主要目的。
流式计算的任务调度和资源管理问题是流式计算的关键技术之一。目前的大数据流式计算构架中，多采用Hadoop Yarn、Amazon EC2和Apache Mesos这种细粒度的资源管理方式来管理资源，通过系统构架中的默认任务调度机制来为任务分配资源。在通用的流式计算架构中，默认的调度策略为了满足多场景的应用往往未考虑应用的实际需求以及集群的物理环境。如Storm作为流式计算业界最具影响力的系统所采用的默认调度策略是将所有作业实例化为执行线程作为任务调度单位，将所有的执行线程按照集群所拥有的资源均匀的分配到各个物理计算节点上。
Storm默认的任务调度机制可以应对一般的应用场景，但却存在以下问题：
(1)某一类的任务对CPU或内存敏感，如果将同样对CPU敏感的任务调度在同一物理机器上，则可能使该机器的多维资源利用不均衡，如CPU资源负载过高，而内存资源却空闲；
(2)在异构集群中，不同物理机拥有的资源(CPU、内存、网络带宽等)不同，将任务线程按照简单的均匀分配策略有可能导致资源稀缺的物理负载过重而导致系统吞吐率下降；
(3)某个任务的数据在A节点上，但却被调度到B节点上执行，这无疑增加了读取数据的带宽延迟开销，这在数据不落地(磁盘不参与缓存)的流式计算中的影响不可忽略；
发明内容
本发明的目的在于克服现有技术中存在的上述不足，而提供一种基于Storm的流式计算二分图任务调度方法。本基于Storm的流式计算二分图任务调度方法可以在保证集群物理机资源负载均衡的情况下，减少任务执行中数据流迁移过程中的网络延迟，从而提升系统整体性能。
本发明解决上述问题所采用的技术方案是：
一种基于Storm的流式计算二分图任务调度方法，其特征在于：将Storm作业有向无环图DAJG(Directed Acyclic Job Graph)节点和集群物理机节点无向图(UndirectedNode Graph)节点看作二分图的两类顶点，构建二分图模型，综合集群物理机各节点的计算能力以及集群中网络传输延迟，根据任务与节点资源之间的可调度关系，采用解决二分图最大权值匹配算法进行任务调度，具体步骤如下：
(1)分别对集群中异构的物理机所拥有的资源和需调度的任务集合进行形式化描述，建立两者之间的可调度关系，建立集群物理节点资源与任务之间的二分图数学模型；
(2)在调度过程中，并不是所有物理节点的可用资源都能满足作业的请求，为了满足使作业得到及时的响应，考虑根据作业的资源请求类型及集群节点提供的可用资源类型，总是将当前需要处理的作业调度到集群中资源负载相对较低的节点，通过引入数学统计值来评价作业与物理节点的可调度性；
(3)根据作业有向无环图DAJG(Directed Acyclic Job Graph)的拓扑结构，考虑将具有前后依赖关系的任务，根据当前集群节点之间的数据传输速率选择“就近”调度，使得每一阶段的调度过程中再集群之间的数据元组传输总速率最大，以此降低网络传输带来的延迟，为二分图模型引入可调度权值，即在作业可以调度到当前物理节点的条件下，利用权值衡量任务调度后数据元组迁移的速率；
(4)采用带权二分图最小权值匹配(最大权值的相反数)算法，求解物理机节点与待调度任务之间的匹配关系，使得待调度任务能获得执行所需资源的前提下，数据在集群物理机之间通过网络传输数据的总延迟最小。
本发明与现有技术相比，具有以下优点和效果：本发明方法与Storm系统中默认调度器相比，有如下方面的优势：(1)流式计算系统Storm的调度器中，所有任务对于调度器都是按照均匀分配的策略，没有考虑任务对于资源的具体需求(如计算密集型任务需要大量的CPU资源，而需要较少的内存资源)。本发明方法对物理机拥有的资源以及待调度的任务都进行了形式化的定量描述，建立了可调度的评价匹配关系，避免了由于过多的任务负载集中在同一物理机上造成的资源负载不均衡，避免系统出现“拖尾”现象，提升了系统的资源利用率。
(2)现有的Storm调度器在处理数据时，默认对于数据在网络上的传输延迟忽略。然而，相对于内存计算的毫秒级响应，网络传输的延迟显然不可忽略。本发明方法降集群中的数据元组传输速率作为二分图模型的权值，在调度过程中考虑将待调度任务调度至“最近”的资源上，使得系统的整体网络传输延迟下降，提升了系统处理数据的吞吐率。
附图说明
图1是本发明实施例作业任务集与集群的二分图模型示意图。
图2是本发明实施例算法流程图。
具体实施方式
下面结合附图并通过实施例对本发明作进一步的详细说明，以下实施例是对本发明的解释而本发明并不局限于以下实施例。
参见图1-图2，本实施例一种基于Storm的流式计算二分图任务调度方法，其特征在于：将Storm作业有向无环图DAJG(Directed Acyclic Job Graph)节点和集群物理机节点无向图(Undirected Node Graph)节点看作二分图的两类顶点，构建二分图模型，综合集群物理机各节点的计算能力以及集群中网络传输延迟，根据任务与节点资源之间的可调度关系，采用解决二分图最大权值匹配算法进行任务调度，具体步骤如下：
(1)分别对集群中异构的物理机所拥有的资源和需调度的任务集合进行形式化描述，建立两者之间的可调度关系，建立集群物理节点资源与任务之间的二分图数学模型；
(2)在调度过程中，并不是所有物理节点的可用资源都能满足作业的请求，为了满足使作业得到及时的响应，考虑根据作业的资源请求类型及集群节点提供的可用资源类型，总是将当前需要处理的作业调度到集群中资源负载相对较低的节点，通过引入数学统计值来评价作业与物理节点的可调度性；
(3)根据作业有向无环图DAJG(Directed Acyclic Job Graph)的拓扑结构，考虑将具有前后依赖关系的任务，根据当前集群节点之间的数据传输速率选择“就近”调度，使得每一阶段的调度过程中再集群之间的数据元组传输总速率最大，以此降低网络传输带来的延迟，为二分图模型引入可调度权值，即在作业可以调度到当前物理节点的条件下，利用权值衡量任务调度后数据元组迁移的速率；
(4)采用带权二分图最小权值匹配(最大权值的相反数)算法，求解物理机节点与待调度任务之间的匹配关系，使得待调度任务能获得执行所需资源的前提下，数据在集群物理机之间通过网络传输数据的总延迟最小。
本说明书中所描述的以上内容仅仅是对本发明所作的举例说明。本发明所属技术领域的技术人员可以对所描述的具体实施例做各种各样的修改或补充或采用类似的方式替代，只要不偏离本发明说明书的内容或者超越本权利要求书所定义的范围，均应属于本发明的保护范围。
Claims (1)
1.一种基于Storm的流式计算二分图任务调度方法，其特征在于：将Storm作业有向无环图DAJG(Directed Acyclic Job Graph)节点和集群物理机节点无向图(UndirectedNode Graph)节点看作二分图的两类顶点，构建二分图模型，综合集群物理机各节点的计算能力以及集群中网络传输延迟，根据任务与节点资源之间的可调度关系，采用解决二分图最大权值匹配算法进行任务调度，具体步骤如下：
(1)分别对集群中异构的物理机所拥有的资源和需调度的任务集合进行形式化描述，建立两者之间的可调度关系，建立集群物理节点资源与任务之间的二分图数学模型；
(2)在调度过程中，并不是所有物理节点的可用资源都能满足作业的请求，为了满足使作业得到及时的响应，考虑根据作业的资源请求类型及集群节点提供的可用资源类型，总是将当前需要处理的作业调度到集群中资源负载相对较低的节点，通过引入数学统计值来评价作业与物理节点的可调度性；
(3)根据作业有向无环图DAJG(Directed Acyclic Job Graph)的拓扑结构，考虑将具有前后依赖关系的任务，根据当前集群节点之间的数据传输速率选择“就近”调度，使得每一阶段的调度过程中再集群之间的数据元组传输总速率最大，以此降低网络传输带来的延迟，为二分图模型引入可调度权值，即在作业可以调度到当前物理节点的条件下，利用权值衡量任务调度后数据元组迁移的速率；
(4)采用带权二分图最小权值匹配(最大权值的相反数)算法，求解物理机节点与待调度任务之间的匹配关系，使得待调度任务能获得执行所需资源的前提下，数据在集群物理机之间通过网络传输数据的总延迟最小。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201611203987.2A CN108241530A (zh) | 2016-12-23 | 2016-12-23 | 一种基于Storm的流式计算二分图任务调度方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201611203987.2A CN108241530A (zh) | 2016-12-23 | 2016-12-23 | 一种基于Storm的流式计算二分图任务调度方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN108241530A true CN108241530A (zh) | 2018-07-03 |
Family
ID=62703993
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201611203987.2A Pending CN108241530A (zh) | 2016-12-23 | 2016-12-23 | 一种基于Storm的流式计算二分图任务调度方法 |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN108241530A (zh) |
Cited By (14)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109413752A (zh) * | 2018-11-21 | 2019-03-01 | 华中科技大学 | 一种面向无线低功耗网络的实时资源调度方法 |
| CN109522108A (zh) * | 2018-10-30 | 2019-03-26 | 西安交通大学 | 一种基于Kernel合并的GPU任务调度系统及方法 |
| CN110109976A (zh) * | 2019-05-15 | 2019-08-09 | 成都四方伟业软件股份有限公司 | 数据处理方法、装置、系统及存储介质 |
| CN110213172A (zh) * | 2019-05-17 | 2019-09-06 | 华中科技大学 | 基于动态负载监测的流连接系统负载均衡方法及装置 |
| CN110222005A (zh) * | 2019-07-15 | 2019-09-10 | 北京一流科技有限公司 | 用于异构架构的数据处理系统及其方法 |
| CN110990059A (zh) * | 2019-11-28 | 2020-04-10 | 中国科学院计算技术研究所 | 一种用于倾斜数据的流式计算引擎运行方法及系统 |
| CN111522637A (zh) * | 2020-04-14 | 2020-08-11 | 重庆邮电大学 | 一种基于成本效益的storm任务调度方法 |
| CN112346866A (zh) * | 2020-11-05 | 2021-02-09 | 中国科学院计算技术研究所 | 一种基于异步数据传输的gpu调度方法及系统 |
| CN112685883A (zh) * | 2020-12-23 | 2021-04-20 | 郑州大学 | 一种舰载机保障作业调度方法 |
| CN112953759A (zh) * | 2021-01-27 | 2021-06-11 | 上海七牛信息技术有限公司 | 节点最优资源覆盖分析调整方法、装置及计算机设备 |
| CN114371936A (zh) * | 2022-01-04 | 2022-04-19 | 浙江大学中原研究院 | 一种多服务器作业的优化调度方法 |
| CN114579261A (zh) * | 2022-04-29 | 2022-06-03 | 支付宝(杭州)信息技术有限公司 | 多语言混合流的处理方法和装置 |
| WO2023116910A1 (zh) * | 2021-12-24 | 2023-06-29 | 华为云计算技术有限公司 | 一种计算资源和缓存资源调度方法、装置及系统 |
| CN116700983A (zh) * | 2023-06-25 | 2023-09-05 | 北京柏睿数据技术股份有限公司 | 一种多类型ai任务动态调度方法 |
-
2016
- 2016-12-23 CN CN201611203987.2A patent/CN108241530A/zh active Pending
Cited By (23)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109522108A (zh) * | 2018-10-30 | 2019-03-26 | 西安交通大学 | 一种基于Kernel合并的GPU任务调度系统及方法 |
| CN109522108B (zh) * | 2018-10-30 | 2020-10-27 | 西安交通大学 | 一种基于Kernel合并的GPU任务调度系统及方法 |
| CN109413752A (zh) * | 2018-11-21 | 2019-03-01 | 华中科技大学 | 一种面向无线低功耗网络的实时资源调度方法 |
| CN110109976A (zh) * | 2019-05-15 | 2019-08-09 | 成都四方伟业软件股份有限公司 | 数据处理方法、装置、系统及存储介质 |
| CN110109976B (zh) * | 2019-05-15 | 2021-09-10 | 成都四方伟业软件股份有限公司 | 数据处理方法、装置、系统及存储介质 |
| CN110213172A (zh) * | 2019-05-17 | 2019-09-06 | 华中科技大学 | 基于动态负载监测的流连接系统负载均衡方法及装置 |
| CN110213172B (zh) * | 2019-05-17 | 2020-10-30 | 华中科技大学 | 基于动态负载监测的流连接系统负载均衡方法及装置 |
| CN110222005A (zh) * | 2019-07-15 | 2019-09-10 | 北京一流科技有限公司 | 用于异构架构的数据处理系统及其方法 |
| CN110990059A (zh) * | 2019-11-28 | 2020-04-10 | 中国科学院计算技术研究所 | 一种用于倾斜数据的流式计算引擎运行方法及系统 |
| CN110990059B (zh) * | 2019-11-28 | 2021-11-19 | 中国科学院计算技术研究所 | 一种用于倾斜数据的流式计算引擎运行方法及系统 |
| CN111522637A (zh) * | 2020-04-14 | 2020-08-11 | 重庆邮电大学 | 一种基于成本效益的storm任务调度方法 |
| CN111522637B (zh) * | 2020-04-14 | 2024-03-29 | 深圳市凌晨知识产权运营有限公司 | 一种基于成本效益的storm任务调度方法 |
| CN112346866A (zh) * | 2020-11-05 | 2021-02-09 | 中国科学院计算技术研究所 | 一种基于异步数据传输的gpu调度方法及系统 |
| CN112346866B (zh) * | 2020-11-05 | 2023-09-01 | 中国科学院计算技术研究所 | 一种基于异步数据传输的gpu调度方法及系统 |
| CN112685883A (zh) * | 2020-12-23 | 2021-04-20 | 郑州大学 | 一种舰载机保障作业调度方法 |
| CN112685883B (zh) * | 2020-12-23 | 2022-12-02 | 郑州大学 | 一种舰载机保障作业调度方法 |
| CN112953759B (zh) * | 2021-01-27 | 2023-10-03 | 上海七牛信息技术有限公司 | 节点最优资源覆盖分析调整方法、装置及计算机设备 |
| CN112953759A (zh) * | 2021-01-27 | 2021-06-11 | 上海七牛信息技术有限公司 | 节点最优资源覆盖分析调整方法、装置及计算机设备 |
| WO2023116910A1 (zh) * | 2021-12-24 | 2023-06-29 | 华为云计算技术有限公司 | 一种计算资源和缓存资源调度方法、装置及系统 |
| CN114371936A (zh) * | 2022-01-04 | 2022-04-19 | 浙江大学中原研究院 | 一种多服务器作业的优化调度方法 |
| CN114579261A (zh) * | 2022-04-29 | 2022-06-03 | 支付宝(杭州)信息技术有限公司 | 多语言混合流的处理方法和装置 |
| CN116700983A (zh) * | 2023-06-25 | 2023-09-05 | 北京柏睿数据技术股份有限公司 | 一种多类型ai任务动态调度方法 |
| CN116700983B (zh) * | 2023-06-25 | 2025-03-07 | 北京柏睿数据技术股份有限公司 | 一种多类型ai任务动态调度方法 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN108241530A (zh) | 一种基于Storm的流式计算二分图任务调度方法 | |
| CN107193652B (zh) | 容器云环境中流数据处理系统的弹性资源调度方法及系统 | |
| CN111431961B (zh) | 一种云数据中心的节能任务分配方法 | |
| Selvarani et al. | Improved cost-based algorithm for task scheduling in cloud computing | |
| Zhang et al. | Network-aware virtual machine migration in an overcommitted cloud | |
| Ma et al. | A novel dynamic task scheduling algorithm based on improved genetic algorithm in cloud computing | |
| CN105491138B (zh) | 一种基于负载率分级触发的分布式负载调度方法 | |
| CN107357652B (zh) | 一种基于分段排序及标准差调整因子的云计算任务调度方法 | |
| Rathore et al. | Variable threshold-based hierarchical load balancing technique in Grid | |
| CN102394931B (zh) | 一种基于云的用户访问请求调度方法 | |
| Tantalaki et al. | Pipeline-based linear scheduling of big data streams in the cloud | |
| CN104331331B (zh) | 任务数目和性能感知的可重构多核处理器的资源分配方法 | |
| Sun et al. | A stable online scheduling strategy for real-time stream computing over fluctuating big data streams | |
| CN104407921A (zh) | 一种基于时间的yarn任务资源动态调度方法 | |
| CN107038071A (zh) | 一种基于数据流预测的Storm任务伸缩调度算法 | |
| Zhang et al. | The real-time scheduling strategy based on traffic and load balancing in storm | |
| CN108270805A (zh) | 用于数据处理的资源分配方法及装置 | |
| Farahabady et al. | A qos-aware controller for apache storm | |
| CN107977271A (zh) | 一种数据中心综合管理系统负载均衡方法 | |
| CN108132840A (zh) | 一种分布式系统中的资源调度方法及装置 | |
| CN115378789B (zh) | 一种多层次协作的流资源管理方法及系统 | |
| Qian et al. | S-storm: A slot-aware scheduling strategy for even scheduler in storm | |
| CN103176850A (zh) | 一种基于负载均衡的电力系统网络集群任务分配方法 | |
| CN111488209A (zh) | 一种启发式Storm节点任务调度优化方法 | |
| Yamazaki et al. | Implementation and evaluation of the JobTracker initiative task scheduling on Hadoop |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| WD01 | Invention patent application deemed withdrawn after publication | ||
| WD01 | Invention patent application deemed withdrawn after publication |
Application publication date: 20180703 |