Flexisample：個性化近似聚合查詢系統(tǒng)*

趙 博 左昌麒 房 俊

（1.北方工業(yè)大學(xué)信息學(xué)院 北京 100144）（2.大規(guī)模流數(shù)據(jù)集成與分析技術(shù)北京市重點實驗室 北京 100144）

1 引言

當(dāng)前，隨著物聯(lián)網(wǎng)的飛速發(fā)展，多維時序數(shù)據(jù)不斷產(chǎn)生，以電能質(zhì)量大數(shù)據(jù)分析系統(tǒng)中的電能質(zhì)量數(shù)據(jù)為例［1］，其部署的監(jiān)測點每隔3s采集2550個指標(biāo)數(shù)據(jù)，目前部署了超1萬的監(jiān)測點，基于上述海量數(shù)據(jù)的挖掘分析對于電能質(zhì)量治理具有重要意義。

聚合查詢是最為常見的數(shù)據(jù)統(tǒng)計與分析方法之一。在面對海量時序數(shù)據(jù)時，聚合查詢性能延遲較大，往往不能滿足業(yè)務(wù)需求。近似查詢犧牲一定查詢精度來換取更快速的查詢結(jié)果，近些年來在研究領(lǐng)域獲得了較多關(guān)注。近似查詢可以總結(jié)為如下公式：

從全量數(shù)據(jù)集x通過一定的方法獲取到用于近似計算的數(shù)據(jù)集xi。為了達到一定的精確度，減小誤差，聚合查詢函數(shù)AGG需要做針對性的修改，修改后的聚合函數(shù)記為AGG′。近似聚合查詢方法主要有采樣技術(shù)［3］，直方圖，小波變換［4］，草圖［5］等方法，其中采樣技術(shù)是大規(guī)模聚合查詢中的一種普適方法［6］，大量聚合查詢工作集中在基于采樣的近似聚合查詢優(yōu)化上。

現(xiàn)有研究集中在方法研究，對近似查詢服務(wù)系統(tǒng)的實現(xiàn)工作相對較少，且實現(xiàn)系統(tǒng)多針對某一類型數(shù)據(jù)的特殊優(yōu)化設(shè)計，用戶在生產(chǎn)生活中迫切需要通用的支持個性化查詢的近似查詢服務(wù)系統(tǒng)來有效降低查詢時延。個性化的查詢包含兩個方面，其一是查詢請求的個性化，業(yè)務(wù)人員的查詢請求多以SQL腳本的形式提出，如表1所示是電能質(zhì)量聚合查詢的示例，查詢請求的個性化要求系統(tǒng)能夠快速的對請求進行解析重寫等操作；其二是查詢時間的個性化，不同的業(yè)務(wù)人員可以承受不同的響應(yīng)時間和查詢精度，為此系統(tǒng)需要滿足業(yè)務(wù)人員一定范圍內(nèi)的時間約束。

表1 多維時序數(shù)據(jù)聚合查詢實例

針對上述問題，本文設(shè)計并實現(xiàn)了一個個性化近似聚合查詢系統(tǒng)Flexisample（Flexiable Sampling），基于分層采樣技術(shù)對樣本進行了結(jié)構(gòu)設(shè)計，運用數(shù)據(jù)項分層與樣本替換策略實現(xiàn)了基于數(shù)據(jù)流的樣本增量維護工作，并且通過對查詢請求的解析實現(xiàn)了系統(tǒng)的查詢請求個性化，使用維護多份物理樣本的方法來滿足查詢時間個性化。

2 相關(guān)工作

聚合查詢目的是幫助人們理解一段時間內(nèi)數(shù)據(jù)集的變化［7］。現(xiàn)有的聚合查詢處理優(yōu)化方法按照返回結(jié)果的準(zhǔn)確程度可分為精確查詢和近似查詢兩類。

