潘鄭冰,戴牡紅

(湖南大學(xué)軟件學(xué)院,長沙410082)

實(shí)時數(shù)據(jù)倉庫中一種改進(jìn)的數(shù)據(jù)流更新算法

潘鄭冰,戴牡紅

(湖南大學(xué)軟件學(xué)院,長沙410082)

為實(shí)現(xiàn)數(shù)據(jù)倉庫中數(shù)據(jù)的高效集成,針對數(shù)據(jù)偏斜分布現(xiàn)象,提出一種改進(jìn)的數(shù)據(jù)流更新算法EH-JOIN。該算法對傳統(tǒng)散列連接方法進(jìn)行改進(jìn),利用索引將部分頻繁使用的主數(shù)據(jù)存儲在內(nèi)存中,解決了高速數(shù)據(jù)流下的磁盤頻繁訪問問題。實(shí)驗(yàn)結(jié)果表明,與MESHJOIN算法和R-MESHJOIN算法相比,EH-JOIN算法的服務(wù)速率在磁盤存儲關(guān)系集保持適當(dāng)大小時分別提高了96%和81%,在內(nèi)存大小不同時提高了57%和48%。

實(shí)時數(shù)據(jù)倉庫;數(shù)據(jù)轉(zhuǎn)換;數(shù)據(jù)流更新;基于流的連接;哈希索引;偏斜分布

1 概述

為給企業(yè)提供及時有效的決策支持,實(shí)時數(shù)據(jù)倉庫正在向數(shù)據(jù)新鮮度更高水平的方向發(fā)展,提供這些新的服務(wù)水平的工具和技術(shù)也正在迅速發(fā)展[1-2]。在實(shí)時數(shù)據(jù)倉庫的環(huán)境下,數(shù)據(jù)更新中連接運(yùn)算的選擇主要取決于源數(shù)據(jù)的來源以及到達(dá)速率。源數(shù)據(jù)可能是突發(fā)性很強(qiáng)的大容量數(shù)據(jù)流,這會帶來極大的磁盤I/O開銷。由于存儲在磁盤中查找表的訪問速率相對緩慢,因此在連接操作中會出現(xiàn)瓶頸[3]。

為解決該問題,文獻(xiàn)[4-5]提出一種MESHJOIN算法,特別針對一些如動態(tài)數(shù)據(jù)倉庫的連續(xù)數(shù)據(jù)流和存儲在磁盤中關(guān)系集的連接,但該算法對于連接組件之間的內(nèi)存分配不夠理想,而且訪問磁盤存儲關(guān)系采取的策略不夠高效。文獻(xiàn)[6]利用一種改進(jìn)的算法解決了連接部件中內(nèi)存的最佳分配問題。文獻(xiàn)[7]提出基于分塊的連接算法來改善MESHJOIN的性能,可以處理間歇的數(shù)據(jù)流。除此之外,還有一些研究更關(guān)注于實(shí)時數(shù)據(jù)流的連接響應(yīng)效率問題,如PMJ算法[8]和RPJ算法[9],都支持在不用完全排序的基礎(chǔ)上盡可能快地產(chǎn)生一小部分連接結(jié)果,以達(dá)到快速響應(yīng)的效果。文獻(xiàn)[10]采用多線程并發(fā)連接技術(shù),合理調(diào)度了實(shí)時元組和準(zhǔn)實(shí)時元組的執(zhí)行。文獻(xiàn)[11]提出一種支持服務(wù)質(zhì)量的更新和查詢的調(diào)度算法,實(shí)現(xiàn)了更新和查詢的實(shí)時調(diào)度。

