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

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

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

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

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

O 引言

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

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

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

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

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

2 what-if分析

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

2.1 基于OLAP的what-if分析

基于OLAP的what-if分析實(shí)質(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個事實(shí)表和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）為兩個事實(shí)表。

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

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

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

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

在連接算法中，首先排除基表中受de1ta表D和U類更新影響的記錄，然后再與de1ta表中U類型和I類型的記錄合并。三種算法具體實(shí)現(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等分布式聚集運(yùn)算等。

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

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

3.1 分布式并行處理

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

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

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

在涉及連接操作運(yùn)算的查詢中，利用分布式并行處理數(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ù)，可將聚查詢分布到不同計(jì)算節(jié)點(diǎn)進(jìn)行聚集計(jì)算，并將各個節(jié)點(diǎn)的聚集計(jì)算結(jié)果進(jìn)行合并輸出。因此what-if分析的OLAP并行查詢可分為兩階段：一是提交查詢到多個子查詢節(jié)點(diǎn)上進(jìn)行并行執(zhí)行；二是合并查詢結(jié)果，然后輸出合并后的最終結(jié)果。

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

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

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

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

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

4 實(shí)驗(yàn)及結(jié)果

4.1 實(shí)驗(yàn)環(huán)境

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

測試實(shí)驗(yàn)為分布式并行處理，分配一個主節(jié)點(diǎn)，數(shù)據(jù)節(jié)點(diǎn)數(shù)分別為1、2、3、4、5，節(jié)點(diǎn)與物理機(jī)的分配方式分為兩種：一是主節(jié)點(diǎn)為單獨(dú)的物理機(jī)，將所有的數(shù)據(jù)節(jié)點(diǎn)放在同一物理機(jī)上；二是主節(jié)點(diǎn)和每個數(shù)據(jù)節(jié)點(diǎn)均放在不同的物理機(jī)上。所有物理機(jī)的配置相同，均為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ù)，事實(shí)表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 實(shí)驗(yàn)結(jié)果

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

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

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

圖4 Segments在同一物理機(jī)

圖5 Segments在不同物理機(jī)

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

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

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

5 結(jié)束語

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

［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］.計(jì)算機(jī)科學(xué)，1997，24（3）：41-45.

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

李暉（1982 -），通信作者，男，副教授，研究生導(dǎo)師，主要研究方向：大規(guī)模數(shù)據(jù)管理與分析、高性能數(shù)據(jù)庫、云計(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

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

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

2016-01-08）

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

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