精確查詢方面，現(xiàn)有研究主要集中在并行計算框架與索引優(yōu)化方向，如Spark SQL［8］利用并行計算框架提升計算能力，有良好的數(shù)據(jù)量和靈活性支持，作者考慮了用戶的使用習(xí)慣，對ad-hoc、reporting、iterative等類型的查詢需求提供了SQL查詢接口，將SQL語句轉(zhuǎn)換為邏輯查詢計劃并對其進行優(yōu)化調(diào)整，最終轉(zhuǎn)化為物理查詢計劃提交給Spark執(zhí)行。Spark SQL基于Hive對個性化查詢提供了支持，但對查詢時延沒有約束，可以通過結(jié)合近似查詢進一步降低查詢時延。文獻［9］采用分布式計算框架和聚合管道與索引結(jié)合的方式提升計算效率，雖然通過優(yōu)化并行計算獲取精確聚合查詢結(jié)果的方式已經(jīng)很大程度上降低查詢時延，達到一定效果，但查詢過程中依舊存在大量的磁盤IO和計算，且并不能對個性化的時間約束做出反應(yīng)，查詢時延對比近似查詢依舊偏高。

近似查詢方面，文獻［10］中提出了增量式的樣本擴容與誤差估計方法，這種方法可以快速地獲取查詢結(jié)果，但在針對稀疏數(shù)據(jù)時效果并不理想，且樣本在時間維度上的覆蓋范圍相對固定，實時在線聚合時在時間維度上無法滿足個性化查詢需求。研究［11］對在線聚集方法進行了優(yōu)化，提出了基于內(nèi)容的數(shù)據(jù)塊劃分，索引以及放置策略。Sameer［16］等基于分布式采樣提出了BlinkDB近似查詢處理系統(tǒng)，其使用大規(guī)模并行查詢引擎，支持交互式SQL查詢，但BlinkDB建立在Shark和Spark之上，對數(shù)據(jù)進行先采樣后計算，系統(tǒng)重量大，擴展性較差，樣本所需空間成本較大。

綜上所述，精確查詢通過預(yù)計算等方法能夠獲得精確結(jié)果，但需要更多的存儲空間，查詢時延較長且不可控，對個性化的查詢需求無法快速反應(yīng)?；诓蓸拥慕朴嬎惴椒梢蕴嵘酆喜樵冃阅?，在一些方法中，樣本在時間維度上的覆蓋范圍是固定的，不能在時間維度上滿足實時的個性化查詢需求，但樣本的擴容與增量維護思想可以借鑒?，F(xiàn)有主流近似查詢系統(tǒng)重量較大，較少考慮擴展需求，樣本靈活性不足。

3 系統(tǒng)設(shè)計

個性化近似聚合查詢系統(tǒng)Flexisample（Flexible samples）設(shè)計基于靈活動態(tài)更新的一組樣本，在樣本結(jié)構(gòu)設(shè)計和樣本在線維護時充分考慮了業(yè)務(wù)人員的個性化查詢需求。系統(tǒng)可以解析個性化查詢請求并組合出多樣的邏輯樣本，同時樣本可以覆蓋全部的時間范圍，并隨時間推移不斷更新維護。本章將詳細介紹系統(tǒng)的設(shè)計思想以及如何滿足多樣的個性化查詢需求。

3.1 系統(tǒng)結(jié)構(gòu)

Flexisample結(jié)構(gòu)如圖1所示，系統(tǒng)包括數(shù)據(jù)持久化、樣本管理、查詢引擎以及用戶個性化查詢接口等模塊。其中，數(shù)據(jù)持久化負責(zé)原始數(shù)據(jù)、元數(shù)據(jù)以及物理樣本的持久化存儲工作；樣本管理包括分層樣本的建立和樣本維護功能。查詢引擎包括查詢請求解析、查詢重寫、邏輯樣本組合和查詢執(zhí)行四個主要部分，其中邏輯樣本組合是為個性化查詢準(zhǔn)備數(shù)據(jù)。

圖1 聚合查詢系統(tǒng)結(jié)構(gòu)

3.2 分層樣本建立

3.2.1 樣本設(shè)計

在以采樣方法為近似查詢基礎(chǔ)的系統(tǒng)中，更低精度的查詢請求并不能換取更快的響應(yīng)速度［12］。根據(jù)蒙特卡洛思想，查詢時間，樣本量存在正相關(guān)的關(guān)系，同時，樣本量與查詢準(zhǔn)確率也存在正相關(guān)的關(guān)系。因此，為提高采樣效率，降低維護成本，F(xiàn)lexisample采用維護多個物理樣本的方式來滿足業(yè)務(wù)人員一定的個性化查詢交互需求。

