王磐++李勛++張濤

摘要：Hadoop是當(dāng)前處理大數(shù)據(jù)環(huán)境的一套生態(tài)系統(tǒng)，按照層次結(jié)構(gòu)為節(jié)點(diǎn)內(nèi)的HDFS，根據(jù)該FS特性編寫的RPC，MapReduce框架，Yarn管理系統(tǒng)，其中各層次可細(xì)分或進(jìn)行全層次結(jié)構(gòu)的整合，如HBase關(guān)注于數(shù)據(jù)存儲(chǔ)方向，使用其中HDFS和RPC通訊對(duì)鍵值對(duì)數(shù)據(jù)進(jìn)行轉(zhuǎn)換并實(shí)現(xiàn)分布式存儲(chǔ)，Spark關(guān)注于數(shù)據(jù)高速運(yùn)算，通過(guò)高速緩存內(nèi)存直接向上作用于RPC的機(jī)制和Yarn對(duì)資源的管理進(jìn)行實(shí)時(shí)的分布式計(jì)算。該文根據(jù)在大數(shù)據(jù)中的快速進(jìn)行有需求抽樣的需求，對(duì)存儲(chǔ)于HDFS中的大規(guī)模非結(jié)構(gòu)化數(shù)據(jù)，RPC機(jī)制，及MapReduce中Map模塊做深入研究。

關(guān)鍵詞：Hadoop；大數(shù)據(jù)；隨機(jī)抽樣

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）20-0009-03

1 概述

在對(duì)海量數(shù)據(jù)進(jìn)行數(shù)據(jù)建模時(shí)，通常會(huì)遇到性能與耗時(shí)的問(wèn)題，由于部分的數(shù)據(jù)建模算法是不可并行的，例如迭代，所以需要對(duì)數(shù)據(jù)進(jìn)行預(yù)處理來(lái)大幅減少耗時(shí)。在傳統(tǒng)數(shù)據(jù)分析流程中，數(shù)據(jù)抽樣是一個(gè)較為通用的方法，但海量數(shù)據(jù)中不一定適用，因此本文提出了一種在Hadoop生態(tài)環(huán)境下的海量數(shù)據(jù)抽樣算法。本文將在第一章介紹技術(shù)背景，第二章闡述海量數(shù)據(jù)抽樣的可行性，第三章提供具體的技術(shù)路線及實(shí)現(xiàn)方法，最后進(jìn)行驗(yàn)證和總結(jié)。

1.1 背景

Hadoop目前已經(jīng)更新在2.x的線路中，2.x引入最重要的機(jī)制是包含了MapReduce 2.0的Yarn架構(gòu).MRv2最基本的設(shè)計(jì)思想是將JobTracker的兩個(gè)主要功能，即資源管理和作業(yè)調(diào)度/監(jiān)控分成兩個(gè)獨(dú)立的進(jìn)程。在該解決方案中包含兩個(gè)組件：全局的ResourceManager（RM）和與每個(gè)應(yīng)用相關(guān)的ApplicationMaster（AM）[1]。這里的“應(yīng)用”指一個(gè)單獨(dú)的MapReduce作業(yè)或者DAG作業(yè)。[9]RM和與NodeManager（NM，每個(gè)節(jié)點(diǎn)一個(gè)）共同組成整個(gè)數(shù)據(jù)計(jì)算框架。RM是系統(tǒng)中將資源分配給各個(gè)應(yīng)用的最終決策者。AM實(shí)際上是一個(gè)具體的框架庫(kù)，它的任務(wù)是“與RM協(xié)商獲取應(yīng)用所需資源”和“與NM合作，以完成執(zhí)行和監(jiān)控Task的任務(wù)”?？傊哂辛己玫牟⑿心芰Φ痪邆鋵?duì)總體的可見性。

1.2 抽樣在統(tǒng)計(jì)分析及數(shù)據(jù)挖掘中的意義

抽樣是非全面的對(duì)數(shù)據(jù)進(jìn)行分析，從研究的總體中按隨機(jī)原則抽取部分單位作為樣本研究，并根據(jù)這部分?jǐn)?shù)據(jù)的分析結(jié)果來(lái)推斷總體，以達(dá)到認(rèn)識(shí)總體的一種統(tǒng)計(jì)方法。使用抽樣的條件：

