海量數(shù)據(jù)實(shí)時(shí)處理算法設(shè)計(jì)與分析

李敏

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

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

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

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

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

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

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

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

三、對(duì)MapReduce改進(jìn)

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

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

（二）分布緩存

對(duì)由N臺(tái)緩存服務(wù)器組成的集群緩存把集群依次編號(hào)為0 - （N-1）。

1）hash機(jī)器節(jié)點(diǎn)。首先求出機(jī)器節(jié)點(diǎn)處的hash值，然后把它分布到0～2^32的一個(gè)圓環(huán)上（順時(shí)針?lè)植迹Ｈ鐖D3-1，集群中有ABCDE五臺(tái)機(jī)器，通過(guò)hash算法把它們分布到如圖3-1所示的環(huán)上。

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

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

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

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

四、實(shí)驗(yàn)

本論文的實(shí)驗(yàn)可以對(duì)是某地區(qū)房?jī)r(jià)數(shù)據(jù)進(jìn)行處理，簡(jiǎn)要的過(guò)程如下：

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

五、結(jié)束語(yǔ)

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

【參考文獻(xiàn)】

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

[2]陳康，鄭緯民.云計(jì)算：系統(tǒng)實(shí)例與研究現(xiàn)狀[J].軟件學(xué)報(bào)，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)，高建民，李言等.基于逆向工程的點(diǎn)云數(shù)據(jù)預(yù)處理技術(shù)研究.現(xiàn)代制造工程.2005.7： 73-75.

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