同時維護多份樣本以滿足多種時間約束將會耗費很大的物理空間，樣本維護代價也會增加。Flexisample設(shè)計采用維護少量物理樣本，并在查詢時臨時生成視圖組合為多種邏輯樣本供查詢引擎查詢的方式。設(shè)原始數(shù)據(jù)量為S，系統(tǒng)的樣本粒度D∈(0，1)可以根據(jù)近似查詢的需求自定義，系統(tǒng)以a=S×D為最小單位，建立并維護形如的n份物理樣本{Sn}，這樣可以有效降低樣本生成與維護的時間及空間消耗，n份物理樣本數(shù)據(jù)之間是相互隔離的，一條數(shù)據(jù)記錄不能同時存在于多份物理樣本之中。n份物理樣本可以在需要時組合為a至的最小粒度為a的2n-1份邏輯樣本供查詢引擎作為近似查詢數(shù)據(jù)源使用。

在進行分層采樣時，應(yīng)盡量減少數(shù)據(jù)掃描次數(shù)，以優(yōu)化預(yù)采樣的時間性能。文獻［12］實現(xiàn)了一種分層采樣優(yōu)化方法，該方法運用多維倒排索引減少數(shù)據(jù)掃描次數(shù)。在我們的系統(tǒng)中，基于該采樣方法按上述樣本結(jié)構(gòu)生成樣本，可以得到不同比例且樣本之間不存在耦合數(shù)據(jù)的多份物理樣本。設(shè)數(shù)據(jù)共分為m層，分層采樣實現(xiàn)過程如圖2。

圖2 物理樣本分層采樣過程

系統(tǒng)第一遍掃描數(shù)據(jù)源，根據(jù)隨機規(guī)則標(biāo)記數(shù)據(jù)，將數(shù)據(jù)標(biāo)記為不同分層{gm}，同時，每一分層中的數(shù)據(jù)項再根據(jù)生成的隨機規(guī)則，按{2na}之間的比例標(biāo)記為n種類別{gmn}。經(jīng)過第一遍的數(shù)據(jù)掃描，所有數(shù)據(jù)項將被全部標(biāo)記完成，系統(tǒng)對標(biāo)記列建立索引。第二遍掃描數(shù)據(jù)源將數(shù)據(jù)按分層信息與分組標(biāo)記持久化到{Sn}之中。系統(tǒng)通過這樣的方式，經(jīng)過兩次全表掃描實現(xiàn)了數(shù)據(jù)分層與多個物理樣本分組的目的。樣本中每個分層數(shù)據(jù)應(yīng)盡可能維護在一個物理塊{tmn}的連續(xù)空間中，以減少執(zhí)行查詢請求時的磁盤IO。

3.2.2 樣本量分配

對于數(shù)據(jù)分層來說，各層的樣本量分配情況會直接影響近似查詢的精確度。常用的樣本量的分配方法有隨機分配、按比例分配、內(nèi)曼分配［13］和最優(yōu)分配［14］等。在進行分層樣本建立時，為保證一定的準(zhǔn)確率，系統(tǒng)需要為樣本量分配方式提供擴展接口。

Flexisample中的樣本量分配模塊設(shè)計采用了模板方法模式（Template Method Pattern）這一設(shè)計模式，支持幾種常用樣本量分配方法的同時保證了程序的擴展性，開發(fā)人員可以根據(jù)數(shù)據(jù)特點以及需求對近似查詢服務(wù)的樣本量分配模塊進行擴展實現(xiàn)。樣本量分配模塊的設(shè)計類圖如圖3所示。

圖3 模板設(shè)計模式類圖

3.3 數(shù)據(jù)流樣本維護

在Flexisample中汲取了文獻［10］與BlinkDB［16］建立和維護一組樣本的思想，基于滑動窗口對數(shù)據(jù)項進行分層，查找分層的tmn并對其中數(shù)據(jù)項進行替換。

Flexisample為每一份物理樣本建立了一個分層信息映射表{Hn}并維護在內(nèi)存中方便快速讀取。映射表中包含了各層樣本在磁盤中的位置信息以及數(shù)據(jù)量，幫助數(shù)據(jù)流快速分層。首先，在接收數(shù)據(jù)流上建立滑動窗口，從內(nèi)存中獲取{Hn}。讀取數(shù)據(jù)項標(biāo)識，按照物理樣本{Sn}數(shù)據(jù)量的比例隨機分發(fā)到內(nèi)存中的臨時存儲空間{kn}，其中，k1對應(yīng)H1，分發(fā)到k1的數(shù)據(jù)項通過數(shù)據(jù)流消費者查找數(shù)據(jù)項所屬的分層gm1，并將數(shù)據(jù)項存入為gm1開辟的臨時存儲空間之中。同理，讀取數(shù)據(jù)流中的數(shù)據(jù)項，對于其他分組進行相同操作。