雖然MESHJOIN算法能有效地分?jǐn)偪焖俚妮斎肓鲙淼拇疟PI/O開銷,但它不能適應(yīng)實(shí)際應(yīng)用中的一般特征,比如在許多市場上少數(shù)產(chǎn)品具有較高的購買頻率[12]。本文針對實(shí)際中常見的數(shù)據(jù)偏斜分布情況,提出一種改進(jìn)的數(shù)據(jù)流更新算法:擴(kuò)展混合連接算法(EH-JOIN)。EH-JOIN的關(guān)鍵特征是將存儲在磁盤的關(guān)系集使用最多的部分存在內(nèi)存中,使其與數(shù)據(jù)流中的頻繁項(xiàng)相匹配。

2 基于數(shù)據(jù)流的連接

數(shù)據(jù)連接作為實(shí)時數(shù)據(jù)倉庫的ETL(Extraction, Transformation,Loading)過程中常見的數(shù)據(jù)轉(zhuǎn)換操作,通常表示為SR,其中,S表示特定的數(shù)據(jù)源;表示特定的連接操作;R表示數(shù)據(jù)倉庫中的關(guān)系集合。如圖1所示,對于實(shí)時數(shù)據(jù)流中的數(shù)據(jù)更新來說,S包含內(nèi)容與到達(dá)速率都在不斷變換的數(shù)據(jù)元組,到達(dá)的每一個元組都要和R完成連接操作。R是一個包含了大量主數(shù)據(jù)的關(guān)系集合,通常存儲在磁盤中。在實(shí)際連接操作中,由于內(nèi)存大小的限制,R不能全部導(dǎo)入到內(nèi)存中,因此必須將R中的元組不停地讀入有限的內(nèi)存中,這就帶來了巨大的I/O開銷。當(dāng)磁盤I/O速率比數(shù)據(jù)元組的到達(dá)速率慢時,就會造成連接操作的瓶頸,影響ETL的實(shí)時性。在MESHJOIN算法中,盡管R中的數(shù)據(jù)元組是分批讀入到內(nèi)存中的,這有助于分?jǐn)侷/O開銷,但對于每一批數(shù)據(jù)流元組,R都需完整地讀入到內(nèi)存中。而實(shí)際情況并不是R中所有元組都要和數(shù)據(jù)流中的數(shù)據(jù)元組做連接操作,這就導(dǎo)致很多無效元組被讀入內(nèi)存中,帶來了很多無效的磁盤I/O。

圖1 基于數(shù)據(jù)流連接的實(shí)例

3 一種改進(jìn)的數(shù)據(jù)流更新算法EH-JOIN

3.1 基于索引的哈希連接結(jié)構(gòu)

相比MESHJOIN,EH-JOIN有2個關(guān)鍵的改進(jìn): (1)修改了Hash連接組件讓它可以利用索引。(2)將頻繁使用的主數(shù)據(jù)緩存到內(nèi)存中,極大地減少了I/O消耗。

EH-JOIN將基于磁盤存儲的關(guān)系集R和數(shù)據(jù)流S相連接。假設(shè)R的連接屬性有一個非聚集索引,并且這個連接屬性對于主數(shù)據(jù)來說是唯一的。這種假設(shè)是很自然的,并且符合常見的應(yīng)用領(lǐng)域,比如在密鑰交換中。

EH-JOIN算法的體系結(jié)構(gòu)如圖2所示。該算法主要消耗內(nèi)存的部分為磁盤緩存、哈希表、隊(duì)列和數(shù)據(jù)流緩存,而存儲在磁盤中的關(guān)系集R和數(shù)據(jù)流S作為輸入流。假設(shè)R擁有連接屬性的索引作為鍵。該算法將數(shù)據(jù)流元組存在哈希表中,該哈希表占用的算法內(nèi)存最多。此外,本文算法還為數(shù)據(jù)元組提供了標(biāo)識符,并將這些標(biāo)示符存入隊(duì)列中,tm隊(duì)列需要支持隨機(jī)刪除,最簡單的實(shí)現(xiàn)方法是雙向鏈表。

圖2 EH-JOIN算法的體系結(jié)構(gòu)

