Abstract: Concerning the problem that sharp increase of data input rate leads to the rising of computing latency which influences the real-time of computing in big data stream processing platform, a dynamic dispatching strategy based on flow network was proposed and applied to a data stream processing platform named Apache Flink. Firstly, a Directed Acyclic Graph (DAG) was transformed to a flow network by defining the capacity and flow of every edge and a capacity detection algorithm was used to ascertain the capacity value of every edge. Secondly, a maximum flow algorithm was used to acquire the improved network and the optimization path in order to promote the throughput of cluster when the data input rate is increasing; meanwhile the feasibility of the algorithm was proved by evaluating its time-space complexity. Finally, the influence of an important parameter on the algorithm execution was discussed and recommended parameter values of different types of jobs were obtained by experiments. The experimental results show that the throughput promoting rate of the strategy is higher than 16.12% during the increasing phases of the data input rate in different types of benchmarks compared with the original dispatching strategy of Apache Flink, so the dynamic dispatching strategy efficiently promotes the throughput of cluster under the premise of task latency constraint.

Key words: data stream, task scheduling, flow network, maximum flow, Apache Flink

摘要： 针对大数据流式计算平台中输入数据流速急剧上升所导致的计算延迟升高问题，提出了基于流网络模型的动态调度策略，并将其应用于Flink数据流计算平台。首先，通过定义有向无环图（DAG）中每条边的容量和流量将其转化为流网络模型，并通过容量检测算法确定每条边的容量值；然后，通过最大流算法计算对应的增进网络和优化路径，从而在输入速率上升阶段提升集群的吞吐量，并通过评估时空代价论证了算法的可行性；最后，讨论了重要参数对算法执行效果的影响，并通过实验得出了在不同类型的作业中推荐的参数取值。经实验验证得出：所提算法与Flink平台现有的任务调度策略相比，在输入速率上升阶段对不同作业类型中集群吞吐量的优化比均高于16.12%。实验结果表明动态调度策略在满足任务延迟约束的前提下有效提高了集群的吞吐量。

关键词: 数据流, 任务调度, 流网络, 最大流, Apache Flink