支持非等值连接的分布式数据流处理系统

实时处理的分布式数据流系统在当今大数据时代扮演着越来越重要的角色.其中,连接查询是大数据分析处理中最为重要且开销较大的操作之一.然而,由于现实应用产生的数据普遍存在倾斜分布现象,加之数据流本身的无界性与不可预知性,给在分布式数据流系统上进行连接查询处理提出了严峻的挑战.目前工业界较为主流的数据流系统处理连接查询的通用性较低,没有提供专门针对连接操作的接口;学术界推出的数据流连接查询原型系统虽然提供了接口,但大多面向等值连接,或仅能支持部分theta连接,且存在资源开销大、负载均衡性能低等问题.本文对比分析三种典型数据流系统,将基于Join-Matrix的连接处理技术与Storm系统相结合,设计并实现了通用的、可支持任意连接查询的数据流处理系统.实验展示了本文设计的系统具有更加良好的吞吐量与资源优化表现.     

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

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

空间数据流的无阻塞快速连接算法

为保证持续输出空间数据流的连接结果,提出一种快速的无阻塞连接算法.通过数学统计连接结果来进行建模.给出一种高效的冲洗策略用于稳定网络下的内存管理,设计代价模型作为不稳定网络下的外部连接的策略.实验采用真实数据,实验结果表明本算法在稳定网和不稳定网下都能快速地产生空间连接结果.     

一种基于负载代价的MapReduce等值连接优化算法

MapReduce并行计算模型在大规模分布式数据处理中应用广泛,但该模型不能很好地支持连接操作,特别是面对倾斜数据时,原有的分区算法容易造成处理节点间的负载不均衡。针对这一问题,提出一种基于key代价的负载均衡等值连接算法,对Map端中间结果进行采样,根据采样结果计算每一key值的负载代价,并在此基础上,设计一种动态划分函数,对不同的key值按照负载代价均匀划分到各个计算节点,实现了负载均衡。实验结果表明,在同构集群下,提出的算法在负载均衡方面具有较好的效果.     

跨隐私数据库加密数据等值连接共享协议

针对管理型SaaS(software as a service)中两个租户公平共享隐私数据的问题,提出一种跨隐私数据库加密数据等值连接共享协议.在该协议中:两个租户通过服务提供方(service provider,SP)用可交换加密函数交换某共有属性的全集,实现属性值交集共享;SP用该属性值生成的密钥加密对应元组其他属性值后向对方租户分发;租户用交集生成的密钥解密;组合双方属性交集中等值元素的元组,实现两个租户通过不可信SP公平共享隐私数据.完备性、安全性证明和效率分析结果表明,在半诚实模型下,协议安全可证,满足最少必要信息共享条件,计算代价和通信代价分别是用AGRAWAL协议实现公平共享的57％和75％.     

一种高效的不确定数据流Top-K 查询算法

在传感器网络、RFID等各种应用中会产生大量不确定性数据,有效的Top-K查询处理是不确定性数据管理中一项重要技术。针对已有的Top-K查询没有很好地结合元组的分值和不确定性,在分析不确定性数据模型和可能世界模型的基础上,定义了不确定数据流元组的查询语义。设计并实现了一种有效的Top-K查询算法。该算法按照元组的得分值进行降序排列,概率值最高的前K个元组集合就是Top-K的查询结果,实验结果表明,与CSQ和SCSQ算法相比,更具高效性和实用性。     

基于近似等深柱状图的数据流并行聚集算法

针对数据流并行聚集问题,提出了一种不同于关系数据和时间序列数据处理的并行聚集方法.为解决已经划分出的数据流元组无法再现的特点,提出能够感知数据流变化的采样算法对数据流采样.利用近似等深柱状图技术描述采样数据的分布特征,平均分配数据流量.使用时间聚集森林结构计算时间窗聚集.通过验证采样个数对并行聚集的影响,数据分布对近似划分向量算法性能的影响,测试数据流量与并行聚集加速比的关系,证明本算法能够高效地计算数据流聚集查询.     

一种基于数据流图的软硬件划分背包算法

在软硬件协同设计中,将数据流图作为软硬件划分问题的输入,建立了以数据流图为基础的软硬件划分数学模型.对于规模较大的划分问题,为了满足系统性能,达到功耗和成本最小化,提出了0-1背包分解算法,采用并行求解的方式,排除了绝大多数无最优解的子问题,从而改善了大规模划分问题的求解效率.实验结果表明在大规模问题和硬件约束条件下,该算法能获得行之有效的划分方案.     

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

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

政府办公自动化信息系统数据迁移解决方案

阐述政府办公自动化新旧系统数据迁移的意义,提出一种政府办公自动化信息系统数据迁移解决方案.该方案通过数据库结构分析、数据迁移流程设计和数据迁移实现3个步骤,可以正确、快速地实现政府办公自动化新旧系统的数据迁移,保证数据的完整性.