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

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

15 行~第 19 行表示在满足之前的两条原则后,对关键节点是否满足网络带宽资源临界原则进行判断:若满足,则
被选节点允许数据迁入;否则,节点数据迁入不满足 tr.
Storm 框架节能策略首先需要考虑算法对集群性能的影响,原集群内拓扑处理任务为轮询调度算法,其时
间复杂度为 O(n).算法 1 首先需要对关键节点是否为极限节点进行判断,其时间复杂度为 O(1);其次,算法 1 的本
质为依次判断数据迁入节点是否满足 3 条原则,其时间复杂度为 3O(1);最后,由于需要遍历整个集群满足 3 条原
则的关键节点,类似于轮询调度算法,因此时间复杂度为 O(n).则算法 1 的时间复杂度 T(A)为
T(A)=O(1)+3O(1)+O(n)=O(n) (26)
3.2 数据迁移算法
数据迁移算法主要包括两部分组成:其一为数据的迁移需要满足资源约束条件;其二为接收数据的节点需
[9]
要满足最优线程重分配.该调度算法可以根据重写 Storm 平台的 IScheduler 接口 来实现.具体的算法描述在算
法 2 中体现.
算法 2. 数据迁移算法.
输入:重分配后的线程集合 E′(C);关键节点 CPU 的优先级 n i pr_cpu .
输出:生成一条新的拓扑路径用于数据的传输与处理.
1. if 满足算法 1 允许数据迁入关键节点 then
2. while ()EC = e′ do
′
ji
3. if 一个非关键线程存在一个父线程 then
4. e′ ← e ;
ab ab
5. end if
6. if 一个非关键线程存在两个及以上父线程 then
7. 非关键线程的重分配需要考虑 RR;
8. 非关键线程的重分配需要考虑 n ;
i pr_cpu
9. e′ ← e ;
ji ji
10. end if
11. if 运行父线程的关键节点资源达到极限 then
12. 非关键线程的重分配需要考虑 RR;
13. 非关键线程的重分配需要考虑 n i pr_cpu ;
14. e′ ← e mn ;
mn
15. end if
16. master.remappingState(Zookeeper);
17. 非关键节点的数据通过式(17)迁出;
18. 删除集群内非关键节点;
19. end while
20. Zookeeper.update(“configuration file”);
21. end if
算法 2 的输入参数为重分配后的线程集合与关键节点 CPU 的优先级;输出参数为生成一条新的拓扑路径
用于数据的传输与处理.算法的第 1 行表示判断关键节点是否满足资源约束条件;算法的第 3 行~第 10 行表示
需要减少集群内节点间的通信开销,并预防非关键线程重分配出现扎堆现象;算法的第 11 行~第 15 行表示避免
关键节点出现资源溢出现象,并预防非关键线程重分配出现扎堆现象;算法的第 16 行表示重新计算 Zookeeper
内状态信息到节点的映射关系,为保证数据迁移后数据处理的一致性做铺垫;算法的第 19 行表示更新
Zookeeper 的配置文件,防止因拓扑的记忆功能而影响到集群数据的传输与处理.