基于混合处理模型的乱序数据流分布式聚合查询处理技术

为了解决现有的乱序数据流聚合查询处理技术不能在降低查询处理延迟,同时保障聚合查询结果的最终正确性的局限性问题,本研究设计了混合嵌入分布式流处理模块和分布式批处理模块的乱序数据流分布式聚合查询处理技术。该技术一方面基于用户给定的结果质量,限制自适应地优化流处理模块所用的缓冲区大小,从而尽可能降低流处理的查询处理延迟;另一方面基于备份于分布式数据存储系统的历史流数据,并以批处理的方式实现对极其晚到流元组的查询处理,从而保障聚合查询结果的最终正确性。基于真实的乱序数据流数据集对该技术进行测试分析表明:该技术在平均查询处理时延、查询结果精度和系统可扩展性方面,比目前最好的基于缓存的乱序数据流处理技术均具有显著优势。     

分布式可扩展数据流连接算法

Join-Matrix是一种高性能的连接矩阵模型,方便部署于分布式环境下,支持任意连接谓词的数据流连接操作.由于采取随机分发元组作为路由策略,Join-Matrix可利用对元组内容的不敏感性来有效抵御数据倾斜.为了实现工作节点的负载均衡以及网络传输代价的最小化,基于连接矩阵模型设计一种高效的数据划分方案尤为重要.针对数据流连接处理,本文设计并实现了一种新颖的连接算子,可灵活地进行划分方案的自适应调整,以应对实时动态变化的数据分布.具体来说,我们根据数据流流量的采样信息和系统额定负载,通过一个轻量级的决策器制定出一个数据划分方案和相应的数据迁移计划,在保证输出结果完整性与正确性的情况下,实现迁移代价的最小化.本文在多种不同的数据集上进行了大量对比实验,结果证明,在资源利用率、系统吞吐率与时间延迟等方面,该连接算子较对比系统具有更高的性能体现.     

OceanBase中基于布隆过滤器的连接算法

在大数据时代,"去IOE"运动的推进以及"双11"等活动的兴起对分布式数据库系统提出了更高的要求.OceanBase是阿里巴巴集团自主研发的开源分布式数据库,支持海量数据跨行跨表事务,但是对复杂查询的处理性能仍有待提高,其中连接操作带来的网络传输严重影响了数据库的性能.本文提出了一种基于布隆过滤器的连接算法,通过构建布隆过滤器对右表数据进行过滤,减少了不必要的数据传输开销,降低了数据处理带来的内存资源的消耗.本文在OceanBase上实现了该算法,并通过实验证明,该算法极大提高了连接操作的效率.     

校园网格环境下异构数据库的集成与分布式查询

针对校园数据网格的分布式异构数据库环境,提出了一种基于网格服务的异构数据库访问和集成方法。该系统为用户提供一致的虚拟数据视图和分布式数据查询支持。在分析和研究现有分布式数据库查询技术的基础上,介绍了一种适用于网格环境下海量数据的连接操作算法,算法依据分布式数据库的固有并行性,利用数据划分来提高查询的并行处理程度,以改进响应时间。理论分析表明,该算法在减少网络通信开销和降低响应时间方面具有较好的性能。     

QJoin：质量驱动的乱序数据流连接处理技术

数据流乱序现象会导致数据流处理结果的丢失,给数据流的分析处理带来了巨大困难。本研究探讨了质量驱动下的乱序数据流连接处理问题,提出一种质量驱动的乱序数据流连接处理技术(QJoin)。QJoin采用缓冲存储技术和对称连接策略,实现并确保对流元组进行即时分析处理,从而降低了流元组处理的平均等待时间。同时,基于质量驱动的理念,根据临近阶段连接处理过程中收集统计的数据,自适应地调整和优化内存缓存区的大小,从而在满足用户结果质量要求的前提下,降低系统内部历史数据的内存缓存量,尽可能保证迟到元组的连接处理完整性。真实数据集上的实验结果表明,与传统的数据流乱序处理技术MP-K-slack相比,QJoin在满足用户结果质量要求的前提下,确保能够即时地分析处理数据流的流元组,显著降低系统的内存开销。     

