基于禁忌搜索的流式计算平台负载均衡策略  

Load balancing strategy of streaming computing platform based on tabu search

作　　者：王英杰 李梓杨 于炯[1,2] 陈鹏程 Wang Yingjie;Li Ziyang;Yu Jiong;Chen Pengcheng(School of Software,Xinjiang University,Urumqi 830008,China;School of Information Science&Engineering,Xinjiang University,Urumqi 830046,China)

机构地区：[1]新疆大学软件学院,乌鲁木齐830008 [2]新疆大学信息科学与工程学院,乌鲁木齐830046

出　　处：《计算机应用研究》2023年第12期3701-3705,共5页Application Research of Computers

基　　金：国家自然科学基金资助项目(62262064,62266043,61966035);新疆维吾尔自治区重点研发项目(2022295358);新疆维吾尔自治区自然科学基金资助项目(2022D01C56);新疆大学博士研究生创新项目(XJU2022BS072)。

摘　　要：针对大数据流式计算平台原生调度机制存在计算负载分配不均衡、资源利用率低的问题,提出异构环境下基于禁忌搜索算法的负载均衡策略,并将其应用于Apache Flink平台。首先,通过构建作业拓扑模型将流式计算作业的拓扑结构抽象为有向无环图(directed acyclic graph, DAG),并将每个任务槽(task slot)抽象为节点,为计算节点的性能评估奠定基础;其次,通过建立性能评估模型,将有向无环图中带性能权值的节点导入性能评估模型进行归一化处理,得到节点性能的优劣;再将评估参数传入禁忌调度算法(tabu search for schedule, TBS)进行作业路径优化,从而得出最优作业路径;最后,使用Flink平台提供的CustomPatitionerWrapper接口将数据分配到最优作业路径包含的节点中,完成计算负载的均衡分配,从而提升Flink平台的整体性能。实验结果表明:通过禁忌调度算法优化后的负载均衡策略与原生的Flink平台相比,平均计算延迟降低了10~20 ms,资源利用率显著提高,平均吞吐量提升约15%,有效证明了负载均衡策略的有效性和优化效果。ed the topology of streaming computing jobs as a directed acyclic graph.Therefore,each task slot became a node,which established the foundation for performance evaluation of computing nodes.Secondly,the method imported the performance evaluation model to nodes with performance weights in the directed acyclic graph,and obtained the performance of the nodes through normalization processing.Then the evaluation parameters were passed into the tabu search for job path optimization,so as to obtain the optimal job path.Finally,by using the CustomPatitionerWrapper interface,this strategy allocated data to the nodes included in the optimal job path and completed the balancing of computational load.The algorithm then passed evaluation parameters into the tabu scheduling algorithm for job path optimization,thereby obtaining the optimal job path.The experimental results show that the load balancing strategy optimized by the tabu scheduling algorithm reduces the average computing latency by 10~20 ms compared to the native Flink platform.The strategy significantly improves resource utilization,and increases average throughput by about 15%.This effectively proves the effectiveness and optimization effect of the load balancing strategy.

关 键 词：流式计算 Apache Flink 负载均衡 性能评估 禁忌搜索算法 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]