关系数据库不可用空值的查询与处理

2017-10-26 12:34郭咏科毛宇光向日锋
计算技术与自动化 2017年3期

郭咏科 毛宇光 向日锋

摘要:在流式大数据系统测试过程中,测试数据集越真实,得到的测试报告越可信。然而真实大量的流式数据并不容易获取,因此需要一种方法能够产生大量符合真实场景特征的数据。这些特征包括数据属性相关性、数据时序相关性、数据流的流速变化等等。在流式大数据环境下,数据的时序相关性与流速变化尤为重要。本文提出了一种适用于流式大数据系统测试的数据生成方法,以真实场景的数据集作为种子数据,对种子数据采用最大互信息系数描述数据属性间的相关性,改进了Prim算法对属性列集合进行分组,在尽量保证属性列强相关的前提下提高生成效率,接着提出了一种时序模型选择策略,保证生成的数据在时序上的相关性,提出了双层滑动窗口的方法控制流数据输出速度。最后,本文比较了提出的方法与其他流数据生成方法的生成效率。

关键词:流式大数据生成;非线性相关性;时序相关性;流速控制

中图分类号:TP311文献标识码:A

Abstract:In the process of streaming big data system testing,the more real test data sets,the more reliable the test report can be obtained.However,real data is not easy to obtain,so a method is needed to generate a large number of data with real scenario features.Thesefeatures include data attribute correlation,data temporal sequence correlation and the rates of streaming data.In the streaming big data environment,the data temporal sequence correlation and the rates of streaming dataare especially important.In this paper,we present amethod forstreaming big data generation,using real scenario streaming data as the seed data,using the maximum mutual information coefficient to describe the correlation between the data attributes,putting forward acprim algorithm to partition the attribute group,improve efficiency in the premise of ensuring that the attributes arestrong related.according to the different characteristics of each attribute group,using different temporal sequence model to ensure that the data generated hold temporal sequence correlation,a double sliding window method is proposed to control thedegree of parallelism and the output speed of the streaming data.Finally,this paper compares the proposed method with other streaming data generation methods for generating efficiency.

Key words:streaming data generation;nonlinear correlation;temporal sequence correlation;velocity control

1簡介

流式大数据广泛存在于社交网络、金融服务等领域,越来越多的流式大数据处理系统应运而生,为了保证此类系统的性能满足设计需求,需要对其进行相应的性能测试。Yahoo开发了云服务测试套件YCSB,用来对云服务进行基础测试,目标是进行云数据服务系统的性能比较[1];Ruirui Lu等人提出了测试套件StreamBench,描绘了流式系统的性能测试框架,比较全面地对流式大数据系统进行了测评[2];詹剑锋等人提出了大数据测试基准BigDataBench,其基准测试程序覆盖了多个大数据应用领域[3]。然而诸如此类的测试套件,重点关注的是负载的全面性,在输入数据集的选择问题上考虑得不够全面。进行流式大数据系统的测试,输入到系统的数据与真实场景下的数据特征越吻合,得到的测试结果越准确,因此需要一种能够保持数据真实特征的大数据仿真生成方法。

在流数据和流数据库仿真生成方面近年来有很多丰硕成果,Eric等人提出了DBMS测试套件MyBenchmark以及数据生成工具[4],把一组查询操作作为输入,能够生成数据库实例,同时用户还能控制生成负载的特征。由于保持了大量数据依赖、数据分布等内层特征,数据生成的速度不是很高。Joseph等人提出了一种合成数据形式化的描述语言SDDL[5],能够并行生成具有某些约束和简单用户定义函数的数据,但是没有考虑到数据的分布特征,不能生成满足例如高斯分布等复杂概率分布的数据。Kenneth等人将数据表的生成转换成图的遍历过程[6],能够保证比较好的属性依赖和概率分布,由于重点保持属性依赖,使得数据的并行化程度不高,在生成数据表规模比较庞大或者依赖关系比较复杂的时候生成速度比较慢。华东师范大学的顾伶等人提出了通用数据生成框架PSUG,使用标准均方关联度量计算属性间相关性,使用隐式狄利克雷模型模拟数据流前后的主题相关性,开发了数据生成工具Chronos,能够生成满足流数据库测试套件的数据[7][8],但是Chronos使用的标准关联度是一个线性的相关性度量指标,对于具有非线性关系的属性关联不能准确地描述,同时对于不存在主题的纯数字型数据,该生成方法无法满足生成的数据在时序上的相关性。流式大数据的属性依赖关系以及其固有流式特征都与传统的数据库和流数据库有所不同。钱宇华等人研究了大数据环境下的数据相关性度量指标的优缺点[9][10],同时指出在大数据环境下,数据之间的相关性一般都是非线性的。Reshef等人提出了最大互信息系数,证明了该度量指标对非线性相关性能进行比较准确的刻画[11]。endprint

