基于Hadoop集群的多表并行關(guān)聯(lián)算法及應(yīng)用

鄭曉薇，馬 琳

（遼寧師范大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，遼寧 大連116081）

近年來，隨著網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，具有價位合理、購買便捷等優(yōu)勢的電子商務(wù)迎來了嶄新的春天。商品交易市場正從賣家市場轉(zhuǎn)向買家市場，消費(fèi)者面對種類繁多的商業(yè)網(wǎng)站及產(chǎn)品有更多的選擇性，商家只有把握顧客才能達(dá)到企業(yè)盈利的目的。深層挖掘網(wǎng)站交易數(shù)據(jù)信息有利于營銷決策的制定，多個大數(shù)據(jù)表關(guān)聯(lián)并轉(zhuǎn)換成適合挖掘的形式是必要步驟。常見的方法是使用并行數(shù)據(jù)庫[1]，但由于其架設(shè)和調(diào)優(yōu)難度大、對異構(gòu)硬件的支持有限、成本高以及需要對數(shù)據(jù)的存儲進(jìn)行格式定義等缺陷導(dǎo)致了其處理因特網(wǎng)中多個大數(shù)據(jù)表關(guān)聯(lián)時使用不便。

Mapreduce是一種分布式并行編程模型，Apache開源社區(qū)的Hadoop項(xiàng)目是一個使用Java語言實(shí)現(xiàn)Mapreduce模型的開源平臺。近年來，基于Hadoop平臺在Web日志挖掘[2]、微博信息挖掘[3]、搜索引擎用戶行為分析[4]、城市交通碳排放數(shù)據(jù)挖掘研究[5]等方面都有很多應(yīng)用。與并行數(shù)據(jù)庫相比，Hadoop集群不需要對數(shù)據(jù)的存儲進(jìn)行格式定義，可將大數(shù)據(jù)表分解到各個計(jì)算節(jié)點(diǎn)，由各節(jié)點(diǎn)并行執(zhí)行，集群監(jiān)控各個計(jì)算節(jié)點(diǎn)的任務(wù)狀態(tài)，具有高容錯性和高擴(kuò)展性。同時，Hadoop滿足數(shù)據(jù)的多級計(jì)算和處理，可有效解決“一個程序的輸出是另外一個程序的輸入”這類復(fù)雜的數(shù)據(jù)挖掘。

本文基于Hadoop集群，設(shè)計(jì)了一個適合多個大數(shù)據(jù)表并行關(guān)聯(lián)的簡便算法MR_Join。以商業(yè)網(wǎng)站凡客誠品的銷售數(shù)據(jù)表為例進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果顯示Hadoop具有在處理網(wǎng)絡(luò)下大數(shù)據(jù)表關(guān)聯(lián)的優(yōu)勢，也驗(yàn)證了MR_Join算法的可行性。集群中各個計(jì)算節(jié)點(diǎn)并行處理，處理速度快、延遲低且易于操作。

1 MR_Join關(guān)聯(lián)算法設(shè)計(jì)

Hadoop的兩個核心部分是分布式文件系統(tǒng)HDFS和Mapreduce模型。HDFS為分布式計(jì)算提供了底層存儲支持，易于讀取大規(guī)模的數(shù)據(jù)文件。Hadoop集群由一個NameNode和一組DataNode組成，采取Master/Slave的架構(gòu)。Mapreduce分布式并行編程模型的基本思想源于函數(shù)式編程語言[6]，Map和Reduce是該模型的兩大基本操作。Map函數(shù)指定各分塊數(shù)據(jù)的處理過程并映射出中間結(jié)果，Reduce函數(shù)指定如何對中間結(jié)果進(jìn)行歸約并生成最終的處理結(jié)果。其概念可以表達(dá)為：Map〈k1，v1〉list〈k2,v2〉；Reduce〈k2，list(v2)〉list(v2)；

1.1 MR_Join大數(shù)據(jù)表并行關(guān)聯(lián)算法