EH-JOIN是一種迭代算法,在每次迭代中,磁盤關(guān)系集R的一個分塊作為一個探測輸入。因此,這個分塊被裝載到磁盤緩存中且僅占用磁盤緩存的一部分。之后,本文算法執(zhí)行了一個典型的哈希連接操作,即它遍歷磁盤緩沖區(qū)的所有元組,并在哈希表中進(jìn)行查找。每一次匹配成功,算法就會輸出那個匹配的數(shù)據(jù)流元組。

同樣地,在每次迭代中,EH-JOIN都會彈出匹配的元組。假設(shè)聯(lián)接屬性是R中唯一證明這個操作正確性的屬性。彈出一個元組意味著同時從哈希表和隊(duì)列中刪除這個元組。本文算法還保留一個計數(shù)器ω來計算彈出元組的數(shù)目。在處理完整個磁盤緩存后,算法從數(shù)據(jù)流緩沖中讀取ω個新元組,將它們裝入哈希表中同時在隊(duì)列中插入標(biāo)識符。

為選擇R中的下一個分塊,EH-JOIN考慮隊(duì)列中最舊的數(shù)據(jù)流元組的連接屬性。利用索引,把R中具有該連接屬性值的分塊加載到磁盤緩存中,這樣每個加載分塊都至少可以和一個數(shù)據(jù)流元組匹配,進(jìn)一步保持它的自適應(yīng)性。

與MESHJOIN一樣,EH-JOIN能在任何數(shù)據(jù)分布情況下工作。然而,在實(shí)踐中,某些特定分布十分常見。目前研究表明,銷售數(shù)據(jù)通常服從冪次法則,或者Zipfian分布[11]。符合冪次法則分布的主要區(qū)別在于它們的指數(shù)。指數(shù)等于1時,得到的分布滿足Zipf定律,也就是通常所說的Zipfian分布。在商業(yè)中,80/20規(guī)則被用于模擬場景,當(dāng)少量商品的出售頻率遠(yuǎn)高于其他產(chǎn)品時,往往簡化成80/20規(guī)則[11],該規(guī)則在商業(yè)應(yīng)用中非常普遍。80/20規(guī)則對應(yīng)于一個指數(shù)略小于1的冪次分布情況。

3.2 EH-JOIN算法

EH-JOIN算法具體如下:

輸入 磁盤存儲帶有索引的關(guān)系集R以及更新數(shù)據(jù)流S

輸出 S與R的連接

參數(shù) S中ω個元組以及R中的一個分塊pi

一旦將內(nèi)存分配給連接組件,就開始按照上述步驟執(zhí)行算法。在開始實(shí)際連接操作前,本文算法先將磁盤存儲的關(guān)系集R中的一部分讀進(jìn)磁盤緩存的非交換區(qū)(第1行)。一開始,哈希表H是空的;因此,將hS賦給ω(第2行)。本文算法包含2層循環(huán)。一個是外層循環(huán),這是一個無限循環(huán)(第3行)。外層循環(huán)的主要目的是把數(shù)據(jù)流壓入到哈希表中。在外層循環(huán)中,還有2個獨(dú)立的內(nèi)層循環(huán)。一個是實(shí)現(xiàn)磁盤緩存非交換區(qū)的探測功能,另一個是實(shí)現(xiàn)磁盤緩存交換區(qū)的探測功能。外層循環(huán)一啟動,算法就開始觀測數(shù)據(jù)流緩存的狀態(tài)。如果數(shù)據(jù)流可以讀取,算法就從數(shù)據(jù)流緩存中讀取ω個元組存入哈希表中,并將它們的屬性值存入隊(duì)列中。讀完后算法將ω重設(shè)為0(第4行～第7行),然后開始執(zhí)行第一個內(nèi)層循環(huán),遍歷磁盤緩存的非交換區(qū)中的所有元組并在哈希表中查找它們。一旦有元組匹配,就產(chǎn)生一個連接輸出。由于采用多重哈希映射表,因此一個磁盤元組可能有多個數(shù)據(jù)元組匹配。產(chǎn)生連接輸出后,就從哈希表中刪除所有匹配過的元組,并且從隊(duì)列中刪除它們對應(yīng)的節(jié)點(diǎn)。哈希表中每刪除一個元組,計數(shù)器ω就加1(第8行～第13行)。在開始第二個內(nèi)層循環(huán)之前,算法讀取隊(duì)列中最舊的連接屬性值,利用這個連接屬性值作為索引將磁盤分塊pi(2≤i≤n)讀到磁盤緩存的交換區(qū)中(第14行～第15行)。當(dāng)特定的磁盤分塊被讀入到磁盤緩存的交換區(qū)后,算法開始執(zhí)行第二個內(nèi)層循環(huán),然后開始重復(fù)上述第一個內(nèi)層循環(huán)的所有步驟(第16行～第21行)。

