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

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

为保证数据迁移后数据处理的一致性与正确性,在将数据从非关键线程内迁出时,第一,需要选择合适的关
键节点并建立关键线程;第二,通过非关键线程的父线程将待处理的数据复制两份分别发送至两个子线程中,并
由原非关键线程继续处理数据,实时产生计算结果并发送至新增的关键线程;第三,将集群拓扑内的状态信息存
储至 HDFS;第四,修改 Zookeeper 内状态信息到节点的映射关系,同时,由新增的关键线程以异步的方式从 HDFS
中拉取对应的状态信息,并执行状态的合并;第五,通过非关键线程的父线程将待处理的数据发送至新增的关键
线程中,由新增的关键线程执行数据处理并向下游线程输出计算结果,以此来保证数据迁移后数据处理的一致
性与正确性.
为确定数据迁移算法对时间开销带来的影响,算法 2 首先判断了关键节点是否满足算法 1,其时间复杂度为
O(1);其次,算法 2 通过遍历整个集群查找合适的关键节点来解决非关键子线程的重分配问题,其时间复杂度为
O(n);此外,算法 2 在遍历整个集群过程中,通过不同的限制条件确定最合适的关键节点来进行非关键子线程的
重分配,其时间复杂度为 3O(1);最后,算法 2 在非关键子线程分配完成后,将数据迁入相对应的关键线程,并更新
Zookeeper 的配置文件,其时间复杂度为 O(1).则算法 2 的时间复杂度 T(B)为
T(B)=O(n)+3O(1)+O(1)=O(n) (27)
此外,ERDM 由算法 1 与算法 2 组成,则 ERDM 的时间复杂度 T(C)为
T(C)=O(n)+O(n)=O(n) (28)
3.3 节能模型
在 Storm 集群中,能耗一般分为基础能耗与动态能耗两种.其中,基础能耗为物理机的待机能耗,一般来说,
同一类型物理机的待机能耗是一个固定常量;动态能耗是任务执行时集群产生的能耗,通常根据任务、功率与
时间的不同,产生的动态能耗不同,因此动态能耗是一个变量.令单位时间 t(s)内基础能耗为 E base ,动态能耗为
t
E t dynamic ,则集群的总能耗 E t 为
E = t E t base + E t dynamic (29)
由于 E t base 是一个固定常量,在这里不做考虑.而 E t dynamic 作为一个变量,因此引入经典的物理公式表述,即
E t dynamic 单位为(J),可通过对单位时间 t 内的集群功率进行积分,其计算公式为
E dynamic = t ∫ t+ Δt P dynamic dt (30)
t
其中,P dynamic 单位为(W),表示时间段[t,t+Δt]内计算节点的功率.令原集群的动态能耗为 E original dynamic ,执行节能策
t
略后集群的动态能耗为 E t ERDM dynamic ,则执行节能策略后节约的能耗 E save dynamic 为
t
E save dynamic = E original dynamic − E t ERDM dynamic (31)
t
t
将式(31)带入式(30),则集群节约的能耗可通过式(32)表示.
E save dynamic = W MP dynamic − W′ MP dynamic (32)
t cost cost
其中,M 单位为(tuple),表示单位时间 t 内集群的数据量.现将式(4)和式(23)带入式(32),化简获得式(33):
⎛ ⎛ nd ⎞ − ⎞
executor
edge
executor
E t save dynamic = (W computation cost + W node cost )MP dynamic − ⎜ W computation cost + ⎜ ⎟ W node cost ⎟ edge MP dynamic
⎝ ⎝ n ⎠ ⎠
⎛ nd ⎞ −
=
edge
edge
W node cost MP dynamic − ⎜ ⎟ W node cost MP dynamic (33)
⎝ n ⎠
d
= W node cost MP dynamic
edge
n
其中,式(33)中的相关参数与式(4)与式(23)相同.式(33)表示集群拓扑执行节能策略后节约的能耗.
3.4 算法的部署与实现
一个完整的 Storm 集群由主控节点、工作节点与关联节点这 3 类节点组成,其中,主控节点上运行 Nimbus
后台服务,是 Storm 集群的中心,负责接受用户提交的拓扑并为工作节点分配任务;工作节点上运行 Supervisor