论文部分内容阅读
近年来,传感器网络、物联网、云数据中心和移动互联网等新技术的快速发展使时间序列数据呈现了爆炸式增长,而时间序列数据具有其他类型数据所不具备的特点。首先,时间序列数据规模非常大,同时又是以数据流的形式源源不断产生,其计算面临着数据流频率高、序列过长和数据量过大而导致响应时间过长的问题;其次,时间序列数据还具有维度高、特征多样化等特点,其索引划分精度和处理效率需进一步提高。在时间序列数据处理平台中还有大量问题需要解决,针对离线批处理、在线计算和数据流实时处理三种典型的大数据处理模式,本文分别选取了基于MapReduce的海量时间序列的相似性连接、基于HBase的时间序列数据的皮尔森相关系数(下文简称"相关系数")估算和实时数据流多连续查询共享三个关键问题进行深入研究;同时针对海量时间序列数据处理平台的Hadoop集群,深入研究了集群网络调度问题。具体创新如下:(1)针对海量时间序列的相似性连接问题,基于MapReduce提出了索引结构相似性连接树SJT(Similarity Join Tree)。SJT可以通过结点之间的位置关系记录分区阶段产生的计算量,在Reduce阶段利用这些已有的计算量剪枝大量精算阶段的计算量,以提高计算效率;为保证分区负载均衡,扩展F-M(Fiduccia-Mattheyse)算法,设计了基于SJT的图分区算法,该方法可以保证分区之间传输的数据量最小。实验证明,提出的方法优于当前的最好的方法ClusterJoin和MAPSS。(2)为了提高在HBase上实时计算长时间序列相关系数的效率,提出了一种相关系数上下界的快速估计算法DCE。为了进一步减少I/O代价,对DCE算法进行扩展,提出了 ADCE算法,该算法通过维护一种多层摘要数据,能够通过迭代对相关系数进行估计。实验证明,提出的算法能够快速计算长时间序列(如:108、1010的长度)的相关系数。(3)针对实时数据流聚集运算,提出基于窗口的多连续查询的协同聚集模型,可以在窗口中实现结果共享,以避免重复的聚集操作。已有的聚集共享方法往往受到窗口步长限制,而本文提出的多连续查询环境下基于步长和结果的窗口重用机制,可以通过一系列逐渐减少的多值来简化聚集过程,每一步都缩减操作步骤,并完成结果共享。提出了 feed语义来标准化共享全过程,并提出compose-and-declare框架来处理数据共享逻辑。实验证明,提出的方法比当前的最好方法TriWeave性能有所提升。(4)为了减少时间序列数据处理作业的完成时间,基于Hadoop集群,通过实时监控并获取应用层的网络流信息,提出了基于作业的优先级调度方法。提出Flow-based和Spray两种利用等价多路径的方法,并在Fat-Tree拓扑中实现负载均衡。实验证明,提出的调度方法可以提升shuffle阶段作业执行效率,尤其是减少了最高优先级作业的网络传输时间。