论文部分内容阅读
近年来,伴随着社交网络、移动互联网和物联网等技术领域的迅猛发展,数据量呈现爆炸式的增长。在这些领域中,通常需要实时地、高效地处理快速变化的海量数据。目前,针对数据流的实时分析和流式处理逐渐成为大数据研究的热门领域。分布式数据流监控问题在许多应用领域被广泛研究,比如:网络流量监控、传感器网络监控、Web日志使用分析和股票市场监管等领域。这些应用场景通常需要监控分布式数据流中存在的异常情况,并进行及时汇报处理。由于数据产生速度快、数据量大,传统的集中式的处理方式变得不再可行,出现了由于中心处理节点计算资源有限、存储能力不足导致的计算延迟,以及耗费大量的网络通信用来传输数据等问题。 本文主要研究基于滑动窗口的分布式数据流Top-K监控问题,即在给定的监控窗口大小内,在分布式数据流上连续地查询前K个数值最大的对象。我们采用连续的分布式监控处理模型来进行分布式数据流的监控,包含一个中心协调处理节点和多个分布式监控节点。每个监控节点负责实时接收处理对应的数据流。中心协调处理节点则负责计算全局的Top-K结果。为了高效地维护和处理数据流,本文采用基于时间的滑动窗口处理模型。该模型将给定的监控时间窗口划分为多个大小相同的窗口单元进行数据流的处理。每当一个新的窗口单元创建完成后,最早的窗口单元将由于过期被移除监控窗口。伴随着监控窗口的滑动,分布式监控节点上对象的数值也随着不断变化。连续地查询前K个数值最大的对象,需要频繁地从分布式监控节点获取对象变化的数值,并计算新的Top-K结果。这将导致整个分布式监控系统的通信负载和计算消耗加重。 为了能够尽可能降低分布式监控系统中出现的通信开销,本文提出了一种基于调整因子的对象数值重分配算法。该算法通过指派调整因子来协调分布式监控节点上对象的数值,使得分布式监控节点上的本地Top-K结果与全局的Top-K结果保持一致。当本地的Top-K结果出现不一致时,才重新进行协调,并计算出新的全局Top-K结果和新的调整因子。该算法只在分布式监控节点出现违反约束时,才需要额外的通信来协调全局的信息,所以能大大减少分布式监控系统中的通信负载。 我们在Apache Storm分布式流数据处理平台上实现上述的Top-K监控算法,并通过大量实验证明了该算法在处理分布式数据流上的Top-K监控具有高效性和可扩展性。