鄭雪梅1,2 ,陳梅1,2 ,李暉1,2
(1.貴州大學 計算機科學與技術學院,貴州 貴陽 550025;2.貴州大學 貴州省先進計算與醫療信息服務工程實驗室,貴州 貴陽 550025)
摘要:根據基于OLAP的what-if分析的查詢特點,使用分布式并行處理技術解決whatif分析性能較低的問題。以星座模型為基礎的whatif分析中,將多維聚集查詢分布到不同計算節點進行聚集計算,然后將各個計算節點的聚集計算結果合并輸出。該方法根據基于OLAP的whatif分析中其維表遠遠小于事實表的特性,將事實表中的記錄進行水平分片,充分利用各節點計算和I/O處理能力,以解決OLAP查詢中計算密集型及I/O消耗過大的難題。在該方法中,隨著計算節點數目的增加,其查詢時間隨之減少,有效地提升了分析效率。
關鍵詞:OLAP; what-if分析;分布式并行處理
0引言
what-if分析是決策者對多種決策方案進行預測或評估時的常用手段,通常以多種形式應用于不同的應用場景,尤其在決策系統中發揮重要作用。簡單地說,whatif分析就是以數據倉庫中歷史數據為基礎數據的假設分析,決策者根據決策目標制定一系列假設場景,通過對已有數據的假設分析得到假設場景下的商業數據變化情況。
近年來,隨著數據倉庫中數據的不斷膨脹,數據量從TB級增長到PB級甚至EB級別,決策者在海量的數據中挖掘價值,以便更快更準地捕獲商機,在很大程度上還需要借助whatif分析工具的應用。因此,基于OLAP的whatif分析一直受到很多學者的關注,但由于whatif分析自身的復雜性,至今未得到廣泛應用。在假設分析時通常需要更改Cube結構或修改Cube數據,這些操作均涉及到Cube重計算,花費時間較長,限制了whatif分析的能力。
隨著大規模并行處理關系數據庫的發展,如Vertica、微軟的SQL Server并行數據倉庫以及Greenplum數據倉庫等的使用,使高效的并行查詢處理及數據分析成為可能。因此,本文結合基于OLAP的whatif分析的特點,與分布式并行處理技術相結合,可以有效提高查詢效率,解決決策者面臨分析效率低的問題。
1相關研究工作
whatif分析的概念早已提出,由于其復雜性未得到廣泛應用,但是對其研究一直在進行中。參考文獻[1]中提出基于Delta表的whatif分析,通過預處理方法提高whatif分析效率,更改工作內容均是在內存數據庫中實現,而不是在基于磁盤的關系型數據庫中實現,其性能未得到明顯提升。參考文獻[2]在參考文獻[1]的基礎上,利用并行計算模型MapReduce實現whatif分析,其性能有一定的提升。隨著whatif分析的研究,參考文獻[34]分別將whatif分析應用于MapReduce的調優及復雜云數據中心的資源分配。參考文獻[5]詳細介紹了分布式并行處理整體方案。參考文獻[6]提出了內存數據庫中利用分布式并行處理技術實現OLAP并行操作的方案。本文中的whatif分析使用分布式并行處理技術,利用并行處理機制提升whatif分析性能。
2what-if分析
本節主要以OLAP模型中的星座模型為例,詳細介紹whatif分析中的基礎概念及實現方法,并分析其實現過程中存在的問題及擬解決方法。
2.1基于OLAP的what-if分析
基于OLAP的whatif分析實質是基于假設場景的OLAP查詢。在假設數據生成后,生成新的Cube,Cube通常有星型、星座和雪花等OLAP模型;基于新的Cube可以執行相應的OLAP操作,如Rollup。圖1為本文使用Foodmart數據的OLAP模型。
圖1中有2個事實表和6個維表。其中,sales_fact(product_id, time_id, customer_id, promotion_id, store_id, store_sales)、sales_fact_virtual(product_id, time_id, customer_id, promotion_id, store_id, store_sales, wbversion, sign)為兩個事實表。
sales_fact用于存儲數據庫中的歷史數據,在whatif分析中稱之為基表;sales_fact_virtual是與sales_fact結構相似的另一個事實表,叫delta表,用于存儲假設數據,這類的假設分析是基于delta表的whatif分析。由事實表可知,delta表是在基表的基礎上增加了多個字段,如wbversion和sign,wbversion表示版本號,sign為更新類型,其更新類型主要有插入(I)、更新(U)和刪除(D)三類,分別用1、0、-1值來表示。store_sales為度量值,其余均為維度值。
2.2what-if分析實現
本節主要介紹基于delta表的what-if分析的實現過程。首先,根據假設場景將假設數據存儲到delta表中;其次,將delta表與基表合并生成新的Cube,此步驟稱之為假設更新,也叫what-if更新;最后,基于新生成的Cube執行OLAP查詢操作。
對于基表與delta表的合并,常用的方法是通過等值連接、左連接和全連接等操作來實現。下面是依據2.1節中的OLAP模型通過使用連接操作來實現what-if分析。
在連接算法中,首先排除基表中受delta表D和U類更新影響的記錄,然后再與delta表中U類型和I類型的記錄合并。三種算法具體實現如下:
算法1等值連接算法
tmptable = sales_fact left(sf) join sales_fact_virtual(sfv)
for each tuple t in sf
output(t.product_id, t.time_id, t.customer_id, t.promotion_id, t.store_id, t.store_sales)->what-if_view_0
for each tuple t in tmptable
output(t.product_id, t.time_id, t.customer_id, t.promotion_id, t.store_id, t.store_sales)->what-if_view_1
for each tuple 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_sales)->what-if_view_2
return what-if_view_0 EXCEPT what-if_view_1 union all what-if_view_2
算法2左連接算法
tmptable = sales_fact left(sf) join sales_fact_virtual(sfv)
for each tuple t in tmptable
if t.sign is null then output(t.product_id, t.time_id, t.customer_id, t.promotion_id, t.store_id, t.store_sales)->what-if_view;
if t.sign=-1 then skip t;
for each tuple 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_sales)->what-if_view_1
return what-if_view union all what-if_view_1
算法3全連接算法
tmptable = sales_fact left(sf) join sales_fact_virtual(sfv)
for each tuple t in tmptable
if t.product_id is not null and t.sign is null then output (t.product_id, t.time_id, t.customer_id, t.promotion_id, t.store_id, t.store_sales) ->what-if_view
if t.product_id is not null and 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_sales(sfv)) ->what-if_view
return what-if_view;
通過連接操作執行假設更新后得到新的Cube,在基于Cube的OLAP查詢中,其OLAP查詢結果通常為group by 和order by所得的聚集結果值,涉及操作有MAX、MIN、SUM、COUNT等分布式聚集運算等。
綜上所述,在what-if分析的實現過程中,關鍵問題是如何高效地合并基表和delta表并執行OLAP操作。下節將介紹使用分布式并行處理來提高whatif分析的整體效率。
3分布式并行執行
3.1分布式并行處理
基于Sharednothing結構的分布式并行數據庫具有較好的可擴展性,圖2為本文使用的分布式并行數據庫集群架構,整個集群由多個數據節點(Segment Host)和控制節點(Master Host)組成。Master Host主要負責與客戶端的通信、對SQL進行分析以及生成執行計劃并分發到每個Segment上執行,最后將匯總結果反饋給客戶端;數據節點負責數據的存儲、存取以及執行Master分發的SQL語句,在每個數據節點上可以允許有多個數據庫。同時,各個節點之間的信息交互通過節點互聯網絡來實現。
分布式并行處理數據庫集群架構中,數據劃分方法對其并行處理的性能影響很大,大多采用的是哈希劃分法和范圍劃分法。文本中即采用了Hash劃分方式將數據分布到各個節點上。其劃分過程為:當數據存入數據庫時進行數據劃分處理,即根據表中的某一個或幾個字段的哈希值分布到每個節點。
在涉及連接操作運算的查詢中,利用分布式并行處理數據庫對查詢操作并行化,可以充分利用系統中所有的處理器和I/O處理能力,從而縮短查詢響應時間。利用分布式并行處理數據庫的優勢,大大減少了whatif分析合并中由于多表連接產生的大量開銷。
3.2what-if分析的并行執行
what-if分析的OLAP查詢中,涉及大量的聚集操作,針對可分布式執行的聚集函數,可將聚查詢分布到不同計算節點進行聚集計算,并將各個節點的聚集計算結果進行合并輸出。因此whatif分析的OLAP并行查詢可分為兩階段:一是提交查詢到多個子查詢節點上進行并行執行;二是合并查詢結果,然后輸出合并后的最終結果。
圖3為what-if分析中并行執行OLAP查詢的計算過程。在此并行查詢處理中,各處理節點均將查詢結果返給OLAP中間服務器,并計算出最終結果。
根據3.1節中數據劃分方法,每個屬性將被分布在不同的節點上。例如,當有n個節點時,針對屬性A,則有A=A1∪A2…∪An,在圖3的分布式聚集函數計算過程中,最終的計算結果是1~n個節點的計算結果的總和。在本文中,實現了常用的分布式聚集函數如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))
在分布式并行執行中,可以利用各計算節點的計算能力及I/O處理能力提高what-if分析的OLAP查詢效率,但與此同時,若將聚集函數轉換為可分布式計算的聚集函數時,額外的通信代價相應地也會增加。因此,在利用各節點處理能力的同時需要考慮其網絡開銷,換句話說,隨著節點在一定范圍的增加,查詢效率會有相應的提升,但當子節點過多時,隨著網絡開銷的逐漸增加其查詢效率將會受到一定的影響。
因此,本文一方面適當增加計算節點提高whatif分析的OLAP查詢效率,另一方面為防止網絡開銷的過度增加而控制計算節點數量。通過此方法,可以有效提高OLAP中所涉及分布式聚集操作。
4實驗及結果
4.1實驗環境
本文實驗包括兩部分,一是對2.2節中的三種連接算法實現what-if分析中基表與delta表合并的性能測試;二是對what-if分析中4種常用的分布式聚集函數的測試。
測試實驗為分布式并行處理,分配一個主節點,數據節點數分別為1、2、3、4、5,節點與物理機的分配方式分為兩種:一是主節點為單獨的物理機,將所有的數據節點放在同一物理機上;二是主節點和每個數據節點均放在不同的物理機上。所有物理機的配置相同,均為Centos6.4 64 bit的操作系統,16 GB內存,100 GB硬盤,Greenplum 4.3.5.2為底層數據庫。
在測試中,Foodmart數據集作為測試數據,事實表sales_fact的記錄數為80millions,sales_fact_virtual的記錄數占sales_fact的4%,并設置sales_fact_virtual中I類型、U類型、D類型占sales_fact_virtual總記錄數的30%、40%和30%。
4.2實驗結果
根據Segments節點與物理機的分配,分別測試whatif分析的3種實現算法的性能變化情況,圖4和圖5縱坐標均表示whatif分析中基表與delta表合并的時間。
圖4為所有的Segments節點在同一物理機時3種連接算法的執行結果。可以看出,隨著節點的增加,查詢響應時間逐漸縮減。
圖5為所有的Segments節點在不同的物理機上,與圖4類似,其性能隨節點增加而增加。比較圖4與圖5中的查詢響應時間,Segments位于不同的物理機上時,whatif分析的響應時間略顯優勢。主要是因為在不同物理機上,其CPU和I/O處理能力更強,但同時也增加了更多的網絡開銷。
兩種結果均表明,當數據節點為1時,其合并時間最高,約是數據節點為5時的5倍。
如圖6為4種分布式聚集函數的并行化執行結果,圖中的Segments放在相同配置的物理機上,當Segments節點數為5時,聚集函數所消耗的時間是單節點所消耗時間的1/4。由此可知,分布式并行執行能有效提高聚集運算的查詢效率,有利于whatif分析中執行的OLAP查詢性能的提高,使whatif分析效率進一步提升。
5結束語
分布式并行處理以其并行執行的優勢,廣泛應用于數據分析領域,可提升數據分析性能。文中詳細介紹使用連接算法實現whatif分析,并分析算法中影響其性能的瓶頸,利用分布式并行執行策略,即在whatif分析的存儲層使用分布式存儲架構,通過并行查詢處理機制,實現多連接查詢的并行化,以達到快速查詢的目的,從而提高whatif分析效率。最后,利用分布式并行執行策略對whatif分析中常用的SUM、COUNT、MAX、MIN等操作進行性能測試。
參考文獻
[1] Zhang Yansong, Zhang Yu, Xiao Yanqin, et al. The tradeoff of delta table merging and rewriting algorithms in whatif analysis application[C]. In Proc. APWeb/WAIM ′09, 2009:260272.
[2] Xu Huan, Luo Hao, He Jieyue. Whatif query processing policy for big data in OLAP system[C]. In Proc. CBD ′13, 2013:110116.
[3] HERODOTOU H, BABU S. Profiling, whatif analysis, and cost based optimization of MapReduce programs[C].Proc. of the VLDB Endowment, 2011:11111122.
[4] SINGH R, SHENOY P, NATU M, et al. Analytical modeling for whatif analysis in complex cloud computing applications[C]. SIGMETRICS Perform, 2013:5362.
[5] 金樹東,馮玉才. 并行數據庫系統原型PARO[J].計算機科學,1997,24(3):4145.
[6] 張延松,張宇,黃偉,等.分布式聚集函數支持的內存OLAP并行查詢處理技術[J].軟件學報,2009(20):165175.