[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

CN105786626B - 基于K划分的Storm平台线程分配方法 - Google Patents

基于K划分的Storm平台线程分配方法 Download PDF

Info

Publication number
CN105786626B
CN105786626B CN201610222259.XA CN201610222259A CN105786626B CN 105786626 B CN105786626 B CN 105786626B CN 201610222259 A CN201610222259 A CN 201610222259A CN 105786626 B CN105786626 B CN 105786626B
Authority
CN
China
Prior art keywords
subset
node
storm
max
weight
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.)
Active
Application number
CN201610222259.XA
Other languages
English (en)
Other versions
CN105786626A (zh
Inventor
肖甫
张哲峰
韩志杰
王少辉
刘磊
王汝传
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Nanjing Post and Telecommunication University
Original Assignee
Nanjing Post and Telecommunication University
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Nanjing Post and Telecommunication University filed Critical Nanjing Post and Telecommunication University
Priority to CN201610222259.XA priority Critical patent/CN105786626B/zh
Publication of CN105786626A publication Critical patent/CN105786626A/zh
Application granted granted Critical
Publication of CN105786626B publication Critical patent/CN105786626B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

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/5083—Techniques for rebalancing the load in a distributed system
    • 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/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
    • G06F9/3885—Concurrent instruction execution, e.g. pipeline or look ahead using a plurality of independent parallel functional units
    • 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/501—Performance criteria

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

本发明公开了基于K划分的Storm平台线程分配方法，首先建立带权值的有向无环图，并在深入理解Storm平台调度方案、通信机制的基础上，将任务的有向无环图划分成多个子集，对应的将大流量通信的线程尽量分配在同一个进程中，从而利用高效的内存队列处理大流量数据，以尽量减少不同进程之间的网络流量，从而提高传输效率。

Description

基于K划分的Storm平台线程分配方法
技术领域
本发明涉及数据流处理技术领域，特别涉及基于K划分的Storm平台线程分配方法。
背景技术
流式数据是大数据时代的一种重要数据形态，相比于静态、批处理和持久化的旧式数据，流式计算以连续、无界和瞬时性为特征。Storm作为一个分布式实时计算系统，可进行可靠的无界数据实时计算，在实时分析、在线机器学习、持续计算等领域得到广泛的应用。Storm具有高吞吐量、可拓展性、容错性、保证数据被处理等特点，并被众多网站采用。
Storm平台包括以下组件：Spout表示数据源，可从外部数据，如消息队列、文件系统中读取；Bolt进行数据处理，自定义方法实现对数据的处理；Topology表示整个拓扑，定义了内部组件和流组关系，形成一个以Spout和Bolt实例为节点，以组件之间信息传递方向为边的有向无环图(DAG，Directed Acyclic Graph)。
Storm的并发模型分成进程(Worker)、线程(Executor)和任务(Task)。每台计算机可以运行一个或多个Worker(本质是一个JVM进程)，但一个Worker只能属于一个Topology；一个Worker中可以有一个或多个Executor(代表一个Spout或者Bolt组件)，一个Executor可以运行一个或多个Task，Task进行实际的数据计算。Worker数、每个组件的Executor数(在Storm里称为并行度)和每个Executor的Task数(默认一个Executor产生一个Task)需要人工定义。Storm的默认线程分配方式，是尽量将Executor(线程)平均分配到Worker(进程)上、尽量将Worker平均分配到集群节点上。
Storm系统中，进程(Worker)之间的通信采用ZeroMQ或Netty方式，通过网络Socket传输，而进程内部通信采用Disruptor Queue，通过内存队列通信。相比之下进程间通信因为涉及序列化和Socket连接，通信负荷较大，而进程内通信不需要序列化和采用内存队列，相对效率高的多。
现有Storm的默认调度方案中，由于仅考虑将线程(Executor)平均分配，而线程产生流量大小不一，相比将大流量信息流通过网络传输，在内存内部传输效率更高，因此如果能实现较为优化的任务分配方案，可以更好地降低总体网络的通信负荷，提高集群效率。
发明内容
本发明针对Storm系统中默认调度方案造成的整体通信负荷较大的问题，提出一种基于K划分的Storm平台线程分配方法，通过将图划分成多个子集的解将Executor划分到多个Worker，划分过程中采用贪心准则，尽量将大流量数据流分配在进程内部，从而减少进程之间的数据流量，相较仅考虑平均分配的默认调度方案减小整个系统的通信总负荷。
基于K划分的Storm平台线程分配方法，包括以下步骤，
S1、在Storm并发模型中获取Spout组件和Bolt组件，以及组件间的并行度，确定Executor线程数、Worker子集数和边，得到带权值的有向无环图；
S2、将具有n个节点的有向无环图G(V,E)划分成k个子集V1、V2……Vk，其中V表示图中顶点的集合，E表示图中边的集合，|V|＝n，每个子集至多含有n/k+1个节点，使得最终连接不同子集的边权值之和最小，同时各子集内部边的权值之和最大；
S3、将V1中对应的Executor线程分配给Worker1，将V2中对应的Executor线程分配给Worker2，以此类推，将Vk中对应的Executor线程分配给Workerk，完成任务分配。
S2的具体过程为：将所有节点置于Vk子集，生成每个子集Vi时(i＝1,2……k)，如果Vi是空集，则将Vk中权值最大的边的两个端点中的任意一个节点v放入Vi中，候选集为Vi的邻节点；如果Vi不是空集，则在候选集中选择增益最大的节点vmax放入Vi，使vmax和Vi子集中其他节点之间的边的权值和尽量大而vmax和Vk子集的节点之间的边的权值和尽量小。
所述增益是指：
A、选取所述vmax和Vi子集中其他节点之间的边的权值和与vmax和Vk子集的节点之间的边的权值和差值最大的节点，从Vk中取出放入Vi，更新候选集S为此时Vi的所有邻节点；
B、重复A，直到Vi中节点个数达到n/k+1为止，则Vi子集完成。
本发明在深入理解Storm平台调度方案、通信机制的基础上，采用基于图k划分算法将任务的DAG图划分成多个子集，对应的将大流量通信的线程尽量分配在同一个进程中，从而利用高效的内存队列处理大流量数据，以尽量减少不同进程之间的网络流量，从而提高传输效率。
附图说明
图1为本发明实施例用到的Storm平台的并发模型示意图；
图2为图1中实施例基于K划分的Storm平台线程分配方法的流程图；
图3(a)为图1中实施例的原始DAG、图3(b)为对图3(a)采用传统分配方案的结果、图3(c)为对图3(a)采用本实施例基于K划分的Storm平台线程分配方法的结果。
具体实施方式
为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。
如图1所示，Storm的并发模型分成进程Worker、线程Executor和任务Task。每台计算机可以运行一个或多个Worker，但一个Worker只能属于一个Topology；一个Worker中可以有一个或多个Executor，一个Executor可以运行一个或多个Task，Task进行实际的数据计算。
本实施例基于K划分的Storm平台线程分配方法，过程如下：
步骤1：读取程序代码，其中的组件Spout和Bolt对应节点的种类、并行度对应该节点的个数、组件之间的流组关系对应边，配置中设定的Worker数对应要划分成的子集个数，生成该任务的DAG，如图3(a)所示。该DAG图将被划分成2个子集，即k＝2。
考虑到Storm中仅统计了各组件传输的数据项，而数据项中字段多少、类型各有不同，仅以数据项的多少衡量节点之间的流量是不客观的。为尽量精确，采用实际的流量来衡量数据量大小。将每个Executor分配到一个Worker中，短暂运行一段时间，通过监听端口的方式确定经过该端口的网络流量，从而确定Worker之间(也即确定了对应Executor之间)的通信负荷，以此作为边的权值。至此，该程序转化成了一个带权值的有向无环图G(V,E)，V为节点的集合，|V|＝n,E为边集合。
步骤2：此时问题抽象成了一个k划分问题，即：如何将一个具有n个节点的有向无环图G(V,E)，划分成k个子集，每个子集至多含有n/k+1个节点(尽可能的让每个子集中节点数相等)，要求最终连接不同子集的边权值之和最小(也即各子集内部边的权值之和最大)。为解决该k划分问题，采用如下启发式算法：首先将所有节点置于Vk子集，以如下办法依次生成k个子集：生成每个子集Vi时，如果Vi是空集，则将Vk中权值最大的边的两个端点中的任意一个v放入Vi中，此时Vi中只有一个节点v，候选集为Vi(此时只有一个v)的邻节点；如果Vi不是空集，则在S中选择增益最大的节点vmax放入Vi，所述增益是指：
A、选取所述vmax和Vi子集中其他节点之间的边的权值和与vmax和Vk子集的节点之间的边的权值和差值最大的节点，从Vk中取出放入Vi，更新候选集S为此时Vi的所有邻节点；
B、重复A，直到Vi中节点个数达到n/k+1为止，则Vi子集完成。
以此方法形成k-1个子集，剩下的就属于Vk子集。
步骤3：按步骤2所产生的结果，将V1中各节点对应的Executor分配给Worker1，将V2中节点对应的线程分配给Worker2，以此类推，重新进行任务分配。
由于Storm的传统调度方案是将Executor尽可能在Worker上平均分配，而不考虑其他指标，导致可能进程之间出现大量数据传输，从而产生大量的底层Socket报文，有造成平台运行性能低下的可能，其结果如图3(b)所示；而本实施例在深入理解Storm平台调度方案、通信机制的基础上，将任务的DAG图划分成多个子集，对应的将大流量通信的线程尽量分配在同一个进程中，从而利用高效的内存队列处理大流量数据，以尽量减少不同进程之间的网络流量，从而提高传输效率，结果如图3(c)所示。
本发明方案所公开的技术手段不仅限于上述实施方式所公开的技术手段，还包括由以上技术特征任意组合所组成的技术方案。

Claims (1)

1.基于K划分的Storm平台线程分配方法，其特征在于，包括以下步骤，
S1、在Storm并发模型中获取Spout组件和Bolt组件，以及组件间的并行度，确定Executor线程数、Worker子集数和边，得到带权值的有向无环图；
S2、将具有n个节点的有向无环图G(V,E)划分成k个子集V1、V2……Vk，其中V表示图中顶点的集合，E表示图中边的集合，|V|＝n，每个子集至多含有n/k+1个节点，使得最终连接不同子集的边权值之和最小，同时各子集内部边的权值之和最大，具体过程为：将所有节点置于Vk子集，生成每个子集Vi时(i＝1,2……k)，如果Vi是空集，则将Vk中权值最大的边的两个端点中的任意一个节点v放入Vi中，候选集为Vi的邻节点；如果Vi不是空集，则在候选集中选择增益最大的节点vmax放入Vi，使vmax和Vi子集中其他节点之间的边的权值和尽量大而vmax和Vk子集的节点之间的边的权值和尽量小；
S3、将V1中对应的Executor线程分配给Worker1，将V2中对应的Executor线程分配给Worker2，以此类推，将Vk中对应的Executor线程分配给Workerk，完成任务分配；
所述增益是指：
A、选取所述vmax和Vi子集中其他节点之间的边的权值和与vmax和Vk子集的节点之间的边的权值和差值最大的节点，从Vk中取出放入Vi，更新候选集S为此时Vi的所有邻节点；
B、重复A，直到Vi中节点个数达到n/k+1为止，则Vi子集完成。
CN201610222259.XA 2016-04-11 2016-04-11 基于K划分的Storm平台线程分配方法 Active CN105786626B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201610222259.XA CN105786626B (zh) 2016-04-11 2016-04-11 基于K划分的Storm平台线程分配方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201610222259.XA CN105786626B (zh) 2016-04-11 2016-04-11 基于K划分的Storm平台线程分配方法

Publications (2)

Publication Number Publication Date
CN105786626A CN105786626A (zh) 2016-07-20
CN105786626B true CN105786626B (zh) 2019-02-19

Family

ID=56396136

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201610222259.XA Active CN105786626B (zh) 2016-04-11 2016-04-11 基于K划分的Storm平台线程分配方法

Country Status (1)

Country Link
CN (1) CN105786626B (zh)

Families Citing this family (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN108259373B (zh) * 2016-12-29 2021-11-02 中移(苏州)软件技术有限公司 一种数据分配调度的方法及系统
CN107633125B (zh) * 2017-09-14 2021-08-31 北京仿真中心 一种基于带权有向图的仿真系统并行性识别方法
CN108415761B (zh) * 2018-01-31 2021-11-05 西北工业大学 一种基于网络流量优化的Storm任务调度方法
CN110347511B (zh) * 2019-07-10 2021-08-06 深圳大学 含隐私约束条件的地理分布式进程映射方法、装置及终端

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN103763378A (zh) * 2014-01-24 2014-04-30 中国联合网络通信集团有限公司 基于分布式流式计算系统的任务处理方法、系统及节点
CN104639466A (zh) * 2015-03-05 2015-05-20 北京航空航天大学 一种基于Storm实时流计算框架的应用网络带宽动态优先级保障方法
CN104683488A (zh) * 2015-03-31 2015-06-03 百度在线网络技术（北京）有限公司 流式计算系统及其调度方法和装置
CN105404554A (zh) * 2015-12-04 2016-03-16 东软集团股份有限公司 用于Storm流计算框架的方法和装置
CN105468626A (zh) * 2014-09-04 2016-04-06 腾讯科技（北京）有限公司 数据处理方法及系统

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US10007702B2 (en) * 2013-12-19 2018-06-26 Siemens Aktiengesellschaft Processing an input query

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN103763378A (zh) * 2014-01-24 2014-04-30 中国联合网络通信集团有限公司 基于分布式流式计算系统的任务处理方法、系统及节点
CN105468626A (zh) * 2014-09-04 2016-04-06 腾讯科技（北京）有限公司 数据处理方法及系统
CN104639466A (zh) * 2015-03-05 2015-05-20 北京航空航天大学 一种基于Storm实时流计算框架的应用网络带宽动态优先级保障方法
CN104683488A (zh) * 2015-03-31 2015-06-03 百度在线网络技术（北京）有限公司 流式计算系统及其调度方法和装置
CN105404554A (zh) * 2015-12-04 2016-03-16 东软集团股份有限公司 用于Storm流计算框架的方法和装置

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
流水行云：支持可扩展的并行分布式流处理系统;张鹏;刘庆云;谭建龙;李焱;杜华明;《电子学报》;20150430;第43卷(第4期);全文
面向大数据的分布式流处理技术综述;张鹏;李鹏霄;任彦;林海伦;杨嵘;刘庆云;《计算机研究与发展》;20141215(第2014/S2期);全文

Also Published As

Publication number Publication date
CN105786626A (zh) 2016-07-20

Similar Documents

Publication Publication Date Title
Liu et al. A hierarchical framework of cloud resource allocation and power management using deep reinforcement learning
WO2020042721A1 (zh) 一种资源配置的预测方法及设备
CN105550323B (zh) 一种分布式数据库负载均衡预测方法和预测分析器
Abd Elaziz et al. IoT workflow scheduling using intelligent arithmetic optimization algorithm in fog computing
Liu et al. A reinforcement learning-based resource allocation scheme for cloud robotics
CN112418482A (zh) 一种基于时间序列聚类的云计算能耗预测方法
CN105786626B (zh) 基于K划分的Storm平台线程分配方法
Jiang et al. Delay-aware task offloading in shared fog networks
Sîrbu et al. Power consumption modeling and prediction in a hybrid CPU-GPU-MIC supercomputer
CN113033800A (zh) 分布式深度学习方法、装置、参数服务器及主工作节点
CN113157443A (zh) 一种基于边缘计算环境的资源均衡调度方法
Zheng et al. Shockwave: Fair and efficient cluster scheduling for dynamic adaptation in machine learning
CN109558248B (zh) 一种用于确定面向海洋模式计算的资源分配参数的方法及系统
CN115373836A (zh) 计算网络、算力度量方法、调度装置及相关产品
Cao et al. A deep reinforcement learning approach to multi-component job scheduling in edge computing
Zhao et al. A hierarchical parallel evolutionary algorithm of distributed and multi-threaded two-level structure for multi-satellite task planning
Zhou et al. DPS: Dynamic pricing and scheduling for distributed machine learning jobs in edge-cloud networks
Sartzetakis et al. Resource allocation for distributed machine learning at the edge-cloud continuum
Liang et al. Communication-efficient large-scale distributed deep learning: A comprehensive survey
Zhang et al. Effective 3C resource utilization and fair allocation strategy for multi-task federated learning
Zhu et al. Learning to optimize workflow scheduling for an edge–cloud computing environment
Sartzetakis et al. Edge/Cloud Infinite-Time Horizon Resource Allocation for Distributed Machine Learning and General Tasks
CN116488344A (zh) 一种用于多类型电网设备量测数据的动态资源调度方法
Kim et al. Fedgpo: Heterogeneity-aware global parameter optimization for efficient federated learning
Wei et al. HERP: Hierarchical and distributed clouds oriented efficient resource scheduling algorithm with stochastic requirements

Legal Events

Date Code Title Description
C06 Publication
PB01 Publication
C10 Entry into substantive examination
SE01 Entry into force of request for substantive examination
CB02 Change of applicant information
CB02 Change of applicant information

Address after: No. 66, New Model Road, Gulou District, Nanjing City, Jiangsu Province, 210000

Applicant after: Nanjing Post & Telecommunication Univ.

Address before: 210023 9 Wen Yuan Road, Ya Dong new town, Nanjing, Jiangsu.

Applicant before: Nanjing Post & Telecommunication Univ.

GR01 Patent grant
GR01 Patent grant
EE01 Entry into force of recordation of patent licensing contract
EE01 Entry into force of recordation of patent licensing contract

Application publication date: 20160720

Assignee: NUPT INSTITUTE OF BIG DATA RESEARCH AT YANCHENG

Assignor: NANJING University OF POSTS AND TELECOMMUNICATIONS

Contract record no.: X2021980013920

Denomination of invention: Thread allocation method of storm platform based on K partition

Granted publication date: 20190219

License type: Common License

Record date: 20211202