针对波动数据流处理的、具备流感知能力且参数自适应的数据分区算法

《Future Generation Computer Systems》：Stream-aware and parameter self-adaptive data partitioning algorithm for fluctuating data stream processing

Apache Flink在异构集群中采用默认数据分区策略存在负载不均和资源利用率低的问题，本文提出SAP-DPO算法，通过构建流负载模型和动态周期模型，结合滑动窗口参数优化机制，实时调整分区更新频率，实验表明其相比默认策略、St-Stream、Dr-Stream和LADP算法，Wordcount平均吞吐量提升25.89%至5.21%，Repartition端到端延迟降低17.13%至5.65%。

　　

任一凡|李洪健

重庆邮电大学计算机科学与技术学院，中国重庆，400065

摘要

随着大数据和实时流处理的快速发展，主流的Apache Flink被广泛应用于大规模数据处理和实时分析中。然而，在异构集群中，其默认的数据分区策略存在负载不平衡和资源利用率低的问题。现有研究大多关注节点间的负载平衡，忽略了由于分区策略无法适应高度波动的数据流而导致的任务实例间负载不均衡和负载偏斜。为了解决这些问题，本文提出了流感知和参数自适应动态分区优化（SAP-DPO）算法，该算法构建了流负载模型和动态循环模型。基于这些模型，流负载感知模块通过实时数据输入监控（整合负载状态和资源利用率）来调整分区更新周期，从而提高系统的适应性；参数优化机制使用滑动窗口来调整循环模型参数，以获得更好的稳定性和有效性。实验结果表明，SAP-DPO的性能优于Flink的默认策略St-Stream、Dr-Stream和LADP：分别将Wordcount平均吞吐量提高了25.89%、9.68%和3.75%，并将Repartition平均端到端延迟降低了17.13%、11.57%、12.81%和5.65%。它改善了负载平衡和资源利用率，为实时流处理系统提供了更高效的解决方案。

引言

普适数字化的普及引发了实时数据流的空前增长[1]。从社交媒体互动的随机动态和高频金融交易到物联网（IoT）生态系统的遥测输出，海量数据集以亚秒级频率生成[2]，这凸显了实时分析框架的战略重要性。然而，这类数据的内在短暂性和多维复杂性对传统处理架构提出了严峻挑战[3]。具体而言，数据摄入速度的加快要求近乎即时的响应时间，而数据模式的异构性则需要高度适应性的处理范式。因此，实施复杂的负载平衡机制对于在波动的工作负载下保持系统弹性和计算吞吐量至关重要[4]。

尽管Apache Flink在处理各种场景下的实时数据方面表现出色，但现有的数据分区策略存在显著局限性[5]。当前的更新周期调整方法相对简单，无法准确感知流数据输入率的实时变化，也无法适应动态的集群条件。当数据量突然增加时，分区策略无法及时响应，导致负载平衡能力不足，无法满足实时数据处理的动态需求。因此，优化数据分区策略以更好地适应实时数据特性对于提高系统负载平衡和整体性能至关重要。

最近，在流处理平台中，高效的负载平衡和数据分区策略对于优化系统性能和改善集群负载平衡至关重要。近年来，许多学者进行了大量关于负载平衡和数据分区优化的研究。文献[6]提出了一种针对偏斜数据流的双层协调负载平衡策略。通过分析节点负载和处理能力差异的时间变化，它对过载节点进行时隙迁移和资源优化，以平衡集群负载。然而，这种方法缺乏对流数据输入率实时波动的主动感知机制。文献[7]提出了一种基于改进的TTNS算法的资源感知调度算法。通过分类任务类型并动态监控节点资源，它实现了负载平衡，从而提高了集群资源利用率和处理性能，但其对动态变化的流特性和突发工作负载的适应性有限。文献[8]提出了Flink的成本高效任务调度算法（CETSA）和成本高效负载平衡算法（LBA-CE），以解决默认调度器在云环境中不考虑成本和负载平衡的问题，显著降低了作业执行成本并优化了负载分布。然而，其对成本效率的重视可能会在流量快速波动时牺牲响应速度和适应性。文献[9]针对默认分区方法仅关注任务局部性的问题，设计了一种随机局部性感知流分区方法。该方法基于下游的往返时间来考虑下游状态，有效优化了流数据分区的效率。然而，它没有充分考虑上游数据输入率的动态变化，这限制了其在突发工作负载场景下的有效性。文献[10]设计了一个多层次协作框架Mc-Stream，用于弹性流处理系统。该框架使用负载感知分区方法调整数据分布，并结合任务重新调度来优化实例数量和资源分配，从而解决了由于离线数据分区导致的任务延迟问题。然而，由于协调周期耗时，该框架在流量突发时缺乏灵活性。文献[11]提出了共享自适应流分区框架（SASPAR），通过跨不同数据分区策略共享同一数据流的分区结果来减少网络传输开销并优化集群负载。然而，尽管网络传输得到了优化，但其对高度不可预测的工作负载波动的适应性仍然有限。文献[12]提出了一种三层负载平衡模型和动态数据分区策略（LADP），通过基于实时负载监控动态调整数据分区策略，有效平衡了计算节点和任务实例之间的负载，提高了整体系统性能。然而，LADP的分区策略更新周期调整机制相对静态，难以灵活适应流数据输入率的动态变化。在流量突然激增的场景中，这一限制尤为明显，可能会降低系统对负载变化的响应能力，从而影响分区策略调整的效果。