1）用于不可能或不必要進(jìn)行全面分析的總體特征的推斷。

2）用于分析模型的評(píng)價(jià)和驗(yàn)證。

抽樣調(diào)查與大數(shù)據(jù)分析是有差別的，最大差別來(lái)源于數(shù)據(jù)表達(dá)上：前者抽樣調(diào)查，后者全面記錄；統(tǒng)計(jì)調(diào)查具有科學(xué)性、準(zhǔn)確性、權(quán)威性。大數(shù)據(jù)具有不確定性、復(fù)雜性。就像望遠(yuǎn)鏡讓我們能夠感受宇宙，顯微鏡觀測(cè)微生物一樣，成為新發(fā)明和新服務(wù)的源泉。大數(shù)據(jù)與統(tǒng)計(jì)數(shù)據(jù)相互佐證，差異較大。從大數(shù)據(jù)理論的最終要解決問(wèn)題出發(fā)，大數(shù)據(jù)分析與傳統(tǒng)的統(tǒng)計(jì)分析完全不同，其分析內(nèi)容不再是總體或群體特征，而是對(duì)個(gè)體特征的預(yù)測(cè)，是不需要進(jìn)行抽樣的。大數(shù)據(jù)分析的目的是直接匹配答案，是不需要理解和解釋原因的分析理念。[2]現(xiàn)在環(huán)境存在兩個(gè)問(wèn)題：1）能夠獲取的數(shù)據(jù)永遠(yuǎn)僅是數(shù)據(jù)的一部分。2）數(shù)據(jù)的處理能力遠(yuǎn)不及數(shù)據(jù)的產(chǎn)生能力。

所以在這個(gè)階段依然需要使用傳統(tǒng)的數(shù)學(xué)模型，進(jìn)行抽樣，建模，擬合預(yù)測(cè)。同樣，存在這個(gè)問(wèn)題還有大數(shù)據(jù)的排序。[3]在調(diào)查研究中發(fā)現(xiàn)，有許多利用大數(shù)據(jù)工具對(duì)數(shù)據(jù)進(jìn)行排序的算法和相關(guān)研究。并且著名的TERASORT也依賴于Hadoop原生的隨機(jī)抽樣算法。

2 分布式系統(tǒng)下的抽樣可行性

2.1 非分布式數(shù)據(jù)的抽樣方法

通常需要抽樣的情況都知道總體的大小，某屬性的范圍，例如從A中根據(jù)A1屬性進(jìn)行x隨機(jī)因子的分層隨機(jī)抽樣：1.計(jì)算size（A）；2.計(jì)算x*size（A），計(jì)算A1各值在x*size（A）中的占比；3.對(duì)每個(gè)標(biāo)記A1值的子集進(jìn)行抽樣，合并。

2.2 蓄水池抽樣算法

在大數(shù)據(jù)中，需要進(jìn)行額外的一次數(shù)據(jù)遍歷才能知道總量，甚至在有實(shí)時(shí)增量的數(shù)據(jù)中，知道總量是不可實(shí)現(xiàn)的，通常的解決方法是蓄水池抽樣（Reservoir Sampling）：從N個(gè)元素中隨機(jī)的等概率的抽取k個(gè)元素，其中N無(wú)法確定。

算法流程描述為圖1：

2.3 MapReduce數(shù)據(jù)處理模型

在海量數(shù)據(jù)中不知道數(shù)據(jù)總體的大小，數(shù)據(jù)總體不在同一片存儲(chǔ)區(qū)，各存儲(chǔ)區(qū)容量可能不同，無(wú)法用傳統(tǒng)抽樣方法或蓄水池法。使用MapReduce處理數(shù)據(jù)包含以下幾個(gè)階段，以WordCount為例，圖2描述了在整個(gè)文章集中各個(gè)單詞出現(xiàn)數(shù)量的統(tǒng)計(jì)過(guò)程。

