基于分布式計算的what-if分析并行處理策略*

鄭雪梅，陳 梅，李 暉（1.貴州大學計算機科學與技術(shù)學院，貴州貴陽550025；2.貴州大學貴州省先進計算與醫(yī)療信息服務(wù)工程實驗室，貴州貴陽550025）

基于分布式計算的what-if分析并行處理策略*

鄭雪梅1，2，陳 梅1，2，李 暉1，2
（1.貴州大學計算機科學與技術(shù)學院，貴州貴陽550025；
2.貴州大學貴州省先進計算與醫(yī)療信息服務(wù)工程實驗室，貴州貴陽550025）

根據(jù)基于OLAP的what-if分析的查詢特點，使用分布式并行處理技術(shù)解決what-if分析性能較低的問題。以星座模型為基礎(chǔ)的what-if分析中，將多維聚集查詢分布到不同計算節(jié)點進行聚集計算，然后將各個計算節(jié)點的聚集計算結(jié)果合并輸出。該方法根據(jù)基于OLAP的what-if分析中其維表遠遠小于事實表的特性，將事實表中的記錄進行水平分片，充分利用各節(jié)點計算和I/O處理能力，以解決OLAP查詢中計算密集型及I/O消耗過大的難題。在該方法中，隨著計算節(jié)點數(shù)目的增加，其查詢時間隨之減少，有效地提升了分析效率。

OLAP；what-if分析；分布式并行處理

O 引言

what-if分析是決策者對多種決策方案進行預測或評估時的常用手段，通常以多種形式應(yīng)用于不同的應(yīng)用場景，尤其在決策系統(tǒng)中發(fā)揮重要作用。簡單地說，what-if分析就是以數(shù)據(jù)倉庫中歷史數(shù)據(jù)為基礎(chǔ)數(shù)據(jù)的假設(shè)分析，決策者根據(jù)決策目標制定一系列假設(shè)場景，通過對已有數(shù)據(jù)的假設(shè)分析得到假設(shè)場景下的商業(yè)數(shù)據(jù)變化情況。

近年來，隨著數(shù)據(jù)倉庫中數(shù)據(jù)的不斷膨脹，數(shù)據(jù)量從TB級增長到PB級甚至EB級別，決策者在海量的數(shù)據(jù)中挖掘價值，以便更快更準地捕獲商機，在很大程度上還需要借助what-if分析工具的應(yīng)用。因此，基于OLAP的what-if分析一直受到很多學者的關(guān)注，但由于what-if分析自身的復雜性，至今未得到廣泛應(yīng)用。在假設(shè)分析時通常需要更改Cube結(jié)構(gòu)或修改Cube數(shù)據(jù)，這些操作均涉及到Cube重計算，花費時間較長，限制了what-if分析的能力。

隨著大規(guī)模并行處理關(guān)系數(shù)據(jù)庫的發(fā)展，如Vertica、微軟的SQL Server并行數(shù)據(jù)倉庫以及GreenP1um數(shù)據(jù)倉庫等的使用，使高效的并行查詢處理及數(shù)據(jù)分析成為可能。因此，本文結(jié)合基于OLAP的what-if分析的特點，與分布式并行處理技術(shù)相結(jié)合，可以有效提高查詢效率，解決決策者面臨分析效率低的問題。

1 相關(guān)研究工作

what-if分析的概念早已提出，由于其復雜性未得到廣泛應(yīng)用，但是對其研究一直在進行中。參考文獻［1］中提出基于De1ta表的what-if分析，通過預處理方法提高whatif分析效率，更改工作內(nèi)容均是在內(nèi)存數(shù)據(jù)庫中實現(xiàn)，而不是在基于磁盤的關(guān)系型數(shù)據(jù)庫中實現(xiàn)，其性能未得到明顯提升。參考文獻［2］在參考文獻［1］的基礎(chǔ)上，利用并行計算模型MaPReduce實現(xiàn)what-if分析，其性能有一定的提升。隨著what-if分析的研究，參考文獻［3-4］分別將what-if分析應(yīng)用于MaPReduce的調(diào)優(yōu)及復雜云數(shù)據(jù)中心的資源分配。參考文獻［5］詳細介紹了分布式并行處理整體方案。參考文獻［6］提出了內(nèi)存數(shù)據(jù)庫中利用分布式并行處理技術(shù)實現(xiàn)OLAP并行操作的方案。本文中的what-if分析使用分布式并行處理技術(shù)，利用并行處理機制提升what-if分析性能。