尽管现有的动态分区算法可以有效应对集群节点和任务实例之间的负载不平衡，并显著提高系统的吞吐量和处理效率，但分区策略的更新周期调整方法仍然相对简单，无法准确感知流数据输入率的实时变化，因此在动态适应性方面仍有优化空间。在实际生产环境中，流数据输入率的剧烈变化通常由外部事件、用户行为或数据源的动态特性引起。尽管现有动态分区算法可以根据集群负载调整分区策略，但分区策略的更新周期调整机制过于静态，难以灵活适应流数据输入率的动态变化。在流量突然增加的情况下，甚至无法及时捕捉负载变化，从而影响调整效果。此外，现有算法的更新周期调整方法在负载较低时也可能导致不必要的资源消耗。尽管现有算法可以通过动态平衡分配机制优化负载分布，但更新周期的调整并未充分考虑流数据输入率的变化，导致在负载较低时可能需要更频繁地监控和更新，浪费计算和网络资源。

针对上述问题，并明确受到克服负载感知动态数据分区（LADP）算法静态更新周期限制的需求的驱动，本文对现有的数据分区策略进行了深入分析和优化。通过构建流负载模型和动态循环模型来优化LADP基线，量化数据波动趋势并自适应调整分区更新频率，然后提出基于负载感知参数的自适应优化算法，该算法能够在流数据输入率高波动的场景下有效提高系统的负载平衡和资源利用率。

本文的主要贡献如下：

• (1)
  构建并设计了流负载模型、动态循环模型和滑动窗口模型，其中流负载模型用于量化数据流输入率的趋势；动态循环模型用于自适应调整分区策略的更新频率，以更准确地匹配负载变化；滑动窗口模型用于参数自适应优化机制，以调整动态循环模型的相关计算参数。
• (2)
  提出了一种流感知和参数自适应动态分区优化算法（SAP-DPO），该算法能够感知负载变化，并结合参数自适应机制来稳定和有效调整分区策略的更新周期，从而有效提高系统的稳定性和整体性能。
• (3)
  基于Flink设计了一种数据分区策略生成和调度系统，包括主节点上的循环更新模块和模型参数自适应模块以及从节点上的速率收集器，该系统能够在流数据输入率高波动的场景下确保负载能力和资源利用率。
• (4)
  构建了一个基于云平台的Flink异构集群，并与Flink的默认分区算法St-Stream算法和现有的动态数据分区算法（LADP）进行了多维度比较和分析，如资源利用率、系统吞吐量、数据端到端延迟和负载平衡等方面，以验证SAP-DPO算法的有效性。

本文的其余部分组织如下。第2节描述了相关工作。第3节系统模型，第4节算法设计和实现介绍了所提出的模型和算法。第5节提供了评估和分析，第6节为结论。

相关研究

为了解决流处理平台中现有数据分区策略的局限性，许多研究人员提出了优化方案。表1总结了相关研究，其中“异构集群”严格指资源级别的硬件异构性，如不同的CPU、内存和网络容量，而不是工作负载或数据偏斜的异构性。文献[13]、[14]分析和优化了默认数据的负载不平衡问题

系统模型

本节介绍了流负载模型（第3.1节）、动态循环模型（第3.2节）和滑动窗口模型（第3.3节）。

算法设计及实现

本节介绍了基于Flink的数据分区策略生成和调度系统（第4.1节）、参数自适应算法（第4.2节）以及流感知和参数自适应动态分区优化算法（第4.3节）。

实验环境

在云平台上构建了一个Flink异构集群，该集群由12个不同资源类型的虚拟机节点组成，包括1个主节点和11个从节点。根据硬件配置，集群节点分为三种类型：中等节点配备4核CPU和8 GB内存，大型节点配备8核CPU和12 GB内存，超大型节点配备12核CPU和16 GB内存。部署在集群上的软件栈包括Hadoop、Zookeeper、Kafka和Flink等

结论

在Flink流处理系统中，实时流数据分析面临数据输入率快速变化和高度波动的挑战。需要持续监控集群负载和流数据速率，并及时调整上游操作者的数据分区策略。为了优化现有动态分区算法（LADP）在高波动数据流场景下的性能，本文提出了一种基于

CRediT作者贡献声明

任一凡：撰写 – 审稿与编辑，撰写 – 原始草稿，资源，方法论，调查，数据整理。李洪健：撰写 – 审稿与编辑，撰写 – 原始草稿，监督，资源，项目管理，方法论，调查。

资金

无资金支持

利益冲突声明

作者声明没有已知的财务利益冲突或个人关系可能影响本文所述的工作。

致谢

无

任一凡正在中国重庆邮电大学计算机科学学院攻读硕士学位，由李博士指导。他的研究兴趣包括大数据分析。