MR_Join算法是一種關(guān)聯(lián)有相同表主鍵的表的關(guān)聯(lián)方法，其計(jì)算流程如圖1所示。算法思路為：被處理的多個表應(yīng)具有相同的表主鍵，算法首先判斷輸入的數(shù)據(jù)塊歸屬于哪個表，同一個表的數(shù)據(jù)塊由同一個Map處理。Map操作把表數(shù)據(jù)拆分成以表主鍵為Key值的鍵值對，Reduce操作把具有相同Key值的鍵值對聚合在一起。最后從各個表中分別選取一個屬性（選取的屬性之間應(yīng)存在直接聯(lián)系），將屬性值進(jìn)行運(yùn)算得到一個新屬性的屬性值，在運(yùn)算過程中實(shí)現(xiàn)數(shù)據(jù)表關(guān)聯(lián)。在Hadoop集群中，NameNode節(jié)點(diǎn)分配計(jì)算任務(wù)給各個DataNode，多個DataNode并行執(zhí)行計(jì)算任務(wù)，達(dá)到短時間內(nèi)快速準(zhǔn)確地完成兩個大數(shù)據(jù)表關(guān)聯(lián)的效果，生成一個可以有效分析的大數(shù)據(jù)表。本文采用Java語言實(shí)現(xiàn)MR_Join算法。

圖1 MR_Join大數(shù)據(jù)表關(guān)聯(lián)計(jì)算流程

1.2 MR_Join算法應(yīng)用實(shí)例

本文以消費(fèi)網(wǎng)站凡客誠品的商品信息和銷售數(shù)據(jù)為例，數(shù)據(jù)獲取的方式采用Web爬蟲方式。Web爬蟲通過訪問凡客誠品網(wǎng)站的Web頁面，解析頁面相關(guān)內(nèi)容和頁面源代碼，獲取所需的數(shù)據(jù)信息，生成商品屬性Product表和購買商品的用戶信息Sale表，并以文本文件的形式輸出數(shù)據(jù)表。兩個數(shù)據(jù)表的“商品編號”字段作為主鍵，并根據(jù) Product表的“單價”和 Sale表的“數(shù)量”計(jì)算出“總價格”，計(jì)算結(jié)果按照“商品編號”升序排序。兩個表相連能夠顯現(xiàn)出購買每種商品的用戶信息和該用戶的消費(fèi)總價格，有利于商家對客戶進(jìn)行歸類及后續(xù)對應(yīng)的商品營銷。Reduce操作按“商品編號”對計(jì)算結(jié)果升序排序，同類商品銷售情況一目了然，為下一步的市場營銷策劃提供客觀依據(jù)。

MR_Join算法處理數(shù)據(jù)基本流程如圖2所示。

(1)定義Product ID為商品表的“商品編號”字段，Sale ID為用戶表的“商品編號”字段。num為用戶表的“數(shù)量”字段，在 Product表中num值為0。“總價格”是通過“單價”和“數(shù)量”之間的運(yùn)算得到的新字段。

(2)算法默認(rèn)逐行讀取表記錄并將記錄偏移量及該行記錄內(nèi)容映射為初始鍵值對。Map操作對初始鍵值對進(jìn)行處理，提取出“商品編號”形成中間鍵值對，生成〈(Product ID,num)記錄內(nèi)容〉或〈(Sale ID,num)記錄內(nèi)容〉。

(3)Shuffle和Sort操作把具有相同鍵值的鍵值對合并分組，其結(jié)果作為Reduce操作的輸入鍵值對。

(4)Reduce操作將相同鍵值的鍵值對聚集，由于Web爬蟲在爬取信息記錄時，消費(fèi)數(shù)量是生成相同數(shù)量的相同消費(fèi)記錄，所以Reduce過程先對Sale表的鍵值對進(jìn)行 For循環(huán)計(jì)算“數(shù)量”，再用 For循環(huán)作相乘運(yùn)算計(jì)算“總價格”。 總價格=（Sale表）num×（Product表）單價。

2 實(shí)驗(yàn)結(jié)果及分析

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

本實(shí)驗(yàn)運(yùn)行在4臺PC機(jī)搭建的Hadoop集群上，均為同等配置。各節(jié)點(diǎn)名分別為 Master、Slave01、Slave02和Salve03。各個節(jié)點(diǎn)均安裝了 Hadoop-0.20.2和JDK。在Hadoop搭建的集群系統(tǒng)上運(yùn)行了本文開發(fā)的MR_Join算法。本實(shí)驗(yàn)分別在單機(jī)、多個節(jié)點(diǎn)集群中運(yùn)行。實(shí)驗(yàn)數(shù)據(jù)是利用Web爬蟲在凡客誠品網(wǎng)站獲取的2012年4月份的商品信息和銷售數(shù)據(jù)。

2.2 實(shí)驗(yàn)內(nèi)容及結(jié)果分析