2 what-if分析

本節(jié)主要以O(shè)LAP模型中的星座模型為例，詳細介紹what-if分析中的基礎(chǔ)概念及實現(xiàn)方法，并分析其實現(xiàn)過程中存在的問題及擬解決方法。

2.1 基于OLAP的what-if分析

基于OLAP的what-if分析實質(zhì)是基于假設(shè)場景的OLAP查詢。在假設(shè)數(shù)據(jù)生成后，生成新的Cube，Cube通常有星型、星座和雪花等OLAP模型；基于新的Cube可以執(zhí)行相應(yīng)的OLAP操作，如Ro11-uP。圖1為本文使用Foodmart數(shù)據(jù)的OLAP模型。

圖1 Foodmart的OLAP模型

圖1中有2個事實表和6個維表。其中，sa1es_fact （Product_id，time_id，customer_id，Promotion_id，store_id，store_sa1es）、sa1es_fact_virtua1（Product_id，time_id，customer_id，Promotion_id，store_id，store_sa1es，wbversion，sign）為兩個事實表。

sa1es_fact用于存儲數(shù)據(jù)庫中的歷史數(shù)據(jù)，在what-if分析中稱之為基表；sa1es_fact_virtua1是與sa1es_fact結(jié)構(gòu)相似的另一個事實表，叫de1ta表，用于存儲假設(shè)數(shù)據(jù)，這類的假設(shè)分析是基于de1ta表的what-if分析。由事實表可知，de1ta表是在基表的基礎(chǔ)上增加了多個字段，如wbversion和sign，wbversion表示版本號，sign為更新類型，其更新類型主要有插入（I）、更新（U）和刪除（D）三類，分別用1、0、-1值來表示。store_sa1es為度量值，其余均為維度值。

2.2 wha t-if分析實現(xiàn)

本節(jié)主要介紹基于de1ta表的what-if分析的實現(xiàn)過程。首先，根據(jù)假設(shè)場景將假設(shè)數(shù)據(jù)存儲到de1ta表中；其次，將de1ta表與基表合并生成新的Cube，此步驟稱之為假設(shè)更新，也叫what-if更新；最后，基于新生成的Cube執(zhí)行OLAP查詢操作。

對于基表與de1ta表的合并，常用的方法是通過等值連接、左連接和全連接等操作來實現(xiàn)。下面是依據(jù)2.1節(jié)中的OLAP模型通過使用連接操作來實現(xiàn)what-if分析。

在連接算法中，首先排除基表中受de1ta表D和U類更新影響的記錄，然后再與de1ta表中U類型和I類型的記錄合并。三種算法具體實現(xiàn)如下：

算法1 等值連接算法

tmPtab1e=sa1es_fact 1eft（sf）join sa1es_fact_virtua1（sfv）

for each tuP1e t in sf

outPut（t.Product_id，t.time_id，t.customer_id，t.Promotion_id，t. store_id，t.store_sa1es）->what-if_view_0

for each tuP1e t in tmPtab1e

outPut（t.Product_id，t.time_id，t.customer_id，t.Promotion_id，t. store_id，t.store_sa1es）->what-if_view_1

for each tuP1e t in sfv

if sign =1 or 0 then outPut（t.Product_id，t.time_id，t.customer_id，t. Promotion_id，t.store_id，t.store_sa1es）->what-if_view_2

return what-if_view_0 EXCEPT what-if_view_1 union a11what-if_ view_2

算法2 左連接算法

tmPtab1e=sa1es_fact 1eft（sf）join sa1es_fact_virtua1（sfv）

for each tuP1e t in tmPtab1e

if t.sign is nu11 then outPut（t.Product_id，t.time_id，t.customer_id，t. Promotion_id，t.store_id，t.store_sa1es）->what-if_view；

if t.sign =-1 then skiP t；

for each tuP1e t in sfv

if sign =1 or 0 then outPut（t.Product_id，t.time_id，t.customer_id，t. Promotion_id，t.store_id，t.store_sa1es）->what-if_view_1 return what-if_view union a11what-if_view_1

算法3 全連接算法

tm Ptab1e=sa1es_fact 1eft（sf）join sa1es_fact_virtua1（sfv）

for each tuP1e t in tmPtab1e