4 實(shí)驗(yàn)結(jié)果與分析

本文通過實(shí)驗(yàn)比較EH-JOIN算法和MESHJOIN算法,使用已知傾斜分布的合成數(shù)據(jù)集來做測試。

4.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)設(shè)置具體如下:

(1)硬件說明:實(shí)驗(yàn)采用酷睿2處理器,2.13 GHz主頻,4 GB內(nèi)存,操作系統(tǒng)是Window XP,分配給測試程序的最大內(nèi)存為250 MB。算法用Java實(shí)現(xiàn),實(shí)驗(yàn)使用Apache內(nèi)置插件和Java API,測量內(nèi)存消耗和處理時間。

(2)數(shù)據(jù)說明:實(shí)驗(yàn)用指數(shù)為1的Zipf’s法則生成的數(shù)據(jù)來測試算法。所生成的數(shù)據(jù)流具有突發(fā)性和自相似性。本文使用MYSQL5.0數(shù)據(jù)庫將關(guān)系集R存儲在磁盤中,其中,關(guān)系集R大小為50萬～800萬個元組不等,每個元組為120 Byte,流數(shù)據(jù)中一個元組為20 Byte,隊(duì)列的一個節(jié)點(diǎn)為12 Byte。為準(zhǔn)確測量每一次I/O操作中的開銷,將提取結(jié)果集合的大小和磁盤上一個分區(qū)的大小設(shè)置為相同。EH-JOIN算法需要在哈希表中一個鍵對應(yīng)多個值,實(shí)驗(yàn)通過Apache提供的多重哈希映射表來實(shí)現(xiàn)。

(3)評價策略:定義服務(wù)速率作為算法的性能判斷標(biāo)準(zhǔn),服務(wù)速率越高,算法性能越好。服務(wù)速率是每秒中被處理的數(shù)據(jù)元組的個數(shù)。每次實(shí)驗(yàn)算法執(zhí)行1 h。實(shí)驗(yàn)開始20 min后開始測量,連續(xù)測量20 min。為增加準(zhǔn)確性,本文實(shí)驗(yàn)對每種規(guī)格采集3種數(shù)據(jù),然后計算出平均值。

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

將EH-JOIN算法與MESHJOIN算法、R-MESHJOIN算法進(jìn)行實(shí)驗(yàn),比較結(jié)果如下:

(1)性能比較:能夠直接影響算法性能的2個參數(shù)是可用內(nèi)存總量以及磁盤存儲的關(guān)系集大小。在實(shí)驗(yàn)中,測試不同參數(shù)對算法的影響,并比較它們的性能。

(2)不同大小磁盤存儲關(guān)系集下的性能比較,如圖3所示,假設(shè)分配給連接的內(nèi)存大小是固定的,同時磁盤存儲的關(guān)系集大小呈指數(shù)級增長。如圖3(a)所示,對于所有不同大小的關(guān)系集R,EH-JOIN的性能總體優(yōu)于所有其他算法。在R保持適當(dāng)大小時, EH-JOIN算法的服務(wù)速率比MESHJOIN算法提高了96%,比R-MESHJOIN算法提高了81%,即使由于R逐漸增到導(dǎo)致算法性能降低時,EH-JOIN相對于其他算法性能仍具有一定優(yōu)勢。

