Page 280 - 《软件学报》2021年第8期

2562 Journal of Software 软件学报 Vol.32, No.8, August 2021

d b
d a
d c
d d2
d d1 d e
d f1 d f2 d g

d h d i

n 1 n 2 n 3
Fig.3 Allocation of data in executor
图 3 线程内的数据分配

路径开销 l p (e ji ,e mn )表示从顶点 e ji 到顶点 e mn 内所有线程与有向边的开销之和,则
l p ( ,e e mn ) = ∑ e + ji ∑ b , j i (1)
ji
e ∈ ji E pe , mn )) b ∈ , j i B ( ( ji ep e , mn ))
(( ji e
edge
executor
令路径的计算开销 W computation cost 为线程数据的处理时间,路径的传输开销 W communication cost 为线程间数据的传
输时间,则路径的总开销 W cost 为
edge
executor
W cost = W computation cost + W communication cost (2)
edge
其中,路径的传输开销W communication cost 由节点内部线程间通信开销、节点内部进程间通信开销以及节点间通信开
销这 3 部分组成.由于每个工作节点仅存在一个工作进程,则节点内部进程间通信开销为 0.故
W = W executor + W edge + W edge (3)
cost computation cost executor cost node cost
edge
edge
其中,W node cost 表示节点间通信开销,W executor cost 表示节点内部线程间通信开销.此外,如果线程 e ji 和 e mn 位于相同
的工作节点,则线程间的通信开销可忽略不计.因此,
executor
W cost = W computation cost + W node cost (4)
edge
令整个拓扑存在 n 条路径,则拓扑执行关键路径 l(G p )为
,
( lG p ) = max{ ( ,l 1 p e e mn ),l 2 p ( ,ee mn ),...,l n p (ee mn )} (5)
ji
ji
ji
此外,根据工作节点是否位于关键路径上,将工作节点分为关键节点与非关键节点;根据线程是否位于关键
节点,将线程分为关键节点上的线程与非关键节点上线程,简称关键线程与非关键线程.
以图 4 为例,定义一条拓扑执行关键路径为 e a →e d1 →e f2 →e h ,则工作节点 n 1 与 n 2 为关键节点,工作节点 n 3
为非关键节点.
e b
e a
b a,d1 e c
e d2
e d1 e e

e f1 b d1,f2 e f2 e g
b f2,h
e h e i
n 1 n 2 n 3
Fig.4 Topology execution of critical path data transmission and processing
图 4 拓扑执行关键路径的数据传输及处理

2.2 资源约束模型
定义 4(资源约束). 为满足 Storm集群进行数据迁移时各工作节点的资源需求,需设置工作节点计算资源集