樣本存儲在磁盤中，通過對內(nèi)容感知的數(shù)據(jù)重分區(qū)方法［11］對磁盤與內(nèi)存中的數(shù)據(jù)塊進行替換?，F(xiàn)有可用于樣本替換的采樣方法包括水庫抽樣［17］（reservoir sampling）、精確抽樣（concise sampling）、計 數(shù) 抽 樣（counting sampling）、鏈 式 抽 樣［18］（chain-sampling）等。其中，水庫抽樣可以在增量數(shù)據(jù)的條件下，為每個分層等概率的選出樣本。具體來說，根據(jù)映射表將磁盤中的tmn載入內(nèi)存，此時tmn就作為一個水庫，tmn的大小k即為水庫大小，存儲在各層臨時存儲空間中的數(shù)據(jù)項{di}逐個進行計算。對于gmn臨時存儲空間中的每個數(shù)據(jù)項來說，都有相同的概率替換掉tmn中的隨機一條數(shù)據(jù)項。

3.4 個性化聚合查詢

近似聚合查詢需要滿足業(yè)務(wù)人員的自定義聚合查詢需求和一定范圍內(nèi)的時間約束。對于前者來說即為將AGG轉(zhuǎn)換為AGG'，對于后者來說可以通過控制查詢數(shù)據(jù)集xi的大小來實現(xiàn)。

業(yè)務(wù)人員多以SQL腳本的形式提出自定義的聚合查詢請求，根據(jù)表1中的多維時序數(shù)據(jù)聚合查詢實例，可以得到如表2所示的聚合查詢請求BNF范式，其中包括：Query_Items查詢項，Table_Names表字段，Query_Conditions查詢條件，Group_Conditions分組條件，Time_Condition時間約束五個主要部分。

表2 個性化查詢請求BNF范式

查詢引擎根據(jù)聚合查詢請求的各個部分解析業(yè)務(wù)人員提出的分組聚合查詢請求，并校驗請求是否合法。對于合法的請求，F(xiàn)lexisample將請求重寫為在維護的樣本上執(zhí)行的近似查詢請求。

另一方面，系統(tǒng)根據(jù)不同的時間約束，動態(tài)的建立邏輯樣本供查詢引擎執(zhí)行近似查詢請求?；趯嶒灴梢詳M合出樣本量與查詢時間的二元關(guān)系模型。在獲取到查詢時間約束后，系統(tǒng)可以根據(jù)二元關(guān)系映射滿足時間約束的最大樣本量。個性化近似查詢在邏輯樣本上執(zhí)行，樣本量大小可以一定程度上控制查詢的運行時間。在執(zhí)行跨樣本查詢時，系統(tǒng)基于Spark的UNION ALL操作創(chuàng)建臨時視圖。因Flexisample中維護的多份物理樣本之間無重復(fù)數(shù)據(jù)，相比于UNION操作，極大降低了組合邏輯樣本所花費的時間成本。

4 系統(tǒng)驗證及結(jié)果分析

4.1 實驗環(huán)境

Flexisample部署在集群上，集群由三臺服務(wù)器組成，三臺機器的CPU、內(nèi)存、操作系統(tǒng)如表3所示，集群中每臺服務(wù)器軟件環(huán)境如下有：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 實驗環(huán)境

4.2 實驗數(shù)據(jù)

本文的實驗數(shù)據(jù)為電網(wǎng)監(jiān)測指標(biāo)數(shù)據(jù)，其原始數(shù)據(jù)格式如表4，包括監(jiān)測點、指標(biāo)、時間戳以及數(shù)值。其中每一個監(jiān)測點對應(yīng)唯一的監(jiān)測點ID。指標(biāo)列負責(zé)標(biāo)注數(shù)據(jù)項所屬的頻率、監(jiān)測點編碼、監(jiān)測指標(biāo)、指標(biāo)相別、指標(biāo)聚合類型等。電能質(zhì)量數(shù)據(jù)來自全網(wǎng)諧波監(jiān)測系統(tǒng)9000多個監(jiān)測點的海量數(shù)據(jù)，數(shù)據(jù)維度高，包括指標(biāo)、時間、空間、電壓等級、監(jiān)測對象等維度，且指標(biāo)之間關(guān)聯(lián)性強。