(3)可用內(nèi)存大小不同時的性能比較:在第(2)組實(shí)驗(yàn)中,關(guān)系集R的大小固定為2×107個元組,分析EH-JOIN使用不同大小內(nèi)存時的性能。實(shí)驗(yàn)結(jié)果如圖3(b)所示。

圖3 算法性能比較

實(shí)驗(yàn)數(shù)據(jù)表明,對于不同的內(nèi)存大小,EH-JOIN的性能明顯優(yōu)于其他算法。在相同條件下,EHJOIN算法的服務(wù)速率比MESHJOIN算法提高了57%,比R-MESHJOIN算法提高了48%?？梢?EHJOIN在磁盤緩存中保持一個交換區(qū)和一個非交換區(qū)對性能提升有較大作用。

非交換部分在數(shù)據(jù)流處理中的作用:為更好地了解磁盤緩存中非交換部分的作用,統(tǒng)計僅用磁盤緩存中的非交換部分處理的數(shù)據(jù)流元組,實(shí)驗(yàn)結(jié)果如圖4所示,設(shè)置非交換部分的大小和交換部分的大小一樣。

圖4 4 000次迭代中非交換區(qū)處理的數(shù)據(jù)元組總量

從圖4可以看出,在4 000次迭代中,當(dāng)內(nèi)存大小為50 MB,關(guān)系集R的大小為2×107個元組時,大約4×104個數(shù)據(jù)流元組要通過磁盤緩存中的非交換部分處理,而且如果實(shí)驗(yàn)增大整體分配的內(nèi)存,那么這個數(shù)量還會增加。對于250 MB內(nèi)存和同樣大小的關(guān)系集R,這個數(shù)量會達(dá)到2×107以上。在其他算法中,由于這種非交換的部分每次從磁盤中載入,因此I/O成本會明顯增加。

5 結(jié)束語

偏斜分布的數(shù)據(jù)集在實(shí)際應(yīng)用場景中十分常見,而經(jīng)典的MESHJOIN算法在這種數(shù)據(jù)集上進(jìn)行連接操作的性能很差,因此,本文提出一種改進(jìn)的數(shù)據(jù)流更新算法EH-JOIN,該算法使用磁盤存儲的主數(shù)據(jù)的索引結(jié)構(gòu)來迅速存取磁盤分塊,并且緩存了主數(shù)據(jù)中使用最頻繁的元組匹配數(shù)據(jù)流中的頻繁項(xiàng),大大減少了磁盤的訪問量。實(shí)驗(yàn)結(jié)果表明,在不同磁盤關(guān)系集或者不同內(nèi)存大小下,該算法都能在性能上得到較好的提升。在今后工作將進(jìn)一步提高算法的內(nèi)存使用效率。

[1] Karakasidis A,Vassiliadis P,Pitoura E.ETL Queues for Active Data Warehousing[C]//Proc.ofthe 2nd InternationalWorkshop on Information Quality in Information Systems.New York,USA:ACM Press, 2005:28-39.

[2] 林子雨,楊冬青,宋國杰,等.實(shí)時主動數(shù)據(jù)倉庫中的變化數(shù)據(jù)捕捉研究綜述[J].計算機(jī)研究與發(fā)展, 2007,44(z3):447-451.

[3] Golab L,Johnson T,SeidelJ S,etal.Stream Warehousing with Data Depot[C]//Proc.of the 35th SIGMOD International Conference on Management of Data.New York,USA:ACM Press,2009:847-854.

[4] Polyzotis N,Skiadopoulos S,Vassiliadis P,etal. Supporting Streaming Updatesin an Active Data Warehouse[C]//Proc.of the 23rd International Conference on Data Engineering.New Jersey,USA: IEEE Computer Society,2007:476-485.

