Flexisample：个性化近似聚合查询系统*

赵 博 左昌麒 房 俊

（1.北方工业大学信息学院 北京 100144）（2.大规模流数据集成与分析技术北京市重点实验室 北京 100144）

1 引言

当前，随着物联网的飞速发展，多维时序数据不断产生，以电能质量大数据分析系统中的电能质量数据为例［1］，其部署的监测点每隔3s采集2550个指标数据，目前部署了超1万的监测点，基于上述海量数据的挖掘分析对于电能质量治理具有重要意义。

聚合查询是最为常见的数据统计与分析方法之一。在面对海量时序数据时，聚合查询性能延迟较大，往往不能满足业务需求。近似查询牺牲一定查询精度来换取更快速的查询结果，近些年来在研究领域获得了较多关注。近似查询可以总结为如下公式：

从全量数据集x通过一定的方法获取到用于近似计算的数据集xi。为了达到一定的精确度，减小误差，聚合查询函数AGG需要做针对性的修改，修改后的聚合函数记为AGG′。近似聚合查询方法主要有采样技术［3］，直方图，小波变换［4］，草图［5］等方法，其中采样技术是大规模聚合查询中的一种普适方法［6］，大量聚合查询工作集中在基于采样的近似聚合查询优化上。

现有研究集中在方法研究，对近似查询服务系统的实现工作相对较少，且实现系统多针对某一类型数据的特殊优化设计，用户在生产生活中迫切需要通用的支持个性化查询的近似查询服务系统来有效降低查询时延。个性化的查询包含两个方面，其一是查询请求的个性化，业务人员的查询请求多以SQL脚本的形式提出，如表1所示是电能质量聚合查询的示例，查询请求的个性化要求系统能够快速的对请求进行解析重写等操作；其二是查询时间的个性化，不同的业务人员可以承受不同的响应时间和查询精度，为此系统需要满足业务人员一定范围内的时间约束。

表1 多维时序数据聚合查询实例

针对上述问题，本文设计并实现了一个个性化近似聚合查询系统Flexisample（Flexiable Sampling），基于分层采样技术对样本进行了结构设计，运用数据项分层与样本替换策略实现了基于数据流的样本增量维护工作，并且通过对查询请求的解析实现了系统的查询请求个性化，使用维护多份物理样本的方法来满足查询时间个性化。

2 相关工作

聚合查询目的是帮助人们理解一段时间内数据集的变化［7］。现有的聚合查询处理优化方法按照返回结果的准确程度可分为精确查询和近似查询两类。

精确查询方面，现有研究主要集中在并行计算框架与索引优化方向，如Spark SQL［8］利用并行计算框架提升计算能力，有良好的数据量和灵活性支持，作者考虑了用户的使用习惯，对ad-hoc、reporting、iterative等类型的查询需求提供了SQL查询接口，将SQL语句转换为逻辑查询计划并对其进行优化调整，最终转化为物理查询计划提交给Spark执行。Spark SQL基于Hive对个性化查询提供了支持，但对查询时延没有约束，可以通过结合近似查询进一步降低查询时延。文献［9］采用分布式计算框架和聚合管道与索引结合的方式提升计算效率，虽然通过优化并行计算获取精确聚合查询结果的方式已经很大程度上降低查询时延，达到一定效果，但查询过程中依旧存在大量的磁盘IO和计算，且并不能对个性化的时间约束做出反应，查询时延对比近似查询依旧偏高。

近似查询方面，文献［10］中提出了增量式的样本扩容与误差估计方法，这种方法可以快速地获取查询结果，但在针对稀疏数据时效果并不理想，且样本在时间维度上的覆盖范围相对固定，实时在线聚合时在时间维度上无法满足个性化查询需求。研究［11］对在线聚集方法进行了优化，提出了基于内容的数据块划分，索引以及放置策略。Sameer［16］等基于分布式采样提出了BlinkDB近似查询处理系统，其使用大规模并行查询引擎，支持交互式SQL查询，但BlinkDB建立在Shark和Spark之上，对数据进行先采样后计算，系统重量大，扩展性较差，样本所需空间成本较大。

综上所述，精确查询通过预计算等方法能够获得精确结果，但需要更多的存储空间，查询时延较长且不可控，对个性化的查询需求无法快速反应。基于采样的近似计算方法可以提升聚合查询性能，在一些方法中，样本在时间维度上的覆盖范围是固定的，不能在时间维度上满足实时的个性化查询需求，但样本的扩容与增量维护思想可以借鉴。现有主流近似查询系统重量较大，较少考虑扩展需求，样本灵活性不足。

3 系统设计

个性化近似聚合查询系统Flexisample（Flexible samples）设计基于灵活动态更新的一组样本，在样本结构设计和样本在线维护时充分考虑了业务人员的个性化查询需求。系统可以解析个性化查询请求并组合出多样的逻辑样本，同时样本可以覆盖全部的时间范围，并随时间推移不断更新维护。本章将详细介绍系统的设计思想以及如何满足多样的个性化查询需求。