數(shù)據(jù)存儲(chǔ)在HDFS中是以BLOCK存在的，每個(gè)BLOCK有固定的大小及對(duì)應(yīng)索引。在進(jìn)入MapReduce程序處理前，形成建立KV值，根據(jù)當(dāng)前集群的負(fù)載情況分成不定數(shù)的Split給Map處理。[6]Split記錄的只是該片在文件中的起始字節(jié)偏移量，數(shù)據(jù)的長(zhǎng)度，以及該Split所包含的第一個(gè)BLOCK所在的主機(jī)地址，而對(duì)文件的操作是從“一個(gè)具體的Input”的層面來(lái)讀寫數(shù)據(jù)，而不是從“一個(gè)BLOCK”的層面來(lái)讀取數(shù)據(jù)。每臺(tái)主機(jī)在Map階段處理的僅是文件的某個(gè)片段，所以還需要一個(gè)對(duì)片段的結(jié)構(gòu)描述，例如LineRecordReader，CSVRecordReader等，同樣也可自定義RecordReader。

單個(gè)Map-Reduce任務(wù)的執(zhí)行過(guò)程以及數(shù)據(jù)輸入輸出的類型如下所示：

Mapper的四個(gè)方法是setup，map，cleanup和run。其中，setup和cleanup用 于管理Mapper生命周期中的資源，setup在完成Mapper構(gòu)造，即將開始執(zhí)行map動(dòng)作前調(diào)用，cleanup則在所有的map動(dòng)作完成后被調(diào) 用。方法map用于對(duì)一次輸入的key/value對(duì)進(jìn)行map動(dòng)作。run方法執(zhí)行了上面描述的過(guò)程，它調(diào)用setup，讓后迭代所有的key /value對(duì)，進(jìn)行map，最后調(diào)用cleanup。Combine，Reduce的周期基本一致，在簡(jiǎn)單抽樣的過(guò)程中，僅需要利用其setup和cleanup階段進(jìn)行數(shù)據(jù)掃描。

2.4 非等概率隨機(jī)命中方法

大數(shù)據(jù)分而治之的思想無(wú)處不在，隨機(jī)抽樣也是如此，大數(shù)據(jù)在存儲(chǔ)時(shí)已使用自身的算法對(duì)數(shù)據(jù)進(jìn)行排序和索引。所以每個(gè)Split中的數(shù)據(jù)認(rèn)為是均勻的，所以僅利用Map的抽樣方法描述為：

對(duì)于樣本數(shù)固定的抽樣，在setup階段利用近似估計(jì)法產(chǎn)生對(duì)應(yīng)split中的隨機(jī)數(shù)據(jù)的概率表，在cleanup中寫入溢寫區(qū)。

樣本數(shù)為總體的百分比：

在setup階段利用使用泊松分布計(jì)算某樣本被選中的概率是否滿足成為候選者，并記錄下候選者。

setup階段完成可知道某個(gè)split對(duì)應(yīng)的樣本總數(shù)。

cleanup階段計(jì)算需要補(bǔ)足或刪掉的候選者，由于候選數(shù)據(jù)是隨機(jī)抽取完成，再次加入極少量數(shù)據(jù)不影響大數(shù)據(jù)下的隨機(jī)性。[7]

3 抽樣算法的實(shí)現(xiàn)

context.getConfiguration 獲取抽樣比例λ，數(shù)據(jù)結(jié)構(gòu)描述，抽樣方式參數(shù)組，偽代碼描述：

3.1 抽樣參數(shù)

一致性隨機(jī)抽樣可以使用偽隨機(jī)，在BLOCK存儲(chǔ)的數(shù)據(jù)是固定不變的使用隨機(jī)種子可保證多次抽樣結(jié)果一致。無(wú)放回的隨機(jī)抽樣中，需要保證每個(gè)獨(dú)立樣本如果可能被抽到，僅被抽到一次。上述算法描述即為無(wú)放回抽樣。有放回隨機(jī)抽樣在Map中利用KeyValue值，在setup中通過(guò)泊松分布生成第一組隨機(jī)數(shù)，該數(shù)字稱為飛鏢[8]，在cleanup中對(duì)所有的飛鏢再進(jìn)行一次隨機(jī)“射擊”可保證每次“射擊”都是該split中的全體數(shù)據(jù)集。

3.2 驗(yàn)證及性能優(yōu)化

