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

针对大数据流式计算平台原生的调度机制存在计算负载分配不均衡、资源利用率低的问题，提出异构环境下基于禁忌搜索算法的负载均衡策略，并将其应用于Apache Flink平台。首先，通过构建作业拓扑模型将流式计算作业的拓扑结构抽象为有向无环图（directed acyclic graph，DAG），并将每个任务槽（task slot）抽象为节点，为计算节点的性能评估奠定基础；其次，通过建立性能评估模型将有向无环图中带性能权值的节点导入性能评估模型，进行归一化处理得到节点性能的优劣；再将评估参数传入禁忌调度算法（tabu search for schedule，TBS）进行作业路径优化，从而得出最优作业路径；最后，使用Flink平台提供的CustomPatitionerWrapper接口将数据分配到最优作业路径包含的节点中，完成计算负载的均衡分配，从而提升Flink平台的整体性能。实验结果表明：通过禁忌调度算法优化后的负载均衡策略与原生的Flink平台相比，平均计算延迟降低了10~20 ms，资源利用率显著提高，平均吞吐量提升约15%，有效证明了负载均衡策略的有效性和优化效果。

Load balancing strategy of streaming computing platform based on tabu search

Focused on the problem of unbalanced computing load distribution and low resource utilization in the native scheduling mechanism of big data streaming computing platform, this paper proposed a load balancing strategy based on tabu search algorithm in heterogeneous environments and applied to the Apache Flink platform. Firstly, this strategy set up a job topology model and abstracted the topology of streaming computing jobs as a directed acyclic graph. Therefore, each task slot became a node, which layed the foundation for performance evaluation of computing nodes. Secondly, the method imported the perfor-mance 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.