李敏

【摘要】本論文針對海量數(shù)據(jù)的處理分析設(shè)計了相應(yīng)的算法，主要是通過預(yù)處理、分布緩存和復(fù)用中間結(jié)果三種方法對MapReduce算法進(jìn)行優(yōu)化處理。本文的實驗部分會對房價方面的數(shù)據(jù)用hash算法進(jìn)行分析和處理。通過實驗得出結(jié)論，該算法可以處理海量數(shù)據(jù)。

【關(guān)鍵詞】海量數(shù)據(jù) MapReduce算法 hash

一、背景以及現(xiàn)狀

隨著互聯(lián)網(wǎng)的發(fā)展，在許多科學(xué)領(lǐng)域，信息數(shù)量呈指數(shù)型增長。截止到2011年全球信息總量為1.8ZB[1]。海量數(shù)據(jù)的時代已經(jīng)來臨，然而面對海量數(shù)據(jù)該如何存儲，如何有效的處理，及時有效的處理了這些數(shù)據(jù)對于各行各業(yè)乃至整個社會的發(fā)展有著重要的意義。過去的幾年里單機(jī)的性能得到發(fā)展，硬件也得到發(fā)展。但在理論上這些硬件技術(shù)的發(fā)展是有限的。現(xiàn)今的多核技術(shù)就是并行技術(shù)發(fā)展的一個實例[2]。

二、MapReduce的技術(shù)特征

1）橫向擴(kuò)展與縱向擴(kuò)展。對于MapReduce集群的構(gòu)建采用低廉且容易擴(kuò)展的低端商用服務(wù)器，考慮到大量數(shù)據(jù)存儲的需要，基于低端服務(wù)器的集群遠(yuǎn)比基于高端服務(wù)器的集群優(yōu)越，所以基于低端服務(wù)器實現(xiàn)都會使用MapReduce并行計算集群。

2）失效與常態(tài)。相對低端的服務(wù)器適用于MapReduce集群，無論哪個節(jié)點失效，其他的節(jié)點要無縫接管著失效節(jié)點的計算任務(wù)；當(dāng)該節(jié)點恢復(fù)以后將不需要人工配置而是能自動無縫加入集群。

3）處理向數(shù)據(jù)遷移。MapReduce采取數(shù)據(jù)與代碼互定位的技術(shù)時，計算節(jié)點首先計算其本地存儲的數(shù)據(jù)并對其負(fù)責(zé)使數(shù)據(jù)發(fā)揮本地化的特點。

三、對MapReduce改進(jìn)

（一）預(yù)處理算法

大量事實證明，在數(shù)據(jù)挖掘中整個工作量的60%到80%都是數(shù)據(jù)預(yù)處理[3]。通過數(shù)據(jù)預(yù)處理工作可以使殘缺的數(shù)據(jù)變得完整，能達(dá)到數(shù)據(jù)類型相同化、數(shù)據(jù)格式的一致化、數(shù)據(jù)存儲集中化和數(shù)據(jù)信息精練化[4]。采用Hash算法，間接取余法。公式：f（x）：= x mod maxM ； maxM一般是不太接近 2^t 的一個質(zhì)數(shù)。得余數(shù)x，根據(jù)x對源數(shù)據(jù)進(jìn)行預(yù)處理分配，采用Hash取模進(jìn)行等價映射。

（二）分布緩存

對由N臺緩存服務(wù)器組成的集群緩存把集群依次編號為0 - （N-1）。

1）hash機(jī)器節(jié)點。首先求出機(jī)器節(jié)點處的hash值，然后把它分布到0～2^32的一個圓環(huán)上（順時針分布）。如圖3-1，集群中有ABCDE五臺機(jī)器，通過hash算法把它們分布到如圖3-1所示的環(huán)上。

2）訪問方式。寫入緩存的請求，Key值為K計算器hash值為hash（K），Hash（K）對應(yīng)著圖3-1環(huán)中的某一個點。若該點沒有對應(yīng)映射到具體的某個機(jī)器節(jié)點上，就進(jìn)行順時針查找直到找到確定的目標(biāo)節(jié)點，也就是首次有映射機(jī)器的節(jié)點。Hash（K）的值介于A～B之間時，那么它命中的機(jī)器節(jié)點應(yīng)當(dāng)就是圖3-1中的B節(jié)點。

3）增加節(jié)點的處理。如圖3-1中如果在原有集群的基礎(chǔ)上想再增加一臺機(jī)器F，過程如下，首先要計算機(jī)器節(jié)點的Hash值，找到環(huán)中的一個節(jié)點，把機(jī)器映射上，如圖3-2所示。在增加機(jī)器節(jié)點F以后訪問策略不發(fā)生改變，按2）中的方式繼續(xù)訪問，那么此時仍然是不可避免的是緩存不命中的情況，hash（K）在增加節(jié)點之前不能命中的數(shù)據(jù)是落在C～F之間的數(shù)據(jù)。hash它使用了虛擬節(jié)點的思想，在圓上分配了100～200個點為其中的每一個物理節(jié)點，這樣就能較好的抑制了分布的不均勻的情況，還能最大限度減小當(dāng)服務(wù)器增減時緩存的重新分布。

{三}復(fù)用中間結(jié)果

在對海量數(shù)據(jù)進(jìn)行了預(yù)處理和分布式緩存之后，采用簡單隨機(jī)取樣[5]的方法對緩存好的數(shù)據(jù)進(jìn)行隨機(jī)取樣具體實現(xiàn)該方法。

四、實驗

本論文的實驗可以對是某地區(qū)房價數(shù)據(jù)進(jìn)行處理，簡要的過程如下：

第一數(shù)據(jù)預(yù)處理階段，首先讓每一組數(shù)據(jù)分別自動編號，然后采用取余的方法。第二根據(jù)分組情況，分別把各組數(shù)據(jù)放置到不同的服務(wù)器上。第三采用簡單隨機(jī)取樣的方法對緩存好的數(shù)據(jù)進(jìn)行隨機(jī)取樣，選擇出最適合的房產(chǎn)。

五、結(jié)束語

本文在算法方面也還有一些不足之處，有待深入的分析。目前海量數(shù)據(jù)的處理還有很多值得深入研究和挖掘的地方，還將會是熱門的話題以及更多專家學(xué)者熱衷研究的方向。

【參考文獻(xiàn)】

[1] John Gantz， David Reinsel .The 2011 Digital Universe study： Extracting Value from Chaos [J]. International Data Corporation （IDC）， 2011

[2]陳康，鄭緯民.云計算：系統(tǒng)實例與研究現(xiàn)狀[J].軟件學(xué)報，2009，20（5） ：1337 -1348.

[3]D. Romano， Data Mining Leading Edge： Insurance&Banking， InProceedings of Knowledge Discovery and Data Mining， Unicorn， BrunelUniversity， 1997.

[4]劉軍強(qiáng)，高建民，李言等.基于逆向工程的點云數(shù)據(jù)預(yù)處理技術(shù)研究.現(xiàn)代制造工程.2005.7： 73-75.

[5]Jiawei Han， Micheline Kambe；著，范明，孟小峰，數(shù)據(jù)挖掘概念與技術(shù)機(jī)械工業(yè)出版社，2001.