3.1 系统结构

Flexisample结构如图1所示，系统包括数据持久化、样本管理、查询引擎以及用户个性化查询接口等模块。其中，数据持久化负责原始数据、元数据以及物理样本的持久化存储工作；样本管理包括分层样本的建立和样本维护功能。查询引擎包括查询请求解析、查询重写、逻辑样本组合和查询执行四个主要部分，其中逻辑样本组合是为个性化查询准备数据。

图1 聚合查询系统结构

3.2 分层样本建立

3.2.1 样本设计

在以采样方法为近似查询基础的系统中，更低精度的查询请求并不能换取更快的响应速度［12］。根据蒙特卡洛思想，查询时间，样本量存在正相关的关系，同时，样本量与查询准确率也存在正相关的关系。因此，为提高采样效率，降低维护成本，Flexisample采用维护多个物理样本的方式来满足业务人员一定的个性化查询交互需求。

同时维护多份样本以满足多种时间约束将会耗费很大的物理空间，样本维护代价也会增加。Flexisample设计采用维护少量物理样本，并在查询时临时生成视图组合为多种逻辑样本供查询引擎查询的方式。设原始数据量为S，系统的样本粒度D∈(0，1)可以根据近似查询的需求自定义，系统以a=S×D为最小单位，建立并维护形如的n份物理样本{Sn}，这样可以有效降低样本生成与维护的时间及空间消耗，n份物理样本数据之间是相互隔离的，一条数据记录不能同时存在于多份物理样本之中。n份物理样本可以在需要时组合为a至的最小粒度为a的2n-1份逻辑样本供查询引擎作为近似查询数据源使用。

在进行分层采样时，应尽量减少数据扫描次数，以优化预采样的时间性能。文献［12］实现了一种分层采样优化方法，该方法运用多维倒排索引减少数据扫描次数。在我们的系统中，基于该采样方法按上述样本结构生成样本，可以得到不同比例且样本之间不存在耦合数据的多份物理样本。设数据共分为m层，分层采样实现过程如图2。

图2 物理样本分层采样过程

系统第一遍扫描数据源，根据随机规则标记数据，将数据标记为不同分层{gm}，同时，每一分层中的数据项再根据生成的随机规则，按{2na}之间的比例标记为n种类别{gmn}。经过第一遍的数据扫描，所有数据项将被全部标记完成，系统对标记列建立索引。第二遍扫描数据源将数据按分层信息与分组标记持久化到{Sn}之中。系统通过这样的方式，经过两次全表扫描实现了数据分层与多个物理样本分组的目的。样本中每个分层数据应尽可能维护在一个物理块{tmn}的连续空间中，以减少执行查询请求时的磁盘IO。

3.2.2 样本量分配

对于数据分层来说，各层的样本量分配情况会直接影响近似查询的精确度。常用的样本量的分配方法有随机分配、按比例分配、内曼分配［13］和最优分配［14］等。在进行分层样本建立时，为保证一定的准确率，系统需要为样本量分配方式提供扩展接口。

Flexisample中的样本量分配模块设计采用了模板方法模式（Template Method Pattern）这一设计模式，支持几种常用样本量分配方法的同时保证了程序的扩展性，开发人员可以根据数据特点以及需求对近似查询服务的样本量分配模块进行扩展实现。样本量分配模块的设计类图如图3所示。

图3 模板设计模式类图

3.3 数据流样本维护

在Flexisample中汲取了文献［10］与BlinkDB［16］建立和维护一组样本的思想，基于滑动窗口对数据项进行分层，查找分层的tmn并对其中数据项进行替换。

Flexisample为每一份物理样本建立了一个分层信息映射表{Hn}并维护在内存中方便快速读取。映射表中包含了各层样本在磁盘中的位置信息以及数据量，帮助数据流快速分层。首先，在接收数据流上建立滑动窗口，从内存中获取{Hn}。读取数据项标识，按照物理样本{Sn}数据量的比例随机分发到内存中的临时存储空间{kn}，其中，k1对应H1，分发到k1的数据项通过数据流消费者查找数据项所属的分层gm1，并将数据项存入为gm1开辟的临时存储空间之中。同理，读取数据流中的数据项，对于其他分组进行相同操作。

样本存储在磁盘中，通过对内容感知的数据重分区方法［11］对磁盘与内存中的数据块进行替换。现有可用于样本替换的采样方法包括水库抽样［17］（reservoir sampling）、精确抽样（concise sampling）、计 数 抽 样（counting sampling）、链 式 抽 样［18］（chain-sampling）等。其中，水库抽样可以在增量数据的条件下，为每个分层等概率的选出样本。具体来说，根据映射表将磁盘中的tmn载入内存，此时tmn就作为一个水库，tmn的大小k即为水库大小，存储在各层临时存储空间中的数据项{di}逐个进行计算。对于gmn临时存储空间中的每个数据项来说，都有相同的概率替换掉tmn中的随机一条数据项。

3.4 个性化聚合查询