if t.Product_id is not nu11and t.sign is nu11 then outPut（t.Product_id，t.time_id，t.customer_id，t.Promotion_id，t.store_id，t.store_sa1es）-> what-if_view

if t.Product_id is not nu11and t.sign =1 or 0 then outPut（t.Product_id （sfv），t.time_id（sfv），t.customer_id（sfv），t.Promotion_id（sfv），t.store_ id（sfv），t.store_sa1es（sfv））->what-if_view

return what-if_view；

通過連接操作執(zhí)行假設(shè)更新后得到新的Cube，在基于Cube的OLAP查詢中，其OLAP查詢結(jié)果通常為grouP by和order by所得的聚集結(jié)果值，涉及操作有MAX、MIN、SUM、COUNT等分布式聚集運算等。

綜上所述，在what-if分析的實現(xiàn)過程中，關(guān)鍵問題是如何高效地合并基表和de1ta表并執(zhí)行OLAP操作。下節(jié)將介紹使用分布式并行處理來提高what-if分析的整體效率。

3 分布式并行執(zhí)行

3.1 分布式并行處理

基于Shared-nothing結(jié)構(gòu)的分布式并行數(shù)據(jù)庫具有較好的可擴展性，圖2為本文使用的分布式并行數(shù)據(jù)庫集群架構(gòu)，整個集群由多個數(shù)據(jù)節(jié)點（Segment Host）和控制節(jié)點（Master Host）組成。Master Host主要負責與客戶端的通信、對SQL進行分析以及生成執(zhí)行計劃并分發(fā)到每個Segment上執(zhí)行，最后將匯總結(jié)果反饋給客戶端；數(shù)據(jù)節(jié)點負責數(shù)據(jù)的存儲、存取以及執(zhí)行Master分發(fā)的SQL語句，在每個數(shù)據(jù)節(jié)點上可以允許有多個數(shù)據(jù)庫。同時，各個節(jié)點之間的信息交互通過節(jié)點互聯(lián)網(wǎng)絡(luò)來實現(xiàn)。

圖2 基于Shared-nothing的并行處理數(shù)據(jù)庫

分布式并行處理數(shù)據(jù)庫集群架構(gòu)中，數(shù)據(jù)劃分方法對其并行處理的性能影響很大，大多采用的是哈希劃分法和范圍劃分法。文本中即采用了Hash劃分方式將數(shù)據(jù)分布到各個節(jié)點上。其劃分過程為：當數(shù)據(jù)存入數(shù)據(jù)庫時進行數(shù)據(jù)劃分處理，即根據(jù)表中的某一個或幾個字段的哈希值分布到每個節(jié)點。

在涉及連接操作運算的查詢中，利用分布式并行處理數(shù)據(jù)庫對查詢操作并行化，可以充分利用系統(tǒng)中所有的處理器和I/O處理能力，從而縮短查詢響應(yīng)時間。利用分布式并行處理數(shù)據(jù)庫的優(yōu)勢，大大減少了what-if分析合并中由于多表連接產(chǎn)生的大量開銷。

3.2 wha t-if分析的并行執(zhí)行

what-if分析的OLAP查詢中，涉及大量的聚集操作，針對可分布式執(zhí)行的聚集函數(shù)，可將聚查詢分布到不同計算節(jié)點進行聚集計算，并將各個節(jié)點的聚集計算結(jié)果進行合并輸出。因此what-if分析的OLAP并行查詢可分為兩階段：一是提交查詢到多個子查詢節(jié)點上進行并行執(zhí)行；二是合并查詢結(jié)果，然后輸出合并后的最終結(jié)果。

圖3為what-if分析中并行執(zhí)行OLAP查詢的計算過程。在此并行查詢處理中，各處理節(jié)點均將查詢結(jié)果返給OLAP中間服務(wù)器，并計算出最終結(jié)果。

圖3 分布式聚集函數(shù)計算過程

根據(jù)3.1節(jié)中數(shù)據(jù)劃分方法，每個屬性將被分布在不同的節(jié)點上。例如，當有n個節(jié)點時，針對屬性A，則有A =A1∪A2…∪An，在圖3的分布式聚集函數(shù)計算過程中，最終的計算結(jié)果是1～n個節(jié)點的計算結(jié)果的總和。在本文中，實現(xiàn)了常用的分布式聚集函數(shù)如SUM、COUNT、MAX以及MIN等的分布式聚集運算，其計算公式分別表示如下：

