基于Hadoop集群的多表并行關聯算法及應用

鄭曉薇，馬 琳

（遼寧師范大學 計算機與信息技術學院，遼寧 大連116081）

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

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

本文基于Hadoop集群，設計了一個適合多個大數據表并行關聯的簡便算法MR_Join。以商業網站凡客誠品的銷售數據表為例進行實驗，實驗結果顯示Hadoop具有在處理網絡下大數據表關聯的優勢，也驗證了MR_Join算法的可行性。集群中各個計算節點并行處理，處理速度快、延遲低且易于操作。

1 MR_Join關聯算法設計

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

1.1 MR_Join大數據表并行關聯算法

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

圖1 MR_Join大數據表關聯計算流程

1.2 MR_Join算法應用實例

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

MR_Join算法處理數據基本流程如圖2所示。

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

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

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

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

2 實驗結果及分析

2.1 實驗環境

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

2.2 實驗內容及結果分析

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

(2)多節點并行測試。圖3為單節點環境與雙節點環境下MR_Join算法執行時間對比，表1為MR_Join算法多節點并行執行效果分析表。P為集群節點數目。

實驗結果顯示出3對不同規模的大數據表關聯時，并行效率與集群的節點數目成正比，且隨著表數據規模的增大而增大。當表數據規模較低時，利用Hadoop集群執行大數據表關聯效率低。當表數據規模較大時，利用Hadoop集群并行執行計算，在節點數為4時可達到78.2%的并行效率。說明在表數據規模和Hadoop集群節點數目選擇適當的情況下，本文設計的MR_Join算法可以取得良好的并行效率。

表1 MR_Join算法多節點并行執行效果分析表

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

[1]王珊，王會舉，覃雄派，等.架構大數據：挑戰、現狀與展望[J].計算機學報，2011，34(10)：1741-1751.

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

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

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

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

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