表4 電網(wǎng)電能質(zhì)量數(shù)據(jù)

4.3 實驗過程與結(jié)果

為驗證上述近似查詢服務(wù)的運行效果，首先進行分層樣本的建立與模擬數(shù)據(jù)流樣本維護。系統(tǒng)中的樣本粒度D設(shè)為1%，并根據(jù)系統(tǒng)設(shè)置建立并維護了1%，2%，4%，8%四份物理樣本，可以在查詢時組合為1%~15%粒度為1%的邏輯樣本。

對試驗系統(tǒng)提出滿足表2所述BNF范式的分組聚合查詢請求。查詢請求為分組聚合查詢，包括省網(wǎng)名稱，市網(wǎng)名稱與AVG( )Value聚合函數(shù)值三個查詢項，表字段為‘pq_data’，查詢值按省網(wǎng)與市網(wǎng)兩個空間維度進行分組。為計算系統(tǒng)的查詢準(zhǔn)確率，需要對全量數(shù)據(jù)進行精確計算，精確計算與近似計算的查詢時延如表5所示，查詢請求中時間約束為10s。對所有分層計算其近似查詢準(zhǔn)確率，結(jié)果的前5項如表6所示，其中省網(wǎng)列與市網(wǎng)列為分組列。

表5 查詢時延

表6 近似查詢結(jié)果及準(zhǔn)確率

為獲得自定義時間約束的查詢效果，在所有可組合樣本量的邏輯樣本上進行聚合查詢實驗，查詢請求仍按省市兩級的分組聚合查詢，去除時間約束，直接在不同邏輯樣本上進行聚合查詢。圖4記錄了系統(tǒng)在不同樣本量下執(zhí)行查詢請求的查詢時間與準(zhǔn)確率。每份邏輯樣本的查詢準(zhǔn)確率由該邏輯樣本所有分層中準(zhǔn)確率最低的分層的近似查詢準(zhǔn)確率代表。

圖4 系統(tǒng)近似聚合查詢實驗

4.4 實驗分析

在上述實驗中，近似聚合查詢系統(tǒng)滿足了查詢請求中的時間約束，系統(tǒng)近似查詢時間僅為全量計算時間的不足7%，有效提高了查詢效率，且對于測試數(shù)據(jù)的全部142個分層來說，其準(zhǔn)確率均達到88%以上。從圖4中可以看到，不同樣本量的查詢時間存在一定程度上的差別，可以滿足用戶對查詢時間一定范圍內(nèi)的時間約束調(diào)整。另一方面，從空間成本來說，系統(tǒng)本次實驗中的存儲空間僅需，而直接存儲多份物理樣本達到同樣效果所需的存儲空間為，空間成本減少了87.5%。在表6中，因查詢數(shù)值的單位不同，故不同分層的查詢結(jié)果數(shù)據(jù)之間有較大差別，但由于層中單位是統(tǒng)一的，因此并不會影響實驗的準(zhǔn)確率。

5 結(jié)語

本文介紹了一個個性化近似聚合查詢服務(wù)系統(tǒng)Flexisample，通過系統(tǒng)實驗證明，F(xiàn)lexisample可以滿足個性化近似聚合查詢需求，樣本在時間維度的覆蓋范圍更廣，分層樣本動態(tài)實時維護并且可以在一定范圍內(nèi)調(diào)整查詢時延，查詢準(zhǔn)確率有一定保障，能有效提高業(yè)務(wù)人員的查詢效率。

系統(tǒng)經(jīng)過長時間基于數(shù)據(jù)流的樣本維護，各個分層的總數(shù)據(jù)量不斷增加，但樣本總量未發(fā)生改變，系統(tǒng)的查詢準(zhǔn)確率會隨樣本維護時間持續(xù)下降。如何在數(shù)據(jù)總量不斷增加的情況下，高效運用樣本中的已有信息來保持甚至提高近似聚合查詢的準(zhǔn)確率將是今后的主要工作目標(biāo)。