分布式流处理系统的时间感知分组算法

随着对实时数据流处理需求的增加,分布式流处理系统的发展也越来越受到关注。大量的倾斜的数据流以及复杂分布式系统的异构性对当前的分布式流处理系统的分组策略提出了挑战。目前已有的分布式流处理分组策略通常关注并行实例之间元组数量的均衡性,而忽视了系统异构性对分组策略造成的影响。该文提出了一种时间感知分组算法,通过对分布式流处理系统存在的网络异构性和处理能力异构性的分析,综合考虑流处理系统中各下游算子实例的处理时间以及上游算子与下游算子之间的通信时间,并根据键值的频率不同制定不同的路由策略,在较小的开销下使系统达到负载均衡。在Apache Flink分布式流处理系统上进行的实验结果表明:时间感知分组算法比已有的分组算法在系统吞吐量上提高了10%,在平均处理延迟上降低了33%。     

数据流系统中的查询处理机制

近年来,一种数据密集型的应用得到了广泛的关注。在这种应用中,数据不再来自于存储在永久介质上的数据库,而是以大量的、连续的、快速的、随时间变化的、无边界的数据流的形式到达。本文论述了当前数据流的产生背景、研究现状并且针对数据流应用中的种种特征,对数据流中的查询处理机制进行了深入讨论,包括查询分类、查询的特点及数据流系统中查询的处理方法。     

数据流连续查询处理技术的研究

数据流查询处理技术的研究是目前数据库研究领域的热点问题.传统的数据库技术不能处理诸如网络监测、传感器网络、股票分析等应用中所生成的新型数据,即数据流.数据流作为一种新的数据形态,不同于传统的静态数据,具有连续快速、短暂易逝、规模宏大和不可预测的特点;其研究核心是在一个远小于数据规模的有限存储空间迅速获得近似查询结果.综述关于数据流查询处理技术的研究成果,主要介绍数据流模型、查询的特征、数据流近似查询操作算法的实现以及数据流系统中的查询处理方法.     

LCDJ:面向内存集群计算的局部感知连接算法

等值连接是数据库系统中最为重要的操作之一,哈希连接在处理等值连接时,表现出较高的性能.在分布式内存数据库系统中,数据即已分布式地存储于多个节点上,哈希连接通常情况需要将参与连接的两个关系表在连接属性上按照相同的哈希函数进行数据重分区,从而保证连接属性值相同的元组被传输到同一个节点上进行本地连接操作.由于内存数据处理速率远远高于网络的数据传输速率,因此数据重分区占据了连接算法的绝大部分时间,成为分布式内存数据库系统中等值连接操作的性能瓶颈.本文提出了一种新颖的分布式内存数据库环境下的等值连接算法LCDJ(Locality Conscious Distributed Join),在充分利用高效的内存计算的同时尽量减少网络数据传输量.算法首先对每个表连接属性的数据分布进行精确的统计,并结合并行度和计算负载均衡因素,进而建立代价模型来衡量不同调度策略下的时间开销,并求出最优的调度策略.LCDJ实现于基于内存的分布式原型系统Claims中.实验结果表明,本文所提算法有效地降低了网络传输代价,大幅度减少了响应时间,比起当前流行的Hive和Shark等系统有明显的性能提升.     

RFID数据流管理关键技术

新一代传感器和RFID(无线射频识别)技术为人们提供了强大的感知、理解并管理世界的能力,同时RFID数据具有不确定性、冗余性、蕴含时空性、需要在线处理等特点,也为数据管理提出了许多挑战,本文回顾了RFID数据管理的研究发展现状,从数据流连续查询、物化视图推导规则、复杂事件处理等角度分析了RFID数据管理涉及到的几种关键技术,最后介绍一种数据流驱动的RFID复杂事件处理系统(CodEye Event Processor)的设计思想,将RFID事件查询设计成复杂连续查询,能够有效捕捉并处理复杂RFID事件.