我們知道等概率的選取的樣本應(yīng)該滿足正態(tài)分布，而正態(tài)分布的確定需要兩個(gè)參數(shù) λ和均值，其中的均值是無(wú)法得知的，而正態(tài)分布是二項(xiàng)分布的連續(xù)，從個(gè)體樣本的選擇出發(fā)僅有兩種，備選和排除。在大數(shù)據(jù)中，假設(shè)數(shù)據(jù)量是足夠大的，因此抽樣過(guò)程可以描述為二項(xiàng)分布的極限情況，這正好符合泊松分布，參考圖3在λ越大時(shí)，其分布圖形趨近于正態(tài)分布，對(duì)應(yīng)隨機(jī)抽樣分布：

根據(jù)德莫佛-拉普拉斯（De'Moivre-Laplace）中心極限定理，這列二項(xiàng)分布將趨近于正態(tài)分布。

合適的配置集群環(huán)境，數(shù)據(jù)處理速度影響最大的是非寄存器級(jí)的IO，所以分布的數(shù)據(jù)并非越多主機(jī)性能越優(yōu)，在抽樣過(guò)程的處理中，考慮到CPU高速緩存的處理速度大概是磁盤IO的10～100倍，及系統(tǒng)正常的負(fù)載，使用每個(gè)節(jié)點(diǎn)同時(shí)處理的MAP數(shù)量控制在10個(gè)。使用LZO壓縮，MAP直接輸出并未使用中間輸出，不需要對(duì)緩存結(jié)果進(jìn)行壓縮和網(wǎng)絡(luò)傳輸。調(diào)整Map和Reduce的數(shù)量到合適的值。根據(jù)分析邏輯使用Combiner使用最合適的Writable類型，無(wú)中間結(jié)果，重用Writable類型。

在節(jié)點(diǎn)內(nèi)，各MAP再次分配對(duì)應(yīng)64M的內(nèi)存作為高速緩存，其中所有的local變量全部使用靜態(tài)[7]。分析Task的運(yùn)行

4 結(jié)束語(yǔ)

本文對(duì)應(yīng)工程僅使用平均200秒完成對(duì)10^8條數(shù)據(jù)，共200G的數(shù)據(jù)的遍歷，并僅使用一次遍歷完成對(duì)工程未知規(guī)模數(shù)據(jù)的抽樣。并通過(guò)100次20%的抽樣對(duì)抽樣的分布進(jìn)行了擬合驗(yàn)證，驗(yàn)證結(jié)果表明完全符合泊松分布，測(cè)試曲線近似于正態(tài)分布，擬合度大于98%，符合在本文所處工程中的要求。

參考文獻(xiàn)：

[1] Tom White. 華東師范大學(xué)數(shù)據(jù)科學(xué)與工程學(xué)院， 譯. Hadoop權(quán)威指南3版[M]. 北京： 清華大學(xué)出版社， 2015.

[2] 李建江， 崔健， 王聃， 等. MapReduce并行編程模型研究綜述[J]. 電子學(xué)報(bào)， 2011（11）.

[3] 陳德華， 解維，李悅. 面向大規(guī)模圖數(shù)據(jù)的分布式并行聚類算法研究[C]//第29屆中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集（B輯）（NDBC2012）. 2012.

[4] ADAMS A， JACOBS D， DOLSON J，et al.The frankencamera： an experimental platform for computational photography. ACM SIGGRAPH 2010 papers，2010：1-12.

[5] DEAN J， GHEMAWAT S. Mapreduce： Simplified data processing on large clusters[J]. Communications of the ACM， 2008， 51（1）： 107-113.

[6] GHEMAWAT S， GOBIOFF H.The google file system[C]. ACM SIGOPS Operating， 2003.

[7] 李超越， 徐國(guó)勝. Hadoop公平調(diào)度算法的改進(jìn)[C]//第十九屆全國(guó)青年通信學(xué)術(shù)年會(huì)論文集. 2014.

[8] 白永超， 付偉，辛陽(yáng). 基于Hadoop和Nutch的分布式搜索引擎研究與仿真[C]//第十九屆全國(guó)青年通信學(xué)術(shù)年會(huì)論文集. 2014.

[9] 范東來(lái). Hadoop海量數(shù)據(jù)處理 技術(shù)詳解與項(xiàng)目實(shí)戰(zhàn)[M].北京：人民郵電出版社， 2015.