本文在此基础上提出一种适用于流式大数据系统测试的数据生成方法,在尽可能保证数据属性相关性的同时,加入流式数据的时序性特征,同时还能控制流数据的流速。本文最后也进行了效率方面的检测,证明了该数据生成方法的有效性。

本文的结构如下:第2节介绍数据生成方法的整体框架,第3节介绍参数设置方法,第4节介绍相关性控制方法,第5节介绍流速控制方法,第6节介绍实验。

2框架结构概述

本节对数据生成方法的框架进行简要的描述,如图1所示,整个框架分为3个部分:参数设置模块、相关性控制模块、流速控制模块。

参数设置模块以种子数据作为输入,提取属性列的信息,生成数据描述文件,定义参数对后续生成的数据的特征进行校正,不同的参数组合可以代表不同的应用场景下数据的不同特点。相关性控制模块任务是计算數据属性间的相关性系数,对属性集合进行划分,划分后得到的属性组拥有类似高内聚低耦合的特征。提出时序模型选择策略对于每个属性组进行时序相关性的分析,得出回归方程用作数据生成。流速控制模块定义内层滑动窗口保证并行生成的数据在整个时间序上的相关性,定义外层滑动窗口控制数据流输出速率。

3参数设置

本节介绍数据生成方法的参数设置。本文方法定义了四个参数:最大相关性忽略系数c;时序相关回归阶数r;时间分段T;数据流速S。

最大相关性忽略系数c是在数据属性组划分阶段,终止搜索下一个属性所参考的变量。取值范围在0.2~0.4,属性相关性在0.2以下说明属性之间相关性极低,在0.2~0.4之间相关性较低。该参数越小,允许忽略的相关性越少,因此分解出的属性组越少,并行化程度越低;相反,分解出的属性组越多,并行化程度越高。对于仅仅需要进行压力或者负载测试的系统来说,该参数设置大一些,忽略数据属性之间一些不必要的相关性;对于某些具备数据挖掘功能的系统来说,该参数应设置小一些,尽量保存数据属性之间的相关性,使得数据挖掘性能能够得到展现。

时序相关回归阶数r是在进行数据时序相关性分析阶段,向前参考数据的个数,取值范围在2~4。该参数越小,时序相关性越弱,但回归公式越简单,数据生成效率越高;相反,考虑的数据时序相关性越强,回归公式越复杂,数据生成效率越低。对于类似股票流数据的场景,该参数应设置高一些,使得生成的数据与之前数据的关系尽可能精准一些;而对于类似车载物联网系统来说,其前后的流数据相关性不是特别重要,该参数可以设置低一点。

时间分段T描述的就是某一个周期下不同数据流速的段数以及时长,是一个自然数的集合,即T={t1,t2,t3……}。该参数元素个数越小,流速越平稳,数据流越稳定;相反,流速变化越频繁,数据流波动越大。例如银行系统,每天早7点之前和晚7点之后,系统负载较小,早7点到11点和下午2点到7点为高峰,负载较大,则可以将整个数据流分为4段,即t1=12(晚7点到第二天早7点);t2=4(早7点到早11点);t2=3(早11点到下午2点);t4=5(下午2点到下午7点)。