[5] Polyzotis N,Skiadopoulos S,Vassiliadis P,etal. Meshing Streaming Updates with Persistent Data in an Active Data Warehouse[J].IEEE Transactions on Knowledge and DataEngineering,2008,20(7): 976-991.

[6] Naeem M,Dobbie G,Weber G.R-MESHJOIN for Nearreal-time Data Warehousing[C]//Proc.of the 13th InternationalWorkshop on Data Warehousing and OLAP.New York,USA:ACM Press,2010:53-60.

[7] Chakraborty A,Singh A.A Partition-based Approach to Support Streaming Up-dates over Persistent Data in an Active Data Warehouse[C]//Proc.of 2009IEEE InternationalSymposium on Parallel& Distributed Processing.Washington D.C.,USA:IEEE Computer Society,2009:1-11.

[8] Chandrasekaran S,Franklin M J.PSoup:A System for Streaming Queries over Streaming Data[J].The VLDB Journal,2003,12(2):140-156.

[9] Tao Yufei,Yiu M,Papadias D.Producing Fast Join Results on Streams Through Rate-based Optimization [C]//Proc.of ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press, 2005:371-382.

[10] 林子雨,林 琛,馮少榮,等.MESHJOIN*:實(shí)時數(shù)據(jù)倉庫環(huán)境下的數(shù)據(jù)流更新算法[J].計算機(jī)科學(xué)與探索,2010,4(10):927-939.

[11] 師金鋼,鮑玉斌,冷芳玲,等.實(shí)時數(shù)據(jù)倉庫中支持QoS的更新和查詢?nèi)蝿?wù)調(diào)度[J].小型微型計算機(jī)系統(tǒng),2011,32(5):801-806.

[12] Erik B,Hu Yu,Duncan S.Goodbye Pareto Principle, Hello Long Tail:The Effect of Search Costs on the Concentration ofProductSales[J].Management Science,2011,57(8):1373-1386.

編輯 陸燕菲

An Improved Data Stream Update Algorithm in Real-time Data Warehouse

PAN Zheng-bing,DAI Mu-hong
(College of Software,Hunan University,Changsha 410082,China)

To achieve data efficient integration in data warehouse,aiming at the phenomenon of data skew distribution,this paper proposes an improved data stream update algorithm——Extended Hybrid Join(EH-JOIN).The algorithm improves the traditional Hash join method,and it can adapt to common skewed data and greatly reduce the disk I/O cost through using index structure and storing some parts of the master data in memory.Experimental results show that the service rate of proposed algorithm is improved by 96%and 80%compared with MESHJOIN algorithm and R-MESHJOUIN algorithm as the relation set keeps an appropriate size,and the service rate of proposed algorithm is improved by 57%and 48%compared with MESHJOIN algorithm and R-MESHJOUIN algorithm as the memory size differs.

real-time data warehouse;data transformation;data stream update;stream-based join;Hash index; skewed distribution

1000-3428(2014)10-0043-04

A

TP311.13

10.3969/j.issn.1000-3428.2014.10.009

湖南省自然科學(xué)基金資助項(xiàng)目(2011FJ3034)。

潘鄭冰(1988-),女,碩士研究生,主研方向:數(shù)據(jù)庫技術(shù),決策支持,知識工程;戴牡紅,副教授。

2013-08-13

2013-10-12E-mail:panzhengbing@163.com

中文引用格式:潘鄭冰,戴牡紅.實(shí)時數(shù)據(jù)倉庫中一種改進(jìn)的數(shù)據(jù)流更新算法[J].計算機(jī)工程,2014,40(10):43-46,51.

英文引用格式:Pan Zhengbing,Dai Muhong.An Improved Data Stream Updating Algorithm in Real-time Data Warehouse[J].Computer Engineering,2014,40(10):43-46,51.