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

蒲勇霖 等:Storm 平台下的线程重分配与数据迁移节能策略 2561

与数据处理编程单元(bolt)两类;B(G)={b 1,2 ,b 1,3 ,…,b n−1,n }为有向边的集合,表示各组件间的数据传输链路.如果
∃b i,j ∈B(G)且 i≠j,则 c i ,c j ∈C(G)表示数据从 c i 发出由 c j 接收.则组件与有向边的对应关系可通过图 1 表示.
组件

c e

b b,e b e,g 数据流
b g,i
c b c g c i
b d,g
b b,d
c d b d,f b f,i
b a,d
b f,h
c a b a,c c f c h
b c,f
c c

Fig.1 A logical DAG of a stream application
图 1 流应用的逻辑 DAG
为提高 Storm 集群的执行效率,需要满足同一时刻执行多个组件,即∀c j ∈C(G),E(C)={e j1 ,e j2 ,…,e jn }.其中,每
个元素 e ji 为一个线程(executor),且 e ji 表示组件 c j 运行第 i 个线程.图 2 为 Storm 集群数据处理及传输示意图,
由 11 个线程与 20 条有向边组成.其中,{e a ,e b ,…,e i }为线程集合,且线程 e a 与 e b 通过拓扑链路发送数据,而后续线
程接收上游线程发送的数据.以此类推,完成整个拓扑.

c e
e e
c g
c b c i
e g
e b c d e i
e d1
c f
c a c d2 c h
e f2
e a e h
e f1
c c
e c

Fig.2 Data processing and transmission in Storm cluster
图 2 Storm 集群数据处理及传输
此外,令线程 e a 为线程{e c ,e d1 ,e d2 }的父线程,则线程{e c ,e d1 ,e d2 }是线程 e a 的子线程.线程 e b 为线程{e d1 ,e d2 ,e e }
的父线程,则线程{e d1 ,e d2 ,e e }是线程 e b 的子线程.以此类推,完成父线程与子线程间的对应关系.
定义 2(线程内的数据分配). 令 N(C)={n 1 ,n 2 ,…,n m }为集群工作节点集合,且每个工作节点内存在多个线程,
由定义 1 可知,工作节点的数据均匀分配到集群的线程上.记工作节点分配给线程 e ji 的数据为 d ji (若线程的并行
度为 1,则该线程上的数据为 d j ),则集合 D n ={d j1 ,d j2 ,…,d jn }表示工作节点分配到线程上的数据集合.图 3 为线程内
数据的分配示意图,由 3 个节点与 11 个线程组成.其中,N={n 1 ,n 2 ,n 3 }表示工作节点的集合,而线程内的数据为
D = { ,d d ,d },D = { ,d d ,d ,d },D = { ,d d d , }.d
,
1 n a d 1 1 f 2 n b d 2 f 2 h 3 n c e g i
此外,为消除节点内部进程间通信开销,图 3 为各工作节点仅分配一个工作进程(worker),因此,拓扑中的通
信开销可分为两类:一类为类似于数据 d d1 与数据 d f1 之间的节点内部线程间通信;一类为类似于数据 d d2 与数据
d f1 之间的节点间通信.无论集群拓扑内如何传输数据,凡存在直接对应关系,都符合上述传输方式.
定义 3(路径开销). 令集合 B(p(e ji ,e mn ))存在一条子路径 p(e ji ,e mn ),表示从顶点 e ji 开始到顶点 e mn 结束.则需要
满足的条件为:如果∃k,则 b j,k ∈p(e ji ,e mn ),b k,i ∈p(e ji ,e mn ).由此,对于∀b j,i ∈p(e ji ,e mn )都存在.此外,对于∀b k,l ∈p(e ji ,e mn ),
如果 k≠j,则∃m 与 b m,k ∈p(e ji ,e mn );如果 i≠j,则∃m 与 b l,m ∈p(e ji ,e mn ).