一种云环境下的大数据快速聚合查询方法

摘要

本发明公开了一种云环境下的大数据快速聚合查询方法，包括步骤一：问题的定义和基本概念；步骤二：数据划分；步骤三：基于MapReduce的大数据聚合查询，假设数据集为T，数据集的势(cardinality)为m，则T＝{ti:1≤i≤m}；数据的维度Dim(T)＝d，因此，每个ti可以表示成{t1(d)，t2(d)，…，ti(d)}，且所有的属性均为数值型；对于聚合问题而言，查询函数f通常是一个单调递增函数(increasingly monotone function)；即，如果对1≤n≤d，ti(n)≤tj(n)，则f(ti)≤f(tj)。本发明的方法能够大幅减少计算量，提高计算效率，同时，本发明的方法也有较好的扩展性。

主权项

一种云环境下的大数据快速聚合查询方法，其特征在于：包括步骤一：问题的定义和基本概念；步骤二：数据划分；步骤三：基于MapReduce的大数据聚合查询；步骤一：假设数据集为T，数据集的势(cardinality)为m，则T＝{ti:1≤i≤m}；数据的维度Dim(T)＝d，因此，每个ti可以表示成{t1(d)，t2(d)，…，ti(d)}，且所有的属性均为数值型；对于聚合问题而言，查询函数f通常是一个单调递增函数(increasingly monotone function)；即，如果对1≤n≤d，ti(n)≤tj(n)，则f(ti)≤f(tj)；最常用的单调函数是加权和(weighted sum)，本文亦采用加权和进行相关的计算；假设权值向量w＝(W₁，W₂，…，W_n)，则此时的f(ti)值越大，代表排序越高；在此定义下的聚合查询就是返回最大的前k个值；不失一般性，本文假设w_i∈^[0，1]，∑w_i＝1且这表明，权值向量中允许有分量为0，但不能全为0，表1对上述符号进行了归纳；为了简化问题以及阐述方便，本发明作如下合理的假设:1)数据集相对固定，或者数据的更新速度相对于整个数据集而言，可以在一定时间段内忽略不计，很多实际的应用场景符合这种假设，例如，淘宝网的商品数据虽然时刻在更新，但是相对于其整个庞大的商品基数而言，可以认为在某个固定时间内(比如1周)变化不大；对于变化频繁的数据集，比如流数据，本发明的方法并不适用；2)数据分布均匀，在数据量足够大的情况下，很多场景的数据基本上符合这个要求；3)任意记录在其任意维的值均不为负值，现实中的应用基本符合该假设，例如，对某饭店或某商品评分，每项分值肯定大于等于0；即使不符合，也可 以通过简单的数据转换，将其数据范围转换到非负区间；4)所使用的服务器数量大致和数据量保持一个合理的比例，数据过多或过少，可以分别通过增加或减少服务器来实现负载平衡；步骤二：在云环境的条件下，数据划分的基本原则是，尽可能地将数据均匀地划分到各个服务器上；这种均匀不仅体现在数据量的均匀上，更重要的是面对特定应用时，这种划分能够尽可能地保证每个服务器上的数据对最后结果均有贡献；在以MapReduce为数据处理框架的云环境下，垂直划分方式不太适合，因为每个子集只有原数据集的部分属性，这样在每次计算时需要访问所有子集才能得到一个完整的加权值，而在MapReduce中，slave节点之间一般不会进行信息交换；考虑到MapReduce的这种特点，本文采用水平划分方式；进一步地，在聚合领域具有代表性的水平划分方式有如下几种:随机划分、基于网格、基于角度和基于超平面；假设将记录的每个属性作为一个维度，则n维聚合问题中的每条记录等价于n维空间的一个数据点(下文中，数据点和记录表示同一概念，可以混用，不再解释)；为了便于理解这几种数据划分方式，以二维数据(即，每条记录有两个属性)为代表，具体的划分方法如图3‑图6所示；图3是随机数据划分方式，对于新的数据点，通过某种方式，比如round‑robin，将数据点随机地分配到某个服务器；图4是网格划分，这种方法将整个数据空间划分成若干个网格，落入某个网格中的数据点则分配到相对应的服务器；图5描述了二维情况下基于角度的数据划分，这种方法首先将笛卡尔坐标系的数据点通过转换规则映射到超球坐标系(hyperspherical coordinate)，在此基础上，对每个维度的数据进行划分，最终得到结果；图6是基于超平面的划分，该方法的本质是将空间数据映射到某个特定的超平面(在二维空间，超平面等价于一个直线)，图例中选择的超平面为直线x+y＝1，具体的映射规则是，将通过数据点和原点的直线与超平面的交点作为该数据 点在超平面上的映射点；完成映射之后，通过对各个数据维度进行划分来完成整个数据空间的划分；该方法可以很容易地推广到更高维空间；基于角度和基于超平面的划分都首先要对数据进行转换映射，区别在于:基于角度的划分数据坐标系发生改变，而基于超平面的划分还是在相同的坐标系；从计算复杂度来看，随机划分方式最为简单，而基于角度的划分方式最为复杂；针对聚合问题，随机划分和基于网格的划分效率不高，原因在于:虽然数据被划分到多个服务器上，但是每个服务器上计算的聚合值对最终聚合值的贡献是不同的；以加权和最大为聚合的衡量标准，则在图3、图4所示的随机划分和网格划分中，靠近右上角分区中的数据更有可能成为最终的全局聚合值，而左下角的分区数据极可能毫无贡献；这必然会造成计算资源的浪费和计算效率的低下；最理想的状态是:每个数据分区都能计算出部分的全局聚合值，这样就能够充分发挥系统的并行特性且充分利用计算资源；因此，基于角度的划分和基于超平面的划分是可能的候选方法，这两种数据划分方式最早都是在分布式Skyline计算中引入的；由于具有一些内在的联系，Skyline的计算在很大程度上和聚合有共通之处；但是考虑到MapReduce的特性，直接使用这两种方法都不太合适，主要原因在于，直接使用这两种划分方式对于后期的数据删选而言不够高效；因此，本发明提出一种同时考虑角度和距离的划分方式；进行基于角度的划分，首先需要将欧式空间的数据点坐标转化至超球坐标；具体转换规则如下；假设数据点的坐标t＝[t(1)，t(2)，…，t(d)]，则其相对应的超球坐标由一个径向坐标r和d‑1个角度坐标φ₁，φ₂，…，φ_d‑1构成，其中考虑到第0.1节中的假设3)，则0≤φ_i≤π/2，对为了便于理解，接下来以二维空间为例解释本文的划分方法，但具体的方法可以扩展到任意维；图7是在假设有3台服务器的前提下，利用本文基于角度和距离的数据划分方式对整个数据空间进行的划分；具体步骤如下:1.依据公式(1)对整个数据空间的数据点进行数据转换，从笛卡尔坐标系转换至超球坐标；2.采用类似网格划分的方式对角度进行划分；此步骤划分仅考虑角度坐标，不考虑径向坐标；网格划分技术相对成熟，有很多可借鉴的划分方式，本文采用较易实现的等分划分方式，其中，等分的数量等于服务器的数量；例如在图7中，根据角度坐标将整个平面首先分成了3个部分，其中，3.经过步骤2，每个角度区间都占据了数据空间的一个部分，由于第2.1节中的假设2)，我们可以认为每个角度区间所占有的数据量大致相同；在此基础上，利用径向坐标r对每个区间的数据作进一步的划分；此步骤的划分区间数量可以根据实际需求进行改变，但需保证以下两点:1)在对r进行划分时粒度不能过细，至少保证二次划分的子区间包含一个块的数据量；由于第2.1节假设4)的保证，每个服务器上会有相对充足的数据量进行划分；2)二次划分的子区间面积相等，即图7中的区间1‑区间9的面积应当相等；这主要是为了保证每个子区间的数据量大致相等；以上方法是在二维空间中进行的，推广到三维空间则是对1/8的球体进行划分，更高维的话没有直观的几何图形，但划分方法一致，只是计算复杂度有所增加；在云环境下，相对原始的基于角度的划分，本文方法有一定的优势，详细分析在下文中会加以阐述；步骤三：1)数据筛选：在云环境下，加速聚合计算最核心的方法有两种:(1)将计算过程并行化，本文通过MapReduce来实现；(2)减少计算所需的数据量；下面将结合第0.2节中提到的数据划分方法来阐述本文数据筛选的方法；对于方法2，需要思考的关键性问题是:在加权和的计算方式下，对于一个特定的聚合查询，如果从几何角度考虑，究竟空间中满足何种性质的数据点最终会成为聚合点？为了解释方便，同样以二维空间的数据点为例；假设现在有若干个数据点，这些点在二维坐标系中的位置如图8所示；如果现在的权值向量w＝(0.5，0.5)，那么对于所有记录而言，0.5x+0.5y的值决定了其最终的排序；如果将权值向量也看作空间中的一个点(称为权值点)，那么过原点和权值点可以构成一条直线(图8中的直线y＝x)；此时，聚合查询有如下性质：性质0：假设权值向量w＝(w₁，w₂，…，w_n)，空间中有限数据点的集合 t＝{t₁，t₂，…，t_n}，则对集合t中任意点t_x，计算可以得到集合L＝{L₁，L₂，…，L_n}；如果L中，值小于或等于L_x的点有k个，则点t_x在权值向量为w、以加权和为查询函数的聚合查询中的最终排序为n‑k；性质1:在聚合查询中，如果以加权和作为查询函数，则数据点在空间中的排序由其在通过原点和权值点构成的直线上的投影位置所决定；可以直观地理解为:数据点在直线上的投影位置距离原点越远，其排序越高；或者说投影长度越长，排序越高；空间中点t到过原点和权值点的直线的投影长，根据L值很容易判断点之间的排序关系；假设现在需要查询如图8所示的数据空间中的Top‑3点，则这些点为t₁，t₂，t₃，且排序关系是t₁>t₂>t₀；本发明在角度之外加入距离的划分因素，最大的好处就是能够确定每个划分区间的距离范围，该距离范围可以用于数据筛选；如图9所示，在确定数据划分和权值向量之后，通过各维度的数值区间和角度区间信息，可以计算出分区3所对应的投影长度区间为(L1，L2)，也就是说，区间3中所有点的投影长度均大于等于L1，小于等于L0.其他区间均可得到其相对应的投影长度区间；但在面对不同的权重值时，区间内可能取到最小和最大投影值的点会发生变动，导致计算复杂度增加；为了简化计算，本文提出松弛投影范围的概念；利用此概念可以大大减少数据筛选的计算量；可以观察到，按照本文的划分方法，每个子区间都可以被一个最小外接超立方体所包围；无论权值向量如何变化，该立方体具有最小和最大投影值的点始终是[t_min(1)，t_min(2)，…，t_min(d)]和[t_max(1)，t_max(2)，…，t_max(d)]；图10展示了二维空间中这种计算方式(二维空间中的超立方体退化为矩形)，图中虚线部分是相对应区间的最小外接超立方体，区间1‑区间3对应的最小和最大投影值点均在图中标示出来；从图中还可以发现，此时的投影长度区间实际上是真实投影长度区间的一个超集，区间范围有所扩大；但是，这种方法因为最大和最小 投影点固定，在面对不同的权值时，可以非常简单地计算出对应的区间，且对于实际的筛选效果影响不是很大；数据划分完成之后，根据区间的距离信息可以确定每个区间在其相对应服务器上的排序(根据与原点间距离，由远到近)，同时也可以确定松弛投影范围概念下的最小和最大投影点；将这些元数据信息以表的形式保存在master节点上，表2是一个实例；表2中的每格代表相应区间的元数据，最前面数字表示区间号，例如第1格中的0区间号之后的两组数据分别表示松弛投影范围概念下的最小和最大投影点坐标；处于表中同一行，代表其位于同一个距离区间，例如第1行表示最外一层的区间3、区间6、区间9，以此类推；假设总的数据点为m个，总的划分区间是n个，因为在划分时保证每个划分区间的面积相等且有第0.1节中提及的假设2)，可以认为每个区间的数据点大致相等，为m/n个；那么，通过比较m/n与k值，就可以确定最终计算所需区间；算法1描述了利用表2中元数据进行数据筛选的过程；算法1：输入:k和w；输出:可用于MapReduce使用的数据分区1.p＝K/(m/n)；/*p是K/(m/n)的边界*/2.扫描元数据，把第1行存入变量p；3.for i＝1to p；4.f.or j＝1to q；/*q是总的列数*/5.Vmin[i][j]＝tmin w/|w|；/*最小被释放的投影值*/6.Vmax[i][j]＝tmax w/|w|；/*最大的被释放的投影值*/7.end for；8.对比所有的数据对(Vmin[i][j]，Vmax[i][j])；9.if Vmax[i][s]≤Vmin[i][t]；10.删除数据分区s；11.else；12.输出s；13.end for；(1)如果m/n>k，则可以保证最终的聚合值只出现在划分中最外侧区间(图9中的区间3、区间6、区间9)，在此基础上，根据表2，对这3个区间作进一步计算；如果3个区间的松弛投影区间均有重叠部分，则3个区间不能进一步筛除，需要全部计算，否则可以进一步筛除；假如权值w＝(0.5，0.5)，则可以利用表2中的数据计算出区间3、区间6、区间9的松弛投影区间分别为；3个区间均互有重叠，因此无法进一步筛除，需要全部进行计算；又假设权值w＝(0，1)，则此时区间3、区间6、区间9相对应的松弛投影区间为；区间3和区间6有重叠，但区间9的最大松弛投影值为，比区间3的最小松弛投影值还要小，区间9可以被进一步筛除；因此，在权值w＝(0，1)的情况下，需要计算的区间仅仅是区间3和区间0；(2)如果k/2≤m/n≤k，则除了最外侧之外，还要加入次外侧区间(图9中的区间2、区间5、区间8)；然后，对区间2、区间5、区间8采用类似步骤1中的方法进一步筛除数据；(3)如果k/3≤m/n≤k/2，则计算所需的区间还要再往内侧增加，以此类推；实际中，m/n的值不光大于k，常常远大于k，例如搜索引擎中的海量数据；而我们最关心的往往只是结果第1页的几十个数据，因此，采用本文的数据划分和筛选方法，一般情况下仅需计算区间3、区间6、区间9所对应区间的block中的数据即可，减少了2/3甚至更高的数据量，大大提高了效率；具体流程计算：从整个过程来看，包括预处理和查询处理两个部分，具体步骤如下:(1)对数据进行预处理，主要是利用上文的方法进行数据划分，最终数据以block形式存入HDFS中；(2)用户提交新的查询，master节点接受参数k和w，利用其上的元数据信息按照算法1的步骤对区间进行筛选，确定参与最终计算的区间号；(3)MapReduce任务只对涉及到的区间进行计算，返回聚合值。