(1)單節(jié)點(diǎn)測試。分別執(zhí)行了200 MB、500 MB、1.1 GB和1.5 GB 4種大小不同的商品屬性表和用戶信息表的關(guān)聯(lián)。通過圖3可以發(fā)現(xiàn)，200 MB表文件的執(zhí)行時間比500 MB表文件的執(zhí)行時間長，之后隨著表文件規(guī)模的增大，算法執(zhí)行的時間也相應(yīng)地增加。說明當(dāng)數(shù)據(jù)規(guī)模較低時，由于Hadoop框架啟動時間長、開銷較大，執(zhí)行效率低。當(dāng)數(shù)據(jù)規(guī)模增大時，執(zhí)行效率逐漸增大。

(2)多節(jié)點(diǎn)并行測試。圖3為單節(jié)點(diǎn)環(huán)境與雙節(jié)點(diǎn)環(huán)境下MR_Join算法執(zhí)行時間對比，表1為MR_Join算法多節(jié)點(diǎn)并行執(zhí)行效果分析表。P為集群節(jié)點(diǎn)數(shù)目。

實(shí)驗(yàn)結(jié)果顯示出3對不同規(guī)模的大數(shù)據(jù)表關(guān)聯(lián)時，并行效率與集群的節(jié)點(diǎn)數(shù)目成正比，且隨著表數(shù)據(jù)規(guī)模的增大而增大。當(dāng)表數(shù)據(jù)規(guī)模較低時，利用Hadoop集群執(zhí)行大數(shù)據(jù)表關(guān)聯(lián)效率低。當(dāng)表數(shù)據(jù)規(guī)模較大時，利用Hadoop集群并行執(zhí)行計(jì)算，在節(jié)點(diǎn)數(shù)為4時可達(dá)到78.2%的并行效率。說明在表數(shù)據(jù)規(guī)模和Hadoop集群節(jié)點(diǎn)數(shù)目選擇適當(dāng)?shù)那闆r下，本文設(shè)計(jì)的MR_Join算法可以取得良好的并行效率。

表1 MR_Join算法多節(jié)點(diǎn)并行執(zhí)行效果分析表

大數(shù)據(jù)表關(guān)聯(lián)后產(chǎn)生的數(shù)據(jù)表是企業(yè)數(shù)據(jù)挖掘和營銷決策制定的重要數(shù)據(jù)基礎(chǔ)。本文設(shè)計(jì)的MR_Join算法以商業(yè)網(wǎng)站凡客誠品的商品銷售數(shù)據(jù)為例進(jìn)行實(shí)驗(yàn)，成功實(shí)現(xiàn)了大數(shù)據(jù)表關(guān)聯(lián)。實(shí)驗(yàn)結(jié)果表明，Hadoop集群對于并行執(zhí)行計(jì)算任務(wù)的高容錯性及高度可擴(kuò)展性使得大數(shù)據(jù)表關(guān)聯(lián)的結(jié)果準(zhǔn)確且并行效率顯著，避免了并行數(shù)據(jù)庫在因特網(wǎng)環(huán)境下實(shí)現(xiàn)表關(guān)聯(lián)的弊端，可以在電子商務(wù)的商業(yè)應(yīng)用中體現(xiàn)更高的價值。現(xiàn)今Hadoop已經(jīng)被廣泛應(yīng)用于海量數(shù)據(jù)存儲和分析、互聯(lián)網(wǎng)服務(wù)、搜索引擎等。本文針對Hadoop下的大數(shù)據(jù)表關(guān)聯(lián)作了有益的嘗試，本文的算法也可以用于其他相關(guān)應(yīng)用中。

[1]王珊，王會舉，覃雄派，等.架構(gòu)大數(shù)據(jù)：挑戰(zhàn)、現(xiàn)狀與展望[J].計(jì)算機(jī)學(xué)報，2011，34(10)：1741-1751.

[2]程苗，陳華平.基于 Hadoop的 Web日志挖掘[J].計(jì)算機(jī)工程，2011，37(11)：37-39.

[3]林大云.基于Hadoop的微博信息挖掘[J].計(jì)算機(jī)光盤軟件與應(yīng)用，2012(1)：7-8.

[4]王振宇，郭力.基于Hadoop搜索引擎用戶行為分析[J].計(jì)算機(jī)工程與科學(xué)，2011，33(4)：115-120.

[5]朱鑰，賈思奇，張俊魁，等.基于 Hadoop的城市交通碳排放數(shù)據(jù)挖掘研究[J].計(jì)算機(jī)應(yīng)用研究，2011，28(11)：4213-4215.

[6]謝桂蘭，羅省賢.基于 Hadoop Mapreduce模型的應(yīng)用研究[J].微型機(jī)與應(yīng)用，2010，29(8)：4-7.