近似聚合查询需要满足业务人员的自定义聚合查询需求和一定范围内的时间约束。对于前者来说即为将AGG转换为AGG'，对于后者来说可以通过控制查询数据集xi的大小来实现。

业务人员多以SQL脚本的形式提出自定义的聚合查询请求，根据表1中的多维时序数据聚合查询实例，可以得到如表2所示的聚合查询请求BNF范式，其中包括：Query_Items查询项，Table_Names表字段，Query_Conditions查询条件，Group_Conditions分组条件，Time_Condition时间约束五个主要部分。

表2 个性化查询请求BNF范式

查询引擎根据聚合查询请求的各个部分解析业务人员提出的分组聚合查询请求，并校验请求是否合法。对于合法的请求，Flexisample将请求重写为在维护的样本上执行的近似查询请求。

另一方面，系统根据不同的时间约束，动态的建立逻辑样本供查询引擎执行近似查询请求。基于实验可以拟合出样本量与查询时间的二元关系模型。在获取到查询时间约束后，系统可以根据二元关系映射满足时间约束的最大样本量。个性化近似查询在逻辑样本上执行，样本量大小可以一定程度上控制查询的运行时间。在执行跨样本查询时，系统基于Spark的UNION ALL操作创建临时视图。因Flexisample中维护的多份物理样本之间无重复数据，相比于UNION操作，极大降低了组合逻辑样本所花费的时间成本。

4 系统验证及结果分析

4.1 实验环境

Flexisample部署在集群上，集群由三台服务器组成，三台机器的CPU、内存、操作系统如表3所示，集群中每台服务器软件环境如下有：JDK：1.8、hadoop：2.6.0、hbase：1.2.0、hive：1.1.0、kafka：2.2.1、spark：1.6.0、zookeeper：3.4.5、flink：1.12.0。

表3 实验环境

4.2 实验数据

本文的实验数据为电网监测指标数据，其原始数据格式如表4，包括监测点、指标、时间戳以及数值。其中每一个监测点对应唯一的监测点ID。指标列负责标注数据项所属的频率、监测点编码、监测指标、指标相别、指标聚合类型等。电能质量数据来自全网谐波监测系统9000多个监测点的海量数据，数据维度高，包括指标、时间、空间、电压等级、监测对象等维度，且指标之间关联性强。

表4 电网电能质量数据

4.3 实验过程与结果

为验证上述近似查询服务的运行效果，首先进行分层样本的建立与模拟数据流样本维护。系统中的样本粒度D设为1%，并根据系统设置建立并维护了1%，2%，4%，8%四份物理样本，可以在查询时组合为1%~15%粒度为1%的逻辑样本。

对试验系统提出满足表2所述BNF范式的分组聚合查询请求。查询请求为分组聚合查询，包括省网名称，市网名称与AVG( )Value聚合函数值三个查询项，表字段为‘pq_data’，查询值按省网与市网两个空间维度进行分组。为计算系统的查询准确率，需要对全量数据进行精确计算，精确计算与近似计算的查询时延如表5所示，查询请求中时间约束为10s。对所有分层计算其近似查询准确率，结果的前5项如表6所示，其中省网列与市网列为分组列。

表5 查询时延

表6 近似查询结果及准确率

为获得自定义时间约束的查询效果，在所有可组合样本量的逻辑样本上进行聚合查询实验，查询请求仍按省市两级的分组聚合查询，去除时间约束，直接在不同逻辑样本上进行聚合查询。图4记录了系统在不同样本量下执行查询请求的查询时间与准确率。每份逻辑样本的查询准确率由该逻辑样本所有分层中准确率最低的分层的近似查询准确率代表。

图4 系统近似聚合查询实验

4.4 实验分析

在上述实验中，近似聚合查询系统满足了查询请求中的时间约束，系统近似查询时间仅为全量计算时间的不足7%，有效提高了查询效率，且对于测试数据的全部142个分层来说，其准确率均达到88%以上。从图4中可以看到，不同样本量的查询时间存在一定程度上的差别，可以满足用户对查询时间一定范围内的时间约束调整。另一方面，从空间成本来说，系统本次实验中的存储空间仅需，而直接存储多份物理样本达到同样效果所需的存储空间为，空间成本减少了87.5%。在表6中，因查询数值的单位不同，故不同分层的查询结果数据之间有较大差别，但由于层中单位是统一的，因此并不会影响实验的准确率。

5 结语

本文介绍了一个个性化近似聚合查询服务系统Flexisample，通过系统实验证明，Flexisample可以满足个性化近似聚合查询需求，样本在时间维度的覆盖范围更广，分层样本动态实时维护并且可以在一定范围内调整查询时延，查询准确率有一定保障，能有效提高业务人员的查询效率。

系统经过长时间基于数据流的样本维护，各个分层的总数据量不断增加，但样本总量未发生改变，系统的查询准确率会随样本维护时间持续下降。如何在数据总量不断增加的情况下，高效运用样本中的已有信息来保持甚至提高近似聚合查询的准确率将是今后的主要工作目标。