数据流速S描述的是时间分段T上的数据流速,S同样是一个自然数的集合,元素个数与T一致。2012年的新年新浪微博的单秒最大数据条数达到了4万条, 2016年11月11日,天猫购物节支付宝的交易峰值也只有16万条数据/秒,根据互联网用户每年25%的增长趋势,本文将其取值范围设置在0~200000条数据/秒。S中元素的值越大,数据输出得越快。假设s1代表晚上5点之前的流速,s2代表晚上7点之后的流速,则对于上述银行系统,朝九晚五的特点使得系统的数据流速在晚上7点之后明显小于5点之前(s1s2);相反对于微博系统,上班族下班,数据流速在晚上7点之后可能又远远大于晚上5点之前(s1s2)。

4相关性控制

本节介绍数据相关性控制方法,对于保证生成的数据符合真实数据特征具有重要作用。首先分析其两两之间的最大互信息相关系数(MIC),得到相关系数图,接着改进了Prim算法进行属性列集合的划分,使得保持数据属性列强相关的同时增加并行化来增加数据生成效率,最后给出一种时序模型选择策略,对不同特征的属性列集合采取不同的时序模型进行拟合,得到回归方程或方程组用作后续数据生成。

41属性相关性

属性相关性是指拥有多个属性的一批数据,其属性之间的关联程度。在大数据相关分析中,MIC可以度量任何函数形式的相关性,具有通用性。同时,如果两组不同形式、拥有相同MIC取值的数据,当给它们同等程度的噪音,MIC的取值仍然保持相等。流式大数据环境下,对数据的生成速度有要求,生成算法计算的复杂度越低越好,同时大数据复杂多样、噪声数据很多,算法的鲁棒性同样重要。表1是MIC与其他相关性度量指标的对比,可以看出MIC更加适合流式大数据的环境。

由于MIC具有对称性,即MIC(A,B) = MIC(B,A),因此对于具有N个属性的数据集,计算后能够得到一个N个节点的带权无向完全图,图中的边的权值代表两个属性列之间的相关系数。当两个属性列之间的相关性比较小时,应该将它们单独生成,而相关性比较大的几个属性列必须作为整体一起生成,所以可以对属性列相关系数图进行划分,把相关性大的属性列划到同一组,以提高并行度,进而提高数据生成的整体效率。

图的最小生成树算法以图中连线权值为参考,生成一条包含所有节点的序列,由于本文进行属性列分组时也需要参考连线权值,所以可以通过加入终止条件的办法,让算法提前结束,获得序列的一条子序列,子序列中包含的节点就被分为同组。普利姆算法(Prim算法)和克鲁斯卡尔算法(Kruskal算法),是最基本的两种图最小生成树算法,分别适用于稠密图和稀疏图。带权无向完全图属于稠密图,因此本文对Prim算法进行改进,提出一种附加终止条件的Prim算法——cPrim算法划分属性列集合。endprint

cPrim算法思想:从任意一个顶点出发,寻找与其相连的边集合中权值最大的边,如果该边的权值仍然小于等于最大相关性忽略系数c,则直接将该节点单独分为一组;如果不小于c,找出最大权值边对应的节点,将该节点纳入出发节点集合,再从出发节点集合出发寻找最大权值的边,不断循环,直到所有节点被分成了若干组。假定最大相关性忽略系数c为0.2,下面以图2为例,简单介绍算法步骤。

图2(a)为划分之前的关联关系图。随机从一个节点出发(例如1号节点),与其相连的边上的权值为0.1、0.1、0.2,均小于等于c,故直接将1号节点单独分为一组,如图2(b)所示。

再从剩下的2,3,4号节点中随机选取一个(例如3号节点),与其相连边最大权值为0.5,大于c,那么将4号节点纳入{3},如图2(c)所示。

继续寻找从3,4號节点出发的最大权值的边,是2号与4号节点的连接边,权值为0.3,大于0.2,将2号节点纳入{3,4}。整个属性集合被分成了2组:{1},{2,3,4},如图2(d)所示。

假定的最大相关性忽略系数c为0.4,根据算法可以将属性集合分为3组:{1},{2},{3,4}。