SUM（A）=SUM（SUM（A1），…，SUM（An））

COUNT（A）=COUNT（COUNT（A1），…，COUNT （An））

MAX（A）=MAX（MAX（A1），…，MAX（An））

MIN（A）=MIN（MIN（A1），…，MIN（An））

在分布式并行執(zhí)行中，可以利用各計算節(jié)點的計算能力及I/O處理能力提高what-if分析的OLAP查詢效率，但與此同時，若將聚集函數(shù)轉(zhuǎn)換為可分布式計算的聚集函數(shù)時，額外的通信代價相應(yīng)地也會增加。因此，在利用各節(jié)點處理能力的同時需要考慮其網(wǎng)絡(luò)開銷，換句話說，隨著節(jié)點在一定范圍的增加，查詢效率會有相應(yīng)的提升，但當子節(jié)點過多時，隨著網(wǎng)絡(luò)開銷的逐漸增加其查詢效率將會受到一定的影響。

因此，本文一方面適當增加計算節(jié)點提高what-if分析的OLAP查詢效率，另一方面為防止網(wǎng)絡(luò)開銷的過度增加而控制計算節(jié)點數(shù)量。通過此方法，可以有效提高OLAP中所涉及分布式聚集操作。

4 實驗及結(jié)果

4.1 實驗環(huán)境

本文實驗包括兩部分，一是對2.2節(jié)中的三種連接算法實現(xiàn)what-if分析中基表與de1ta表合并的性能測試；二是對what-if分析中4種常用的分布式聚集函數(shù)的測試。

測試實驗為分布式并行處理，分配一個主節(jié)點，數(shù)據(jù)節(jié)點數(shù)分別為1、2、3、4、5，節(jié)點與物理機的分配方式分為兩種：一是主節(jié)點為單獨的物理機，將所有的數(shù)據(jù)節(jié)點放在同一物理機上；二是主節(jié)點和每個數(shù)據(jù)節(jié)點均放在不同的物理機上。所有物理機的配置相同，均為Centos6.4 64 bit的操作系統(tǒng)，16 GB內(nèi)存，100 GB硬盤，GreenP1um 4.3.

5.2為底層數(shù)據(jù)庫。

在測試中，F(xiàn)oodmart數(shù)據(jù)集作為測試數(shù)據(jù)，事實表sa1es_fact的記錄數(shù)為80mi11ions，sa1es_fact_virtua1的記錄數(shù)占sa1es_fact的4%，并設(shè)置sa1es_fact_virtua1中I類型、U類型、D類型占sa1es_fact_virtua1總記錄數(shù)的30%、40% 和30%。

4.2 實驗結(jié)果

根據(jù)Segments節(jié)點與物理機的分配，分別測試what-if分析的3種實現(xiàn)算法的性能變化情況，圖4和圖5縱坐標均表示what-if分析中基表與de1ta表合并的時間。

圖4為所有的Segments節(jié)點在同一物理機時3種連接算法的執(zhí)行結(jié)果?？梢钥闯觯S著節(jié)點的增加，查詢響應(yīng)時間逐漸縮減。

圖5為所有的Segments節(jié)點在不同的物理機上，與圖4類似，其性能隨節(jié)點增加而增加。比較圖4與圖5中的查詢響應(yīng)時間，Segments位于不同的物理機上時，what-if分析的響應(yīng)時間略顯優(yōu)勢。主要是因為在不同物理機上，其CPU和I/O處理能力更強，但同時也增加了更多的網(wǎng)絡(luò)開銷。

圖4 Segments在同一物理機

圖5 Segments在不同物理機

兩種結(jié)果均表明，當數(shù)據(jù)節(jié)點為1時，其合并時間最高，約是數(shù)據(jù)節(jié)點為5時的5倍。

如圖6為4種分布式聚集函數(shù)的并行化執(zhí)行結(jié)果，圖中的Segments放在相同配置的物理機上，當Segments節(jié)點數(shù)為5時，聚集函數(shù)所消耗的時間是單節(jié)點所消耗時間的1 /4。由此可知，分布式并行執(zhí)行能有效提高聚集運算的查詢效率，有利于what-if分析中執(zhí)行的OLAP查詢性能的提高，使what-if分析效率進一步提升。

圖6 聚集運算執(zhí)行結(jié)果

