论文部分内容阅读
随着计算机技术、传感器技术、网络技术的高速发展,在越来越多的领域出现了对海量、快速到达的数据进行实时处理的需求,这种数据以连续的、不可预测的、快速的、时变的流的形式到达,被称为数据流。基于窗口的数据流处理技术在保证应用对准确性的需求下,只在内存中保留最近一段时间的数据,能加快数据的处理速度,正成为实时数据流处理的研究热点。当今,分布计算成为数据流处理的主流技术,在分布式数据流处理平台提供窗口支持具有严峻挑战。一是所设计的窗口需要支持分布式处理以加快数据处理速度,为了保证正确的窗口语义,需要花费大量的通信开销;二是为了在用户自定义操作中提供窗口支持,需要将窗口逻辑与处理逻辑解耦,这要求所设计的窗口具有通用性和可扩展性;三是数据流到达速率动态变化大,要求所设计的窗口具有弹性,以提高资源的利用率。目前基于窗口分布处理的相关研究主要面向特定操作,不具备通用性和扩展性,用户在开发基于窗口的操作时,需要重新实现窗口逻辑,极大增加开发者负担。此外,已有的窗口分布处理技术只支持少数几类窗口类型,无法满足用户需求。为此,本文围绕实现通用可扩展的窗口分布处理技术这一目标,对窗口的分布处理技术和通用窗口处理技术展开深入研究,并在分布式数据流处理平台进行系统实现,为用户提供通用可扩展的窗口分布处理模型。在分布式数据流平台上提供窗口支持,要求窗口具有通用性和扩展性以支持用户自定义操作。为此,本文提出了通用可扩展的滑动窗口分布处理框架GDSW(General Distributed Sliding Window)。GDSW针对不同类型的操作提供不同的处理模型,根据数据到达的速率,配置合适的并行度可实现实时处理。GDSW将基于窗口的操作分为两大类:数据无关的操作和数据相关的操作。对于数据无关的操作,本文提出了窗口等分算法EPartition-RR(Equal Partition-Round Robin sending),该算法采用等分窗口、轮询发送的策略,保证了窗口的正确语义,并不添加任何附加代价。对于数据相关的操作,本文提出了滑动窗口索引算法SWindowIndex(Sliding Window Index)和输入触发算法InputTrigger。SWindowIndex算法具有实时处理数据的能力,每收到一个新数据立即更新窗口状态,但相比集中式窗口处理需要花费两倍的通信开销。对于滑动步长大于1的窗口,失效是周期进行的,每收到一个新数据立即淘汰旧数据,将引入额外的通信开销。InputTrigger算法通过消除显示失效信号,可以有效降低通信开销。实验结果表明,GDSW能够应对高速数据流和超大窗口,通过提升窗口并行度,可以实现实时处理。相比集中式处理模型,在高速数据流与大窗口情景下,可以将吞吐量提升10倍以上并控制处理延迟在毫秒范围内。负载均衡是分布式系统实现的重要目标之一,不仅可以提高资源利用率,同时能够有效提高系统吞吐量和降低处理延迟。固定的数据分发算法无法适应分布不断变化的数据流。为此,本文提出了一种基于缓存使用量的动态负载均衡算法BufferUsageDLB(Buffer Usage Dynamic Load Balance)。BufferUsageDLB不断的获取输入缓存的占用情况来实现负载均衡的检测,通过收集、分析、重学习、再部署四步骤完成对任务的重新分配。此外,BufferUsageDLB算法通过估算节点的计算能力,实现更加准确的任务分配。为了处理数据分布不均的情况,采用著名的SpaceSaving算法低开销统计键值的分布,针对高频键值采用定制的数据分配方案。实验结果表明,BufferUsageDLB可以准确检测数据分布变化,保持良好的负载均衡。与已有算法相比,BufferUsageDLB可以提高80%~150%的吞吐量,并降低至少80%的处理延迟。数据流到达速率的动态变化,要求系统具有弹性扩展能力。当窗口并行度不足以处理高速数据流时,应该增加并行度;反之,当资源分配过多时,回收适当资源以提高资源利用率。为此,本文提出了基于阈值方法的弹性扩展算法EWindow,EWindow算法统计流量的大小,根据节点的计算能力,计算合适的并行度。实验结果表明,EWindow算法可以适应数据流速率的动态变化,通过调整并行度,在保证系统性能的前提下,使节点资源利用率大于70%。为了进一步验证本文的理论研究,本文基于分布式数据流处理平台Storm设计并实现了支持窗口的分布式数据流处理系统WindowStorm。WindowStorm采用层次结构设计,底层以Storm作为数据流处理引擎,在上面实现了GDSW框架,以实现窗口分布处理。最上层为应用层,提供了目前最广泛使用的基于窗口的数据流操作,用户也可以通过继承和实现窗口接口来扩展操作。此外,为了应对动态数据流分布变化以及速度变化带来的系统性能损失,WindowStorm提供了动态负载均衡模块以及弹性扩展模块。动态负载均衡模块以BufferUsageDLB算法为核心,通过实时监控各处理节点的负载情况,根据数据分布变化,动态调整数据分发方案。弹性扩展模块以EWindow算法作为核心,通过监控流量,自动调整窗口并行度以提高资源利用率。实验结果表明,WindowStorm可以有效降低用户开发复杂窗口操作的负担,在高速、动态变化的数据流下,可以以高于70%的资源利用率进行实时处理,将处理延迟控制在毫秒内。