算法伪代码:

42时序相关性

数据的时序相关性是指带有时间戳的一组数据,其前后数据属性值的关联关系。在流式大数据环境下,数据的时序性非常关键,缺少了时序的流式数据就丧失了数据挖掘特别是趋势预测的意义。本小节提出一种时序模型选择策略,针对不同特点的属性组采用不同的时序模型进行回归方程的拟合。

属性分组划分完之后,首先将属性组分为2类:单属性组和多属性组。

对于单属性组,首先判断其是否平稳,即序列是否围绕某个固定值上下波动或者序列的标准差是否保持不变。若平稳,则采用经典的自回归移动平均(ARMA)模型进行拟合,形式为:

Xt=Φ1Xt-1+…+ΦpXt-p+εt-…-θqεq(5)

其中Xt是需要估计的下一个值,Xt-1~Xt-p是回归参考的属性数据,εt是当前噪声,εt-1~εt-p是回归参考的噪声数据,Φ1~Φp以及θ1~θq为回归参考数据的参数。

若非平稳,则采用自回归滑动平均(ARIMA)模型进行拟合。ARIMA模型是针对非平稳的单变量时间序列的,其基本思想是将一个非平稳的时间序列通过一次或者多次差分转换成平稳序列再进行拟合。一般来说,一阶差分可以使有线性趋势的序列变得平稳;二阶差分可以使有曲线趋势的序列变得平稳。ARIMA模型形式为:

其中Δd是指经过了d阶差分,其他参数同ARMA模型的参数。

对于多属性组,采用自向量回归(VAR)模型进行拟合。VAR模型针对的是多变量的时间序列,拟合之前需要观察数据VAR模型根模散点是否均落在单位圆内来的判断序列是否平稳,若不平稳,首先差分成平稳序列再进行拟合,模型形式为:

Xt=Φ1Xt-1+…+ΦpXt-p+βYt+εt(7)

其中Xt~Xt-p为内生变量向量,Yt是外生变量向量,改变量是指除了参与,εt是当前噪声向量,Φ1~Φp以及β为回归参考数据的参数。对所有属性组进行拟合得到回归方程,用作数据生成。

5流速控制

本节描述一种双层滑动窗口的方法,控制流数据流速。滑动窗口的概念最先出现在计算机网络中,通讯双方约定一个能够接受的窗口大小,每次只发送和接收指定窗口大小的内容,防止数据溢出。

为了保证流数据整体的时序性,必须在增加并行度时进行控制,定义内层滑动窗口,窗口大小为时序相关回归阶数r,维护着最新的r个数据,如图3所示,有2个线程分别生成属性a和属性b,c。

当属性组需要增加并行化时,不直接通过随机数生成器生成种子,而是将窗口内的r个数据当作新线程的种子数据,如图4所示。因为回归方程带有一定的噪声,因此在当前窗口基础上生成的后续数据和以这批数据作为新种子生成的数据不会完全一样,同时保证了一个属性组在整个时间序列上的相关性。

为了控制数据流流速,定义外层滑动窗口,外层窗口大小为当前时间段T上的流速S,输出数据时,以恒定的速率输出窗口内数据,需要流速加大时,就增大窗口大小;需要流速减小时,就减小窗口大小。如图5所示,T1阶段流速为500条/秒,T2阶段流速为5000条/秒。

6实验

本节介绍实验,验证提出的方法生成的数据满足预设的速率要求;数据属性之间的相关性仍然保持;最终生成的数据与种子数据的分布基本一致。此外,实验还比较了本文方法与PSUG[7]和文献[13]提出方法的数据生成效率。

61实验设置

实验配置为:4核酷睿i7处理器,主频3.4 GHz,内存16 GB,硬盘存储1 TB。

初始参数设置:最大相关性忽略系数c为0.2,时序相关回归阶数r为2,运行总时间30分钟,分为3段,即t1=10、t2=10、tz=10,流速分别为500条/秒,10000条/秒,50000条/秒,即s1=500、s2=10000、sz=50000,3个时间段总计分别生成30W,600W,3000W条数据。实验的种子数据为10000条带有时间戳的新浪微博数据,经过清洗之后每条数据包含“微博文本长度”,“转发数”,“评论数”,“点赞数”4个属性。