5 結(jié)束語

分布式并行處理以其并行執(zhí)行的優(yōu)勢，廣泛應(yīng)用于數(shù)據(jù)分析領(lǐng)域，可提升數(shù)據(jù)分析性能。文中詳細介紹使用連接算法實現(xiàn)what-if分析，并分析算法中影響其性能的瓶頸，利用分布式并行執(zhí)行策略，即在what-if分析的存儲層使用分布式存儲架構(gòu)，通過并行查詢處理機制，實現(xiàn)多連接查詢的并行化，以達到快速查詢的目的，從而提高what-if分析效率。最后，利用分布式并行執(zhí)行策略對what-if分析中常用的SUM、COUNT、MAX、MIN等操作進行性能測試。

［1］Zhang Yansong，Zhang Yu，Xiao Yanqin，et a1.The tradeoff of

de1ta tab1e merging and re-writing a1gorithms in what-if ana1ysis

aPP1ication［C］.In Proc.APWeb/WAIM′09，2009：260-272.

［2］Xu Huan，Luo Hao，He Jieyue.What-if query Processing Po1icy for big data in OLAP system［C］.In Proc.CBD′13，2013：110-116.

［3］HERODOTOU H，BABU S.Profi1ing，what-if ana1ysis，and cost based oPtimization of MaPReduce Programs［C］.Proc.of the VLDB Endowment，2011：1111-1122.

［4］SINGH R，SHENOY P，NATU M，et a1.Ana1ytica1mode1ing for what-if ana1ysis in comP1ex c1oud comPuting aPP1ications ［C］.SIGMETRICS Perform，2013：53-62.

［5］金樹東，馮玉才.并行數(shù)據(jù)庫系統(tǒng)原型PARO［J］.計算機科學，1997，24（3）：41-45.

［6］張延松，張宇，黃偉，等.分布式聚集函數(shù)支持的內(nèi)存OLAP并行查詢處理技術(shù)［J］.軟件學報，2009（20）：165-175.

李暉（1982 -），通信作者，男，副教授，研究生導師，主要研究方向：大規(guī)模數(shù)據(jù)管理與分析、高性能數(shù)據(jù)庫、云計算等。E-mai1：cse.HuiLi@gzu.edu.cn。

Para11e1Processing strategy for what-if ana1ysis based on distributed comPuting

Zheng Xuemei1，2，Chen Mei1，2，Li Hui1，2
（1.Co11ege of ComPuter Science and Techno1ogy，Guizhou University，Guiyang 550025，China；2.Guizhou Engineering Laboratory for Advanced ComPuting and Medica1 Information Service，Guizhou University，Guiyang 550025，China）

According to the query characteristics of OLAP based what-if ana1ysis，using distributed Para11e1Processing techno1ogy to so1ve the Prob1em of 1ow Performance of what-if ana1ysis.On the basis of the conste11ation mode1，the query with aggregate functions are distributed to each comPuting node to get aggregate resu1ts and fina1 resu1t can be achieved by merging a11 the aggregate resu1ts from mu1tiP1e comPuting nodes.The features of OLAP based what-if ana1ysis is that the dimension tab1e is far 1ess than the fact tab1e，using horizonta1 fragmentation Po1-icy to distribute data in mu1ti-node，and making fu11 use of each node comPutation and I/O Processing abi1ity to imProve efficiency.In this method，with the increase of the number of comPuting nodes，the query time is reduced，and the Performance is imProved significant1y.

on1ine ana1ytica1Processing（OLAP）；what-if ana1ysis；distributed Para11e1Processing

TP302

A

10.19358 /j.issn.1674-7720.2016.09.024

鄭雪梅，陳梅，李暉.基于分布式計算的what-if分析并行處理策略［J］.微型機與應(yīng)用，2016，35（9）：81-84.

國家自然科學基金（61462012）；貴州省科技計劃項目（GY ［2014］3018）；貴州大學研究生創(chuàng)新基金（研理工2015015）

2016-01-08）

鄭雪梅（1990 -），女，碩士研究生，CCF學生會員，主要研究方向：數(shù)據(jù)庫技術(shù)、OLAP。

陳梅（1964 -），女，教授，研究生導師，主要研究方向：大規(guī)模數(shù)據(jù)管理與分析、高性能數(shù)據(jù)庫以及云服務(wù)技術(shù)。