62实验结果

图7为生成的数据分布与种子数据分布的对比,其中生成数据的分布图是由生成的数据随机开始位置10000条连续的记录产生的,由于无法确定提取的数据流处在整个数据流的位置,考察每个值出现的位置没有意义,比较每个数据段上的数据量分布即可,可以看到生成的数据比较符合种子数据的数据分布,图7只列出了“文本长度”和“转发数”的数据分布对比,“评论数”和“点赞数”与“转发数”类似。endprint

圖8为本文方法与其他方法的效率对比,与PSUG相比,两种方法在属性相关性分析方法策略上有所不同,但数据生成的速率本文方法大约为PSUG的2倍;与不保证时序相关的流数据表生成方法相比,本文提出的方法加入了数据时序性的特征,生成速度大约下降了20%,速度损失可以接受。

7总结和展望

本文提出了一种适用于流式大数据系统测试的数据生成方法,采用了更加适用于流式大数据系统的非线性相关系数MIC来描述数据属性之间的相关关系,改进了Prim算法合理地划分属性集合;加入流式数据重要的时序性特征,尽可能保留了前后数据之间的相关性;提出了双层滑动窗口的概念,能更好地控制数据输出的速率。

本文的不足之处在于:自动化程度不高,不能运行时动态添加属性;需要手动定义变量;数据时序相关性分析的参数需要手动赋值;整个数据流的流速变化比较突然,实际的应用系统中的数据流速变化应该比较平滑;不能支持非结构化类型的数据生成。

在未来的工作中,我们希望能够将数据生成的预处理过程进一步自动化,挖掘数据流的流速变化规律,支持生成更多数据类型的数据。

参考文献

[1]COOPER B F,SILBERSTEIN A.Benchmarking Cloud Serving Systems with YCSB[C].international IEEE SOCC,2010.

[2]LU Ruirui,WU Gang,XIE Bin.StreamBench:Towards Benchmarking Modern Distributed Stream Computing Frameworks[C].IEEE/ACM 7th International Conference on Utility and Cloud Computing.2014.

[3]ZHAN Jianfeng,GAO Wanling,WANG Lei.Big Data Bench:An Opensource Big Data Benchmark Suite[J].Chinese Journal Of Computers,2016,39(1):196-211.

[4]LO Eric,CHENG Nick.Generating Databases for Query Workloads[J].VLDB.2010,3(1),848-855.

[5]HOAG J E,THOMPSON C W.A parallel generalpurpose synthetic data generator[C].SIGMOD.2007,36(1),19-24.

[6]HOUKJAR K,TORP K,WID R.Simple and realistic data generation[C].VLDB.2006,1243-1246.

[7]GU Ling,ZHOU Minqi.A Scalable Framework for Universal Data Generation in Parallel[C].6th TPCTC.2014.

[8]GU Ling,ZHOU Minqi.Chronos:An Elastic Parallel Framework for Stream Benchmark Generation and Simulation[C],IEEE 31st International Conference on Data Engineering.2015.

[9]LIANG Jiye,FENG Chenjiao,SONG Peng.A Survey on Correlation Analysis of Big Data[J].ChineseJournal Of Computers,2016,39(1),1-18.

[10]QIAN Yuhua,CHENG Honghong,LIANG Xinyan.Review for Association Measures in Big Data[J].Journal of Data Acquisition and Processing,2015,30(6),1147-1159.

[11]RESHEF D N,RESHEF Y A,FINUCANE H K,et al.Grossman.Detecting Novel Associations in Large Data Sets[C].Science,2011,334(10),1518-1524.

[12]HU Bo,GUO Li.Practical statistical analysis method and technology[M].Beijing:Chemical Industry Press,2013.

[13]ARASU A,KAUSHIK R,LI Jian.Data Generation using Declarative Constraints[J].Acm Sigmod International Conference on Management of Data,2011,685-696.endprint